ЛИСП

2 Каковы типы аргументов базовых функций?

3 Какие значения они возвращают?

4 Что такое предикат?

5 Назовите основные отличия предикатов EQ, EQL, EQUAL и =.

6 Назовите отличия функций CONS и LIST.

7 Что такое символ?

8 Различия функций SET, SETQ, SETF?

9 Особенности свойств символов?

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

Тема: Определение функций. Функции ввода-вывода. Вычисления,

изменяющие структуру.

Цель: Получить навыки в написании функций. Изучить функции ввода-

вывода.

Функции, определяемые пользователем.

Функция ввода.

Функции вывода.

Вычисления, изменяющие структуру.

Задание к лабораторной работе.

Вопросы.

1. Функции, определяемые пользователем.

Определение функций и их вычисление в Лиспе основано на лямбда-

исчислении Черча.

В Лиспе лямбда-выражение имеет вид

(LAMBDA (x1 x2 ... xn) fn)

Символ LAMBDA означает, что мы имеем дело с определением функции.

Символы xi являются формальными параметрами определения, которые имеют

аргументы в описывающем вычисления теле функции fn. Входящий в состав формы

список, образованный из параметров, называют лямбда-списком.

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

вычислить интерпретатор Лиспа.

_(lambda (x y) (+ x y))

Формальность параметров означает, что их можно заменить на любые

другие символы, и это не отразится на вычислениях, определяемых функцией.

Лямбда-выражение - это определение вычислений и параметров функции в

чистом виде без фактических параметров, или аргументов. Для того, чтобы

применить такую функцию к некоторым аргументам, нужно в вызове функции

поставить лямбда-определение на место имени функции:

(лямбда-выражение а1 а2 ... аn)

Здесь ai - формы, задающие фактические параметры, которые вычисляются

как обычно.

