Expansion¶

One of the evaluator’s tasks is to expand templates and then evaluate the result of that expansion. This process occurs immediately on discovery of the use of a template and can use any Idio function (or template) defined so far.

Let’s just say, it gets a little involved….

Template Definition¶

Defining a template is straightforward enough. It’s a function that takes some arguments (unevaluated from the application of the template), does whatever it wants then returns some “code.” In particular we mean some “source code,” something that looks as though we might have typed it ourselves. Given that we’re in that weird world of homoiconicity, the “code” looks like a list of lists of lists etc..

We could return some literal source code like '(+ 1 2) – notice the leading quote to prevent the evaluator evaluating the source code into byte code thus preventing us returning the source code verbatim.

Returning a literal like that doesn’t look as though it’s going to handle variables very well so we might want to construct our source code dynamically along the lines of (list '+ 1 var) where we’ve some careful quoting of things we want to remain literals and not quoting of things we want the evaluator to expand on our behalf.

That becomes really complicated really quickly and so, naturally, we should leave it to the computer to do it for us. Hence, quasiquotation where we describe the structure of the source code in a quoted way and allow the variable bit to be expanded for us.

In Scheme they use the backtick symbol ` to start quasiquotation and the comma symbol for unquoting (meaning expand!) as in `(+ 1 ,var) which I find hard to read when it gets much more complicated than that. I guess you get used to it.

We simple scripting folk are more familiar with using the dollar symbol to represent expanding things and then we only need something to start quasiquotation. # introduces weird stuff, we’re calling this world templating so #T{ + 1 $var } it is.

So, within those lists we can ask for expressions to be evaluated and the results of that evaluation to be substituted in place. That’s beginning to sound complicated, let’s try an example. I’ll use the non-operator style inside the #T{...} construct to avoid the reader confusing matters by re-writing infix expressions:

define-template (my-plus-two sym val) {
  var := string->symbol (append-string "my-" (symbol->string sym))

  #T{
    := $var $(+ val 2)
  }
}

my-plus-two bob 3

Yes, yes, we haven’t done any type checking!

The template, my-plus-two, takes two arguments, a symbol and a value. We create a local variable, var, which is the “symbolification” of the string concatenation of "my-" and the “stringification” of the symbol passed in.

The “code” we return inside the #T{...} construct wants to be an assignment operator, the value of the var variable and then the value of the expression (+ val 2).

The overall result of which is that we would expect the call to the template, my-plus-two "bob" 3 to result in the “code”:

:= my-bob 5

Quasiquotation¶

It’s not quite that easy, though, and here we start getting a bit meta. There’s going to be two evaluations, for a start!

The #T{...} expression (quasiquote in Scheme) is our first port of call. Ultimately it needs to produce some “code” from the expression := $var $(+ val 2), its body form(s).

There’s a two step process, even here. At some point the evaluator will have recognised that this is a quasiquote expression, the #T bit should have been a clue.

we have to expand the quasiquote expression

Here we’re looking to recursively descend the expression toggling the state of “expansion” and returning a data structure for the evaluator to, er, evaluate into the desired result.

Quasiquote expansion’s job is not to evaluate anything but return a construction with the quoting figured out. We’ll use the evaluator afterwards to figure out what the resultant expression should be.

The default state of quasiquotation is quoted. You get back what you put in.

However, if a (sub-)expression is “unquoted” then we should not quote it but rather allow it to be evaluated. As we descend into this unquoted expression we will very likely encounter another quasiquoted expression in which case quoting is re-enabled, and so on.

The final “code” will be a list of things but we’re not there yet. We’re in an intermediate stage, here, where we’re merely toggling quoting on and off and entities like var and val are just symbols in the mix – nothing in the quasiquote expansion knows anything about the values of var and val.

That means the output of quasiquotation expansion should be something that, when evaluated, would construct a list (of lists …).

In our example, to construct that “code” by hand, knowing the expected result, we could have written the following:
```
list ':= var (+ val 2)
```
Notice something subtle, here. For a start we’re not returning the final form, we’re returning something that creates the final form.

Secondly, the assignment operator is quoted but nothing else is. So, if we were to ask the evaluator to take a look at this we would expect it to be treated as a regular bit of source code in which those arguments will get evaluated as list is just a regular function.

