ФИЛП практика (Мет пособие)

Содержание

Часть 1 : “Язык программирования Лисп” 1. Основы программирования на языке Лисп……………………………....2

1.1Представление данных в Лиспе…………………………………….....2

1.2Лямбда-исчисление и функциональное программирование…….…..3 1.3 Пример простейшей программы на языке Лисп………………….….5

2. Функции Лиспа………………………………………………………….…7

2.1 Функции отбора………………………………………………………..7

2.2. Функции конструктора………………………………………………..8

2.3 Функции компаратора…………………………………………………10

2.4Функции распознавателя……………………………………………..12

2.5Функции назначения………………………………………………….13

2.6 Логические функции………………………………………………….15

2.7Числовые функции……………………………………………………16

Виды рекурсии…………………………………………………………….22

Задания к лабораторным работам по языку программирования ЛИСП…25

Часть 2

Лабораторная работа №1……………………………………………………..28

Лабораторная работа №2……………………………………………………..32

Лабораторная работа №3……………………………………………………..36

Лабораторная работа №4……………………………………………………..39

Лабораторная работа №5……………………………………………………..45

Литература…………………………………………………………………….50

2

Часть 1 “Язык программирования Лисп”

1.Основы программирования на языке Лисп

1.1Представление данных в Лиспе

Данные в Лиспе представляются атомами, списками, консами, символьными выражениями. Взаимосвязь понятий иллюстрируется рис. 1.

Символьные выражения

Атомы

Консы

Символы Списки

T NIL

Числа

Рис.1 символьные выражения Лиспа Атомы, простейшие объекты Лиспа, делятся на символьные и числовые.

Символьный атом - это последовательность букв, цифр и возможно специальных символов, например, X1, Gruppa-11, ABCD. Числовой атом - это последовательность цифр, например, 2, -75, 355. В числовом атоме могут присутствовать символы '+', '-', '.', '/', например –11, +55.473, 2/5. Числовые атомы интерпретируются как константы, символьные - как константы и как переменные. Атом T обозначает логическое значение "истина", атом NIL - логическое значение "ложь" или пустой список.

Последовательность элементов, разделенных пробелами и заключенных в круглые скобки, является списком. Элементами списка могут быть любые объекты: атомы, списки, консы, например, (1 a 2 b 3 c), ((x1 0) (x2 1)), ((y . blue) (z . yellow)). Пустой список не содержит элементов и обозначается ( ) или NIL. Таким образом, список - это многоуровневая или иерархическая структура данных, в которой открывающие и закрывающие скобки находятся в строгом

3

соответствии. Например, приведенные ниже выражения являются правильно составленными списками:

(+ 2 3) - список из трех элементов;

(((((первый) 2) третий) 4) 5) - список из двух элементов.

Список, в котором нет ни одного элемента, называется пустым списком и обозначается "( )" или символом NIL. Пустой список - это не то же самое, что "ничего". Он выполняет ту же роль, что и ноль в арифметике. NIL может быть, например, элементом других списков:

NIL	то же, что и ( );
(NIL)	список, состоящий из атома NIL;
(( ))	то же, что и (NIL);
((( )))	то же, что и ((NIL));

(NIL ( ) ) список из двух пустых списков.

Пара элементов, разделенных точкой и заключенных в круглые скобки, называется консом, или точечной парой. Список (e1 e2 … en) может быть представлен суперпозицией консов - (e1 . (e2 . (… (en . NIL) …))).

Символьным выражением в Лиспе является один из следующих объектов: - атом, список (s1…sn) или конс (s1.s2), где s1, s2, …, sn - символьные выражения. Например, (S3 (T . L) . (a c)) является символьным выражением.

Сложные структуры в Lisp представляются с использованием списочных ячеек(рис.2а). Так, конс (a.b) представляется одной списочной ячейкой (рис.2б), в то время как список (a b) представляется двумя ячейками (рис.2в).

Первый элемент списка называется головой (head), а остаток списка, т.е. список без первого его элемента, называется хвостом списка (tail). Левая часть списочной ячейки указывает на голову списка (или левую часть конса), а правая – на хвост списка (или правую часть конса). При помощи селекторов CAR и CDR можно выделить из списка его голову и хвост.

В Лиспе формы представления программы и обрабатываемых ею данных одинаковы и представляются списочной структурой. Списки, представляющие программы и данные, состоят из списочных ячеек, расположение и порядок которых в памяти несущественный. Структура списка определяется логически на основе имен символов и указателей. Добавление новых элементов в список или удаление из списка может производиться без переноса списка в другие ячейки памяти. Резервирование и освобождение могут в зависимости от потребности осуществляться динамически, ячейка за ячейкой.

