Fexpr - Fexpr

В Лисп языки программирования, fexpr - это функция, операнды которой передаются ей без оценки. Когда вызывается fexpr, оценивается только тело fexpr; никакие другие оценки не выполняются, кроме случаев, когда они явно инициированы fexpr. Напротив, когда вызывается обычная функция Лиспа, операнды вычисляются автоматически, и только результаты этих вычислений предоставляются функции; и когда (традиционный) Макрос Лиспа вызывается, операнды передаются без оценки, но какой бы результат ни возвращала функция макроса, она оценивается автоматически.

Происхождение названия "fexpr"

В раннем Лиспе среда отображала каждый символ в список ассоциаций, а не непосредственно к значению.[1] Стандартные ключи для этих списков включали два ключа, используемые для хранения значения данных, которые нужно искать, когда символ встречается в качестве аргумента (APVAL и APVAL1); и четыре клавиши, используемые для хранения функции, которую нужно искать, когда символ встречается как оператор. Из функциональных клавиш СУБР указывает скомпилированную обычную функцию, операнды которой были вычислены и переданы ей; ФСУБР указала скомпилированную специальную форму, операнды которой были переданы без вычисления; EXPR указывает обычную функцию, определяемую пользователем; и FEXPR указывает определяемую пользователем специальную форму. Единственная разница между FEXPR и EXPR заключалась в том, автоматически ли оценивались операнды.

Таким образом, в строгом первоначальном использовании FEXPR является определяемой пользователем функцией, операнды которой передаются без оценки. Однако в дальнейшем употреблении термин fexpr может описать любой первоклассная функция чьи операнды передаются без оценки, независимо от того, является ли функция примитивной или пользовательской.[2]

КлючмагазиныОпределяетсяФункция / Специальная форма
APVALзначение данных----
APVAL1значение данных----
СУБРфункциясистемафункция
ФСУБРфункциясистемаособая форма
EXPRфункцияПользовательфункция
FEXPRфункцияПользовательособая форма

Пример

В качестве простой иллюстрации того, как работают fexprs, вот определение fexpr, написанное на Язык программирования ядра, что похоже на Схема. (По соглашению в Kernel имена fexprs всегда начинаются с $.)

($ определить! $ f   ($ vau (Икс у z) е      ($ если (>=? (оценка Икс е) 0)           (оценка у е)           (оценка z е))))

Это определение предоставляет fexpr под названием $ f, который принимает три операнда. Когда вызывается fexpr, местный среда создается путем расширения статической среды, в которой был определен fexpr. Затем создаются локальные привязки: символы Икс, у, и z связаны с тремя операндами вызова fexpr, а символ е привязан к динамической среде, из которой вызывается fexpr. Тело fexpr, ($ если...), затем оценивается в этой локальной среде, и результат этой оценки становится результатом вызова fexpr. Чистый эффект состоит в том, что первый операнд оценивается в динамической среде, и, в зависимости от того, является ли результат этой оценки неотрицательным, оценивается либо второй, либо третий операнд, и этот результат возвращается. Другой операнд, третий или второй, не оценивается.

Этот пример статическая область видимости: локальная среда является продолжением статической среды. Примерно до 1980 года языки Lisp, поддерживающие fexprs, имели в основном динамическую область видимости: локальная среда была расширением динамической среды, а не статической среды.[3] Однако иногда все же необходимо было указать локальное имя для динамической среды, чтобы избежать захват имена локальных параметров.[4]

Обычное использование и устаревание

Поддержка Fexpr продолжалась в Лисп 1.5, последний стандартный диалект Лиспа до того, как он распался на несколько языков.[5] В 1970-х годах два доминирующих языка Lisp[6] — MacLisp и Интерлисп - оба поддерживали fexprs.[7]

В 1980 г. Конференция по Лиспу и функциональному программированию, Кент Питман представил статью «Специальные формы в Лиспе», в которой он обсудил преимущества и недостатки макросов и fexprs и, в конечном итоге, осудил fexprs. Его центральное возражение заключалось в том, что в диалекте Лиспа, допускающем fexprs, статический анализ не может в целом определить, представляет ли оператор обычную функцию или fexpr, поэтому статический анализ не может определить, будут ли оцениваться операнды. В частности, компилятор не может сказать, можно ли безопасно оптимизировать подвыражение, поскольку подвыражение может обрабатываться как неоцененные данные во время выполнения.

МАКРОСпредлагает адекватный механизм для указания определений специальной формы и ... FEXPRне надо. ... Предполагается, что при разработке будущих диалектов Лиспа следует серьезно рассмотреть предложение о том, что FEXPR's следует полностью исключить из языка.[8]

После упадка MacLisp и Interlisp, два языка Lisp, которые стали доминировать к 1993 г.[9] — Схема и Common Lisp - не поддерживают fexprs. newLISP поддерживает fexprs, но называет их «макросами». В Пиколисп все встроенные функции - это fsubrs, а функции уровня Lisp - это exprs, fexprs, lexprs или их смесь.

fexprs с 1980 года

Начиная с Брайан Смит с 3-Лисп в 1982 году было разработано несколько экспериментальных диалектов Лиспа, чтобы исследовать пределы вычислительное отражение. Для поддержки отражения эти Лиспы поддерживают процедуры, которые могут овеществлять различные структуры данных, относящиеся к их вызову, включая неоцененные операнды вызова, что делает эти процедуры fexprs. К концу 1990-х годов fexprs стали ассоциироваться в основном с вычислительной рефлексией.[10]

Получены некоторые теоретические результаты по fexprs. В 1993 году Джон С. Митчелл использовал Лисп с fexprs в качестве примера языка программирования, исходные выражения которого не могут быть формально абстрактными (поскольку конкретный синтаксис исходного выражения всегда может быть извлечен контекстом, в котором он является операндом для fexpr. ).[11] В 1998 г. Митчелл Палочка показал, что добавление устройства fexpr к лямбда-исчисление - устройство, подавляющее перезапись операндов - производит формальная система с тривиальным уравнением теория, что делает невозможным оптимизацию от источника к источнику без анализ всей программы.[10] В 2007 году Джон Н. Шатт предложил расширение лямбда-исчисления, которое будет моделировать fexprs без подавления перезаписи операндов, якобы избегая результата Ванда.[12]

Смотрите также

Следующие языки реализуют fexprs или близкие к ним эквиваленты:

Сноски

  1. ^ Маккарти и др., Руководство программиста на Лисп IС. 88–91.
  2. ^ Питман, Пересмотренное руководство MacLisp, п. 75.
  3. ^ Стил и Габриэль, «Эволюция Лиспа», стр. 239–240.
  4. ^ Питман, Пересмотренное руководство MacLisp, п. 62
  5. ^ Стил и Габриэль, «Эволюция Лиспа», стр. 231-232.
  6. ^ Стил и Габриэль, "Эволюция Лиспа", стр. 235.
  7. ^ Питман, Пересмотренное руководство MacLisp, п. 182.
  8. ^ Питман, "Особые формы в Лиспе", стр. 179.
  9. ^ Стил и Габриэль, «Эволюция Лиспа», стр. 245–248.
  10. ^ а б Жезл, "Теория Fexprs тривиальна", стр. 189.
  11. ^ Митчелл, "Об абстракции и выразительной силе языков программирования", раздел 7.
  12. ^ Шатт, "Вау-калькуляции и теория фэкспрессов".

Рекомендации

  • Маккарти, Дж.; Брайтон, Р.; Эдвардс, Д.; Фокс, П.; Ходс, Л.; Лакхэм, Д.; Малинг, К.; Парк, Д.; Рассел, С. (Март 1960 г.), Руководство программиста LISP I (PDF), Бостон, Массачусетс: Группа искусственного интеллекта, M.I.T. Вычислительный центр и Исследовательская лаборатория По состоянию на 11 мая 2010 г.
  • Джон С. Митчелл, «Об абстракции и выразительной силе языков программирования», Наука компьютерного программирования 212 (1993), стр. 141–163. (Специальный выпуск статей Symp. Theor. Aspects of Computer Software, Сендай, Япония, 1991 г.) Проверено 24 января 2008 г.
  • Кент М. Питман, "Особые формы в Лиспе", Материалы конференции ACM 1980 г. по Лиспу и функциональному программированию, 1980 г., стр. 179–187. Доступ 25 января 2008 г.
  • Кент М. Питман, Пересмотренное руководство MacLisp (Субботнее вечернее издание), MIT Laboratory for Computer Science Technical Report 295, 21 мая 1983 г.
  • Джон Н. Шатт, "Vau-Calculi и теория fexprs", доклад, Серия симпозиумов по языкам программирования и системам Новой Англии (NEPLS), 18 октября 2007 г. Абстрактный по состоянию на 27 января 2008 г.
  • Гай Л. Стил и Ричард П. Габриэль, «Эволюция Лиспа», Уведомления ACM SIGPLAN 28 нет. 3 (март 1993 г.), стр. 231–270.
  • Митчелл Ванд, «Теория Fexprs тривиальна», Лисп и символьные вычисления 10 шт. 3 (май 1998 г.), стр. 189–199. Доступ 25 января 2008 г.