3 ms·

I could be totally wrong, happy to be corrected. And I'm less familiar with lazy languages. My very basic impression of implementing laziness is just that you w

• mananaysiempre 5y ago
  Wrapping in bare functions gives you “call by name”, where let y = f(x) in g(y, y) will compute f(x) twice. In effect you just evaluate function applications (and lets) by substituting a copy(!) of the argument text for every occurence of the variable in the body. It’s pretty easy for this to get exponentially bad. If you want conventional lazy evaluation, that is “call by need”, you need to memoize: wrap everything in stateful functions (“thunks” in Haskell-implementer-speak, “promises” in Scheme-speak, but not the same as E/JavaScript-style async promises) that compute the result and save it on the first invocation, but then return it immediately. Apart from efficiency considerations (it’s better to use a tagged union of function pointer and result value instead of calling the function all the time) and a single conceptual wrinkle[1], that’s it. Call-by-name and call-by-need obviously yield very different complexity, but are in fact equivalent regarding termination, and optimal: if any evaluation strategy terminates on a given term, so do they. The lovely recent paper “Call-by-need is clairvoyant call-by-value”[2] shows that lazy evaluation in fact never does more steps than call-by-need and in fact does a subset of them: those and only those that influence the final result. (The problem, of course, is that none of this addresses memory usage.) Emulating eager evaluation with lazy can be done if you have seq: (a `seq` b) means “when this is forced, force (the outermost layer of) a, then replace yourself with b (which will then be forced as much as necessary)”: replacing f(e) with (let x = e in x `seq` f(x)) everywhere is not quite enough IIRC, but gets you most of the way there. In a dynamically-typed language, you can implement seq using some of the built-in strictness, like a `seq` b = if null(a) then b else b, because null (or any other type discriminator) needs to force the outer layer of its argument (though I’m not sure if you can make this work in bare lambda calculus with functions only, oops); in a statically typed language, a polymorphic seq is AFAIU an unimplementable primitive, but if you need to translate a complete program you should always be able to implement seqT for every type T that occurs in it and use that (and every lazy language has seq anyway). [1] https://srfi.schemers.org/srfi-45/srfi-45.html https://srfi.schemers.org/srfi-45/srfi-45.html [2] https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf, https://youtu.be/S69UOGqda8w https://youtu.be/S69UOGqda8w
  • eatonphil 5y ago
    Right I forgot that everything is memoized. Thanks for the correction!