Comment by DonbunEf7 | Hacker News Reader

Comment by DonbunEf7 | Hacker News Reader

Parent Full thread

Indeed, homoiconicity is a very powerful thing. It doesn't have to be core to the nature of the language, though; as far as I know, any Turing-equivalent language readily admits a metacircular interpreter, and so really a homoiconic language is a language with a compiler in the standard library.

As a thought experiment, imagine Lisp without macros. It's not hard; after all, "The Little Schemer" covers metacircular interpretation without ever mentioning macros. So what's going on? Apparently we don't need macros! But, we could add macros to a Lisp by reifying them in the metacircular interpreter. There's actually a feature in plain sight which makes this possible, and it's the humble (quote) special form. This is what makes code and data intermix so cleanly in Lisp.

This is why languages like Julia and Monte are not shy about using "homoiconic" to describe their language design; a standard library compiler is just as good as a compiler in the core semantics, as long as it's easy to use and meshes well with the rest of the language.

No, this is incorrect. The syntax and the AST must be isomorphic for a language to be homoiconic. It's not enough to expose the compiler/AST as a first-class library.

Wikipedia has a nice entry on this. In short, "homoiconicity is where a program's source code is written as a basic data structure that the programming language knows how to access."

[1]: https://en.wikipedia.org/wiki/Homoiconicity

According to that page, the term was introduced by the designer of something called TRAC, who used it to denote the idea that the program is stored in the memory in the same form in which the user enters it, which allows it to be inspected and changed. Nothing about ASTs.

And TRAC is all about macros...

TRAC is lots of fun. I read about it in Nelson's book, Computer Lib/Dreams, when I was a freshman at Illinois. That spring, my Dad bought an Altair and I wrote a version of Trac for it, in assembly. Had support for bignum arithmetic, in ASCII :-)

Later, when I learned about tail recursion, I was happy to figure out that my implementation was indeed properly tail recursive.

What you said and what I said are in agreeement, so I'm not sure I follow. "Program stored in memory in the same form in which the user enters it" makes it isomorphic. Which was exactly the point I was trying to make in response to the parent comment.

You cannot simply expose the compiler/AST data structure and call your language homoiconic because the text the user enters and the resulting AST are not isomorphic which is a necessary precondition for homoiconicism.

I may be missing something in what you said though, so please do let me know.

By "first-class", I really did mean "indistinguishable from the rest of the core of the language." Consider Monte:

    def x :Int := 42 # evaluated statement
    def ast := m`def x :Int := 42` # quasi-quoted Monte fragment
    eval(ast, safeScope) # easy evaluation

Now, it happens that m`` is a library written in Monte itself, but that's unsurprising when you consider how much of the Monte compiler is also self-hosting. Since Monte is a complex and rich language, the homoiconic representation is equally rich:

    def m`def @lhs := @rhs` := ast # pattern-matching!
    [lhs, rhs] # [mpatt`x :Int`, m`42`]

The Julia developer have backed away from the claim that Julia is homoiconic; they no longer describe it that way. Nevertheless your points are really interesting, to the extent that I can understand them.

> imagine Lisp without macros.

Early on in my Scheme career, I found the tools to create macros a bit confusing and arcane .. but I still knew I wanted macros.

I ended up writing code transformers - a poor man's macro system if you will, taking my "high level" foo.scm through a couple of translation layers that turned the abstractions I wanted into running code. It was literally:

  $ scheme expand-foo.scm < myprog.scm > myprog1.scm
  $ scheme expand-bar.scm < myprog1.scm > myprog2.scm
  $ scheme myprog2.scm

What made this possible - trivial - was the homoiconicity: simply by (read)ing a program from stdin I had a list of lists that I could pattern match over and make the transformations I wanted. Exactly as my final program did with ordinary data.

In some ways, this was a more satisfying approach than using define-syntax / syntax-case, which differ from the rest of Scheme in somewhat uncomfortable ways. That macros could never be first class eventually put me off, but that's another story :).

Reply on news.ycombinator.com