Программирование при помощи отображений Функциональные отношения и базовые функции Lisp Функции Eugeny L Yakimovitch

Понятие функции В математике функция отображает одно множество в другое. Записывается: Y = F (x) Для х из множества определения (Domain) ставится в соответствие Y из множества значений (range) функции F. Можно записать: У функции может быть любое количество аргументов, в том числе их может не быть совсем. Функция без аргументов имеет постоянное значение. Примеры функций: abs( -3 ) --> 3 абсолютная величина. + ( 2, 3 ) --> 5 сложение union ( ( a, b ), ( c, b ) ) --> ( a, b, c ) объединение множеств. количество_букв ( слово ) --> 5

Обобщение функции Функция в общем случае задает отображение из нескольких множеств в множество значений. Это функция двух аргументов: первый х принадлежит А, второй у принадлежит В, значение z принадлежит С. В этом случае говорят, что аргументы и значение имеют разные типы.

Пример отношения для аргументов различных типов 1 Январь 1 января Январь{январь, февраль,.., декабрь }

Иерархия вызовов В какой последовательности будет вычислена функция (+ 1 2) : А) (+ (+ 1 2) 3) B) (+ 3 (+ 1 2)) ?

Иерархия вызовов 1) CL-USER> (trace +) 2) WARNING: TRACE: redefining function + in top-level, was defined in C 3) ;; Tracing function +. 4) (+) 5) CL-USER> (+ (+ 1 2) 3) 6) 1. Trace: (+ '1 '2) 7) 1. Trace: + ==> 3 8) 1. Trace: (+ '3 '3) 9) 1. Trace: + ==> 6 10) 6 11) CL-USER> (+ 3 (+ 1 2)) 12) 1. Trace: (+ '1 '2) 13) 1. Trace: + ==> 3 14) 1. Trace: (+ '3 '3) 15) 1. Trace: + ==> 6 16) 6 17) CL-USER> Правило: Первый вызов «изнутри», т.е. первым выполняется самый глубокий (удаленный от вершины) лист дерева s-выражения.

Базовые функции В Лиспе для обработки списков, т.е. для разбора, анализа и построения списков существуют базовые функции. Они образуют систему аксиом языка, к которым сводятся символьные вычисления. В этом смысле их можно сравнить с основными арифметическими операциями. Простота базовых функций и их малое число - одно из достоинств Лиспа.

Базовые функции Функции для атомов и пар: Функции для атомов и пар: cons car cdr eq atom Объявление и управление: Объявление и управление: cond lambda define eval quote Пример Пример (lambda (x) (cond ((atom x) x) (T (cons A x)))) function f(x) = if atom(x) then x else cons(A,x) Функции с побочным эффектом Функции с побочным эффектом rplaca rplacd

Блокировка QUOTE В некоторых случаях не требуется вычисления значений выражений, а требуются само выражение. Если прямо ввести ( ), то 5 получится как значение. Но можно понимать ( ) не как функцию, а как список. S-выражения, которые не надо вычислять, помечают для интерпретатора апострофом " ' " (quote). QUOTE - специальная функция с одним аргументом, которая возвращает в качестве значения этот аргумент.

Примеры использования Quote ' ( ) ( ) ' ( ) ( ) 'y 'yy ( QUOTE QUOTE ) QUOTE ( QUOTE QUOTE ) QUOTE

Примеры использования Quote Вместо апострофа можно использовать функцию QUOTE. Вместо апострофа можно использовать функцию QUOTE. > ( quote ( ) ) ( )* ( quote y ) y > ( quote ( ) ) ( )* ( quote y ) y > ' ( a b ' ( c d ) ) (a b ( quote c d ) ) > ' ( a b ' ( c d ) ) (a b ( quote c d ) ) Апостроф автоматически преобразуется в QUOTE.

Примеры использования Quote Перед константами не надо ставить апостроф, так как число и его значение совпадают. Перед константами не надо ставить апостроф, так как число и его значение совпадают. >' >' >( + ' 2 3 ) 5 >( + ' 2 3 ) 5 > t T > t T > ' t T > ' t T >' nil NIL >' nil NIL

Eval Функция EVAL обеспечивает дополнительный вызов интерпретатора Лиспа. Функция EVAL обеспечивает дополнительный вызов интерпретатора Лиспа. При этом вызов может производится внутри вычисляемого S-выражения. При этом вызов может производится внутри вычисляемого S-выражения. Функция EVAL позволяет снять блокировку QUOTE. Функция EVAL позволяет снять блокировку QUOTE.

Eval quote и eval действуют во взаимно противоположенных направлениях и аннулируют эффект друг друга. ( quote ( ) ) ( quote ( ) ) ( ) ( eval ( quote ( ) ) ) ( eval ( quote ( ) ) )3

