Министерство образования Республики Беларусь

белорусский государственный университет

информатики и радиоэлектроники

Кафедра программного обеспечения информационных технологий

И.А.Мурашко, И.М.Марина

МЕТОДИЧЕСКОЕ ПОСОБИЕ

по курсу "Функциональное и логическое программирование"

для студентов специальности Т10.02.00

"Программное обеспечение информационных технологий"

Часть 1

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

Минск 2002

УДК 681.3

Мурашко И.А., Марина И.М. Методическое пособие по курсу "Функциональное и логическое программирование" для студентов специальности Т10.02.00 "Программное обеспечение информационных технологий" Часть 1 “Язык программирования Лисп” - Мн.: БГУИР, 2002. - с.

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

Рис. 2, .

 И.А.Мурашко, И.М.Марина

Введение

Язык функционального программирования Лисп (Lisp) был разработан в 1958 году Джоном МакКарти (John McCarthy). Название Лисп (Lisp) происходит от List processing (обработка списков). Лисп представляет собой язык функционального программирования. Он основан на алгебре списочных структур, лямбда-исчислении и теории рекурсивных функций. Cсуществует несколько диалектов языка Лисп: Lisp1 (1958), MacLisp (1964), InterLisp (1972), CommonLisp (1984). Диалект CommonLisp получил наибольшее распространение.

Первые реализации языка были интерпретаторами и особой скоростью не отличались. В настоящее время все коммерческие и некоторые бесплатные реализации имеют качественные оптимизирующие компиляторы. По разнообразию типов данных Лисп превосходит любой другой язык: числа целые, целые с неограниченным числом знаков, вещественные, дробные (выполнение (/ 1 3) вернет 1/3, а не 0.3333333...), комплексные, списки, массивы, строки, символы, последовательности, функции, структуры, макросы, классы и объекты. В Лиспе типы привязываются к значению переменной, а не к ее имени, поэтому легко создавать разнотипные списки и массивы

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

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

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

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

Рис.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. Таким образом, список - это многоуровневая или иерархическая структура данных, в которой открывающие и закрывающие скобки находятся в строгом соответствии. Например, приведенные ниже выражения являются правильно составленными списками:

(+ 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 можно выделить из списка его голову и хвост.

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

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