_((lambda (x y) (+ x y)) 1 2) ( 3

Лямбда-вызовы можно свободно объединять между собой и другими

формами. Вложенные лямбда-вызовы можно ставить как на место тела лямбда-

выражения, так и на место фактических параметров.

_((lambda (x)

;Тело лямбда-вызова -

((lambda (y) (list x y)) ‘b)) ‘a) ( (a b)

лямбда-вызов.

Записывать вызовы функций полностью с помощью лямбда-вызовов не

разумно, поскольку очень скоро выражения в вызове пришлось бы повторять,

хотя разные вызовы одной функции отличаются лишь в части фактических

параметров. Проблема разрешима путем именования лямбда-выражений и

использования в вызове лишь имени.

Дать имя и определить новую функцию можно с помощью функции DEFUN:

(DEFUN имя лямбда-список тело)

DEFUN соединяет символ с лямбда-выражением, и символ начинает

представлять определенные этим лямбда-выражением вычисления. Значением этой

формы является имя новой функции.

После именования функции ее вызов осуществляется по имени и

параметрам.

_(defun list1 (x y)

(cons x (cons y nil))) ( list1

_(list1 ‘c ‘n) ( (c n)

(eval )

Функция возвращает результат выражения , где -

любое выражение языка LISP. Например, дано:

(setq a 123)

(setq b 'a)

(eval 4.0) ( 4.000000

(eval (abs -10)) ( 10

(eval a) ( 123

(eval b) ( 123

2. Функция ввода.

Лисповская функция чтения READ обрабатывает выражение целиком. Вызов

функции осуществляется в виде

_(READ)

(Вводимое выражение) ( ;выражение пользователя

( (ВВОДИМОЕ ВЫРАЖЕНИЕ) ;значение функции READ

...

Функция не показывает, что она ждет ввода выражения. Она лишь читает

выражение и возвращает в качестве значения само это выражение, после чего

вычисления продолжаются.

Если прочитанное выражение необходимо сохранить для дальнейшего

использования, то вызов READ должен быть аргументом какой-нибудь формы,

например присваивания (SETQ), которая свяжет полученное выражение:

_(SETQ input (READ))

(+ 1 2) ;введенное

выражение

(+ 1 2) ;значение

_input ( (+1 2)

3. Функции вывода.

Для вывода выражений используют несколько функций: PRINT, PRIN1,

PRINC.

Функция PRINT.

Это функция с одним аргументом, которая сначала вычисляет значение

аргумента, а затем выводит это значение. Функция PRINT перед выводом

аргумента переходит на новую строку, а после него выводит пробел. Таким

образом, значение выводится всегда на новую строку.

_(PRINT (+ 1 2))

3 ;вывод

3 ;значение

PRINT является псевдофункцией, у которой есть как побочный эффект,

так и значение. Значением функции является значение ее аргумента, а

побочным эффектом - печать этого значения.

Функции PRIN1 и PRINC.

Эти функции работают так же, как PRINT, но не переходят на новую

строку и не выводят пробел:

(PRIN1 5) ( 55

(PRINC 4) ( 44

Обеими функциями можно выводить кроме атомов и списков и другие типы

данных которые мы рассмотрим позже:

_(PRIN1 «CHG») ( «CHG»«CHG»

_(PRINC «tfd») ( tfd«tfd» ;вывод без кавычек,

;результат -

значение аргумента

С помощью функция PRINC можно получить более приятный вид. Она

выводит лисповские объекты в том же виде, как и PRIN1, но преобразует

некоторые типы данных в более простую форму.

Функция TERPRI.

Эта функция переводит строку. У функции TERPRI нет аргументов и в

качестве значения она возвращает NIL:

_(DEFUN out (x y)

(PRIN1 x) (PRINC y)

(TERPRI) (PRINC (LIST ‘x ‘y)) ( out

_(out 1 2) ( 12

(1 2)

4. Вычисления, изменяющие структуру.

Основными функциями, изменяющими физическую структуру списков,

являются RPLACA и RPLACD, которые уничтожают прежние и записывают новые

значения в поля CAR и CDR списочной ячейки:

(RPLACA ячейка значение-поля) ;поле CAR

(RPLACD ячейка значение-поля) ;поле CDR

Первым аргументом является указатель на списочную ячейку, вторым -

записываемое в нее новое значение поля CAR или CDR. Обе функции возвращают

в качестве результата указатель на измененную списочную ячейку:

_(SETQ a ‘(b c d)) ( (b c d)

_(RPLACA a ‘d) ( (d c d)

_(RPLACD a ‘(o n m)) ( (d o n m)

_a ( (d o n m)

5. Задания к лабораторной работе.

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

+y-x*y;

x*x+y*y;

x*y/(x+y)-5*y;

2. Определите функции (NULL x), (CADDR x) и (LIST x1 x2 x3) с помощью

базовых функций. (Используйте имена NULL1, CADDR1 и LIST1, чтобы не

переопределять одноименные встроенные функции системы.

3. Используя композицию, напишите функции, которые осуществляют

обращение списка из 2, 3, ... , n элементов.

4. Используя композицию описанных выше предикатов и логических

связок, постройте функцию, которая проверяет, является ли ее аргумент:

a) списком из 2, 3, ... элементов;

b)списком из 2, 3, ... атомов;

5. Напишите функцию:

такую, что P(n) для произвольного целого n есть список из трех элементов, а

именно: квадрата, куба и четвертой степени числа n;

для двух аргументов значением которой является список из двух элементов

(разности и остатка от деления);

такую, что A(n) есть список (The answer is n). Так, значением (A 12) будет

(The answer is 12);

семи аргументов, значением которой служит сумма всех семи аргументов.

6. Для каждого из следующих условий определить функцию одного

аргумента L , которая имеет значение T, если условие удовлетворяется, и NIL

в противном случае:

n-ый элемент L есть 12;

n-ый элемент L есть атом;

L имеет не более n элементов (атомов или подсписков).

7. Напишите функцию, которая вводит фразу на естественном языке и

преобразует ее в список.

8. Напишите функцию, которая спрашивает у пользователя ФИО студента

из группы (список группы составлен раньше) и выдает следующие данные о нем:

год рождения;

средний бал;

родителей;

списки свойств, присвоенные ему раньше.

9. Напишите функцию:

от одного аргумента (ФИО любого студента), замещающую в списке с данными о

нем (написанном раньше) подсписки со средними балами на списки свойств;

вычисляющую средние балы, беря данные из списков свойств.

10. Каковы будут значения выражений (RPLACA x x) и (RPLACD x x),

если:

x = ’(a b);

x = ’(a);

11. Вычислите значение следующих выражений:

(RPLACD ‘(a) ‘b);

(RPLACA ‘(a) ‘b);

(RPLACD (CDDR ‘(a b x)) ‘c);

(RPLACD ‘(nil) nil)

6. Вопросы.

1. Что такое лямбда-выражение?

2. Для чего используется функция DEFUN?

3. Чем различаются основные функции вывода?

4. Что возвращает в качестве значения функция READ?

5. Особенности функций, изменяющих структуру?

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

Тема: Организация вычислений в Лиспе.

Цель: Изучить основные функции и их особенности для организации

вычислений в Лиспе.

1. Предложения LET и LET*.

2. Последовательные вычисления.

3. Разветвление вычислений.

4. Циклические вычисления.

5. Передача управления.

6. Задание к лабораторной работе.

7. Вопросы.

1. Предложения LET и LET*.

Предложение LET создает локальную связь внутри формы:

(LET ((m1 знач1) (m2 знач2)...)

форма1 форма2 ...)

Вначале статические переменные m1, m2, ... связываются (одновременно)

с соответствующими значениями знач1, знач2, ... . Затем слева на право

вычисляются значения формы1, формы2, ... . Значение последней формы

возвращается в качестве значения всей формы. После вычисления связи

статических переменных ликвидируются.

Предложения LET можно делать вложенными одно в другое.

_(LET ((x ‘a) (y ‘b))

(LET ((z ‘c)) (LIST x y z))) ( (a b c)

_(LET ((x (LET ((z ‘a)) z)) (y ‘b))

(LIST x y)) ( (a b)

_(LET ((x 1) (y (+ x 1)))

(LIST x y)) ( ERROR

При вычислении у У и Х еще нет связи. Значения переменным

присваиваются одновременно. Это означает, что значения всех переменных mi

вычисляются до того, как осуществляется связывание с формальными

параметрами.

Подобной ошибки можно избежать с помощью формы LET*:

_(LET* ((x 1) (y (+ x 1)))

(LIST x y)) ( (1 2)

2. Последовательные вычисления.

Предложения PROG1 и PROGN позволяют работать с несколькими

вычисляемыми формами:

(PROG1 форма1 ... формаN)

(PROGN форма1 ... формаN)

Эти специальные формы последовательно вычисляют свои аргументы и в

качестве значения возвращают значение первого (PROG1) или последнего

(PROGN) аргумента.

_(PROG1 (SETQ x 1) (SETQ y 5)) ( 1

_(PROGN (SETQ j 8) (SETQ z (+x j))) ( 9

3. Разветвление вычислений.

Условное предложение COND:

(COND (p1 a1)

...

(pn an))

Предикатами pi и результирующими выражениями ai могут быть

произвольные формы. Выражения pi вычисляются последовательно до тех пор,

пока не встретится выражение, значением которого является T. Вычисляется

результирующее выражение, соответствующее этому предикату, и полученное

значение возвращается в качестве значения всего предложения COND. Если

истинного предиката нет то значением COND будет NIL.

Рекомендуется в качестве последнего предиката использовать символ T.

Тогда соответствующее ему an будет вычисляться в том случае, если другие

условия не выполняются.

Если условию не ставится в соответствие результирующее выражение, то

в качестве результата выдается само значение предиката. Если же условию

соответствуют несколько форм, то при его истинности формы вычисляются

последовательно слева на право и результатом предложения COND будет

значение последней формы.

Предложения COND можно комбинировать.

(COND ((> x 0) (SETQ рез x))

((< x 0) (SETQ x -x) (SETQ рез х))

((= х 0))

(Т ‘ошибка))

Предложение IF.

(IF условие то-форма иначе-форма)

(IF (> x 0) (SETQ y (+ y x)) (SETQ y (- y x)))

Если выполняется условие (т. е. х>0), то к значению y прибавляется

значение х, иначе (x x y) (IF (< x z) (PROGN (PRINT x)

(PRINT

«среднее (1)»))

(IF (> y z) (PROGN (PRINT

y)

(TERPRI)

(PRINT «среднее (2)»))

(PROGN

(PRIN1 z)

(PRIN1«среднее (3)»)))))

((< x y) (IF (< y z) (PROGN (PRIN1 y)

(TERPRI)

(PRIN1 «среднее (4)»))

(IF (> x z) (PROGN (PRINC

x)

(PRINC «среднее (5)»))

(PROGN

(PRINC z)

(TERPRI)

(PRINC «среднее (6)»)))))

(T (PRINC «ошибка ввода»))))

7. Вопросы.

1. Для чего используется предложение LET?

2. В чем его отличие от предложения LET*?

3. Чем различаются функции COND и IF?

4. Каковы возвращаемые ими значения?

5. Чем различаются функции PROG1 и PROGN?

6. Почему не желательно использовать операторы передачи управления?

Чем их можно заменить?

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

Тема: Рекурсия в Лиспе. Функционалы и макросы.

Цель: Изучить основы программирования с применением рекурсии.

Научиться работать с функционалами и макросами.

1. Рекурсия. Различные формы рекурсии.

2. Применяющие функционалы.

3. Отображающие функционалы.

4. Макросы.

5. Задание к лабораторной работе.

6. Вопросы.

1. Рекурсия. Различные формы рекурсии.

Основная идея рекурсивного определения заключается в том, что функцию

можно с помощью рекуррентных формул свести к некоторым начальным значениям,

к ранее определенным функциям или к самой определяемой функции, но с более

«простыми» аргументами. Вычисление такой функции заканчивается в тот

момент, когда оно сводится к известным начальным значениям.

Рекурсивная процедура, во-первых содержит всегда по крайней мере одну

терминальную ветвь и условие окончания. Во-вторых, когда процедура доходит

до рекурсивной ветви, то функционирующий процесс приостанавливается, и

новый такой же процесс запускается сначала, но уже на новом уровне.

Прерванный процесс каким-нибудь образом запоминается. Он будет ждать и

начнет исполняться лишь после окончания нового процесса. В свою очередь,

новый процесс может приостановиться, ожидать и т. д.

Будем говорить о рекурсии по значению и рекурсии по аргументам. В

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

Во втором - в качестве результата функции возвращается значение некоторой

другой функции и рекурсивный вызов участвует в вычислении аргументов этой

функции. Аргументом рекурсивного вызова может быть вновь рекурсивный вызов

и таких вызовов может быть много.

Рассмотрим следующие формы рекурсии:

простая рекурсия;

параллельная рекурсия;

взаимная рекурсия.

Рекурсия называется простой, если вызов функции встречается в

некоторой ветви лишь один раз. Простой рекурсии в процедурном

программировании соответствует обыкновенный цикл.

Для примера напишем функцию вычисления чисел Фибоначчи (F(1)=1;

F(2)=1; F(n)=F(n-1)+F(n-2) при n>2):

(DEFUN FIB (N)

(IF (> N 0)

(IF (OR N=1 N=2) 1

(+ (FIB (- N 1)) (FIB (- N 2))))

‘ОШИБКА_ВВОДА))

Рекурсию называют параллельной, если она встречается одновременно в

нескольких аргументах функции:

(DEFUN f ...

...(g ... (f ...) (f ...) ...)

...)

Рассмотрим использование параллельной рекурсии на примере

преобразования списочной структуры в одноуровневый список:

(DEFUN PREOBR (L)

(COND

((NULL L) NIL)

((ATOM L) (CONS (CAR L) NIL))

(T (APPEND

(PREOBR (CAR L))

(PREOBR (CDR L))))))

Рекурсия является взаимной между двумя и более функциями, если они

вызывают друг друга:

Страницы: 1, 2, 3, 4