globalf5-240972240972 (850810), страница 19
Текст из файла (страница 19)
Этот возврат происходит автоматически при пропускепрограммы, где бы ни исчерпался список свободной памяти.Программа, восстанавливающая память, называется "мусорщик" . Любая124Л.В. ГородняяОсновы функционального программированиячасть структуры списка, доступная программе, рассматривается какактивный список и не затрагивается мусорщиком. Активные спискидоступны программе через некоторые фиксированные наборы базисныхячеек, таких как ячейки списка атомов и ячейки, вмещающие частичныерезультаты Лисп-выражений. Сложные структуры списков могут бытьпроизвольной длины, но каждое активное слово должно бытьподведено к базисной ячейке цепью CAR-CDR.Любая ячейка, не достижимая таким образом, недоступна дляпрограммы и не активна, поэтому ее содержимое не представляетинтереса.
Неактивные, то есть недоступные программе ячейкивосстанавливаются мусорщиком в списке свободной памяти следующимобразом. Во-первых, каждая ячейка, к которой можно получить доступчерез цепь CAR-CDR, метится установлением отрицательного знака.Где бы ни выявилось отрицательное слово в цепи во время процессапометки, мусорщик знает, что остаток раскручиваемого списка содержитуже помеченные ячейки.
Затем мусорщик предпринимает линейноевыметание осовободившегося пространства, собирая ячейки сположительным знаком в новый список свободной памяти ивосстанавливая исходный знак активных ячеек.Иногда структуры списка указывают на полные слова, такие какпечатные имена и числа. Мусорщик не может пометить эти слова,потому что знаковый разряд использован. Мусорщик долженпрекратить работу, потому что указатели, расположенные в адресе идекременте таких слов, бессмысленны.В этом случае проблемы повторного использования памяти решаютсярасположением полных слов в зарезервированной области памяти,называемой областью полных слов. Мусорщик должен прекращатьпрослеживание, как только покидает поле свободной памяти.
Пометка вполе полных слов осуществляется таблицей битов.Такая реализация экономична в отношении памяти, но она имеет ряднеприятных следствий: непредсказуемые длинноты (время работы) припоиске очередной порции ячеек и "перегрев системы", если такиепорции слишком малы для продолжения счета. По мере ростапроизводительности оборудования разработаны простые и не стольобременительные алгоритмы повторного использования памяти на базе125Л.В. ГородняяОсновы функционального программированияпараллельных процессов и профилактического копирования активныхструктур данных в дополнительные блоки памяти. Такие методы нетребуют сложной разметки и анализа достижимости. Содержательнаяаналогия с мастерским мытьем посуды, то есть не допускаяпереполнения раковины, вполне отражает метод stop© принятый всовременных реализациях.Гибкий интерпретаторВ качестве примера повышения гибкости определений приведеноупрощенное определение Лисп-интерпретатора на Лиспе, полученноеиз М-выражения, приведенного Дж.
Маккарти в описании Lisp 1.5 [1].Ради удобочитаемости здесь уменьшена диагностичность, нетпредвычислений и формы Prog. Лисп хорошо приспособлен коптимизации программ. Любые совпадающие подвыражения можнолокализовать и вынести за скобки, как можно заметить по передачезначения"(ASSOC e al )".Определения функций хранятся в ассоциативном списке, как и значенияпеременных.Функция SUBR — вызывает примитивы, реализованные другими,обычно низкоуровневыми, средствами. ERROR — выдает сообщения обошибках и сведения о контексте вычислений, способствующие поискуисточника ошибки.
Уточнена работа с функциональными аргументами:(DEFUN EVAL (e al )(COND((EQ e NIL ) NIL )((ATOM e )((LAMBDA (v )(COND (v (CDR v ) )(T (ERROR 'undefvalue )) )) (ASSOC e al ) ))((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) )126Л.В. ГородняяОсновы функционального программирования((EQ (CAR e) 'FUNCTION )(LIST 'FUNARG (CADR fn ) al ) )((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) )(T (apply (CAR e)(evlis (CDR e) al ) al ) )))(DEFUN APPLY (fn args al )(COND((EQ e NIL ) NIL )((ATOM fn )(COND((MEMBER fn '(CAR CDR CONS ATOM EQ ))(SUBR fn agrs al ))(T (APPLY (EVAL fn al ) args al ))))((EQ (CAR fn ) 'LABEL )(APPLY (CADDR fn )args(CONS (CONS (CADR fn )(CADDR fn ))al ) ) )((EQ (CAR fn ) 'FUNARG )(APPLY (CDR fn ) args (CADDR fn)) )((EQ (CAR fn ) 'LAMBDA )(EVAL (CADDR fn )(APPEND (PAIR (CADR fn ) args ) al ))(T (APPLY (EVAL fn al ) args al ))))Определения ASSOC, APPEND, PAIR, LIST — стандартны.Примерно то же самое обеспечивают EVAL-P и APPLY-P,рассчитанные на использование списков свойств атома для храненияпостоянных значений и функциональных определений.
ИндикаторCATEGORY указывает в списке свойств атома на правилоинтерпретации функций, относящихся к отдельной категории, MACRO— на частный метод построения представления функции. Функция127Л.В. ГородняяОсновы функционального программированияVALUE реализует методы поиска текущего значения переменной взависимости от контекста и свойств атомов.(DEFUN EVAL-P (E C)(COND ((ATOM E) (VALUE E C))((ATOM (CAR E))(COND ((GET (CAR E) 'CATEGORY)((GET (CAR E) 'CATEGORY) (CDR E) C) )(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))))(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))))(DEFUN APPLY-P (F ARGS C)(COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C))((ATOM (CAR F))(COND ((GET (CAR F) 'MACRO)(APPLY-P ((GET (CAR F) 'MACRO)(CDR F) C) ARGS C))(T (APPLY-P (EVAL F E) ARGS C))))(T (APPLY-P (EVAL F E) ARGS C))))Или то же самое с вынесениемвспомогательные параметры:общихподвыражений(DEFUN EVAL-P (E C)(COND ((ATOM E) (VALUE E C))((ATOM (CAR E))((LAMBDA (V) (COND (V (V(CDR E) C) )(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C)))) (GET (CAR E) 'CATEGORY) ) )(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))))(DEFUN APPLY-P (F ARGS C)(COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C))((ATOM (CAR F))128воЛ.В.
ГородняяОсновы функционального программирования((LAMBDA (V) (COND (V (APPLY-P (V (CDR F)C) ARGS C))(T (APPLY-P (EVAL F E) ARGS C))))(GET (CAR F) 'MACRO) ))(T (APPLY-P (EVAL F E) ARGS C))))Расширение системы программирования при таком определенииинтерпретацииосуществляетсяпростымвведением/удалениемсоответствующих свойств атомов и функций.Полученная схема интерпретации допускает разнообразные категориифункций и макросредства конструирования функций, позволяетзадавать различные механизмы передачи параметров функциям.
Так, вязыке Clisp различают, кроме обычных, обязательных и позиционных,—необязательные(факультативные),ключевыеисерийные(многократные, с переменным числом значений) параметры .Виды параметров обозначаются пометкой &OPTIONAL, &KEY и &RESTсоответственно, размещаемой перед параметрами в LAMBDA спискеформальных аргументов. При этом серийный параметр должен бытьпоследним в списке.(DEFUN FUNCALL (FN &REST AGRS) (APPLY FN ARGS))Необязательный параметр может иметь начальное значение,устанавливаемое по умолчанию, т.е. если этот параметр не задан привызове функции. При отсутствии начального значения его роль играетNil.(DEFUN EX-OPT (space &OPTIONAL dot (line 'x))(LIST space 'of dot 'and- line))(EX-OPT 'picture)(EX-OPT 'picture 'circle)(EX-OPT 'picture 'circle 'bars)Пример 6.2.Ключевые параметры, являясь необязательными, не зависят еще и отпорядка вхождения в список аргументов.
Незаданные аргументы поумолчанию связываются с NIL.129Л.В. ГородняяОсновы функционального программирования(DEFUN KEYLIST (A &KEY X Y Z) (LIST A X Y Z))(KEYLIST 1 :Y 2) ;= (1 NIL 2 NIL)(DEFUN LENGTH (L &OPTIONAL (V 0))(COND ((NULL L) V)(T (+ 1 (LENGTH (CDR L))))) )((LENGTH '(1 2) 3);=5(DEFUN REVERSE (L &OPTIONAL (M NIL))(COND ((NULL L) M)(T (REVERSE (CDR L) (CONS (CAR L) M) ))) )(REVERSE '(1 2 3)); = (3 2 1)(REVERSE '(1 2 3) '(5 6)) ;= (3 2 1 5 6)Такой подход к работе параметрами часто освобождает отнеобходимости во вспомогательных функциях, что упрощает иопределение EVAL от обязательности упоминания а-списка.
Есливоспользоваться сводимостью ( COND ) к NIL при отсутствииистиного предиката и кое-где использовать отображения, тоопределение становится совсем компактным.130Л.В. ГородняяОсновы функционального программированияДетализация базовых функцийРассматривается функциональный подход к низкоуровневомупрограммированию на уровне ассемблера, использованный приреализации Лисп. Изучается понятие абстрактной машины (secd) дляопределения операционной семантики языка функциональногопрограммирования по Венской методике, а именно для отображенияабстрактного синтаксиса языка на язык абстрактной машины.Анализируется процедура включения средств уровня ассемблера ввысокоуровневую обстановку языка Лисп, опробованных при раскруткеЛисп-системы.Низкоуровневое программирование. АссемблерП.Лэндин (P.J.Landin) предложил специальную абстрактную машинуSECD, удобную для спецификации машинно-зависимых аспектовсемантики Лиспа, которая будет рассмотрена ниже.
А в первых Лиспсистемах для реализации ядра и встроенных операций использовалсяспециальный Лисп- ассемблер LAP, описание которого приводим вкачестве иллюстрации [1]. (LAP проектировался специально для нуждкомпилятора, но он применялся и для низкоуровневых определенийфункций, а также для обработки исправлений (patches). Этодвухпроходный встроенный, исключительно внутренний ассемблер.Первый просмотр анализирует программу и выясняет взаимосвязимежду ее частями и Лисп-системой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
