Löb with Promises

Javascript is an imperative, eager language with mutable data structures, so things like circularly linked lists are easy to create. What an eager language can’t do well is infinite data structures; instead one has to fake laziness using some other technique. The traditional one is to use closures: instead of manipulating values, you manipulate functions that take no parameters and return values. I wrote an article on that approach back in 2012.

There’s a fun connection between Löb’s theorem and type theory that results in a “spreadsheet functor“. Unfortunately, in Javascript that approach has the downside that following links creates new objects. You expect this for infinite data structures, but not for circular ones. It also has terrible performance, recomputing all the values a cell depends on for each cell. Surprisingly, these bugs can even crop up in Haskell; Haskell’s lazy, but you have to use it properly.

Promises are a different approach to deferring execution of code until later. Here’s an implementation of the spreadsheet functor that uses Promises and both gets allocation right as well as cacheing the results of computations so they can be reused later.

const r = Promise.resolve().bind(Promise);
const s = r();
const defer = s.then.bind(s);
const ploeb=(formulas) => {
  var results = formulas.map(
    (formula) => defer(() => formula(results))
  ); 
  return results;
}; 
const q=ploeb([
  (c) => r({val:0, next:c[1]}),
  (c) => r({val:1, next:c[0]})
]); 
let x = await q[0];
console.log(x.val); // 0
console.log(x.next === q[1]); // true
x = await x.next;
console.log(x.val); // 1
console.log(x.next === q[0]); // true
x = await x.next;
console.log(x.val); // 0
x = await x.next;
console.log(x.val); // 1