Основы функционального программирования

Реализационные решения

Разбить на страницы
Показывать лекцию целиком

Сборка системы и ее рабочий цикл

Моделирование Лиспа или другого языка программирования на идеальном базовом Лиспе вполне может послужить иллюстрацией определения операционной семантики языков программирования .

Традиционно система программирования для языка Лисп содержит пару интерпретатор-компилятор. Между этими понятиями трудно установить формальную границу. Любой интерпретатор содержит элементы, реализация которых описывается в машинных терминах: структура памяти, реализация двоичных деревьев и т. п. Любая компилированная программа содержит интерпретируемые элементы: например, обращения к файловой системе и другим элементам ОС. На практике достоинства интерпретации проявляются при отладке программ, а преимущества компиляции — при эксплуатации готового программного продукта. Более подробное обсуждение этой темы заслуживает отдельного разговора.

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

Ядро интерпретатора языка Лисп может быть реализовано следующим образом:

  • выбирается реализация списков в виде бинарных деревьев, листья которого рассматриваются как атомы, а узлы используются для выстраивания списков (левые ветви — элементы списка, правые — продолжение списка или конец списка, т.е. пустой список);
  • выбирается реализация атомов как объектов, внутренняя структура которых при определении и исполнении функций не всегда существенна, но при необходимости доступна специальным операциям;
  • встраивается специальный атом NIL, являющийся реализацией пустого списка () ;
  • встраивается операция, связывающая различные данные с атомами, и ассоциируется с атомом LABEL ;
  • определяются правила доступа к параметрам встроенных операций с размещением их результата и встраивается специальная операция (монитор), выполняющая применение операций к правильно размещенным аргументам ( SUBR );
  • встраивается операция, строящая из атомов и списков более сложные структуры (списки и узлы из любых элементов), и ассоциируется с атомом CONS ;
  • встраиваются операции, выполняющие разбор и анализ структур, и ассоциируются с атомами CAR, CDR, ATOM, EQ, представляющими эти операции;
  • встраиваются специальные операции (псевдо-функции), выполняющие блокировку вычислений, выбор ветви и конструирование определений функций, и ассоциируются с атомами QUOTE, COND и LAMBDA, соответственно;
  • универсальная функция ассоциируется с EVAL ;
  • определяется рабочий цикл передачи данных интерпретатору и вывода результата интерпретации.
    •

    Такое ядро представляет собой машинно-зависимую часть Лисп-интерпретатора. Встраивание операции в ядро системы — это включение в его реализацию исполнимого кода, который является реализацией этой операции. Адрес такого кода ассоциируется с именем атома, с помощью которого будет организовано выполнение операции при интерпретации программ.

    При ассоциировании атомов с произвольной информацией можно использовать специально организованный ассоциативный список, построенный из пар, содержащих атомы и их определения. Например, ассоциативный список

    ((T . T )(NIL . NIL))

    обеспечивает значение T и NIL в соответствии с семантикой базового Лиспа, список

    ((ОДИН . 1)(ДВА . 2))

    дает символьные имена числовым значениям, а список

    ((ГОЛОВА . CAR)(ХВОСТ . CDR)(УЗЕЛ . CONS))

    — синонимы для обозначения базовых операций Лиспа.

    Ассоциативный список работает как стек: при многократных определениях доступно самое новое, т.е. расположенное ближе к началу списка. Если мы знаем адреса кода операций, встроенных в ядро системы, то можем соответствие между именами операций и адресами их кода хранить в ассоциативном списке. Можно считать, что начальное состояние ассоциативного списка содержит таблицу соответствия между именами и адресами операций.

    Основой определения интерпретатора является функция EVAL (evaluation), вычисляющая произвольные выражения языка с учетом состояния ассоциативного списка AL. Спецификация такой функции для базового Лиспа может быть проиллюстрирована следующими примерами:

    (EVAL NIL AL )     ; = NIL
    (EVAL T AL )        ; = T
    (EVAL 'X AL )       ; = (CADR (ASSOC X AL)) 
    (EVAL '(QOUTE EXPR ) AL )          ; = EXPR 
    (EVAL '(COND ((T YES) ... )) AL )  ; = YES
    (EVAL '(SETQ X Y ) AL )
                 ; = (CDAR(CONS (CONS 'X (EVAL Y )) AL))
    (EVAL '(CAR A) '((A 1 2 3)(NIL NIL)) )  ; = 1

    В других случаях выражения получают значение в результате применения некоторой функции, стоящей в голове списка, к ее аргументам, что выполняется другой важной частью определения интерпретатора — функцией APPLY. Для ее работы необходима функция, вычисляющая значения аргументов с учетом состояния ассоциативного списка.

    При написании на базовом Лиспе определения функции EVAL согласно приведенной выше спецификации, способной от данного списочного представления выражения E перейти к его значению с учетом заданного ассоциативного списка AL, хранящего значения атомов, мы несколько отступаем от ранее данных определений, с тем чтобы более явно выделить линии сборки системы.

    (DEFUN EVAL (e al )
       (COND 
          ((MEMBER e '(NIL T )) e ) 
          ((ATOM e ) ((LAMBDA (v )
             (COND (v (CADR v ) ) 
                        (T (ERROR ''undefined_value  )) 
             ))
             (ASSOC e al ) 
       )   ) 
       ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) )
       ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) 
       ((EQ (CAR e) 'LET )
         (EVAL (CADDDR e )
             (CONS (CONS (CADR e )
                (CONS (EVAL (CADDR e ) al ) NIL) ) al )
       ))
       (T (APPLY (CAR e) (EVLIS (CDR e) al ) al ) )
    ))

    В этом функциональном значении используется имя функции APPLY, применяющей произвольную функцию к ее аргументам при заданном ассоциативном списке. ERROR — псевдо-функция, выдающая заданные диагностические сообщения.

    Определение функции APPLY работает при условии, что функция SUBR осуществляет применение встроенных функций к их аргументам, заданным в виде списка значений.

    (DEFUN APPLY (fn args al )
       (COND
          ((MEMBER fn '(CAR CDR CONS ATOM EQ ))
             (SUBR (CADR (ASSOC fn al)) args ))
          ((EQ fn NIL) NIL) 
          ((ATOM fn ) (APPLY (EVAL fn al ) args al ))
          ((EQ (CAR fn ) 'LAMBDA )
             (EVAL (CADDR fn )
                 (APPEND (PAIR (CADR fn ) args ) al ) 
          )  )
          ((EQ (CAR fn) 'LABEL ) 
                 (APPLY (CADDR fn) args
                            (CONS (CDR fn ) al )
          )      ) 
         (T (ERROR- 'undefined_function)) 
    )  )

    Обратите внимание, что в EVAL при поиске атома в ассоциативном списке мы допускаем отсутствие ассоциированного с атомом значения и сообщаем об этом диагностикой с помощью функции ERROR. В APPLY же при выборе адреса встроенной функции мы рассчитываем, что все известные функции реализованы, и их адреса размещены в ассоциативном списке — за правильность выбора имен встроенных функций отвечает программист.

    Можно еще поработать с таким определением интерпретатора и более четко локализовать его зависимость от четырех различных категорий объектов: самоопределяемые атомы — (NIL T 1 2 3 ... ), базовые операции над данными языка, обрабатывающие предварительно вычисленные аргументы, — (CAR CDR CONS ATOM EQ ... ), специальные функции, управляющие обработкой аргументов без их предварительного вычисления, — (QUOTE COND LET ...) и конструкторы функций, строящие функциональные значения из обычных выражений, — (LAMBDA LABEL... ).

    Желающие могут поэкспериментировать с самодельным интерпретатором, превращая его в модель ядра любого языка программирования, используя какую-нибудь Лисп-систему, например GNU Clisp (с точностью до имен отдельных функций).

    Упражнение 9.1. Пусть READ и PRINT — встроенные функции, обеспечивающие прием с клавиатуры и вывод на экран произвольных данных языка Лисп. Напишите определение рабочего цикла интерпретации последовательности выражений.

    Ответ.

    (DEFINE CIRCLE (al ) (PRINT (EVAL (PRINT (READ )) 
       al ))
       (CIRCLE al ) )

    "Но оно же зациклится!" — скажете вы и будете правы.

    Но это не помешает эксперименту, ведь в нашем распоряжении имеется конец файла Ctrl-Z или встроенная операция завершения процесса типа BYE, EXEC, SYSTEM либо что-то подобное.

    Упражнение 9.2. Полученные 50 строк определения Лисп-интерпретатора и его вспомогательных функций содержит 1263 символа, если не считать пробелы в начале строк. Попробуйте написать сравнимое определение на каком-нибудь знакомом вам языке программирования.

    Реализация динамической памяти и структур данных

    После обсуждения схемы функционирования Лисп-интерпретатора и его сборки из машинно-зависимого конструктива пришло время поговорить о структурах данных, используемых при реализации списков и атомов.

    Обычно при обработке программ в памяти располагаются разносортные результаты, возникающие при разборе и анализе текста программы и ее данных, при построении ее внутреннего кода и при формировании результата. В Лисп-системах традиционно при всех этих видах работ принято придерживаться принципов логики здравого смысла:

  • новые значения строятся на новом месте,
  • предпочитаются интересы малых программ,
  • автоматизируется повторное использования памяти, что на первых шагах разработки освобождает программиста от необходимость уделять внимание вторичным проблемам распределения памяти.
    •

    Кроме того, почти исключается необходимость присваиваний, они в программах заменяются именованием.

    Память обычно распределена по блокам, содержащим ряд слов, образующих структуры данных. Физический объем памяти, логическая длина данных и состав информации, полезной для продолжения вычислений, могут существенно различаться. Минимальные потери в результативности работы с памятью дает динамическая обработка бинарных деревьев — нет простоев из-за незаполненности части полей. Каждый узел такого дерева имеет небольшой объем, достаточный для хранения двух типизированных указателей ( CAR и CDR, левый и правый). Типизация указателей нужна для динамического контроля соответствия данных и операций по их обработке. NIL, атомы, списки, числа, строки — все это реализационно различимые типы данных. (Утверждение о бестиповости Лиспа имеет отношение лишь к отсутствию статического связывания в тексте программы имен переменных с типами их значений. Для компиляции приходится дополнять Лисп-программы сведениями о типах значений свободных переменных, но далеко не каждая программа доживает до компиляции.) Лиспу свойственна функциональная классификация значимых типов данных, т.е. именно реализационно различимых.

    Реализация бинарных деревьев или односвязных списков описана в классических курсах по программированию, а реализацию атомов мы рассмотрим подробнее. Эффективность приведенного выше определения интерпретатора с использованием ассоциативного списка существенно зависит от числа различимых атомов в программе. Такая зависимость обычно смягчается механизмом функций расстановки (хэш-функций), обеспечивающим доступ к информации по ключу. В качестве ключа используется имя атома. В результате вся связанная с атомом уникальная информация становится легко и быстро достижимой. Структура такой информации называется списком свойств атома. Она представляет собой чередование так называемых "индикаторов" и "значений" свойств. Число свойств атома не ограничено. Свойства бывают встроенные, системные или вводимые программистом. Значения атомов, адреса встроенных операций, определяющие выражения функций — примеры встроенных свойств. Встроенные операции типа LET, LABELS в системе Clisp обычно используют списки свойств. Обработка таблицы, связывающей атомы и их списки свойств, как правило, зависит от реализации. Методы задания и изменения свойств работают подобно обычным присваиваниям. Псевдо-функция PUT задает индикатор и соответствующее ему новое значение свойства атома, а функция GET обеспечивает доступ к свойству атома, соответствующему заданному индикатору. Теперь с помощью списков свойств мы могли бы добиться точного соответствия семантики констант и определений функций их спецификации в базовом Лиспе, но не будем отвлекаться на это.

    Самым интересным, можно сказать революционным, механизмом работы с памятью в Лиспе, бесспорно, стала "сборка мусора". С начала 1960-х годов методам такой работы посвящены многочисленные исследования, которые продолжаются до наших дней и сильно активизировались в связи с включением похожего механизма в реализацию языка Java.

    Общая идея всех таких методов достаточно проста:

  • пока памяти хватает, о ней можно не беспокоиться и располагать новые данные в новых блоках памяти;
  • если памяти вдруг не оказалось, то надо выполнить "сборку мусора", в процессе которой, возможно, найдутся ставшие бесполезными для программы блоки;
  • если память нашлась, ее снова можно тратить.
    •

    Специальная программа "Сборщик мусора" выполняет анализ достижимости всех блоков памяти просто пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков, но они обнаруживаются лишь в сравнительно сложных процессах, требования которых мы сейчас не учитываем.

    Обычно с машиной связывается представление о блоках информации фиксированного объема, таких как слова, байты, регистры. Функциональное программирование нацелено на более крупные построения — структуры данных не ограниченной заранее длины. Такие структуры достаточно эффективно реализуются посредством специального стека, приспособленного к обработке произвольного числа компонентов текущего уровня иерархической структуры данных.

    От обычного стека он отличается выделением указателя на конец текущего уровня.

    При переходе на новый внутренний уровень Кон_тек_ур записывается в стек, Нач_стека переписывается в Кон_тек_ур, а адрес новой вершины стека становится значением Нач_стека.

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

    Значительный резерв производительности функциональных программ дают деструктивные функции, являющиеся формальными аналогами чистых функций:

    Соответствие строгих функций и их деструктивных аналогов.
    APPEND NCONC
    SUBST NSUBST
    REMOVE DELETE
    REVERSE NREVERSE
    UNION NUNION

    Реальный состав системы и внешний мир

    Реальный состав системы и возможности ее компонентов можно исследовать с помощью специальных функций, предоставляющих информацию о включенных в систему объектах и их свойствах.

    Состав системы:

    (APROPOS 'nm 'package) — печатает информацию обо всех символах, имена которых содержат подстроку " nm ". Второй аргумент, если он указан, ограничивает эту информации заданным пакетом.

    (DESCRIBE 'fn ) — дает описание места объекта в системе.

    (SYMBOL-PLIST 'fn) — выдает перечень всех свойств объекта.

    (DOCUMENTATION 'fn 'function) — выдает документацию по объекту.

    Отладка программ:

    (DRIBBLE 'file) — направляет в файл протокол работы с Лисп-интерпретатором.

    (STEP expr) — обеспечивает пошаговый режим интерпретации выражения с выдачей результатов каждого шага.

    Ввод-вывод данных:

    (SETQ inpt (OPEN file-in :direction :input )) — заведение переменной для обозначения открытого потока.

    (READ inpt) — чтение из файла, открытого как поток.

    (PRINT (PRINT eval-val prtcl) outpt) — запись данного eval-val в два разных файла.

    (OPEN file-in :direction :input ) — открытие файла на чтение.

    Далее следуют три варианта открытия файлов на запись:

    (OPEN "output" :direction :output :if-exists 
		:rename :if-does-not-exist :create)
    (OPEN "protocol" :direction :output :if-exists 
		:overwrite :if-does-not-exist :create)
    (OPEN "history" :direction :output :if-exists 
		:append :if-does-not-exist :create )
    (CLOSE prtcl) — закрытие потока.

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

    (DEFUN eval-protocol () (PROG (eval-val)
    ; выражения хранятся в файле "input.lsp"
 
    metka
       (PRINT '> prtcl)
       (SETQ eval-val (EVAL
          (list 'STEP ; пошаговое вычисление выражения
          (PRINT (PRINT
             ( if (eq 'eof (setq rinpt
                   (READ inpt NIL 'eof) ))
                (return(CLOSE inpt))
                rinpt)
       prtcl) hstry)
    )))
 
    ; прочитанное записывается в файлы "protocol" и 
    ; "history"
    (PRINT '- prtcl)
    ;(print eval-val)
    (print (print eval-val
                prtcl) outpt)
    ; результат интерпретации в файлах 
    ; "protocol" и "output"
    (go metka)
    ))
 
    (DEFUN help ( function-name )
    (ed (string function-name )) )
 
    (DEFUN step1 (file-in)
    (PROG ()
 
          (SETQ inpt (OPEN file-in :direction :input ))
       (SETQ outpt (OPEN "output" :direction :output 
    :if-exists :rename
    :if-does-not-exist :create))
    (SETQ prtcl (OPEN "protocol" :direction :output 
    :if-exists :overwrite
    :if-does-not-exist :create))
    (SETQ hstry (OPEN "history" :direction :output 
    :if-exists :append
    :if-does-not-exist :create ))
    (PRINT '"****** new-session ******" hstry)
 
    ; цикл прервется по достижении конца файла ввода
    (eval-protocol)
 
    (CLOSE prtcl)
    (CLOSE hstry)
    (CLOSE outpt)
    ))
 
    (step1 "input.lsp")
    ; интерпретируемые выражения хранятся в файле 
    ; "input.lsp"
    Страницы:

    Сборка системы и ее рабочий цикл

    Моделирование Лиспа или другого языка программирования на идеальном базовом Лиспе вполне может послужить иллюстрацией определения операционной семантики языков программирования .

    Традиционно система программирования для языка Лисп содержит пару интерпретатор-компилятор. Между этими понятиями трудно установить формальную границу. Любой интерпретатор содержит элементы, реализация которых описывается в машинных терминах: структура памяти, реализация двоичных деревьев и т. п. Любая компилированная программа содержит интерпретируемые элементы: например, обращения к файловой системе и другим элементам ОС. На практике достоинства интерпретации проявляются при отладке программ, а преимущества компиляции — при эксплуатации готового программного продукта. Более подробное обсуждение этой темы заслуживает отдельного разговора.

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

    Ядро интерпретатора языка Лисп может быть реализовано следующим образом:

  • выбирается реализация списков в виде бинарных деревьев, листья которого рассматриваются как атомы, а узлы используются для выстраивания списков (левые ветви — элементы списка, правые — продолжение списка или конец списка, т.е. пустой список);
  • выбирается реализация атомов как объектов, внутренняя структура которых при определении и исполнении функций не всегда существенна, но при необходимости доступна специальным операциям;
  • встраивается специальный атом NIL, являющийся реализацией пустого списка () ;
  • встраивается операция, связывающая различные данные с атомами, и ассоциируется с атомом LABEL ;
  • определяются правила доступа к параметрам встроенных операций с размещением их результата и встраивается специальная операция (монитор), выполняющая применение операций к правильно размещенным аргументам ( SUBR );
  • встраивается операция, строящая из атомов и списков более сложные структуры (списки и узлы из любых элементов), и ассоциируется с атомом CONS ;
  • встраиваются операции, выполняющие разбор и анализ структур, и ассоциируются с атомами CAR, CDR, ATOM, EQ, представляющими эти операции;
  • встраиваются специальные операции (псевдо-функции), выполняющие блокировку вычислений, выбор ветви и конструирование определений функций, и ассоциируются с атомами QUOTE, COND и LAMBDA, соответственно;
  • универсальная функция ассоциируется с EVAL ;
  • определяется рабочий цикл передачи данных интерпретатору и вывода результата интерпретации.
    •

    Такое ядро представляет собой машинно-зависимую часть Лисп-интерпретатора. Встраивание операции в ядро системы — это включение в его реализацию исполнимого кода, который является реализацией этой операции. Адрес такого кода ассоциируется с именем атома, с помощью которого будет организовано выполнение операции при интерпретации программ.

    При ассоциировании атомов с произвольной информацией можно использовать специально организованный ассоциативный список, построенный из пар, содержащих атомы и их определения. Например, ассоциативный список

    ((T . T )(NIL . NIL))

    обеспечивает значение T и NIL в соответствии с семантикой базового Лиспа, список

    ((ОДИН . 1)(ДВА . 2))

    дает символьные имена числовым значениям, а список

    ((ГОЛОВА . CAR)(ХВОСТ . CDR)(УЗЕЛ . CONS))

    — синонимы для обозначения базовых операций Лиспа.

    Ассоциативный список работает как стек: при многократных определениях доступно самое новое, т.е. расположенное ближе к началу списка. Если мы знаем адреса кода операций, встроенных в ядро системы, то можем соответствие между именами операций и адресами их кода хранить в ассоциативном списке. Можно считать, что начальное состояние ассоциативного списка содержит таблицу соответствия между именами и адресами операций.

    Основой определения интерпретатора является функция EVAL (evaluation), вычисляющая произвольные выражения языка с учетом состояния ассоциативного списка AL. Спецификация такой функции для базового Лиспа может быть проиллюстрирована следующими примерами:

    (EVAL NIL AL )     ; = NIL
    (EVAL T AL )        ; = T
    (EVAL 'X AL )       ; = (CADR (ASSOC X AL)) 
    (EVAL '(QOUTE EXPR ) AL )          ; = EXPR 
    (EVAL '(COND ((T YES) ... )) AL )  ; = YES
    (EVAL '(SETQ X Y ) AL )
                 ; = (CDAR(CONS (CONS 'X (EVAL Y )) AL))
    (EVAL '(CAR A) '((A 1 2 3)(NIL NIL)) )  ; = 1

    В других случаях выражения получают значение в результате применения некоторой функции, стоящей в голове списка, к ее аргументам, что выполняется другой важной частью определения интерпретатора — функцией APPLY. Для ее работы необходима функция, вычисляющая значения аргументов с учетом состояния ассоциативного списка.

    При написании на базовом Лиспе определения функции EVAL согласно приведенной выше спецификации, способной от данного списочного представления выражения E перейти к его значению с учетом заданного ассоциативного списка AL, хранящего значения атомов, мы несколько отступаем от ранее данных определений, с тем чтобы более явно выделить линии сборки системы.

    (DEFUN EVAL (e al )
       (COND 
          ((MEMBER e '(NIL T )) e ) 
          ((ATOM e ) ((LAMBDA (v )
             (COND (v (CADR v ) ) 
                        (T (ERROR ''undefined_value  )) 
             ))
             (ASSOC e al ) 
       )   ) 
       ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) )
       ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) 
       ((EQ (CAR e) 'LET )
         (EVAL (CADDDR e )
             (CONS (CONS (CADR e )
                (CONS (EVAL (CADDR e ) al ) NIL) ) al )
       ))
       (T (APPLY (CAR e) (EVLIS (CDR e) al ) al ) )
    ))

    В этом функциональном значении используется имя функции APPLY, применяющей произвольную функцию к ее аргументам при заданном ассоциативном списке. ERROR — псевдо-функция, выдающая заданные диагностические сообщения.

    Определение функции APPLY работает при условии, что функция SUBR осуществляет применение встроенных функций к их аргументам, заданным в виде списка значений.

    (DEFUN APPLY (fn args al )
       (COND
          ((MEMBER fn '(CAR CDR CONS ATOM EQ ))
             (SUBR (CADR (ASSOC fn al)) args ))
          ((EQ fn NIL) NIL) 
          ((ATOM fn ) (APPLY (EVAL fn al ) args al ))
          ((EQ (CAR fn ) 'LAMBDA )
             (EVAL (CADDR fn )
                 (APPEND (PAIR (CADR fn ) args ) al ) 
          )  )
          ((EQ (CAR fn) 'LABEL ) 
                 (APPLY (CADDR fn) args
                            (CONS (CDR fn ) al )
          )      ) 
         (T (ERROR- 'undefined_function)) 
    )  )

    Обратите внимание, что в EVAL при поиске атома в ассоциативном списке мы допускаем отсутствие ассоциированного с атомом значения и сообщаем об этом диагностикой с помощью функции ERROR. В APPLY же при выборе адреса встроенной функции мы рассчитываем, что все известные функции реализованы, и их адреса размещены в ассоциативном списке — за правильность выбора имен встроенных функций отвечает программист.

    Можно еще поработать с таким определением интерпретатора и более четко локализовать его зависимость от четырех различных категорий объектов: самоопределяемые атомы — (NIL T 1 2 3 ... ), базовые операции над данными языка, обрабатывающие предварительно вычисленные аргументы, — (CAR CDR CONS ATOM EQ ... ), специальные функции, управляющие обработкой аргументов без их предварительного вычисления, — (QUOTE COND LET ...) и конструкторы функций, строящие функциональные значения из обычных выражений, — (LAMBDA LABEL... ).

    Желающие могут поэкспериментировать с самодельным интерпретатором, превращая его в модель ядра любого языка программирования, используя какую-нибудь Лисп-систему, например GNU Clisp (с точностью до имен отдельных функций).

    Упражнение 9.1. Пусть READ и PRINT — встроенные функции, обеспечивающие прием с клавиатуры и вывод на экран произвольных данных языка Лисп. Напишите определение рабочего цикла интерпретации последовательности выражений.

    Ответ.

    (DEFINE CIRCLE (al ) (PRINT (EVAL (PRINT (READ )) 
       al ))
       (CIRCLE al ) )

    "Но оно же зациклится!" — скажете вы и будете правы.

    Но это не помешает эксперименту, ведь в нашем распоряжении имеется конец файла Ctrl-Z или встроенная операция завершения процесса типа BYE, EXEC, SYSTEM либо что-то подобное.

    Упражнение 9.2. Полученные 50 строк определения Лисп-интерпретатора и его вспомогательных функций содержит 1263 символа, если не считать пробелы в начале строк. Попробуйте написать сравнимое определение на каком-нибудь знакомом вам языке программирования.

    Реализация динамической памяти и структур данных

    После обсуждения схемы функционирования Лисп-интерпретатора и его сборки из машинно-зависимого конструктива пришло время поговорить о структурах данных, используемых при реализации списков и атомов.

    Обычно при обработке программ в памяти располагаются разносортные результаты, возникающие при разборе и анализе текста программы и ее данных, при построении ее внутреннего кода и при формировании результата. В Лисп-системах традиционно при всех этих видах работ принято придерживаться принципов логики здравого смысла:

  • новые значения строятся на новом месте,
  • предпочитаются интересы малых программ,
  • автоматизируется повторное использования памяти, что на первых шагах разработки освобождает программиста от необходимость уделять внимание вторичным проблемам распределения памяти.
    •

    Кроме того, почти исключается необходимость присваиваний, они в программах заменяются именованием.

    Память обычно распределена по блокам, содержащим ряд слов, образующих структуры данных. Физический объем памяти, логическая длина данных и состав информации, полезной для продолжения вычислений, могут существенно различаться. Минимальные потери в результативности работы с памятью дает динамическая обработка бинарных деревьев — нет простоев из-за незаполненности части полей. Каждый узел такого дерева имеет небольшой объем, достаточный для хранения двух типизированных указателей ( CAR и CDR, левый и правый). Типизация указателей нужна для динамического контроля соответствия данных и операций по их обработке. NIL, атомы, списки, числа, строки — все это реализационно различимые типы данных. (Утверждение о бестиповости Лиспа имеет отношение лишь к отсутствию статического связывания в тексте программы имен переменных с типами их значений. Для компиляции приходится дополнять Лисп-программы сведениями о типах значений свободных переменных, но далеко не каждая программа доживает до компиляции.) Лиспу свойственна функциональная классификация значимых типов данных, т.е. именно реализационно различимых.

    Реализация бинарных деревьев или односвязных списков описана в классических курсах по программированию, а реализацию атомов мы рассмотрим подробнее. Эффективность приведенного выше определения интерпретатора с использованием ассоциативного списка существенно зависит от числа различимых атомов в программе. Такая зависимость обычно смягчается механизмом функций расстановки (хэш-функций), обеспечивающим доступ к информации по ключу. В качестве ключа используется имя атома. В результате вся связанная с атомом уникальная информация становится легко и быстро достижимой. Структура такой информации называется списком свойств атома. Она представляет собой чередование так называемых "индикаторов" и "значений" свойств. Число свойств атома не ограничено. Свойства бывают встроенные, системные или вводимые программистом. Значения атомов, адреса встроенных операций, определяющие выражения функций — примеры встроенных свойств. Встроенные операции типа LET, LABELS в системе Clisp обычно используют списки свойств. Обработка таблицы, связывающей атомы и их списки свойств, как правило, зависит от реализации. Методы задания и изменения свойств работают подобно обычным присваиваниям. Псевдо-функция PUT задает индикатор и соответствующее ему новое значение свойства атома, а функция GET обеспечивает доступ к свойству атома, соответствующему заданному индикатору. Теперь с помощью списков свойств мы могли бы добиться точного соответствия семантики констант и определений функций их спецификации в базовом Лиспе, но не будем отвлекаться на это.

    Самым интересным, можно сказать революционным, механизмом работы с памятью в Лиспе, бесспорно, стала "сборка мусора". С начала 1960-х годов методам такой работы посвящены многочисленные исследования, которые продолжаются до наших дней и сильно активизировались в связи с включением похожего механизма в реализацию языка Java.

    Общая идея всех таких методов достаточно проста:

  • пока памяти хватает, о ней можно не беспокоиться и располагать новые данные в новых блоках памяти;
  • если памяти вдруг не оказалось, то надо выполнить "сборку мусора", в процессе которой, возможно, найдутся ставшие бесполезными для программы блоки;
  • если память нашлась, ее снова можно тратить.
    •

    Специальная программа "Сборщик мусора" выполняет анализ достижимости всех блоков памяти просто пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков, но они обнаруживаются лишь в сравнительно сложных процессах, требования которых мы сейчас не учитываем.

    Обычно с машиной связывается представление о блоках информации фиксированного объема, таких как слова, байты, регистры. Функциональное программирование нацелено на более крупные построения — структуры данных не ограниченной заранее длины. Такие структуры достаточно эффективно реализуются посредством специального стека, приспособленного к обработке произвольного числа компонентов текущего уровня иерархической структуры данных.

    От обычного стека он отличается выделением указателя на конец текущего уровня.

    При переходе на новый внутренний уровень Кон_тек_ур записывается в стек, Нач_стека переписывается в Кон_тек_ур, а адрес новой вершины стека становится значением Нач_стека.

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

    Значительный резерв производительности функциональных программ дают деструктивные функции, являющиеся формальными аналогами чистых функций:

    Соответствие строгих функций и их деструктивных аналогов.
    APPEND NCONC
    SUBST NSUBST
    REMOVE DELETE
    REVERSE NREVERSE
    UNION NUNION

    Реальный состав системы и внешний мир

    Реальный состав системы и возможности ее компонентов можно исследовать с помощью специальных функций, предоставляющих информацию о включенных в систему объектах и их свойствах.

    Состав системы:

    (APROPOS 'nm 'package) — печатает информацию обо всех символах, имена которых содержат подстроку " nm ". Второй аргумент, если он указан, ограничивает эту информации заданным пакетом.

    (DESCRIBE 'fn ) — дает описание места объекта в системе.

    (SYMBOL-PLIST 'fn) — выдает перечень всех свойств объекта.

    (DOCUMENTATION 'fn 'function) — выдает документацию по объекту.

    Отладка программ:

    (DRIBBLE 'file) — направляет в файл протокол работы с Лисп-интерпретатором.

    (STEP expr) — обеспечивает пошаговый режим интерпретации выражения с выдачей результатов каждого шага.

    Ввод-вывод данных:

    (SETQ inpt (OPEN file-in :direction :input )) — заведение переменной для обозначения открытого потока.

    (READ inpt) — чтение из файла, открытого как поток.

    (PRINT (PRINT eval-val prtcl) outpt) — запись данного eval-val в два разных файла.

    (OPEN file-in :direction :input ) — открытие файла на чтение.

    Далее следуют три варианта открытия файлов на запись:

    (OPEN "output" :direction :output :if-exists 
		:rename :if-does-not-exist :create)
    (OPEN "protocol" :direction :output :if-exists 
		:overwrite :if-does-not-exist :create)
    (OPEN "history" :direction :output :if-exists 
		:append :if-does-not-exist :create )
    (CLOSE prtcl) — закрытие потока.

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

    (DEFUN eval-protocol () (PROG (eval-val)
    ; выражения хранятся в файле "input.lsp"
 
    metka
       (PRINT '> prtcl)
       (SETQ eval-val (EVAL
          (list 'STEP ; пошаговое вычисление выражения
          (PRINT (PRINT
             ( if (eq 'eof (setq rinpt
                   (READ inpt NIL 'eof) ))
                (return(CLOSE inpt))
                rinpt)
       prtcl) hstry)
    )))
 
    ; прочитанное записывается в файлы "protocol" и 
    ; "history"
    (PRINT '- prtcl)
    ;(print eval-val)
    (print (print eval-val
                prtcl) outpt)
    ; результат интерпретации в файлах 
    ; "protocol" и "output"
    (go metka)
    ))
 
    (DEFUN help ( function-name )
    (ed (string function-name )) )
 
    (DEFUN step1 (file-in)
    (PROG ()
 
          (SETQ inpt (OPEN file-in :direction :input ))
       (SETQ outpt (OPEN "output" :direction :output 
    :if-exists :rename
    :if-does-not-exist :create))
    (SETQ prtcl (OPEN "protocol" :direction :output 
    :if-exists :overwrite
    :if-does-not-exist :create))
    (SETQ hstry (OPEN "history" :direction :output 
    :if-exists :append
    :if-does-not-exist :create ))
    (PRINT '"****** new-session ******" hstry)
 
    ; цикл прервется по достижении конца файла ввода
    (eval-protocol)
 
    (CLOSE prtcl)
    (CLOSE hstry)
    (CLOSE outpt)
    ))
 
    (step1 "input.lsp")
    ; интерпретируемые выражения хранятся в файле 
    ; "input.lsp"
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^