Bicameral, Not Homoiconic
parentheticallyspeaking.org
parentheticallyspeaking.org
Line numbered BASIC is homoiconic: you can edit any line of code and continue the program.
POSIX shell lets functions be redefined. They can be listed with the set command executed without arguments, and copy-pasted.
In Common Lisp, there is a function called ed, support for which is implementation-defined. If support is available, it is supposed to bring up an editor of some kind to allow a function definition to be edited. That is squarely a homoiconic feature.
Without ed support or anything like it, the implementation does not retain definitions in a way that can be edited; i.e. is not homoiconic. Some Lisps compile everything entered into them; you cannot edit a defun because it has been turned into machine language.
The idea has merit. Having the REPL deal with the parse structure of data in such a way that taking parsed data and presenting it as code has a lower barrier to effective outcome on the current run state than eval() is pretty big.
I'd say eval() isn't self-modifying. You can't come out the other side of eval() with future execution state of yourself different. As I understand it, the homoiconic features of LISP means you can.
Well, sort of. Mostly that's just English.
There's no Latin at all, but hom- [same] and icon [image] are arguably Greek roots. The Latin equivalents would be eadem [same, as in "idempotent"] and imago [image, and the feminine gender of this word explains why we need "eadem" and not "idem"]. I'm not sure how you'd connect those. (And you might have issues turning imago into an adjective, since the obvious choice would be imaginary.)
However, since icon begins with a vowel, I don't think it's possible for hom- to take the epenthetic -o- that appears when you're connecting two Greek roots that don't have an obvious way to connect. If the word was constructed based on Greek principles, it would be hom(e)iconic. Treating homo- as a prefix that automatically includes a final O is a sign of English; in Greek they're separate things.
I remember that when there was a scandal around cum-ex financial instruments, a lot of people wanted to say that cum-ex was Latin for "with-without", which it isn't; it's Latin for "with-from". ("Without" in Latin is sine, as compare French sans or Spanish sin.) Cum-ex is English for "with-without", and the same kind of thing is going on with homoiconic.
(Technically, you wouldn't expect an N before vowels anyway because the root word ends in an M, so hypothetically you'd have "cominstar". But since the consonant just disappears before vowels, that's moot. [Though technically technically, disappearing when before vowels is expected of M - this is a feature of Latin pronunciation generally - and not of N.])
"con"+"iacio" (also "jacio") => "conicio" (also "coicio" also "conjicio")
(Also "coinstar" is a trademark of those spare change gobblers you find after the register at Walmart.)
[0] https://www.perseus.tufts.edu/hopper/text?doc=Perseus:text:1...
It'd be a better example of an exception if it unambiguously started with a vowel. This is sort of the reverse of the case I pointed to above, where "habito" does start with a vowel, or rather it almost does, enough to trigger the same changes.
https://www.etymonline.com/word/com-
> Before vowels and aspirates, it is reduced to co-; before -g-, it is assimilated to cog- or con-; before -l-, assimilated to col-; before -r-, assimilated to cor-; before -c-, -d-, -j-, -n-, -q-, -s-, -t-, and -v-, it is assimilated to con-, which was so frequent that it often was used as the normal form.
I and J aren't different letters in Latin, but they are different kinds of sound, if sometimes only hazily different. Same goes for U and V. By modern convention we have convention and conjecture; the hazy difference seems sufficient to explain why the Romans left us every variety of the compound, from coniicio through conicio to coicio. A naive analysis (the most I can really do) would say that coniicio comes from someone who sees iacio as starting with a consonant, coicio comes from someone who doesn't, and conicio is a reduced form of coniicio.
(In Latin, there are plenty of words ending in -atio(n); however, within the language this is not a single unit, it's a sequence of part of the verb stem plus two separate morphemes -a-t-io(n). The -at- marks the passive participial form of an a-stem verb; compare faction (zero-stem), inhibition (e-stem).)
«same form» in Greek would rather be «homomorphic». (Or in latin «eademforma», which could maybe be turned to «idoform» in english)
«Homoiconic» could also have been named «monomorphic» (single form), similar to to «polymorphic» (many forms).
«Homoiconic» in Greek means «same-likeness» or «self-similarity» in English.
It's enough that the language stores the current source code and can reload it for that. So hot-code-swapping/reload is enough, not homoiconicity needed - which makes it not so squarely a homoiconic feature.
Oh man, anyone else remember those self-modifying BASIC programs, which would:
1. Clear the screen
2. Print a bunch of new BASIC lines on the screen, with a CONTINUE command at the end, thus:
100 PRINT $NEWVAR
110 <whatever>
CONTINUE
4. Enable some weird mode where "Enter" was considered to be pressed over and over again
5. Execute the BREAK command, so that the interpreter would then read the lines just printed?
I forget the kinds of programs that used this technique, but thinking back now as a professional developer, it seems pretty wild...
https://www.atariarchives.org/creativeatari/SelfModifying_Pr...
>allowing the definitions to be recalled at runtime and redefined
>Some Lisps compile everything entered into them; you cannot edit a defun because it has been turned into machine language.
Ability to recall and redefine definitions at runtime, even when the language is compiled is orthogonal to homoiconicity. Ruby can do this (interpreted). Clojure too (compiled). To do so, they don't store the program as text, they store source locations (file://...:line:col) and read the files from the disk (or jar). In fact any programming language that does source-mapping and has eval() is inches away from being able to do this. This was the case for Ruby and was made possible by the pry REPL library [1]. And then there are tools like javassist [2] that allow you to edit compiled code to some extent using a limited form of the language.
Note that in the case of lisps, this is entirely orthogonal to macros (the source is passed as arguments to macros in the form of an AST/list rather than a pointer into a file), which is where homoiconicity shines. Storing code in the same format it is written in (strings) doesn't alleviate the headache of processing it when you want to do meta programming.
Additionally, macros allow you to do structured meta programming: macros are guaranteed to only impact code they enclose. Compare this with redefinitions that are visible to the whole code base. This is like global vs local variables: macros don't redefine code, they transform it.
[1] https://github.com/pry/pry#edit-methods
[2] https://www.javassist.org/tutorial/tutorial2.html#before
That's also known as "storing the program as text".
But yeah, macros are related to another kind of homoiconicity, where the interpreted bytecode is written using the same symbols as your program data.
You can have both of those (source = bytecode) and (bytecode = data structures) only one of them or neither.
1. Scanner divides source-code-string into ordered chunks each with some identifying information, what is the type and content of each chunk.
2. The next stage better NOT be a "Parser" but a "Reader" which assembles the chunks into a well-formed tree-structure thus recognizing which chunks belong togeether in the branches of such trees.
3. Parser then assigns "meaning" to the nodes and branches of the tree produced by Reader, by visiting them. "Meaning" basically means (!) what kind of calculation will be performed on some nodes of the tree.
4. It is beneficial if the programming language has primitives for accessing the output of the reader, so it can have macros that morph the reader-produced tree so it can ask the parser to do its job on such a re-morphed tree.
Did I get it close?
> 3. Parser then assigns "meaning" to the nodes and branches of the tree produced by Reader, by visiting them. "Meaning" basically means (!) what kind of calculation will be performed on some nodes of the tree.
So, an "AST builder" that is followed by a "semantic pass". That's... how most of the compilers have been structured, at least conceptually, since their invention. In particularly memory-starved environments those passes were actually separate programs, launched sequentially; most famously the ancient IBM FORTRAN compilers were structured like this (they couldn't manage fit both the program being compiled and the whole compiler into the core; so they've split the compiler into 60-something pieces).
The article discusses this particularly with regards to the meme of LISPs being "homoiconic". The author elaborates that the difference between LISPs and other programming languages lies actually not in "homoiconicity" (a Javascript string can contain a program, and you can run `eval` on it, hence Javascript is "homoiconic"), but in what step of the parsing pipeline they let you access: with Javascript, it's before Tokenization happens; with LISPs, it's after Reading happened, before the actual Parse step.
So here is a problem with the article: the author believes that what he calls "bicamerality" is unique to LISPs, and that it also requires some S-expr/JSON/XML-like syntax. But that's not true, isn't? Java, too, has a tree-like AST which can be (very) easily produced (especially when you don't care about the semantic passes such as resolving imports and binding names mentions to their definitions, etc.), and it has decidedly non-LISP-like syntax.
And no, I also don't believe the author actually cares all that much about the reader/parser/eval being available inside the language itself: in fact, the article is structured in a way that mildly argues against having this requirement for a language to be said to have "bicameral syntax".
> So here is a problem with the article: the author
> believes that what he calls "bicamerality" is unique to
> LISPs, and that it also requires some S-expr/JSON/XML-
> like syntax.
So, here are some excerpts:
These advantages ("It’s a lot easier to support matching, indentation, coloring, and so on", and "tools hit the trifecta of: correct, useful, and relatively easy") are offset by one drawback: some people just don’t like them. It feels constraining to some to always write programs in terms of trees, rather than more free-form syntax.
Still, what people are willing to embrace for writing data seems to irk them when writing programs, leading to the long-standing hatred for Lispy syntaxes.
But, you argue, “Now I have a bicameral syntax! Nobody will want to program in it!” And that may be true. But I want you to consider the following perspective.
[...] a bicameral syntax that is a very nice target for programs that need to generate programs in your language. This is no longer a new idea, so you don’t have to feel radical: formats like SMT-LIB and WebAssembly text format are s-expressions for a reason.
And notice that nothing in those excerpts and nothing in the text surrounding them (sections 4 to 7) really refers to the ability to access the program's syntax from inside the program itself. In fact, the sections 1 to 2 argue that such an ability is not really all that important and is not what makes LISPs LISPs. Then what does? The article goes on about "bicamerality" (explicit distinction between the reader and the parser) but doesn't ever mention again the ability of the program to modify its own syntax or eval.
I can't help but to make the tacit deduction that those never-again-mentioned things are not part of "bicamerality". You, perhaps, instead take those things as an implicit, never-going-out-of-sight context that is always implied to be important, so those things are never mentioned again because already enough has been said about them but they still are crucial part of "bicamerality".
It's a duck-reabbit article. We both perceive it very differently; perhaps in reality it's just an amalgam of ideas that, when mixed together in writing, lack the coherent meaning?
void foo(int int) {
else {
x = 3;
}
}
Of course that is well-known but I think it is a big deal, that you have such homo-iconicity in Lisp but no in most other languages. Prolog maybe?
A token tree is not a full parse tree with resolved operator precedence and whatnot. It only has child nodes for bracket pairs ((), [] and {}) and their contents, in part to determine where the macro call ends. Otherwise, it's a flat list of tokens that the macro (what this article would call the "parser") can interpret in any way it wants.
This is instantly useful to the compiler writer because most of “LISP” is built upon more basic primitives. The disadvantage is the Jeff Goldblum “You scientists” meme.
> These advantages are offset by one drawback: some people just don’t like them. It feels constraining to some to always write programs in terms of trees, rather than more free-form syntax.
I think this is misdiagnosing why many people are averse to Lisp. It's not that I don't like writing trees; I love trees for representing data. But I don't think that thinking of code as data is as intuitive or useful as Lisp users want me to think it is, despite how obviously powerful the notion is.
This could be contrasted with C where code (maybe more precisely program logic) is opaque (modulo preprocessor) and can only be represented by function pointers (unless you're doing shellcode). Here the chamber that does the parsing from text (if we don't look inside GCC) also does semantic "checking" and so while valid functions can be represented within C (via the memory contents at the function pointer), the unchecked AST or some partial program is not represented.
I've tried not to give too many parentheticals above, but I'm not sure the concept holds water if you play tricks. Any Turing machine can represent any program, presumably in a way that admits cutting it up into atoms and rearranging to an arbitrary (potentially invalid) form. I'd be surprised if this hasn't been discussed in more detail somewhere in the literature.
This
As opposed to building first an untyped CST (concrete syntax tree), and then transforming that into a typed AST.
CPython does exactly this, but it has no macro stage either, so it's not exposed to users. (Python/ast.c is the CST -> AST transformation. It transforms an untyped tree to a typed tree.)
So the key reason it matters is that it's a place to insert the macro stage.
---
I agree that the word "bicameral" is confusing people, but it basically means "reader --> parser" as opposed to just "parser".
The analogies in the article are very clear to me -- in this world, JSON and XML parsers are "readers", but they are NOT "parsers"! (and yes that probably confuses many people, some new words could be necessary)
The JSON Schema or XML Schema would be closer to the parser -- it determines whether you have a "for loop" or "if statement", or an "employee" and "job title", etc.
Another clarifying comment - https://lobste.rs/s/ici6ek/bicameral_not_homoiconic#c_bmx0vf
For example, Github Actions uses YAML as its Reader / S-expression / CST layer.
And then it has a separate "parser", for say "if" nodes, and then another parser for the string value of those "if" nodes.
https://docs.github.com/en/actions/writing-workflows/workflo...
if: ${{ ! startsWith(github.ref, 'refs/tags/') }}
if: github.repository == 'octo-org/octo-repo-prod'
You must always use the ${{ }} expression syntax or escape with '', "", or () when the expression starts with !, since ! is reserved notation in YAML format.
So I feel that they could have done a better job with language design by taking some lessons from the past.
Gitlab has the same kind of hacky language on top of YAML as far as I remember
Strings don't make it "homoiconic" in the usual way, I think; so, JavaScript does not count.
I think "Bicameral" isn't really a great way to capture this, because there are often multiple layers of parsing/lexing/compilation/interpretation and you might want to hook in at multiple of them (e.g. in lisps you may have both reader macros that operate at a low-level stage and higher-level macros that operate after parsing). And of course it's a spectrum, but essentially the more the language exposes itself as a set of compositional libraries rather than just being a monolithic service.
I think this is due to a significant property shared by both languages: the parser’s primary role is distinguishing between numbers and anything that’s not a number. No need to worry about operator precedence, keywords, or building complex syntax trees. Tokens are numbers and “not-numbers”, and that’s it.
In Forth, a “not-number” is a Word, and in Lisp a Symbol, both of which can be variables or functions. The only difference between the two is that Forth checks for Word definitions first, and Lisp checks for numbers first. If you wanted to redefine 4 to 5 for some reason, Forth’s got your back, but Lisp will save you ;).
A Forth Dictionary is very similar to a Lisp Environment; they both serve as a lookup table for definitions, and they both allow the programmer (or program!) to redefine words/symbols.
They also both have REPLs to facilitate a much more dynamic development cycle than other REPLs in most languages.
I could go on, but on a fundamental level the similarities are striking (at least to me, anyway). It’s an interesting rabbit hole to explore, with lots of “drink me” bottles laying around. It’s fun here.
[0] https://git.sr.ht/~vdupras/duskos/tree/master/item/fs/doc/co...
Homoiconicity is more useful when comparing lisps IMO, and pondering on how they could be improved. To me, homoiconicity is a constant struggle and should be appreciated in degrees because homoiconicity is about immediacy.
A lisp that doesn't allow you to embed data along with code, JSON/Javascript style, is less homoiconic than a language that does, and it's more about what the core library allows than the language itself. For instance I'd say Clojure is more homoiconic than Scheme because it allows you to embed hashmaps in your code natively, whereas in scheme you only have `(make-hash-table)` without the corresponding reader macro. Similarly, a lisp without syntax quote would be less homoiconic than one that has it.
This is why I say it's about immediacy. When you don't have to deal with hashmaps, or templated s-exprs in terms of the process that builds them, the mediation layer disappears.
Things I'd like to be more immediate in Clojure:
- keeping track of whitespaces within s-exprs. Useful when you want to print code as it is indented in the source file. There's a library for that (rewrite-clj), but it isn't integrated in the reader+compiler pipeline, so it's a bit of an headache as you have to read code from files, which implies, bridging the gap between the compilation pipeline and this library on your own.
- accessing semantic info within macros. Which functions use which variables. Which variables are global vs local (in particular when lexically shadowed), which variables are closed over by which lambdas, etc. To do this you have to use clojure.core.analyzer, which is very complex and poorly documented: not immediate enough.
Using Google Books search, we can identify that a 1996 book called Advanced Programming Language Design by Raphael A. Finkel uses the word in this new way, claiming that TCL and Lisp are homoiconic.
The word returns to flatlining towards the end of the 1990s, and then surges after 2000.
I think the property being discussed is more understandable if you just describe it simply: in some Lisps (notably Common Lisp and its direct ancestors) source code is not made of text strings; it's made of symbolic expressions consisting of cons cells and atoms.
The text that you see in "foo.lisp" isn't Lisp source code; it's a serialization of Lisp source code. You could serialize it differently to get a different text file, but the reader would turn it into the same source code. The actual source code is distinct from any specific text serialization of it.
We write programs in the form of text serialization because the reader will convert it for us, and because it's easier and more rewarding to write good and comfortable text editors than to write good and comfortable s-expression editors.
There are of course text editors and addons that attempt to make text editing act more like s-expression editing, but I don't know of many actual s-expression editors. The canonical one, I suppose, is Interlisp's DEdit, which operates on actual s-expression data structures in memory.
From this point of view, what people mean by "homoiconic" is just that source code is all made of convenient arrangements of standard data structures defined by the language that can be conveniently operated on by standard functions defined by the language.
Or, to put it another way, "homoiconic" basically means "convenient", and "non-homoiconic" means "inconvenient".
That's all there is to it, really, but it has far-reaching consequences. In a Lisp designed this way, basic manipulation of source code is trivially easy to do with operations that are all provided for you in advance by the language itself. That makes all sorts of code-processing tools exceptionally easy to write.
That's not true in most languages. Take C, for example: sure, a C compiler parses text and turns it into an abstract syntax tree before processing it further in order to eventually yield executable machine code. Is all of that machinery part of the language definition? Can you count on those APIs and data structures to be exposed and documented by any arbitrary C compiler?
No.
In that sense, any programming language could be made "homoiconic" if enough people wanted it. They manifestly don't, because most languages aren't.
But some programmers prefer working with a language implementation that makes it so very easy to manipulate code. So that's what we use.
It's not some Platonic ideal of language design, but it doesn't need to be. It's a pragmatic design decision made by certain implementors in a certain lineage, and it has consequences that a certain fraction of programmers find congenial. Congenial enough that it makes some of us prefer to work with languages and implementations that work that way.
Do you have a candidate in mind?
TCL is not "bicameral" in the OP's sense, but that doesn't seem to stop anyone from doing metaprogramming.
Tcl's equivalent of the "Parser" is built-in to each command, which decides whether to interpret its arguments as data, code, option flags, etc..
I suspect this division of responsibilities is very helpful for metaprogramming techniques.
On the other hand, TCL provides much less support for building up the string to be evaluated if it's more complex than a single command; and even for a single command it can be tricky.
Is this a view some people actually hold? Would be interesting to see some argumentation why someone would think this is the case.
Seriously; if we could redefine the CL scanner, then e.g. package-local-nicknames could be a library instead of having to have been reimplemented in every single CL implementation.
Leaving this here, with the deepest respect.
Eternal Flame - Julia Ecklar https://www.youtube.com/watch?v=u-7qFAuFGao
Minor typo: "an syntax" in the second-to-last paragraph should be "a syntax".