Terminação do Combinador Z com Call-by-Valor

Question

Eu estou tentando construir meu próprio intérprete de cálculo. Até agora ele suporta a ordem normal e normal.

Agora quero tentar a recursão através de pontos fixos. A $ Y $ Combinator funciona com ordem normal, testada com a função do corpo docente $$ \ text {fac}=lambda f . \ Lambda n. \ text {{iczero} \, n \, 1 (\ text {mul} \, n \, (f (\ text {pred} \, n)))) \ TEXT {,} $$ E, por exemplo, meu intérprete produz $ y \, \ text {fac \, 3 \ stackrel {\ text {no}} {\ rightarrow} 6 $ . (Vou escrever numerais de igrejas equivalentes de comportamento como números decimais)

Tanto quanto eu sei para chamada por valor eu precisarei da $ z $ Combinator em vez disso:

$$ z=lambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \ text {,} $$

como $ y $ causaria uma regressão infinita imediata.

Meu problema é, não entendo como $ z \, \ text {fac \, 0 $ é suposto terminar. Também não termina no meu intérprete, mas quero entendê-lo manualmente primeiro.

Depois de algumas etapas chamada por valor deve chegar a: $$ z \, \ text {fac} \, 0 \\=lambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \, \ text {fac} \, 0 \\\ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda x. \ text {fac} (\ lambor y. xxy) (\ lambda x. \ text {fac} (\ lambda y. xxy) ) \, 0 \\\ stackrel {\ text {cbv}} {\ rightarrow} \ text {fac}} (\ lambda y. (\ lambda x. \ text {fac} (\ lambda y '. xx y') (\ lambda x . \ Texto {fac} (\ lambor y. xx y ')) y) \, 0 \\\ stackrel {\ text {cbv}} {\ rightarrow} \ text {fac} \, f \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} \ text {iczero} \, 0 \, 1 \, a \ text {,} $$ < / span>

onde o termo omitido

$$ a=text {mul} \, 0 \, (f \, (\ text} \, 0)) $$ contém < / p >.

$$ f=lambda y. (\ lambda x. \ text {fac} (\ lambda y'.xxy ') (\ lambda x. \ text {fac } (\ lambda y'.xxy ')) \, y $$ novamente.

agora, $ \ text {iczero} \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} \ lambda t. \ lambda ft $ , st

$$ \ Texto {iczero} \, 0 \, 1 \, a \ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda t. \ lambda ft ) \, 1 \, a \ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda f. 1) \, a \ text {.} $$

Se a nossa linguagem tivesse uma construção de ramificação que ignorasse a ramificação $ a $ a $ que seríamos feitos, mas com valor por chamada, temos que avaliar < span class="contêiner matemática"> $ a $ para um valor, ou seja, uma abstração.

$ a=text {mul} \, 0 \, (f \, (\ text} \, 0)) $ e $ \ text {mul} {mul} \, 0 $ será outra abstracção, então em seguida, tenho que reduzir $ f \, (\ text {pred } \, 0) $ .

$ \ text {pred} \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} 0 $ , então reduzimos $ f \, 0 $ .

$$ f \, 0= (\ lambda y. (\ lambda x. \ text {fac} (\ lambda y'.xxy ')) (\ lambda x. \ text {fac} (\ lambda y'.xxy ')) \, y) \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda x. \ text {fac} (\ lambda y' .xxy ')) (\ lambda x. \ text {fac} (\ lambda y'.xxy')) \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} \ text} \, f \ 0 $$

e agora estamos de volta ao quadrado um. Estou fazendo algo errado?

Answer 1

Eu não acho que você está fazendo a redução errada, mas o problema não é o combinador Z.O problema é $ \ text {iczero} $ .Construções de ramificação em chamadas por valor não podem apenas levar os termos diretos para cada ramificação como argumentos como eles podem em nome por nome (ou similar), porque ambos os ramos serão avaliados independentemente do teste.Isso claramente interage mal com a recursão, mas também é indesejável em geral.

Em vez disso, as construções de ramificação no valor de chamada devem ter argumentos explicitamente atrasados.Então, algo como: $$ \ Texto {iczero} \n\ (λ \ _. 1) (λ \ \ \. \ Text {mul} \n\ (f \ (\ text{pred} \ n)) $$ desta forma a avaliação recursiva pode ser evitada a menos que seja realmente necessário. Você poderia, é claro, deixar $ {iczero}$ como é, sempre use dessa maneira, e fornecer um argumento extra, mas eu acho que normalmente seria definido para esperar argumentos atrasados.