In what sense are languages like Elixir and Julia homoiconic?

by

In the words of Bill Clinton, “It depends upon what the meaning of the word ‘is’ is”. Well, ok, not really, but it does depend on what the meaning of the word “homoiconic” is. This term is sufficiently controversial that we no longer say that Julia is homoiconic – so you can decide for yourself whether it qualifies. Instead of trying to define homoiconicity, I’ll quote what Kent Pitman (who knows a thing or two about Lisp) said in a Slashdot interview back in 2001:

I like Lisp’s willingness to represent itself. People often explain this as its ability to represent itself, but I think that’s wrong. Most languages are capable of representing themselves, but they simply don’t have the will to. Lisp programs are represented by lists and programmers are aware of that. It wouldn’t matter if it had been arrays. It does matter that it’s program structure that is represented, and not character syntax, but beyond that the choice is pretty arbitrary. It’s not important that the representation be the Right® choice. It’s just important that it be a common, agreed-upon choice so that there can be a rich community of program-manipulating programs that “do trade” in this common representation.

He doesn’t define homoiconicity either – he probably doesn’t want to get into a definitional argument any more than I do. But he cuts to the heart of the matter: how willing is a language to represent itself? Lisp is willing in the extreme – you can’t even avoid it: the representation of the program as data is just sitting right there, staring you in the face. Julia doesn’t use S-expression syntax, so the representation of code as data is less obvious, but it’s not hidden very deep:

julia> ex = :(2a + b + 1)
:(2a + b + 1)

julia> dump(ex)
Expr
  head: Symbol call
  args: Array(Any,(4,))
    1: Symbol +
    2: Expr
      head: Symbol call
      args: Array(Any,(3,))
        1: Symbol *
        2: Int64 2
        3: Symbol a
      typ: Any
    3: Symbol b
    4: Int64 1
  typ: Any

julia> Meta.show_sexpr(ex)
(:call, :+, (:call, :*, 2, :a), :b, 1)

julia> ex.args[3]
:b

julia> ex.args[3] = :(3b)
:(3b)

julia> ex
:(2a + 3b + 1)

Julia code is represented by the Expr type (and symbols and atoms), and while the correspondence between the surface syntax and the structure is less immediately obvious, it’s still there. And more importantly, people know that code is simply data which can be generated and manipulated, so there is a “rich community of program-manipulating programs”, as KMP put it.

This is not just a superficial presentation of Julia code as a data structure – this is how Julia represents its code to itself. When you enter an expression in the REPL, it is parsed into Expr objects. Those Expr objects are then passed to eval, which “lowers” them to somewhat more regular Expr objects, which are then passed to type inference, all implemented in Julia. The key point is that the compiler uses the exact the same representation of code that you see. The situation is not that different in Lisp. When you look at Lisp code, you don’t actually see list objects – those only exist in the computer’s memory. What you see is a textual representation of list literals, which the Lisp interpreter parses and turns into list objects which it then evals, just like Julia. Julia’s syntax can be seen as a textual representation for Expr literals – the Expr just happens to be a somewhat less general data structure than a list.

I don’t know the details, but I suspect that Elixir is similar – maybe José will chime in.

Update (2019)

Having thought about this more for the past 4+ years, I think the key difference between Lisp and Julia is this:

  • In Lisp, the syntax for code is the same as the syntax for the data structure that is used to represent that code.
  • In Julia, the syntax for code is quite different from the syntax for the data structure that represents that code.

Why does this matter? On the pro-Julia side, people like special syntax for things and often find S-expression syntax inconvenient or unpleasant. On the pro-Lisp side, it’s much easier to figure out how to do metaprogramming correctly when the syntax of the data structure you’re trying to generate (to represent code) is the same as the syntax of the code that you would normally write. This is why one of the best pieces of advice when people are trying to write macros in Julia is to do the following:

  1. Write an example of the kind of code you want your macro to generate
  2. Call Meta.@dump on that code to see it as a data structure
  3. Write code to generate that data structure—this is your macro.

In Lisp, you don’t have to do step 2 because syntax for the code is already the same as the syntax for the data structure. There are the quasiquoting (in Lisp speak) quote ... end and :(...) constructs in Julia, which allow you to construct the data structures using code syntax, but that’s still not as direct as having them use the same syntax in the first place.

See also:

Leave a Comment