Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1156449), страница 3

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

Текст из файла (страница 3)

quote– цитировать, взять в кавычки). Необходимость в этом нередко возникаетпри использовании обычных встроенных функций (т.е. вычисляющихзначения своих аргументов), чтобы задать аргументы в явном виде иизбежать их вычисления, например:(cons 5 (quote(А Т)) ) => (5 А Т).Если убрать в этом примере обращение к quote, то второй аргументфункции cons будет рассматриваться как обращение к функции сименем А, и в случае, когда функция с таким именем не определена, лиспинтерпретатор выдаст сообщение об ошибке.Отметим, что константы – числа и атомы T, NIL при ихиспользовании в качестве аргументов обычных функций можно неквотировать, поскольку значением любой константы является она сама.Функция quote используется часто, поэтому допускаетсяупрощённый способ обращения к ней с помощью апострофа,маркирующего квотируемое выражение:10(quote (ATOM B)) => (ATOM B)'(ATOM B) => (ATOM B)(cons (quote(A (B))) NIL) => ((A (B)))(cons '(A (B)) NIL) => ((A (B)))(atom '(NIL)) => NILСледующая функция базового набора eval выполняет двойноевычисление своего аргумента.

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

condition – условие) служит средствомразветвления вычислений. В строго функциональном программированиивызов этой функции, как правило, имеет вид(cond (p1 e1) (p2 e2) … (pn en)) , n≥1.Обращение к функции cond называется условным выражением,выражения (pi ei) – ветвями условного выражения, а выраженияформы pi – условиями ветвей.Функция cond является особой, поскольку в условном выраженииможет быть произвольное количество ветвей, и не все формы ei11вычисляются в общем случае. Вычисление условного выражениявыполняется по следующим правилам:I. последовательно вычисляются условия ветвей до тех пор, пока невстретится выражение-форма pi, значение которой отлично от NIL;II.

