Материалы (8) (Материалы к лекциям)

Язык ЛиспЯзык Лисп – один из старейших языковпрограммирования и первый функциональныйязык, получивший широкое распространение. Ядроязыка было создано в 60-х годах прошлого векаизвестным ученым Дж. Маккарти для решениязадач обработки символьной информации .Основная структура данных языка Лисп – список,отсюда и название языка: Lisp – List Processing.Атомы и списки, функцииОбрабатываемые в языке Лисп данные можноразделить на скалярные (простые) и структурные(составные). К скалярным данным относятся атомы(атом – неделимое целое), а к структурным – списки,или списочные структуры.

В свою очередь атомыподразделяются на:-- символьные, т.е. идентификаторы (например: BETA, A , SYM_1);-- числовые, т.е. целые и вещественные числа ( -25,375.08 и др.).Атомы и списки, функцииСреди множества атомов базового Лиспаконстантами являются:-- все числовые атомы;-- символьные атомы T и NIL, обозначающиесоответственно логические значения истина иложь; а атом NIL также обозначает пустой списокАтомы и списки, функцииКлючевым понятием языка Лисп является список –рекурсивная структура, которая может бытьописана следующими БНФ (металингвистическимиформулами Бэкуса-Наура):список ::= ( последовательность_элементов ) |пустой списокпоследовательность_элементов ::= элемент |элемент └─┘ последовательность_элементовэлемент ::= атом | списокпустой список ::= () | NILАтомы и списки, функцииПримеры списков языка Лисп:(BETA 56 (9))((С ()) NIL 81 (ЕE В С))()((((Т))))Атомы и списки, функцииГлубиной списка считается максимальноеколичество вложенных пар скобок.

Так, на верхнемуровне списка (BETA 56 (9)) находятся триэлемента: символьный атом BETA, число 56 ивложенный список (9), а глубина этого спискаравна 2. Единственной константой составного типаявляется пустой список (), который может бытьзаписан и как атом NIL, обе эти записиэквивалентны.Атомы и списки, функцииЛисп-программа представляет собойпоследовательность форм, а форма, иливычислимое выражение – это атом или список,который можно вычислить и получить значение.Вычисление программы реализует лиспинтерпретатор, который считывает очереднуювходящую в программу форму, вычисляет её ивыводит полученный результат (атом или список).Атомы и списки, функцииВычислимые атомы и списки:для чисел:72 => 72для символьных атомов: t => T() => NILNIL => NILСимвольный атом вычислим только тогда, когда онпредставляет собой имя формального параметра(аргумента) некоторой функции, и этот параметримеет значение, например:x => (B C D).Атомы и списки, функцииСписок можно вычислить, если он представляетсобой обращение к функции, или функциональныйвызов: (f e1 e2 … en),где f – символьный атом, обозначающий имявызываемой функции,а e1, e2, …, en –аргументы этой функции, n0.n - число аргументов функции.В случае n=0 имеем вызов функции безаргументов: (f).

Обычно e1, e2, …, en являютсявычислимыми выражениями и вычисляютсяпоследовательно слева направо.Атомы и списки, функцииФункции Лиспа обычно делятся на:-- встроенные, или стандартные, которые могутприменяться без определения;-- определяемые пользователем в его программе.Другое важное в Лиспе деление функций на классыучитывает количество и вычислимость аргументовфункции. Различают:обычные функции (их большинство);особые, или специальные функции.Атомы и списки, функцииОбычная функция имеет строго фиксированное числоаргументов, и при вычислении её значения интерпретаторсначала вычисляет значения её аргументов слева направо,а уже затем функция применяется к вычисленнымзначениям.У особой функции нарушается хотя бы одно из двухуказанных требований, т.е.

у неё может бытьпроизвольное количество аргументов и/или некоторые еёаргументы могут не вычисляться.Базовый набор функцийФункция car от одного аргумента возвращает первыйэлемент списка, являющегося значением её аргумента.Функция cdr возвращает хвост списка, являющегосязначением её единственного аргумента (хвостом, илиостатком списка является список без своего первогоэлемента). Contents of Adress Register и Contents of Decrement Register.Функция cons от двух аргументов (cons e1 e2) строит новыйсписок, первым элементом которого является значениепервого аргумента е1, а хвостом – значение второгоаргумента е2. По сути, эта функция включает заданныйэлемент (значение выражения е1) в начало списка,являющегося значением е2.Базовый набор функцийПусть переменная x имеет значение (GAMMA (15)), апеременная y имеет значение (TETA):x => (GAMMA (15))y => (TETA)Тогда(car x) => GAMMA(cdr x) => ((15))(cdr y) => NIL(car (cdr x)) => (15)(car(car(cdr x))) => 15(cons x y) => ((GAMMA (15)) TETA)(cons y ()) => ((TETA))Базовый набор функцийФункция atom вырабатывает значение T, если значениемеё единственного аргумента является атом (числовой илисимвольный).

