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

Единственное, что можетпроизойти с уже существующей списочной структурой – потеря указателяна неё. Например, после вычисления вызова функции append (см. Рис. 4)пропадает указатель на первый её аргумент – структуру (Q(R)()), и трисписочные ячейки этой структуры становятся недоступны.34Неизменяемость уже созданных списочных структур представляеттакое важное свойство функционального программирования, какотсутствие побочных эффектов вычислений [14, 15].Изучая списочные структуры, показанные на Рис.

4, можно такжезаметить, что стрелки (указатели) могут сходиться на одной списочнойячейке, но не могут образовать замкнутый цикл. Это справедливо для всехсписочных выражений, построенных на основе базового набора лиспфункций. Таким образом, физической (внутренней) структуройS-выражения является ациклический ориентированный граф.Внутреннее представление S-выражений проясняет вопрос оспособах их сравнения на равенство. Поскольку любой символьный атомединственным образом представлен в таблице символов, то для проверкиравенства двух атомов достаточно сравнить их адреса в таблице. Именнотак реализована встроенная функция eq, проверяющая равенство двухатомов. Другими словами, физическое равенство атомов означает илогическое их равенство.Однако для списочных структур логическое и физическое равенствоне одно и то же, поскольку логически одинаковые списки могут бытьпредставлены различными списочными ячейками памяти.

Подобнаяситуация возникает, например, в результате работы функции Copy,копирующей в памяти заданное списочное выражение:(defun Copy (x)(cond ((atom x) x)(T(cons (Copy (car x))(Copy (cdr x)) )) ))Поскольку копирование элементов происходит на всех уровняхсписочного выражения x, в результате в памяти создаётся его дубликат,причём указатель на этот дубликат отличен от указателя на исходноесписочное выражение.Таким образом, логическое равенство двух списков не может бытьпроверено путём сравнения указателей на списочные ячейки в памяти,необходима последовательная проверка содержимого соответствующихсписочных ячеек сравниваемых списков.

Такую проверку реализуетвстроенная функция-предикат equal с двумя вычисляемымиаргументами. Она выполняет сравнение на равенство двух произвольныхS-выражений и вырабатывает соответственно T или NIL.Для работы лисп-интерпретатора традиционно выделяются две, какправило, независимые области памяти:• под таблицу символьных атомов;• под списочные ячейки (списочная память).35В процессе работы часть списочной памяти уже использованаинтерпретатором под списочные ячейки, остальная часть называетсясвободной списочной памятью, и из неё берётся новая списочная ячейкапри вызове функции cons.

Было показано, что в ходе вычислений частьсписочных ячеек перестаёт использоваться и ссылки на них могуттеряться. Если не уничтожать ненужные списочные ячейки (а они могутзанимать существенную часть памяти), рано или поздно область свободнойсписочной памяти будет исчерпана, что обнаружится при очередномобращении к функции cons. Для решения указанной проблемы лиспинтерпретаторы обычно используют специальную утилиту сборки мусора(т.е. списочных ячеек, которые недоступны на текущий моментвычислений) и подсоединения их к области свободной списочной памяти.Эта утилита вызывается либо по исчерпании свободной списочной памяти,либо периодически в ходе работы интерпретатора.Во многих диалектах языка Лисп есть так называемые структурноразрушающие встроенные функции (rploca, rplocd, nconc и др.),изменяющие содержимое уже существующих списочных ячеек.

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

Более важно, однако, другое –подавляющее число функций побочного эффекта как раз не имеет. Именноэто и представляет собой одну из главных отличительных особенностейфункционального программирования. Кроме неё можно указать и другиеособенности, связанные с характером использования переменных иуправления последовательностью операций [14, 15].В строго функциональном языке переменные скорее подобныматематическим переменным – они употребляются, чтобы дать именазначениям аргументов некоторой функции, и связаны с этими значениямина протяжении всего вычисления тела этой функции. Обычный в36традиционных императивных языках программирования (Паскаль, С и др.)оператор присваивания переменной значения отсутствует в строгофункциональных языках, и переменная может получить значение, толькобудучи формальным параметром некоторой функции, во времявычисления её вызова. По окончании вычисления вызова функции этапеременная-параметр автоматически теряет полученное значение.В функциональном программировании нужная последовательностьопераций достигается вызовом функций в определённом порядке, т.е.суперпозицией функций.

Передача данных между функциями выполняетсячерез их аргументы и возвращаемые результаты (значения). Вместотрадиционных условных операторов и циклов применяется соответственноусловное выражение (cond) и более мощное средство – рекурсия.Программа на функциональном языке является ничем иным, какнабором запрограммированных функций. Еще одна особенностьфункциональной программы связана с тем, что в строго функциональномязыке отсутствует понятие глобальной переменной и константы. Всепеременные локальны, поскольку представляют собой формальныепараметры функций с областью действия – телом функции.Типичная лисп-программа включает:• определения новых функций на базе встроенных функций и другихфункций, определённых в этой программе;• вызовы этих новых функций для конкретных значений ихаргументов.Как правило, в начале программы ставятся определения функций, а затем –их вызовы.В тексте лисп-программы можно использовать комментарии.Комментарии обычно начинаются точкой с запятой (;), при этом вся частьстроки, следующая за этим символом, считается комментарием.В качестве примера приведём программу, в которой определяютсяосновные операции над комплексными числами.

