Terminazione del combinatore Z con call-by-value

Question

Sto cercando di costruire il mio interprete λ-calcolo. Finora supporta sia il valore call-by-value che l'ordine normale.

Ora voglio provare la ricorsione tramite punti fissi. La $ y $ Combinator funziona con ordine normale, testato con la funzione di facoltà $$ \ text {fac}=lambda f . \ Lambda n. \ Text {ISZERO} \, n \, 1 (\ testo {mul} \, n \, (f (\ testo {pred} \, n))) \ text {,} $$ . E ad esempio il mio interprete rendisce $ y \, \ testo {fac} \, 3 \ stackrel {\ text {no}} {\ dama dama} 6 $ . (Scriverò i numeri della chiesa equivalenti comportamentalmente come numeri decimali)

Per quanto ne so per call-by-value avrò bisogno della $ z $ combinatore invece:

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

come $ y $ causerebbe una regressione infinita immediata.

Il mio problema è che non riesco a capire come $ z \, \ testo {fac} \, 0 $ dovrebbe terminare. Inoltre non termina nel mio interprete, ma voglio capirlo manualmente prima.

DOPO alcuni passaggi CALL-by-Value dovrebbe arrivare a: $$ z \, \ testo {fac} \, 0 \\=lambda f. (\ Lambda x. f (\ Lambda y x x y)) (\ lambda x. f (\ lambda y x x y)) \, \ testo {fac} \, 0 \\\ backrel {\ text {cbv}} {\ reapyarrow} (\ lambda x. \ testo {fac} (\ lambda y xxy)) (\ lambda x. \ testo {fac} (\ lambda y xxy) ) \, 0 \\\ Stackrel {\ text {cbv}} {\ reapyarrow} \ text {fac} (\ lambda y. (\ lambda x. \ testo {fac} (\ lambda y '. xx y')) (\ Lambda x . \ testo {fac} (\ lambda y xx y ')) y) \, 0 \\\ Stackrel {\ text {cbv}} {\ Right Dlayrsow} \ Text {Fac} \, f \, 0 \ stackrel {\ text {cbv}} {\ reapyarrow} \ testo {iszero} \, 0 \, 1 \, a \ testo {,} $$ < / span>

dove il termine omesso

$$ A=testo {mul} \, 0 \, (f \, (\ testo {pred} \, 0)) $$ contiene < / P >.

$$ f=Lambda y. (\ Lambda x. \ testo {fac} (\ Lambda y'xxxy ')) (\ Lambda x. \ testo {fac } (\ Lambda y'xxyy ')) \, y $$ di nuovo.

Ora, $ \ Text {ISZERO}} {\ backrel {\ text {cbv}} {\ Dlayrsore} \ Lambda t. \ Lambda ft $ , st

$$ \ Text {ISZERO}} \, 0 \, 1 \, A \ Stackrel {\ TEXT {CBV}} {\ Right Director} (\ Lambda T. \ Lambda ft ) \, 1 \, A \ stackrel {\ text {cbv}} {\ reapyarrow} (\ lambda f. 1) \, a \ testo {.} $$

Se la nostra lingua aveva un costrutto ramificato che ignorerebbe la $ A $ ramo che saremmo fatti, ma con il valore call-by-value dobbiamo valutare < Span Class="Math-Container"> $ A $ ad un valore, ovvero un'astrazione.

$ a=testo {mul} \, 0 \, (f \, (\ testo {pred} \, 0)) $ e $ \ testo {mul} \, 0 $ sarà un'altra astrazione così successivamente devo ridurre $ f \, (\ Text {Pred } \, 0) $ .

$ \ text {pred}} {cbv} {\ text {cbv}} {\ dama damersow} 0 $ , quindi riduriamo $ f \, 0 $ .

$$ f \, 0= (\ Lambda y. (\ Lambda x. \ testo {fac} (\ Lambda y'xxy ')) (\ Lambda X. \ testo {fac} (\ Lambda y'xxyy ')) \, y) \, 0 \ backrel {\ text {cbv}} {\ reapyarrow} (\ Lambda x. \ testo {fac} (\ Lambda y' .xxy ')) (\ Lambda x. \ testo {fac} (\ lambda y'xxyy')) \, 0 \ backrel {\ text {cbv}} {\ dama dama} \ testo {fac} \, f \ , 0 $$

E ora siamo tornati a quelli quadrati. Sto facendo qualcosa di sbagliato?

Answer 1

Non penso che tu stia facendo la riduzione sbagliata, ma il problema non è il combinatore Z.Il problema è $ \ Text {ISZERO} $ .I costrutti di ramificazione nel valore call-by-value non possono semplicemente prendere i termini diretti per ciascun ramo come argomenti come possono in calo by-name (o simili), poiché entrambi i rami saranno valutati indipendentemente dal test.Questo interagisce chiaramente male con la ricorsione, ma è anche indesiderabile in generale.

Invece, i costrutti di ramificazione in call-by-value dovrebbero prendere argomenti esplicitamente ritardati.Quindi qualcosa come: $$ \ text {ISZERO} \ N \ (λ \ _. 1) (λ \ _. \ Testo {mul} \n\ (f \ (\ testo{Pred} \ n)) $$ In questo modo la valutazione ricorsiva può essere evitata a meno che non sia effettivamente necessaria. Potresti, ovviamente, lasciare $ \ Text {ISZERO}$ Come è, usalo sempre in questo modo e fornisci un argomento extra da solo, ma penso che normalmente sarebbe definito aspettarsi argomenti ritardati.