В противном случае возвращается NIL.Функция-предикат eq (сокращение от англ. equal)проверяет совпадение двух своих аргументов-атомов,вырабатывая значение T, когда:1) значением одного из аргументов является атом, иодновременно2) значения аргументов равны (идентичны).В ином случае значением функции eq является NIL. Будемсчитать, что когда оба аргумента функции eq – списки, еёрезультат неопределён. Для чисел есть отдельная ф-я.Базовый набор функцийx => (GAMMA (15))(atom NIL) => T(atom T) => T(atom x) => NIL(atom ()) => T(atom (cdr (cdr x))) => T(eq (atom 5) T) => T(eq (car x)(cdr x)) => NILБазовый набор функцийОсобая функция quote, которая в качестве своегозначения выдаёт сам аргумент, не вычисляя его:(quote e) => e(cons 5 (quote(А Т)) ) => (5 А Т)(quote (ATOM B)) => (ATOM B)'(ATOM B) => (ATOM B) -- другое обозначение quote(cons (quote(A (B))) NIL) => ((A (B)))(cons '(A (B)) NIL) => ((A (B)))(atom '(NIL)) => NILБазовый набор функцийФункция базового набора eval выполняет двойноевычисление своего аргумента.

Эта функция являетсяобычной, и первое вычисление аргумента выполняет также, как и любая обычная функция. Полученное при этомвыражение вычисляется ещё раз.(eval (quote (atom b))) => T(eval (quote (quote quote))) => QUOTE(eval '(car '(a b c))) => A(eval (cons (quote car) (quote (x)))) => GAMMA└──────────(car x)───────┘Базовый набор функцийФункция базового набора cond (сокращение от англ.condition – условие) служит средством разветвлениявычислений.

В строго функциональномпрограммировании вызов этой функции, как правило,имеет вид(cond (p1 e1) (p2 e2) … (pn en)) , n1.Обращение к функции cond называется условнымвыражением, выражения (pi ei) – ветвями условноговыражения, а выражения-формы pi – условиями ветвей.Функция cond является особой, поскольку в условномвыражении может быть произвольное количество ветвей,и не все формы ei вычисляются в общем случае.Базовый набор функций(cond ((eq 'A T) 'are_equal)(Т 'not_equal))=>NOT_EQUAL(cond ((eq 'A1 'A2) 'are_equal)('not_equal))=>NOT_EQUALЗдесь выражение e2 опущено, его роль играет p2Базовый набор функцийПример.

Сложение по модулю 2:(cond (x (cond (y NIL)(T))(y))Эта форму можно упростить так:(cond (x (eq y NIL)) (y))(cond (NIL (eq NIL NIL)) (NIL)) => NIL.Базовый набор функцийПример. AND и OR(cond (x y))(cond (x) (y))Определение функцийлямбда-выражениелямбда-выражение ::= (lambda лямбда-списоктело_функции)Лямбда-список представляет собой лисповский список изсимвольных атомов, рассматриваемых как именаформальных параметров функции.

В частном случае этотсписок может быть пустым, что соответствует функции безаргументов.Телом функции является некоторое лисповскоевыражение (форма), в которое в общем случае входятзаданные в лямбда-списке формальные параметры. Телофункции служит для вычисления её значения.Определение функцийПриведём пример лямбда-выражения с двумяпараметрами x и y:(lambda (x y) (cond (x) (y)))и лямбда-выражения с одним параметром x:(lambda (x) (cond (x) (y)))Отличие этих выражений в том, что в последнемслучае переменная y не внесена в числопараметров функции.Определение функцийПример безымянной функции, вычисляющейдизъюнкцию двух своих аргументов (прирасширенном понимании истинного значения):(lambda (x y) (cond (x) (y)))Лямбда-вызов является формой следующейструктуры:((lambda (x1 x2 … xk) e) p1 p2 … pk)где k0 ,p1, p2 … pk – произвольные выражения-формы(фактические параметры),x1, x2 … xk – символьные атомы (формальныепараметры).Определение функцийПример((lambda(x y)(cond (x) (y))) 'A 3) => AОпределение функций((lambda (x1 x2 … xk) e) p1 p2 … pk)этапы вычисления этой формы при k1:Вычисление аргументов: последовательновычисляются фактические параметры p1, p2, … pkлямбда-вызова, пусть их значения – v1, v2, …, vk .Связывание формальных параметров:формальные параметры x1, x2, … xk попарносвязываются (на время вычисления лямбдавызова) соответственно со значениями v1, v2, …,vk фактических параметров лямбда-вызова:x1=v1, x2=v2, …, xk=vk .Определение функцийВычисление тела: вычисляется форма e (телофункции), причём всюду, где необходимовычислить xi, в качестве его значения берется vi.Вычисленное таким образом значение формы eслужит итоговым значением лямбда-вызова.Определение функцийВычисление тела: вычисляется форма e (телофункции), причём всюду, где необходимовычислить xi, в качестве его значения берется vi.Вычисленное таким образом значение формы eслужит итоговым значением лямбда-вызова.В частном случае k=0 вычисление лямбдавызова без аргументов: ((lambda () e))сводится к вычислению формы e и выдачеполученного результата в качестве значенияэтого лямбда-вызова.Определение функцийДля неоднократного применения функции (атакже для построения рекурсивной функции)требуется средство её именования – для этогослужит особая встроенная функция defun,обращение к которой обычно имеет вид:(defun имя_функции лямбда-списоктело_функции )В качестве имени функции выступаетсимвольный атом.