In which case it is the function list with arguments: the quoted symbol :=, whatever var evaluates to plus the result of the evaluation of the expression (+ val 2).

*

Of course, the fact that we knew the result and could figure out the condensed answer doesn’t mean the quasiquotation expander can. Instead, it will plod through creating a result from much more fundamental parts, pairs:
```
pair ':= (pair var (pair (+ val 2) #n))
```
which will result in the same thing.
Now, as noted above, if we ask the evaluator to figure out that expression then the evaluator is in a position to replace references to var and val with some variable references.

By invoking idio_meaning() on the output of quasiquote expansion we get two benefits:
1. idio_meaning() will descend all of the expression so that if the result of quasiquote expansion contained the use of another template then we will expand that template in turn.
  
  Templates calling templates calling…
2. templates really are just regular functions, so var is a local variable in the body of the template and val is a parameter to the template
  
  Templates really only differ in that they are flagged as expanders internally so the evaluator can identify them, and that the value they return is itself evaluated in turn (we’ll get to this!).
In this case there are no addition templates, only expressions that need evaluating. If we could peek halfway we’d now see:
```
list ':= my-bob (+ 3 2)
```
idio_meaning()’s job is, normally, a pre-cursor to calling the code generator to generate some byte code, however, in this case, we’re using it to figure out the intermediate code for the quasiquote expression on our behalf.

When we return the result from idio_meaning() it’ll just be like any other calculated chunk of intermediate code from any other expression. The only novelty, here, is that we are using it on self-generated code rather than user-supplied code.

As this will ultimately be sent to the code generator we’ll end up with some byte code to run the code for list ':= var (+ val 2) which, when run would result in:
```
(:= my-bob 5)
```
a list of three elements: :=, my-bob and 5.

In other words, some code.

That’s just the result of finding the meaning of the quasiquotation expression, the result of the template invocation.

—

While we’re tying ourselves in meta-knots, you can use quasiquotation at any time. There’s a tendency to use it as the return value in a template because of its code-generating nature but if you want it to generate some code (unlikely) or a data structure (much more likely) then it’s just as good for you. Suppose you wanted to construct an element for an association list:

Idio> var := 'my-bob
my-bob
Idio> val := 3
3
Idio> #T{ $var $(+ val 2) }
(my-bob 5)

Of course you could have just called list var (+ val 2) but where’s the fun in that?

Re-Evaluation¶

When you use a template, the body of the template is run (including that final meaning of the quasiquotation expression) and, in this case, we’ll get back the “code” (:= my-bob 5).

There’s still one last trick. We’ve said all along that the result of using a template will be evaluated. So, we throw that resultant “code,” (:= my-bob 5), at the evaluator. In other words we can look at our original template invocation:

my-plus-two bob 3

and imagine that it was replaced with:

:= my-bob 5

and the evaluator now runs on := my-bob 5 which will (finally!) give us our desired assignment.

Phew!

Expansion Space¶

When we’re running a template expansion we’re in a strange halfway world of creating new source code – something you did completely separately from Idio with your favourite text editor, cat, right?

https://imgs.xkcd.com/comics/real_programmers.png

– and this code creation process may use a couple of tricky features.

On the one hand it may use some inter-call state variables, think about giving every new class a unique identification number before it piles a slew of accessor functions into your namespace. That number has to be kept somewhere, preferably where it isn’t going to clash with what the user is doing and, even more preferably, somewhere where the user isn’t likely to endanger it.

On the other hand, the expansion of this template might provoke the expansion of another template. The first template is now acting much like the user in the first scenario, the second template should, by rights, be running somewhere where the actions of the first template and it will not interfere. Especially so if this template in a template is creating accessor functions left right and centre.

The answer to this recursive conundrum is to have template expansion run in a new namespace/module, which we might call, *expander* which should be adjoint to the current module. If another template requires expansion from this first template then it should be run in a module called *expander* adjoint to the first *expander* module.

We should see a tree of *expander* modules indicating the levels of expansion we’ve attained. This is an idea explored by Christian Queinnec in Macroexpansion Reflective Tower ([Que96]).

We don’t currently, we just get the one. Play nicely, everyone!

Timing¶

Changing what is being unquoted makes all the difference to how the resultant code behaves, so:

#T{
  := $var (+ $val 2)
}

