M-выражение

M-выражения (или метавыражения) в программировании изначально предназначались для использования для записи функций на Лиспе. Данные, обрабатываемые при помощи M-выражений, записывались с использованием S-выражений. M-выражения использовались в первоначальном теоретическом языке, описанном в ранних статьях о Лиспе, однако, в первой работающей реализации Лиспа M-выражения кодировались S-выражениями, и транслятор M-выражений так и не был реализован.

Проект по точному определению M-выражений и их компиляции, или, по крайней мере, трансляции в S-выражения так и не был ни закончен, ни явным образом заброшен. Он был просто отложен на некое неопределённое время, а новое поколение программистов открыло для себя, что они предпочитают внутреннюю нотацию любым формам записи программы в стиле FORTRAN-а или ALGOL-а, которые могли бы быть придуманы.

Оригинальный текст  (англ.)  

The project of defining M-expressions precisely and compiling them or at least translating them into S-expressions was neither finalized nor explicitly abandoned. It just receded into the indefinite future, and a new generation of programmers appeared who preferred internal notation to any FORTRAN-like or ALGOL-like notation that could be devised.

— Джон Маккарти^[1], История Лиспа

Историческая связь с S-выражениями

S-выражения представляют данные, составляемые из атомов и пар. Первоначально атом описывался, как символ в верхнем регистре, а пары ограничивались скобками. Было описано также сокращённая запись списков, хотя первоначально элементов списков разделялись запятыми, а не пробелами. Например запись (мы используем пробелы, а не запятые):

((A B) (C D) (E F))

представляет собой список из трех элементов, каждый из которых представляет собой список из двух символов.

М-выражение может также использовать имена операторов, метапеременные и списки аргументов. Имена операторов и метапеременных задавались в нижнем регистре, чтобы показать, что они не являются символами (данными). Списки аргументов ограничивались квадратными скобками, [] и их элементы отделялись точкой с запятой. Например:

car[cons[(A . B); x]]

представляет собой операцию из двух частей:

• в первой части конструируется пара из структуры данных (A . B) и всех данные представленных метапеременной x;
• во вторая части извлекает первый элемент сконструированной пары.

В первоначальном описании Лиспа, опубликованном Маккарти, где он представлен как теоретический универсальный язык, описана функция eval, которая принимает в качестве входных данных S-выражения, переводя их в форму М-выражений, а также выполняет программы в виде М-выражения, являющихся закодированными S-выражениями. Вот несколько примеров M-выражений и их перекодировки в S-выражения (опять же с использованием современных обозначениях списков):

{M-выражения}                    {S-выражения}
(A B C)                          (QUOTE (A B C))
car[x]                           (CAR X)
car[append[(A B C); (D E F)]]    (CAR (APPEND (QUOTE (A B C)) (QUOTE (D E F))))

Первоначальная реализация Лиспа планировалась как очень долгий процесс, так как в то время компиляторы писались годами. Реализация началась с ручной компиляции определенных функций, в то время как подъязык М-выражений носил ещё предварительный характер. Однако Стив Рассел (англ.) и Daniel J. Edwards поняли, что реализация eval будет работать как полная реализация интерпретатора Лиспа использующего S-выражения.^[2] Ручная компиляция функции eval оказалась в сравнении с ожидаемым многолетним построением компилятора очень простой задачей. Сообщество программистов, использующих S-выражения быстро развивалось. M-выражения были заброшены и не были никогда реализованы.

Современное использование M-выражений

Хотя для Лисп программистов и несвойственно придумывать альтернативные формы языка (один из немногих примеров — это MLISP), некоторые всё же используют M-выражения. Но такие диалекты теряют равнообразность S-выражений, считающуюся важным моментом для выразительности языка. В результате, практически во всех общепринятых диалектах Лиспа S-выражения остаются основным (или единственным) синтаксисом. В число исключений входит язык Logo, который можно рассматривать (с некоторой степенью вольности) как Лисп на основе M-выражений. Некоторые другие языки программирования, такие как Dylan и Ruby, многое позаимствовали у Лиспа, однако используют ALGOLоподобный синтаксис, отличающийся и от S-выражений, и от M-выражений.

Имеется также реализация интерпретатора M-LISP на Common Lisp, также вычисляющая M-выражения.

Варианты

Синтаксис функционального языка ML (англ. Metalanguage, «метаязык»), подобен синтаксису M-выражений («метавыражений»), он так же основан на математической нотации. Однако, наличие в ML дополнительных концепций, таких как аннотации типов и регулярные выражения маскирует это сходство.

Синтаксис, подобный оригинальным M-выражениям использует язык системы Mathematica, списки в нём записываются с использованием скобок (можно использовать для них и нотацию M-выражений), а для записи функций используются M-выражения.

Недавней вариацией на эту тему стали I-выражения, в которых роль неявных скобок играют отступы (как в Python). Таким образом они представляют собой нечто среднее между S-выражениями и M-выражениями. В SRFI-запросе (англ.) № 49 такие I-выражения были предложены как дополнительный синтаксис для языка Scheme, но он не получил широкого распространения.

Ссылки

• Scheme Request For Implementation 49

Примечания

1. ↑ The implementation of LISP
2. ↑ http://community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf