Re-reading Paul Graham, specifically The Hundred-Year language helped me understand that I need to write down the axioms of XL. I need to describe XL’s equivalent of lambda-calculus for Lisp. If there is such a thing.

Lisp inventions

In Revenge of the Nerds, Paul Graham makes a list of the 9 things that Lisp invented

  1. Conditionals
  2. Function types (i.e. functions as first-class items)
  3. Recursion
  4. Dynamic typing
  5. Garbage collection
  6. Programs composed of expressions (no statements)
  7. A symbol type
  8. A notation for code using trees of symbols and constants (programs as data).
  9. The whole language there all the time (no distinction between load time, compile time and run time).

Of these, many became part of mainstream languages over time. Some remain the exception rather than the norm.

What makes XL unique

Later in that same essay, however, Paul Graham unknowingly explains that makes XL unique in my opinion (emphasis mine):

Macros (in the Lisp sense) are still, as far as I know, unique to Lisp. This is partly because in order to have macros you probably have to make your language look as strange as Lisp. It may also be because if you do add that final increment of power, you can no longer claim to have invented a new language, but only a new dialect of Lisp.

What XL demonstrates is precisely that you can have Lisp-style macros (and in fact build a whole language on macros) without the hairy syntax. Here is how you use ‘if then else‘ in XL (whether the imperative variant XL1 or the functionalish variant XLR):

    if A < 0 then
        write "A is negative"
        write "A is positive or null"

This code should look really familiar to users of other languages, I would hope. Yet under the hood, it corresponds exactly to a simple parse tree similar to what Paul Graham refers to in his point #6. Here is what that parse tree will look like if you expand it:

% ./xl -parse ifthenelse.xl -style debug -show
(infix else
 (infix then
   (infix <
  (block indent
    "A is negative")))
 (block indent
   "A is positive or null")))

The big difference with Lisp is that Lisp, as Paul Graham points it out, has no parser. XL has a simple parser, but a parser nonetheless.

Axiom #1: A simple parse tree improves code readability

This leads to axiom #1 of XL: you can parse text with 8 node types or less. The 8 node types currently found in XLR are:

  1. Integer: Numbers like 1234
  2. Real: Numbers like 3.1415
  3. Text: Literals such as "ABC" or 'X'
  4. Names and symbols: Names contain letters and digits, like HelloWorld or X0, symbols contain other characters such as ; or ->
  5. Prefix: Adjacent nodes where the first one defines the operation, such as sin x or -3.
  6. Postfix: Adjacent nodes where the second one defines the operation, such as 3! (factorial of 3) or 24in (24 inches)
  7. Infix: Adjacent nodes separated by a name or symbol which defines the operation, such as 3+4 or X and Y
  8. Block: A node surrounded by separators, such as (24-3) or the second half of the prefix A[3].

This can be reduced to less than 8 relatively easily: the real and integer types could be merged into a “number” type, the prefix and postfix could be merged into a “positional” operator, which could be made more general, for instance allowing “above” and “below” notations.

In practice however, the choice currently implemented in XL is a practical trade-off. For instance, the natural computer representation of integers and real numbers are different, so it makes sense to treat them as separate from the beginning.

Of note, in XL, indentation is represented by a block, and line separators are just another kind of infix.

The benefit of this representation compared to the Lisp representation is that it is only marginally more complex (4 constructed node types instead of one, the list), but allows us to parse things much closer to the way humans do. For instance, XL will parse 2+3*6 the right way.

Axiom #2: Programs can be evaluated with macros

Despite what Paul Graham says, Lisp really has two “modes” of operation: macros/compile-time and evaluation. The distinction is subtle: Macros (and compilers) evaluate one program to transform another program, whereas evaluation evaluates the program itself.

In the XL1 compiler (the XL imperative language), the distinction is more marked than in Lisp, whereas in XLR (the XL runtime language), it is less clearly visible. Let me illustrate with an example of each.

In XL1, you would define a recursive factorial as follows:

function Factorial(N : integer) return integer written N! is
    if N = 0 then
        return 1
        return N * (N-1)!

That example looks really similar to what you would write in C or Ada or whatever other imperative language you can think of. But the parse tree is there, not too far. One example is the notation written N!. This allows the compiler to recognize that (N-1)! is really a call to Factorial. This is called expression reduction. This is already quite useful, but basically it’s a compile-time only thing.

Under the hood, however, the XL1 compiler uses the exact same mechanism to recognize (N-1)! and to recognize if-then-else. The exact same macro rewrite mechanism is at play. In fact, you can extend the compiler easily with your own “macros”, so that for example you could write d/dx(sin x) and have the compiler rewrite it for you as cos x. This particular differentiation plug-in has been in the compiler for several years now.

In short, the language looks imperative, but it’s implemented as a big set of macros.

By contrast, in XLR, you would define the same function as:

0! -> 1
N! -> N * (N-1)! 

The code is much shorter, because XLR basically has only one built-in operator, which is the macro rewrite operator ->. XLR is little more than a big macro pre-processor. Now, if XLR happens to dynamically generate machine code using LLVM to evaluate this quickly enough, it’s just an optimization, an evaluation strategy.

As a result, in XLR, evaluation and macros are practically the same thing, even more so than in Lisp in my opinion.

Axiom #3: C+ hackers and Lisp hackers are both right

Depending on whether your favorite language is C or Lisp, Ada or Haskell, Java or Python, you may prefer the first or the second approach. It’s really a matter of taste, and after years of healthy competition, the two camps are not any closer to being reconciled

What XL brings to the table is a single technology that demonstrably can do both.

Axiom #4: It works, almost

Well, today, XL does neither too well, mostly because the technology is not finished. It has never stopped making progress in the years since the project began, though. If you want to contribute, go to the XL web site


4 thoughts on “The XL axioms: reconciling Lisp and C++ hackers

  1. Bonjour Christophe,et bravo pour XL, le langage à l'air vraiment très intéressant.Est-il encore développé et utilisable (j'ai une contrainte de taille: je suis sous Windows)?Merci.

  2. Bonjour Kib,Il y a deux langages. Le langage impératif est en "pause" pour l'instant. Le langage fonctionnel est l'objet d'un développement actif, dans le cadre de l'utilisation par la société Taodyne que je suis en train de créer.Concernant Windows, les deux projets fonctionnent à peu près via MinGW, un peu moins bien sous Cygwin. Il y a quelques problèmes liés au scripts de test (pas de ln -s décent sous Windows, problèmes CR/LF).Merci de ton intérêtChristophe

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s