globalf5-240972240972 (850810), страница 18
Текст из файла (страница 18)
ГородняяОсновы функционального программированияЗначением (GET 'FF 'EXPR) будет (LAMBDA (X) (COND ...)), если определение FF было предварительно задано с помощью(DEFUN FF (X)( COND ... )).Свойство с его индикатором может быть вычеркнуто - удалено изсписка функцией REMPROP в форме (REMPROP x i).С середины 70-х годов возникла тенденция повышать эффективностьразработкой специальных структур, отличающихся в разныхреализациях. Существуют реализации, например, muLisp, допускающиеработу с представлениями атома как с обычными спискамипосредством функций CAR, CDR.Согласно стандарту Common Lisp, глобальные значения переменных иопределения функций хранятся в фиксированных полях структурыатома. Они доступны с помощью специальных функций, SYMBOLFUNCTION и SYMBOL-VALUE.
Список произвольных свойств можнополучить с использованием функции SYMBOL-PLIST. ФункцияREMPROP в Clisp удаляет лишь первое вхождение заданного свойства.Новое свойство можно ввести формой вида:(SETF (GET atom indicator ) property )Числа представляются в Лиспе как специальный тип атома. Атом такоготипа состоит из указателя с тэгом, специфицирующим слово как число,тип этого числа и адрес собственно числа произвольной длины. Вотличие от обычного атома одинаковые числа при хранении несовмещаются.До этого момента списки рассматривались на уровне текстового вводавывода.
В настоящем разделе анализируется кодовое представлениесписков внутри машины и сборщик мусора, обеспечивающийповторное использование памяти.Представление структуры спискаВ машине списки хранятся не как последовательности символов, а какструктурные формы, построенные из машинных слов как частей116Л.В. ГородняяОсновы функционального программированиядеревьев, подобно записям в Паскале при реализации односвязныхсписков.
При изображении структуры списка машинное слово рисуетсякак прямоугольник, разделенный на две части: адрес и декрементРис. 1.1. структура спискаКаждая из частей занимает фиксированное число разрядов,представляющее тэг и адрес. Если декремент слова "x" указывает наслово "y", то это можно выразить стрелками на схеме:Рис. 1.2.
схемаТеперь можно дать правило представления S-выражений в машине.Представление атомов будет пояснено ниже. В тех случаях, когдамашинное слово в адресе или декременте содержит указатель на атом,данный атом отобразится как запись в соответствующемпрямоугольнике:Рис. 1.3. отображение атома в прямоугольникеПравило представления неатомных S-выражений — начало со слова,содержащего указатель на car выражения в адресе и указатель на cdr вдекременте.
Ниже нарисовано несколько схем S-выражений. Посоглашению NIL обозначается как перечеркнутый по диагоналипрямоугольник.117Л.В. ГородняяОсновы функционального программированияРис. 1.4. обозначение NILвместо (A . B).Рис. 1.5. (A . B)Непосредственная польза от сопоставления графического вида спредставлением списков в памяти поясняется при рассмотрениифункций, работающих со списками, на следующем примере из [1]:((M . N) X (M . N))Рис.
1.8. примерВозможное для списков использование общих фрагментов ((M . N) X (M. N)) может быть представлено графически:Рис. 1.9. графическое представлениеВ точности такую структуру непосредственно текстом представитьневозможно, но ее можно построить с помощью одного из выраженийвыражений:(LET ((a '(M . N))) (SETQ b (LIST a 'X a)) )118Л.В.
ГородняяОсновы функционального программирования((LAMBDA (a) (LIST a 'X a) )'(M . N))Циклические списки обычно не поддерживаются. Такие списки немогут быть введены псевдо-функцией read, однако они могутвозникнуть как результат вычисления некоторых функций, точнее,применения структуроразрушающих или деструктивных функций.Печатное изображение таких списков имеет неограниченную длину.Например, структураРис. 1.10. структураможет распечатываться как ( A B C A B C ... ).Преимущества структур списков для хранения S-выражений в памяти:1.
Размер и даже число выражений, с которыми программа будетиметь дело, можно не предсказывать. Кроме того, можно неорганизовать для размещения выражений блоки памятификсированной длины.2. Ячейки можно переносить в список свободной памяти, как толькоисчезнет необходимость в них. Даже возврат одной ячейки всписок имеет значение, но если выражения хранятся линейно, тоорганизовать использование лишнего или освободившегосяпространства из блоков ячеек трудно.3. Выражения, являющиеся продолжением нескольких выражений,могут быть предоставлены только однажды.Ниже следует простой пример, иллюстрирующий точность построенияструктур списка.
Показаны два типа структур списка и описаны наЛиспе функции для преобразования одного типа в другой.Предполагается, что дан список видаL1 = ((A B C)(D E F ) ... (X Y Z))представленный как119Л.В. ГородняяОсновы функционального программированияРис. 1.11. точность построения структр спискаи нужно построить список видаL2 = ((A (B C))(D (E F)) ... (X (Y Z)))представленный какРис. 1.12. список видаРассмотрим типичную подструктуру (A (B C)) второго списка.Она может быть построена из A, B и C с помощью(CONS 'A (CONS (CONS 'B (CONS 'C NIL)) NIL))120Л.В.
ГородняяОсновы функционального программированияили, используя функцию list, можно то же самое записать как(LIST 'A (LIST 'B 'C))В любом случае дан список x из трех атомов x = (A B C),аргументы A, B и C, используемые в предыдущем построении, можнонайти какA = (CAR x)B = (CADR x)C = (CADDR x)Первый шаг в получении L2 из L1 — это определение функции GRP,строящей (X (Y Z)) из списка вида (X Y Z).(GRP x) = (LIST (CAR x) (LIST (CADR x) (CADDR x)))Здесь GRP применяется к списку L1 в предположении, что L1заданного вида.Для достижения цели новая функция MLTGRP определяется как(MLTGRP L) = (COND ((NULL L) NIL)(T (CONS (GRP (CAR L)) (MLTGRP (CDR L)) )))Итак, MLTGRP, применяемая к списку L1, перебирает (X Y Z) поочереди и применяет к ним GRP, чтобы установить их новую форму (X(Y Z)) до тех пор, пока не завершится список L1 и не построитсяновый список L2.Деструктивные(разрушающие)структуры списковпреобразованияТеория рекурсивных функций, изложенная в лекции 2, будетупоминаться далее как строгий, чистый или элементарный Лисп.
Хотяэтот язык универсален в смысле теории вычислимых функций отсимвольныхвыражений,оннепрактиченкаксистемапрограммирования без дополнительного инструмента, увеличивающего121Л.В. ГородняяОсновы функционального программированиявыразительную силу и эффективность языка.В частности, элементарный Лисп не имеет возможностимодифицировать структуру списка. Единственная базисная функция,влияющая на структуру списка — это CONS, а она не изменяетсуществующие списки, только создает новые.
Функции, описанные вчистом Лиспе, такие как SUBST, в действительности не модифицируютсвои аргументы, но делают модификации, копируя оригинал.Элементарный Лисп работает как расширяемая система, в которойинформация как бы никогда не пропадает. SET внутри PROG лишьформально смягчает это свойство, сохраняя ассоциативный список имоделируя присваивания теми же CONS.Теперь же Лисп обобщается с точки зрения структуры спискадобавлением структуроразрушающих средств — деструктивныхбазисных операций над списками RPLACA и RPLACD.
Эти операциимогут применяться для замены адреса или декремента любого слова всписке. Они используются ради их действия так же, как и ради ихзначения и называются псевдо-функциями.(RPLACA x y) заменяет адрес из x на y, эквивалент (CAR x) :=y. Ее значение — x, но x, несколько отличающийся от того, что былораньше. На языке значений RPLACA можно описать равенством(RPLACA x y) = (CONS y (CDR x))Но действие различное: никакие CONS не вызываются и новые слова несоздаются.(RPLACD x y) заменяет декремент x на y, эквивалент (CDR x) := y.Эти операции должны применяться с осторожностью! Они могут вкорне преобразить существующие определения и основную память.
Ихприменение может породить циклические списки, приводящие кбесконечной печати или выглядящие бесконечными для таких функцийкак EQUAL и SUBST.Деструктивные функции используются при реализации списков свойстватома и ряда эффективных, но небезопасных, функций Clisp-а, таких122Л.В. ГородняяОсновы функционального программированиякак NCONC, MAPC и т.п.Для примера рассмотрим функцию MLTGRP. Это преобразующаясписок функция, которая преобразует копию своего аргумента.Подфункция GRP реорганизует подструктуруРис. 1.13. подструктурав структуру из тех же атомов:Рис.
1.14. структура из тех же атомовИсходная функция делает это, создавая новую структуру и используячетыре CONS. Из-за того, что в оригинале только три слова, по крайнеймере, один CONS необходим, а GRP можно переписать с помощьюRPLACA и RPLACD. Изменение состоит в следующем:Рис. 1.15. новая структураПусть новое машинное слово строит (CONS (CADR x) (CDDRx)). Тогда указатель на него встраивается в x при вычислении формы:(RPLACA (CDR x) (CONS (CADR x) (CDDR x)))Другое изменение сводится к удалению из второго слова указателя натретье слово.Это выполняется как вычисление формы (RPLACA (CDR x) NIL).123Л.В. ГородняяОсновы функционального программированияФункция PGRP теперь определяется как соотношение:(PGRP x) = (RPLACD (RPLACA (CDR x) (CONS (CADR x)(CDDR )x))) NIL)Функция PGRP используется, в сущности, ради ее действия.
Еезначением, неиспользуемым, является подструктура ((B C)). Поэтомудля MLTGRP необходимо, чтобы PGRP выполнялось, а ее значениеигнорировалось. Поскольку верхний уровень не должен копироваться,MLTGRP не обязана основываться на CONS.(PMLTGRP L) =(COND ((NULL L) NIL)(T (PROG2 (PGRP (CDR L))(PMLTGRP (CDR L)) )))PROG2 — функция, вычисляющая свои аргументы. Ее значение —второй аргумент.Значение PMLTGRP — NIL, PGRP и PMLTGRP — псевдо-функции.Список свободной памяти и сборщик мусораВ любой момент времени только часть памяти, отведенной для структурсписков, действительно используется для хранения S-выражений.Остальные ячейки организованы в простой список, называемыйсписком свободной памяти.Первые реализации действовали по следующей схеме [1].Определенный регистр FREE содержит информацию о первой ячейкеэтого списка.
Когда требуется слово для формирования дополнительнойструктуры списка, берется первое слово списка свободной памяти, а кодв регистре FREE заменяется на информацию о втором слове спискасвободной памяти. Не требуется никаких программных средств для того,чтобы пользователь программировал возврат ячеек в список свободнойпамяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
