How to make a language homoiconic

Question

According to this article the following line of Lisp code prints "Hello world" to standard output.

(format t "hello, world")

Lisp, which is a homoiconic language, can treat code as data in this way:

Now imagine that we wrote the following macro:

(defmacro backwards (expr) (reverse expr))

backwards is the name of the macro, which takes an expression (represented as a list), and reverses it. Here’s "Hello, world" again, this time using the macro:

(backwards ("hello, world" t format))

When the Lisp compiler sees that line of code, it looks at the first atom in the list (backwards), and notices that it names a macro. It passes the unevaluated list ("hello, world" t format) to the macro, which rearranges the list to (format t "hello, world"). The resulting list replaces the macro expression, and it is what will be evaluated at run-time. The Lisp environment will see that its first atom (format) is a function, and evaluate it, passing it the rest of the arguments.

In Lisp achieving this task is easy (correct me if I'm wrong) because code is implemented as list (s-expressions?).

Now take a look at this OCaml (which is not a homoiconic language) snippet:

let print () =
    let message = "Hello world" in
    print_endline message
;;

Imagine you want to add homoiconicity to OCaml, which uses a much more complex syntax compared to Lisp. How would you do that? Does the language has to have a particularly easy syntax to achieve homoiconicity?

EDIT: from this topic I found another way to achieve homoiconicity which is different from Lisp's: the one implemented in the io language. It may partially answer this question.

Here, let’s start with a simple block:

Io> plus := block(a, b, a + b)
==> method(a, b, 
        a + b
    )
Io> plus call(2, 3)
==> 5

Okay, so the block works. The plus block added two numbers.

Now let’s do some introspection on this little fellow.

Io> plus argumentNames
==> list("a", "b")
Io> plus code
==> block(a, b, a +(b))
Io> plus message name
==> a
Io> plus message next
==> +(b)
Io> plus message next name
==> +

Hot holy cold mold. Not only can you get the names of the block params. And not only can you get a string of the block’s complete source code. You can sneak into the code and traverse the messages inside. And most amazing of all: it’s awfully easy and natural. True to Io’s quest. Ruby’s mirror can’t see any of that.

But, whoa whoa, hey now, don’t touch that dial.

Io> plus message next setName("-")
==> -(b)
Io> plus
==> method(a, b, 
        a - b
    )
Io> plus call(2, 3)
==> -1

Answer 1

You can make any language homoiconic. Essentially you do this by 'mirroring' the language (meaning for any language constructor you add a corresponding representation of that constructor as data, think AST). You also need to add a couple of additional operations like quoting and unquoting. That's more or less it.

Lisp had that early on because of its easy syntax, but W. Taha's MetaML family of languages showed that it's possible to do for any language.

The whole process is outlined in Modelling homogeneous generative meta-programming. A more lightweight introduction to the same material is here.

Answer 2

The Ocaml compiler is written in Ocaml itself, so certainly there is a way to manipulate Ocaml ASTs in Ocaml.

One might imagine adding a built-in type ocaml_syntax to the language, and having a defmacro built-in function, which takes an input of type, say

f : ocaml_syntax -> ocaml_syntax

Now what is the type of defmacro? Well that really depends on the input, as even if f is the identity function, the type of the resulting piece of code is dependent on the piece of syntax passed in.

This problem does not arise in lisp, since the language is dynamically typed, and no type needs to be ascribed to the macro itself at compile time. One solution would be to have

defmacro : (ocaml_syntax -> ocaml_syntax) -> 'a

which would allow the macro to be used in any context. But this is unsafe, of course, it would allow a bool to be used in stead of a string, crashing the program at run-time.

The only principled solution in a statically-typed language would be to have dependent types in which the result type of defmacro would be dependent on the input. Things get quite complicated at this point though, and I would start by pointing you at the nice dissertation by David Raymond Christiansen.

In conclusion: having complicated syntax is not an issue, since there are many ways to represent the syntax inside the language, and possibly use meta-programing like a quote operation to embed the "simple" syntax into the internal ocaml_syntax.

The issue is making this well-typed, in particular having a run-time macro mechanism that does not allow for type errors.

Having a compile-time mechanism for macros in a language like Ocaml is possible of course, see e.g. MetaOcaml.

Also possibly useful: Jane street on meta-programing in Ocaml

Answer 3

As an example consider F# (based on OCaml). F# is not fully homoiconic, but supports getting the code of a function as an AST under certain circumstances.

In F#, your print would be represented as an Expr that is printed as:

Let (message, Value ("Hello world"), Call (None, print_endline, [message]))

To highlight the structure better, here is an alternative way how you could create the same Expr:

let messageVar = Var("message", typeof<string>)
let expr = Expr.Let(messageVar,
                    Expr.Value("Hello world"),
                    Expr.Call(print_endline_method, [Expr.Var(messageVar)]))