Язык Lisp был оценен, как самый мощный язык программирования в мире. Но только очень небольшой процент самых элитных программистов пользуются им из-за его загадочного синтаксиса и его академической репутации. Это весьма печально, поскольку Lisp не так уж и трудно понять. Если вы хотите быть в числе избранных, то эти статьи для вас. Это четвертая статья в серии, которая началась в июне 2011 года.
Для тех, кто относится ко второй и третьей категорий, я ниже отвечу на некоторые ваши вопросы, которые помогут вам стать на путь просветления. Я стою на плечах гигантов. Некоторые фрагменты ответов были взяты из следующих двух источников:
Common Lisp не является интерпретируемым языком. На самом деле даже нет разумного определения понятия «интерпретируемый язык». Мне кажется, что в качестве разумных определений «интерпретируемого языка» можно взять только следующие два определения:
В случае первого определения все языки являются интерпретируемыми. Во втором случае ни один из языков не является интерпретируемым.
Иногда мы смешиваем понятия интерпретируемости и интерактивности. Мы склонны думать, что всякий раз, когда есть интерактивный цикл, например, как цикл чтение-выполнение-выдача результата, имеющийся в Lisp-е, то также должен быть и интерпретатор. Это неправда. Часть, связанную с выполнением, можно реализовывать с помощью компилятора.
Кроме того, обычным пользователям свойственно преувеличивать важность скорости. Есть целый ряд приложений, которые очень медленные, например, Perl, Shell, Tcl/Tk, Awk, и т.д. Неверно, что всегда нужна максимальная скорость.
Lisp не используется в промышленности
… или «я не видел языка Lisp в рекламе о найме на работу».
Lisp используется. Несколько крупных коммерческих программных пакетов написаны на языке Common Lisp или некотором ином варианте языка Lisp. На каком языке написано коммерческое программное обеспечение, разобраться трудно (поэтому пользователю об этом беспокоиться не нужно), но есть некоторые пакеты, о которых это хорошо известно. Interleaf, система документирования, написана на языке Lisp. То же самое можно сказать и о AutoCAD, системе автоматизированного проектирования. Оба они являются основными приложениями в своих областях. Между тем некоммерческая система Emacs, которая также является одной из важных, также написана на Lisp-е.
В 1980-х годах и в начале 1990-х годов основной акцент методологии разработки программного обеспечения был смещен в сторону того, чтобы «все сразу разрабатывалось правильно», т. е. на подходе, при котором на тщательную разработку спецификаций системы необходимы предварительные усилия и на более поздних этапах жизненного цикла разработки программного обеспечения изменения в спецификациях не допускаются. Для сферы искусственного интеллекта было необходимо, чтобы разработка программ была гораздо более гибкой, поскольку в процессе разработки программ нужно было достаточно просто вносить в спецификации неизбежные изменения. Lisp идеально подходит для этого, поскольку в нем можно в интерактивном режиме выполнять проверку, а также поскольку в нем есть краткие и быстро кодируемые мощные высокоуровневые конструкции, например, предназначенные для обработки списков, а также функции типа generic. Другими словами, Lisp был впереди своего времени, поскольку даже до того момента, когда он стал солидно выглядеть среди других главных инструментальных средств, предназначенных для разработки программ, в нем уже присутствовали достаточно гибкие возможности разработки программного обеспечения.
Кроме того, будет ли язык, например, Common Lisp, использоваться в промышленности, гораздо больше зависит от отдельных студентов, а не от промышленности как таковой. Среди студентов распространен миф о том, что промышленность это нечто монолитное, в котором нельзя изменить применяемые инструменты и методы. На самом деле, в промышленности работают люди. В промышленности используется только то, что используют работающие в ней люди. Вместо того, чтобы отказываться от изучения сложных инструментов и методов, студент может решить после окончания обучения попытаться стать в промышленности одним из инноваторов.
Рекурсия или итерация?
В отличие от некоторых других функциональных языков, при программировании на языке Lisp можно использовать как рекурсивный, так и итеративный стили программирования. В качестве примера рассмотрим создание функции, которая вычисляет факториал положительного целого числа n. Факториал, который записывается как n!, является произведением всех целых чисел от 1 до n; т.е.. n! = n×(n-1)×(n-2)×…×2×1. Функция, вычисляющая это число, может быть написана в рекурсивном стиле следующим образом:
Определение функции задается следующим образом. При n равном нулю возвращается значение 1, в противном случае возвращается произведение числа n и факториала n-1. Эта же функция может быть записана в итеративном стиле следующим образом:
Объектная ориентированность
Как и многие другие современные языки программирования, Common Lisp является объектно-ориентированным. На самом деле, это был первый объектно-ориентированный язык стандарта ANSI, включающий в себя CLOS (Common Lisp Object System — систему объектов языка Common Lisp). CLOS предоставляет набор функций, которые позволяют определять классы, иерархию их наследования и связанные с этим классом методы.
Класс определяет своеобразную ячейку, в которые помещаются значения, хранящие информацию об экземплярах объекта. В определении класса можно также указать значения, которые будут использоваться по умолчанию, а также дополнительные достаточно сложные механизмы поведения (например, проверку целостности), которые будут выполняться во время создания объекта. В качестве примера объектно-ориентированного программирования на языке Lisp, рассмотрим определение нескольких фигур, которые могут быть либо кругами, либо прямоугольниками. Положение фигуры задается координатами x и y. Кроме того, круг имеет радиус, а прямоугольник имеет ширину и высоту. Благодаря им можно вычислить площадь окружности и прямоугольника. Ниже приведен рабочий набор определений:
Его площадь можно вычислить с помощью метода area (площадь):
Ниже я попытаюсь в моем глубоко продуманном стиле (я надеюсь, что я не услышу усмешки) объяснить некоторые темы, которые будущим почитателям Lisp-а будет трудно усваивать с помощью книг.
Функция quote
Атом, список и предикаты
То, что находится в списке, но само не является списком, например, слова и цифры (до сих пор использовавшиеся в наших примерах), называются атомами. Атомы отделены друг от друга пробелами или скобками. Вы можете использовать термин атом для обозначения практически любого объекта Lisp, который не рассматривается как состоящий из частей. Атомы, такие как 2,718 и 42, называются числовыми атомами или просто числами.
Функция setq
Функция setq присваивает каждому символу переменной значение, полученное при вычислении соответствующего выражения. В функции setq можно указывать любое четное число аргументов, которые должны быть переменно символами и значениями. Функция возвращает последнее значение.
SETQ не работает для безымянной функции В самоучителе по Лиспу нашел, что можно лямбда-функцию присвоить переменной, и вызывать как обычную.
Setf и другие спискоразрушающие функции. Когда их применение оправдано? Ознакомившись с функциями rplaca, rplacd, я решил никогда, без крайней нужды, не применять.
cout.setf не могу понять Не могу понять что это значит. cout.setf(ios_base::fixed, ios_base::floatfield); В книге.
В свое время я тоже не смог «въехать» в этот вопрос. Читал и статью «setf vs setq». Методически она написана не вполне корректно:
На мой взгляд, лучше было бы обойтись без сомнительных нововведений и просто сказать: setf позволяет модифицировать различные структуры (и, в т.ч. присваивать значения символам). Реализуется, как макрос.
Простейшая реализация (из HomeLisp):
Catstail, тут, ИМХО, больше интересна возможность определять custom setf’able places (для Common Lisp).
Это неформальное понятие, которое используется для объяснения сущности setf. Вот мой вольный перевод фрагмента из главы «Generalized Variables» (CLtL), в которой об этом говорится немного подробнее:
Возможно, лучше было перевести «storage location» как «место хранения».
Частичное применение и «каррирование» функций в Лиспе
Одно из известных преимуществ Лиспа над другими языками программирования состоит в том, что в Лиспе проще, чем где бы то ни было, реализуются различные новые механизмы, появляющиеся в современных языках программирования. Причин тому несколько: это и гомоиконность Лиспа (единая форма представления программ и данных) и уникальная по своим возможностям система макро. В общем, Лисп не зря называют «программируемым языком программирования».
В этой небольшой заметке мы рассмотрим, как можно реализовать в Лиспе такой, весьма популярный ныне программный механизм, как частичное применение функций. При этом я буду использовать свою реализацию Homelisp (это чистый интерпретатор Лиспа с некоторыми дополнительными возможностями).
Вероятно, использование частичного применения в Common Lisp будет не очень простым (в связи с тем, что для вызова вычисляемого функционального объекта нужно использовать funcall/apply); в Scheme дело должно обстоять проще. В ближайшее время я планирую опубликовать новую версию HomeLisp, в котором для вызова вычисляемого функционального объекта не требуется funcall/apply. В тех случаях, когда поведение кода отличается, я буду это подчёркивать.
Частичное применение — это строгая математическая операция. Но мы рассмотрим ее «на пальцах», без обращения к лямбда-исчислению и комбинаторной логике.
Частичное применение функции f — это получение из функции f новой функции f’, которая уже приняла заданные аргументы, и готова принять остальные. Для чего нужно частичное применение? Например, для того, чтобы из функции можно было вернуть функциональное значение.
Рассмотрим частичное применение на простом примере. Пусть функция f задана формулой:
тогда частичное применение этой функции с аргументами x=1 и y=2 должно породить функцию:
В языке Хаскелл частичное применение ничего не стоит программисту:
Однако, в Лиспе такая попытка приведет к неудаче:
Конечно, в Лиспе существует механизм создания функций с любым числом аргументов (конструкция &rest); можно создать функцию, которая будет принимать два или три (или десять) параметров:
Но важно понимать разницу: эта функция обрабатывает все параметры и возвращает результат вычисления, тогда как частичное применение дает в результате новую функцию, которая «готова продолжить вычисления».
Посмотрим, как можно реализовать на Лиспе механизм частичного применения функции. И поможет нам в этом… да-да, аппарат анонимных функций (lambda). Некоторые программисты думают, что анонимные функции нужны только для экономии имен (мол, их место во всяких stream-map-filter-reduce для того, чтобы выполнить короткое действие над элементом последовательности). На самом же деле анонимные функции способны на гораздо большее, в чем мы сейчас и убедимся.
Начнем с того, что рассмотрим, как функция может вернуть другую функцию как результат. В Лиспе это очень просто:
Как видим, функция возвращает замыкание, в котором значение свободной переменной x зафиксировано (равно 5). Результат функции можно вызвать как функцию. Для этого в Common Lisp и HomeLisp (с редакцией ядра
Честно говоря, автор первоначально не планировал излагать в этом руководстве основы Лиспа. Однако, изучив литературу, изданную по Лиспу на русском языке, автор вынужден признать, что она весьма немногочисленна, а последняя книга по Лиспу издана почти 20 лет назад. Получается, что читатель, не знакомый с Лиспом, вынужден либо искать библиографические редкости, либо что-то качать из Интернета.
Хорошая документация должна быть самодостаточна; это обстоятельство и послужило причиной написания раздела, разъясняющего основы Лиспа.
В заключение, автор просит извинения у искушенного читателя (если он сюда забредет!) за навязчивое объяснение элементарных вещей.
Любой язык программирования предназначен для кодирования команд, которые выполняет компьютер. Результатом выполнения команд является все то, ради чего человек использует вычислительную технику (обработка текста, графика, звук, расчеты и т.д.). Процессор компьютера, как правило, умеет исполнять только элементарные команды. Поэтому команды, написанные человеком, обычно преобразуются (транслируются) в команды процессора. Возможен и другой подход, при котором программа на языке программирования не преобразуется в команды процессора, а поступает на вход программы-исполнителя (интерпретируется).
Именно так работает Лисп.
Алфавит языка Лисп.
Алфавит языка Лисп включает в себя заглавные и строчные латинские буквы, цифры и все специальные знаки, которые есть на клавиатуре. Буквы национальных языков традиционно в алфавит не входят, хотя нет никаких особых запретов на этот счет. В частности, в алфавит HomeLisp входят все русские строчные и заглавные буквы.
Среди всех символов алфавита выделяются следующие шесть символов, которые используются особым образом: это пробел, точка, открывающая и закрывающая КРУГЛЫЕ скобки, апостроф и двойная кавычка. Остальные символы, в общем, «равноправны».
отдельно стоящей точки
отдельно стоящей левой или правой скобок или групп левых или правых скобок (за исключением открывающей и закрывающей скобки, стоящих подряд)
отдельно стоящего пробела или группы пробелов
отдельно стоящего апострофа или двойной кавычки
Строка символов, изображающая атом, не может содержать пробела и круглых скобок, но может содержать точку. Кроме того, имеется ограничение на использование двойной кавычки внутри строки, изображающей атом.
Среди всех мыслимых атомов Лиспа сразу выделим четыре специальные группы атомов:
Атомы Nil и T. Эти атомы (особенно Nil) используются для разнообразных целей.
Ниже приводится таблица, иллюстрирующая правила построения атомов Лиспа.
Автор надеется, что читатель вполне уяснил правила составления имен атомов.
бессмысленна (по крайней мере, в HomeLisp). Однако, две следующие записи представляют собой корректные точечные пары:
Введем важное определение: часть точечной пары, расположенную между левой скобкой и точкой будем называть A-частью или А-компонентой. Соответственно, часть пары, расположенную между точкой и правой скобкой будем называть D-частью или D-компонентой.
Атом или точечная пара называются S-выражением. В «мире Лиспа» нет ничего, кроме S-выражений; S-выражениями являются и программы и данные. В памяти компьютера все конструкции, кроме атомов, хранятся и обрабатываются в виде точечных пар.
Этих правил всего два:
Цепочки . Nil просто удаляем;
Цепочки . ( удаляем вместе с соответствующей закрывающей скобкой.
Рассмотрим применение этих правил к записи S-выражения:
На приведенном ниже рисунке показана последовательность упрощений:
Использование описанных правил упрощения привело к тому, что большая часть S-выражений в Лиспе записывается в чисто скобочной нотации и называется списками.
Это последнее определение обычно и приводится в курсах Лиспа. Оно, разумеется, правильно, но не следует забывать, что все S-выражения хранятся в памяти компьютера в виде точечных пар. Точечная запись «незримо присутствует» при работе Лисп-системы (а иногда и неожиданно проявляется; такой пример будет приведен ниже).
Для представления списка в точечной записи существует достаточно простое правило. В соответствии с последним определением, любой список может быть представлен в виде:
В заключение дадим еще три важных определения.
Конструкция () соответствует определению списка. Такой список называется пустым списком. В Лиспе принято считать, что пустой список эквивалентен атому Nil.
Первый элемент списка (он может, в свою очередь, быть атомом или списком) называется головой списка.
Часть списка, за исключением головы называется хвостом списка. Если кроме головы список не содержит других элементов, то хвост такого списка есть пустой список.
Внутреннее представление списков.
Оперативная память, в которой хранятся S-выражения, обычно делится на две больших области: список объектов и область списочных ячеек.
В списке объектов хранятся атомы. Каждый атом занимает блок памяти переменного размера. В этом блоке хранится символьное изображение атома и ряд его дополнительных характеристик.
Область списочных ячеек состоит из блоков фиксированного размера. Каждая списочная ячейка хранит два адреса, которые по историческим причинам называются А-указатель и D-указатель. Эти адреса могут указывать как на атомы (т.е. хранить адреса областей из списка объектов), так и на другие списочные ячейки.
Графически точечную пару изображают так:
Не представляет труда построить графическое изображение и более сложных списков. Так, например, список (A B C D) устроен так:
Автор надеется, что читатель уяснил преимущества графического представления списочных структур. Надо заметить, что с помощью прямоугольников и стрелок можно изобразить S-выражения, которые невозможно записать в скобочной нотации. Речь идет о циклических списках. Вот пример такого выражения:
Как видно из рисунка, S-выражение состоит из двух списочных ячеек и двух атомов. В D-указателе второй списковой ячейки содержится указатель на первую списковую ячейку. Записать это S-выражение в скобочной записи нельзя, но его можно создать (с помощью функций RPLACA и RPLACD; автор счел нецелесообразным описывать эти функции в элементарном введении в Лисп. )
Говоря о внутреннем представлении S-выражений, следует добавить, что каждый атом уникален. Даже если в каком-либо списке атом A встречается многократно, в списке объектов он представлен в единственном экземпляре (т.е. во всех списочных ячейках из которых исходят стрелки, указывающие на атом A, будет содержаться один и тот же адрес).
В обращении к читателю было сказано, что синтаксис S-выражений на первых порах проще всего представлять, как формальную знаковую систему. Начиная с этого момента, читатель может смотреть на S-выражения не как на формальные конструкции из букв и скобок, а как на реальные структуры данных, хранящиеся в памяти компьютера.
Лисп-машина читает входящие команды, имеющие вид S-выражений, вычисляет значение каждого из введеных выражений, и выводит результат. Значением S-выражения является, разумеется, тоже S-выражение. (Кроме S-выражений в мире Лиспа ничего нет!) Побочным эффектом вычисления входящих S-выражений является изменение состояния Лисп-машины.
Вычисление значения выполняется по следующим формальным правилам:
Если входное S-выражение является атомом то:
— для атомов T и Nil их значением является сами атомы T и Nil соответственно;
— для атомов, представляющих корректное изображение числа, строки или битовой шкалы значением также является сам атом. Такие атомы (Nil, T, числа, строки и битовые шкалы) будем далее называть самоопределенными.
— все прочие атомы могут иметь значением S-выражение, которое было присвоено атому вызовом функций SET, SETQ или CSETQ. Если атому не было присвоено значения перечисленными выше функциями, то такой атом не имеет значения.
Если входное S-выражение является списком, но голова списка представляет собой список, то этот список рассматривается как т.н. лямбда-выражение. Лямбда выражение задает безымянную функцию. Хвост исходного S-выражения задает список параметров этой безымянной функции. Разумеется, лямбда-выражение составляется по строгим правилам, которые будут описаны ниже. Если голова списка не является корректным лямбда-выражением, то вычисление завершается ошибкой.
Все остальные S-выражения значений не имеют. Попытка вычисления таких выражений вызывает ошибку.
В частности, если головой списка является число, строка, битовая шкала или список (не являющийся лямбда-выражением), то ведущая функция заведомо не существует и не может быть вычислена.
S-выражения, которые имеют значения, называются формами.
Вызовы функций типа SUBR и типа EXPR не отличаются по форме и выглядят следующим образом:
Многоточие здесь означает повторение. Каждый из аргументов может быть атомом или списоком. Функция «знает» сколько аргументов ей требуется. Если количество аргументов оказывается больше или меньше необходимого, возникает ошибка вычисления функции и выдается соответствующее сообщение. Бывают функции с переменным числом аргументов, а бывают и функции без аргументов. Обращение к такой функции выглядит так:
В математике широко применяется конструкция «функция от функции». Например, запись F(G(x)) означает вычисление G(x), а затем вычисление функции F, с аргументом, равным G(x). Как записать эту конструкцию в обозначениях Лиспа? Очевидно, что запись:
Именно так Лисп-машина и поступает!
Вычисление выражения общего вида:
Рассмотрим, например, вычисление следующего S-выражения:
Вычисление будет проходить через следующие этапы:
S-выражение (H «q» «p») является вызовом функции H с двумя аргументами «q» и «p». Значением атома «q» является сам атом «q», а значением атома «p» является сам атом «p». Далее вычисляется значение функции H с двумя аргументами «p» и «q». Предположим, что это значение равно S-выражению Рез_Н. Таким образом, первый аргумент исходного вызова функции F принимает вид (G 1 2 Рез_Н). Это выражение вычисляется, предположим, что результат вычисления равен Рез_G.
Проблема вычисляемых аргументов. Классификация функций Лиспа.
Получается, что никакой функции Лиспа принципиально нельзя передать параметр вида (1 2 3 4 5)?
Разумеется, это не так. Отмеченая проблема решается в Лиспе двумя способами: введением специального класса функций, которые не вычисляют свои аргументы, а также выборочным использованием функции QUOTE, о чем будет сказано ниже.
В Лиспе есть класс встроенных функций, которые не вычислют значения своих аргументов, а используют сами аргументы. Встроенные функции, вычисляющие значения аргументов, называются функциями класса SUBR, а встроенные функции, НЕ вычисляющие значения некоторых или всех аргументов, называются функциями класса FSUBR.
Соответственно, функции, написанные на Лиспе, тоже могут не вычислять значения своих аргументов. Функции, написанные на Лиспе и вычисляющие значения аргументов, называются функциями класса EXPR, а функции, написанные на Лиспе и НЕ вычисляющие значения некоторых или всех аргументов, называются функциями класса FEXPR.
В целом, классификация функций Лиспа может быть изображена следующим рисунком:
Диалог с Лисп-машиной.
Большинство Лисп-машин работают по «телетайпному» принципу: пользователь вводит S-выражение, Лисп-вычисляет и выводит ответ (тоже, естественно, S-выражение). Простейшим примером такого диалога может служить консольное окно Windows (или UNIX/LINUX). В HomeLisp пользователь вводит S-выражение в область ввода и получает ответ в области вывода. Подробности диалога описаны в здесь. Введенное выражение дублируется в области вывода, поэтому область вывода содержит полный протокол диалога с пользователем.
Важно отметить следующее: если вычисление введенного завершено с ошибкой, то HomeLisp возвращает в качестве результата специальный атом ERRSTATE (ведь результат должен быть тоже S-выражением!). Если вычисления результата заняли слишком много времени, происходит принудительная остановка Лисп-машины и в качестве результата возвращается специальный атом BRKSTATE
Кроме того, некоторые функции могут что-то выводить в область вывода. Эта информация выводится перед результирующим S-выражением.
Ниже приводится пример взаимодействия с Лисп-машиной. Ответ Лисп-машины предваряется набором символов «==>».
Здесь пользователь ввел имя атома _ver (версия ядра) и получил ответ.
Выше был приведен пример функции SUMLIST, вычисляющей сумму элементов списка, заданного единственным аргументом. Если функция SUMLIST принадлежит к классу EXPR или SUBR, то попытка вычислить (SUMLIST (1 2 3 4 5)) вызовет ошибку. Ведь сначала будет предпринята попытка вычислить значение списка (1 2 3 4 5), а это S-выражение не имеет значения. А вот вызов (SUMLIST (QUOTE (1 2 3 4 5))) не вызовет ошибки, ведь сначала будет вычислено значение (QUOTE (1 2 3 4 5)), результат вычисления равен (1 2 3 4 5). Этот результат без повторного вычисления будет передан на вход функции SUMLIST, которая вычислит сумму.
Ниже приводится пример использования функции QUOTE. Предполагается, что функция SUMLIST имеется в системе, принадлежит к классу EXPR или SUBR (т.е. вычисляет свои аргументы).
По уже укоренившейся традиции вместо того, чтобы писать:
Далее в этом разделе будет употребляться именно такая запись. Следует обратить внимание на то, что скобки перед апострофом не ставятся.
Присвоение значений атомам. Функции SET, SETQ и CSETQ.
Выше было отмечено, что произвольному атому Лиспа можно присвоить значение. Сейчас будут рассмотрены функции, которые выполняют эти действия.
Рассмотрим несколько примеров использования функции SET:
Попытка присвоить атому a значение 1 оказалась неудачной, поскольку при вычислении первого аргумента была выполнена попытка вычисления значения атома a. Чтобы предотвратить ошибку, нужно квотировать первый аргумент. Вторая попытка оказывается удачной. Теперь атом a получил значение 1, в чем можно убедиться, просто послав на вход Лисп-машины атом a.
Следующая команда (set ‘a a) должна была бы присвоить атому a значение a. Однако, этого не происходит. Причина заключается в том, что, поскольку втрой аргумент функции SET не квотирован, произойдет его вычисление. Атом a имеет значение 1, поэтому фактически будет выполнена команда (SET ‘a 1). Значение атома а не изменится.
А вот команда (set ‘a ‘a) присваивает атому a значение a. ЧуднО, но логично!
Функция SETQ (класса FSUBR) отличается от SET тем, что не вычисляет значение первого аргумента. Поэтому первый аргумент при вызове SETQ не нужно квотировать. В остальном функция SETQ эквивалентна функции SET.
Атом, которому присвоено значение вызовом функций SET/SETQ обычно называется переменной.
Функция СSETQ (класса FSUBR) отличается от SETQ тем, что целевой атом после возврата получает значение, которое нельзя изменить (превращается в константу). Попытка изменить значение константы с помощью команд SET/SETQ/CSETQ вызывает ошибку. Соответственно, если атом является переменой, превратить его в константу уже не удастся. Рассмотрим примеры:
Здесь успешно создана константа ZZ. Попытка изменить ее значение или превратить в переменную, вызывает ошибку.
Разбор списков на составные части. Функции CAR, CDR и их комбинации.
Функции CAR и CDR служат для выделения головы и хвоста списка соответственно. Обе эти функции принадлежат к классу SUBR, т.е. они вычисляют значение своего единственного аргумента. Несколько странные названия этих функций обусловлены историческими причинами (функции названы в честь регистров компьютера IBM-709, на котором была выполнена первая реализация Лиспа). В свременных языках, допускающих обработку списков, эти функции называются HEAD и TAIL. Лисп, однако, остается верен традициям.
Попытка применить функции CAR и CDR к атому вызовут состояние ошибки.
Вот исчерпывающий набор примеров вызова функций CAR и CDR:
Чтобы выделить второй, третий и т.д. элементы списка, можно применять комбинации CAR и CDR. Так например, для того, чтобы получить второй элемент списка S, нужно вычислить форму (CAR (CDR S)). В связи с тем, что различные комбинации вызовов CAR и CDR встречаются в реальных программах достаточно часто, в Лисп обычно вноятся их стандартные комбинации, приведенные ниже.
Вызов
Результат
(CDAR ‘((1 2) (3 4)))
(2)
(CAAR ‘((1 2) (3 4)))
1
(CADR ‘((1 2) (3 4)))
(3 4)
(CDDR ‘((1 2) (3 4)))
Nil
(CDDDR ‘(1 2 3 4))
(4)
(CADAR ‘((1 2) (3 4) (5 6)))
2
(CADDR ‘((1 2) (3 4) (5 6)))
(5 6)
(CADDDR ‘(1 2 3 4 5 6))
4
Построение списков из составных частей. Функции CONS и LIST.
Вот реальные примеры вызова CONS:
В последнем случае можно было ожидать, что должен был бы получиться список (a b c d), но это не так! Чтобы понять, почему так происходит, достаточно представить оба аргумента CONS в виде точечных пар, построить результат (тоже в виде пары), и применить к нему правила упрощения.
Цепочка упрощений показана ниже (удаляемые элементы выделены красным):
Для получения из двух списков (a b) и (c d) списка (a b c d) служит функция APPEND, описываемая ниже.
В отличие от функции CONS, функция LIST принимает произвольное число аргументов. Эта функция принадлежит классу SUBR (ее аргументы вычисляются). Функция возвращает список, состоящий из значений аргументов.
Таким образом, LIST представляет собой полезнейшую функцию Лиспа: т.к. она позволяет «собирать» из составных частей списки произвольной длины. Если какой-либо из аргументов этой функции не требуется вычислять, его можно квотировать.
Проверка на «атомность». Функция АТОМ.
Сколь-нибудь содержательная программа на любом языке программирования не может состоять только из «линейных» действий (типа присвоения, композиции сложного из простого и разложения сложного на простые составляющие). Необходимы средства сравнения и принятия решений. Лисп не составляет исключения. Ниже будут рассмотрены все необходимые конструкции Лиспа, служащие для сравнения S-выражений.
По-видимому, самый простой вопрос, который можнет относиться к произвольному S-выражению, это вопрос: «Является ли S-выражение атомом или нет?». На этот вопрос отвечает функция ATOM (класса SUBR). Эта функция возвращает атом T, если значение ее единственного аргумента есть атом, и Nil в противном случае.
Вот примеры вызова функции ATOM:
Первый и второй примеры понятны без комментариев. Некоторое удивление может вызвать третий пример, ведь аргументом функции ATOM является список (car ‘(1 2 3)), тем не менее, функция возвращает T. Все дело в том, что функции ATOM на вход попадает не сам аргумент, а его значение (функция принадлежит классу SUBR!). Значением же S-выражения (car ‘(1 2 3)) является атом 1. Поэтому функция ATOM «увидит» на входе не (car ‘(1 2 3)), а простую единицу. Естественно, результат вычисления будет T (единица есть атом).
Сравнение атомов. Функции EQ, NEQ, NOT и NULL.
Функция EQ, относящаяся к классу SUBR принимает два аргумента. Она работает следующим образом:
Если значением первого и второго аргумента является один и тот же атом, то функция возвращает в качестве результата атом T;
Во всех остальных случаях функция возвращает атом Nil.
Все остальные случаи включают ситуации, когда значение одного или обоих аргументов не есть атом. Функция EQ вернет Nil даже в случае, когда значением обоих аргументов является одно и то же S-выражение, но не атом!
Вот примеры вызова функции EQ:
При вызове функции атомы Nil и T не квотируются, поскольку, как было отмечено выше, эти атомы являются самоопределенными.
Символы EQ при вызове одноименной функции можно заменить знаком равенства (=). Таким образом, запись (EQ a b) полностью эквивалентна записи (= a b).
Функция NEQ, относящаяся к классу SUBR, принимает два аргумента. Она выполняет действия, в точности противоположные функции EQ:
Если значением первого и второго аргумента является один и тот же атом, то функция возвращает в качестве результата атом Nil;
Во всех остальных случаях функция возвращает атом T.
Все остальные случаи, как и для функции EQ, включают ситуации, когда значение одного или обоих аргументов не есть атом. Следует обратить внимание на то, что функция вернет T даже в случае, когда значением обоих аргументов функции является одно и то же S-выражение, но не атом.
Вместо символов NEQ можно писать знак неравенства <>. Вот несколько примеров вызова функции NEQ:
Функции NULL и NOT (класса SUBR) представляют собой в сущности, одну и ту же функцию. Действие, выполняемое этой функцией, очень простое. Если значение единственного аргумента функции есть Nil, то функция возвращает T. Во всех остальных случаях (когда значение аргумента НЕ есть Nil, функция возвращает Nil. Примеры вызова:
Теперь все готово к тому, чтобы рассмотреть главную условную конструкцию Лиспа, чему и посвящен следующий раздел.
Функция вычисляет свое значение следующим образом:
Вычисляется значение выражения Условие1;
Если это значение есть атом T, то вычисляется значение выражения Результат1 и это значение возвращается в качестве результата функции COND;
Если это значение НЕ есть атом T, то вычисляется значение выражения Условие2;
Если это значение есть атом T, то вычисляется значение выражения Результат2 и это значение возвращается в качестве результата функции COND;
Процесс повторяется до тех пор, пока список аргументов будет исчерпан, либо пока значение одного из условий не окажется атомом T.
Если не одно из условий не дает в результате вычисления атом T, то функция COND вернет атом Nil. (Так реализована функция COND в HomeLisp; в других версиях Лиспа реализация может несколько отличаться. Возможна, например, не сравнения результата условия с атомом T, а несравнение с атомом Nil.)
Легко видеть, что конструкция:
очень похожа на конструкцию оператора IF языка Visual Basic:
Впрочем, знакомые с языком Visual Basic могут заметить, что в Visual Basic перед завершающим END IF может стоять конструкция ELSE Результат, которая получит управление, если все условия оказались ложными. Для этих целей в функции COND обычно в качестве последнего условия ставят атом T. В этом случае последнее условие оказывается гарантированно выполненым.
Рассмотрим примеры вызова COND (пока, весьма элементарые):
Арифметические функции Лиспа.
В приведенной ниже таблице представлены элементарные арифметические функции HomeLisp.
Имя функции
Сокращение
К-во аргументов
Результат
PLUS
+
переменное
сумма значений
DIFFERENCE
—
переменное
значение первого минус сумма значений остальных
TIMES
*
переменное
произведение значений
QUOTIENT
\
2
целочисленное частное
REMAINDER
%
2
целочисленный остаток
DIVIDE
/
переменное
значение первого аргумента делится на произведение значений оставшихся (с плавающей точкой)
EXPT
^
2
значение первого аргумента, возведенное в степень, равную значению второго.
GREATERP
>
2
Т если значение первого аргумента больше значения второго; Nil в противном случае
GREQP
>=
2
Т если значение первого аргумента больше или равно значению второго; Nil в противном случае
LESSP
2
Т если значение первого аргумента меньше значения второго; Nil в противном случае
LEEQP
2
Т если значение первого аргумента меньше или равно значению второго; Nil в противном случае
EQ
=
2
Т если значение первого аргумента равно значению второго; Nil в противном случае
NEQ
<>
2
Т если значение первого аргумента не равно значению второго; Nil в противном случае
Вот примеры использования всех перечисленых функций:
Детали, относящиеся к каждой из арифметических операций, более подробно изложены в разделе, посвященным встроенным функциям Лиспа.
Универсальная функция EVAL.
Функция EVAL, относящаяся к классу SUBR, вычисляет значение своего единственного аргумента и возвращает его в качестве результата. Ядро Лиспа, в сущности, работает следующим образом:
1. Ожидает ввода S-выражения;
2. Передает введенное S-выражение функции EVAL;
3. Выводит полученный результат;
Функцию EVAL можно употреблять, например, при необходимости вычислить значение S-выражения, построенного динамически (в процессе вычислений). Другое применение функции EVAL состоит в вычислении (при необходимости) значений аргументов функции класса FEXPR в теле самой функции.
Создание собственных функций. Функция DEFUN.
Для создания функции класса EXPR служит специальная встроенная функция DEFUN (определить функцию). Сама функция DEFUN принадлежит классу FSUBR. Вызов этой функции требует трех аргументов:
Первый аргумент должен атомом;
Второй аргумент должен быть списком атомов;
Третий аргумент может быть произвольной формой (S-выражением, имеющим значение).
Атом, который задан первым аргументом функции DEFUN, после возврата «превратится в функцию». Второй аргумент функции DEFUN называется списком формальных параметров. Третий аргумент функции DEFUN называется телом функции или определяющим выражением.
Если вызов функции DEFUN завершился удачно, то в качестве результата возвращается атом, заданный первым параметром, а в системе появляется новая функция, требующая при вызове столько аргументов, сколько элементов содержалось в списке формальных параметров. При вычислении этой новой функции значения аргументов будут вычисляться.
Итак, чтобы создать функцию, необходимо обратиться к порождающей функции DEFUN:
Построим простейшую арифметическую функцию, которая вычисляет разность квадратов своих аргументов. Для имени функции выберем атом QDIF (полагая, что такой функции еще нет). Список параметров нашей функции будет содержать два формальных параметра: (x y). Остается написать тело функции (S-выражение, вычисляющее разность квадратов значений x и y:
Пусть читатель обратит внимание на то, что тело функции содержит атомы, входящие в список формальных параметров. Можно создать функцию, тело которой не обращается к формальным параметрам. Однако, такая функция при любых параметрах давала бы один и тот же результат.
Как работает функция? При вызове:
Теперь испытаем нашу функцию:
Рассмотрим приведенную врезку подробнее. Введенная команда DEFUN возвращает в качестве результата атом QDIF. Это является признаком успешного создания функции QDIF. Следующие затем три вызова «свежесозданной» функции QDIF подтверждают ее работспособность.
Далее заводятся две переменные x и y и им присваивается значение 6. Последующий вызов функции с аргументами 12 и 11 дает правильный результат. А вот проверка значений атомов x и y может удивить. Ведь, в соответствии со сказанным выше, переменным x и y при вызове функции должны были присвоиться значения 12 и 11. Тем не менее, значения переменных x и y остаются теми же, какими были до вызова функции!
Будем называть атомы, входящие в список формальных параметров какой-либо функции переменными, связанными в теле этой функции. Переменные, не входящие в список формальных параметров, но использующиеся в теле функции, будем называть свободными переменными.
Испытание нашей функции QDIF демонстрирует важный принцип Лиспа: после возврата из функции значения связанных в теле функции переменных будут теми же самыми, что и до вызова функции.
А вот если функция каким-либо образом изменит значение свободной переменной, то это изменение останется и после выхода из функции. Как же функция может изменить значение свободной переменной? Употреблением функций SET/SETQ. Изменим тело нашей функции QDIF следующим образом:
Здесь тело функции представляет собой вызов SETQ, который присваивает свободной переменной z значение разности квадратов, которое вычисляется по прежней формуле. Поскольку SETQ возвращает значение второго аргумента, функция QDIF не теряет работоспособности, однако, если приcвоить атому z какое-либо значение, то после вызова оно будет заменено разностью квадратов:
Приемы программирования на Лиспе. Рекурсия.
Сейчас будет рассмотрен первый пример нетривиальной программы на Лиспе, который вполне передает суть этого замечательного языка.
Пусть имеется произвольный список, состоящий из чисел. Нужно подсчитать сумму чисел, входящих в список. Как это сделать? Длина списка (количество его элементов) заранее не известна. Читателям, знакомым с традиционными языками программирования, возможно, покажется, что нужно завести переменную для будущей суммы, а затем, перебирая элемент за элементом наш список, копить сумму. Процесс этот повторять до завершения списка. Так поступить действительно можно, но непонятно, как организовать циклическое повторение.
На самом деле, поставленная задача допускает простое и элегантное решение. Обозначим нашу будущую функция SUMLIST. Тогда, если входной список пуст, то функция должна возвращать нуль. Это понятно. А если список непуст, то представляется вполне очевидным, что сумма элементов списка равна его первому элементу (CAR) плюс сумма элементов остатка (CDR). Другими словами, нашу функцию можно представить так:
Пусть читатель обратит внимание на лаконичность определения функции. Всего две строки, причем очень понятного кода! В каком еще языке программирования такое возможно?!
Чтобы убедиться в работоспособности нашей функции, попробуем вычислить сумму списка (1 2 3 4 5):
Функция работает. Можно убедиться, что функция будет работать правильно с любым одноуровневым списком чисел. Следует отметить, что функция SUMLIST вызывает сама себя. Такие функции называются рекурсивными.
Может возникнуть вполне естственный вопрос: почему функция, вызывающая сама себя, не «зацикливается»? Это происходит потому, что в теле функции первым условием стоит проверка значения входного параметра на пустоту. Если значение входного параметра есть пустой список (Nil), то происходит выход из функции с возвратом значения 0. А теперь пусть читатель обратит внимание на то, что повоторное обращение к функции SUMLIST происходит не к исходному списку, а к его остатку (после отделения головы). Последующее обращение происходит с остатком остатка и т.д. Поскольку список имеет конечное число элементов, то рано или поздно остаток окажется пустым списком. Это гарантирует завершение цепочки вызовов.
Обычно тело рекурсивной функции состоит из проверки различных условий. Условие, гарантирующее выход, называется терминальным условием. Обычно, хотя и не обязательно, терминальное условие располагается в списке условий первым (как в функции SUMLIST). Что произойдет, если терминальное условие будет опущено? Ответ на этот вопрос дает следующая врезка:
Здесь вводится определение неправильной рекурсивной функции (без терминальной ветви). Функция принимается ядром Лиспа, однако, попытка вычислить сумму даже простого списка из трех элементов вызывает ошибку с соответствующей диагностикой.
Рекурсия «изнутри». Трассировка выполнения. Функции TRACE и UNTRACE.
Трудно предположить, какие чувства испытывает читатель при первом знакомстве с рекурсией, но у автора этих строк рекурсия до сих пор вызывает ощущение чуда. Чтобы изучить работу рекурсивной функции, удобно использовать возможность Лиспа, называемую трассировкой.
Видно, что рекурсивная функция SUMLIST, «точит исходный список, как карандаш». Суммирование элементов происходит от последнего к первому.
Другие примеры рекурсивных функций.
Функция SUMLIST верно работает только для атомных одноуровневых списков (т.е. списков, состоящих из атомов). Если попытаться вызвать эту функцию для списков другого типа, то она окажется неработоспособной:
В протоколе трассировки видно, что ошибка происходит, когда функция пытается к числу 6 прибавить список (4 5).
Доработаем функцию SUMLIST таким образом, чтобы она могла суммировать элементы списков любой структуры. Это не так трудно, как может показаться на первый взгляд. Посмотрим еще раз на определение функции SUMLIST:
Читатель, вероятно, уже догадывается, что для того, чтобы не возникала ошибка, нужно перед сложением применить к выражению (CAR x) функцию SUMLIST. Таким образом, наша функция станет «дважды рекурсивной»:
Это, однако, еще не решает проблему, а, напротив, порождает новые ошибки:
Можно убедиться, что функция работоспособна:
Хорошо видно, что теперь функция работает корректно с любыми списками, подаваемыми на ее вход.
Рассмотрим еще одну задачу обработки списков. Пусть заданы два произвольных списка. Требуется их объединить (т.е. из списков (a b c) и (d e f) получить список (a b c d e f).
Сразу обратим внимание читателя на то, что «лобовое» применение функции CONS не дает требуемого результата. Значением выражения (CONS ‘(a b c) ‘(d e f)) будет список ( ( a b c ) d e f), а отнюдь не (a b c d e f).
Решение снова получилось коротким и изящным (что, как правило, всегда характерно для рекурсивных программ).
Безымянные функции. Конструкция LAMBDA.
Вот пример задания безымянной функции:
Легко видеть, что приведенная выше LAMBDA-конструкция полностью эквивалентна традиционной именованной функции:
Впрочем, HomeLisp позволяет использовать безымянные функции нетрадиционным образом: если присвоить какому-либо атому в качестве значения корректное LAMBDA-выражение, то появляется возможность использовать это LAMBDA-выражение без повторного задания:
Последний вызов (sq2 6 7) очень похож на вызов функции sq2. Сходство, однако, чисто внешнее. Атом sq2 не является именем функции (что будет разъяснено ниже, при рассмотрении списков свойств).
Буква греческого алфавита лямбда взята из т.н. лямбда-исчисления разработанного английским математиком Чёрчем. Изображение буквы лямбда давно стало негласным символом языка Лисп.
Функциональные аргументы. Функционалы.
Рассмотрим простую задачу: дан произвольный список чисел, требуется построить список квадратов этих чисел. Решение этой задачи довольно просто:
В теле функции сначала анализируется, не пуст ли входной список. Если это так, функция возвращает пустой список (обязательная терминальная ветвь рекурсии). В противном случае функция отщепляет первый элемент списка, возводит его в квадрат и строит точечную пару из этого квадрата и результата применения функции к остатку исходного списка без первого элемента. Функция успешно работает.
Теперь предположим, что потребовалась аналогичная функция, но возводящая элементы списка не в квадрат, а в куб. Придется составить фукнцию p3:
Если сравнить определяющие выражения функций p2 и p3, то легко увидеть, что эти функции различаются только действием, применяющимся к голове списка, в остальном эти функции идентичны. А что, если действие, применяющееся к голове списка, сделать параметром функции? Тогда вместо двух (или большего числа) разных функций достаточно будет составить единственную функцию:
Для того, чтобы воспользоваться новой функцией pf, нужно составить функцию, возводящую одно число в квадрат (или куб):
Читатель вероятно уже догадался, что для возведения элементов списка в квадрат, нужно вызвать функцию pf следующим образом: (pf ‘(1 2 3 4) f^2). Однако такой вызов приводит к ошибке:
И понятно, почему это происходит: функция pf принадлежит к классу EXPR, поэтому, перед вызовом ядро Лиспа делает попытку вычислить значение атома f^2. Чтобы предотвратить эту ошибку, атом f^2 при вызове нужно квотировать:
Второй аргумент вызова функции pf представляет собой имя функции. Такой аргумент называется функциональным, а функция, имеющая хотя бы один функциональный аргумент, называется функционалом.
Для вызова функционалов предназначена специальная «функция» FUNCTION. С использованием этой «функции» последний вызов записывается так:
На месте функционального аргумента может стоять и безымянная функция, т.е. лямбда-выражение. Приведенный выше пример возведения элементов списка в квадрат может быть решен без предварительного определения именованной функции следующим образом:
Применяющие функционалы. Функции FUNCALL и APPLY.
В ядро Лиспа встраиваются два стандартных функционала FUNCALL и APPLY. Рассмотрим их подробнее.
Функция FUNCALL принадлежит классу SUBR и принимает произвольное количество аргументов. Эта функция применяет свой первый (функциональный) аргумент к оставшемуся списку аргументов. Это выглядит примерно так:
Использование FUNCALL позволяет, например, давать именам функций синонимы (примеры взяты из книги Э.Хювенен, Й.Сеппянен [6]):
Более того, допустимо использовать имя стандартной функции для хранения ссылки на какую-либо другую функцию:
Любопытно, что если вернуться к предыдущему примеру (с присвоением значения + атому сложить), то легко убедиться, что квотирование здесь не дает эффекта:
Отображающие функционалы. Функции MAPLIST и MAPCAR.
Еще одним классом функционалов является класс отображающих функционалов. Такие функционалы применяют функциональный аргумент к элементам списка, в результате чего строится новый список. Отсюда и название: исходный список отображается на результирующий.
Здесь будут рассмотрены два отображающих функционала: MAPLIST и MAPCAR.
В первом примере используется функция, вычисляющая сумму элементов списка. Первый раз суммируется список (1 2 3 4 5 6); получается 21. Затем суммированию подвергается список (2 3 4 5 6); получается 20 и т.д. Полученные результаты объединяются в список. Результат равен (21 20 18 15 11 6).
Во втором примере используется функция, обращающая список. Эта функция возвращает не атом, а список. При первом вызове обращается список (1 2 3 4 5 6); получается (6 5 4 3 2 1). Затем обращается список (2 3 4 5 6); получается (6 5 4 3 2) и т.д. В результате получается список, состоящий из списков.
В отличие от MAPLIST, функционал MAPCAR применяет функциональный аргумент не к остаткам списка, а последовательно к каждому элементу. Результаты этих применений объединяются в список, который и возвращает функционал MAPCAR. Вот как это выглядит:
Функциональное выражение, заданное вторым аргументом MAPCAR, возводит свой аргумент в квадрат. Вызов MAPCAR отображает исходный список на список своих квадратов.
В противоположность функциональной, процедурная парадигма соответствует подходам традиционных языков: используются присвоения, явные переходы, циклы.
Процедурное программирование в Лиспе. Функция PROG.
Разумеется, Лисп имеет в своем составе и средства для процедурного программирования. Как известно, краеугольным камнем процедурного подхода является понятие оператора. Оператор выполняет различные действия над значениями переменных. Для присвоения переменным значений служат функции SET/SETQ. А для моделирования блока операторов служит конструкция PROG, которая описывается ниже.
Конструкция PROG имет следующий общий вид:
Как видно из врезки, далее в теле PROG подряд располагаются атомы или произвольные вызовы функций. Эти, отдельно стоящие атомы, называются метками. Выполнение тела PROG заключается в том, что последовательно выполняются вызовы функций, а метки пропускаются. Обычно отдельные вызовы в теле PROG-конструкции называются операторами. Таким образом, можно сказаь, что тело PROG-конструкции состоит из операторов и меток.
Могут быть вызваны любые доступные функции, а кроме того, имеются две специфические функции, которые могут употреблятся только в теле PROG. Это функции GO и RETURN. Обе эти функции принадлежат к классу SUBR.
Значением единственного аргумента функции GO должен быть атом. Выполнение GO заключается в том, что среди меток тела PROG ищется значение аргумента GO. Если значение найдено, то в качестве следующего вызова функции выполняется вызов функции, стоящей после найденной метки. Если же метка, заданная при вызове GO, отсутствует в теле функции, то выполнение PROG завершается ошибкой. Легко видеть, что функция GO осуществляет передачу управления.
Функция RETURN осуществляет выход из PROG-конструкции. Значение аргумента RETURN возвращается, как значение всей PROG-конструкции. После выполнения функции RETURN все атомы, входящие в список локальных переменных, теряют значения, которые могли быть им присвоены в теле PROG. Если же атом, входящий в этот список, ранее имел значение, то это значение восстанавливается.
Если последний вызов функции в теле PROG-конструкции (перед закрывающей скобкой) не есть вызов RETURN, то происходит принудительный выход из PROG-конструкции, а в качестве результата возвращается Nil.
В качестве первого примера PROG-конструкции рассмотрим уже решенную ранее задачу подсчета суммы элементов одноуровнего списка. Решение получится вполне традиционным: заводим локальную переменную для суммы (x) и для остатка списка (y). Далее:
2) Прибавляем к значению x голову y;
3) Присваиваем переменной y значение хвоста y;
4) Если значение y оказывается равным Nil, возвращаем значение х;
5) Переходим к шагу 2.
Ниже показывается, как работает такая конструкция:
Здесь сначала переменной lst присваивается суммируемый список. Далее PROG-конструкция вычисляет сумму его элементов. Как можно убедиться, получается правильный результат. Далее, переменной x «нарочно» присваивается значение 777, после чего снова вычисляется сумма элементов списка. И, хотя переменная x меняет свое значение в теле PROG, после возврата значение x сохраняется.
Функции типа FEXPR. Функция DEFUNF.
Функции типа FEXPR отличаются от функций типа EXPR тем, что при их вычислении, ядро Лиспа не вычисляет значения аргументов, а передает их функции как есть.
Для создания функции типа FEXPR служит функция DEFUNF, являющаяся полным аналогом функции DEFUN, но порождающая функцию типа типа FEXPR. Использование функций типа FEXPR требует понимания и острожности. Рассмотрим в качестве примера простую функцию создающую точечную пару из двух аргументов:
Если значение параметра f (обязательно вычисляемого в теле функции!), равно Nil, строится точечная пара из значений аргументов. Если же значение параметра f равно T, то строится точечная пара из самих аргументов. Вызов CONSQ с параметром f=Nil требует вычисления значений аргументов (и вызывает ошибку, если хотя бы один из аргументов не имеет значения).
Функции типа MACRO. Функция DEFMACRO.
Если преобразуемый текст есть текст программы на каком-либо языке программирования, то применение средств макрогенерации позволяет, например, на основе одного исходного текста генерировать программы, рассчитанные на различные аппаратные платформы (Windows, Unix, Linux). Практически все современые средства разработки программ имеют в своем составе более или менее мощные макрогенераторы. Если такой макрогенератор автоматически запускается перед компиляцией, то его принято называть препроцессором.
Изобразительные возможности языка препроцессора, как правило, заметно слабее изобразительных возможностей базового языка. Исключение, пожалуй, составляет язык PL/I, в составе которого имеется мощный препроцессор, очень сходный по синтаксису с базовым языком. В языках C/С++, VB, Delphi возможности препроцессора весьма скромны.
Функции-макросы начинают вычисляться, как обычные функции класса FEXPR, но результат вычисления вновь подается на вход универсальной функции EVAL. Введение таких функций в Лисп открывает любопытные возможности.
Вернемся к задаче вычисления суммы элементов произвольного списка (уже решенной выше). Оказывается, с использованием макро задачу о суммировании элементов списка можно решить значительно проще! В самом деле, если имеется числовой одноуровневый список произвольной длины, то для вычисления суммы элементов достаточно вычислить значение S-выражения, которое получается простым добавлением плюса в начало исходного списка.
Для того, чтобы реализовать эту идею, необходимо в теле функции лишь построить список, состоящий из плюса и всех элементов суммируемого списка, а функция EVAL будет применена к этому списку автоматически:
В приведенном выше фрагменте использована функция DEFMACRO. Эта функция ничем не отличается от функций DEFUN и DEFUNF, кроме того, что порождает функции, вычисляемые в два этапа (как описано выше). Аргументы функций типа MACRO не вычисляются, поэтому при вызове список (1 2 3 4) не квотируется. Результат получается правильным (и заметно быстрее, чем при рекурсивном суммировании!).
При отладке MACRO бывает полезно увидеть промежуточное S-выражение, которое подается затем на вход EVAL. Увидеть это выражение позволяет встроенная функция MACROEXPAND:
Поверхностный взгляд может привести к заключению, что функции типа MACRO бесполезны: ведь не составляет большого труда написать обычную функцию (типа EXPR/FEXPR), которая готовит промежуточное S-выражение, а затем явно вызывает EVAL для его вычисления:
Функция верно считает сумму, но не присваивает результат в качестве значения второму параметру. Понятно, почему это происходит: ведь функция SETQ не вычисляет значения первого аргумента. В результате, присвоение выполняется, но значение получает не атом z, указанный при вызове, а атом y (связанная переменная). При выходе из функции связанная переменная y уничтожается, а с атомом z ничего не происходит. Исправить ситуацию можно, употребив вместо функции SETQ функцию SET:
Все хорошо? Не будем торопиться с выводами. Проверим, как будет работать наша функция, если мы захотим присвоить результат переменной y:
А вот что получится, если вместо функции EXPR-типа воспользоваться MACRO:
Было бы неверно полагать, что поскольку MACRO выполняется в два этапа, выполнение макро-функций требует больше времени, чем вычисление функций типа EXPR/FEXPR. Это далеко не всегда так. Например, рекурсивное суммирование списка чисел от единицы до двухсот на компьютере автора выполняется примерно за 60 мсек, тогда, как функция MSUMLIST вычисляет тот же результат менее чем за 9 мсек. (почти в 7 раз быстрее). В данном случае это происходит потому, что рекурсивная программа много времени тратит на рекурсивные вызовы, тогда как при использовании макро рекурсии нет совсем, а вычисление происходит за один вызов функции PLUS, которая принадлежит классу SUBR и работает быстро. Сказанное, разумеется, не означает, что автор противопоставляет макро рекурсивному подходу; просто в ряде случаев макро может оказаться эффективнее.
Одним из наиболее важных применений макро является создание «новых конструкций» в языке. Кавычки здесь употребляются не случайно: макровызов все равно в процессе вычисления преобразуется в одну из базовых конструкций Лиспа.
В качестве иллюстрации сказанного попробуем составить макро, добавляющий к конструкциям базового Лиспа простой «оператор» IF. Синтаксис этого «оператора» определим так:
Напишем макро, которое реализует требуемые действия:
Легко убедиться, что макро IF просто генерирует простую COND-конструкцию. Атомы Then и Else при вызове макро связываются в переменных dummy1 и dummy2. Эти переменые в теле макро никак не анализируются. При необходимости можно было бы ужесточить синтаксис «оператора» IF, анализируя значения переменных dummy1 и dummy2.
Из приведенного примера видно, что макро IF допускает вложенный вызов и работает правильно. Кстати, понятно, почему при вызове макро не вычисляются аргументы. Если бы это было бы не так, то в приведенном выше примере пришлось бы квотировать атомы Then и Else, что нельзя признать изящным.
В Лиспе все обстоит не так. Конструкция, соответствующая оператору x=x+y, в Лиспе имеет вид (SETQ x (+ x y)). При вычислении выражения (+ x y) (при значениях x=1 и y=2) получится 3, что в идеологии Лиспа означает, что будет создан атом 3. Именно этот атом и будет присвоен в качестве значения атому x.
Прежде, чем создать новый атом, Лисп-машина проверяет, не существует ли этот атом в системе. Если атом не существует, Лисп-машина его создает. В любом случае, при построении списка или другого S-выражения, содержащего атом, в самом выражении хранится не атом, а ссылка на него.
Все сказанное выше означает, что Лисп является символьным языком: первичными объектами Лиспа являются символы (атомы). Атомы могут иметь вид привычных человеку чисел, строк и т.д., но могут быть и совершенно произвольными цепочками литер. Символьный характер Лиспа порождает довольно любопытные ситуации, иногда не имеющие аналогов в традиционных (не символьных) языках программирования. Один из таких моментов рассматривается подробно в следующем разделе.
Контекст вычисления в HomeLisp.
Ниже речь будет идти в основном о HomeLisp; тонкости других известных автору реализаций будут оговорены явно.
Рассмотрим очень простой пример:
Здесь определена функция, которая строит из своих аргументов точечную пару. Функция ведет себя абсолютно предсказуемо. Рассмотрим, к примеру, вызов (g1 x y). Поскольку функция g1 принадлежит классу EXPR, то значения аргументов x и y будут вычислены ядром Лиспа до передачи управления в функцию g1; связанные в теле функции переменные x и y получат значения 1 и 2 соответственно.
А теперь чуть-чуть подправим функцию g1 и создадим функцию g2:
Отличие заключается в том, что к значениям аргументов дополнительно применяется функция eval. Испытаем нашу функцию, предполагая, что переменные x, y и z имеют прежние значения (1, 2 и 3) соответственно:
Результат вызова (g2 x y) не отличается от результата вызова (g1 x y) и это неудивительно: при вычислении значений атомов x и y получается 1 и 2 соответственно. Связанные в теле функции переменные x и y получат значения 1 и 2. И, поскольку (eval 1) равно 1, а (eval 2) равно 2, результат получается такой же, как и при вызове g1.
Разберемся, почему это происходит.
Получается, что функции типа приведенной выше g2 («довычисляющие» значения аргументов в теле функции) будут работать неверно, если значение фактического параметра совпадет с именем какого-либо формального параметра. В действительности дело обстоит еще хуже: если значение фактического параметра есть выражение, содержащие свободные переменные, имена которых совпадают с именами связанных переменных, то при вычислении в теле функции будут подставлены значения связанных переменных. Крайне неприятная ситуация, совершенно немыслимая для традиционных языков типа Паскаля, Си или Бэйсика (несимвольных языков)! Правда, в Лиспе «довычисление» значений аргументов характерно скорее для класса FEXPR, но ситуация от этого не становится более легкой.
Определим новую функцию-макрос g2m следующим образом:
то ситуация нормализуется (предполагается, что переменные x, y и z имеют прежние значения):
Ситуация дополнительно усложняется при использовании конструкции PROG и локальных переменных. Рассмотрим следующую врезку:
Здесь тело функции fqq представляет собой PROG-конструкцию с локальной переменной z. Этой локальной переменной в теле функции присваивается значение 222. Когда функция fqq вычисляется со значением аргумента, равным 5, не происходит ничего неожиданного: результат равен пяти. А вот если вычисляется выражение (fqq ‘z), то происходит следующее: сначала связанная переменная n (формальный параметр функции) получает значение z; когда в теле функции будет выполняться оператор RETURN, произойдет обращение к функции eval с аргументом z. В даный момент атом z будет иметь значение 222, поэтому функция вернет результат 222. То, что свободная переменная z имеет значение 111, не окажет никакого влияния на результат: значение свободной переменной «перекрыто» значением одноименной локальной переменной.
Снова получается, что значение выражения зависит от места, где оно вычисляется (т.е. от контекста вычисления). Если функция «довычисляет» значения своих аргументов, то имена локальных PROG-переменных могут повлиять на результат. Поэтому, некоторые версии Лиспа не поддерживают PROG-переменных.
А вот в системах XLisp Дэвида Бетца (David Betz) и Томаса Алми (Thomas Almy), и в Российской реализации Лиспа YLisp Дмитрия Иванова и Арсения Слободюка аналогичный пример дает другой результат:
В этих системах использование локальных переменных с любыми именами не окажет влияния на «довычисление» значений аргументов в теле функции. Видно, что при вычислении (eval n) использовалось значение z, как глобальной переменной.
Вот еще одна достаточно сложная ситуация, которая сводится к проблеме контекста. Рассмотрим следующую врезку:
Здесь происходит неявное «довычисление» значения параметра в теле функции. Поскольку функция SET принадлежит к классу SUBR, то при вычислении (set n x) ядро Лиспа сначала вычислит значение n (при этом получится z), затем вычислит значение второго аргумента (получится 111). Функция SET будет вычисляться с аргументами z и 111. Естественно, атом z получит значение 111, что и будет напечатано. Поскольку z является локальной PROG-переменной, то после выхода из функции атом z не будет иметь никакого значения (или не изменит прежнего значения, если до вызова символ z был переменной).
Совсем по-другому эта функция будет вычисляться в среде XLisp:
Вызов функции SET создает здесь переменную, которая сохраняет значение после выхода из функции. Казалось бы, вызов (set n x) при значении n, равном z, должен был бы изменить значение локальной переменной z, а вместо этого создается свободная переменная z, а локальная переменная не меняет значения. Получается, что set действует в другом контексте.
Отмеченные расхождения долго не давали покоя автору этих строк. Наконец было принято решение ввести в ядро языка две функции geval (вычислить в глобальном контексте) и gset (присвоить в глобальном контексте).
Функция geval работает совершенно аналогично функции eval за одним исключением: при вычислении значений атомов сначала проверяется, не существует ли свободная переменная с соответствующим именем. И, если такая переменная существует, используется ее значение; в противном случае используется значение локальной PROG переменной. Если же одноименная локальная переменная не найдена, то функция geval «полагает», что атом не имеет значения.
Приведенный выше пример, в котором вместо eval используется geval, дает точно такой же результат, что и в XLisp:
Вот как выглядит модифицированная функция sqq:
Динамические и лексические переменные.
Рассмотрим следующий пример:
Здесь символ x связан в теле функции f (является параметром), а символ y свободен. Если не существует глобальной переменной y (созданной вызовом SET/SETQ на верхнем уровне), то вычисление (f x) завершится ошибкой (т.к. свободный символ символ y не имеет значения). При вычислении функции g символ y получит значение и последующее вычисление значения f завершится нормально. Чтобы разобраться, почему это происходит, имеет смысл включить дампирование и посмотреть на пары, возникающие в ассоциативном списке при вычислении выражения (+ x y):
Переменная, которая видима во всех формах в течение своего времени жизни, называется динамической. Как можно убедиться, все переменые в HomeLisp (по крайней мере в редакциях ядра 11.*.*) являются динамическими.
Если попытаться выполнить приведенный выше пример в системе XLisp или YLisp, то результат будет другим:
Здесь переменная y, связанная в функции g оказывается невидимой в форме (f 5).
Переменная, которая видима только в форме, в которой определена, называется лексической. В системах XLisp, YLisp (и всех других, следующих стандарту CommonLisp) все переменные по умолчанию являются лексическими. Соблюдения стандарта CommonLisp в части лексических переменных планируется реализовать в редакциях ядра HomeLisp, начиная с версии 13.1.*.
Кстати, в стандарте CommonLisp лексическую переменную легко превратить в динамическую. Для этого достаточно вызвать функцию defvar в форме: (defvar Имя_переменной). После успешного завершения этой команды переменная, имя которой задано при вызове defvar начинает вести себя как динамическая:
Пару функций f и g, приведенную выше, можно использовать в качестве теста, проверяющая тип переменных той или иной реализации Лиспа. Вот пример проверки известной в недалеком прошлом системы MuLisp:
Сразу видно, что в MuLisp переменные по умолчанию динамические.
Классическое определение гласит: Лексической переменной (или переменной с лексической областью видимости является переменная, видимая только в той форме, где она определена. Добавим, что если в форме, определяющей переменную, есть вызов функции, а переменная не входит в список формальных параметров этой функции, то переменная не будет видима в теле функции.
Чтобы сказанное не казалось слишком абстрактным, рассмотрим простой пример:
Такое поведение переменной a вовсе не связано с тем, что эта переменная создана при помощи LET-конструкции. Вот другой пример, дающий тот же результат:
Здесь переменная a (равная после вызова g единице) снова невидима в теле функции f. Описанное и задает суть понятия лексическая видимость. Можно несколько «оживить» данное выше определение:
Лексическая переменная, это такая переменная, которая, будучи свободной относительно функции, невидима в этой функции.
Все переменные в HomeLisp по умолчанию являются лексическими.
Если переменную a из предыдущих примеров сделать динамической, то результаты вычислений изменятся:
Легко убедиться, что переменная a теперь видима в теле функции f. Следует отметить, что превращение переменной в динамическую вызовом DEFDYN не присваивает этой переменной никакого значения; попытка вычислить значение a завершается ошибкой. Важно отметить, что став динамической, переменная будет оставаться таковой до завершения работы Лисп-машины.
В HomeLisp в дополнение к динамическим есть также глобальные переменные. Если переменная объявлена глобальной, то она будет видима в любой точке программы (как и положено глобальной переменной). Создать глобальную переменную можно либо вызовом функции DEFGLOB, либо вызвав SET/SETQ на верхнем уровне. При этом «глобальность» и «лексичность/динамичность» не исключают друг друга. Если глобальная переменная не объявлена динамической, то она будет вести себя, как лексическая: установленное выше значение не «просочится» в вызов, а будет просто взято глобальное значение. Глобальная динамическая переменная практически не отличается от просто динамической переменной.
Вот комплексный пример:
Списки свойств атомов.
STRING— признак строки;
WINDOW— признак графического окна;
DIALOG— признак диалога;
Когда создается атом, являющийся числом, битовой константой или строкой, то ядро Лиспа сразу же строит список свойств, содержащий соответствующие флаги. Ссылка на этот список хранится вместе с атомом. Для других атомов соответствующий признак попадает в список свойств, когда выполняется функция создания соответствующего программного объекта (диалога, графического окна, файла и т.д.)
Чтобы увидеть список свойств атома нужно вызвать функцию PROPLIST. Эта функция показывает список свойств своего единственного аргумента, который должен являться атомом. Вот примеры вызова функции PROPLIST:
Рассмотрим еще несколько примеров вызова функции PROPLIST:
Список свойств атома может иметь сколь угодно сложную структуру, однако обычно он является одноуровневым списком.
В принципе двух описанных функций (PROPLIST и SPROPL) достаточно для любых манипуляций со списками свойств. При необходимости другие функции можно реализовать на Лиспе (см. PUTFLAG, PUTPROP, FLAG, FLAGP).
Совершенно естественным применением списков свойств могло бы быть моделирование математических объектов (рациональные числа, векторы, матрицы и т.д.). К сожалению, использование списков свойств здесь не так удобно, как может показаться на первый взгляд. Проблема состоит в том, что каждый атом в Лиспе уникален, соответственно уникален и список его свойств. А вот значения атома зависят от контекста вычислений. Если некий атом используется как локальная переменная, то его значение при выходе из PROG-конструкции восстановится. Но если внутри PROG-конструкции у этого атома модифицировался список свойств, то этот список свойств не изменится при выходе из PROG. Подобная ситуация совершенно недопустима, поэтому в главе, посвященной приемам программирования на Лиспе, признаки создаваемых объектов (массивов, рациональных чисел и т.д.) хранятся в общем списке с данными, составляющими сущность моделируемого объекта.
Setf и другие спискоразрушающие функции. Когда их применение оправдано?
отдельно стоящей точки