Сами комплексные числапредставляются как двухэлементные списки чисел вида(действительная_часть мнимая_часть),например: список (1.2 -5) представляет число 1.2-5i.Сначала в программе определяются функции-операции надкомплексными числами – сложения, умножения, вычитания, деления,сравнения на равенство.

Затем эти функции используются для вычислениянескольких выражений, в которых используются комплексные числа. Впрограмме даётся комментарий к каждой определяемой функции ивычисляемым затем выражениям.37; Программа для работы с комплексными числами; комплексное число – список вида; (действительная_часть мнимая_часть); функция сложения двух комплексных чисел(defun AddCom(Com1 Com2)(cons (+ (car Com1)(car Com2))(cons (+ (cadr Com1)(cadr Com2)) NIL))); функция вычитания двух комплексных чисел(defun SubCom(Com1 Com2)(cons (- (car Com1)(car Com2))(cons (- (cadr Com1)(cadr Com2)) NIL))); функция сравнения двух комплексных чисел(defun EqCom(Com1 Com2)(and (= (car Com1)(car Com2))(= (cadr Com1)(cadr Com2)))); функция умножения двух комплексных чисел(defun MultCom(Com1 Com2)(cons (- (* (car Com1)(car Com2))(* (cadr Com1)(cadr Com2)))(cons (+ (* (car Com1)(cadr Com2))(* (cadr Com1)(car Com2)))NIL))); функция деления комплексных чисел(defun DivCom(Com1 Com2)(let ((z (+ (* (car Com2)(car Com2))(* (cadr Com2)(cadr Com2))) ))(cons (/ (+ (* (car Com1)(car Com2))(* (cadr Com1)(cadr Com2)))z)(cons (/ (- (* (cadr Com1)(car Com2))(* (car Com1)(cadr Com2)))z)NIL )))); вычисление суммы чисел 2+3i и 1.5-8i(AddCom '(2 3) '(1.5 -8)); вычисление произведения чисел 3-i и 3+i(MultCom '(3 -1) '(3 1))38Хотя входящие в эту программу вычисляемые выражения(определения функций и их вызовы) могут быть последовательно введеныпользователем с клавиатуры, обычно лисп-программа хранится втекстовом файле (имеющем в диалекте MuLisp расширение .lsp).

Лиспинтерпретатор загружает этот файл, последовательно вычисляя входящие внего лисповские выражения. По окончании обработки всего файлаинтерпретатор переходит к вычислению выражений, вводимых склавиатуры.Рассмотренный пример программы демонстрирует лёгкость иестественность расширения языка Лисп новыми операциями. За счёт этогов рамках одного диалекта Лисп можно реализовать конструкции другогодиалекта. Например, в MuLisp файл common.lsp содержит определенияряда встроенных функций диалекта Common Lisp (отсутствующих вMuLisp), и после загрузки его лисп-интерпретатором появляетсявозможность использования этих функций.В языке Лисп уже установленная связь имени и определяющеговыражения функции реально используется только в момент вызовафункции и вычисления её значения, согласно так называемой концепциипозднего связывания [11].

Поэтому порядок определения функций впрограмме может быть произвольным, и возможны случаи, когда функцияиспользуется в определении другой функции, но сама определяетсяпозднее. Главное, к моменту своего реального вычисления функциядолжна быть определена. В приведённом примере лисп-программы вызовыфункций AddCom и MultCom (для вычисления суммы и произведениядвух конкретных комплексных чисел) стоят после определения всехфункций, но каждый из этих вызовов может быть поставлен раньше, сразупосле определения соответствующей функции.Для переменных позднее связывание означает динамическуютипизацию и динамическое связывание со значением [11, 15].В языке Лисп переменные не связываются предварительно с какимито типами данных, тип данных любой переменной определяется во времяисполнения программы – в тот момент, когда эта переменная получаетзначение определенного типа. Необходимая проверка этого типа тожеосуществляетсядинамически.Динамическаятипизациядаётдополнительную гибкость использования переменных в лисп-программах,однако неизбежной платой за это является трата времени на проверкунужного типа на этапе исполнения.Динамическое связывание, или динамический доступ к значениямпеременных (применялось во всех ранних диалектах Лиспа, а ныне – вMuLisp) означает, что значение переменной берётся из ближайшейобъемлющей вычисляемой функции, где есть переменная с таким именем.39Указанная стратегия связывания упрощает создание интерпретаторафункционального языка.

Однако она может приводить к нежелательнымэффектам в случаях, когда тела вычисляемых функций содержат не толькоеё параметры, но и другие переменные, значения которых необходимобрать из внешнего окружения. Простейший пример такой функции:(lambda (x) (cond (x) (y)))Нежелательные эффекты возникают в случаях конфликта имён такихпеременных (в данном примере – переменная y); более подробно этотвопрос будет рассмотрен в разделе про функционалы. Заметим, что втекущем разделе во всех определениях лисп-функций в телах этихфункций для вычисления их значения использовались только значения ихформальных параметров.Для исключения возможных проблем многие диалекты Лиспаприменяют статическое связывание. В частности, в Common Lisp поумолчанию действует статическое (лексическое) связывание, но принеобходимости для некоторых переменных можно установитьдинамическое связывание. В целом, статическое связывание позволяетпроводить более эффективную компиляцию функциональных программ,однако проигрывает динамическому по времени исполнения программы.Различные диалекты и реализации языка Лисп отличаются наиболеезначительно именно стратегией связывания.Хотя в строго функциональном программировании на Лиспеглобальные переменные отсутствуют, есть некоторое исключение.