[archevel]

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?

[zephyrfalcon]

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.

[taejo]

> 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.

[drtse4]

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...

[Patient0]

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

[kaosjester]

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.)