Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 8
Текст из файла (страница 8)
Лиспинтерпретатор загружает этот файл, последовательно вычисляя входящие внего лисповские выражения. По окончании обработки всего файлаинтерпретатор переходит к вычислению выражений, вводимых склавиатуры.Рассмотренный пример программы демонстрирует лёгкость иестественность расширения языка Лисп новыми операциями. За счёт этогов рамках одного диалекта Лисп можно реализовать конструкции другогодиалекта. Например, в MuLisp файл common.lsp содержит определенияряда встроенных функций диалекта Common Lisp (отсутствующих вMuLisp), и после загрузки его лисп-интерпретатором появляетсявозможность использования этих функций.В языке Лисп уже установленная связь имени и определяющеговыражения функции реально используется только в момент вызовафункции и вычисления её значения, согласно так называемой концепциипозднего связывания [11].
Поэтому порядок определения функций впрограмме может быть произвольным, и возможны случаи, когда функцияиспользуется в определении другой функции, но сама определяетсяпозднее. Главное, к моменту своего реального вычисления функциядолжна быть определена. В приведённом примере лисп-программы вызовыфункций AddCom и MultCom (для вычисления суммы и произведениядвух конкретных комплексных чисел) стоят после определения всехфункций, но каждый из этих вызовов может быть поставлен раньше, сразупосле определения соответствующей функции.Для переменных позднее связывание означает динамическуютипизацию и динамическое связывание со значением [11, 15].В языке Лисп переменные не связываются предварительно с какимито типами данных, тип данных любой переменной определяется во времяисполнения программы – в тот момент, когда эта переменная получаетзначение определенного типа. Необходимая проверка этого типа тожеосуществляетсядинамически.Динамическаятипизациядаётдополнительную гибкость использования переменных в лисп-программах,однако неизбежной платой за это является трата времени на проверкунужного типа на этапе исполнения.Динамическое связывание, или динамический доступ к значениямпеременных (применялось во всех ранних диалектах Лиспа, а ныне – вMuLisp) означает, что значение переменной берётся из ближайшейобъемлющей вычисляемой функции, где есть переменная с таким именем.39Указанная стратегия связывания упрощает создание интерпретаторафункционального языка.
Однако она может приводить к нежелательнымэффектам в случаях, когда тела вычисляемых функций содержат не толькоеё параметры, но и другие переменные, значения которых необходимобрать из внешнего окружения. Простейший пример такой функции:(lambda (x) (cond (x) (y)))Нежелательные эффекты возникают в случаях конфликта имён такихпеременных (в данном примере – переменная y); более подробно этотвопрос будет рассмотрен в разделе про функционалы. Заметим, что втекущем разделе во всех определениях лисп-функций в телах этихфункций для вычисления их значения использовались только значения ихформальных параметров.Для исключения возможных проблем многие диалекты Лиспаприменяют статическое связывание.
В частности, в Common Lisp поумолчанию действует статическое (лексическое) связывание, но принеобходимости для некоторых переменных можно установитьдинамическое связывание. В целом, статическое связывание позволяетпроводить более эффективную компиляцию функциональных программ,однако проигрывает динамическому по времени исполнения программы.Различные диалекты и реализации языка Лисп отличаются наиболеезначительно именно стратегией связывания.Хотя в строго функциональном программировании на Лиспеглобальные переменные отсутствуют, есть некоторое исключение. Кглобальным можно отнести связи, установленные для имён функций (атакже связь атома с его списком свойств). Эти связи доступны в любоймомент вычислений и могут быть использованы для организации впрограмме констант. К примеру, можно ввести и применять затемфункцию без аргументов, выдающую в качестве своего значения нужнуюконстанту:(defun PI () 3.14)Такую функцию имеет смысл помещать в начало лисп-программы,аналогично тому, как в традиционных языках программированияопределения констант идут в начале программы или блока.402.
Рекурсивное программированиеРекурсия естественно возникает при обработке данных, имеющихрекурсивную внутреннюю структуру, в том числе – при обработке списков[6]. Использование рекурсии в таких случаях не только упрощаетнаписание программ, но и делает их более понятными.В данном разделе на примерах решения задач рассматриваютсятипичные приёмы построения рекурсивных программ и обсуждаются видыиспользуемой при этом рекурсии.2.1. Простая рекурсияБудем говорить, что рекурсия простая, если рекурсивный вызовфункции встречается не более одного раза в любой ветви условноговыражения, служащего телом функции. Простая рекурсия ужеиспользовалась нами при программировании функций Length, Member,Append, RevАppend.В качестве ещё одного примера простой рекурсии приведёмопределение функции Reverse (обычно это встроенная функция).
Онапереворачивает свой список-аргумент, т.е. меняет порядок его элементовверхнего уровня на противоположный, например:(Reverse '(A (B D) C)) => (C (B D) A).(defun Reverse (L)(cond ((null L) NIL)(T (append (Reverse (cdr L))(cons (car L) NIL) )) ))В этом определении реализована следующая идея рекурсивногопостроения требуемого списка: он получается из перевёрнутого спискахвоста исходного списка (т.е. списка без первого элемента верхнегоуровня) присоединением к нему справа первого элемента. Дляприсоединения используется функция append, а не cons, т.к.
последняяможет добавлять элементы только в начало списка. Поскольку обааргумента append должны быть списками, в качестве второго аргументаберётся одноэлементный список из первого элемента исходного списка.Покажем ход вычисления функции Reverse. Теперь дляиллюстрации динамики вычислений вместо схематичного изображениястека с отложенными функциональными вызовами будем просто по шагампереписывать вычисляемое выражение, последовательно заменяя в нёмвычисленное на данном шаге подвыражение (функциональный вызов) наего значение.
На каждом шаге вычисляется один функциональный вызов.41Номер шага вычисления указывается слева от выражения, полученного наэтом шаге вычисления, а внутри выражения подчёркиваетсяфункциональный вызов, подлежащий вычислению на следующем шаге.0)1)2)3)(Reverse: L=(A (B D) C) )(append (Reverse: L=((B D) C)) '(A))(append (append (Reverse: L=(C)) '((B D))) '(A))(append (append (append (Reverse: L=()) '(C))'((B D))) '(A))4) (append (append (append () '(C)) '((B D))) '(A))5) (append (append '(C) '((B D))) '(A))6) (append '(C (B D)) '(A))=> (C (B D) A)Видно, что при движении по исходному списку от начала в конец(реализуемого с помощью функций car и cdr), очередные элементыисходного списка сохраняются (в виде одноэлементных списков) вовтором аргументе отложенных рекурсивных вызовов функций append.Выполнение же этих отложенных вызовов и реальное построениеперевёрнутого списка начинается, когда пройдены все элементы верхнегоуровня исходного списка (т.е.
список стал пуст). При этом подсоединениесохранённых элементов к результирующему списку происходит в порядке,противоположном их следованию в исходном списке.Сложность рекурсивных вычислений можно оценивать такойхарактеристикой, как глубина рекурсии – количество сохранённых иобработанных в стеке вложенных вызовов рекурсивной функции. Врассмотренном примере функции Reverse глубина рекурсии равна длинереверсируемого списка.Заметим, что в традиционных языках программирования (Паскаль, Си др.) для программирования повторяющихся вычислений используютсяциклы.
Известно, что рекурсия – более мощное средство, чем любаяциклическая конструкция, в то же время циклы требуют меньшего объёмапамяти и, как правило, выполняются быстрее. Объём памяти, требуемойдля выполнения цикла, можно оценить некоторой константой, независящей от числа шагов цикла (итераций). Для рекурсии необходимыйобъем памяти (стека) линейно зависит от глубины рекурсии.В целом, рекурсия – более затратный по памяти и времени механизм(из-за расходов, связанных с организацией стека). Тем не менее, есть классрекурсивных функций, вычисление которых можно выполнять без стека –это функции, представляющие так называемую хвостовую рекурсию.Современные лисп-интерпретаторы и компиляторы распознают случаихвостовой рекурсии и оптимизируют вычисление таких функций.42Ключевая идея оптимизации хвостовой рекурсии – выполнениерекурсивной функции так, как если бы она была циклической(итерационной), т.е.
её вычисление в строго фиксированном участкепамяти, при этом рекурсивная функция как бы вызывает сама себя безстека.Из приведённых нами примеров простой рекурсии к хвостовойрекурсии относятся только функции Member и RevAppend . Рекурсиясчитается хвостовой, если в теле функции рекурсивный её вызов невстречается в качестве аргумента никакой другой функции. В то же времяпри вычислении аргументов рекурсивного вызова допускаются обращенияк другим функциям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
