Лекции в ворде, страница 4

$ (cons '(Бил Клинтон) '((Борис Ельцин)))

((БИЛ КЛИНТОН) (БОРИС ЕЛЬЦИН))

$ (cons (+ 1 2) '(+ 4))

(3 + 4)

• Некоторые предикаты (см п. 2.3)

$ (atom 'x)

T

$ (atom '(a b c))

NIL

$ (eq 'x 'мышь)) ;предикат eq проверяет тождественность двух

NIL ;символов

$ (eq 'кот '(кот мышь))

T

$ (eql 3 3.0) ;предикат eql сравнивает числа одинаковых

NIL ;типов

$ (= 3 3.0) ;предикат = сравнивает числа разных типов

Т

$ (equal '(a b c) (cons 'a '(b c))) ;equal проверяет идентичность

T ;записей

$ (null ()) ;null проверяет, является ли аргумент пустым

T ;списком

• Другие полезные примитивы

Вложенные вызовы car и cdr

Формат: (c...r список)

Вместо многоточия записывается нужная комбинация букв а (для функции car) и d – (для функции cdr):

(cadr x)((car(cdr x)

(cddar x)((cdr(cdr(car x)))

Примеры использования:

$ (cadr '(я умею программировать на Лиспе))

УМЕЮ

$ (caddr '((a b c) (d e) (f)))

(F)

(nth n список) – вычисляет n-й элемент списка

$ (nth 2 '(1 2 3))

3 ; индекс начинается с нуля

(last x) – выделяется последний элемент списка

$ (last '(a b c))

C

(list x1 x2...xn) – выдает список из значений аргументов

$ (list 'a 'b )+ 1 2))

(A B 3)

Упражнения

1. Запишите последовательность вызовов car и cdr, выделяющую из приведенных ниже списков символ цель. Упростите эти вызовы функцией вида C...R:

a) (1 2 цель 3 4)

б) ((1) (2 цель) (3 (4)))

в) ((1 (2 (3 4 цель))))

2. Вычислите значения выражений:

а) (cons nil '(это пустой список))

б) (cons '(nil) '(nil))

в) (cons (car '(a b)) (cdr '(a b)))

г) (list (list 'a 'b) '(car (c d)))

3. Какие из следующих вызовов возвращают значение Т?

а) (atom '(cdr nil))

б) (equal '(a b) (cons '(a) '(b)))

в) (null (null t))

г) (equalp (atom nil) (caar '((t))))

4.3. Имя и значение символа

Символ может обозначать произвольное выражение. У символов изначательно нет какого-либо значения, как у констант. Поэтому, если ввести символ функция, то, поскольку интерпретатор не может вычислить значение символа, то будет выдано сообщение об ошибке.

$ функция

Error: Unbound atom ФУНКЦИЯ

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

$ (set 'функции '(car cdr cons atom eq)) ;символу функции присвоено

(CAR CDR CONS ATOM EQ) ;значение '(car cdr cons atom eq)

$ функции ;теперь можно вычислить

(CAR CDR CONS ATOM EQ ;значение символа функции

$ (set (сar функции) '(a b c)) ;сперва вычисляется car от зна-

;чени символа функции. Это

;значение есть car, а set присво

(A B C) ;ит car значение'(a b c)

$ (car функции)

CAR

$ car

(A B C)

$ функции

(CAR CDR CONS ATOM EQ)

SETQ связывает имя, но не вычисляет его

Эта функция вычисляет только свой второй аргумент. О блокировании вычисления первого аргумента напоминает буква Q (quote):

$ (setq функции '(car cdr eq))

(CAR CDR EQ)

Знак апострофа перед первым аргументом можно опустить. Для проверки связывания первого аргумента со вторым используется функция boundp:

$ (boundp 'функции)

Т

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

$ (list (+ (setq a 3) 4) a) ;здесь setq только связывает аргумент "а" с 3,

(7 3)

$ а

3

$ (list b (setq b 3)) ;вычисляется слева направо, поэтому

Error: Unbound atom b

Ћ! Вычисление любого правильно составленного лисповского выражения выполняет функция EVAL. Эта функция в том числе и разблокирует ранее блокированное от вычисления выражение.

$ (setq f '(+ 2 3))

(+ 2 3)

$ (eval 'f)

(+ 2 3)

$ f ;этот вызов эквивалентен предыдущему, поскольку eval

(+ 2 3) ;на самом деле является интерпретатором Лиспа

$ (eval f)

5

$ 'f

F

Упражнения

1. Каковы значения следующих вызовов при условии, что значением X является Y а значением Y –Х:

а) $(set x y);

б) $(setq x y).

1. Каково значение атома А после вызовов:

а) $(set (setq a'a) 'b)

б) $(set(setq b 'a)(setq a 'c))

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

а) $ '(car '(a b c))

б) $(eval '(car '(a b c)))

c) $ (quote (eval (quote (quote quote))))

1. Используя функцию setq, добавить к списку (A B C D) элемент F.

4.4. Определение функций

Определение функций и их вычисление в Лиспе основано на -исчислении Черча. Соответствие этому исчислению определение функций в Лиспе имеет следующий вид:

(lambda (x1 x2...xn) fn).

Здесь символ lambda означает, что определяется функция с х1,х2...xn формальными параметрами этого определения, представленного телом функции fn. -определение – это определение вычислений и параметров функции в чистом виде без фактических параметров. Если к такому определению добавить фактические параметр (аргументы), то будем иметь дело с вызовом функции, определенной в -определении:

(lambda (x y) (+ x y)) ;определение функции

$ ((lambda (x y) (+ x y))2 3) ; вызов функции

5

Вычисление -вызова, т.е. применение -выражения к фактическим параметрам, производится в два этапа:

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

• вычисление тела -выражения и возврат полученного значения в качестве значения -вызова.

-вызовы можно объединять между собой. Вложенные вызовы можно ставить как на место тела -выражения, так и на место фактических параметров:

$ ((lambda ( y) ((lambda ( х) ; y -вызова

(list y x)) 'внутри)) 'вне) ; тело вновь -вызов

(ВНЕ ВНУТРИ) ;результат

Ћ! (-выражение – функция без имени

Ћ! (-выражение – это безымянная функция, которая исчезает тотчас же после вычисления значения формы. Ее трудно использовать снова, так как нельзя вызвать по имени, хотя ранее было доступно как списочный объект.

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

Формат: (defun имя лямбда-список тело).

Такой формат эквивалентен (-выражению, в котором исключены внешние скобки и сам атом lambda:

(defun list1(lambda (x y)(cons x(cons y nil))))(

(defun list1 (x y)(cons x(cons y nil))).

DEFUN соединяет символ с (-выражением. Символ именует определенные этим (-выражением вычисления. Значением этой формы является имя новой функции.

Пример1.

$ (defun list1 (x y) ; определение

(cons x (cons y nil)))

LIST1 ;результат определения

$ (list1 'a 'b) ; вызов

(A B) ;результат вычисления list1.

Пример2.

Определяется функция проценты двух аргументов часть и чего. Эта функция вычисляет, сколько процентов составляет первый аргумент (часть) от второго (чего).

$ (defun проценты (часть чего)

(* (/ часть чего) 100) )

ПРОЦЕНТЫ

$ (проценты 3 15)

20

Упражнения

1. Вычислить значения lambda-вызовов:

а) ((lambda(x)(cons x nil)) 'y);((lambda (x)(cons x nil)) 'y)

б) ((lambda(x)(list x))(list nil)).((lambda (x )(list x))(list nil))

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

а) факториала заданного числа;

б) число Фибоначчи для заданного n.

1. Определить рекурсивную функцию last_element, определяющую последний элемент списка lst. Руководствуйтесь алгоритмом:

а) если список lst пуст, то возвращается значение nil, иначе

б) если в списке один элемент, то возвращается car(lst), иначе

в) искать последний элемент в в cdr(lst).

1. Определить рекурсивную функцию append, склеивающую два списка lst1 и lst2. Алгоритм:

а) если список lst1 пуст, то возвращается lst2, иначе

б) если cons прибавляет car(lst1) к списку, полученному в результате применения append, присоединяющей cdr(lst1) к lst2.

