Как управлять порядком оценки в вызове по стоимости?

Question

У меня есть вопрос о вызове по значению лямбда-исчисления.

1) λx. (Λy.y) x является застрявшим термином или должен быть оценен с λx.x?

2) λx. (Λy.y) (λz.z), что относительно этого?

3) как контролировать порядок оценки в реализации?

Я чувствую себя довольно смущенным, может ли кто-нибудь объяснить эту ценность, застрял срок, порядок оценки, как контролировать?

Заранее благодарен!

Answer 1

1) λx. (Λy.y) x является застрявшим термином или должен быть оценен до λx.x?

Это может помочь подумать с точки зрения терминов и суб-терминов. Здесь мы имеем:

• Абстракция, & lambda; x. (& Lambda; y.y) х, с:
  • приложения (& лямбда; y.y) х, которая применяется
    • & лямбда; y.y (абстракция, с простым термином у)
    • х.

Приложения могут быть преобразованы, следовательно, мы получаем:

• абстракция, & лямбда; х. x, так как приложение перезаписывает x. Это также записывается как комбинатор I.

& Lambda; х (& Lambda; y.y) х не застрял термин:. Термин застрял тогда и только тогда оно не может быть преобразован.

2) λx. (Λy.y) (λz.z), что относительно этого?

В идеале вы пытаетесь сделать это самостоятельно.

Мы имеем:

• абстракция, & лямбда; х. (& Lambda; y.y) (& Lambda; z.z), с:
  • приложение, которое применяется
    • абстракция & лямбда; y.y к
    • Абстракции & Lambda; z.z.

Мы можем преобразовать приложение с помощью Y = (& лямбда; ZZ) и получим: & Lambda; х (& лямбда; ZZ), который может быть сокращен до & лямбда; xz.z или . K *.

3) как контролировать порядок оценки в реализации?

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

Термин К. И. Ω, например, имеет бесконечный путь сокращения, поскольку она сводится к себе (за счет уменьшения Ω ≡ ω ω ≡ (& лямбда; z.zz) (& лямбда; z.zz) к себе), пока он также можно свести к I, применяя K ≡ & lambda; xy.x.

Следовательно, трюк на языке, основанном на исчислении лямбда, заключается в выборе стратегии оценки, которая даст нормальную форму, если таковая существует. Самой основной стратегией является стратегия "leftmost outermost", также называемая обычной оценкой порядка, которая всегда выбирает самую левую и лямбда; абстракции, которые могут быть применены. Он неэффективен, но гарантирует получение нормальной формы, если таковой существует.

В языках программирования необходимо применять трюки, чтобы сделать оценку более эффективной. Чаще всего это включает strictness analysis и graph rewriting.