Особенности языка ЛИСП

Основные данные о работе

Версия шаблона	2.1
Филиал	Астраханский
Вид работы	Курсовая работа
Название дисциплины	Информационные технологии
Тема	Особенности языка ЛИСП
Фамилия студента	Селиванов
Имя студента	Алексей
Отчество студента	Михайлович
№ контракта	04500110601002

 

Содержание

Введение  3

1. Язык программирования ЛИСП 5

1.1 Основные функции языка Лисп 5

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

1.3 Логические функции   7

1.4 Специальные функции 9

2. Особенности диалектов языка ЛИСП 12

2.1. MacLISP 12

2.2. MuLISP  13

2.3. InterLISP 14

2.4 CommonLISP 16

3. Особенности языка ЛИСП   20

Заключение  24

Глоссарий 26

Список использованных источников…… 28

Приложения…..…………………………………………………………….29

Введение

LISP (от англ. LISt Processing — «обработка списков») — семейство языков программирования, основанных на представлении программы системой линейных списков символов, которые притом являются основной структурой данных языка. Лисп считается вторым после Фортрана старейшим высокоуровневым языком программирования.

 В 1950-х годах специалисты по искусственному интеллекту начали поиски языка программирования, который бы позволял манипулировать понятиями, выраженными словами и фразами на естественном языке. Первый результат был получен в виде семейства языков под названием ИПЛ (IPL, от Information Processing Languages — языки обработки информации), созданного одним из пионеров в области искусственного интеллекта Алленом Ньюэллом и его сотрудниками. Центральным для ИПЛ являлось понятие списка. Представляя данные в виде списка слов и символов, программист мог связать понятия в памяти компьютера приблизительно таким же образом, как, по мнению специалистов по искусственному интеллекту, они связываются в памяти человека.

Понятием списка заинтересовался  и Джон Маккарти [8], разносторонний математик, один из ведущих исследователей в области искусственного интеллекта (причем сам термин искусственный интеллект был предложен именно им в 1956 году). Язык Лисп был предложен Джоном Маккарти в работе в 1960 году и ориентирован на разработку программ для решения задач не численного характера. Английское название этого языка – LISP является аббревиатурой выражения LISt Processing (обработка списков) и хорошо подчеркивает основную область его применения. Понятие “список” оказалось очень емким. В виде списков удобно представлять алгебраические выражения, графы, элементы конечных групп, множества, правила вывода и многие другие сложные объекты.

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

После появления LISP различными авторами был предложен целый ряд других алгоритмических языков ориентированных на решение задач в области искусственного интеллекта. Однако это не помешало LISP остаться наиболее популярным языком для решения таких задач. На протяжении почти сорокалетней истории его существования появился ряд диалектов этого языка: Common LISP, Mac LISP, InterLISP, Standard LISP и др. [3] Различия между ними не носят принципиального характера и в основном сводятся к несколько отличающемуся набору встроенных функций и некоторой разнице в форме записи программ. Поэтому, программист, научившийся работать на одном из них, без труда сможет освоить и любой другой.

Большим достоинством LISP является его функциональная направленность, т. е. программирование ведется с помощью функций. Причем функция понимается как правило, сопоставляющее элементам некоторого класса соответствующие элементы другого класса. Сам процесс сопоставления не оказывает никакого влияния на работу программы, важен только его результат – значение функции. Это позволяет относительно легко писать и отлаживать большие программные комплексы. Ясность программ, четкое разграничение их функций, отсутствие каверзных побочных эффектов при их выполнении является обязательными требованиями к программированию таких логически сложных задач, каковыми являются задачи искусственного интеллекта. Дисциплина в программировании становится особенно важной, когда над программой работает не один человек, а целая группа программистов. [1]

Цель курсовой работы – изучение особенностей языка LISP. Для достижения цели курсовой работы в ней будут рассмотрены основные функции данного языка программирования и отличительные особенности некоторых его диалектов. 

Для достижения цели курсовой работы были поставлены и решены следующие  задачи:

- подробный анализ основных  функций языка программирования  LISP;

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

Основная часть

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

 