4

CAR CDR

a)

(a . b)

b

a

б)

(a b)

a

в)

b

Рис.2 Представление объектов Лиспа (а -списочная ячейка, б- конс, с-список).

1.2 Лямбда-исчисление и функциональное программирование

Определение функций и их вычислений в Лиспе основано на лямбдаисчислении (lambda calculus) Черча. Лямбда-выражение - это определение вычислений и параметров функции в чистом виде, то есть без фактических параметров или аргументов, которое имеет вид

(LAMBDA (x1 x2…xn) fn)

Символ LAMBDA обозначает, что мы имеем дело с определением функции. Символы xi язвляются формальными параметрами (formal parameter) определения, которые именуют аргументы в описывающем вычисления теле (body) функции fn. Входящий в состав формы список, образованный из параметров, называется лямбда-списком (lambda list).

Телом функции является произвольная форма, значение которой может вычислить интерпретатор Лиспа, например: константа, связанный со значением символ или композиция из вызовов функций.

В математике и обычных языках программирования вызов функции записывается, как правило, в так называемой префиксной записи (нотации), в которой имя функции стоит перед скобками, окружающими аргументы:

5

f(x), g(x,y), h(x, g(y,z))

Определение функции в языке Лисп позволяет задать произвольное вычислимое отображение. Например, функцию, вычисляющую сумму квадратов, можно определить с помощью сложения и умножения:

(defun сумма_квадратов (x y) (+ (* x x) (* y y)))

имя –сумма_квадратов; аргументы - x, y; значение – x*x+y*y. Используя лямбда-выражение, данную функцию можно записать

(lambda (x y) (+ (* x x) (* y y)))

Здесь x и y – формальные параметры, представляющие произвольные числа. Формальность параметров означает, что их можно заменить на любые другие символы, и это не отразится на вычислениях, определяемых функцией. Именно это и скрывается за лямбда-нотацией.

Вызов функции обозначает запуск, или применение определения функции к конкретным значениям аргументов. Например, применим функцию суммаквадратов к фактическим аргументам x =2 и y =3:

(cумма_квадратов 3 4) → 25.

Используемое в Лиспе функциональное программирование основывается на том, что в результате каждого действия возникает значение. Значения становятся аргументами следующих действий и конечный результат всей задачи выдается пользователю. Программы строятся из логически расчлененных определений функций. Кроме функционального программирования в Лиспе можно использовать программирование, основанное на обычном последовательном исполнении операторов с присваиваниями, передачами управления и специальными операторами цикла.

ВЛиспе существуют специальные функции, которые проверяют наличие

усимвольного выражения некоторого свойства, которые называются предикатом. Другими словами, предикат - это функция, которая определяет, обладает ли аргумент определенным свойством и возвращает в качестве значения "ложь" (или NIL) в случае, если аргумент не обладает этим свойством, и "истина" (или T) в противном случае.

6

1.3 Пример простейшей программы на языке Лисп.

Одно из самых важных понятий для Lisp-программирования – рекурсия. Функция называется рекурсивной, если вызывает сама себя. Каждая рекурсивная функция содержит 2 ветви: рекурсивную (вход в рекурсию) и нерекурсивную (выход). Идея рекурсии – вычисление функции можно свести к вычислению этих же функций, но с более простыми аргументами. Рекурсия бывает простая и сложная.

Вкачестве примера использования простой рекурсии определим функцию, которая вычисляет факториал целого числа n. Для этого необходимо перемножить все числа от 1 до n. Из математики известно, что n!=n(n-1)!, то есть факториал n равен произведению n и факториала от (n-1) Запишем определение функции, считая что 0!=1

(defun fact (n)

(cond (zerop n) 1)

(t (* n (fact (- n 1)))))

где defun – зарезервированное слово, выполняет те же функции, что и function в языке программирования Pascal; cond – оператор, примерно аналогичный оператору switch в С/С++, подробнее будет рассмотрен ниже; zerop – возвращает T, если n=0.

Вданном примере функция fact рекурсивно вызывает сама себя с аргументом, который на 1 меньше значения предыдущего вызова. Рекурсивный вызов продолжается до тех пор, пока значение аргумента не станет равно 0.

(fact 3)	(3*fact(2))	3*2=6
	(2*fact(1))	2*1=2
	(1*fact(0))	1*1=1

7

2. Функции Лиспа

2.1 Функции отбора