1. Определить рекурсивную функцию member(x, lst), определяющую принадлежность атома х списку lst:

а) Если список пуст (null), возврат – nil.

б) Если атом х совпадает (eql) с car от списка, то возврат Т, т.е. атом х является первым элементом списка, иначе

в) Атом х принадлежит хвосту списка – cdr(lst)

6.Определить рекурсивную функцию rember(obj lst), которая удаляет только первый попавшийся в списке lst элемент, идентичный obj.

Тема 5. Передача параметров и область их действия

Ћ! В Лиспе используется передача параметров по значению

5.1. Статические переменные локальны.

Параметры используются для передачи данных в функцию, а результат возвращается как значение функции. Формальные параметры функции называются статическими или лексическими. Связи статической переменной действительны только в пределах той формы, в которой они определены. Они перестают действовать в функциях, вызываемых во время вычисления, но текстуально описанных вне данной структуры. Изменение значений переменных не влияет на одноименные переменные вызовов более внешнего уровня. После вычисления функции, созданные на это время связи формальных параметров ликвидируются и происходит возврат к тому состоянию, которое было до вызова функции.

Пример.

$ (defun не_меняет (х) ;х –статическая

(setq х 'новое))

НЕ_МЕНЯЕТ

$ (setq х 'старое)

СТАРОЕ

$ (не_меняет 'новое) ; статическое значение

НОВОЕ ; х изменяется

$ х ;первоначальная связь

СТАРОЕ ; не меняется

5.2. Свободные переменные меняют свое значение

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

Пример.

$ (defun изменить (у)

(setq х 'старое)) ;х – свободная

ИЗМЕНИТЬ

$ изменить 'новое

НОВОЕ

$ х ; значение свободной

СТАРОЕ ; переменной не изменилось

Ћ! Если переменная является статической, использование ее в качестве формального параметра в более внешнем определении не влияет на значение свободной переменной. У переменной либо не будет значение, что приведет к ошибке, либо ее значение определяется в соответствии с ее глобальным значением, присвоенным на самом внешнем уровне функцией setq.

$ (setq x 100) ;глобальное значение х

100

$ (defun f1 (x) ;х – статическая. Здесь определена функция f1, ее

(f2 2)) ;телом является еще не определенная функция f2

F1

$ (defun f2 (y) ;определяется функции f2, у – формальный параметр.

(list x y)) ;Телом функции f2 является функция list, создающая

; список из аргументов. х – свободная переменная

F2

$ (f1 1) ;формальный параметр х получил значение 1

(1 2)

$ (f2 3) ;формальному параметру у передано значение 3

(100 3) ;свободна переменная х наследует глобальное значение

$ x ;100

100

5.3. Управляющие формы Лиспа.

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

• последовательное выполнение: предложения prog1, progn;

• разветвление вычислений: cond, if

• циклические: loop;

• передача управления: prog, return .(здесь не рассматриваются)

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

(PROGN (форма1 форма2 ...формаN)) последовательно вычисляет формы, начиная с <формы1>, и выдает значение последней вычисленной формы.

Пример:

$ (progn (setq N1 (+ 2 5))

(setq N2 (* 3 4))

((< N1 N2) ;если N1<N2, то

((minusp N1) ; если N1<0, то

(* 3 N2) ) ; результат вычисления 3*N2, иначе

(+ N1 N2) ) ; результат вычисления N1+N2=19

(- N1 N2) ) ;иначе результат вычисления N1-N2

19

(PROG1 форма1 ... формаN) вычисляет <форму1>, затем - оставшиеся формы, используя неявную PROGN, и возвращает результат вычисления <формы1>. PROG1 часто используют для того, чтобы не вводить временные переменные для хранения результатов в процессе вычисления других выражений.

Пример:

(setq foo '(a b c d)) --

(A B C D)

$ (prog1 (car foo) (setq foo (cdr foo)))

A

$ foo

(B C D)

• Условные предложения

IF [условие, то-форма, иначе-форма]

Если значение условия(предиката) – не NIL, то IF вычисляется, и выдается <то-форма>. В противном случае вычисляется IF и выдается <иначе-форма> или NIL, если <иначе-форма> отсутствует. Специальная форма IF в LISP аналогична конструкции "if-then -else" в других языках.

Пример: