Homoiconicity isn’t the point (2012)
calculist.org
calculist.org
It is true: Being able to "read without parsing" is definitely nice.
But that is only a subset of those advantages that a homoiconic language gives you. An at least equally important advantage is due to the fact that programs in homoiconic languages are typically very easy to reason about by built-in mechanisms in that language.
For example, Prolog programs are readily represented as Prolog terms, and can be easily reasoned about by built-in mechanisms such as unification.
Since I regard it as a key advantage of homoiconic languages that their abstract syntax is completely uniform and can typically be easily reasoned about within such languages, I disagree with the main point that the article is trying to make.
One interesting fact about homoiconicity is that extremely low-level languages (like assembly code) and extremely high-level languages (like Prolog) are homoiconic, yet there is a large gap "in the middle", where there are many languages (like Java, C, Python etc.) that lack this property.
In fact, the macropy project[1] offers the "read" step (by abusing the import system), and while using them is pretty cool, I don't think the implementation of the macros is very nice.
The fact that you can access the AST in a language is not sufficient to make it homoiconic. There are several programming languages like Julia that let you access the AST yet are not (conventionally) considered homoiconic.
[1] https://stackoverflow.com/questions/31733766/in-what-sense-a...
There are languages like picolisp and guile that try and fill that gap a little :)
Languages allow you to express your reasoning, but they don't do the reasoning by themselves. Also, there is no conclusive evidence that homoiconic languages have simpler semantics, especially of the denotational kind.
Um, and how exactly are primitive forms defined?
> most keywords get the explanation of "this is how the computer will act" and then explanations of new behaviors.
Have you heard of Hoare logic? The meaning of ordinary ALGOL-style imperative programs can be given in terms of relating preconditions to postconditions. Suppose that you have the Hoare triples:
{P} foo {Q}
{Q} bar {R}
{P} foo; bar {R}
foo; bar
My point was that you don't typically see c constructs explained in terms of other c constructs. This is quite common in lisp. To see lisp constructs explained in terms of other lisp constructs. In large because there are few constructs.
You showing me that you can explain using other logic is kind of my point. It is awesome that you can do this. I recommend the skill. It is still not showing c or Java or Haskell or whatever in terms of themselves.
Note that I think you actually can do this, in large. It is not typically done, though.
Don't confuse “defined” with “implemented”. This is the entire point to having an axiomatic semantics!
> My point was that you don't typically see c constructs explained in terms of other c constructs.
Languages can't be entirely defined in terms of themselves. At some point you need to drop down to something else. If most of Lisp is defined in terms of other Lisp constructs, that is perfectly fine, but, for my purposes, i.e., proving things about programs, there are two mutually exclusive possibilities:
(0) The semantics of Lisp is the semantics of its primitive forms, and derived forms are just Lisp's standard library.
(1) So-called “derived” forms have an abstract semantics of their own right, and their implementation in terms of so-called “primitive” forms is, well, an implementation detail.
So, my answer to “most of Lisp is defined in terms of Lisp itself” is “that's cute, but how mathematically elegant is the part of Lisp that is not defined in terms of itself?”
So, by all means, keep arguing points I'm not making. I was offering what I suspect the parent post meant by it being easier to reason using the mechanics of the language. Nothing more.
And it still doesn't make sense. “Reasoning about programs” is making inferences about their meaning, i.e., deriving judgments from prior judgments. How exactly do homoiconic languages make it any easier to make inferences about the meaning of programs, given that homoiconicity is largely a property of how concrete and abstract syntaxes are related to each other? (Not that homoiconicity makes things more difficult either. It is just completely unrelated to reasoning about programs.)
https://en.wikipedia.org/wiki/Abstract_interpretation
Using abstract interpretation, you can derive interesting program properties. The uniformity and simplicity of Prolog code, as well as its built-in language constructs like unification and backtracking, make it especially easy to write abstract interpreters for Prolog.
Here is a paper that applies this idea to derive several interesting facts about programs and their meaning:
Michael Codish and Harald Søndergaard, Meta-circular Abstract Interpretation in Prolog (2002) https://link.springer.com/chapter/10.1007%2F3-540-36377-7_6
Abstract interpretation is also applicable to other programming languages. However, it is much easier to apply to homoiconic languages like Prolog.
Please note that what makes this reasoning method so easily applicable in this case is uniformity of the abstract syntax, not of the surface syntax, which is also called concrete syntax.
Homoiconicity is a relation between the concrete and abstract syntax tree (AST) of programs and the language's built-in data structures.
Specifically, learning algebraic manipulation is typically taught by showing the basic math that you are abstracting over. Multiplication is often taught in terms of addition.
Are there deeper understandings? Of course! I am again just saying that I see the appeal for this method and suspected that was the point that sparked confusion.
False; the syntax before expanding macros is an AST, so is the one after. It's an AST-AST transformation.
If anything, the one with macros is more abstract: because it, like, has the abstractions in their original abstract form!
Also, non-Lisp languages perform AST-AST transformations; just usually not with Lisp-like macros. For instance, the AST node for a while loop in a C compiler might be replaced with a combination of if, goto and statement label nodes (with generated labels: analogous to a Lisp macro's gensyms). That's a form of expansion. The input is an AST with while nodes; the output is one without.
So, no the advantage really is that with Lisp we are reading rather than parsing. Or, alternatively, that the parsing is very simple and uniform, and that the language of the parser over-generates: it produces a large space of forms which do not have a meaning, but serve as arbitrary data or can be given a meaning with new abstractions.
In, say C, we have a syntax in which there are numerous lists: lists of declaration specifiers in a declaration, lists of parameters, lists of structure members in a struct declaration, lists of global definition, lists of statements in a statement body. These all have their own grammar productions with their own quirks. And none of them have an object model to which they correspond.
In Lisp, the analogous things are all the same list type with the same syntactic representation. It corresponds to an object, and is operated upon by the same access and construction methods.
Homoiconicity isn't the point, because that just refers to storing procedures in the form in which they were entered ("code is characters, and nothing but"). Code is structured data is code is the point, with a nice, straightforward printed representation for working with the data textually.
I mean, yes, in the same vacuous sense that the flat stream of tokens output by a lexer technically qualifies as an AST. If you like, your lexer could output a "tree" of 1+N nodes: a Parse node, and within it, a list of N arguments (the lexer-tokens.) You would then apply an AST-AST transformation that responds to the "parse" node by parsing its contents.
When we talk about an AST in the context of programming, we usually mean to refer not to any airy CS concept, but specifically to the output of an LR(k) parser—that is, a bottom-up, context-free parser. To parse the lexer-token stream in an LR(k) parser, you need to be able to output ("produce") a structure given a sequence of tokens, without having any context of the greater rule you're executing "within" (i.e. above on the call-stack) other than the fact of what the current rule is.
Homoiconicity is exactly the property of a programming-language grammar that allows code containing macros to pass cleanly through this initial "lexical parsing" step. Usually, this requires a separation of the grammar from the syntax of the language, such that the "lexical parsing" grammar will no longer directly produce any of the "special forms" of the language itself, but these will rather be later handled by a similar (or the same!) process as macro-expansion—consuming AST subtrees to produce other, more specialized AST subtrees.
Or, to put that another way: macros require top-down parsing. If you want to avoid using a full-on top-down parser, you can instead apply a traditional bottom-up context-free parser followed by applying a folding transformation to the generated tree to do "the rest" of the parsing. But, to achieve this parsing strategy, the property you have to imbue your language grammar with is called "homoiconicity."
Can you explain more why this makes macros AST -> AST transformation only vacuously true? I didn't follow the argument. Also why macros require top down parsing?
Perhaps more interesting, would the property you described still be called homoiconic if the the parser were context sensitive?
(In C, the preprocessing phase also works with the same input and output language. It's not a tree data structure, but rather a sequence of preprocessor tokens. Tokens in, tokens out. Parsing is then done in the next phases of translation. Macros have to do some light parsing in order to delimit the argument lists, of course, and to identify the operators like the token pasting ##, stringification # and whatever, plus to handle the preprocessing directives and #if expressions with arithmetic.)
In context, this is about producing an AST in a "base" language without all the language extensions the actual user program uses.
That is completely false. If the code happens not to use any macros, they are the same. One is exactly as "superficial" as the other.
Macros write code in the same language that the human user; they use other macros and even recursively themselves sometimes.
Stuff like this is frankly why so many programmers shy away from lisp and s-expression based languages.
That's the popular slogan, but there'a actually quite a lot more to it than that. After all, strings are data too, and C programs are represented as strings, so "code is data" in C too. But that is obviously missing the point.
What's really going on is that, in Lisp, code is a particular kind of data, specifically, it's a tree rather than a string. Therefore, some (but not all) of the program's structure is represented directly in the data structure in which it is represented, and that makes certain kinds of manipulations on code easier, and it makes other kinds of manipulations harder or even impossible. But (and this is the key point) the kinds of manipulations that are easier are the kind you actually want to do in general, and the kind that are harder or impossible are less useful. The reason for this is that the tree organizes the program into pieces that are (mostly) semantically meaningful, whereas representing the program as a string doesn't. It's the exact same phenomenon that makes it easier to manipulate HTML correctly using a DOM rather than with regular expressions.
I ask myself based on this world view if there are useful other representations beyond the popular choices of lists and strings. Apparently, lists (like in lisp) are already so universal that they can represent any kind of structural data.
In fact, there is no one "killer feature". It's a confluence of lots of little details. Two of the details that turn out to matter most is having symbols, and not having comas as separators in the surface syntax. Those two things are the difference between S-expressions:
(defun foo (x y) (baz (bar x) (bing y)))
and JSON, which can represent the exact same thing:
['defun', 'foo', ['x', 'y'], ['bar', 'x'], ['bing', 'y']]]
but obviously you wouldn't want to write your code like that.
You might be able to improve on linked lists as a code representation. You could, for example, use vectors instead of linked lists (i.e. cons cells) or maybe associative maps (i.e. dictionaries) as a core data structure. It's not hard to try out things like this in Lisp, so if you really want to know what happens, just grab yourself a Lisp interpreter (or even better, write one yourself) and try it.
Mind. Blown. Your whole comment is incredible. I've never thought about it this way or realized what the value proposition was. Thanks!
http://www.defmacro.org/ramblings/lisp.html
If not then people might enjoy a deeper dive into this kind of thing! For anybody who's not read it - since it's pretty long I'll try and sum it up with a quote from about 2/3 of the way down:
"Lisp is executable XML with a friendlier syntax"
This bit always comes to mind when I think of lisp and "code as data / data as code".
I thought the point in lisp was that the syntax for non-code data and code are the same so treating code as data (and thinking about code as data) is easier than in many other programming languages.
I'd just like to interject for a moment.
To add on to what you have said: More precisely, Lisp programs are just lists; and in Lisp lists are first-class data structures (that is, there is a ton of functions for working with list). Thus, in Lisp, Lisp programs are first-class data structures as well.
I do it because the editors are terrible.
I love s-expressions, but it will be a cold day in hell before I waste more of my life with Emacs, Vim or DrRacket.
DLang, for example, has free-form macros that they weirdly call "mixin" (as in, mixing in some text or declarations into the AST, syntax-wise).
Each mixin must be a valid AST subtree on its own, which gives the same guarantee that paren matching prior to macro expansion gives you.
Then, the compiler can interleave:
parsing
-> evaluating mixin strings
-> resuming parsing of the mixin subtrees
-> evaluating the deeper mixin strings
-> ...
`if is.open(file) && read(file) { ... }`
can't actually be implemented by a function. That is, you can't write a function:
`special_and(is.open(file), read(file), ...)`
Because the `read` is automatically evaluated before the function is called.
This means a programming language with lisp-style macros can very easily implement constructs that behave like `&&` and short circuit, because they are implemented as a macro instead of a function. This opens up new (& fast) ways to control program flow that aren't available to a lot of people. The profound impact is that lisp libraries can tack on new control structures in a way that, say, C can't.
I'm no language designer, so this is basically out there to see if I get corrected.
Note that even in a language which is generally strict, laziness can be provided selectively for individual values, and vice versa. Haskell's laziness has proven to be a cause of troublesome performance problems, sometimes needing to be solved by "strictness annotations"; the newer language Idris is strict, but offers laziness as a type.
http://docs.idris-lang.org/en/latest/faq/faq.html#how-can-i-...
EDIT: phamilton beat me to it, maybe the links are still useful.
defmacro unless(clause, do: expression) do
quote do
if(!unquote(clause), do: unquote(expression))
end
end
With code blocks as values and syntax for unevaluated arguments, you can do this with normal functions without macros being a special, different thing; Rebol/Red do this, for instance.
For the Lisp reader the form (+ 1 2) in
(first '(+ 1 2))
(* (+ 1 2) 3)
All we represent is a bunch of tokens in nested lists.
For example, in typical cases, reasoning about such data structures (lists in Lisp, terms in Prolog, bytes in assembly code etc.) is very convenient in homoiconic languages, and in fact I think one could rightfully regard this ability to conveniently reason about a program's abstract syntax tree via built-in language mechanisms as a key advantage of homoiconic languages.
And then in addition to being able to parse user defined operators, then you have to have a decently organized, simple system for applying AST transformations and modifying tree objects. And there again homoconicity in the grammar can be useful if it makes it easy to textually serialize and set object attributes.
For me this was most poignantly demonstrated by https://chrisdone.com/z/
Then, it turns out to be the easiest thing about the entire endeavour, and you forget about it in all of your first 10 minutes on the job.
Because of this I have zero interest in working with a lisp day-to-day, but there are multiple C-style langs I'd be happy working with for a day-job.
I think GPP is right in asserting that most people just won't ever get over it, and you shouldn't be so quick to hand-wave their opinion away.
They struggled with functional programming and immutability. At least to start with. I actually found it amazing how easily people moved over and how enjoyable they found it. Out of 30 people only one didn't take to Clojure. He moved to a C# team for a while but eventually decided to rejoin and pick Clojure back up.
Obviously everyone is different but this was quite a good sample.
So, i.e., they were struggling with just the stuff in Clojure that makes it a non-Lisp.
Those programmers should have been informed that there are real Lisps out there in which you don't have to do functional programming, and things are mutable.
I'm not defending a generalization against counterexamples by trying to exclude them with a moving-goalpost definition.
Mutation and pure procedural programming are part of Lisp. They are part of Lisp when they are bad, and part of Lisp when they are good. I've never shifted a definition of what is Lisp to exclude or include these characteristics in order to suit an argument at hand.
Struggled to start with, sure. But ultimately for me those are the best parts. Immutability particularly. It takes a few weeks learn how to solve problems again but I do think it makes things simpler and removes a nice category of bugs.
Actually maybe Java interop was the best part. Without that I doubt we could have picked up Clojure. It's far less true today but this was almost 6 years ago. Back then knowing there would be a library, even if we had to quickly wrap it was essential.
That being said, I find that Prolog code is often more readable than Lisp code. An important reason for this is that Prolog supports prefix, infix and postfix operators that can be defined as part of the concrete syntax. On the level of the abstract syntax tree, all terms conform to the inductive definition, so this is only a notational convenience.
I've also struggled with understanding header files in C++, with templates and operator overloading and all the different meanings of const. But C++ has a massive user base. My point is C++ syntax is hard to grok too. Maybe popularity is an accidental thing related to inertia and winner-take-all effects?
Believe me, there are many reasons why Lisp hasn't gained more traction, and little of this has anything to do with the syntax or with the homoiconicity.
Consider this in Python (or any other language):
a = [1, 2, 3]
Now sort it.
In lisp, everything is:
(function [arg] ....)
You've conquered the entire syntax of the language. Now we can move on to getting things done and not have to worry about order of operations, variations on the basic syntax, and so on.
You can do newline type formatting with paredit and sane indentation habits, which aren't any different than other languages.
Take LET and LAMBDA. Both don't follow above pattern.
So what's it good for? Well, it's a generalise way of doing objects. In OO code, when you're given an object, say in parameter of a function, you're given data and, joy, you're given code as well. That's super handy because now data and code-that-runs-on-those-data come in the same package. You dont have to know the details (and more importantly, you dont care about the details) of how that piece of code-and-data was made - Im looking at you polymorphism - you can interface your algorithm to it and things will run the way they are supposed to. Notice how your programming has become more powerful. You've decoupled things here: now you dont need to know how the code works, but you still can interface to it. Other teams can supply piece of code-and-data, and, as long as you've agreed on the interface, things will run. That's classy.
Now you could go one step further. You could go literally matrix on this concept, and by changing virtually nothing. Let's just represent an object in a different, yet identical way: as an ordered list of members and methods - which it literally is. What's that cool for? Well now you have a list, you can splice it. You can add and remove code-and-data at will which is what you were doing when using polymorphism (you were swapping methods, adding members, that kind of stuff).
What's it good for? Step back a minute, what is polymorphism good for? We mentioned it before, it allows you to decouple implementation from execution. Well then, homoiconicity is good at the exact same thing. That's it, there is nothing more to say. If you understand what inheritance and polymorphism are good for, you understand what homoiconicity is good for: it's tools for representing and manipulating code-and-data. Notice how polymorphism and inheritance are tools from compile-time. Homoiconicity is the most usefull at compile time too, yet can be used at runtime as well.
All in all, that's why coding in lisp will make you a better programmer. OO languages and Lisp have the same goals. Only one is the nerd version of the other. Code in lisp and you'll come back to OOP thinking "this looks like BASIC now".
Ultimately, OO is good. The only thing that's bad with OO is that it's clunky in practice (what a pain to change a class hierarchy) and therefore gets in the way of refactoring. Refactoring is the key difference between waterfall and good software development. I had a friend who used to say "you should be refactoring 30% of the time" and I believe he's right. So while OO features are arguably good enough, programmers tend to waterfall with it and that's a killer.