вычисляется выражение ei соответствующей ветви и его значениевозвращается в качестве значения функции cond;III. если все условия pi имеют значение NIL, то значением условноговыражения становится NIL.Часто в качестве условия последней ветви pn берут атом Т,обозначающий логическое значение истина – тогда значение enстановится значением условного выражения в случае, когда все значенияпредыдущих условий оказались равны NIL. Например:(cond ((eq 'A T) 'are_equal)(Т 'not_equal))=>NOT_EQUALЗаметим, что в таких случаях вместо атома Т может использоваться любоевыражение, значение которого не равно NIL. По сути, работа функцииcond опирается на расширенное понимание логического значения истина:истинным значением считается не только T, но и любое лисповскоевыражение, отличное от NIL.В обращении к функции cond могут быть опущены некоторыевыражения-формы ei – в этом случае их роль выполняет соответствующееpi, и если результат вычисления pi будет отличен от NIL, то этотрезультат и будет возвращён в качестве значения всего условноговыражения.

Например:(cond ((eq 'A1 'A2) 'are_equal)('not_equal))=> NOT_EQUALЗаметим, что каждую ветвь условного выражения принятозаписывать на отдельной строке, при этом часто используются пробельныеотступы, показывающие вложенность функциональных вызовов.Приведём пример вложенных условных выражений: записаннаяниже форма с двумя переменными x и y вычисляет логическое значение –результат применения к значениям переменных операции исключающегоили (сложение по модулю 2):(cond (x (cond (y NIL)(T))(y))Эта форму можно упростить так:(cond (x (eq y NIL)) (y)) .12Задавая всевозможные комбинации логических значений T и NILдля переменных x и y (всего таких комбинаций – 4, NIL обозначаетлогическое значение ложь), получаем логические значения, например, длякомбинации x=NIL и y= T:(cond (NIL (eq T NIL))(T)) => T .Следующие два выражения-формы с двумя переменными x и yвыражают соответственно логические конъюнкцию и дизъюнкцию:(cond (x y))(cond (x) (y))Эти условные выражения вычислимы не только при логических значенияхпеременных.

В качестве значений x и y могут быть взяты любыелисповские выражения, к примеру, x=(Н7(12)) и y=(Т), и при этоммогут получиться значения, отличные от атомов T и NIL. По сути, эти двавыражения реализуют конъюнкцию и дизъюнкцию при расширенномпонимании логического значения истина. Аналогичная ситуация имеетместо и для формы, реализующей операцию сложения по модулю 2.Такая трактовка логических значений, при которой истиннымсчитается любое выражение (атом, список), отличное от NIL, являетсяособенностью языка Лисп. Она позволяет считать произвольноелисповское выражение логическим, а любую лисповскую функцию –предикатом.Рассмотренные примеры показывают гибкость и мощность функцииcond, с помощью которой можно выразить все известные логическиеоперации.

Описанный набор из 8 встроенных лисповских функций вкупесо средствами определения новых функций является алгоритмическиполным, т.е. позволяет записать любой алгоритм обработки списочныхструктур. Однако этот набор явно недостаточен для практическогопрограммирования.1.3. Определение функцийДля определения новой функции необходимо задать выражение длявычисления её значения и указать, какие переменные этого выражениябудут служить формальными параметрами функции. Кроме того, следуетопределить, в каком порядке должны рассматриваться формальныепараметры при передаче им фактических значений. Для этих целей вбазовом Лиспе используется конструкция, называемая лямбдавыражением или определяющим выражением функции (термин лямбдавыражение был заимствован из лямбда-исчисления – специальногоформализма для описания вычислимых функций).

БНФ этой конструкции:лямбда-выражение ::= (lambda лямбда-список тело_функции)13Лямбда-список представляет собой лисповский список изсимвольных атомов, рассматриваемых как имена формальных параметровфункции. В частном случае этот список может быть пустым, чтосоответствует функции без аргументов.Телом функции является некоторое лисповское выражение (форма), вкоторое в общем случае входят заданные в лямбда-списке формальныепараметры. Тело функции служит для вычисления её значения.Приведём пример лямбда-выражения с двумя параметрами x и y:(lambda (x y) (cond (x) (y)))и лямбда-выражения с одним параметром x:(lambda (x) (cond (x) (y)))Отличие этих выражений в том, что в последнем случае переменная y невнесена в число параметров функции.По сути, лямбда-выражение – это средство параметризациивычисляемого выражения.

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

Вычисленное таким образом значение формы e служит итоговымзначением лямбда-вызова.Важно, что формальные параметры функции локализованы в её теле и всесвязи xi=vi носят временный характер: по окончании вычисления тела этисвязи разрушаются, и если переменные xi были ранее связаны с какимилибо другими значениями, то более ранние связи восстанавливаются.В частном случае k=0 вычисление лямбда-вызова без аргументов:((lambda () e))сводится к вычислению формы e и выдаче полученного результата вкачестве значения этого лямбда-вызова.Таким образом, лямбда-вызов является средством связыванияформальных и фактических параметров на время вычисления телафункции.

А лямбда-выражение и лямбда-вызов, взятые вместе – механизмопределения и выполнения параметризованных вычислений. Отметим, чтоприсутствие в этом механизме этапа 1 означает, что передача фактическихпараметров выполняется по значению, а значит, с помощью него можетбыть определена и вычислена только обычная функция.Ясно, что безымянная функция, определённая в некотором лямбдавыражении и применённая в лямбда-вызове с некоторыми фактическимиаргументами, уже не может быть использована в других лямбда-вызовах,для этого она должна быть повторно в них определена. Поэтомубезымянные функции – это функции, вызываемые один раз, чаще всегоони используются в функционалах (функциях, аргументом или значениемкоторых является функция).Для неоднократного применения функции (а также для построениярекурсивной функции) требуется средство её именования – для этогослужит особая встроенная функция defun, обращение к которой обычноимеет вид:(defun имя_функции лямбда-список тело_функции )15В качестве имени функции выступает символьный атом.

Характеристики

Список файлов книги