Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 11

Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, апотом работает CONS над полученными значениями. Но если EVAL задано (QOUTE X), то Xне будет вычисляться. QUOTE - специальная форма, которая препятствует вычислению своихаргументов.Специальная форма отличается от других функций двумя чертами. Ее аргументы невычисляются до того, как специальная форма сама просмотрит свои аргументы. COND,например, имеет свой особый способ вычисления аргументов с использованием EVCON.Второе отличие от функций заключается в том, что специальные формы могут иметьнеограниченное число аргументов.Определение рекурсивной функции можно преобразовать к безымянной форме.

Техникаэквивалентных преобразований позволяет поддерживать целостность системы функцийвтягиванием безымянных вспомогательных функций внутрь тела основного определения.Верно и обратное: любую конструкцию из лямбда-выражений можно преобразовать всистему отдельных функций. Техника функциональных определений и их преобразованийпозволяет рассматривать решение задачи с естественной степенью подробности, гибкости имобильности.Специальная функция FUNCTION обеспечивает доступ к функциональному объекту, афункция FUNCALL обеспечивает применение функции кпроизвольному числу ееаргументов.(funcall f a1 a2 ...

) = (apply f (list a1 a2 ...))Разрастание числа функций, манипулирующих функциями, связано с реализационнымразличием структурного представления данных и представляемых ими функций.Программы для Лисп-интерпретатора.Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.20Пример 1.(CAR '(A B)) = (CAR (QUOTE(A B)))Функция: CARАргументы: ((A B))Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственнымаргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подаетсясписок аргументов.Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR.

Это корректно, но не являетсянеобходимым.Пример 2.(CONS 'A '(B . C))Функция: CONSАргументы: (A (B . C))Результат (A . (B . C)) программа печати выведет как (A B . C)Пример 3.(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )Функция: CONSАргументы:((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))Значением такого вычисления будет((CAR (QUOTE (A . B))) . (CDR (QUOTE (C .

D))))21Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE(A . B)) получить A и ожидал (A . D) в качестве итогового значения CONS. Кроме очевидногостирания апострофов:(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )ниже приведены еще три правильных способа записи нужной формы. Первыйсостоит в том, что CAR и CDR части функции задаются с помощью LAMBDA вопределении функции.

Второй - в переносе CONS в аргументы и вычислении их спомощью EVAL при пустом а-списке. Третий - в принудительном выполненииконстантных действий в представлении аргументов,((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A . B) '(C . D))Функция:(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))Аргументы:((A . B)(C .

D))(EVAL '(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))Nil)Функция: EVALАргументы:((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)Значением того и другого является (A . D)22((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A . B)))'(CDR (QUOTE (C . D))) )Функция:(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))Аргументы:((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))Решения этого примера показывают, что грань между функциями и данными достаточноусловна - одни и те же вычисления можно осуществить при разном распределениипромежуточных вычислений внутри выражения, передвигая эту грань.Выводы:-Чтобы выполнить вычисление на реальном Лисп-интерпретаторе необходимо уточнитьряд правил по оформлению текста Лисп-программы.-Определения функций можно сделать обозримее именованием выражений. Это дает иэкономию на времени вычисления совпадающих форм.-При реализации системы программирования возникают дополнительные механизмы,такие как списки свойств атома, повышающие скорость доступа к необходимойинформации.-Некоторые функции системы необходимо реализовывать в виде машинных подпрограмм.Они образуют ядро системы.-При подготовке программ для Лисп-интерпретатора грань между программой иданными может устанавливаться в зависимости от текущих обстоятельств.238.

Управление процессамиТеперь рассмотрим более тонкие методы повышения эффективности и результативностивычислений:••замедленные вычислениярецепты вычисленияЗамедленные вычисления (lazy evaluation)Интуитивное представление о вычислении выражений, согласно которому функцияприменяется к заранее вычисленным аргументам, не всегда гарантирует получениерезультата. Ради полноты вычислений, гибкости программ и результативности процессовтакое представление можно расширить и ввести категорию специальных функций, которые"сами знают", когда и что из их аргументов следует вычислить.

Примеры таких функций специальные функции QUOTE и COND, которые могут анализировать и варьироватьусловия, при которых вычисление необходимо. Такие функции манипулируют данными,представляющими выражения, и явно определяют в программах позиции обращения кинтерпретатору.Источником неэффективности стандартных “прямолинейных” вычислений может бытьцелостность больших сложных данных, избыточное вычисление бесполезных выражений,синхронизация формально независимых действий.

Такую неэффективность можно смягчитьпростыми методами замедленных вычислений (lazy evaluation). Необходимо лишь вестиучет дополнительных условий для их фактического выполнения, таких как востребованностьрезультата вычислений. Такие соображения по обработке параметров функций называют“вызов по необходимости”.Любое большое сложное данное можно вычислять "по частям". Вместо вычислениясписка(x1 x2 x3 ... )можно вычислить x1 и построить структуру(x1 (рецепт вычисления остальных элементов))Получается принципиальная экономия памяти ценой незначительного расхода времени навспомогательное построение.

