Small question I don't really feel like thinking about too much, and which is probably in literature somewhere anyway. I am looking for references.

Assume a lambda calculus (LCi) with side effects/impure function calls: LCi = v | \v . LCi | (LCi LCi) | call LCi* . * is a sequence of terms.

An example term: (\x. \y. call (+) x y) 2 3.

Assume EAGER(l) and LAZY(l), eager and lazy operational semantics for closed, mostly terminating, terms in LCi, respectively. Call accepts terms in strong normal form (snf), and return terms in snf.

We assume that EAGER and LAZY map a term into (LCi = call LCi*)* LCi, the collection of made calls in temporal order followed (possibly) by the term in snf.

I.e., the eager operational semantics of the example would be: 5 = call (+) 2 3, 5.

Needed: two functions e_to_l and l_to_e such that EAGER(l) =LAZY(e_to_l l), LAZY(l) = EAGER(l_to_e l), EAGER(l) = EAGER(l_to_e (e_to_l l)), and LAZY(l) = LAZY(e_to_l (l_to_e l)).

Note that = is equivalence modulo alpha-renaming.

Rationale: I want to implement some lazy features in an eager language.

More rationale: Nice functions to have because:

1. Say you would like to implement a Haskell compiler but you only have a Lisp compiler. Solution: translate Haskell to a corresponding LCi term l, translate that term to l' = l_to_e l, translate that to Lisp.

2. Say you want to have eager semantics in impure Haskell. That could be done similarly with the e_to_l function.

I didn't think it through too much, CPS probably doesn't do it.

[EDIT: REPLACED THE WHOLE POST :)]