1). Функция CAR [ object ] возвращает car-элемент <объекта> (т.е. объект данных, на который указывает car-элемент <объекта>). Корректная интерпретация car-элемента объекта зависит от того, является ли объект атомом, а если нет, рассматривается ли он как список или бинарное дерево. Если объект - атом, то его car-элемент есть текущее значение атома. Если объект - список, его car-элемент есть первый элемент списка. Если объект - бинарное дерево, его car-элемент есть левая ветвь дерева, или car-ветвь.

(CAR '(A B C D E)) --> A (CAR '((A.B) . C)) --> (A.B) (SETQ NUM 7) --> 7 (CAR 'NUM) --> 7

2)Функция CDR [object] возвращает cdr-элемент <объекта> (т.е. объект данных, на который указывает cdr-элемент <объекта>). Корректная интерпретация cdr-элемента объекта зависит от того, является ли объект атомом, списком или бинарным деревом. Если объект - символ, его cdr-элемент есть список свойств символа. Если объект - число, его cdr-элемент указывает признак и тип числа . Если объект - список, его cdr-элемент есть остаток списка (т.е. все, кроме последнего, элементы списка). Если объект - бинарное дерево, его cdr-элемент есть правая ветвь дерева, или cdr-ветвь.

(CDR '(A B C)) -->(B C) (CDR '((A.B) . C)) --> C

3)Функция LAST [list] возвращает последний на верхнем уровне cons <списка>. Отметим, что LAST возвращает последний cons, но не последний элемент <списка>. Если <список> есть атом, LAST возвращает признак NIL. Как показано на примере, последний элемент может извлекаться путем использования функции CAR от (LAST list)

