6 ms·

It's the opposite, no? Basically every lazy language has some way to force evaluation, but in most strict languages laziness is never fully supported. Closest I

It's the opposite, no? Basically every lazy language has some way to force evaluation, but in most strict languages laziness is never fully supported. Closest I can think of is a Scheme with continuations, but even then it takes some extra work. I know in CL even primitive laziness takes a lot of work and a code-walker, and whatever it's other flaws Common Lisp is at least adaptable.

eatonphil 4y ago
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 wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laziness_in_eager_languages https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...
- mananaysiempre 4y 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 4y ago
    Right I forgot that everything is memoized. Thanks for the correction!
kmill 4y ago
In strict languages, you can delay computation by wrapping it in a zero-argument lambda -- i.e., a "thunk." For efficiency, you want to memoize thunks (that's what Haskell does[1]) so that they only ever evaluate once. Scheme has the "delay" operator to create memoized thunks, which you can later "force". It is true that these are not first class in the sense that you need to manually force the computation, but if it were automatic, how would you (efficiently) pass un-evaluated values around? [1] Incidentally, this is why Haskell's garbage collector needs to be able to deal with mutation. A thunk might graduate to an older generation, and once it is finally evaluated it can end up having pointers to the nursery or other younger generations.
- moomin 4y ago
  So I had a bit of fun implementing something like Haskell’s “Validation” in an eager language recently that has coloured my take somewhat. Basically “perform all these computations and tell me all the things that were wrong with my inputs” is way easier to express in a default lazy language than a default eager language. In default eager you’re constantly trying to figure out the largest number of operations you can do before can no longer continue. Yes, there’s weird perf things that can bite you, but there’s also a bunch of regular bread-and-butter coding things that pervasive makes very much easier.
  - kmill 4y ago
    You really can simulate laziness in a strict language at the small cost of wrapping things in lambdas yourself -- you don't have to figure out what operations you can do yourself so long as you make everything that should be deferred deferrable (for example, if you're trying to do monadic fixedpoints you need to be careful). If you create your own lazy data structures, if your language supports it you can even have those thunks be forced for you automatically. For example, lazy streams (infinite lists) in Python with memoized thunks: class Thunk: def __init__(self, f): self.evaluated = False self.val = f def __call__(self): if not self.evaluated: self.val = self.val() self.evaluated = True return self.val class Cons: def __init__(self, x, xs): assert isinstance(xs, Thunk) self.head = x self._tail = xs @property def tail(self): return self._tail() def nth(self, n): for _ in range(n): self = self.tail return self.head ones = Cons(1, Thunk(lambda: ones)) print([ones.nth(i) for i in range(10)]) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] def lazy_map(xs, f): return Cons(f(xs.head), Thunk(lambda: lazy_map(xs.tail, f))) nats = Cons(0, Thunk(lambda: lazy_map(nats, lambda x: x + 1))) print([nats.nth(i) for i in range(10)]) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] def lazy_zip(xs, ys, f): return Cons(f(xs.head, ys.head), Thunk(lambda: lazy_zip(xs.tail, ys.tail, f))) fibs = Cons(0, Thunk(lambda: Cons(1, Thunk(lambda: lazy_zip(fibs, fibs.tail, lambda x, y: x + y))))) print([fibs.nth(i) for i in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] I think laziness is pretty cool, but it does mix up two notions that turn out to be individually important: data and codata. Mixing them together makes a language's type system logically inconsistent, in the sense that you can't use Curry-Howard isomorphism anymore (nonempty types <-> true propositions). Data is, essentially, anything you can do structural recursion on and evaluate in finite time, no matter the evaluation strategy. Codata is fuzzier to me, but the canonical example of codata is the lambda abstraction. Haskell smears a layer of codata over all its algebraic datatypes (data) to make everything lazy. I once took advantage of this in a light way when designing a compiler targeting C in Haskell, with a goal of making beautiful-ish C code. The language, unlike C, was expression-based, so everything could evaluate to a value. The step that lowered expressions into C syntax returned a struct with multiple fields, each giving a piece of C syntax depending on how the expression was going to be used in context -- was the value of the expression going to be used? or just its side-effect? Then, due to laziness, only one of the fields of the struct would actually be evaluated. (It also handled other cases: lvalues and whether the expression's value was going to be immediately stored somewhere, since then the expression could use that location directly rather than creating a temporary variable if it might have needed one.)

eatonphil 4y ago

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 wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laziness_in_eager_languages https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...

mananaysiempre 4y 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 4y ago
  Right I forgot that everything is memoized. Thanks for the correction!

kmill 4y ago

In strict languages, you can delay computation by wrapping it in a zero-argument lambda -- i.e., a "thunk." For efficiency, you want to memoize thunks (that's what Haskell does[1]) so that they only ever evaluate once. Scheme has the "delay" operator to create memoized thunks, which you can later "force". It is true that these are not first class in the sense that you need to manually force the computation, but if it were automatic, how would you (efficiently) pass un-evaluated values around? [1] Incidentally, this is why Haskell's garbage collector needs to be able to deal with mutation. A thunk might graduate to an older generation, and once it is finally evaluated it can end up having pointers to the nursery or other younger generations.

moomin 4y ago
So I had a bit of fun implementing something like Haskell’s “Validation” in an eager language recently that has coloured my take somewhat. Basically “perform all these computations and tell me all the things that were wrong with my inputs” is way easier to express in a default lazy language than a default eager language. In default eager you’re constantly trying to figure out the largest number of operations you can do before can no longer continue. Yes, there’s weird perf things that can bite you, but there’s also a bunch of regular bread-and-butter coding things that pervasive makes very much easier.
- kmill 4y ago
  You really can simulate laziness in a strict language at the small cost of wrapping things in lambdas yourself -- you don't have to figure out what operations you can do yourself so long as you make everything that should be deferred deferrable (for example, if you're trying to do monadic fixedpoints you need to be careful). If you create your own lazy data structures, if your language supports it you can even have those thunks be forced for you automatically. For example, lazy streams (infinite lists) in Python with memoized thunks: class Thunk: def __init__(self, f): self.evaluated = False self.val = f def __call__(self): if not self.evaluated: self.val = self.val() self.evaluated = True return self.val class Cons: def __init__(self, x, xs): assert isinstance(xs, Thunk) self.head = x self._tail = xs @property def tail(self): return self._tail() def nth(self, n): for _ in range(n): self = self.tail return self.head ones = Cons(1, Thunk(lambda: ones)) print([ones.nth(i) for i in range(10)]) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] def lazy_map(xs, f): return Cons(f(xs.head), Thunk(lambda: lazy_map(xs.tail, f))) nats = Cons(0, Thunk(lambda: lazy_map(nats, lambda x: x + 1))) print([nats.nth(i) for i in range(10)]) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] def lazy_zip(xs, ys, f): return Cons(f(xs.head, ys.head), Thunk(lambda: lazy_zip(xs.tail, ys.tail, f))) fibs = Cons(0, Thunk(lambda: Cons(1, Thunk(lambda: lazy_zip(fibs, fibs.tail, lambda x, y: x + y))))) print([fibs.nth(i) for i in range(10)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] I think laziness is pretty cool, but it does mix up two notions that turn out to be individually important: data and codata. Mixing them together makes a language's type system logically inconsistent, in the sense that you can't use Curry-Howard isomorphism anymore (nonempty types <-> true propositions). Data is, essentially, anything you can do structural recursion on and evaluate in finite time, no matter the evaluation strategy. Codata is fuzzier to me, but the canonical example of codata is the lambda abstraction. Haskell smears a layer of codata over all its algebraic datatypes (data) to make everything lazy. I once took advantage of this in a light way when designing a compiler targeting C in Haskell, with a goal of making beautiful-ish C code. The language, unlike C, was expression-based, so everything could evaluate to a value. The step that lowered expressions into C syntax returned a struct with multiple fields, each giving a piece of C syntax depending on how the expression was going to be used in context -- was the value of the expression going to be used? or just its side-effect? Then, due to laziness, only one of the fields of the struct would actually be evaluated. (It also handled other cases: lvalues and whether the expression's value was going to be immediately stored somewhere, since then the expression could use that location directly rather than creating a temporary variable if it might have needed one.)