Лекция - ЛИСП - язык обработки списков

Подождите немного. Документ загружается.

Sosnitsky Alexander V.,

+ 380634639028

LISP – the Language of List Processing

(ЛИСП – язык обработки списков)

Лекция 1

Введение в дисциплину

Существуют два основных класса машинных языков высокого уровня:

1. Алгоритмические (процедурные, императивные). Они развивают Ассемблеры до

различных высоких уровней и достигли предельного уровня СИ, Джава и т.п.

первым алгоритмическим языком был Фортран – от Formula Translation. Сегодня

все возможности полностью исчерпаны. Дальнейшее развитие невозможно. Они

далее нацелены в сторону ИИ.

2. Декларативные (функциональные). Они основаны на описании задач, а алгоритмы

автоматически генерируются в процессе решения задачи. Фактически они

непосредственно направлены на создание ИИ, но пока не достигли его. В

программе приводятся функции решения задачи, которые последовательно

вызывают друг друга от начала до решения.

Первые такие языки в своих классах есть ФОРТРАН и ЛИСП, возникшие практически

одновременно в 1960-х годах. Но первый реализован до конца, а второй более мощный, но

не хватило уровня понимания его возможностей, почему он полностью не освоен до

настоящего времени и получил слабое распространение. Но все самые сложные

программы созданы именно на ЛИСП, например – Автокад, машинная графика, ИИ и др.

Дальнейшее развитие программирования ожидается через ЛИСП и через 10-15-20 лет

алгоритмические языки полностью заменятся декларативными. Они более сложные, но

более мощные и их надо изучать современным студентам.

ЛИСП разработан в Массачусетском университете в 1960-х годах американским

математиком Дж. Маккарти на основе так называемого λ-исчисления. Список

символически записывается перечислением имен в круглых скобках через пробелы с

предыдущим апострофом, например:

‘(a b c d).

Если нет апострофа:

(a b c d)

то первое имя обозначает функцию остальных имен списка, которые служат аргументами

функции. Значение функции или:

1. явно сохраняется в одном из аргументов, что соответствует классическому

представлению функции, например b = a(c, d);

2. или неявно изменяет свои аргументы или другие объекты программы, что

называется побочным эффектом.

Функциональное представление списка (без апострофа) является более общим и считается

основным. Апостроф также может быть заменен функцией QUOTE, например

(quote (a b c d)). Это эквивалентно ‘(a b c d).

В этом состоит атавизм ЛИСПа, я думаю основным должно описание списков без

апострофа, а функции можно было бы дать другое представление. Однако это есть не

более, чем проблема описания при сильном содержании.

Программа представляется исключительно списками. Часть списков представляет данные,

другая часть – действия. Можно записать, что

программа = данные (списки с апострофом или quote) + действия (без них).

Списки представляются в машинной памяти комбинацией различным образом связанных

между собой списочных элементов с двумя полями следующего вида:

Имеется одна ссылка на значение (поле CAR – произносится «кар») и одна ссылка на

другой элемент (поле CDR – произносится «кудр»).

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

иметь имя, списочный элемент тоже может иметь имя. Все имена ЛИСП-программы

хранятся в специальных встроенных таблицах программы все время выполнения

программы. Они могут не иметь имен, но тогда будут определены только на

ограниченный промежуток выполнения программы, после чего превращаются в мусор, на

который уже никогда нельзя сослаться и он регулярно убирается специальным

мусорщиком.

Из такого списочного элемента могут быть построены все основные структуры данных

ЛИСПа:

Список:

Дерево:

Кольца:

Циклические графы:

…

Следовательно, списками можно построить любой классический ориентированный граф

вида G(V,S), где V – множество вершин графа; S – множество дуг графа. Дополнительно к

этому за каждой вершиной закреплено некоторое значение. При этом связи и значения

вершин могут динамически изменяться в процессе выполнения программы. Поскольку и

данные и действия программы представлены списками с изменяемыми значениями и

структурой, то программа меняет как свои данные, так и себя. В этом состоит

уникальность ЛИСПа.

ЛИСП-программа может иметь динамическую (формат файла .lsp) или фиксированную

(формат файла .exe) структуры. В первом случае она обрабатывается интерпретатором, во

втором случае компилятором. Интерпретатор работает медленнее, но позволяет менять

программу, а компилятор много быстрее, но фиксирует ее. За все надо платить.

Переменные программы есть динамические:

1. атомы - скалярные переменные поля CAR списочных элементов;

2. списки элементов, из которых строится любые графовые структуры.

Действия также описываются списочными структурами и выполняются слева направо в

тексте программы, которая естественно имеет последовательную структуру предложений.

Но предложения могут включать ссылки на любое другое предложение, в том числе на

самих себя, что называется рекурсией. Рекурсия часто используется в ЛИСП-программах

в различных видах.

Все имена в ЛИСП-программе не типизированы. Это означает, что формат представления

данных также расфиксирован и может меняться в процессе выполнения программы, если

не запрещено специально. Интерпретатор или преобразует форматы автоматически в

совместимый вид или выдает ошибку о несовместимости форматов. Имена в ЛИСП-

программе называются символами.

Целью дисциплины есть изучение языка программирования ЛИСП и стиля

программирования на нем.

Задачами дисциплины есть:

1. Изучение теории ЛИСП и СП ЛИСП.

2. Получение навыков программирования элементарных задач на ЛИСП.

3. Приложение ЛИСП для создания простейших ЭС или других интеллектуальных

приложений.

1. Синтаксис

Синтаксис Лиспа очень простой. Программа на Лиспе состоит из S-выражений (от

Symbolic - символьный), которые для краткости далее мы будем называть просто

выражениями. Каждое выражение представляет собой либо атом, либо список. Атом

представляется каким-либо значением данного определенного типа, исключая списки.

Разрешенные типы данных различны в разных диалектах Лиспа. Список является

последовательностью (возможно пустой) элементов списка, заключенной в скобки.

В форме Бэкуса-Наура синтаксис Лиспа определяется следующим образом:

<Лисп-программа> ::= <S-выражение>...

<S-выражение> ::= <атом>|<список>

<список> ::= (<элементы списка>)

<элементы списка> ::= <пусто>

<элементы списка> ::= <S-выражение> [<элементы списка>]

<пусто> ::=

Таким образом, всякое выражение представляет собой набор атомов и списков, например:

(((звери) лев тигр слон) ((рыбы) акула лещ щука) животные)

2. Базовые функции

Лисп основан на функциональном стиле программирования, т.е. программа на Лиспе

является композицией функций. Пусть нужно вычислить функцию f от двух аргументов x

и y, которая в математике записывается f(x,y). В Лиспе эта запись будет выражением (f x

y). Таким образом, вызов функции представляется в виде списка, первый элемент

которого является функцией, а возможные последующие элементы - аргументами этой

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

композицию функций. Например, вычисление выражения (+ 2 (* 3 5)), являющегося

композицией функций сложения и умножения, дает результат 17.

Операция применения функции к аргументу называется аппликацией, поэтому

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

Работа интерпретатора Лиспа заключается в том, что определяется значение каждого

выражения, поступающего в компьютер. Мы будем пользоваться символом стрелки

вправо -> для указания значения выражения. Например, для предыдущего выражения

имеем

(+ 2 (* 3 5)) -> 17

Одной из важнейших особенностей Лиспа, позволяющих осуществлять

метапрограммирование, является возможность доступа как к символьной форме

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

ставится апостроф, например:

'(+ 2 3) -> (+ 2 3)

(+ 2 3) -> 5

Апостроф запрещает вычисление следующего за ним выражения, которое

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

Для присваивания значений переменной используется встроенная функция SETQ,

первый аргумент которой - атомарное имя переменной, а второй - присваиваемое

значение. Например, выражение

(setq ABC 1) -> 1

вычисляет значение второго аргумента и в качестве побочного эффекта присваивает

переменной ABC это значение.

Все имена переменных в Лиспе называются символами и записываются в виде

атомарной последовательности алфавитно-цифровых литер. При присваивании

переменной значения говорят, что значение связывается с символом переменной, и этот

символ становится связанным. Так в предыдущем примере с символом ABC связано

значение 1.

Множество всех связанных символов и их значений, доступных в данной точке

программы, называется обстановкой (средой) связывания, а также контекстом.

Две фундаментальные встроенные функции car и cdr позволяют обрабатывать списки.

Функция CAR определяет первый элемент своего списочного аргумента, например:

(car '(A B C)) -> A

(car '((A) B)) -> (A)

(car 'A) -> ошибка, т.к. A не есть список

(car ()) -> NIL

Встроенный символ NIL обозначает пустой список. Значение NIL используется также в

качестве логически ложного значения, а в качестве значения логической истины

используется символ T.

Функция CDR определяет остаток своего списочного аргумента после исключения его

первого элемента, например:

(cdr '(A B C)) -> (B C)

Иногда первый элемент списка называют его "головой", а его остаток - "хвостом".

Таким образом, функции car и cdr определяют соответственно голову и хвост списка.

Действие встроенной функции cons противоположно действию функций car и cdr.

Функция CONS составляет список из головы, являющейся первым аргументом, и хвоста,

являющегося вторым аргументом, например:

(cons 'A '(B C)) -> (A B C)

В общем случае для любого списка L имеем равенство

(cons(car L) (cdr L)) = L.

Вложенные вызовы CAR и CDR: (C..R список), нпример:

(cadr x) эквивалентно (car (cdr(x))

(cddar x) эквивалентно (cdr(cdr(car x)))

FIRST, SECOND, THIRD, FOURTH … вызов соответствующих элементов списка.

(NTH n список) – вызов н-го элемента списка

(LAST список) – вызов последнего элемента списка

(LIST x1 x2 x3 …) – создание списка из элементов. Элементы могут быть другими

списками – так создаются вложенные списки (деревья). Получаемый список

присваивается выражению, но без имени и тряется. Чтобы его сохранить его надо

записать (setq a list(x1 x2 x3 …)), в этогм случае и выражение и символ а получат значение

(ссылку) на список и после завершения выражения имя а сохранит адрес списка и им

можно будет пользоваться.

3. Базовые предикаты

Предикат есть функция, возвращающая значения T (истина – любое значение, отличное от

NIL) или NIL (0-ложь). Они возникают при сравнении объектов.

(АТОМ s-выражение) – проверяет выражение, есть ли оно атом. Примеры:

>(atom 'x)

>(atom(cdr '(a b c)))

NIL

LISTP – проверка на список

ARRAYP – провенка на массив

EQ – сравнивает два символа: (EQ ‘a ’b) -> NIL; (EQ ' a (car '(a b))) -> T

EQL – сравнивает числа одинакового типа

EQUAL – сравнивает любые два списка

NULL – проверяет на пустой список

4. Машинное представление и оценивание выражений

Для интерпретатора программ на языке Лисп ячейки памяти компьютера объединены

попарно. Эти ячейки содержат адреса указателей на другие ячейки. Условимся адреса

указателей изображать стрелками на рисунках. На рис. 1.1 показано некоторое выражение

и его физическая реализация.

Адрес

410------------¬

----+-817 ¦ 906-+¬

------------¬ ------------¬ ¦ +-----------+¦

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦¦

------------- ------------- ¦817+-----------+¦

--->¦ ¦ ¦¦

------------¬ +-----------+¦

¦ ¦ ¦ ¦ ¦¦

------------- 906+-----------+¦

-->¦ ¦ ¦¦

¦ -------------¦

-----------------

а) б)

Рис. 1.1. Машинное представление выражения: а - графическое изображение

представления, б - пример его физической реализации.

Команда (setq L1 '(A B)) создает структуру, показанную на рис. 1.2. При этом будем

использовать следующие соглашения: отсутствие указателя обозначается символом 0;

атомы обрабатываются отдельно (для указания на них используются специальные

метки). Как видно из этого рисунка, car некоторого списка есть то, на что указывает

указатель его левой ячейки, и cdr некоторого списка есть то, на что указывает указатель

его правой ячейки.

------------¬ ------------¬

L1-->¦ * ¦ *--+>¦ * ¦ 0 ¦

L--+--------- L--+---------

V V

A B

Рис. 1.2. Машинное представление результата команды (setq L1 '(A B)).

Чтобы распознать выражение по его машинному представлению, нужно просмотреть это

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

глубину (просмотр в глубину) и затем - по указателям, расположенным в правых ячейках

(просмотр в ширину). Каждой стрелке от левой ячейки, не заканчивающейся на атоме,

при записи выражения в исходном тексте соответствует открывающая скобка, а

каждому пустому указателю 0 - закрывающая скобка. Таким образом, приведенное на

рис. 1.3 представление соответствует списку L2 имеющему значение ((A) (B)).

Кроме того, интерпретатор постоянно ведет список свободных ячеек, предназначенных

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

обозначена символом d. Так, например, выполнение команды (setq L3 (cons 'C L2))

вызывает перемещение (рис. 1.5) указателя d от предыдущей заданной отметки и

создание символа C, если он еще не существует. Представление символа L3 после

выполнения этой команды приведено на рис. 1.6.

L2-----¬

1(V

------------¬ ------------¬

¦ * ¦ *---->¦ * ¦ 0 ¦)1

---+--------- ---+---------

2(V 3(V

------------¬ ------------¬

¦ * ¦ 0 ¦)2¦ * ¦ 0 ¦)3

---+--------- ---+---------

V V

A B

Рис. 1.3. Машинное представление символа L2 со значением ((A) (B)). Цифрами

обозначены номера пар скобок.

------------¬ ------------¬ ------------¬ ------------¬

d->¦ ¦ *--+>¦ ¦ *--+>¦ ¦ *--+- - >¦ ¦ 0 ¦

------------- ------------- ------------- -------------

Рис. 1.4. Список свободных ячеек. Пунктиром обозначены другие свободные ячейки.

------------¬ ------------¬ ------------¬

d'->¦ ¦ *--+>¦ ¦ *--+- - >¦ ¦ 0 ¦

L------------ L------------ L------------

Рис. 1.5. Измененный список свободных ячеек (рис. 1.4) после создания новых структур

в оперативной памяти.

5. Имя и значение символа

Значением константы в тексте программы есть сама константа.

Значением имени атома в тексте программы есть содержимое поля CAR списочного

элемента этого атома.

Значением имени списка есть адрес этого списка.

Адреса имен атома и списка выбираются из внутренних скрытых таблиц программы по

этим именам. Если появляется новое имя, то оно сразу же заносится в эти таблицы. Если

идет дальнейшее упоминание имен, то их адреса выбираются из таблиц.

(SET имя s-выражение) – 1) вычисляет имя и выражение и 2) связывает выражение с

именем, например: (set ‘a ‘(b c d e f)) – имя а связывается с явно заданным списком, они не

вычисляются.

(SETQ имя s-выражение) – 1) то же, что и set, но 2) не вычисляет имя, например: (setq a

‘(b c d e f)).

Каждое s-выражение (список данных, предложение программы) получает значение через

ссылку на соответствующий списочный элемент, закрепленный за выражением.

Если выражение запрещено для вычисления, то это адрес аргументов.

Если разрешено, то это адрес результата.

Если он получил имя, то доступ к нему через таблицу имен.

Если вы разрешите выполнить отложенное вычисление, то вместо адреса аргументов

выражение получает адрес результата.

Продолжается вычисление функцией EVAL , например:

>(quote (+ 2 3))

(+ 2 3)

(eval(quote (+ 2 3)))

Фактически eval есть вызов интерпретатора ЛИСП в заданную точку входа текста

программы.

В этих примерах строки не имеют имен. Поэтому они становятся неизвестными вне

главного предложения, их содержащего. Для использования в других предложениях им

следует присвоить имена, по которым они помещаются во внутренние таблицы.

6. Определение функций

Лямбда-выражение есть предок функций ЛИСП. Оно имеет формат:

(LAMBDA (x1 x2 x3 …) (s-выражение)),

например (lambda (x y) (+(* x y)(* y y))). В чистом виде оно не имеет значения и имени.

Лямбда-вызов формируется из лямбда-выражения по формату:

(LAMBDA (x1 x2 x3 …) (s-выражение) p1 p2 p3…),

где (x1 x2 x3 …) – список формальных параметров, p1 p2 p3… - список фактических

параметров. Например (lambda (x y) (+(* x y)(* y y)) 2 3). В таком случае получается

значение = 13, которое присваивается выражению. Имя для множественного

использования выражения как функции получается разными способами, например

функцией set.

Основным способом задания имени s-выражению есть функция DEFUN:

(DEFUN имя лямбда-выражение), например (defun f1(x y)(+ (* x x) (*y y))), вызов – (f1 2 3)

и получим тот же ответ 13. После этого эту функцию мы можем вызывать произвольное

число раз.

Формальные параметры могут следовать за ключевыми словами:

&OPTIONAL – необязательные параметры (можно не указывать при вызове)

&REST – переменное количество параметров

&KEY – ключевые параметры

&AUX – вспомогательные переменные