8 ms·
Lisp, Smalltalk, and the Power of Symmetry (2014)
- deleted 9y ago[deleted]
- DonbunEf7 9y agoIndeed, 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.
- leephillips 9y agoThe 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.
- Denzel 9y agoNo, 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 https://en.wikipedia.org/wiki/Homoiconicity
- kazinator 9y agoAccording 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.
- Denzel 9y agoWhat 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.
- prestonbriggs 9y agoAnd 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.
- DonbunEf7 9y agoBy "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`]
- saywatnow 9y ago> 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 :).
- bitwize 9y agoLisp and Smalltalk actually suffer from the same problem: late-binding sucks. When I was in college a professor once pointed out to me that he didn't know of an LL(1) parser for Smalltalk. There's a reason for that: Smalltalk's syntax is late-bound! It's almost like Forth's syntax: the reader consumes words and decides what to do with them on the spot, whether they represent variables, operators, constants, or parts of a message send and once it has a subject, verb, and objects, dispatches the message also on the spot. This plays havoc with your ability to do static analysis, and languages that hinder static analysis should not be used in real-world systems. If the earliest you find out about errors is in a running system, it's far too late and you are hosed. This is why the Lisp and Smalltalk Evangelism Strikeforces have been met with decades of failure, while the Rust Evanglism Strikeforce is getting on with a massive project of digital tikkun olam.
- big_spammer 9y agoThere are alternatives that make static analysis look like the suboptimal approach. https://pointersgonewild.com/2015/09/24/basic-block-versioning-my-best-result-yet/ https://pointersgonewild.com/2015/09/24/basic-block-versioni...
- maemre 9y agoStatic analysis is not just about inferring types and hot paths for optimization. For that kind of stuff, a dynamic analysis is most of the time way better (lots of JIT compilers with speculative optimizations prove this point). There is another goal where static analysis shines: verification. If I'm writing a somewhat critical application, I want to make sure that it behaves according to my intent in all cases. For example, if I'm writing an airplane sofware, I want to make sure that it will at least never invoke any undefined behavior (this is done in ASTREE project). Static analysis is a powerful tool to give such guarantees in many cases. Some highly dynamic language features make analysis really imprecise or really hard (in terms of computation cost). There has been quite a lot of work on making static analyses that can handle such language features (for example control flow analysis helps analyzing code that uses dynamic dispatch or closures a lot but cost of the analysis is exponential in terms of the precision level most of the time). Sometimes people tackle analyzing highly dynamic languages like JavaScript but at a huge time cost in certain cases [1]. I'd prefer using a language designed with static analysis in mind if I were to prove certain properties about my code. [1]: http://www.cs.ucsb.edu/~benh/research/papers/dewey15parallel.pdf http://www.cs.ucsb.edu/~benh/research/papers/dewey15parallel...
- big_spammer 9y ago> Smalltalk doesn’t need macros because it has classes instead. I'm not sure this is true. Surely any programming language that lacks macros would be more powerful with them.
- aaron-lebo 9y agoIt might be more accurate to say: > Smalltalk doesn’t need macros because it has classes, powerful introspection capabilities, and simple expressive syntax (especially blocks) instead. There's a debate to be had if compile-time macros are superior to passing blocks as arguments. It also is easy to make your language parser extensible or easy to modify without having traditional lisp macros. Metalua does something like this.
- gnaritas 9y agoYea, that's a weird statement, however a better one is that Smalltalk doesn't need macros because it has a clean syntax for lambas that remove a common use for macros, hiding boilerplate use of Lisp's lambda. Beyond that, Smalltalk isn't file based, you don't edit some version of the code that gets compiled (and macro expanded) into some runtime version of the code you can only see through introspection; rather in Smalltalk you're actually editing the runtime version in a running image. Macros simply wouldn't fit into Smalltalk in any meaningful way and Smalltalk's syntax is pretty much already ideal for building DSL's without the need to clean it up with macros. What makes both Lisp and Smalltalk interesting is that there's no difference between language and library; the constructs you create yourself are on equal footing with the ones most consider built in. Macros let you build special forms to control evaluation semantics, Smalltalk simply uses blocks [ ] to delay evaluation, and both languages are their libraries. Lisp has functions/macros, if/cond, etc; Smalltalk has objects used in a way you simply do not see in other object oriented langauges. Smalltalk has no if statement, no while statement, no reserved words beyond true, false, nil, self, super, and thisContext, everything else is library including all control flow constructs which are implemented with objects/classes/inhertance, and polymorphism. They are both "pure" languages in a sense, and that pleases some people greatly. If you haven't programmed in Smalltalk, you really have no idea what object oriented actually means at a deep level. All of the popular so called OO languages are actually just procedural languages with hundreds of special keywords that have classes, but the languages themselves aren't build from classes and objects, they're procedural and defined by the compiler writer as special forms you cannot create yourself. Having objects, and being truly object oriented all the way down, are drastically different things.
- mark_l_watson 9y agoWonderful article! "Smalltalk, like Lisp, runs in the same context it’s written in." I have been programming professionally in Common Lisp (off and on) since the 1980s but there is something equally magical about Smalltalk. I have often thought that Smalltalk could be the language I use after I retire (I am in my 60s and I will probably stop working in about ten years).
- deleted 9y ago[deleted]
- lispm 9y ago> Smalltalk is powerful because all Smalltalk data are programs–all information is embodied by running, living objects. That's what Lisp systems do too. Program elements like classes, functions, methods, symbols, ... are first class objects. With something like CLOS you have a similar level of object-oriented meta-programming capabilities. Many Lisp systems offer additionally to execute Lisp data using a Lisp interpreter and Lisp has a simple data representation for Lisp programs: Lisp data. Smalltalk OTOH uses text as source code and usually a compiler to byte-code. > because Lisp source code is expressed in the same form as running Lisp code Only if you use a Lisp interpreter. Otherwise the running Lisp code might be machine code or some byte code. > Smalltalk goes one further than Lisp: it’s not that Smalltalk’s source code has no syntax so much as Smalltalk has no source code. That's a misconception. Smalltalk has source code. As text. It's just typically managed by the integrated development environment. It's actually Lisp which goes further than Smalltalk, because Lisp has source as data and can use that in Lisp interpreters directly for execution.
- pg314 9y ago> Smalltalk OTOH uses text as source code That is not completely correct. It uses a mixture of text (strings) and objects. The class graph is composed of objects, but the method bodies are stored as objects and (optionally) strings. To edit the class graph, it presents (parts of) it as text that you can edit (see ClassDescription>>definition in Squeak). E.g. to allow you to edit the Behavior class, it generates the following string and presents it in a text editor: Behavior subclass: #ClassDescription instanceVariableNames: 'instanceVariables organization' classVariableNames: 'TraitImpl' poolDictionaries: '' category: 'Kernel-Classes' Notice that this is a Smalltalk statement that can be evaluated. If you edit this strings and accept it, it will evaluate the code which updates the objects describing the class. The primary representation is not textual, but an object graph. A method is stored as byte code, and optionally as a string. The system will present you with a textual representation that you can edit, which is either the stored string or the decompiled byte code (which loses the original comments, indentation, and variable names). You can strip the textual representation of all methods to slim down the image (see SmalltalkImage>>abandonSources). You can also file in/out a textual representation of classes and their methods. But that is not the primary representation of the code.
- pron 9y ago> What most of these languages seem to miss is that Smalltalk’s class system, like Lisp’s macro system, is a symptom of the power already available in the language, not its cause. If it didn’t already have it, it wouldn’t really be that hard to add it in yourself. What most of these articles seem to miss is that that Java's designers were themselves expert Lispers and Smalltalkers, and they most certainly realized all that, and that Java's success is a consequence of them understanding exactly why not to repeat the same design. Design doesn't live in a vacuum. Design is shaping a product not just to fit some platonic ideal, but reality, with all its annoying constraints. To understand why Lispers and Smalltalkers designed Java the way they did, I recommend watching James Gosling's talk, How The JVM Spec Came To Be[1], and the first 20 minutes or so of Brian Goetz's talk, Java: Past, Present, and Future[2]. [1]: https://www.infoq.com/presentations/gosling-jvm-lang-summit-keynote https://www.infoq.com/presentations/gosling-jvm-lang-summit-... [2]: https://www.youtube.com/watch?v=Dq2WQuWVrgQ https://www.youtube.com/watch?v=Dq2WQuWVrgQ
- lispm 9y agoGosling was an expert Lisper? I only heard that he developed a strange/tiny Lisp variant called Mocklisp as extension language for his Emacs editor. > Design doesn't live in a vacuum. Java was designed as a modernized/slim replacement for C++ when developing set-top boxes and PDAs. What SUN took from Lisp and Smalltalk in some limited form was the runtime: managed runtime with GC, code loading, typed objects and a virtual machine. VMs were thought as an advantage on machines with little memory, because of compact code representations. Various Lisps and also Smalltalk had that. But that was mostly it. The language level wasn't influenced by Lisp at all: no Lisp syntax, no Evaluator, no lambdas, no code-as-data, no macros, no support for functional programming, ... https://en.wikipedia.org/wiki/Oak_(programming_language) https://en.wikipedia.org/wiki/Oak_(programming_language)
- pron 9y agoThat's precisely the point. Watch the talks I linked to. Gosling presents Java's design as a wolf in sheep's clothing. They figured that the features most important in Lisp and Smalltalk are memory safety, GC, dynamic linking and reflection, shoved all of them into the JVM, and wrapped them in a non-threatening language that could actually gain significant traction. They did that because they realized that the linguistic features are not where most of the power lies. That's what good design looks like: you hide the power in a palatable package.
- saywatnow 9y agoThe thing about both Lisp and Smalltalk that keeps making me feel alienated is that their power seems much weaker beyond their kingdom. The outside world does not have an object browser, nor is it made of s-expressions. Tcl occupies a very nice place in this regard: its homoiconicity and symmetry (and late binding) come from text. The outside world, to a very close approximation, is also made of text. Subprocesses, sockets, FFI, files and user interaction just feel more native - in the image-oriented languages, I always find myself fighting the ambassador who imperfectly represents these things in forms the kingdom understands. Just a feeling. They're all wonderful languages, and this article speaks well to some of the "why".
- coldtea 9y ago>The outside world does not have an object browser, nor is it made of s-expressions. You'd be surprised. Joking aside, you seem to fixate on an implementation detail. It's just that the computing world, or rather the Unix on, is "made of text". The world is actually made of objects and data, and this is closer to Lisp and Smalltalk.
- agumonkey 9y agoI find symmetries a very necessary concept. It's a complexity divider. A bit like self similarity or inductive reasoning, it turns chaos into cosmos.