In particular, this kind of mini embedded language interpreters can be great to build upon. For the folks who think LISP is dead and irrelevant (spoiler, it is not), think of https://www.lua.org/ as a prominent embedded language. Lua is based on a stack based programming idiom/VM. In a similar spirit, LISP is somewhat the lingua franca for intermediate code representation and therefore omnipresent in compiler contexts.
You can even write LISP interpreters in less lines of code. Norvig required 90 lines of Python: http://norvig.com/lispy2.html :-)
+1 really cool project! Definitely appreciate the use of Modern Java (records, pattern matching etc.) for showing that Java might not necessarily be extremely verbose compared to some dynamic languages. I'd recommend adding Nim and Kotlin as well (nim -> for comparison with python and kotlin for comparison with java)
It looks like several of your implementations have extremely similar styles. If you want to realistically compare verbosity between languages, it makes sense to adapt to the features available.
For example, in the Python example, you define a bunch of classes to represent the Lisp data structures. But you can embed basic Lisp data structures directly in Python lists or tuples, so its not clear what advantage this gives, while of course in Java its almost required.
In general it takes a lot of effort to make code concise, more so in languages with more features and thus less of a floor on program length, so I can understand starting with roughly the same implementation everywhere!
I tried to stick with code I'd be happy to see in a pull request at work. I'm a huge fan of using classes for data so I argue that the use of classes here was fair.
If you're using just Python lists everywhere the code would be somewhat harder to read.
Classes definitely make sense for some things, especially those that don't have a Python analogue, such as symbols.
What do you gain by wrapping a native representation of the same thing with a class? A cons cell _is_ a 2 element tuple.
That was only one example, in general your Python example has a somewhat Javaish, imperative style. I think it could also probably benefit from using the string libraries a little more.
As another commenter noted, Norvig did a similar thing in Python, and its ~100 lines, you might take a look for inspiration:
> I think it could also probably benefit from using the string libraries a little more.
Definitely agree. I forgot about some builtins like str.isdigit(), str.isalpha(). But Java also has Character.isDigit and Go has unicode.IsLetter and so forth.
I was just using the methods that came immediately to mind and in some cases did miss builtins in all implementations.
I thought the same, the c# Code is not very modern. It is possible to make it even nicer. But I guess it’s a great start, maybe I’ll submit a pull request :)
For example, here's IMO a bit cleaner Sexp record:
record Sexp(SexpKind Kind, Token Atom, (Sexp First, Sexp Second)? Pair) {
public String Pretty() {
if (Kind == SexpKind.Atom) return Atom.Value;
const string nil = "NIL";
return $"({Pair?.First.Pretty() ?? nil} . {Pair?.Second?.Pretty() ?? nil})";
}
public static Sexp Append(Sexp first, Sexp second) {
if (first == null) return new (SexpKind.Tuple, null, (second, null));
if (first.Kind == SexpKind.Atom) return new (SexpKind.Tuple, null, (first, second));
return new (SexpKind.Tuple, null, (first.Pair?.First, Append(first.Pair?.Second, second)));
}
}
One issue with original code is that it assumes 'pair' tuple is not null in most places while it is initialized to null at the beginning. I haven't had the time to dive into the code to see how to properly refactor this.
To get more modern C# I would:
- turn on nullable reference types for the project (it takes some time at first to get used to it)
- replace all Tuple.Create calls with new ValueTuple shorthand: (val1, val2)
(Tuple is old class based tuple, ValueTuple is modern struct based tuple type that is integrated into the language)
Code feels very imperative to me. While this is good for performance, using more functional style would probably simplify code a bit more. I'm not sure it is possible though, as I haven't tried to refactor it myself.
Some of this may be down to longer identifiers in Java and C# compared to Go, but also visually it seems there is somewhat more going on in the Java and C# implementations.
I will note that I much prefer writing C#/Java versus Go, and find Go to be generally verbose, but I think that this is not a case for it - the verbosity mostly comes from error handling and lack of generic programming, neither of which is used in this project.
I hate to be negative, but the typescript is terrible. Full strictness is a must.
Once you have that, you will notice why the code is bad:
You have a kind-property on the class. That tells me there should either be 2 separate classes or (much better) just a tagged union. I don’t see that classes has any benefit in this use case, so I’d just get rid of it.
`ctx` is typed as a Map, but it is used like just a plain hash.
I started a similar, though much less advanced project in the past. Here's a CLI that solves http://codekata.com/kata/kata04-data-munging/ written in Clojure, TypeScript, C# and Rust. The LoC are 36, 47, 88, 50.
Would be interesting to have some extra metrics besides line count regarding verbosity.
My intuition based on experience is that Java/C# might have much longer or more complex lines.
Alternatively, maybe verbosity is more about perception. For example, I always feel like Java makes me write more type declarations than should be necessary. Wereas in Python, there might be more code but it is more related to the problem at hand rather than incidental complexity of the language.
Having to write type names when defining variables is a tradeoff between ease-of-writing and ease-of-reading. When reading code in e.g. a book or a patch, where semantic tooling is not available, it helps to know the type of a thing.
My main complaint with Java verbosity is in the type declarations: everything is in triplicate (property names, constructor parameters, getters and optionally setters are all duplicated). The IDE can write these for you, but you still have to read that code.
Something that would be a five-line algebraic data type in Haskell becomes five files, each with a single anemic data class.
This. After learning about ADTs through OCaml, i felt sad working in other languages that don't have them. Spoiled yes, but in a different way than the way the word usually gets used (bratty | pampered). I thought i'll have to stop learning advanced languages because it would make working a dayjob miserable, years before i had my first job. Making impossible states irrepresentable? Yes Please.
Kotlin enabling an approximation through sealed classes and exhaustive, compile time checked, matching with when was noticed, gratefully.
"You can take those ADTs from my cold, dead hands." - Yaron Minsky
Doubly so for building compilers, or compiler-like programs (a long chain of intermediate representations, with lots of little transformations from one to the next).
Adding a new type of node, in a language with ADTs, leads to compile-time breakage I can fix.
In a language where exhaustiveness errors are caught at runtime, it's like building on quicksand.
This is a good question. From my observations, it feels like half the community is just following the "LTS" releases (11, and 17 next month). And then the other 50% is split between chasing the current release and forever being stuck on 8.
It's really sad because JDK 8 really is an antiquated runtime. You're doing a disservice to your developers, users, and your $$ if you're still running it.
Surely a tour de force to do this in this many languages. It’s been helpful to me to see how I might write a parser.
On a different tangent: what is it about lisp that people love so much? Are lisp programmers much more productive? Is the code better in terms of performance or lack of bugs?
I can only answer for myself, but I'm happy to do that.
For context, I've been a professional programmer and technical writer since 1988, and more than half of my career has been spent writing Lisp code for a living.
What is it about Lisp that I love so much?
First and foremost, I can write a program by starting a Lisp running and teaching it incrementally to be the program I want. The Lisp is already a working program; it just isn't the one I want to build. So I teach it one expression at a time how to be the program I want. When it does everything I want it to do correctly and well, I'm done. I can save it and ship it.
This point is the single most important one for me. Most programming languages don't work this way (there are a couple of others that do). I am dramatically more productive working this way than in a batch-compiled style. That's not true for everyone, but it's true for some, including me.
Second, Common Lisp implementations in particular (as well as a small number of other languages, some of which are not Lisp) provide built-in comprehensive support for working that way. They offer a runtime that continues to run as I change it, even when errors occur. Rather than quitting with a backtrace, Lisp responds to an error by spinning up an interactive repl inside the dynamic context that generated the error, enabling me to rummage through the environment, examining and even editing everything in it.
The runtime provides tools and access that enable you to examine and change absolutely everything about iit, while it runs. The runtime has comprehensive information about itself built in, inspection and reflection facilities that enable me to examine and edit everything while it runs, and error-handling that enables me to inspect, diagnose, and repair errors as they occur, without leaving the running Lisp.
I can start a Lisp, interactively construct simple data structures to model my naive assumptions about the program I intend to write, write functions to construct, inspect, and transform those structures, modify their definitions, catch and examine errors, write corrections to data structures and functions while in the dynamic environment that generated an error, continue on my way after making the corrections, and all without leaving and restarting the Lisp.
I can go on in this vein ad infinitum, so I'll arbitrarily stop here. In brief, I love Lisp because it gives me all the tools I want to build and change a program while it runs, it doesn't get in my way, and it yields high-performance code (good native-code compilers are the rule in Common Lisp implementations, rather than the exception).
Oh, and about the idiosyncratic parenthesized syntax that everyone loves to hate: I hated it, too, when I first started, but the interactivity sucked me in. Like many Lispers before and after me, I thought the thing to do was to master the language and then implement a proper syntax for it. Again, like many Lispers before and after me, I eventually came to see the syntax as a strength rather than a weakness, both for how easy it is to write code-manipulation tools for it, and for a nice aesthetic that is maybe only noticeable after one gets over the hatred of parentheses. Parenthesized S-expressions feel like strings of pearls, where each pearl is a nugget of meaning composed of smaller pearls.
This is compelling:
“ First and foremost, I can write a program by starting a Lisp running and teaching it incrementally to be the program I want. The Lisp is already a working program; it just isn't the one I want to build. So I teach it one expression at a time how to be the program I want. When it does everything I want it to do correctly and well, I'm done. I can save it and ship it.”
I really find this compelling. I’m going to give the language a shot. I get some of this with Python. When stuck with a small thing I can code it in the Repl or even import a module or function of my own making and iterate on it.
I'm curious about this way of working. Can you get a preview of all the functions in the system and how they interact with each other? How do you refactor effectively? How do you work with other people in a repository? Compare git changes and other stuff?
If you want to use this as an example of how to write a parser, keep in mind that lisp is exceptionally easy to parse. It has essentially no syntax, in the sense that what you read in and parse is actually what would be output as a parse tree for a more syntactically complicated language.
I would actually study a recursive descent parser for a larger language to give yourself an idea how to write a parser.
Apparently Java still won't have algebraic data types, which are very useful for this kind of code. It does have records, which are like kotlin data classes, a slightly more compact switch statement, and "pattern matching" which isn't actually pattern matching, it just allows you to omit a cast in an if branch if the if condition checks the type using instanceof.
Actually it's not completely true, in Java 17, the switch statement will be able to "match" a class name, and with sealed + permits and records you can have something like algebraic data types.
Still, seems like no destructuring records, but maybe it's not strictly necessary.
Great idea. A suggestion: it may have taken a bit more code, but a powerful and idiomatic way in C# would have been to parse S-Experssions into LINQ expression trees. That would have made parsing more involved but would have made the Eval function trivial.
It has been discussed many times already. Projects like this don't produce a Lisp. It's a toy, Lisp-like language at best. Calling it a Lisp does a disservice to the proper languages in the family.
Excuse the following harshness. But it is due to the dismissive tone I am responding to.
Bullshit. "Lisp" is completely adequate description of a specific succint, elegant and infinitely portable formalism to describe programs - even without the ecosystem.
It is compact and elegant. The concepts within a Lisp like system can be expanded to help in myriad programming tasks.
It's like a koan that cannot be repeated enough until every programmer has implemented a lisp interpreted at least once.
Meh, I agree with the parent you're responding to.
Calling these toys Lisp just leads to more ignorance in the general public. "Oh, Lisp is so small and elegant" and "Lisp is totally impractical because it's so small" are just blatantly incorrect for any "industrial strength" Lisp produced in the past 40 years. Whether Scheme is a Lisp or not is also an internal debate. Not that it matters much, Scheme is a nice base.
JMC's first Lisp paper had goto in it[0] and was described in terms of the hardware it ran on, is this part of the compact and elegant formalism which you are thinking of?
If you want a compact and elegant formalism then grab the untyped lambda calculus. If you want a Lisp, then at least make something with a GC and macro system.
I think we have two schools of thought here. The first appreciates lisp as a formalism, and the second as an industrial strength language.
I don't see why the other would invalidate the other.
Tiny lisp interpreters cherish Lisp as a small formalism that for some people help understand computing on a deeper theoretical level.
It can also be jury rigged on top of any substrate to implement various ad-hoc systems (Greenspuns tenth rule very much applies here).
The fact that we use Lisp in Greenspun 10th form or as a syntax to think about programs does not mean it would be nice to have Lisp production systems.
I don't see how small lisp interpreters would be offensive to anyone. They are pure joy in my opinion, expressing neatly how a topic that sound fairly complex (interpreters) is actually expressible in elegant and succint form.
On public:
"more ignorance in the general public"
I don't know how much public sentiment matters in deep professional fields. I don't need to know how neurosurgeons think about their craft - why should a neurosurgeon know what Lisp is?
SICP is such a legendary book that it should hold Lisp's flag high enough in my opinion.
Producing a full-blown Lisp does not appear to be the primary purpose of this project
Rather, it's an attempt to judge the verbosity of various languages by writing the same small interpreter in each of those languages. I'm not entirely convinced that this is a definitive way of doing this, but that's what the author is trying to do. It says as much on the project page.
I think it's pretty clear from the description that it's only a ~250 line toy project. Looks like it's meant to act as a test for implementing the same project in different languages.
Given that all the implementations were around 10% of each other it doesn't seem like a particularly conclusive result (as far as line count goes, which looks like it was the main metric). At that point minor things like code formatting will make a lot of difference (for example the C# solution is the shortest, but they're using a more concise brace style than the standard one for C#).
Well done. I love the smallness. Small is strong.