How to implement letrec in Javascript?

231 views Asked by At

The following combinator uses default parameters in a creative (some would say abusive) way and it behaves kind of like Scheme's letrec*:

* Please correct me if I'm wrong, I don't know Scheme well

const bind = f => f();

const main = bind(
  (x = 2, y = x * x, z = y * y, total = x + y + z, foo = "foo") => [x, y, z, total, foo]);

console.log(main);

It works but bind has no type. Next I tried to manually encode the above main function:

const app = x => f => f(x);

const main = app(2) (x =>
  app(x * x) (y =>
    app(y * y) (z =>
      app(x + y + z) (total =>
        app("foo") (foo => [x, y, z, total, foo])))));

console.log(main);

It may work but it is hideous. How can I avoid the nesting? I've played around with fix and recursion but I have no clue how to express closures this way:

const fix = f => x => f(fix(f)) (x);

const letrec3 = f => fix(rec => acc => x =>
  acc.length === 2
    ? acc.reduce((g, x) => g(x), f) (x)
    : rec(acc.concat(x))) ([]);
    
const main = letrec3(x => y => z => total => foo => [x, y, z, total, foo]) (2) ("2 * 2") ("4 * 4") ("2 + 4 + 16") ("foo");

console.log(main);

Is there a recursive algorithm that effectively creates closures or local bindings, so that the current binding may depend on the previous ones?

1

There are 1 answers

0
CMCDragonkai On

It seems the bind can be replaced by an IIFE. Furthermore, you can refer to local bindings or global bindings by using [x]:

Here's an example

const data2 = ((
  x = 2,
  y = x * x,
  z = y * y,
  total = x + y + z,
  foo = "foo",
  what = { x, y }
) => ({
  x,
  y,
  z,
  total,
  foo,
  what,
  haha: {
    what
  },
  zzz: ((
    x = 10
  ) => ({
    [x]: 3,
    [y]: 4,
  }))(),
}))();

console.log(data2);

I think you'd need a macro library to make this elegant enough to use. Otherwise there's a lot of braces needed. Plus the fact that JS object keys can have things like - and arbitrary strings, but JS variable names cannot.