Make a Lisp | Hacker News Reader

Make a Lisp

github.com

361 pointstalles41 comments

His documentation and approach is priceless https://github.com/kanaka/mal/blob/master/process/guide.md

Agreed, it did not get that far in but this is one of the better explanations I have seen.

Seed, and small accretions. Very neat.

Those diagrams are awesome!

I like how it takes an incremental, step-by-step approach. One of my favourite papers is Ghuloum's "An Incremental Approach to Compiler Construction" [1], which shows how to build not a mere interpreter, but a _compiler_ to actual machine code, in twenty-four steps, starting from simple integers and proceeding through more and more advanced topics.

Shameless plug: I've been trying to follow along, but making it entirely self-contained and avoiding any additional tools. The result (in very early stages, currently dormant but not quite dead yet) is called Lithium [2].

[1]: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

[2]: https://github.com/nathell/lithium

Obligatory cloc reading to see which implementations were shortest:

    -------------------------------------------------------------------------------
    Language                     files          blank        comment           code
    -------------------------------------------------------------------------------
    Rust                            17            294            155           3919
    C                               18            446            383           3356
    C#                              19            472            235           3314
    Visual Basic                    17            322            131           2945
    Java                            17            322            134           2872
    Go                              17            299            147           2636
    Bourne Shell                    16            304            241           2308
    Perl                            19            263            165           2167
    Haskell                         17            328             99           1951
    MATLAB                          25            176            114           1880
    Javascript                      23            263            145           1873
    PHP                             17            242            118           1791
    Scala                           16            219            113           1731
    Lua                             18            227             87           1715
    Python                          18            218            143           1393
    Ruby                            17            165             87           1219
    OCaml                           15            105             98           1154
    Clojure                         17            247            117           1011
    CoffeeScript                    17            193            126            989
    CSS                              6            150            132            792
    make                            26            233             59            580
    HTML                             1             17             27            227
    C/C++ Header                     6             47              9            172
    Maven                            1              2              7             72
    -------------------------------------------------------------------------------
    SUM:                           380           5554           3072          42067
    -------------------------------------------------------------------------------

Apparently Maven is uniquely suited for writing a LISP!

Or at least, describing the project for one.

https://github.com/kanaka/mal/blob/90ab31710e9a495ba3aebf794...

The Maven, HTML, C headers, and CSS are just support.

Forth is missing.

Personally I found Forth implementation the most impressive, even more so than bash. Well, Make comes close :)

Hm, I guess clock doesn't support forth? I just ran `cloc .` from the root directory.

That chart (i.e. cloc) is actually missing 6 of the more interesting implementations:

- forth

- mal itself (e.g. self-hosting: all implementations can run this)

- miniMAL (Lisp interpreter in < 1024 bytes of JS)

- PostScript

- R

- Racket

At first I was surprised to see it implemented in Bash shell.

Then I saw GNU Make.

The language statistics ribbon for this is beautiful.

Shameless plug, but I have a project with 24 languages if you want: https://github.com/bfontaine/Katas

This is right up my alley. You might be interested in a project of mine I work on from time to time: https://github.com/seaneshbaugh/rosetta-euler

Sweet!

Good point. I wonder how many projects have that much languages in a single repo.

This is interesting. Since it's hard to read, I've extracted the language statistics and I'll leave them here:

C# - 7.9% C - 7.2% Rust - 7.1% Visual - Basic - 6.6% Makefile - 6.5% Java - 5.8% Forth - 5.0% Go - 4.5% PostScript - 4.2% Haskell - 4.0% Shell - 3.8% Perl - 3.5% JavaScript - 3.4% Matlab - 3.2% Scala - 3.1% PHP - 3.1% OCaml - 3.0% Lua - 2.8% R - 2.7% Python - 2.7% CoffeeScript - 1.9% Ruby - 1.9% Clojure - 1.9% Scheme - 1.7% CSS - 1.4% Other - 1.1%

It seems you could extrapolate interesting theories regarding productivity using these numbers.

There's a jump between Ruby/CoffeeScript and Python, and I wonder why.

The fact that C# came out with 36% more lines than Java would make me doubt much extrapolation about productivity from these numbers. You can do a token for token substitution of Java and end up with close to compilable C# code; there are only a handful of things Java has that C# doesn't, while C# has many more abstraction tools.

Yep. Things like this:

https://github.com/kanaka/mal/blob/master/cs/core.cs#L272

Could easily be turned into one line ... not that any sane person would want to, though.

This is just because Java is using `readline` and C# is reimplementing it AFAICT.

I'm willing to bet that most of the Java code could be made shorter with the use of more functional style code in Java 1.8 (which might be why he labeled it "Java 1.7")

I was curious about this, so here is the result of my digging.

