Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 6
Текст из файла (страница 6)
Как и введённое ранее понятие лисповского списка, понятиеS-выражения определяется рекурсивно и допускает произвольноеколичество вложений точечных пар друг в друга, например:((Т . К) . NIL)((А . В) .(С . (А . Е )))В общем случае разделяющая точка в точечной паре должна бытьвыделена пробелами слева и справа, чтобы не слиться со стоящим слеваили справа атомом (т.к.
обычно точка допускается в именах атомов). Еслиже слева или справа от точки стоит скобка, то соответствующий пробелможет быть опущен.Для S-выражений функции базового набора car, cdr и consопределены следующим образом. Пусть значением формы Е являетсяS-выражение (v1 . v2), а v1 и v2 – некоторые S-выражения:Е => (v1 . v2) ,тогда(car Е) => v1 , (cdr Е) => v2 .27Если S-выражения e1 и e2 имеют значения v1 и v2 соответственно:e1 => v1 ,e2 => v2 ,то(cons e1 e2) => (v1 . v2) .Таким образом, аргументами функции cons могут быть произвольныелисповские выражения, в том числе – атомы.Поскольку S-выражение – обобщение понятий атома и списка, вселисповские списки можно записать как S-выражения, используя точечнуюзапись.
Соответствие двух форм записи – точечной и обычной списочной –для одного и того же лисповского объекта можно установить на основеопределения функции 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 создаёт новую списочную ячейку, помещает в поля этойячейки указатели лисповских объектов, являющихся значениями еёаргументов, и возвращает в качестве своего значения указатель насозданную ячейку.Рассмотрим, какие структуры могут образовать списочные ячейки впамяти компьютера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
