Явная подстановка - Explicit substitution

В Информатика, лямбда-исчисления говорят, что имеют явные замены если они обратят особое внимание на формализацию процесса замена. Это в отличие от стандартного лямбда-исчисление где замены выполняются бета-редукции неявным образом, который не выражается в расчетах. Концепция явных подстановок стала печально известной (несмотря на большое количество опубликованных в литературе исчислений явных подстановок с совершенно разными характеристиками), потому что это понятие часто встречается (неявно и явно) в формальных описаниях и реализации всех математических форм замена с такими переменными, как в абстрактные машины, логика предикатов, и символьное вычисление.

Обзор

Простой пример лямбда-исчисление с явной заменой - "λx", который добавляет одну новую форму термина к лямбда-исчисление, а именно форма M⟨x: = N⟩, которая читается как «M, где x будет заменен на N». (Значение нового термина такое же, как и обычная идиома позволять х: = N в M из многих языков программирования.) Λx можно записать следующим образом: переписывание правила:

  1. (λx.M) N → M⟨x: = N⟩
  2. x⟨x: = N⟩ → N
  3. x⟨y: = N⟩ → x (x ≠ y)
  4. (M1M2) ⟨X: = N⟩ → (M1⟨X: = N⟩) (M2⟨X: = N⟩)
  5. (λx.M) ⟨y: = N⟩ → λx. (M⟨y: = N⟩) (x ≠ y и x не свободен в N)

Делая замену явной, эта формулировка все же сохраняет сложность лямбда-исчисление «соглашение о переменных», требующее произвольного переименования переменных во время сокращения, чтобы гарантировать, что условие «(x ≠ y and x not free in N)» в последнем правиле всегда выполняется перед применением правила. Поэтому многие исчисления явной подстановки вообще избегают имен переменных, используя так называемый "безымянный" Индекс Де Брёйна обозначение.

История

Явные замены были описаны в предисловии к книге Карри по комбинаторной логике.[1]и вырос из "уловки реализации", используемой, например, АВТОМАТ, и стала респектабельной синтаксической теорией в лямбда-исчисление и переписывание теория. Хотя на самом деле это произошло с де Брюйн,[2] Идея специального исчисления, в котором замены являются частью объектного языка, а не неформальной метатеории, традиционно приписывается Абади, Карделли, Куриен и Леви. Их основополагающая статья[3] на исчислении λσ объясняет, что реализации лямбда-исчисление нужно быть очень осторожным, имея дело с заменами. Без сложных механизмов для разделения структуры замены могут вызвать взрывной рост размера, и поэтому на практике замены задерживаются и явно записываются. Это делает соответствие между теорией и реализацией весьма нетривиальным, а правильность реализаций может быть трудно установить. Одно из решений - сделать замены частью исчисления, то есть иметь исчисление явных подстановок.

Однако как только подстановка сделана явной, основные свойства подстановки меняются с семантических на синтаксические. Одним из наиболее важных примеров является «лемма о подстановке», которая с обозначением λx принимает вид

  • (M⟨x: = N⟩) ⟨y: = P⟩ = (M⟨y: = P⟩) ⟨x: = (N⟨y: = P⟩)⟩ (где x ≠ y и x не свободен в P )

Удивительный контрпример, принадлежащий Меллиесу,[4] показывает, что способ кодирования этого правила в исходном исчислении явных подстановок не соответствует действительности. сильно нормализующий. После этого было описано множество исчислений, пытающихся предложить лучший компромисс между синтаксическими свойствами явных исчислений подстановки.[5][6][7]

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

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

  1. ^ Карри, Хаскелл; Фейс, Роберт (1958). Комбинаторная логика, том I. Амстердам: Издательская компания Северной Голландии.
  2. ^ Н. Г. де Брёйн: безымянное лямбда-исчисление с возможностями внутреннего определения выражений и сегментов. Технологический университет Эйндховена, Нидерланды, факультет математики, (1978), (TH-Report), номер 78-WSK-03.
  3. ^ М. Абади, Л. Карделли, P-L. Curien и JJ. Леви, Явные замены, Журнал функционального программирования 1, 4 (октябрь 1991 г.), 375–416.
  4. ^ П-А. Melliès: Типизированные лямбда-исчисления с явными заменами не могут завершаться. TLCA 1995: 328–334
  5. ^ П. Лесканн, От λσ к λυ: путешествие по исчислениям явных подстановок, POPL 1994, стр. 60–69.
  6. ^ К. Х. Роуз, Явная замена - Учебное пособие и обзор, BRICS LS-96-3, сентябрь 1996 г.ps.gz ).
  7. ^ Делия Кеснер: теория явных замен с безопасной и полной композицией. Логические методы в компьютерных науках 5 (3) (2009)