Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1156449), страница 6
Текст из файла (страница 6)
Соответствие двух форм записи – точечной и обычной списочной –для одного и того же лисповского объекта можно установить на основеопределения функции cons, в частности:(cons 'A NIL) => (A . NIL) ,в то же время(cons 'A NIL) => (A) ,поэтому(A) ≡ (A . NIL);аналогично:ипоэтому(cons 'A(cons 'B NIL)) => (A . (B . NIL))(cons 'A (cons 'B NIL)) => (A B) ,(A B) ≡ (A . (B . NIL)).Обобщая, получаем:(v1 . (v2 .
(v3 . … (vk . NIL) … ))) ≡ (v1 v2 v3 … vk)где v1, v2, … vk могут быть произвольными S-выражениями.Заметим, что второй аргумент функции cons может бытьпроизвольным S-выражением, в том числе атомом, отличным от NIL:(cons 'A (cons 'B 'C)) => (A . (B . C))Тем самым второе выражение vk+1 в самой вложенной точечной пареS-выражения может оказаться произвольным атомом, и в этом случае этаточечная пара не может быть преобразована в списочную форму:(v1 . (v2 .
(v3 . … (vk . vk+1) … )))≡(v1 v2 v3 … vk . vk+1)Сформулируем правила перевода списочных выражений из точечнойформы записи в обычную списочную:1) Точка, за которой непосредственно следует открывающая скобка,может быть опущена вместе с этой открывающей скобкой исоответствующей закрывающей скобкой.2) Точка, за которой непосредственно следует атом NIL, может бытьопущена вместе с NIL.Эти правила не всегда позволяют полностью избавиться от точечныхпар: если в правой части некоторой точечной пары S-выражения стоитатом, отличный от NIL, то эта точечная пара остаётся.28В то же время обратные правила преобразования из списочнойформы в точечную позволяют записать в точечных обозначениях любойсписок.
Для этого:1) Каждый пробел, разделяющий элементы списка верхнего уровня,заменяется точкой, за которой ставится открывающая скобка;соответствующая закрывающая скобка вставляется непосредственноперед скобкой, закрывающей верхний уровень списка.2) Последний элемент v списка заменяется точечной паройвида(v . NIL).3) К подспискам (т.е. не атомарным элементам) преобразуемого спискаприменяются эти же правила преобразования.Приведём примеры точечной и списочной записи для одних и тех жесписочных выражений:(A (B) C D) ≡ (A .((B .
NIL) .(C . (D . NIL))))((A B)(C D)) ≡ ((A .(B . NIL)).((C .(D . NIL)). NIL))(A (B C) D) ≡ (A .((B .(C . NIL)).(D . NIL)))Как мы видим, списочная форма записи более простая, в то же времяточечная форма – более общая, она позволяет записывать списочныеструктуры, которые нельзя выразить без точечных пар.Отметим, что хотя S-выражения – списочные структуры болееобщего вида, чем списки, их рекурсивное определение (одна БНФ) прощеи короче, чем рассмотренное нами ранее определение лисповского списка.Как мы увидим далее, более простое определение позволяет в ряде случаевстроить более простые рекурсивные функции.Ещё одно преимущество точечной записи – она упрощает пониманиедействия базовых функций обработки списков – пары селекторов cdr,car и конструктора cons.
Действие функций car и cdr дляS-выражения становится симметричным. Симметричен также результатфункции cons по отношению к двум своим аргументам. Указанные трибазовые функции взаимно обратны, что можно записать как(cons (car S)(cdr S)) ≡ S(car (cons S1 S2)) ≡ S1(cdr (cons S1 S2)) ≡ S2Произвольное S-выражение можно изобразить в виде бинарногодерева, у которого листья – атомы этого выражения, а поддеревья –точечные пары. Поэтому считают, что логической структуройS-выражения является бинарное дерево. Примеры таких деревьев показанына Рис. 1.29(A .((B .
C). D))(A .((B . NIL) .(C . (D . NIL))))≡ (A (B) C D)AADBCBNILCDNIL((A .(B . NIL)).((C .(D . NIL)). NIL))≡ ((A B)(C D))ABNILNILCDNIL(A .((B .(C . NIL)).(D . NIL)))≡ (A (B C) D)ABDCNILNILРис.1. Древовидная структура S-выражений301.7. Внутреннее представление S-выраженийПонятие S-выражения возникло в связи с определённым способомпредставления этих выражений в памяти компьютера. Рассмотримпоочерёдно внутреннее представление атомов и списочных структур.Лисп-интерпретатор в ходе своей работы поддерживает специальнуютаблицу символьных атомов (таблицу символов), в которой хранитсяинформация обо всех атомах, встретившихся в тексте интерпретируемойпрограммы или используемых в качестве обрабатываемых данных.
Приобработке очередного символьного атома интерпретатор проверяет,занесён ли он в таблицу. Если атом уже есть в таблице, интерпретаторизвлекает нужную информацию о нём из таблицы. Если же атомотсутствует в таблице (т.е. новый), соответствующая информация о нёмзаписывается в таблицу.В общем случае для каждого символьного атома в таблице хранится:• его внешнее имя (т.е.
строка, представляющая его при вводе/выводе);• его значение как аргумента функции – фактическое значение, которое сним связано при его использовании в роли формального параметранекоторой функции;• его функциональное значение – определяющее выражение функции,при его использовании в качестве имени этой функции;• список свойств атома (который будет рассмотрен в дальнейшем).Перечисленные пункты можно считать разными видами значенийодного атома.
За исключением внешнего имени, эти значения могутотсутствовать. В общем же случае атом имеет несколько разных значений,и они независимы друг от друга. Это означает, что один и тот жесимвольный атом может быть использован и как имя функции, и как имяформального параметра. Нужная его интерпретация обеспечивается исходяиз контекста его применения.Например, можно определить функцию, один из формальныхпараметров которой совпадает с именем встроенной функции car:(defun Func (z car)(cond (z NIL)(T (car car))))=> FUNCВ этом определении атом car объявлен как формальный параметрфункции Func и используется в её теле дважды: как имя функции и как еёаргумент.
При выполнении вызова функции Func:31(Func (cdr '(G)) '(G)) => Gc её параметрами z и car будут связаны соответственно значения NIL и(G). Далее при вычислении тела функции для атома car сначала будетвзято его определяющее выражение (т.к. он встречается в позиции именифункции), а затем – его значение как параметра (т.к.
он употреблён впозиции аргумента функции).Уточним, что в таблице символьных атомов для каждого атомахранятся не сами его значения (рассмотренных выше видов), а указатели(ссылки) на внутренние представления этих значений. В ряде диалектовЛиспа есть встроенные функции, использующие эти указатели, чтобы длязаданного аргумента-атома выдать в качестве результата его разныезначения: значение атома как параметра функции, функциональноезначение, список свойств этого атома (в Common Lisp это соответственнофункции Symbol-value, Symbol-function, Symbol-plist).Внутренним представлением символьного атома фактическиявляется указатель, ссылка на соответствующий элемент таблицы атомов.Уникальность всех значений, связанных с атомом, обеспечивается тем, чтокаждый известный лисп-интерпретатору атом хранится в таблице толькоодин раз.При представлении в памяти компьютера списочных структуркаждой точечной паре (A .
B) соответствует списочная ячейка,состоящая из двух полей. Эти поля, называемые соответственно car-полеи cdr-поле, содержат указатели на лисповские объекты A и B (атомы илисписочные пары) – см. Рис. 2. Адрес С самой списочной ячейки служитуказателем на эту точечную пару.CABРис. 2. Списочная ячейкаВнутренним представлением S-выражения, состоящего в общемслучае из нескольких точечных пар, является совокупностьвзаимосвязанных списочных ячеек.
Адрес заглавной (первой) списочнойячейки, соответствующей самой внешней точечной паре этогоS-выражения, служит указателем на всю списочную структуру.На Рис. 3 показано внутреннее представление следующихлисповских выражений:32(A (B C) D) ≡ (A .((B .(C . NIL)).(D . NIL)))и(A .((B . C). D)).При этом как указатели списочных структур используются адреса x и y:х ссылается на (A (B C) D), а y – на (A .((B . C). D))). В каждойструктуре число списочных ячеек равно числу точечных парпредставляемого выражения.xAD NILBC NILyADBCРис 3. Внутреннее представление списочных структурРеально в памяти компьютера списочной ячейке можетсоответствовать либо одна ячейка памяти, либо несколько ячеек.Действие встроенных функций базового набора car, cdr и consлегко описывается в терминах внутреннего представления S-выражений: car выбирает содержимое (указатель) из car-поля заглавнойсписочной ячейки структуры, полученной в результате вычисленияаргумента этой функции; cdr выбирает содержимое (указатель) из cdr-поля заглавнойсписочной ячейки структуры, являющейся значением аргументафункции; cons создаёт новую списочную ячейку, помещает в поля этойячейки указатели лисповских объектов, являющихся значениями еёаргументов, и возвращает в качестве своего значения указатель насозданную ячейку.Рассмотрим, какие структуры могут образовать списочные ячейки впамяти компьютера.
В общем случае из полей списочной ячейки указателиведут к другим списочным ячейкам или к элементу таблицы атомов. На33списочную ячейку могут указывать car- и cdr-поля некоторых другихсписочных ячеек. Также возможны ссылки на списочные ячейки изтаблицы атомов – для тех атомов, которые используются как формальныепараметры некоторой функции и в текущий момент имеют значения. НаРис. 4 показана конфигурация списочных ячеек, возникающая послевычисления выражения(append '(Q(R)()) (cons X (cons 'P X)))если значением X было выражение (A .
B).(Q(R)())XQNILRNILNILABP(cons X (cons 'P X))QNIL(append '(Q(R)())(cons X (cons 'P X)))Рис. 4. Списочные структуры в памятиПри вычислении первого аргумента функции append будет созданасписочная структура из четырёх ячеек, а при вычислении второго еёаргумента – структура из трёх ячеек. При вычислении же тела этойфункции будет создана копия верхнего уровня первого списка-аргумента, ккоторой и будет подсоединена вторая списочная структура (напомним,функция append при своей работе использует cons для подсоединенияэлементов первого списка-аргумента ко второму списку-аргументу).Особенность вычислений с использованием встроенных функцийcar, cdr, cons и функций, определённых на основе базового набора,состоит в том, что при этом в памяти компьютера лишь создаются новыесписочные ячейки и структуры на основе уже существующих, ранее жесозданные структуры никогда не изменяются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
