4 ms·
I don't think that's right. There is a basic theorem in (untyped) lambda calculus that says that if a term has a normal form, then any evaluation strategy, incl
by quchen 12y ago
I don't think that's right. There is a basic theorem in (untyped) lambda calculus that says that if a term has a normal form, then any evaluation strategy, including strict and non-strict, will reduce that term to that normal form. Since non-strict evaluation can "skip" arguments that may have no normal form, there are expressions in non-strict languages that terminate while their strict counterparts don't. The opposite scenario does not exist: if a term has to be evaluated, it has to be done in both the strict and non-strict versions. (And in simply typed lambda calculus, all reduction sequences terminate.)
- seliopou 12y agoFor (actual) programming languages without mutation and with more than just lambdas and application for control flow, it is right: f x y = y f (raise Done) Ω Under lazy application semantics this program will never terminate. Under eager application semantics it will.