How to implement letrec in Javascript?

Question

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?

nested bindings are defined with `let*`, mutually recursive bindings - with `letrec`. `let*` just translates into a series of nested one-binding `let`s, much like what you've shown. there's no recursion involved in this, no closures. — Will Ness, Feb 01 '20 at 13:21
`bind` has no type, but you can give its invocations a type provided you assert the types of the default parameters. [Playground](http://www.typescriptlang.org/play/?ssl=1&ssc=14&pln=1&pc=17#code/MYewdgzgLgBARgSzAExgXhgHgIID4AUAZgFwz4CU6uM2la1hFA3AFAuIr74AexYArgFs4AUwBO6GACYANDACefIaIkZuMAFQxucgF5Lh4yfM0K61ANo6FegLrkgA) — , Feb 01 '20 at 15:04
Why not just use `const` and `return`? Not everything needs to be an expression. — Aadit M Shah, Feb 01 '20 at 15:16
@AaditMShah I love statements. What would life be without making and listening to statements? I just want to learn how local bindings are related to recursion. As I understand Will's comment `let*` depends on macros and is transformed to nested `let` during expansion. So the key to my q seems to be mutual recursion. — , Feb 01 '20 at 15:32
but there is no mutual recursion in the example that you show. there is no shared scope, only nested scope. see also [this](https://stackoverflow.com/questions/15003518/confused-by-the-difference-between-let-and-let-in-scheme/15006018#15006018). — Will Ness, Feb 01 '20 at 18:19
@WillNess I was referring to your 1st comment. You mentioned `letrec` depends on mutual recursion. At least this is how I interpreted it. — , Feb 01 '20 at 18:22
not depends, expresses. you said "the key to [this] Q is mutual recursion", so I responded to that. just to clarify. — Will Ness, Feb 01 '20 at 18:22
This would be useful for any kind of recursive data structure. Wanted to use this for simple objects that can reference themselves while preserving the types. — CMCDragonkai, Jul 05 '22 at 04:53

CMCDragonkai · Answer 1 · 2022-07-05T05:18:54.703

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.

How to implement letrec in Javascript?

1 Answers1