ПРАКТИЧЕСКОЕ ВВЕДЕНИЕ В ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных работ

.

Данные методические указания содержат описание интерпретатора muLisp, а также основные конструкции и приемы программирования на языке Лисп. программирования (Пролог), объектно-ориентированного программирования (C++, Смолток). Изучение функционального програм-мирования не входило в программы обучения. Между тем сегодня не приходится убеждать в достоинствах языка Лисп. На этом языке написано все математическое обеспечение системы инженерного проектирования AUTOCAD, целый ряд других программ, созданных в области искус-ственного интеллекта. Небольшой объем теоретического курса по функциональному программированию в какой-то степени дополняется кратким теоретическим введением к каждой лабораторной работе.

Понимание изложенного материала не требует от студентов знания других языков программирования.

Лабораторная работа №1

В лабораторной работе №1 исследуются символьные структуры данных, которые представляются как объекты - составляющие muLISP. Объекты могут быть простыми или составными Простые объекты данных - это атомы . Они неделимы . Имя атома - это строка символов . Например:

APPLE RABBIT 54321 -41

Составные объекты данных - это списки . Списки состоят из нуля или более объектов, которые могут быть как простыми , так и составными . Пример списка, состоящего из четырех элементов:

(THE QUICK BROWN FOX)

Эти объекты используют для создания символьных структур данных , которыми оперируют функции muLISP . Чистый muLISP снабжен следующими 5 функциями для работы с объектами:

1. (CAR список) - функция выборки, которая возвращает первый элемент <списка>;

2. (CDR список) - функция выборки, которая возвращает все элементы <списка>, кроме первого;

3. (CONS объект список) - функция создания, которая возвращает список и CAR от этого списка есть <объект>, а CDR - <список>;

4. (EQL aтом1 атом2) - функция сравнения, которая возвращает T, если <aтом1> и <атом2> представляют собой один и тот же атом, в противном случае функция возвращает NIL; эта функция определена в том случае, когда оба ее аргумента являются атомами.

5. (ATOM объект) - функция распознавания, которая возвращает T, если объект является атомом, и NIL в противном случае.

В muLISP для вызова функций принят следующий формат:

(name arg1 arg2 ...)

где <name> - имя функции, <arg1> - первый аргумент, <arg2> - второй и т.д.

Взаимодействие с muLISP: вначале вы вводите выражение, которое должно следовать за знаком $, затем muLISP читает выражение, оценивает его и выдает результат. Для предотвращения оценки выражения вы должны поставить апостроф перед выражением. Пример:

$ 'APPLE

Введите свое имя атома, выбрав предварительно опцию Break. Для продолжения наберите (RETURN) и нажмите клавишу <ENTER>.

BREAK

Задание к выполнению лабораторной работы.

1. Используя комбинации CAR и CDR, выберите из списка

((Height 72) (weight 175) (hair blond)) элемент 175

2. Выполните присоединение (EYES BROWN) к ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).

2. Выполните присоединение (EYES BROWN) к ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).

3. Заданы два списка. Включите второй элемент первого списка во второй список.

4. Используя функции CAR, CDR и EQL, посмотрите, равен ли

WEIGHT (вес), точно определенный в списке

((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)) , 175.

Лабораторная работа №2

В лабораторной работе №2 изучаются возможности определения функций, условные операторы и определение рекурсивных функций.

В чистом muLISP выражения вида

(DEFUN name (arg1 arg2 ...)

task1

task2

... )

используются для определения функции, называемой <name>. DEFUN (DEfine FUNction) дает описанию функции имя <name>, позволяющее ссылаться на функцию из других вызовов. Атомы <arg1>, <arg2>,...- формальные аргументы функции. Тело функции состоит из одного или более операторов (task_i).

Рассмотрим примеры функций.

$ (DEFUN FIRST (LST)

(CAR LST) )

FIRST возвращает первый аргумент списка <LST>. Например:

$ (FIRST '(DOG CAT COW PIG))

В чистом muLISP операторы, составляющие тело функции, бывают простыми и условными. Простой оператор - это оператор, являющийся атомом или списком, CAR которого есть атом. Пример:

(CONS ATM LST)

Условный оператор - это оператор, являющийся списком, CAR которого - не атом. Пример:

((ATOM EXPN) (CONS EXPN LST))

CAR условного оператора - условный предикат. Если предикат возвращает NIL, значение условного оператора также будет NIL, оценивается значение следующего оператора, иначе оценивается CDR условного оператора.

(DEFUN LISTP (OBJ)

((ATOM OBJ) NIL) T )

Задание к выполнению лабораторной работы

1. Определить функцию THERD выбора третьего элемента списка LST.

2. Определите функцию NULL, которая возвращает Т, если ее аргумент есть пустой список (т.е. NIL), в противном случае возвращается NIL.

3. Переопределите LISTP так, чтобы она возвращала Т , когда вы зададите ей нулевой список .

4. Определите рекурсивную функцию MBR (от двух аргументов) выбора конкретного члена из списка имен. При определении функции используйте следующий алгоритм:

а. Если список - NULL, возврат NIL. Имя не является членом нулевого списка.

b. Если имя - EQL с CAR от списка(имя сопоставимо с CAR от спис-ка), то возврат Т. Имя является первым членом списка.

c. Если имя не является EQL с CAR от списка, то возврат - значение возвращенное процедурой, примененной к CDR от списка .Имя является членом списка тогда, когда оно является членом CDR от списка .

5. Определите рекурсивную функцию EQLIST, которая возвращает Т, если два списка, состоящие из атомов, равны. Иначе возвращается NIL. При определении функции используйте следующий алгоритм:

а. Если первый список - NULL, возврат: проверка второго списка.

b. Если второй список - NULL, возврат: NIL .

c. Если NOT EQL CAR от первого списка с CAR от второго, возврат: NIL .

d. Возврат: EQLIST CDR от первого списка с CDR от второго.

Необходимо определить и NOT - предикатную функцию, которая возвращает T, если ее аргумент есть NIL.

Замечание.

1. Определенные ранее функции в сеансе работы сохраняются и их переопределять для выполнения задания 5 не нужно.

2. Выполнение рекурсивных функций рекомендуется посмотреть в режиме TRACE. Для этого перед выполнением необходимо ввести

строку (TRACE <имя функции₁> <имя функции₂>...), где имя функции_i - функции, входящие в тело определения. Например, для MBR - это (TRACE MBR), а для EQLIST - (TRACE EQLIST NULL NOT). Это даст возможность проследить все шаги рекурсии.