globalf5-240972240972 (850810), страница 24
Текст из файла (страница 24)
ВAPPLY же при выборе адреса встроенной функции мы рассчитываем,что все известные функции реализованы, и их адреса размещены вассоциативном списке — за правильность выбора имен встроенныхфункций отвечает программист.Можно еще поработать с таким определением интерпретатора и болеечетко локализовать его зависимость от четырех различных категорий160Л.В. ГородняяОсновы функционального программированияобъектов: самоопределяемые атомы — (NIL T 1 2 3 ... ),базовыеоперациинадданнымиязыка,обрабатывающиепредварительно вычисленные аргументы, — (CAR CDR CONS ATOMEQ ... ), специальные функции, управляющие обработкойаргументов без их предварительного вычисления, — (QUOTE CONDLET ...) и конструкторы функций, строящие функциональныезначения из обычных выражений, — (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символа, если не считать пробелы в начале строк. Попробуйте написатьсравнимое определение на каком-нибудь знакомом вам языкепрограммирования.Реализация динамической памяти и структур данныхПосле обсуждения схемы функционирования Лисп-интерпретатора и161Л.В.
ГородняяОсновы функционального программированияего сборки из машинно-зависимого конструктива пришло времяпоговорить о структурах данных, используемых при реализациисписков и атомов.Обычно при обработке программ в памяти располагаютсяразносортные результаты, возникающие при разборе и анализе текстапрограммы и ее данных, при построении ее внутреннего кода и приформировании результата. В Лисп-системах традиционно при всех этихвидах работ принято придерживаться принципов логики здравогосмысла:новые значения строятся на новом месте,предпочитаются интересы малых программ,автоматизируется повторное использования памяти, что напервых шагах разработки освобождает программиста отнеобходимость уделять внимание вторичным проблемамраспределения памяти.Кроме того, почти исключается необходимость присваиваний, они впрограммах заменяются именованием.Память обычно распределена по блокам, содержащим ряд слов,образующих структуры данных.
Физический объем памяти, логическаядлина данных и состав информации, полезной для продолжениявычислений, могут существенно различаться. Минимальные потери врезультативности работы с памятью дает динамическая обработкабинарных деревьев — нет простоев из-за незаполненности частиполей.
Каждый узел такого дерева имеет небольшой объем,достаточный для хранения двух типизированных указателей ( CAR иCDR, левый и правый). Типизация указателей нужна для динамическогоконтроля соответствия данных и операций по их обработке. NIL,атомы, списки, числа, строки — все это реализационно различимыетипы данных. (Утверждение о бестиповости Лиспа имеет отношениелишь к отсутствию статического связывания в тексте программы именпеременных с типами их значений. Для компиляции приходитсядополнять Лисп-программы сведениями о типах значений свободныхпеременных, но далеко не каждая программа доживает до компиляции.)Лиспу свойственна функциональная классификация значимых типовданных, т.е.
именно реализационно различимых.162Л.В. ГородняяОсновы функционального программированияРеализация бинарных деревьев или односвязных списков описана вклассических курсах по программированию, а реализацию атомов мырассмотримподробнее.Эффективностьприведенноговышеопределения интерпретатора с использованием ассоциативного спискасущественно зависит от числа различимых атомов в программе. Такаязависимость обычно смягчается механизмом функций расстановки(хэш-функций), обеспечивающим доступ к информации по ключу. Вкачестве ключа используется имя атома. В результате вся связанная сатомом уникальная информация становится легко и быстродостижимой. Структура такой информации называется списком свойстватома. Она представляет собой чередование так называемых"индикаторов" и "значений" свойств. Число свойств атома неограничено. Свойства бывают встроенные, системные или вводимыепрограммистом.
Значения атомов, адреса встроенных операций,определяющие выражения функций — примеры встроенных свойств.Встроенные операции типа LET, LABELS в системе Clisp обычноиспользуют списки свойств. Обработка таблицы, связывающей атомы иих списки свойств, как правило, зависит от реализации. Методызадания и изменения свойств работают подобно обычнымприсваиваниям. Псевдо-функция PUTзадает индикатор исоответствующее ему новое значение свойства атома, а функция GETобеспечивает доступ к свойству атома, соответствующему заданномуиндикатору. Теперь с помощью списков свойств мы могли бы добитьсяточного соответствия семантики констант и определений функций ихспецификации в базовом Лиспе, но не будем отвлекаться на это.Самым интересным, можно сказать революционным, механизмомработы с памятью в Лиспе, бесспорно, стала "сборка мусора". С начала1960-х годов методам такой работы посвящены многочисленныеисследования, которые продолжаются до наших дней и сильноактивизировались в связи с включением похожего механизма вреализацию языка Java.Общая идея всех таких методов достаточно проста:пока памяти хватает, о ней можно не беспокоиться и располагатьновые данные в новых блоках памяти;если памяти вдруг не оказалось, то надо выполнить "сборкумусора", в процессе которой, возможно, найдутся ставшие163Л.В.
ГородняяОсновы функционального программированиябесполезными для программы блоки;если память нашлась, ее снова можно тратить.Специальная программа "Сборщик мусора" выполняет анализдостижимости всех блоков памяти просто пометкой узлов, видимых изконечного числа рабочих регистров системы программирования. Ктаким регистрам относятся промежуточные результаты вычислений,активная часть стека, ассоциативный список, таблица атомов и др.После пометки все непомеченные узлы объединяются в списоксвободной памяти, передающий их для повторного использованияновым вызовам функции CONS. Такая автоматизация не лишенанедостатков, но они обнаруживаются лишь в сравнительно сложныхпроцессах, требования которых мы сейчас не учитываем.Обычно с машиной связывается представление о блоках информациификсированного объема, таких как слова, байты, регистры.Функциональное программирование нацелено на более крупныепостроения — структуры данных не ограниченной заранее длины.Такие структуры достаточно эффективно реализуются посредствомспециального стека, приспособленного к обработке произвольногочисла компонентов текущего уровня иерархической структуры данных.От обычного стека он отличается выделением указателя на конецтекущего уровня.164Л.В.
ГородняяОсновы функционального программированияПри переходе на новый внутренний уровень Кон_тек_ур записывается встек, Нач_стека переписывается в Кон_тек_ур, а адрес новой вершиныстека становится значением Нач_стека.В результате стек хранит ссылки на границы уровней, что обеспечиваетвозможность возврата на любой нужный уровень, в частности,восстановления процесса обработки в случае неожиданных ситуаций.Значительный резерв производительности функциональных программдают деструктивные функции, являющиеся формальными аналогамичистых функций:Таблица 9.1.Соответствие строгихфункций и ихдеструктивныханалогов.APPEND NCONCSUBST NSUBSTREMOVE DELETEREVERSE NREVERSE165Л.В.
Городняя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 в два разных файла.166Л.В.
ГородняяОсновы функционального программирования(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-val167Л.В.
ГородняяОсновы функционального программирования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"168Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
