Краткие теоретические сведения по программированию на языке Лисп

Язык функционального программирования Лисп (Lisp) был разработан в 1958 году Джоном МакКарти (John McCarthy). Название Лисп (Lisp) происходит от List processing (обработка списков). Лисп представляет собой язык функционального программирования. Он основан на алгебре списочных структур, лямбда-исчислении и теории рекурсивных функций. Принципы, положенные в основу языка LISP: использование единого спискового представления для программ и данных, применение выражений для определения функций, скобочный синтаксис языка. Таким образом, LISP представляет собой интерпретирующую систему, а это позволяет значительно облегчить и ускорить процесс создания сложных комплексов программ в интерактивном режиме, так как обеспечивает немедленную реакцию системы на изменения, вносимые пользователем, и предоставляет мощные средства отладки и редактирования программ.

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

Второй особенностью является применение в качестве основной управляющей структуры не итерации (цикла), как в языках императивного программирования, а рекурсии.

Третья особенность состоит в широком использовании структуры данных "связанный список", поэтому обработка списков лежит в основе большинства алгоритмов языка LISP.

Классификация простейших типов данных в языке LISP представлена на рисунке 1.

Рис.1. Классификация простейших типов данных

Атом является основным простейшим типом данных. Атомы могут быть числовыми, литеральными и строковыми.

В нотации Бэкуса-Наура это выглядит так:

<Атом>::= <Числовой_атом> | <Литеральный_атом> |         <Строковый_атом> | T | NIL

Литеральный атом (идентификатор) - это последовательность букв и цифр, начинающаяся с буквы.

К литеральным атомам относятся специальные литеральные атомы:

• NIL - логическое значение "ложь" и одновременно обозначение пустого списка,
• T - логическое значение "истина".

В нотации Бэкуса-Наура это выглядит так:

<Литеральный_атом>::= <Буква> |                         <Буква> <Последовательность> <Последовательность>::= <Правильный_символ> | <Правильный_символ> <Последовательность> <Правильный_символ>::= <Буква> | <Цифра> <Цифра>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 <Буква>::= A | B | C | D | E | F | G | H | I | G | K |            L | M | N | O | P | Q | R | S | T | U | V |             W | X | Y | Z |           a | b | c | d | e | f | g | h | i | j | k |            l | m | n | o | p | q | r | s | t | u | v |             w | x | y | z | <Числовой_атом>::= <Целое_без_знака> |                   +<Целое_без_знака> |                   -<Целое_без_знака> <Целое_без_знака>::= <Цифра> | <Цифра> <Целое_без_знака> <Цифра>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 <Строковый_атом>::= "<Последовательность любых символов, не содержащая символа кавычка>"

 

На этом шаге мы продолжим изучение простейших типов данных, в частности, введем такое понятие, как точечная пара.

Синтаксически точечная пара определяется следующим образом:

<Точечная пара>::=     (<Атом>. <Атом>) | (<Атом>. <Точечная пара>) |     (<Точечная пара>. <Атом>) |      (<Точечная пара>. <Точечная пара>)

 

Таким образом, точечная пара - это упорядоченная пара, элементами которой могут быть как атомы, так и точечные пары, а точка играет роль разделителя. Приведем примеры точечных пар:

(JOHN. SMITH) (SIN. (X. (PLUS. Y))) (A. ((B. 1). NIL))

Часто бывает удобно не различать атомы и точечные пары. В этом случае говорят о S-выражениях (от Symbolic ─ символьный). Таким образом, по определению

S ─ выражение::= Атом ¦ Точечная пара    

или же

S ─ выражение::= Атом | (S-выражение. S ─ выражение)

"S ─ выражение ─ это либо атом, либо левая скобка, за которой следуют S-выражение, точка, S-выражение и правая скобка".

Основным фундаментальным типом данных в языке LISP является список. Название языка LISP образовано от "LISt Processing" ("обработка списка").

Список рекурсивно определяется так:

   Список::= NIL | (S ─ выражение. Список)

Согласно этому определению любой непустой список является точечной парой.

Приведем примеры списков:

(LISP Functional language) (5 6 (8 (9)) 23 NIL)

Важно выделить понятие пустого списка, который не содержит элементов, он обозначается () или атомом NIL. Например, (NIL ()) ─ список, состоящий из двух пустых списков. Оперативная память компьютера, на котором "работает" LISP, логически разбивается на маленькие области, которые называются списочными ячейками. Списочная ячейка состоит из полей с именами CAR и CDR, каждое из которых содержит указатель. Указатель может ссылаться на другую списочную ячейку или на другой объект языка LISP, например, на атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый атом, известный системе, записан в определенном месте памяти лишь один раз. Графически списочную ячейку будем представлять прямоугольником, разделенным на поля CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на который ссылается указатель.

 

Пример 1. Изобразим список (A B C D) в графической нотации:

Рис.2. Список (A B C D)

 

Пример 2. Список (A (16 (A 25)) (B) (21)) в графической нотации имеет вид:

 

 

Пример 3. Список (A (16 (A 25)) (B) (21)) в графической нотации имеет вид:

 

 

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

Пример 4. Структура, графическое представление (A. NIL)  имеет вид:

 

Пример 5.  Структура с графическим представлением (A. (B. NIL)) имеет вид:

Пример 6. Точечная пара (A. B) с графическим представлением имеет вид:

 

Пример 7. Точечная пара (A. (B. C)) с графическим представлением имеет вид:

 

Точечная запись списков обладает некоторыми преимуществами по сравнению со списочной записью. Она является более общей, так как любой список можно переписать в точечных обозначениях, но уже простейшее точечное выражение (A. B) ─ не может быть представлено списочной записью. Когда выражение строится из небольшого, и главное, заранее известного количества элементов, точечные конструкции предпочтительнее. Если же число элементов сравнительно велико и может быть переменным, то целесообразнее пользоваться списочными конструкциями. Существует правило, позволяющее упростить запись точечных выражений. Для возврата от точечной записи к списочной необходимо: если точка стоит перед открывающей скобкой, то она заменяется пробелом и удаляется одновременно открывающаяся и парная ей закрывающаяся скобка. Это же правило позволяет избавиться и от лишних NIL. Это правило разрешается применять к любому правильно построенному S-выражению.

К примеру:

запись (A. (B. C))  эквивалентна (A B. C), запись ((A. B). (C. D)) эквивалентна ((A. B) C. D).

По сокращенной точечной записи можно восстановить полную точечную запись. Для этого каждый пробел заменяется точкой, за которой ставится открывающая скобка. Соответствующая закрывающая скобка вставляется непосредственно перед ближайшей справа от этого пробела закрывающей скобкой, не имеющей парной открывающей скобки также справа от пробела. Используя точечную нотацию, можно сократить объем необходимой памяти. Например, структура данных (A B C), представленная в виде списочной записи, требует трех ячеек, хотя те же данные можно представить в виде (A B. C), требующем только двух ячеек.

Так как в Лиспе не только данные представляются в виде s-выражений, но и программы. Выполнение программы состоит в вычислении s-выражений. Вычисляемое s-выражение характеризуется определенной семантикой, которая анализиру­ется интерпретатором. Если результаты анализа не противоречат семантике языка, то интерпретатор вычисляет значение s-выражения. Они называются фор­мами.

На рисунке 5.4 приведена обобщенная схема интерпретации s-выражений, работа которой состоит из трех шагов. На первом шаге проис­ходит считывание s-выражения с помощью встроенной функции READ. По умолчанию исходные s ─ выражения вводятся с клавиатуры. На втором шаге выполняется интерпретация s-выражения с помощью функ­ции EVAL, которая является вызовом интерпретатора. На третьем шаге функция PRINT осуществляет вывод значения s-выражения. По умолчанию вычисленные значения выводятся на дисплей. Затем цикл READ ─ EVAL ─ PRINT повторяется для другого s ─ выражения и т.д.

 

Рис.1. Схема интерпретации s-выражений

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

(f_n a₁ a₂ …a_n),

где f_n - имя вызываемой функции; аи аг... а_п - аргументы функции, кото­рые задаются вычисляемыми s- выражениями.

К примеру, если требуется вычислить сумму чисел 5 и 3, то с клавиа­туры вводится следующее s-выражение (+ 5 3). Результат интерпретации следующий:

>(+ 5 3)

8

>

Здесь знак "+" соответствует имени функции, вы­полняющей сложение.

В общем случае формы могут быть заданы константами, перемен­ными, списками. Константы соответствуют самоопределяемым формам, которые представляют самих себя и имеют фиксированные значения (чис­ла, символы Т и NIL, строки и др.). Переменные в Лиспе обозначаются сим­волами. При вычислении такой формы возвращается значение символа. Форма, заданная в виде списочной структуры, может представлять: вызов функции, рассмотренный выше, вызовы специальных форм, которые позволяют выполнять действия, недостижимые с по­мощью обычных функций, к примеру, присваивать значения переменным, осуществлять условные вычисления. К таким формам относят: SETQ, QUOTE, IF и др. Макровызовы внешне соответствуют вызову функции, но отличаются по способу вычисления. Они вычисляются в два этапа: снача­ла из аргументов макроса строится форма, а затем она вычисляется. При вычислении s-выражений, представленных в форме констант, переменных или списков, интерпретатор EVAL реализует следующие уп­рощенные правила:

1. если s ─ выражение ─ это константа (самоопределяемая форма), на­пример, число или атомы Т и NIL, то EVAL возвращает такое s-выражение без изменений;

2. если s ─ выражение ─ это переменная, представленная символом, то функция EVAL возвращает последнее значение, которое было связано с этим символом; если символ не имеет значения, что выдается сообщение об ошибке;

3. если s ─ выражение ─ это список, и первый элемент списка ─ символ, то EVAL интерпретирует его либо как имя функции, либо как имя спе­циальной формы, либо как имя макроса. Указанные имена должны быть известны системе. Если первый элемент списка - имя функции, то EVAL интерпретирует оставшиеся элементы списка как ее аргументы, которые подлежат вычислению с помощью EVAL.

 Арифметические функции

В Лиспе имеется встроенные арифметические функции. Аргументы этих функций должны иметь числовые значения. Числа в Лиспе подразделяются на целые, вещественные и рациональные. Рациональные числа представляются в виде дроби, например, 2/3. Комплексное число 6+3i на языке Лисп записывается в форме #С(6 3).

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

 

 

Арифметическая операция	Реализация в среде интерпретатора
сложение 2-х аргументов	> (+2 3) 5
сложение 2-х и более аргументов	> (+3123) 9
унарный +	> (+9) 9
вычитание 2-х и более аргументов	> (-13 12 3) 7
вычитание 2-х и более аргументов	> (--9) 9
умножение 2-х аргументов	> (* 2 1.5) 3.5
умножение 2-х и более аргументов	> (* 2 2 3) 12
деление целочисленных аргументов	> (/7 2 2) 7/4
деление с преобразованием к вещественному значению	> (/7 2 2.0) 1.75
обратное значение	> (/5.0) 0.2
обратное значение	> (/ 2) 1/2
минимум	> (min 2 3 1) 1
максимум	> (max 2 3 1) 3
абсолютное значение	> (abs -5) 5
остаток от деления	> (rem 17 4) 1

Если в арифметических операциях участвуют вещественные аргу­менты, то результаты представляются в вещественной форме.

Для сравнения скалярных чисел в Лиспе используются функции, имена которых задаются знаками отношений (=, | = (не равно), <, >, <=, >=). Эти функции могут иметь произвольное количество аргументов. В этом случае проверяется выполнение соответствующего отношения для всех аргументов. Если отношение выполняется, то функция возвращает в качестве результата значение Т, иначе ─ NIL. К примеру:

> (> 5 4 3 2 1)

                           Т

В Лиспе имеется большой набор иррациональных и трансцендент­ных функций: EXP, EXPT, LOG, SORT, SIN, COS, TAN, ASIN, ACOS, ATAN. Аргументы тригонометрических функций задаются в радианах. Функции TRUNCATE, ROUND, FLOAT выполняют преобразование чисел из одного формата в другой. Функция ROUND выполняет округление числа и также возвращает в качестве результата два значения - ближайшее целое и разность между ис­ходным значением и найденным ближайшим целым. Функция FLOAT преобразует целое число в число с плавающей точ­кой.