Рецепт - это ссылка на уже существующую программу,связанную с контекстом ее исполнения, т.е. с состоянием ассоциативного списка в моментпостроения рецепта.24Пример: Построение ряда целых от M до N с последующим их суммированием. Обычнаяформула:(defun ряд_цел (M N) (cond ((> M N) Nil)(T(cons M (ряд_цел (1+ M) N)))))(defun сумма (X) (cond ((= X 0) 0)(T (+ (car X)( сумма (cdr X))))) )Введем специальные операции || - приостановка вычислений и @ - возобновление ранееотложенных вычислений. Приостановка сводится к запоминанию символьногопредставления программы, которая временно не вычисляется, но можно вернуться к еевычислению с помощью операции возобновления.

Отложенная программа преобразуется втак называемый рецепт вычисления, который можно хранить как данное и выполнять влюбой момент.В рецепте хранится не только вычисляемая форма, но и контекст, в котором первоначальнобыло предусмотрено ее вычисление. Таким образом, гарантируется, что переход от обычнойпрограммы к программе с отложенными действиями не нарушает общий результат.Избежать целостного представления большого и возможно бесконечного ряда чисел можнонебольшим изменением формулы, отложив вычисление второго аргумента CONS “до лучшихвремен” – когда его значение действительно понадобится более внешней функции:(defun ряд_цел (M N) (cond ((> M N) Nil)(T(cons M ( || (ряд_цел (1+ M) N))))))(defun сумма (X) (cond ((= X 0) 0)(T (+ (car X)( @ ( сумма (cdr X))))) ))Можно исключить повторное вычисление совпадающих рецептов. Для этого вовнутренне представление рецепта вводится флаг, имеющий значение T - истина для ужевыполненных рецептов, Nil - ложь для невыполненных.Таким образом рецепт имеет вид (Nil e AL ) или ( T X ), где X = (eval e AL ) дляпроизвольного e, в зависимости от того, понадобилось ли уже значение рецепта или еще небыло в нем необходимости.Это заодно дает возможность понятие данных распространить на бесконечныемножества.

Например, можно манипулировать рядом целых, превосходящих M с помощьюфункции:(defun цел (M) (cons M ( || (цел (1+ M) ))))25Можно из таким образом организованного списка выбирать нужное количество элементов,например, первые K элементов можно получить по формуле:(defun первые (K Int) (cond ((= Int Nil) Nil)((= K 0) Nil)(T (cons (car Int)( первые ( @ (cdr Int))) )) ))Формально эффект таких приостанавливаемых и возобновляемых вычисленийполучается следующей реализацией операций || и @:||e = > (lambda () e )@e = > (e ),что при интерпретации дает связывание функционального аргумента с ассоциативнымсписком для операции || - приостановка и вызов функции EVAL для операции @ возобновление вычислений.Обычно в языках программирования различают вызовы по значению, по имени, по ссылке.Техника приостановки и возобновления функций может быть названа вызовом понеобходимости.При небольшом числе значений заданного типа, например, для истиностных значений,возможны вычисления с вариантами значений с последующим выбором реальнойальтернативы пользователем, но это удобнее обсудить позднее, при изучении вариантов инедетерминированных вычислений.Техника замедленных вычислений позволяет выполнять декомпозицию программы наобязательно выполнимые и возможно невыполнимые действия.

Выполнимые действия втексте определения замещаются на их результат, а невыполнимые преобразуются востаточные, которые будут выполнены по мере появления дополнительной информации.Многие выражения по смыслу используемых в них операций иногда определены причастичной определенности их операндов, что часто используется при оптимизации кодапрограмм (умножение на 0, разность или частное от деления совпадающих форм и т.п.)Отложенные действия - естественный механизм программирования асинхронных ипараллельных процессов.Выводы:-Замедленные вычисления могут быть результативнее обычных.Хранимые вместе с данными рецепты их вычислений позволяют работать сбесконечными множествами.26-В ряде случаев возможно получение полного результата при неопределенных значенияхчастей.279.Традиционное (стандартное) программирование-Императивное программированиеСписки свойств атомаСтруктуры данных и памятиДеструктивные операцииСвободная память и мусорщикФорма “Prog” и циклыПротивопоставление функционального и императивного (операторно-процедурного)стилей программирования порой напоминает свифтовские бои остроконечников ступоконечниками.

Впрочем, переписать функциональную программу в императивнуюпроще, чем наоборот.С практической точки зрения любые конструкции стандартных языков программированиямогут быть введены как функции. Это делает их вполне легальными средствами в рамкахфункционального подхода. Надо лишь четко уяснить цену такого дополнения и егопреимущества, обычно связанные с наследованием решений или с привлечениемпользователей.

В первых реализациях Лиспа были сразу предложены специальные формы иструктуры данных, служащие мостом между разными стилями программирования. Онизаодно смягчали на практике недостатки упрощенной схемы интерпретации С-выражений,выстроенной для учебных и исследовательских целей. Важнейшие средства такого рода,выдержавшее испытание временем, - prog-форма, списки свойств атома и деструктивныеоперации. В результате язык программирования расширяется так, что становятсявозможными оптимизирующие преобразования структур данных, программ и процессов ираскрутка систем программирования.Рассмотрим предложенный МакКарти пример, показывающий возможности prog-формыпри императивном стиле определения функции Length.