will get you pair ':= (pair var (pair (pair '+ (pair val (pair 2 #n))) #n)) where only the evaluation of val will occur, not (+ val 2) giving the final “code” of:

(:= my-bob (+ 3 2))

Whether you want the value 5 or the function call (+ 3 2) is up to how you want the assignment to perform. In this instance, integer addition makes little difference but would make a huge difference if you were looking a key up in a table. In one case the key will be looked up at the time of compilation (probably bad) and the other at run time (probably good).

*

You don’t normally get to see these quasiquotation expansions as they are immediately thrown at idio_meaning() however a judicious call to:

idio_debug ("dq=%s\n", dq);

in idio_meaning_quasiquotation() is very helpful if you subsequently type the #T{...} expression at the prompt.

Mechanisms¶

Finding sources for template expansion is a little tricky, more so since there are two phases: quasiquotation expansion and template expansion.

Quasiquotation Expansion¶

In the C version of the evaluator I implemented a version along the lines of the one in lib/compiler.stk in the STklos distribution, partly as I could follow what it was doing. I see that there’s a very similar implementation to the STklos one in lib/init-7.scm in Alex Shinn’s Chibi-Scheme.

Nils M Holm opts for a double function solution in S9fES in qq-expand. A rummage on the Intertubes leads you to the appendix of Alan Bawden’s Quasiquotation in Lisp paper ([Baw] –where I can’t find a published date nor publisher) where he disparages Scheme implementations of the day for using cons (pair in Idio) because it won’t handle nested quasiquotations containing splicing properly.

In the interests of fairness, I’ve implemented the QiL variant (which uses list and append) in the Idio variant of the evaluator.

The QiL solution, slightly reworked looks like:

file:evaluate.idio¶

define (qq-expand-list e) {
  if (pair? e) {
    sym := ph e
    (cond ((eq? 'unquote sym)          #T{ (list $(pht e)) })
          ((eq? 'unquote-splicing sym) (pht e))
          ((eq? 'quasiquote sym)       (qq-expand-list
                                        (qq-expand (pht e))))
          (else                        #T{ (list (append
                                                  $(qq-expand-list (ph e))
                                                  $(qq-expand (pt e)))) }))
  } {
    #T{ '($e) }
  }
}

define (qq-expand e) {
  if (pair? e) {
    sym := ph e
    (cond ((eq? 'unquote sym)          (pht e))
          ((eq? 'unquote-splicing sym) (error 'qq-expand "illegal"))
          ((eq? 'quasiquote sym)       (qq-expand
                                        (qq-expand (pht e))))
          (else                        #T{ (append $(qq-expand-list (ph e))
                                                   $(qq-expand (pt e))) }))
  } {
    #T{ '$e }
  }
}

which, let’s be honest, looks a bit intimidating.

Template Expansion¶

For the template-expand and template-expand* functions I’ve followed in the style of STklos’ lib/runtime.stk which itself appears to be following in the style of Dybvig, Friedman and Haynes’ Expansion-Passing Style: A General Macro Mechanism ([RKD88]).

To perform template expansion we need to go a bit meta. We want to loop recursively expanding templates until we run out of templates to expand. To manage that we have embedded the actual template function inside an expander which takes a uniform pair of arguments: the expression to be expanded, x, and an “expansion” function, e. By passing e it is the “expansion” passing style. e only really gets used in application-expander.

The original template definition, define-template (name formal*) body, is reworked into define-template name (function (formal*) body) or define-template name proc.

We can use proc in the expander by defining it as:

expander = function (x e) {
   apply proc (pt x)
}

remembering that x is the whole expression name args and therefore pt x is equivalent to args.

The entry point for expansion is always initial-expander and the nominal value for e is also initial-expander.

initial-expander looks at the expression and decides if it is:

an atom – return it
a template – use the template’s associated function to do the expansion
or we call application-expander

application-expander descends into x and asks e to expand each element – of course we pass e into the expansion otherwise it wouldn’t be EPS!

e doesn’t have to be initial-expander. The EPS paper suggests an expand-once function with a do-nothing e:

define (expand-once x) {
  initial-expander x (function (x e) x)
}

thus preventing the recursive descent.

Last built at 2024-12-21T07:11:00Z+0000 from 463152b (dev)