Eval EVAL - это универсальная функция Лиспа, которая может вычислить любое правильно составленное s-выражение. ( setq x ' ( a b c ) ) ( a b c ) ( setq x ' ( a b c ) ) ( a b c ) x ( a b c ) x ( a b c ) ' x x ' x x ( eval ' x ) ( a b c ) ( eval ' x ) ( a b c )

Использование символов в качестве переменных В начале работы виртуальной машины символы в Лиспе не имеют значения, т.к. они не проинициализированы. Значения имеют только константы. CL-USER> 1.7 CL-USER> CL-USER> t CL-USER> t T CL-USER> nil CL-USER> nil NIL NIL

Связывание символов со значениями Значения символов хранятся в ячейках, закрепленных за каждым символом. Значения символов хранятся в ячейках, закрепленных за каждым символом. Если в эту ячейку положить значение, то символ будет связан (bind) сo значением. В процедурных языках говорят "будет присвоено значение". Если в эту ячейку положить значение, то символ будет связан (bind) сo значением. В процедурных языках говорят "будет присвоено значение". Value Symbol … 1. CL-USER> (set `duck `donald) 2. DONALD 3. CL-USER> duck 4. DONALD

Связывание символов со значениями Кроме того, для диалекта Common Lisp, справедливо следующее: Не оговаривается, что может хранится в ячейке: целое, атом, список, массив и т.д. В ячейке может хранится что угодно. Не оговаривается, что может хранится в ячейке: целое, атом, список, массив и т.д. В ячейке может хранится что угодно. С одним символом может быть связана неограниченное число ячеек-значений. С одним символом может быть связана неограниченное число ячеек-значений. Для связывания символов используется три функции: SET SET SETQ SETQ SETF SETF

Функция SET В качестве результата функции возвращается второй аргумент. В качестве результата функции возвращается второй аргумент. ( set 'a 'b ) => b Связывает символ в первом аргументе, предварительно вычислив значение первого аргумента. Если первый аргумент указан без апострофа, то присваивается (вставляется) по результату вычисления этого аргумента. Связывает символ в первом аргументе, предварительно вычислив значение первого аргумента. Если первый аргумент указан без апострофа, то присваивается (вставляется) по результату вычисления этого аргумента. ( set b `c) => с ( set b `c) => с ( set a `b) => b ( set a b) => с (eval a) => c На значение символа можно сослаться записав его без апострофа. На значение символа можно сослаться записав его без апострофа.

SETQ и SETF (SETQ a b) эквивалентно (SET `a b) Буква Q означает блокировку и значение первого аргумента не вычисляется В ранних версиях диалектов Lisp функция SETF и обобщенные переменные не были доступны. И роль функции присваивания выполняла SETQ. Современная реализация использует макрос SETF для всех видов присваиваний, и SETQ считается атавизмом. Но если внимательно посмотреть на работу отладчика, можно увидеть, что все SETF присваивания будут заменены на SETQ.

CONS Функция CONS создает точечную пару, конс или просто пару. Конс строит новый список из своих аргументов: CONS S-Выражение Список

Примеры для CONS CL-USER> (cons `a `(b c)) CL-USER> (cons `a `(b c)) (A B C) (A B C) CL-USER> (cons '( a b ) '( ( a b ) ) ) CL-USER> (cons '( a b ) '( ( a b ) ) ) ((A B) (A B)) ((A B) (A B)) CL-USER> (cons '(+ 1 2 ) '(+ 3 4 ) ) CL-USER> (cons '(+ 1 2 ) '(+ 3 4 ) ) ( ( ) ) ( ( ) ) CL-USER> ( cons ' a nil ) ( a ) ; элемент превратился в список CL-USER> ( cons ' a nil ) ( a ) ; элемент превратился в список CL-USER> `(C. C) ; пример точечной пары CL-USER> `(C. C) ; пример точечной пары (C. C) (C. C) CL-USER> (CONS A B) ; если (setq a `c) (setq b `c) CL-USER> (CONS A B) ; если (setq a `c) (setq b `c) (C. C) (C. C)

История возникновение CAR и CDR В первые Lisp был реализован на машине IBM 704 (конец 50- х). В первые Lisp был реализован на машине IBM 704 (конец 50- х). В архитектура 704 была специальная поддержка разбиения 36-битного машинного слова на четыре части, «адрес»(15 бит), «декремент» (15), «префикс» (3 бита) и «метка» (3 бита). В архитектура 704 была специальная поддержка разбиения 36-битного машинного слова на четыре части, «адрес»(15 бит), «декремент» (15), «префикс» (3 бита) и «метка» (3 бита). Префиксные курсоры Lisp включали в себя функции car ("Contents of the Address part of Register number"), cdr, cpr и ctr, каждая из которых выбирала физический адрес аргументы, загружала соответствующее слово из памяти в процессор, и извлекало нужные биты. А функция cons собирала отдельные значения вместе в один список, который легко трансформировался обратно в машинное слово. Префиксные курсоры Lisp включали в себя функции car ("Contents of the Address part of Register number"), cdr, cpr и ctr, каждая из которых выбирала физический адрес аргументы, загружала соответствующее слово из памяти в процессор, и извлекало нужные биты. А функция cons собирала отдельные значения вместе в один список, который легко трансформировался обратно в машинное слово. Современная реализация языка поддерживает более понятные аналоги этих слов first и rest. Современная реализация языка поддерживает более понятные аналоги этих слов first и rest. AddressDecrementPrefixTag

Функция CAR Возвращает голову списка или ключевой (первый) элемент точечной пары (конса). Возвращает голову списка или ключевой (первый) элемент точечной пары (конса). (car `(a b c d)) => A Первый элемент списка – голова (head). Первый элемент списка – голова (head).

Функция CDR Возвращает хвост списка или второй элемент точечной пары (конса). Возвращает хвост списка или второй элемент точечной пары (конса). (cdr `(a b c d)) => (B C D) Список без головного элемента – хвост (tail). Список без головного элемента – хвост (tail).

Сравнение CONS, CAR, CDR ТИП Записывает изменения в Возвращает РЕЗУЛЬТАТ CARСелекторСписок S-Выражение CDRСелекторСписокСписок CONSКонструктор Список

Сравнение CONS, CAR, CDR Список, разбитый с помощью функции CAR и CDR на голову и хвост, можно восстановить функцией CONS. Список, разбитый с помощью функции CAR и CDR на голову и хвост, можно восстановить функцией CONS. Селекторы CAR и CDR являются обратными для конструктора CONS. Селекторы CAR и CDR являются обратными для конструктора CONS.CARCDRCONSCARCDRCONS CAR CDR CONS ( H T )

Вложенные CAR и CDR CL-USER> (first `(a b c d e )) CL-USER> (first `(a b c d e )) A CL-USER> (second `(a b c d e )) CL-USER> (second `(a b c d e )) B CL-USER> (third `(a b c d e )) CL-USER> (third `(a b c d e )) C CL-USER> (caddr `(a b c d e )) CL-USER> (caddr `(a b c d e )) C CL-USER> (car (cdr (cdr `(a b c d e )))) CL-USER> (car (cdr (cdr `(a b c d e )))) C

Функция номера элемента NTH (NTH 5 `( )) (NTH 5 `( )) 5 Nth для номера 0 эквивалентно функции car. Nth для номера 0 эквивалентно функции car.

Функция LIST Функция LIST создает и возвращает список из символьных выражений (списков или атомов). (list s-e1 s-e2 s-e3.. ) Выполняется для любого числа аргументов.

Функция LENGTH Возвращает число элементов списка верхнего уровня или длину списка. Возвращает число элементов списка верхнего уровня или длину списка. CL-USER> (Length `(1 (2 3) 4)) CL-USER> (Length `(1 (2 3) 4)) 3

Арифметика (+ x1 x2... xn) возвращает x1 + x2 + x xn. (+ x1 x2... xn) возвращает x1 + x2 + x xn. (- x1 x2... xn) возвращает x1 - x2 - x xn. (- x1 x2... xn) возвращает x1 - x2 - x xn. (* y1 y2... yn) возвращает y1 * y2 * y3 *... * yn. (* y1 y2... yn) возвращает y1 * y2 * y3 *... * yn. (/ x1 x2... xn) возвращает x1/x2/... /xn. (/ x1 x2... xn) возвращает x1/x2/... /xn.

Инкремент и декремент (1+ x) (1+ x) (1- x) (1- x) Примечание: Здесь знаки 1+ образуют один символ

Степень и логарифм Функция логарифм имеет следующий прототип (log arg ) и (log arg base) Функция логарифм имеет следующий прототип (log arg ) и (log arg base) >(log 2.7) Хотя для извлечения корня существует функция SQRT, эту операцию всегда можно выполнить через экспоненту вызывая функции EXP и EXPT. Хотя для извлечения корня существует функция SQRT, эту операцию всегда можно выполнить через экспоненту вызывая функции EXP и EXPT. > (expt 2 1/2) >(log (expt 2 8) 2) 8

Задачи Напишите решения в виде коротких функций, которые будут возвращать n-ый элемент числовой последовательности заданной по одному из правил: a) a(n+1) = a(n) + (n+1); b) a(n+1) = a(n) * (n+1); c) f(0)=1; f(1)=1; f(n+2)=f(n)+f(n+1); n+1 | m=0; n+1 | m=0; d [1] ) A(m,n)= A(m-1,1) | m>0, n=0; [1] A(m-1, A(m,n-1)) | m>0, n>0 A(m-1, A(m,n-1)) | m>0, n>0 При решении считать. Проверить способы получения последовательностей используя итерации, простую рекурсию, хвостовую рекурсию. [1][1] Не примитивно рекурсивная функция Аккермана. [1]