searching for signal

This is part 2 of a series that started here.

First, a quick correction: I claimed that Lisp macros didn't have the
ability change the basic syntax of Lisp. I believed that because I
hadn't yet learned about "read" macros. Using "read" macros in Lisp
you can indeed adjust some pretty basic syntax rules. That can't be
done in JaM yet, but it's something that can probably be added in
later.

So let's look more closely at the first stages of what JaM does.
As stated previously, JaM.include("foo.js") fetches a
JavaScript source file as text. It then passes that text to
JaM.eval( ... ). The eval function does a
lexical analysis of the text (currently using code from JSLint) to generate a
JavaScript array of token objects.

A JaM token object is basically just a JSLint token object. For each
word read from the JavaScript source, it contains the word itself, the
line number and column where it was seen, and other bits of meta-data.
Here's a couple of examples:

{
  value: "function",
  line: 99,
  character: 16,
  reserved: true,
  identifier: true
}

{
  value: "'bar'",
  line: 134,
  character: 32,
  type: '(string)'
}

I'm not sure if all this will be needed or useful in the long run, but
JSLint produces it, and I have no good reason to throw any of it away.
So far the "value" has been the only part that is has regularly been
useful in the macros I've written.

Next, eval uses a few simple grouping rules to generate a
tree of nested arrays of token objects. For example, the JavaScript
expression "alert('hi!');" would be translated into the following
tree:

  [
    { value: "alert", ... },
    [
      { value: "(", ... }
      [
        [
          { value: "'hi!'", ... }
        ]
      ],
      { value: ")", ... }
    ],
    { value: ";", ... }
  ]

These grouping rules have to be simple and loose because they must
correctly parse not only normal JavaScript but also the code which
will be the input to all our macros. (This is the stage where we
could be using Lisp-like "read" macros instead of it being hardcoded
as it is in JaM currently).

For example, if we plan to define a unless macro, JaM at
this stage does not know what the word unless means, but
it needs to generate an appropriate tree anyway. So for this
expression:

  unless( false ) { alert( 'hi' ); }

JaM generates the tree below. For brevity I'll show just the value of
each token object:

  [
    "unless",
    ["(",[["false"]],")"],
    ["{",
      [
        [
          "alert",
          ["(",[["'hi'"]],")"],
          ";"
        ],
        []
      ],
    "}"]
  ]

This nested tree of token objects is the data structure that JaM
macros operate on. What exactly a macro might do with with this
structure will be covered in the next installment.

A couple weeks ago I was reading Paul Graham's excellent book href="http://www.paulgraham.com/onlisp.html">On Lisp, and I was
struck with the thought that many of the features of Lisp he seems to
really like are also provided by JavaScript. These include dynamic
typing, lexical variable scoping, first-class functions, closures,
etc. But macros are of course completely missing from JavaScript.

How hard would it be to add Lisp-like macros to JavaScript, I
wondered? I'm learning about Lisp macros for the first time here, so
I didn't really know, but I thought it would be fun to try.

This will be the first of several posts describing "JaM", my
attempt to add Lisp-like macros to JavaScript.

It seems to me there a few essential ingredients to make a macro
system for JavaScript that is as powerful as Lisp's:

1. Macros are written in JavaScript with access to all functions
   defined up to that point.
2. The source code that the macros read and write is in a format
   that is easy for JavaScript to manipulate, such as a
   JSON parse tree, not just a big string.

Number 1 is important, because otherwise you end up with something
like C or C++ macros -- a weak mini-language that looks and acts
differently than the host language. I suppose it's better than
nothing, but it doesn't have nearly the language-building power that
Lisp macros do.

As for number 2, I suppose it would be possible to set up a system
where each macro could match based on a regex or something equally
flexible, but this would have a couple of drawback. First, most
macros wouldn't need that flexibility and would end up reimplementing
the same patterns as other macros, including tricky things like
matching up pairs of parens, curly braces, etc. Second, I don't want
to try to read code that's being worked over by macros that are that
flexible. I'd like to be able to assume that each macro is
constrained in its scope, following roughly the same rules as the core
JavaScript language. Lisp macros certainly have this restriction, so
I'm not worried about this causing my macro system to be too weak.

Let's start off with a function JaM.include("foo.js"),
which will fetch the JavaScript file, expand any macros in it, and
then run it through the regular JavaScript eval(). Except it's not
quite that simple because we want to be able to mix function
definitions and macro definitions after each other in any order so
they can build on each other. So we'll need to split "foo.js" into
top-level expressions that can be correctly evaluated. I'll leave the
details of this step for another time, but what's important is that
for each top-level expression we will expand any macros and then
evaluate it before moving on to the next expression.

This will probably be very slow -- certainly slower than just
letting the JavaScript interpreter have at foo.js directly. But if
that's the sort of thing that worries you, perhaps you'll be comforted
by these thoughts: First, as described here the parsing, macro
expansion, and separate evals happen once when a new source file is
being loaded. Once the code is up and running there may be no need to
do further macro expansion. Second, we could add another step to the
processing of each top-level expression: after expanding any macros in
an expression we could save the resulting code before evaluating it.
Doing this with each expression in turn would result in a file full of
fully-expanded normal JavaScript that browsers could run directly and
at full speed.

Ok, that was pretty dull; perhaps I can whet your appetite with
some sample code? Let's say you really like perl's
unless keyword, and you wish JavaScript had something
similar. With JaM, you can add it yourself:

defMacro unless( expr, block: body ) {
  return {{
    if( ! ( #expr ) ) {
      #body
    }
  }};
}

unless( true == false ) {
  alert( 'Hello, macro-enabled world!' );
}

It may not be the most useful example one can imagine, and even so
I feel I've got a fair bit more to explain before it'll make much
sense. We'll build our way up to defMacro,
{{ ... }}, and the # operator
over the next few posts. Hopefully, though, all of the above will be
sufficient for you to understand where I'm headed.