4 ms·

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 w

by 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.)

by kmill 4y ago

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.)