Можно ли продемонстрировать различные стратегии оценки, изменив этот простой редуктор?

Я предпочитаю учиться, глядя на код вместо того, чтобы читать длинные объяснения. Это может быть одной из причин, по которым мне не нравятся длинные академические документы. Код является однозначным, компактным, бесшумным, и если вы не получите что-то, что вы можете просто сыграть с ним, не нужно спрашивать автора.

Это полное определение исчисления лямбда:

-- A Lambda Calculus term is a function, an application or a variable.
data Term = Lam Term | App Term Term | Var Int deriving (Show,Eq,Ord)

-- Reduces lambda term to its normal form.
reduce :: Term -> Term
reduce (Var index)      = Var index
reduce (Lam body)       = Lam (reduce body)
reduce (App left right) = case reduce left of
    Lam body  -> reduce (substitute (reduce right) body)
    otherwise -> App (reduce left) (reduce right)

-- Replaces bound variables of `target` by `term` and adjusts bruijn indices.
-- Don't mind those variables, they just keep track of the bruijn indices.
substitute :: Term -> Term -> Term
substitute term target = go term True 0 (-1) target where
    go t s d w (App a b)             = App (go t s d w a) (go t s d w b)
    go t s d w (Lam a)               = Lam (go t s (d+1) w a) 
    go t s d w (Var a) | s && a == d = go (Var 0) False (-1) d t 
    go t s d w (Var a) | otherwise   = Var (a + (if a > d then w else 0))

-- If the evaluator is correct, this test should print the church number #4.
main = do
    let two = (Lam (Lam (App (Var 1) (App (Var 1) (Var 0)))))
    print $ reduce (App two two)

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

Ответы

Ответ 1

Вызов по имени требует только нескольких изменений:

  • Не вычисляет тело абстракции лямбда: reduce (Lam body) = (Lam body).

  • Не оценивать аргумент приложения. Вместо этого мы должны заменить его следующим:

    reduce (App left right) = case reduce left of
    Lam body -> reduce (substitute right body)

Call-by-need (aka lazy evaluation) кажется сложнее (или, возможно, невозможным) реализовать полностью декларативно, потому что нам нужно запоминать значения выражений. Я не вижу способа добиться этого с небольшими изменениями.

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

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

Ответ 2

Тема довольно широка. Я просто напишу о нескольких идеях.

Предлагаемый reduce выполняет параллельную переписывание. То есть он отображает App t1 t2 в App t1' t2' (при условии, что t1' не является абстракцией). Некоторые стратегии, такие как CBV и CBN, являются более последовательными, поскольку они имеют только одно redex.

Чтобы описать их, я бы изменил reduce так, чтобы он возвращал, действительно ли было сделано сокращение, или если вместо этого термин был нормальной. Это можно сделать, вернув a Maybe Term, где Nothing означает нормальную форму.

Таким образом, CBN будет

reduce :: Term -> Maybe Term
reduce (Var index)            = Nothing   -- Vars are NF
reduce (Lam body)             = Nothing   -- no reduction under Lam
reduce (App (Lam body) right) = Just $ substitute right body
reduce (App left right) = 
      (flip App right <$> reduce left) <|>  -- try reducing left
      (App left       <$> reduce right)     -- o.w., try reducing right

тогда как CBV будет

reduce :: Term -> Maybe Term
reduce (Var index)            = Nothing
reduce (Lam body)             = Nothing   -- no reduction under Lam
reduce (App (Lam body) right) 
     | reduce right == Nothing            -- right must be a NF
     = Just $ substitute right body
reduce (App left right) = 
      (flip App right <$> reduce left) <|>
      (App left       <$> reduce right)

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