(LAST '(A B C D)) --> (D) (LAST '(A B C . D)) --> (C . D) (LAST 'F) --> NIL

(CAR (LAST '(A B C))) --> C

4)Функция NTHCDR [n,list] ) возвращает n-й cdr элемент <списка>.

Если <список> имеет n или меньше элементов или n≤0, то возвращается NIL.

(NTHCDR 0 '(A B C D)) --> (A B C D)

(NTHCDR 1 '(A B C D)) --> (B C D)

(NTHCDR 2 '(A B C D)) --> (C D)

8

(NTHCDR 5		'(A B C D)) -->	NIL
(NTHCDR 2		'(A B . C)) --> C
5) Функция NTH [n,list]			возвращает n-й элемент <списка>. Если
<список> имеет n или меньше элементов или n≤0, то возвращается NIL.
(NTH 0	'(A B C D)) --> A
(NTH 3	'(A B C D)) --> D
(NTH 4	'(A B C D)) --> NIL
(NTH 2	'(A B . C)) --> NIL

2.2.Функции конструктора.

1)Функция CONS [object1, object2] возвращает cons, у которого carэлемент указывает на <обьект1>, а cdr-элемент - на <обьект2>. Если значение *FREE-LIST* есть cons, CONS модифицирует и возвращает этот cons и приводит *FREE-LIST* к cdr *FREE-LIST*. Корректная интерпретация (СONS обьект1 обьект2) зависит от того, как рассматривается <обьект2>. Если <обьект2> - список, CONS создает список, первым элементом которого является <обьект1>, а остатком - <обьект2>. Если <обьект2> - атом или бинарное дерево, CONS создает дерево, у которого левая ветвь, или car-ветвь есть <обьект1>, а правая ветвь, или cdr-ветвь - <обьект2>.

(CONS 'A '(B C D)) --> (A B C D) (CONS 'A 'B) --> (A . B)

2)Функция ACONS[key,object,alist] создает пару (ключ.объект), располагает ее в начале ассоциативного списка и возвращает результирующий ассоциативный список. ACON упрощает процесс создания ассоциативных списков.

(ALIST 'EYES 'BLUE '((WEIGTH . 170) (HEIGTH . 72))) --> ((EYES . BLUE) (WEIGTH . 170) (HEIGTH . 72))

3)Функция LIST [object1,object2,..,objectn] создает и выдает список,

состоящий из элементов с <обьекта1> по <объектn>. Если функция вызвана без аргументов, то LIST возвращает признак NIL. LIST может работать с любым количеством аргументов.

(LIST 'A 'B 'C 'D) ---> (A B C D) (LIST 'A '(B C) 'D) ---> (A (B C) D) (LIST) ---> NIL

4)Функция APPEND [list1,list2,...,listn] создает и возвращает список, состоящий из элементов списков, начиная со <списка1> и по <списокn>.

9

APPEND копирует cons-ы высшего уровня каждого из своих аргументов, кроме последнего. Если функция вызывается с единственным аргументом, APPEND просто возвращает этот аргумент без его копирования. Следовательно, для копирования списка лучше использовать COPY-LIST, чем APPEND. Отметим, что APPEND использует cons-ы для копирования всех, кроме последнего, аргументов.

(SETQ FOO '(D E F)) --> (D E F)

(APPEND '(A B C) FOO '(G H I)) --> (A B C D E F G H I) FOO --> (D E F)

(APPRND '(A B C D) 'E 'F 'G) --> (A B C D . G)

5)Функция FIRSTN [n,list]. Если <n> - положительное целое, (FIRST n список) копирует и возвращает первые n элементов списка. FIRSTN возвращает NIL, если n -неположительное целое. Если <список> имеет n или более элементов, FIRSTN копирует и возвращает элементы <списка>.

(FIRSTN 0 '(SUE JOE ANN BOB)) --> NIL (FIRSTN 2 '(SUE JOE ANN BOB)) --> (SUE JOE)

(FIRSTN 4 '(SUE JOE ANN BOB)) --> (SUE JOE ANN BOB) (FIRSTN 5 '(SUE JOE ANN BOB)) --> (SUE JOE ANN BOB) (FIRSTN 2 '(A B . C) -> (A B)

(FIRSTN 3 '(A B . C --> (A B)

6)Функция REVERSE [list,object] создает и выдает список, состоящий из элементов <списка>, но в обратном порядке. (REVERSE список объект) выдает элементы <списка> в обратном порядке, присоединенные к <объекту>. Результат является таким же, как и при работе функции (APPEND (REVERSE list) object), но вызов REVERSE в качестве второго аргумента более эффективен

(REVERSE '(A B C D E))	--> (F D C B A)
(REVERSE '(A B C) '(D E F)) --> (C B A D E F)
(REVERSE '(A B C) 'D)	--> (C B A . D)

7) Функция LENGTH [object] возвращает длину <объекта>, соответствующую его типу данных. Если <объект> есть NIL или cons, то LENGTH выдает количество cons-ов высокого уровня (т.е. элементов) в объекте. Если <объект> - символ, то LENGTH выдает количество букв в Р- имени <объекта>. Если <объект> - число, LENGTH выдает количество слов (слово равно 2-м байтам), требуемых для размещения числового вектора <объекта>.

(LENGTH '(A B C D)) --> 4 (LENGTH NIL) --> 0

10

(LENGTH 'MULISP) --> 6 (LENGTH -13) --> 1

2.3Функции компаратора.

1)Функция EQ [object1, object2] проверяет на идентичность 2 своих аргумента (т.е. они указывают на одинаковые объекты данных в памяти). Так как символы и малые целые числа (т.е. целые числа, меньше 65536 по абсолютной величине) определяются уникально, EQ является хорошим способом определения, являются ли 2 символа или 2 малых целых числа равными друг другу. Функция NEQ [object1, object2] эквивалентна функции

(NOT (EQ обьект1 обьект2)). (EQ 'Alice 'Alice) --> T

(SETQ F1 '(A B C)) --> (A B C) (EQ F1 '(A B C)) --> NIL (SETQ F2 F1) --> (A B C) (EQ F1 F2) --> T

(EQ 7 (+ 3 4)) --> T

(EQ 100000 100000)--> NIL

2)Функция EQL [object1, object2]. Если <обьект1> идентичен <обьекту2> или если оба аргумента являются числами с одинаковыми значениями, то (EQL обьект1 обьект2) возвращает Т, иначе - NIL. Функция NEQL [обьект1 обьект2] эквивалентна функции (NOT (EQL обьект1 обьект2)). Т.к. большие целые числа (т.е. целые числа, больше 65536 по абсолютной величине) и дробные числа не определяются уникально, EQL по сравнению с EQ может быть гораздо эффективнее при определении эквивалентности 2-х чисел. Аргументы - не атомы являются эквивалентными тогда и только тогда, когда они указывают на одинаковые ячейки в памяти.

(EQL 'Alice 'Alice) --> T (EQL 7 (+ 3 4)) --> T (EQL 100000 100000) --> T (EQL '(A B) '(A B)) --> NIL

3)Функция: EQUAL [object1, object2]. Если <обьект1> эквивалентен <обьекту2>, функция возвращает Т, иначе - NIL. EQUAL проверяет на эквивалентность 2 своих аргумента. Если один или оба аргумента являются атомами, EQUAL работает аналогично функции EQL. Два аргумента-атома находятся в отношении EQUAL, если они являются изоморфными структурами