Differences between revisions 5 and 7 (spanning 2 versions)
Revision 5 as of 2010-05-13 18:21:24
Size: 2645
Editor: MengWang
Comment:
Revision 7 as of 2010-05-13 18:21:59
Size: 99
Editor: MengWang
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
----------
 . | (subst B x N) -nor-> B'

 . M N -cbn-> B' |

----------
 . | M N -nor-> B' |

4) M -cbn-> (M' =/= (\x.B)) | M-cbn->(M' =/= (\x.B)), M'-nor-> M,

 .
----------
 . | N -nor-> N'

 . M N -cbn-> M'N |

----------
 . | M N -cbn-> M' N'

 . Then it follows inductively on the structure of the derivation that nor is absorbent to cbn. For the rules 1) 2) and 4) this is direct. For the rule 3) we use the induction hpothesis. Every other possible pair of subsidiary and hybrid orders leads to the same inductive proof. The substitution is what makes the proof hard, but both the hybrid and the subsidiary evaluation orders use the same evaluation order for |op1|. For the evaluation of the substitution the hypothesis is enough.

This theorem induces us to think that the following definitions for nor are equivalent:

> -- la op1 ar1 op2 ar2 >

----------
 . > cbn = eval return cbn return cbn return > nor = eval nor cbn return (cbn >=> nor) nor > nor' = eval nor' cbn return nor' nor'

because we know that (cbn >=> nor) T = nor T. But this does not have to be generally true, because in the definitions above nor =/= nor', as they are different fix points. It is possible true but further poorf regarding fix point issues must be done.

We expect that the hybridation operation and the absorption theorem can be extended to the case where the evaluation orders being hybridated are not uniform and simplified. This requires to extend the definition of the weaker-than realtion to the infinite space induced by multiple-step recursion definitions and extend the proof as well.

BIBLIOGRAPHY:

@InProceedings{Rey72,

 . author = "John Reynolds", title = "Definitional Interpreters for Higher Order Programming
  . Languages",
 booktitle = "ACM Conference Proceedings", pages = "717--740", publisher = "ACM", year = "1972",

} @Article{Plo75,

 . author = "G. D. Plotkin", title = "Call-by-name, Call-by-value and the Lambda Calculus", journal = "Theoretical Computer Science", volume = "1", year = "1975", pages = "125--159",

} @InProceedings{Ses02,

 . author = "Peter Sestoft", title = "Demonstrating Lambda Calculus Reduction", booktitle = "The Essence of Computation: Complexity, Analysis,
  . Transformation. Essays Dedicated to Neil D. Jones, number 2566 in Lecture Notes in Computer Science",
 year = "2002", pages = "420--435", publisher = "Springer-Verlag",

}
EVALUATION OF THE LAMBDA-CALCULUS - GENERIC EVALUATORS
by Alvaro Garcia Perez
October 23th 2009

EVALUATION OF THE LAMBDA-CALCULUS - GENERIC EVALUATORS by Alvaro Garcia Perez October 23th 2009

None: Minutes20091023 (last edited 2010-05-13 18:21:59 by MengWang)