template symbol binding (dynamic scope handling)

[saem]

Recently in chat a discussion started about how to handle single pass symbol
resolution for templates. @zerbina and I discussed some preliminary thoughts
and we both seem to be leaning towards making use of a new symbol kind to
track a binding scope.

During the discussion I realized my own thinking was fuzzy, so I collected my
thoughts a bit and recorded them (see below). Hoping to use this thread to
memorialize some of the ideas and direction.

[saem]

Here is my current thinking, it's early so I'll likely change my mind over the course of discussion.

---

How templates should work

NB:

• purposefully written without thinking too much about current implementation
• this is my mental model and thinking about what to strive for

Quick Version

In their simplest form template declarations are a "function" of the form: definingContext -> callingContext -> seq[param] -> ast. The analysis of a template declaration results in callingContext -> seq[param] -> ast. When a template call is analysed so we know which template definition to dispatch we pass it a callingContext and we get: seq[param] -> ast. To wrap up the analysis passes in the params and we finally end up with ast.

More Details/Long Version

Each step is basically partial application, the two contexts are likely the most alien parts, so I'll describe what they're for first.

When we give it a definingContext we end up with a partial function which can:

• can resolve template locals
• can resolve up the scope chain at the definition site
• basically it closes over definitions

When we give it a callingContext we end up with a partial function which can:

• can resolve all call site locals
• can resolve up the scope chain at the call site
• this is boring old lexical scope

Since this is all partial application the actual resolution of the identifiers in the partially applied function can be deferred to the callsite. As an optimisation we can partially evaluate the definition resolving all the immediately known bits and leaving the rest for the callingContext and params.

If you're curious how we get a callingContext into the partially applied template at the callsite. I think of the partially applied function as having a template "calling convention", which instructs dispatch to pass in the callingContext -- I thought this was especially cute.

Issues/Solution Sketch

The problem with all this is that macros are horrible destructive little monsters, that can mess stuff up. :( For this I think the best approach would be that the AST emitted by the template call is representative of the "activation record" of the template. Meaning something like:

# given mymodule.nim

template foo(a: int) =
  a * 2

var a = 11

foo(3)

#[ expands to (mix of tree and syntax, hope it's clear enough):
stmtList:
  let genSym"foo" {.definingCtx: "mymodule.foo".} # used by sym resolution
  let a {.templateParam.} = IntLit(3) # registers in the `definingCtx`
  infixCall
    ident"*"
    ident"a"
    intLit 2
]

In the expansion the first line within the stmtList adds a definingCtx, think of it as a sort of temporary. All lookups will now use the defining context identified by the fully qualified template name, "mymodule.foo". Mechanically, the defining context remembers all the lookups at time of definition, closing over them. This ensures that template security can't be violated at least wrt what private items can be accessed... although how many times they're accessed and the order can be altered via a nasty macro (rude!). Everything not closed by the definingCtx falls back to the previous definingCtx or, if none, good ol' lexical scope.

Scoping the definingCtx to the stmtList means it naturally dies and lookup goes back to using whatever came before (another defining context or if those are all gone good ol' lexical context.

Finally, resolved symbols storing a ref to the definingCtx or none if lexical scope feels like the beginnings of flattening the stmtList.

Thoughts

• I like the smallness
• I really like the lack of redex cruft
• I like how it turns dynamic scope sorta lexical
• there is still a security boundary problem with templates -- present today
• I like how moving things or trying to reference them in the wrong spot breaks as it should and vice versa
• I don't like the incompleteness of it, but I do like the questions it forces
• the racket folks went a different route and I wouldn't think much of it, except for the fact that they're world class researchers in the field

[saem]

Things which might be worth clarifying which I ran out of time for, how resolution should work/differ for:

1. Immediate templates
2. typed, untyped , typedesc, and typed expr template return values
3. Dirty templates

Relevant changes to any other semantics