A Critique of Homoiconicity

Homoiconicity is a property of Lisp in which program and data have the same representation, namely S-expressions. This gives Lisp uniquely strong power to write programs that manipulate programs, such as interpreters and compilers. But it also makes it easy for a novice programmer to be confused between program and data.

Philip Wadler described several such confusions in his paper, “A critique of Abelson and Sussman – or – Why calculating is better than schemin“. The original paper compared Scheme and Miranda, but I changed them to more modern languages Clojure and Haskell respectively.

Clojure lists are not self-quoting

In Clojure, lists are not self-quoting while numbers as data are self-quoting. For example, 3 evaluates to 3 itself, but (1 2 3) evaluates as a function call, not as a list. To include list as a datum, one must quote it as in (quote (1 2 3)) or ‘(1 2 3).

user=> 3
3
user=> (1 2 3)
ClassCastException java.lang.Long cannot be cast to clojure.lang.IFn user/eval5 (NO_SOURCE_FILE:4)
user=> (quote 1 2 3)
1
user=> ‘(1 2 3)
(1 2 3)

When combined with the substitution model to explain the evaluation of (list (list 1 2) nil), this is quite confusing because the intermediate steps are no longer legal Lisp expressions.

(list (list 1 2) nil)
-> (list (1 2) nil)
-> (list (1 2) ())
-> ((1 2) ())

In Haskell, one just writes [[1,2], []]. It is already a value, so there is no evaluation to explain.

Further confusion with quote

Surprisingly, (peek ”abracadabra) evaluates to quote.

user=> (peek ”abracadabra)
quote

because (peek ”abracadabra) expands to (peek (quote (quote abracadabra))) which evaluates as in

(peek (quote (quote abracadabra)))
-> (peek (quote abracadabra))
-> quote

Evaluating too little or too much

As Clojure represents program and data in the same form, one often mistakenly evaluates either too little or too much.

(peek (quote (a b)))

The result of evaluating the expression above is a. However, many programmers give the answer quote (too little) or the value of the variable a (too much).

In Haskell, no such problem arises because there is no quote.

Other confusions with lists

A list containing just one element x is (list x) or (x) in Clojure, while it is [x] in Haskell. As people tend to drop parenthesis, (x) often mistakenly read as x.

People also get confused between cons and list because (cons x y) and (list x y) in Clojure look similar while x:y and [x, y] in Haskell look distinct.

These are just notational differences, but some notations certainly make people more confused than others.

Syntax

Programming language research does not talk much about syntax because the preference of one syntax over the others depends much on the taste of a programmer. But the famous S-expression certainly hinders reasoning with algebraic properties, such as associativity. Also most people who are accustomed to infix notations taught at math classes find it hard read S-expressions at first.

Conclusion

A Lisp family language such as Clojure traditionally has been regarded as a good introductory language to students or novice programmers thanks to its simple syntax (or lack of) and semantics. But one of its powerful language feature, homoiconicity is a mixed blessing for beginners as it makes it hard to reason about programs. Maybe this is the reason why other functional programming languages such as OCaml, F#, Scala and Haskell end up not including homoiconicity in the language.

Advertisements

3 thoughts on “A Critique of Homoiconicity

  1. Clojure is a lisp dialect, but it’s not homoiconic language because it has special reader macros for immutable data structures such as vector, hash map.

    You can express as follows.
    user=> [[1 2] []] ;; or (vector (vector 1 2) (vector))
    [[1 2] []]

  2. A small parade of edge cases is hardly an effective critique of homoiconicity in programming languages. I did not find any of the points of confusion here compelling. Let me help — when developing in Clojure I used to forget to properly invoke lambdas in a threading context:

    (->> [{:id “soup”}]
    (map :id)
    (fn [x] (conj x “name”)))

    which simply returns the lambda function rather than executing it..

    #function[dev/eval64504/fn–64505]

    To execute the lambda requires another level of parenthesis:

    (->> [{:id “soup”}]
    (map :id)
    ((fn [x] (conj x “name”))))

    (“name” “soup”)

    As I have learned and used Clojure, I have found smoother experiences:

    (as-> [{:id “soup”}] x
    (map :id x)
    (conj x “name”))

    (“name” “soup”)

    What was once confusing, and a programming trap for me, I often later learned was completely unnecessary to begin with. All of the programming languages I have learned and used have such thorns.

    Homoiconicity provides an effective basis for macro systems, as well as unparalleled meta-programming facilities. An effective critique of these abilities ought to address them.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s