1.1 Основные  функции языка Лисп

 

К числу основных особенностей языка  Лисп относится то, что программой является несколько определенных пользователем  функций (Приложение А). С точки зрения синтаксиса Лисп-функция, как и обрабатываемые ею данные, представляет собой так называемое S-выражение. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном - список, т.е. последовательность элементов, разделенных обычно пробелом и заключенных в круглые скобки [4].

Списки  языка Лисп имеют рекурсивную структуру: элементом списка может быть произвольное S-выражение - как атом, так и список, например: (1() (a b (c)) class). Некоторые S-выражения можно вычислять, получая в результате значения (тоже S-выражения); такие выражения называются формами.

Формой  может быть переменная, т.е. атом-идентификатор, которому было присвоено значение одной  из функций Лиспа (значением такой формы является текущее значение переменной). Формой является также список-обращение к функции вида(f a₁, a₂ ... a_n), где f - имя функции, а a_i - ее аргументы (n≥0). Программа на Лиспе представляет собой последовательность таких форм, и ее выполнение заключается в их вычислении.

  В большинстве версий языка Лисп имеется много встроенных (стандартных) функций, на основе которых составляется программа. Все они есть в наиболее известных версиях Лиспа, таких как Common Lisp и MuLisp [5].

Для определения новых функций используется встроенная функция defun, к которой возможны следующие (равноценные) обращения: (defun f (lambda (v1 v2 ... vn) e)) или (defun f (v1 v2 ... vn) e).

Вычисление  функции defun в качестве побочного  эффекта приводит к появлению  в программе новой функции  с именем f ; v_i - формальные параметры новой функции (n≥0), а e - форма, зависящая от v_i. Таким образом, определяется обычная ЛИСП-функция, т.е. функция с фиксированным количеством аргументов, которые всегда вычисляются при обращении к ней.

При последующем обращении к этой уже определенной функции (f a₁ a₂ ... a_n) сначала вычисляются аргументы (фактические параметры) ai, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных vi, после чего эти переменные уничтожаются. Значением данной формы становится значение функции f при аргументах a_i.

Операции  над списками (car l) – значением аргумента l должен быть непустой список, тогда значением функции является первый элемент (верхнего уровня) этого списка (cdr l) и значением функции является "хвост" этого списка, т.е. список, полученный отбрасыванием первого элемента [6].

Кроме этих двух функций-селекторов элементов  списка часто используются функции, являющиеся их суперпозициями. Имена всех таких функций начинаются на букву c, а заканчиваются на букву r, между ними же может стоять произвольная комбинация из не более чем 5 букв a и d, например, (cadar l)≡(car(cdr(car l))) .

Предполагается, что список-аргумент l всех этих функций, так же как и следующей функции nth, содержит необходимое число элементов (в противном случае вычисления прерываются).

(nth n l) – значением аргумента n должно быть положительное целое число (обозначим его N), а значением аргумента l - список. Значением функции является N-й от начала элемент этого списка.

(last l) – функция выбирает последний (от начала) элемент списка, являющегося значением ее аргумента.

(cons e l) – в отличие от предыдущих функций эта функция является конструктором, т.е. строит новый список, который и выдает в качестве своего результата. Первым элементом этого списка будет значение аргумента e, а хвостом списка - значение аргумента l . Например, (append l1 l2)

Эта функция осуществляет слияние (конкатенацию) двух списков, являющихся значением  двух ее аргументов.

(list e1 e2 ... en ) – еще одна функция конструктор, она имеет произвольное количество аргументов, из их значений она строит список (количество элементов результирующего списка равно количеству аргументов).

 

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

 

(add1 n) – значением аргумента этой функции должно быть число, функция прибавляет к этому числу 1 и выдает результат в качестве своего значения.

(sub1 n) – значением аргумента должно быть число, функция вычитает из него 1 и выдает результат в качестве своего значения.

(+ n1 n2) – значениями обоих аргументов функции должны быть числа, результат вычисления функции - их сумма.

(- n1 n2) – значениями аргументов должны быть числа, значение функции - их разность.

(length l) – значением аргумента l должен быть список, значением функции является количество элементов (верхнего уровня) этого списка, например:

(mod n1 n2) –  значениями обоих аргументов функции должны быть целые числа. Функция выполняет деление нацело первого числа на второе, и результат выдает в качестве своего значения.

(rem n1 n2) – значениями аргументов функции должны быть целые числа, результат вычисления функции - остаток от деления первого числа на второе.

 

 

 

1.3 Логические функции

 

Предикатом  обычно называется форма, значение которой  рассматривается как логическое значение "истина" или "ложь". Особенностью языка Лисп является то, что "ложью" считается пустой список, записываемый как () или nil, а "истиной" - любое другое выражение (часто в этой роли выступает атом T) [5].

(null e) – эта функция проверяет, является ли значение ее аргумента пустым списком: если да, то значение функции равно T, иначе - ().

(eq e1 e2) – функция сравнивает значения своих аргументов, которые должны быть атомами-идентификаторами. В случае их совпадения (идентичности) значение функции равно T, иначе - ().

(eql e1 e2) – в отличие от предыдущей функции eql сравнивает значения своих аргументов, которыми могут быть не только атомы-идентификаторы, но и атомы-числа. Если они равны, то значение функции равно T, иначе - ().

(equal e1 e2) – пункция производит сравнение двух произвольных S-выражений - значений своих аргументов. Если они равны (имеют одинаковую структуру и состоят из одинаковых атомов), то значение функции равно T, иначе - ().

(neq e1 e2) – аналог, но значения аргументов сравниваются на "не равно".

Функция (member a l) производит поиск атома, являющегося значением первого ее аргумента, в списке (на верхнем его уровне), являющемся вторым аргументом. В случае успеха поиска значение функции равно T, иначе - ().

Значениями аргументов функции (gt n1 n2) или (> n1 n2) должны быть числа. Если первое из них больше второго, то значение функции равно T, иначе - ().

(lt n1 n2) или (< n1 n2) – аналог, но числа сравниваются на "меньше".

Логическими функциями называются три функции, реализующие основные логические операции [7].

Функция (not e), реализующая "отрицание", является дубликатом функции null: если значение аргумента равно () ("ложь"), то функция выдает результат T ("истина"), а при любом другом значении аргумента выдает результат ().

(and e1 e2 ... ek) (k≥1) – конъюнкция. Функция по очереди вычисляет свои аргументы. Если значение очередного из них равно () ("ложь"), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением (), а иначе переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

(or e1 e2 ... ek) (k≥1) – дизъюнкция. Функция по очереди вычисляет свои аргументы. Если значение очередного из них не равно () ("ложь"), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением этого аргумента, в противном случае она переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

К числу логических функций можно  отнести и условное выражение: [cond (p1 e1,1 e1,2 ... e1,k1) ... (pn en,1 en,2 ... en,kn)] (n≥1, ki≥1)

Функция cond последовательно вычисляет  первые элементы своих аргументов – обращения к предикатам p_i. Если все они имеют значение () ("ложь"), тогда функция заканчивает свою работу с этим же значением. Но если был обнаружен предикат p_i, значение которого отлично от (), т.е. он имеет значение "истина", тогда функция cond уже не будет рассматривать остальные предикаты, а последовательно вычислит формы e_i,j из этого i-го аргумента и со значением последнего из них закончит свою работу. Следует отметить, что поскольку значения предыдущих форм из этого аргумента нигде не запоминаются, то в качестве этих форм имеет смысл использовать только такие, у которых есть побочный эффект, например, обращение к функции присвоения значения [2].

 

1.4 Специальные  функции

 

Функция блокировки вычислений (quote e) или 'e, выдает в качестве значения свой аргумент, не вычисляя его.

Функция (gensym) генерации уникальных атомов, при каждом обращении к ней вычисляет (образует) новый атом-идентификатор. Этот идентификатор получается склеиванием специального префикса и очередного целого числа. Префикс и целое число, от которого начинается нумерация генерируемых атомов, могут быть установлены заранее, как например, в языке MuLisp: (setq *gensym-prefix* 'S) (setq *gensym-count* 2) [10].