Лямбда-исчисление: разница между контекстами и контекстами оценки

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

Рассмотрим нетипизированное лямбда-исчисление с логическими значениями и операторами if, термины которых задаются этим синтаксисом:

 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

Контексты C в этом случае будут заданы в соответствии с этим синтаксисом:

C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C 

Кроме того, можно определить контексты оценки E согласно этому другому синтаксису:

E ::= [-] | \x. E | v E | E t | if E t t 

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

1. Когда используются два понятия? Например, я знаю, что контексты оценки используются для определения семантики исчисления, но использование контекстов все еще несколько ускользает от меня. Также я хотел бы получить подтверждение моих знаний здесь.
2. Когда одно предпочтительнее другого и почему?
3. Не могли бы вы указать соответствующие статьи, которые могут помочь мне разобраться в этом вопросе?

Контекст используется для многих целей, но обычно для определения конгруэнции в программах. Оценочные контексты являются подмножеством контекстов. Они обычно используются для определения редукционных отношений. Позвольте мне привести пример каждого.

Один формальный способ определения программы равенства есть две программы , и N являются контекстуально равны , они могут заменять друг друга в каждом контексте без изменения поведения. Мы можем определить это следующим образом: M и N контекстуально равны при условии всех замыкающих контекстов C [ ⋅ ] для M и N : C [ M ] ⇓ t тогда и только тогда, когда C [ N ] ⇓ t . Мы говорим, что контекст закрывается для M , N$M$$N$$M$$N$$C[\cdot]$$M$$N$$C[M] \Downarrow t$$C[N] \Downarrow t$$M, N$если ни ни C [ N ] не имеют свободных переменных. Выражение M ⇓ t означает, что программа M за конечное число шагов уменьшается до значения t . (Кроме того, обратите внимание, что определение контекстуальной эквивалентности более широко используется для богатых понятий вычислений, например, параллельных процессов.)$C[M]$$C[N]$$M \Downarrow t$$M$$t$

Напротив, контексты оценки - это контексты, которые не блокируют оценку. Точнее, контекст оценки - это термин с дырой в точке, где должен произойти следующий шаг восстановления атома (или он может иметь место для недетерминированных вычислений). Таким образом, следующее правило должно выполняться для контекстов оценки: В качестве примера использования контекстов оценки рассмотрим правила редукции дляλ-вычисления по вызову, где мы не уменьшаемся приλ. Таким образом, даже когдаM→N, у нас нет сокращенияλx. M→λx. N. Это можно легко выразить с помощью общего контекстуального правила, приведенного выше, вместе с грамматикой для контекстов оценки, в которой пропущеныλ-выражения. Оценочные контексты были впервые использованы в

$$\frac{M \rightarrow N}{E[M] \rightarrow E[N]}$$ $\lambda$$\lambda$$M \rightarrow N$$\lambda x.M \rightarrow \lambda x.N$$\lambda$Пересмотренный доклад о синтаксических теориях последовательного контроля и государства Феллайзена и Хиба.

Контекст - это синтаксическое понятие. Контекст - это термин с одной дырой. (Иногда существуют многозадачные контексты, определение будет дано четко в этом случае.) Синтаксис контекстов определяется путем принятия синтаксиса терминов и предоставления возможности одному подтерму быть дырой вместо термина. В BNF (я использую лямбда-исчисления в качестве примера, без булевы и если заявления , которые не приносят ничего к примеру.): C : : = [ ] | х | $[]$

$$C ::= [] \mid x \mid t \, C \mid C \, t \mid \lambda x.C$$

$C[]$$t$$C[t]$$t$$[]$$C[t]$$[]$$t$

$$(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}$$ $M \{x\leftarrow N\}$$x \mapsto N$$M$

$t$$M$$N$$x$$t = (\lambda x. M) \, N$$t$$t'$$t' = (\lambda x. M) \, N$$t$$C$$M$$N$$x$$t = C[(\lambda x. M) \, N]$$C[M \{x\leftarrow N\}]$

$$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \qquad \dfrac{M \to_\beta N}{C[M] \to_\beta C[N]} (\gamma)$$ $$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_\beta N}{\lambda x. M \to_\beta \lambda x. N} (C_\lambda) \qquad \dfrac{M \to_\beta N}{M \, P \to_\beta N \, P} (C_{@\lt}) \qquad \dfrac{M \to_\beta N}{P \, M \to_\beta P \, N} (C_{@\gt})$$

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

$$D ::= [] \mid x \mid t \, D \mid D \, t$$ $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} \qquad \dfrac{M \to_{np} N}{D[M] \to_{np} D[N]}$$ $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_{np} N}{M \, P \to_{np} N \, P} (C_{@\lt}) \qquad \dfrac{M \to_{np} N}{P \, M \to_{np} P \, N} (C_{@\gt})$$ $D$ будет называться контекстом оценки, поскольку он используется для определения понятия оценки. Контекст оценки не является особым видом контекста; скорее, назвать его контекстом оценки - это вопрос того, для чего используется этот контекст .

Я приведу еще один пример контекста. Определим значения соответствии со следующим синтаксисом: Теперь давайте определим другой тип контекстов: По сравнению с выше, дыра может быть на стороне функции приложения, если аргумент приложения равен ценность. Затем определите следующее понятие сокращения: $V$

$$V ::= x V_1 \ldots V_n \mid \lambda x. M$$ $$E ::= [] \mid M \, E \mid E \, V$$ $D$ $$\dfrac{}{(\lambda x. M) \, V \to_{cbva} M \{x\leftarrow V\}} (\beta_{cbva}) \qquad \dfrac{M \to_\beta N}{E[M] \to_{cbva} E[N]} (\gamma_{cbva})$$ С ограничением, что аргумент функции должен быть значением в первом правиле, и что лямбда-абстракции не являются контекстами, мы определяем стратегию оценки по значению. С дополнительным ограничением на то, что аргумент оценивается перед функцией, это - аппликативный вызов порядка по значению.