Понятие функционального программирования
Введение
В настоящее время большое развитие получили процедурные (императивные) языки, в которых вычисления производятся путём последовательной записи операторов, выполняющих действия по занесению данных в ячейки памяти и передаче управления. Вместе с тем, необходимо знать, что существуют и другие виды языков программирования, зачастую в приложении к определённому классу задач обладающие весьма мощными выразительными средствами.
Среди таких видов языков можно отметить функциональные языки и конкретно язык Lisp. Этот язык был разработан Дж. Маккарти в 1962 году и с тех пор завоевал прочное место среди средств разработки программного обеспечения, особенно в области искусственного интеллекта. В частности, можно отметить, что набор редакторов текстов GNU EMACS написан на Lisp, а также весьма известным продуктом, написанным на этом языке, является AUTOCAD.
Чистый Lisp является весьма ограниченным набором функций, позволяющим выполнять все необходимые действия. Поэтому было разработано большое количество его последующих версий, в которых вводились дополнительные функции, опирающиеся на базовые и позволяющие сделать код более лаконичным. Среди таких версий можно, прежде всего, отметить Common Lisp, являющийся стандартом де-факто. В дальнейшем речь будет идти в основном про эту версию. Получить интерпретатор Common Lisp можно, например, по следующим адресам:
· ftp://ftp.gnu.org/gnu/clisp/release/2.30/clisp-2.28-win32.zip (для Windows)
· ftp://ftp.gnu.org/gnu/clisp/release/2.30/clisp-2.28.tar.bz2 (для Linux)
В своей работе автор также использовал демонстрационную версию Allegro Common Lisp, доступную (на момент написания учебного пособия) по адресу www.frantz.com.
Функциональное программирование, как и другие альтернативные императивному программированию модели, применяются для решения задач, которые трудно сформулировать в терминах последовательных операций. Это практически все задачи, связанные с искусственным интеллектом, в том числе задачи распознавания образов, общение с пользователем на естественном языке, реализация экспертных систем, автоматизированное доказательство теорем, символьные вычисления, построение трансляторов.
Методическое пособие предназначено для студентов специальности 2204, обучающихся в СПб ГУАП.
Лямбда-исчисление
Данные и выражения языка Lisp.
Основные конструкции
Последовательности вычислений
В языке Lisp существует возможность организации последовательностей вычислений, вплоть до поддержки процедурного стиля программирования. Для этого служат различные специфичные конструкции, часть из которых будут описана в этом разделе.
| let | (LET ( (локальная_переменная1 значение1) ( локалная_переменная2_значение2 )… ) форма1 форма2 … ) Создаёт локальную связь. Содержит в своём первом параметре список, каждый элемент которого представляет собой пару "локальная переменная - значение" и выполняется в начале вычисления оператора. Остальными параметрами LET являются вычисляемые формы, значение последней из которых возвращается в качестве результата. Необходимо отметить, что результат модификации локальных переменных по завершении оператора не сохраняется. |
| >(SETQ A 1) >(LET ((A 2)) (+ A 1)) >A |
Отметим, что в данном случае оператор LET содержал в себе одну форму (+ A 1) и, в то же время, естественно, сам являлся формой. В качестве параметра-формы LET вполне мог использоваться другой оператор LET или любой другой оператор.
| prog1 prog2 prong | (progn форма1 форма2 форма3…) Позволяет выполнять последовательные вычисления форм. Возвращается значение, соответственно, первой, второй и последней формы. |
| >(PROG1 1 2 3) >(PROG2 1 2 3) >(PROGN 1 2 3) |
Естественно, применение этой конструкции может быть и более сложным:
| >(progn (setq A 5) (setq B 7)) >A >B |
Условные операторы и циклы
Для того, чтобы решать задачи, необходимо обеспечивать разветвление алгоритмов, в частности, языку особенно необходимы условные конструкции и циклы. Здесь мы рассмотрим некоторые из них, имеющие наиболее частое применение, и начнём с операторов условия.
| cond | (cond (условие1 форма1) (условие форма2)…) Реализует таблицу решений. В зависимости от выполняемого условия возвращает сопоставленное ему выражение. Аргументами COND являются списки из двух элементов, первый из которых указывает на условие, а второй определяет, какое значение при выполнении этого условия должен вернуть COND. Если ни одно условие не подойдёт, возвращается NIL. Ветви просматриваются последовательно, и как только одно из условий оказывается истинным, выполнение COND завершается |
COND является наиболее общей формой условного оператора. Все остальные условные операторы могут быть выражены через него. Примером использования может быть некая таблица решений, например, вывести день недели по его номеру:
| >(SETQ DAY 3) >(COND ((EQL DAY 1) "Monday") ((EQL DAY 2) "Tuesday") ((EQL DAY 3) "Wednesday") ((EQL DAY 4) "Thursday") ((EQL DAY 5) "Friday") ((EQL DAY 6) "Saturday") ((EQL DAY 7) "Sunday") (T "Check your calendar") ) "Wednesday" |
При попытке выполнить пример необходимо обратить внимание, что дни недели, написанные по-русски, некоторые интерпретаторы не понимают. Также заметим, что последним условием является T - это условие по умолчанию, оно всегда выполнится, если только до него не выполнилось уже какое-то другое. Естественно, условие NIL бессмысленно.
| if | (if условие форма-для-истинности форма-для-ложности) Реализует простой условный оператор. Содержит три аргумента - условие, результат, если условие истинно, результат, если условие ложно. Соответствует оператору (cond (Условие результат-при-истинном-условии) (T результат-при-ложном-условии)) |
В качестве примера приведём следующий код, пытающийся определить, является ли число натуральным:
| >(SETQ NUMBER 100) >(IF (> NUMBER 0) "Natural" "Not Natural") "Natural" >( SETQ NUMBER -100) -100 >(IF (> NUMBER 0) "Natural" "Not Natural") "Not Natural" |
Наконец, можно использовать также дополнительные виды условных операторов, такие как WHEN, UNLESS, CASE.
| when | (when условие значение-при-истинности) Модифицированный вариант оператора COND, содержит в качестве параметров одно условие (первый параметр) и несколько форм, которые вычисляются последовательно при истинности условия. Возвращается значение последней вычисленной формы. |
| unless | (unless значение-при-ложности) То же самое, что и WHEN, однако формы вычисляются, если условие ложно. |
| case | (case ключ (список-ключей форма1 форма2…) (список-ключей форма1 форма2…)…) Традиционная таблица решений (сходна с соответствующим оператором языка Pascal). Содержит первый параметр - ключ, который вычисляется перед обработкой всех остальных параметров. Остальные параметры состоят каждый из списка ключей и последовательности вычисляемых форм, причём вычисляются формы (и возвращается последняя из них) в том случае, если значение ключа CASE было найдено в списке ключей одного из параметров. |
Приведём примеры использования соответствующих функций. Используем наш старый пример с определением того, является ли число натуральным (в противном случае возвращается NIL):
| >(SETQ NUMBER 100) >(SETQ NUMBER 100) >(WHEN (> NUMBER 0) "Natural") "Natural" >(UNLESS (> NUMBER 0) "Not Natural") NIL >( SETQ NUMBER -100) -100 >(WHEN (> NUMBER 0) "Natural") NIL >(UNLESS (> NUMBER 0) "Not Natural") "Not Natural" |
А также модифицированная версия таблицы решений относительно дней недели:
| >(SETQ DAY 3) >(CASE DAY (1 "Monday") (2 "Tuesday") (3 "Wednesday") (4 "Thursday") (5 "Friday") (6 "Saturday") (7 "Sunday") (T "Check your calendar") ) "Wednesday" |
Теперь рассмотрим операторы циклов
| do | (do ((переменная начальное-значение приращение)…) (условие-окончания форма1 форма2 …) форма 11 форма12…) Функция является наиболее общим вариантом организации циклов. Реализуется в форме DO Инициализация Условие Тело цикла. Инициализация является списком правил, каждое из которых состоит из имени переменной, начального значения и приращения, Условие состоит из собственно условия выхода и вычисляемых форм, которые вычисляются при возврате функцией значения (как обычно, возвращается последняя). Наконец тело представляет собой последовательность вычисляемых форм, которые выполняются каждый раз при новой итерации. К сожалению, не во всех версиях Lisp поддерживается приращение итератора. В таких слуяаях необходимо выполнять её приращение отдельным кодом. |
Примером работы с оператором DO может служить программа, вычисляющая факториал числа (этот пример достаточно показателен в следствие последующего изложения эквивалентности решений с помощью циклов и рекурсии).
| >(defun f1 (x) (do ((res 1) (rs 1)) ((eql x 0) rs) (setq rs (* res rs)) (setq x (- x 1)) (setq res (+ res 1)) )) F1 >(f1 5) |
Существует и более простой в обращении цикл LOOP:
| loop | (loop форма 1 форма2…) Функция повторяет вычисление своих форм до тех пор, пока среди них не встретится оператор RETURN |
| return | (return результат) Функция позволяет выйти из цикла и вернуть значение для операторов LOOP и PROG. |
Модифицируем факториал с помощью LOOP:
| >(defun f1 (x) (progn (setq res 1) (loop (setq res (* res x)) (setq x (- x 1)) (if (eql x 0) (return res)) ))) F1 >(f1 5) |
Наконец, последним алгоритмическим средством, рассматриваемым в этом разделе, является оператор PROG, позволяющий выполнять программирование в традиционном процедурном стиле. Сразу отметим, что оператор PROG не имеет почти ничего общего с PROG1 и PROGN.
| prog | (prog(переменная1 переменная2… ) оператор1 оператор2…) позволяет программировать в традиционном процедурном стиле, используя передачу управления между последовательными операторами. Позволяет использовать в качестве своих форм операторы GO и RETURN |
| go | (go метка) Функция позволяет выполнить внутри оператора PROG переход на некоторую метку. Форма считается меткой если она является символом или числом. |
Приведём в качестве примера работы с функцией PROG следующий код, вычисляющий степень некоторого числа.
| >(defun exp1 (x n) (prog (res) (setq res x) loop (if (= n 1) (return res)) (setq res (* res x)) (setq n (- n 1)) (go loop) ) ) EXP1 >(exp1 2 3) |
Рекурсия
Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. В математике рекурсия применяется повсеместно, например, следующее определение рекурсивно: "0 является натуральным числом; натуральное число плюс единица есть натуральное число".
С точки зрения реализации различают прямую рекурсию (когда процедура содержит ссылку на себя) и косвенную (когда процедура содержит ссылку на другую процедуру, содержащую ссылку на исходную). Более подробная информация о рекурсии вообще может быть найдена в источнике (Вирт, 1986).
В большинстве процедурных языков программирования рекурсия является скорее нежелательным методом программирования (вследствие возможности переполнения стека), однако в Lisp она является не только допустимой без ограничений, но, более того, является основным инструментом организации циклов. В чистом Lisp операторы DO и LOPP, а тем более PROG отсутствуют, и должны быть заменены рекурсией. Здесь мы рассмотрим основные приёмы использования этого механизма.
Простейшая рекурсия заключается в том, что некоторая функция вызывает сама себя для проведения некоторых вычислений. Рекурсия отражает рекуррентные соотношения (когда в ряду значений каждое новое вычисляется на основании предыдущих). Простейшим примером является факториал, который задаётся в частности как n!=n* (n-1)!. В примере с функцией DO было рассмотрено вычисление факториала с помощью цикла. С помощью рекурсии можно вычислить его так:
| >(defun fc2 (x) (cond ((eql x 0) 1) ((eql x 1) 1) (T (* x (fc2 (- x 1)))))) FC2 >(fc2 5) |
Как видно из примера, рекурсивный вызов полностью отражает рекуррентное соотношение, описывающее факториал. Тем не менее, можно с помощью такого же метода организовывать и циклы, например, в следующем примере функция создаёт список из элементов от 1 до n
| >(defun lst2 (x lst) (cond ((eql x 0) lst) (T (lst2 (- x 1) (cons x lst))))) LST2 >(LST2 5 nil) (1 2 3 4 5) |
Основной проблемой, которая может возникнуть при работе с таким механизмом, является бесконечная рекурсия. Бесконечная рекурсия возникает вследствие логических ошибок в программе и приводит к зацикливанию алгоритма и исчерпанию системных ресурсов машины. Примером бесконечной рекурсии может быть следующее выражение:
| >(defun err1 () (err1)) ERR1 >(err1) Error: Stack overflow (signal 1000) [condition type: SYNCHRONOUS-OPERATING-SYSTEM-SIGNAL] |
В этом примере функция ERR1 выполняет свой рекурсивный вызов всегда, тем самым, вызывая переполнение стека и ошибку. Для того, чтобы избегать подобного, необходимо следовать следующим простым правилам:
· В теле функции всегда должно присутствовать правило, гарантирующее выход из рекурсии.
· Правила, гарантирующие выход из рекурсии, должны предшествовать правилам, содержащим рекурсию
Даже при соблюдении таких правил зацикливание всё равно возможно, поэтому необходимо использовать отладку. Отладка рекурсивных функций является, вообще говоря, не слишком простым делом. Для неё используется функция TRACE
| trace | (trace функция) Функция позволяет выводить на экран дерево вызовов некоторой функции. |
| untrace | (untrace функция) Функция позволяет отменить режим вывода дерева вызовов некоторой функции, установленный функцией trace. |
В качестве примера приведём всё то же вычисление факториала:
| >(defun fc2 (x) (cond ((eql x 0) 1) ((eql x 1) 1) (T (* x (fc2 (- x 1)))) )) FC2 >(fc2 5) >(trace fc2) (FC2) >(fc2 5) 0: (FC2 5) 1: (FC2 4) 2: (FC2 3) 3: (FC2 2) 4: (FC2 1) 4: returned 1 3: returned 2 2: returned 6 1: returned 24 0: returned 120 |
Подобный механизм способен существенно упростить отладку рекурсивных функций. К сожалению, не все версии Lisp позволяют выполнять отладку нескольких функций одновременно.
В заключение обсуждения простой рекурсии рассмотрим некоторые примеры операций над списками, реализуемые с помощью рекурсии.
Функционалы
В математике под функционалом понимается функция, имеющая своим аргументом другую функцию. Соответственно, в языках программирования, в том числе в Lisp, функционалом является функция, принимающая некоторыми своими аргументами "процедурный" тип данных.
Первым делом параметр-функцию надо передать, подавив её вычисление. Для этого используется функция FUNCTION
| function | (function функция аргументы) Функция позволяет подавить вычисление своего параметра. Действует аналогично QUOTE, но для аргументов функционального типа. В большинстве случаев функциональный параметр используется вместе с QUOTE, однако FUNCTION может быть использована для указания, что в качестве параметра следует ждать именно функцию. |
Другая задача - вычислить переданный таким образом аргумент.
| funcall | (funcall функция) Обратная FUNCTION функция, позволяющая отменить подавление вычисления. |
| >(FUNCALL (FUNCTION (LAMBDA (X Y) (* X Y)) ) 2 4) |
В приведённом примере с помощью LAMBDA задаётся функция, принимающая два аргумента и возвращающая их произведение. Вычисление этой функции подавляется с помощью FUNCTION (иначе мы получили бы ошибку о недопустимом числе аргументов). Затем над результатом, а именно функциональным аргументом, выполняется FUNCALL, с указанием двух аргументов - 2 и 4. Как видно, результатом было искомое произведение.
Приведём пример использования функционала. Например, мы хотим вычислить экстремум в некоторой последовательности:
| >(defun extremum (lst fn el) (cond ((eq (cdr lst) nil) (car lst)) ((funcall fn (car lst) (extremum (cdr lst) fn el)) (car lst)) (T (extremum (cdr lst) fn el)))) EXTREMUM |
Теперь вычислим минимум и максимум в последовательностях:
| >(extremum '(6 -3 1 2 3) (function <) 1000) -3 >(extremum '(6 -3 1 2 3) (function >) -1000) |
Таким образом, в зависимости от переданного в функцию функционального аргумента (< или >) мы вычисляем минимум или максимум. Третьим параметром функции является условно наибольшее и наименьшее число. В принципе, можно таковым считать первый символ последовательности (пример апеллирует к определённой ранее функции EXTREMUM).
| >(defun extremum2 (lst arg) (extremum (cdr lst) arg (car lst))) EXTREMUM2 >(extremum2 '(1 2 3) (function <)) >( extremum2 '(1 2 3) (function >)) |
В Lisp присутствует также некоторое количество стандартных функций с функциональными аргументами, которые в основном также как и в нашем примере реализуют работу с последовательностями. Различают два основных класса функционалов - отображающие и применяющие. Применяющими функционалами являются уже известный нам FUNCALL, а также APPLY.
| apply | (apply функция аргумент) Функционал применяет некоторую функцию к аргументам, которые заданы списком в качестве второго параметра APPLY |
| >(apply 'car '((a b))) A >(funcall 'car '((a b))) (A B) |
Отметим, что не все функции могут использоваться в качестве функциональных аргументов, например, использование OR и AND даёт ошибку (интерпретатор аргументирует это тем, что OR, AND и некоторые другие функции имеют некую специальную реализацию).
Общая идея, объединяющая применяющие функционалы, заключается в применении функций к спискам аргументов. Отображающие функционалы предназначены для повторения вычисления функции на элементах списка.
| mapcar | (mapcar функция список) Функция, позволяющая выполнить некоторое вычисление последовательно надо всеми элементами списка. Результатом является список, построенный из результатов применения функционального аргумента к элементам списка. |
| >(mapcar 'null '(() (a b) (nil c d))) (T NIL NIL) >(mapcar '(lambda (x) (cons x nil)) '(a b c)) ((A) (B) (C)) |
| maplist | (maplist функция список) Функция, позволяющая выполнить некоторое вычисление последовательно над хвостовыми частями списка. Сперва вычисляется функция от списка, затем (CDR список), затем (CDDR список), (СDDDR список) и так далее. Результатом является список, построенный из результатов применения функционального аргумента к хвостовым элементам списка. |
| >(maplist '(lambda (x) x) '(a b c)) ((A B C) (B C) (C)) |
С помощью таких функционалов можно существенно сократить тексты функций в некоторых специальных случаях. Например, так выглядит вычисление максимума:
| >(defun max2 (lst) (progn (setq x (car lst)) (mapcar '(lambda (y) (if (< x y) (setq x y))) lst) x)) MAX2 >(max2 '(1 2 3)) |
| mapcan mapcon | (mapcan функция список) (mapcon функция список) Аналоги MAPCAR и MAPLIST, однако при своей работе строят список, используя функцию NCONC, т.е. потенциально структура исходных данных может разрушиться. Эти функционалы называются объединяющими, и одно из основных проявлений их особенностей заключается в уничтожении всех вхождений NIL в результирующий список. |
| >(setq x '(A B C)) (A B C) >(mapcar 'list x) ((A) (B) (C)) >(mapcan 'list x) (A B C) >(maplist 'list x) (((A B C)) ((B C)) ((C))) >(mapcon 'list x) ((A B C) (B C) (C)) |
Используем способность объединяющих функционалов уничтожать NIL для написания функции, проверяющей вхождение элемента в список:
| >(defun isinlist (lst el) (car (mapcan (function (lambda (y) (if (eql y el) '(t) nil))) lst))) ISINLIST >(isinlist '(1 2 3) 2) T >(isinlist '(1 2 3) 4) NIL |
| mapc mapl | (mapc функция список) (mapl функция список) Аналоги MAPCAR и MAPLIST, однако эти функции не строят никакого нового результата, а просто возвращают исходный список. Таким образом, для них может быть важен только некоторых побочный результат, в том случае, если использованная в качестве параметра функция содержит в той или иной форме присвоение, вывод на экран и т.п. |
В качестве примера такого побочного действия рассмотрим вывод на экран.
| >(mapc 'print '(A B C)) A B C (A B C) |
Таким образом, все элементы списка были по очереди выведены, а в качестве результата вернулся исходный список. Очевидно, этот же эффект мог быть достигнут и MAPCAR, и MAPCAN, однако при этом не тратились ресурсы на конструирование новых структур в памяти.
Функционалы не обязательно работают с функциями одного аргумента. Если аргументов больше, требуется подача на вход нескольких списков. В качестве примера рассмотрим преобразование двух списков в третий, содержащий в себе произведения элементов исходных списков, находящихся в одинаковых позициях.
| >(mapcar '* '(1 2 3) '(4 5 6)) (4 10 18) |
Или, например, попарное объединение элементов двух списков:
| >(mapcar 'list '(1 2 3) '(4 5 6)) ((1 4) (2 5) (3 6)) |
Расширением этого примера может быть вычисление скалярного произведения двух векторов (в примере [1 2 3] и [4 5 6]):
| >(apply '+ (mapcar '* '( 1 2 3) '(4 5 6))) |
В случае, если у списков параметров не совпадают размеры, лишние элементы списков будут просто проигнорированы:
| >(mapcar 'list '(1 2 3) '(4 5)) ((1 4) (2 5)) |
Для MAPC и MAPL возвращаемым значением всегда будет первых аргумент-список.
Макросы
Макросом называется специальная функция, которая вычисляется не сразу а в два этапа: сперва вычисляется её тело, и только потом тело применяется к аргументам. Это бывает полезно, например, если мы хотим сформировать последовательность вычислений программно, а затем эту последовательность выполнить.
| defmacro | (defmacro имя лямбда-список тело) Определяет макрос. Синтаксис определения макроса в целом сходен с синтаксисом определения функции, однако при вызове макроса не происходит предварительное вычисление его аргументов. |
Первый этап вычисления макроса называется этапом расширения. На этом этапе макрос преобразуется в вычисляемую форму. На втором этапе эта форма вычисляется и возвращается результат.
В качестве примера макроса определим функцию SETQQ, которая была бы аналогична SETQ, но не требовала явного подавления вычисления второго аргумента.
| >(defmacro setqq (x y) (list 'setq x (list 'quote y))) SETQQ >setqq x (a b c)) (A B C) >x (A B C) |
| macroexpand | (macroexpand макровызов) Функция возвращает результат расширения макроса. Имеет важное значение для тестирования. |
Для того, чтобы посмотреть, какая именно форма была вычислена, применим следующий вызов:
| >(macroexpand '(setqq x (a b c))) (SETQ X '(A B C)) T |
В том, что, несмотря на выведенное на печать значение T, функция возвращает именно результат раскрытия макроса, можно убедиться на следующем примере:
| >(setq x (macroexpand '(setqq x (a b c)))) (SETQ X '(A B C)) >x (SETQ X '(A B C)) |
Контекст вычисления макроса отличается от контекста вычисления функции. На этапе раскрытия в макросе могут использоваться все статические связи, созданные при его определении, однако когда происходит вычисление, текст макроса полностью подменяется на результат расширения его определения, и все статические связи становятся недоступны.
В принципе, макросы могут при расширении давать формы, содержащие в себе макровызовы, в том числе и рекурсивные. Эти формы будут расширены и вычислены на этапе вычисления основного макроса.
Макросы могут быть рекурсивными. Это означает, что расширение макроса даёт нам новый макрос. Рекурсивные макросы сродни рекурсивным функциям, за исключением того, что вычисление нового макровызова также производится в два этапа. В качестве примера рекурсивного макроса приведём следующий макрос, считающий сумму чисел в списках специального вида:
| >(DEFMACRO UNWRAP (X Y) (cond ((atom Y) (list '+ X Y)) (T (list '+ X (list 'UNWRAP (car y) (cadr y)))))) UNWRAP >(unwrap 1 2) >(unwrap 1 (2 3)) >(unwrap 1 (2 (3 4))) >(macroexpand '(unwrap 1 (2 (3 4)))) (+ 1 (UNWRAP 2 (3 4))) |
Естественно, отладка подобных макросов является достаточно трудоёмкой задачей.
Также как и для функций, для параметров макросов можно использовать зарезервированные слова &OPTIONAL, &KEY, &REST и &AUX. Дополнительно можно использовать свойство параметра &WHOLE, которое свяжет параметр со всей формой макровызова. Особенно полезно это в макросах, способных динамически менять свой код с помощью псевдофункций, таких как RPLACA, RPLACD, SETF м другие. В качестве примера приведём макрос, который сам себя превращает в функцию CAR:
| >(defmacro frst (arg &whole call) >(rplaca call 'car)) FRST >(frst '(1 2)) |
С макросами тесно связан механизм обратной блокировки, позволяющий упростить их запись. Обратная блокировка изображается символом ` (апостроф, наклонённый вправо) и отличается от обычной тем, что внутри такого выражения можно управлять вычислением или невычислением секций. Например, запятая указывает, что следующее выражение должно быть вычислено. Символ @ позволяет включить идущее после него выражение в результирующий список.
| >`(a ,(+ 1 2) 3) (A 3 3) >(setq x '(+ 1 2)) (+ 1 2) >`(a ,@x 3) (A + 1 2 3) |
Ввод и вывод
Одной из основных задач для каждого языка программирования является организация взаимодействия с пользователем. В Lisp для этой цели предусмотрены функции ввода-вывода для стандартного устройства, а также функции работы с файлами.
| read | (read [поток]) Функция читает выражение из консоли и возвращает его в качестве результата. Функция никак не показывает пользователю, что ожидается ввод. В этой функции и далее: если поток не указан, чтение (или для других функций запись) производится со стандартного устройства ввода - консоли. |
| >(read) >>a+b A+B |
Здесь при вызове функции READ пользователь ввёл выражение A+B (символ >> символизирует приглашение к вводу и не должен переноситься в текст при попытке выполнить пример). Результатом вычисления явилось собственно введённое выражение.
В качестве примера рассмотрим вычисление суммы от двух введённых чисел:
| >(* (read) (read)) >>3 >>8 >(* (read) (read)) >>3 8 |
Иными словами, Lisp, как и большинство языков высокого уровня, выполняет синтаксический разбор ввода с консоли и выделяет параметры, идущие через пробел. При этом READ вводит именно выражения, т.е. если бы в примере мы ввели, например, (+ 5 7) (- 6 4) то этот ввод также был бы распознан как два параметра, другое дело что подобное выражение недопустимо в рамках примера. Модифицируем пример следующим образом:
| >(* (eval (read)) (eval (read))) >>(+ 5 7) (- 6 4) |
Некоторые символы в Lisp при вводе указывают интерпретатору на выполнение определённых действий (например, скобки, пробел, точка). Lisp хранит информацию о таких символах в специальной таблице, называемой таблице чтения. Эти символы называются макрознаками, и их набор может быть изменён (вследствие чего, естественно, может измениться и синтаксис языка Lisp).
| set-macro-character | (set-macro-character символ функция) Функция сопоставляет символу некоторую функцию, обрабатывающую этот символ при синтаксическом разборе выражений. Функция разбора должна иметь два аргумента - поток чтения и собственно символ, который мы обрабатываем. |
Следующий пример заставляет Lisp интерпретировать символ % так же, как апостроф (т.е. как функцию QUOTE)
| >(SET-MACRO-CHARACTER #\% (lambda (stream char) (list 'quote (read)))) T > %(A) (A) |
| print prin1 princ | (print выражение [поток]) (prin1 выражение [поток]) (princ выражение [поток]) Функция выводит данные на консоль. PRINT выводит данные, печатает пробел и переводит строку. В различных диалектах указанные действия производятся в различной последовательности. Кроме того, иногда функция не печатает пробел. PRIN1 работает точно также, но не переводит строку. PRINC работает также, как и PRIN1, но преобразует при выводе некоторые типы данных (например, строковые) к более приятному для восприятия виду. |
| >(progn (setq data "a b c d") (print data) (prin1 data) (princ data)) "a b c d" "a b c d"a b c d "a b c d" |
Как видно из примера, в Allegro Common Lisp функция PRINT сперва перевела строку, а затем вывела данные и пробел. Затем функция PRIN1 вывела те же самые данные, но строку не перевела и пробел не напечатала. Наконец, PRINC вывела всё ту же самую строку, но при выводе исключила кавычки. Однако, результатом этой функции, как мы видим, является всё та же строка.
| terpri | (terpri [поток]) Функция переводит строку в стандартном устройстве вывода. |
| format | (format поток образец [аргументы]) Функция выводит строку в соответствии с образцом. Если вы качестве потока задаётся Т, то вывод производится на экран, в противном случае необходимо указать ассоциированный с файлом и открытый поток вывода. В качестве образца в функцию подаётся строка, определяющая формат вывода (в чём-то сходная со строкой форматирования функции printf языка С). Значения управляющих символов в строке даны в таблице 1. Текст в образце, не являющийся управляющими символами, также печатается. Функция возвращает в качестве своего значения nil. |
Таблица 1
Символы управления выводом функции format
| Символ | Смысл |
| ~% | Перевод строки |
| ~S | Вывод очередного аргумента функцией PRIN1 |
| ~A | Вывод очередного аргумента функцией PRINС |
| ~nT | Начинает вывод с колонки n. Если она уже была достигнута, выводится пробел. |
| ~~ | (Два знака тильды подряд) Вывод самого знака тильды |
| >(format t "~~Первый параметр ~A и второй параметр ~S" 5 7) ~ 5 7 NIL |
Данная функция весьма удобна при выводе таблиц:
| >(format t "~10T~%~A~10T~A~%~A~10T~A~%~A~10T~A~%" 1 2 3 4 5 6) 1 2 3 4 5 6 |
Файловый ввод и вывод несколько отличается от работы с консолью. Во-первых, для работы с файлом его надо ассоциировать с потоком и открыть. Во-вторых, по окончании работы с файлом его надо закрыть. Также различаются файлы последовательного доступа, где записи могут быть получены последовательным чтением с начала файла, и файлы прямого доступа, в которых в любой момент можно обратиться к каждой записи.
Для работы с файлами в Lisp предусмотрены следующие средства. Во-первых, определены специальные символы, указывающие на стандартное устройство ввода и стандартное устройство вывода. Эти символы, например, могут применяться в функциях PRIN1, PRINC и READ, а также FORMAT.
| *STANDARD-INPUT* *STANDARD-OUTPUT* | Символы указывают на стандартные устройства ввода и вывода соответственно (т.е. клавиатуру и экран). |
Можно также связать какой-либо поток с файлом, используя специальные функции.
| open | (open файл направление_обмена) Функция открывает файл для чтения или записи. Если файл необходимо открыть для чтения, в качестве направления обмена указывается :INPUT, если для записи -:OUTPUT. Для одновременного чтения и записи указывают направление обмена :IO.В качестве возвращаемого значения передаётся открытый поток, который может быть использован в других функциях. |
| close | (close поток) Функция закрывает поток, открытый ранее с помощью OPEN |
| with-open-file | (with-open-file (имя_потока имя_файла направление_обмена) формы) Функция открывает поток, выполняет все формы и закрывает поток, не требуя от пользователя никаких дополнительных действий. |
Отдельно следует отметить функцию, существенно облегчающую написание Lisp-программ и позволяющую создавать их во внешних редакторах и дробить на части:
| load | (load имя_файла) Функция загружает и исполняет код на языке Lisp, хранящийся в указанном файле. |
Типы данных
Иерархия типов
Типы данных являются классами и подклассами используемых в программах на Lisp объектов. Как и в большинстве других языков, в Lisp различают простые и составные типы данных.
Зато важным отличием является то, что тип данных связывается не с именем символа, а с его значением, что в общем-то характерно для интерпретаторов (аналогичный механизм используется, например, в весьма популярном языке JavaScript). Присвоение переменной значения всегда является корректным, независимо от того, что это за переменная и что это за значение. Поэтому Lisp иногда называют нетипизированным (в другом варианте бестиповым) языком. Тем не менее, типы данных в нём есть, а термин обозначает лишь отсутствие жёсткой типизации.
В виду отсутствия жёсткой типизации важное значение имеет преобразование типов и проверка на принадлежность какому-либо типу.
| typep | (typep объект тип) Функция возвращает Т, если объект имеет указанный тип, и NIL в противном случае. |
| type-of | (typep объект) Функция возвращает имя типа, который имеет объект. |
| coerce | (coerce объект тип) Функция преобразует тип объекта в указанный параметром функции COERCE. |
В качестве примера приведём следующий код:
| >(type-of 'ATOM) SYMBOL >(type-of 1) FIXNUM >(type-of '(A B C)) CONS >(typep 'A 'atom) T >(typep 'A 'symbol) T >(typep 'A 'fixnum) NIL |
Таким образом, мы видим, что один и тот же символ может принадлежать к нескольким типам одновременно, т.е. между типами существуют отношения иерархии.
В таблице 2 приводится полный список всех простых типов языка Lisp, а в таблице 3 - составных ( в соответствии со спецификацией ANSI Lisp):
Таблица 2
Полный перечень простых типов языка Lisp.
| arithmetic-error | division-by-zero | function | real | simple-condition |
| array | double-float | generic-function | restart | simple-error |
| atom | echo-stream | hash-table | sequence | simple-string |
| base-char | end-of-file | integer | serious-condition | simple-type-error |
| base-string | error | keyword | short-float | simple-vector |
| bignum | extended-char | list | signed-byte | simple-warning |
| bit | file-error | logical-pathname | simple-array | single-float |
| bit-vector | file-stream | long-float | simple-base-string | standard-char |
| broadcast-stream | fixnum | method | simple-bit-vector | standard-class |
| built-in-class | float | method-combination | style-warning | standard-generic-function |
| cell-error | floating-point-inexact | nil | symbol | standard-method |
| character | floating-point-invalid-operation | null | synonym-stream | standard-object |
| class | floating-point-overflow | number | t | storage-condition |
| compiled-function | floating-point-underflow | package | two-way-stream | stream |
| complex | random-state | package-error | type-error | stream-error |
| concatenated-stream | ratio | parse-error | unbound-slot | string |
| Condition | rational | pathname | unbound-variable | string-stream |
| Cons | reader-error | print-not-readable | undefined-function | structure-class |
| control-error | readtable | program-error | unsigned-byte | structure-object |
| vector | warning |
Таблица 3
Полный перечень составных типов языка