Building a Lisp from scratch with Swift | Hacker News Reader

Building a Lisp from scratch with Swift

uraimo.com

122 pointsingve30 comments

Once again pimping one of my favorite DIY projects - Make A Lisp. Lisp in (almost) every language!

I find it to be a great tool for both learning about Lisp and the language you're writing your mal implementation in.

I have never used Swift, but I can confirm that writing a Lisp is a lot of fun in something like C or Go. I especially like the fact that you can build in so much raw power by implementing Lisp macros for example.

Yeah! Even more so if you have first-class macros (fexprs) like say Kernel does. I had a lot of fun building a fexpr-based lisp-1 with quasiquote (which Kernel eschews) and also with a first-class apply that works on both functions and macros. Not even Kernel can do that.

  $ git clone https://github.com/akkartik/wart
  $ cd wart
  $ ./wart
  ready! type in an expression, then hit enter twice. ctrl-d exits.
  mac (foo x)
    `(+ ,x 1)
  => (object function {sig, body})
  (foo 3)
  => 4
  (foo @(list 3))  # apply analogous to the ,@ splice operator
  => 4
  (foo @'(3))
  => 4

More info at http://akkartik.name/post/wart. Lots of example programs at http://rosettacode.org/wiki/Category:Wart.

Take it a step lower and do one in assembly and it is even more fun. I almost have enough code together to say that I'm doing one in RISC-V assembly. At this point I have already accidentally picked up a more intuitive understanding of how a lisp compiler works.

Assembly? Hell, I did mine in microcode, VHDL, and telepathy using a tachyon-driven IDE. It was done before I started.

What about this guy who created universe where life evolved and wrote lisp interpreter for him. That is low level my friend.

I am constantly being outclassed

Funny you should say that:

https://github.com/marcpaq/arpilisp

That is beautifully well documented. Are you planning to extend it further or do any similar projects?

Thanks. The inspiration was jonesforth.

I have no plans to extend it.

A similar project I've considered: write an Algol compiler in assembly. Algol is another elegant, influential language originally implemented in assembly.

I wrote a lisp in Go a while back and got to the point where it could parse and interpret basic lisp code. I got stuck on making it do proper tail call optimization since I didn't want it to do trampolining. Since Go doesn't support TCO the only way I came up with was to rewrite the interpreter either use a big while loop or gotos instead of relying on function calls. Does Swift do TCO making this trivial? Anyone else solved implementing a lisp with TCO in an elegant way in a non-TCO language?

One way is to model the call stack explicitly. I.e. you will need objects (or structs, in Go) representing a stack frame, and have a stack of those (the actual call stack). Evaluation works very different that way, since you can no longer piggyback on the implementation language's call stack. It does mean that you can now do the desired tail call optimizations, e.g. if you're evaluating (if cond a b), and you've evaluated 'cond', then you can replace the if's stack frame with one containing just a or b, and continue evaluation there.

One benefit of this is that continuations become trivial to implement (they're just a snapshot of the call stack at a given point).

Admittedly, almost all write-your-own-Lisp tutorials omit this, and use a bunch of recursive calls (in the implementation language) instead, which makes it very hard to do TCO, continuations or anything else that requires a real call stack (exception tracebacks, for example).

(I hope this answer makes sense; it's 3 in the morning here, so clarity might suffer a bit. ;-) But as it happens, I am writing a (hopefully non-toy) Lisp interpreter myself, in Go, so the question attracted my interest.

> anything else that requires a real call stack (exception tracebacks, for example).

You can go full metacircular and have the interpreter throw an exception and introspect its traceback, in languages that support that.

Author here, no, it doesn't support TCO and you'd have to resort to trampolining here too. In another post[1] I've talked about this and I agree it's definitely not an elegant workaround.

[1] https://www.uraimo.com/2016/05/05/recursive-tail-calls-and-t...

Here's how I did this in .Net: http://patient0.github.io/FirstClassLisp/

As other's have mentioned, TCO and first class continuations tend to go together

You can build a CEK machine (https://cs.umd.edu/class/summer2015/cmsc330/material/cek/), switching from big-step operational semantics to small-step operational semantics. Then you dump the CEK machine in a while loop that runs until the continuation is empty and the code is a value. (On a side note, this is how most C-targeting Scheme implementations work.)

A couple of other Lisp in Swift examples:

http://www.h4labs.com/dev/ios/swift.html?age=10000&q=lisp

Can you type declare the fact that NIL is both a list and an atom in Swift?

It doesn't have to be. In Common Lisp nil is a symbol but not a list. In Racket '() is a list but not a symbol (or a cons).

FWIW, in my rite-of-passage lisp-in-C implementation the type of nil and () is nil, just like the car or cdr of nil: http://akkartik.name/post/wart

In Common Lisp, NIL is a symbol and a list and a Boolean.

Ah, you're right. It's a list but not a cons.

  $ sbcl
  * (symbolp nil)
  T
  * (listp nil)
  T
  * (consp nil)
  NIL

Is there a boolean predicate? My Common Lisp is rusty and I don't see one at https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node73.html#S....

Also, the type of NIL in Common Lisp is NULL. There is a NIL type, but it is empty: there exists no value which is an instance of the NIL type. NIL is a subtype of every type (including itself), and the type T is a supertype of every type, including itself. This situation with NIL and T on opposite ends of the "type spindle" is quite clever and subtly better than making NIL a type which contains NIL.

Thanks for the pointer! I'd never seen http://www.lispworks.com/documentation/lw70/CLHS/Body/t_null... before, in spite of poring over the CLHS for many hours over almost a decade.

Can you suggest any example Common Lisp programs that print the _types_ NULL or NIL or T? Or show off the benefits of this spindle arrangement? I can intuitively see the benefits of this approach, but an example makes things much more memorable.

The nice thing about T is that it's the first letter of True and of Type. E.g.

  ;; catch-all method for any type
  (defmethod foo ((arg t)) ...)

  ;;
  (defmethod foo (arg ...) ...) ;; alternative spelling: omit class

NIL is the empty list and that is mnemonic for "empty type". For instance, the intersection of two mutually exclusive types is the empty type. Nothing can be both a cons and an atom, so the type denoted by the type expression (and cons atom) is empty; and that is nil. The set manipulation which underlies types needs an empty set, and nil fill the need for that empty set (pun intended).

NULL is useful in writing methods that capture NIL (the only instance of NULL). That may be recognized as the "null object pattern":

  (defmethod foo ((arg null))
    ;; (foo nil) called
    )

  (defmethod foo ((arg number))
    ;; (foo <number>) called
    )

  (defmethod foo ((arg t))
    ;; (foo <anything else>) called
    )

> Is there a boolean predicate?

Nope, because everything is a Boolean: NIL is false, and everything else is true.

This is not quite precisely true. Everything is a generalized boolean, but not a boolean. Only T and NIL are of type BOOLEAN, which you can check with the function:

    (defun booleanp (x) (TYPEP x 'BOOLEAN))

You're right, of course. Still, 'everything is a boolean' is close enough for government work:-)

Sure, just make two protocols that nil's class conforms to, one for list and one for atom.

Cool. That's one of the biggest pains I've found with implementing a lisp in a typed language.

I watched this guy developing a productivity app in Swift (https://www.liveedu.tv/zzzel/videos/8OX1z-building-productiv...) and it made me want to go back to Ionic.

Reply on news.ycombinator.com