The only PL example I can think of is unification, which logic programming has as well as evaluation.
A programming language where you can write programs to rewrite programs.
It appears that author of Pure is prone to come up with PL names that are quite unsearchable.
See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...
let y = f(x) in g(y, y)
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,
[1] https://srfi.schemers.org/srfi-45/srfi-45.html
[2] https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf, https://youtu.be/S69UOGqda8w
[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.
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.
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 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.)
But, the effort to implement call-by-need evaluation (graph rewriting or remembrance of computed value) is higher in strict languages than (sparse) addition of annotations in lazy ones.
There is also another GHC extension called bang patterns to request strictness on pattern matches.
The original bang (`!`) which is Standard Haskell can make fields of data structures strict, see: https://wiki.haskell.org/Performance/Data_types#Strict_field...
In general both lazy and strict languages can be strict or lazy. But the way it shows in the data types is different. A strict language can defer evaluation by adding a level of abstraction (instead of type `X` you have `() -> X`). A lazy language can force evaluation (it will have to evaluate at some point anyway) but you might not see it in the type. I’m not sure which one is better to be honest. Being able to infer laziness/strictness from the type is nice, but it also hinders interoperability.
Also, your suggestion will result in identical code being copied for different contexts. Consider lazy structures in OCaml and C#.