15
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ You might want to have a look at how Scala did its macros $\endgroup$ – Bergi Sep 14 '16 at 22:25
  • 1
    $\begingroup$ @Bergi Scala has a new approach to macros: scala.meta. $\endgroup$ – Martin Berger Sep 15 '16 at 7:38
  • $\begingroup$ I've always though homoiconicity is overrated. In any sufficiently powerful language you can always define a tree structure that mirrors the structure of the language itself, and utility functions can be written to translate to and from the source language (and/or a compiled form) as required. Yes, it's slightly easier in LISPs, but given that (a) the vast majority of programming work should not be metaprogramming and (b) LISP has sacrificed language clarity to make this possible, I don't think the tradeoff is worth it. $\endgroup$ – Periata Breatta Sep 15 '16 at 14:09
  • $\begingroup$ @PeriataBreatta You are right, but the key advantage of MP is that MP enables abstractions without run-time penalty. Thus MP resolves the tension between abstraction and performance, albeit at the cost of increasing language complexity. Is it worth it? I'd say the fact that all major PLs have MP extensions indicates that a lot of working programmers find the trade-offs MP offers useful. $\endgroup$ – Martin Berger Sep 15 '16 at 14:22
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Correct me if I'm wrong. "mirroring" is related to the second part of the question (homoiconicity in io lang), right? $\endgroup$ – incud Sep 14 '16 at 19:19
  • $\begingroup$ @Ignus I'm not sure I fully understand your remark. The purpose of homoiconicity is to enable the treatment of code as data. That means any form of code must have a representation as data. There are several ways of doing this (e.g. ASTs quasi-quotes, using types to distinguish code from data as done by the light-weight modular staging approach), but all require a doubling/mirroring of the language syntax in some form. $\endgroup$ – Martin Berger Sep 15 '16 at 7:48
  • $\begingroup$ I assume @Ignus would benefit from looking at MetaOCaml then? Does being "homoiconic" just mean being quotable then? I assume that multi-stage languages like MetaML and MetaOCaml go further? $\endgroup$ – Steven Shaw Sep 19 '16 at 16:03
  • 1
    $\begingroup$ @StevenShaw MetaOCaml is very interesting, especially Oleg's new BER MetaOCaml. However, it is somewhat restricted in that it performs only run-time meta-programming, and represents code only via quasi-quotes which is not as expressive as ASTs. $\endgroup$ – Martin Berger Sep 19 '16 at 21:01
7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ MetaOCaml has runtime-meta-programming, not compile-time meta-programming. Also MetaOCaml's typing system doesn't have dependent types. (MetaOCaml was also found to be type-unsound!) Template Haskell has an interesting intermediate approach: every stage is type-safe, but when entering a new stage, we must re-do type-checking. This works really well in practise in my experience, and you don't loose the benefits of type-safety at the final (run-time) stage. $\endgroup$ – Martin Berger Sep 14 '16 at 19:17
  • $\begingroup$ @cody it is possible to have metaprogramming in OCaml also with Extension Points, right? $\endgroup$ – incud Sep 14 '16 at 20:01
  • $\begingroup$ @Ignus I'm afraid I don't know about much about Extension Points, though I do reference it in the link to the Jane Street blog. $\endgroup$ – cody Sep 14 '16 at 20:04
  • 1
    $\begingroup$ My C compiler is written in C, but that doesn't mean you can manipulate the AST in C... $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 14 '16 at 23:51
  • 2
    $\begingroup$ @immibis: Obviously, but if that's what he meant then that statement is both vacuous and unrelated to the question... $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 15 '16 at 6:05
1
$\begingroup$

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)]))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.