[kazinator]

In what language do we input code as HOAS, and target that representation with macros?

(Can't we expand macros in a conventional representation with symbols and environments and then go to HOAS?)

(It's not news that macros are weak in some sense; I mean you can shoot yourself in the foot with the classic non-hygienic ones; you can disrespect even the first order abstract syntax that you're working in: the macro can re-locate a piece of raw syntax which contains identifier references into the wrong scope where those references resolve otherwise.)

Anyway, have fun fishing for mackerel with your bear trap?

[catnaroek]

The “conventional” representation of syntax using explicitly named variables is utterly inconvenient and error-prone for anything other than parsing. The very first thing I want to do after parsing is convert the syntax tree to de Bruijn indices/levels or HOAS.

[kazinator]

You could expand some conventional macros first, then go to HOAS with what is left (and then do another pass with a separate HOAS macro system, perhaps).

How the heck do you handle hierarchical run-time environments in these representations? Especially mutable ones? If we have this:

  (let (a b c)
     (let (d e f)
        (lambda ())) ;; escapes somehow
     (let (g h i)
       (lambda ()))) ;; ditto
     (lambda ())) ;; ditto

These lambdas capture different, overlapping environments which share the (a b c) bindings. If there is an inner loop which repeatedly instantiates the (d e f), then new closures are made with different instances of these variables: yet those closures all share the same (a b c) bindings.

So we can't just flatten the entire lexical scope to some HOAS terms and pretend that its hierarchical structure doesn't exist.

[catnaroek]

Mutable shared environments is an absolutely terrible idea. All this achieves is to gratuitously make it unsafe to call in parallel multiple closures created in the same environment. A saner approach is to let variable bindings be immutable, and only then let some variables have (not necessarily static) type “mutable cell” (something like Rust's `Rc` or `Arc`).

[kazinator]

Even if environments are immutable, the problem has to be solved somehow that the environments are hierarchical. Newly instantiated versions of a sub-environment share the same super-environment. For instance, a local tail call occurring in the scope of some stable outer bindings, capturing different versions of the tail call inner variables.

[catnaroek]

I fail to understand why hierarchical environments pose a problem for HOAS. Environments map variables to their values, and they're used to give meaning to non-closed terms (containing variables that aren't bound within the term itself).

The whole point to HOAS is making unbound variables irrepresentable in the first place (which is the source of the accidental variable capture problem), eliminating the need for environments as separate data structures. For example, this is the HOAS representation of closed terms of the untyped lambda calculus:

    datatype term = Lam of term -> term
                  | App of term * term

Note there is no need for a separate constructor for free variables.