`core` has inline lambdas in Ruby:

    :prn =>       lambda {|*a| puts(a.map {|e| _pr_str(e, true)}.join(" "))},

but separately defined ones in Python

    def prn(*args):
        print(" ".join(map(lambda exp: printer._pr_str(exp, True), args)))
        return None

    ...

    'prn': prn,

Note that `return None` isn't needed - Ruby doesn't have it, so that's a "wasted" line. The function should also be more like

    def prn(*args):
        print(" ".join(printer._pr_str(exp, True) for exp in args))

or, if Python 2 support wasn't needed,

    def prn(*args):
        print(*(printer._pr_str(exp, True) for exp in args))

Defining these out-of-line is a good idea, though (it improves introspection in Python).

`mal_readline` has a bit of support for Python 2 which takes a few lines, but mostly it's code like

    try:
        with open(histfile, "r") as hf:
            for line in hf.readlines():
                pyreadline.add_history(line.rstrip("\r\n"))
                pass
    except IOError:
        print("Could not open %s" % histfile)
        pass

versus

    File.readlines($histfile).each {|l| Readline::HISTORY.push(l.chomp)}

The Python code handles errors but has two pointless `pass` statements and a couple of odd choices. It should better be:

    try:
        with open(histfile) as hf:
            for line in hf:
                pyreadline.add_history(line.rstrip("\n"))
    except IOError:
        print("Could not open %s" % histfile)

Note that the Python uses lazy reading which is why it needs explicit closing; Ruby likely would too if it read lazily.

I have no idea what's up with `mal_types`/`types`; Ruby does simple stuff and then Python does... something. I will say that the Python can be a lot simpler at minimum, although I'd need to grok what it does before I can say what. For example,

    elif _hash_map_Q(a):
        akeys = a.keys()
        akeys.sort()
        bkeys = b.keys()
        bkeys.sort()
        if len(akeys) != len(bkeys): return False
        for i in range(len(akeys)):
            if akeys[i] != bkeys[i]: return False
            if not equal_Q(a[akeys[i]], b[bkeys[i]]): return False
        return True

can be replaced with

    elif type(a) is Hash_Map:
        return a.keys() == b.keys() and all(equal_Q(val, b[key]) for key, val in a.items())

I think the `_Q` suffix is a the writer missing Ruby's `?`-suffixes on identifiers.

There's also a lot of mess that I think arises because the writer might not be aware that you can make callable objects in Python.

I think in the end it comes down to language experience. My Ruby would probably look as hacky as Joel Martin's Python. I doubt there would be as large a difference if they were both written with the same language familiarity.

I guess it's really hard to be idiomatic in 23 languages.

Python is one of the oldest implementations and I ought to do a another pass through to clean it up sometime.

I'm happy to take pull requests that make an implementation shorter and/or more idiomatic as long as it doesn't change the overall order/flow (and doesn't break any of the tests of course).

> Modern polyglot developers do not memorize dozens of programming languages. Instead, they learn the peculiar terminology used with each language and then use this to search for their answers.

This is the clearest explanation of how polyglot programming works I ever read.

Great work in general, very valuable resource for studying and comparing different languages. I'd like to add one more resource to the mentioned in the guide: http://rigaux.org/language-study/syntax-across-languages/ - it's similar to hyperpolyglot, but has comparisons between non-related languages too. And focuses solely on syntax.

Good resource. Added.

Well, I know what I'm doing this weekend...

Very cool, I am going to have to try out the C one. The only thing missing is HDL (Verilog or VHDL) but there are tons of those out there (e.g. https://github.com/jbush001/LispMicrocontroller)

Excellent -- a much gentler version of Lisp In Small Pieces. (http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...)

I'm working on a lisp interpreter right now, so this should be useful for reference.

One question, how would I go about implementing tail call recursion? I's assume that's a pretty important thing to have in lisp (or any functional language for that matter). I'm working in ruby, if that matters.

I assume you already saw this by now: https://github.com/kanaka/mal/blob/master/process/guide.md#s...

I did not, thanks for the link!

Hi--the project looks beautiful! Maybe the .gitignore could be improved?

now if we can just have it for C please... :)

http://www.buildyourownlisp.com/

mal C implementation: https://github.com/kanaka/mal/tree/master/c

Caveat, no GC. Although that could probably be added easily using the Boehm GC. I plan to do so at some point assuming nobody beats me to it.

oh sorry, i meant if we can have a tiny C, or C-like compiler implementation. :)

(although having a C implementation is awesome, even with the caveat)

lisps are great as an instruction on the subject because of the clean and elegant design, but a C compiler requires tackling all kinds of very nasty problems...

i'm sure it would be very valuable for people wanting to go even further with gaining a practical understanding of programming language/library implementation

Reply on news.ycombinator.com