Boxed closures should be nameable, too

[jwise]

It would be really nice if it were possible for a boxed closure to recur on itself. A use case that I find particularly compelling is a variable substitution, which currently looks like this (impl version suggested by @nikomatsakis):

  /* this code is in an impl, e.subst(x, y) := [x/y]e */
  fn subst(gen: fn@() -> var, x: expr, y: var) -> expr {
    let fvs = x.freevars();

    type subst_encap = { gen: fn@() -> var, x: expr, y: var, fvs: map::set<var>};

    impl subst_ops for subst_encap {
      fn subst(e: expr) -> expr {
        alt e {
          e_app(e1, e2) {
            e_app(@self.subst(*e1), @self.subst(*e2))
          }
          e_lam(v, ep) {
            alt self.fvs.find(v) { /* v free in x? */
              option::none { /* no */
                e_lam(v, @self.subst(*ep))
              }
              option::some(_) { /* yes, alpha-vary \v.ep */
                let vp = self.gen();
                e_lam(vp, @self.subst((*ep).subst(self.gen, e_var(vp), v)))
              }
            }
          }
          e_var(v) {
            if v == self.y { self.x }
            else { e }
          }
        }
      }
    }

    let enc : subst_encap = {gen: gen, x: x, y: y, fvs: fvs};
    enc.subst(self)
  }

Previously, it was even worse; the inner function was something of the form 'fn subst_(...)', which passed 'gen', 'x', 'y', and 'fvs' all the way through, which was really painful.

@nikomatsakis then suggested that I file this bug. My suggestion is syntax of the form: fn@ subst_(...). The problem then is if we want functions that mutually recur; another thought, then, is an ML-style let rec func1 = fn@(...) {...} and func2 = fn@(...){...}.

Thoughts?

[nikomatsakis]

The annoying part is getting the scoping right. It seems so special case to introduce named fn@'s that can only recurse to themselves. On the other hand, introducing a let rec also seems like a lot of work for something that doesn't come up that often.

[jwise]

Right. I mean, one solution is to have named fn@s that also have ands -- i.e.:

fn@ func1(x: int) -> int {
  if (x == 0) { -1 } else { func2(x-1) }
}
and fn@ func2 (x: int) -> int {
  if (x % 3 == 0) { x * 5 } else { func1(x-1) }
}

But let rec is not just used for this, I should note. For instance, consider if I want a circularly linked runqueue:

enum runqueue_e {
  not_yet(),
  rq_next({tid: int, name: str, mut next: @runqueue_e}),
}

fn gen_init() -> @runqueue_e {
  let rq : @runqueue_e = @rq_next({ tid: 1, name: "init", mut next: @not_yet });
  alt *rq { rq_next(a) { a.next = rq; } not_yet() { } };
  rq
}

This is very painful, in part because an enum is needed (to get around the 'no recursive non-enumful types' issue), and in part because it's an extra step. (The enum is very painful, since it needs the 'alt' mess to get at the contents.)

This could be trivially rewritten with something of the form:

type runqueue = {tid: int, name: str, mut next: @runqueue};

fn gen_init() -> @runqueue_e {
  let rec rq : @runqueue = { tid: 1, name: "init", mut next: rq} ;
  rq
}

I mentioned this on IRC. @nikomatsakis noted that there are two issues here -- type-checking this (in particular, I think you now need to seriously think hard about how to infer the type of 'rq', if you wish to do so), and guaranteeing that intermediate states are not visible. Even if this is constrained to boxes, it's still possible for intermediate states to exist -- how do the MLs deal with this?

[jwise]

Talked to @msullivan today. Apparently the way the MLs do it is by saying that only lambdas are allowed to be let recs. So perhaps fn@ foo... and fn@ bar... is the right way to do it?

[pcwalton]

What about:

let mut foo, bar;
foo = fn@() { ... use bar ... }
bar = fn@() { ... use foo ... }

Edit: Oh wait, the closures copy. I guess you would need:

let foo = @mut none, bar = @mut none;
foo = some(fn@ { ... use bar.get() ... })
bar = some(fn@ { ... use foo.get() ... })

Blech.

[catamorphism]

Closing due to lack of consensus. Reopen if someone is still interested.