Теоретические сведения. В этой работе Вы познакомитесь с языком программирования Лисп

В этой работе Вы познакомитесь с языком программирования Лисп. Мы будем использовать диалект Лиспа, известный как Common Lisp.

Название языка Лисп происходит из “list processing” (обработка списков). Лисп представляет собой язык так называемого функционального программирования. Он основан на алгебре списочных структур, лямбда-исчислении и теории рекурсивных функций.

Первая реализация языка Лисп 1 появилась в 1958 г. для машины IBM 704. Разработчиком языка стал доцент Массачусетского технологического института (MIT) Джон Маккарти. За период с 1958-1963 г Лисп претерпел некоторые изменения и дополнения. В 1963 г появляется версия Лисп 1.5 для машины IBM 7090. В этом виде Лисп стал стандартом. Однако широкое признание язык получил в начале 80-х годов. До этого времени он использовался в различных университетских исследовательских проектах.

В Лиспе формы представления программ и обрабатываемых ее данных одинаковы. И то и другое представляется списочной структурой, имеющей одинаковую форму. Таким образом, программы могут обрабатывать и преобразовывать другие программы и даже самих себя. Используемое в Лиспе, так называемое, функциональное программирование основывается на той простой идее, что в результате каждого действия возникает значение. Значения становятся аргументами следующих действий, и конечный результат всей задачи выдается пользователю. Функции также могут являться аргументами и возвращаться в качестве значений других функций.

Атомы и списки

Основными типами данных языка Лисп являются атомы и списки.

Атомами являются символы и числа. В Лиспе используется много различных типов чисел. Символ – это имя, состоящее из букв, цифр и специальных знаков. Символы T и NIL имеют в Лиспе специальное значение. T обозначает логическое значение истина, а NIL – логическое значение ложь. Числа и логические значения T и NIL являются константами, остальные символы – переменными.

Список в Лиспе – это последовательность, элементами которой являются атомы либо списки (подсписки). Списки заключаются в круглые скобки, элементы списка разделяются пробелами.

Например,

(+ 2 3) – список из трех элементов

(a b (c d) e) – список из четырех элементов

Список, в котором нет ни одного элемента, называется пустым списком и обозначается () или NIL.

Атомы и списки называются символьными выражениями или s-выражениями.

Функции

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

Например, выражение 2 + 3 будет записано в Лиспе как (+ 2 3), а вызов функции f(x, g(y, x)) будет записан в Лиспе как (f x (g y z)).

Лисп содержит функцию quote или ’ (апостроф), которая требует одного аргумента и возвращает этот аргумент без вычисления.

Основные функции обработки списков

Функция car возвращает голову переданного в качестве аргумента списка (первый элемент списка называется головой, а остаток списка – хвостом).

Функция cdr возвращает хвостовую часть списка.

Функция nth возвращает элемент списка по его номеру. Эта функция получает два аргумента: первый – номер элемента в переданном в качестве аргумента списке (нумерация начинается с нуля); второй – сам список.

Функции first, second., third, … возвращают соответственно первый, второй, третий, … элементы переданного в качестве аргумента списка.

Функция last возвращает последний элемент списка.

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

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

Диаграммы s-выражений

Базовый элемент этих диаграмм называется списочной ячейкой (cons-cell). Списочная ячейка состоит из 2-х частей: полей CAR и CDR, т.е. частей, содержащих голову и хвост списка. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или некоторый другой лисп-объект, например, атом. Графически списочная ячейка представляется следующим образом:

Для представления списка используют одну списочную ячейку для каждого элемента списка. Первая часть ячейки заполняется именем атома, если элемент является атомом, или указателем на другой список, если элемент является списком. Вторая часть списочной ячейки содержит указатель на следующий элемент списка или знак \ (слэш), если этот элемент является последним элементом списка.

На рисунке 4.1 приведено несколько примеров представления конструкций языка в виде диаграмм списочных ячеек:

 

(+ 3 5)

 

 

(* (a b (c)))

 

 

Рис. 4.1. Изображение списков в виде диаграмм списочных ячеек