М-выражение
 | Эта статья нуждается в дополнительных цитатах для проверки . ( август 2013 г. ) |
В компьютерном программировании М -выражения (или метавыражения ) были ранним предложенным синтаксисом для языка программирования Лисп , вдохновленным современными языками, такими как Фортран и АЛГОЛ . Эта нотация так и не была реализована в языке и, как таковая, никогда не была доработана. [1]
М-выражения представляют собой синтаксис кода LISP и обеспечивают обозначение функций , синтаксис для cond форме и для встроенных литеральных данных (через S-выражения) в программы. Таким образом, M-выражения использовали S-выражения для буквальных данных. Синтаксис S-выражений («Язык данных») и M-выражений («Метаязык») определен на страницах 8 и 9 руководства по Lisp 1.5. [2]
M-выражения также имели соответствующее представление S-выражений. Код был вручную переведен из M-выражений в S-выражения. В M-выражениях были встроены литеральные данные, которые затем приходилось заключать в кавычки в S-выражениях.
Форма M-выражения
append[listvar;(PARIS BERLIN NEWYORK TOKYO)]
затем необходимо преобразовать в форму S-выражения
(APPEND LISTVAR (QUOTE (PARIS BERLIN NEWYORK TOKYO)))
Предыстория [ править ]
Джон Маккарти опубликовал первую статью о Лиспе в 1960 году, будучи научным сотрудником Массачусетского технологического института . В ней он описал язык символических выражений ( S-выражений ), который мог представлять сложные структуры в виде списков. Затем он определил набор примитивных операций над S-выражениями и язык метавыражений (M-выражений), который можно было использовать для определения более сложных операций. Наконец, он показал, как сам метаязык может быть представлен с помощью S-выражений, в результате чего появилась система, которая потенциально была самодостаточной . [3] Черновая версия этого документа известна как «AI Memo 8». [4]
| Тип выражения | LISP M-выражение | соответствующее S-выражение LISP |
|---|---|---|
| Буквальный атомный символ, написанный заглавными буквами. | ALPHA123
|
(QUOTE ALPHA123)
|
| Список букв в обозначении минусов | (A . (B . NIL))
|
(QUOTE (A . (B . NIL)))
|
| Буквенный список в списочной записи | (A B C 1 2 3)
|
(QUOTE (A B C 1 2 3))
|
| Идентификатор переменных и функций, записанный строчными буквами в M-выражениях. | name123
|
NAME123
|
| Приложение функции с переменными | f[x;y]
|
(F X Y)
|
| Приложение функции на S-выражении | car[(A B C)]
|
(CAR (QUOTE (A B C)))
|
| Применение функции на двух S-выражениях | cons[A;(B C D)]
|
(CONS (QUOTE A) (QUOTE (B C D)))
|
| Условное выражение | [lessp[x;0] → minus[x]; T → x]
|
(COND ((LESSP X 0) (MINUS X)) (T X))
|
| Определение рекурсивной функции | label[ff;λ[[x];[atom[x] → x; T → ff[car[x]]]]]
|
(LABEL FF (LAMBDA (X) (COND ((ATOM X) X) (T (FF (CAR X))))))
|
Маккарти планировал разработать автоматический компилятор Лиспа ( LISP 2 ), используя M-выражения в качестве синтаксиса языка и S-выражения для описания внутренних процессов компилятора. Стивен Б. Рассел прочитал статью и предположил, что S-выражения являются более удобным синтаксисом. Хотя Маккарти не одобрял эту идею, Рассел и его коллега Дэниел Дж. Эдвардс вручную написали программу- интерпретатор , которая могла выполнять S-выражения. [2] Эта программа была принята исследовательской группой Маккарти, сделав S-выражения доминирующей формой Лиспа.
Маккарти размышлял о судьбе М-выражений в 1979 году:
Проект точного определения М-выражений и их компиляции или, по крайней мере, перевода в S-выражения не был ни завершен, ни заброшен явно. Оно просто отошло в неопределенное будущее, и появилось новое поколение программистов, которые предпочитали внутреннюю нотацию любой нотации, подобной FORTRAN или ALGOL, которую можно было изобрести. [5]
Книга Джона Аллена «Анатомия LISP» объясняет определение M-выражений и использует их на протяжении всей книги для объяснения Lisp и его реализации. [6]
Примеры [ править ]
Определения функций применяются и оцениваются из Руководства по Lisp 1.5, стр. 13.
apply[fn;x;a] =
[atom[fn] →
[eq[fn;CAR] → caar[x];
eq[fn;CDR] → cdar[x];
eq[fn;CONS] → cons[car[x];cadr[x]];
eq[fn;ATOM] → atom[car[x]];
eq[fn;EQ] → eq[car[x];cadr[x]];
T → apply[eval[fn;a];x;a]];
eq[car[fn];LAMBDA] → eval[caddr[fn];parlis[cadr[fn];x;a]];
eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];caddr[fn]];a]]]
eval[e;a] =
[atom[e] → cdr[assoc[e;a]];
atom[car[e]] →
[eq[car[e],QUOTE] → cadr[e];
eq[car[e];COND] → evcon[cdr[e];a];
T → apply[car[e];evlis[cdr[e];a];a]];
T → apply[car[e];evlis[cdr[e];a];a]]
Использование функции eval для s-выражения.
eval[(EQ (QUOTE A) (CAR (CONS (QUOTE A) (QUOTE (B C D)))));NIL]
Реализации [ править ]
Для ЛИСП [ править ]
MLisp был современным (1968–1973) проектом по реализации внешнего интерфейса Lisp, похожего на M-выражение. несколько дополнительных функций, таких как гигиенические макросы , сопоставление с образцом и возврат назад Было включено . В конечном итоге он превратился в заброшенный проект LISP70 . M-LISP ( MetaLISP ) 1989 года был еще одной попыткой объединить M-выражения со Scheme. [7]
Анализатор М-выражения « AI Memo 8» доступен в Common Lisp , но автор рассматривает его как аргумент против М-выражений из-за его предполагаемой неспособности справиться с макросами. [8]
Дальнейшее развитие [ править ]
CGOL MacLisp (1977) был реализован в . и преследует аналогичную цель - введение синтаксиса, подобного Алголу, с инфиксными операторами [7] Известно, что он работает над Armed Bear Common Lisp . [9]
Более поздний (около 2003 г.) вариант — это I-выражение , которое использует отступы для неявного обозначения круглых скобок и, таким образом, в некотором смысле является промежуточным между S-выражениями и M-выражениями. I-выражения были введены в Scheme Request For Implementation 49 как вспомогательный синтаксис для Scheme , но они не получили широкого распространения. [10]
Дальнейшее развитие — «милое» t-выражение , имеющее инфиксные операторы без приоритета. Как и I-выражения, t-выражения представляют собой всего лишь простое преобразование S-выражений, поэтому теоретически их можно использовать на любом диалекте Лиспа и не мешать таким функциям, как макросы. [11]
Дополнительные, связанные с синтаксисом, включают Dylan от Apple (токены типа Algol) и Clojure других литеральных синтаксисов. добавление [7]
Примечания [ править ]
Ссылки [ править ]
- ^ «Реализация LISP» . www-formal.stanford.edu . Проверено 29 марта 2020 г.
- ^ Перейти обратно: а б с «Руководство программиста LISP 1.5» (PDF) . Community.computerhistory.org. 1965. Архивировано из оригинала (PDF) 11 февраля 2006 г. Проверено 2 сентября 2013 г.
- ^ Маккарти, Джон (апрель 1960 г.) «Рекурсивные функции символьных выражений и их машинное вычисление, часть I»
- ^ Маккарти, Джон (март 1959 г.). «Рекурсивные функции символьных выражений и их машинное вычисление (AI Memo 8)» .
- ^ «Реализация LISP» . Официальный сайт Stanford.edu. 12 февраля 1979 г. Проверено 24 августа 2013 г.
- ^ «Анатомия LISP» . МакГроу-Хилл, Инк. 1978.
- ^ Перейти обратно: а б с Ли, Ха. «Обзор синтаксиса инфиксов LISP» .
- ^ «Парсер M-выражений» .
Давайте новичкам поиграем с ними и поймем, насколько они непрактичны. Обратите внимание, например, что мы больше не можем использовать макросы, поскольку их синтаксис должен быть известен анализатору M-выражений.
- ^ CGOL о ABCL Разработка блога о реализации Armed Bear Common Lisp .
- ^ Мёллер, Эгиль (2003). «SRFI 49: Синтаксис, чувствительный к отступам» . srfi.schemers.org .
- ^ Уилер, Д.А. (2013). «SRFI 110: Sweet-выражения (t-выражения)» . srfi.schemers.org .