[cjh_]

I have been working on a small r7rs scheme interperter [1] and it has been extremely educational. I had never used scheme previously but learning it from sicp [2] has been rather enlightening, it surprisingly lived up to expectations.

I haven't considered if I will go down the compiler route, but either way that resource looks very interesting; especially the coverage on tail call optimisation at the assembly level.

Does anyone have any further resources discussing tail call optimisation? I would like something a bit more in depth.

The other topic I would like to read more on is continuations, as a still newbie-schemer I find the idea of implementing them to be quite daunting.

[1] https://github.com/mkfifo/plot [2] https://mitpress.mit.edu/sicp/

[rayiner]

The best way to deal with tail call "optimization" is to not treat it as an optimization at all. Tail calls are a syntactic property of source code. You can easily determine whether a given call is in a tail position by recursively traversing the AST. Then you just have to generate tail calls in a way that uses constant stack space. This is mostly a matter of properly designing the calling convention. See: www.complang.tuwien.ac.at/schani/diplarb.ps‎.

[cjh_]

Thanks for those words and that link.

I like that way of thinking of it, I see it as just reusing the existing stack frame as a call in a tail call position doesn't need anything from the current stack (returning to this frame adds no extra meaning to it).

Having never implemented them though I feel like my ideas still need some fleshing out, my naive approach seems to be similar to the idea of trampolining.

Really looking forward to reading the linked document, very thorough and looks to be just what I was looking for (it even covers architecture dependent aspects!).

[rayiner]

If you've got the freedom to design your calling convention, you don't need trampolines or anything like that.

The basic idea is to compile every call in a tail position to a jump. You just need to clean up your stack before making the call, and make sure to arrange your calling convention such that A can call B, which can jump to C, which can return directly to A.

In the A -> B -> C example, this means:

1) Using a callee-pops convention so that callees pop arguments off the stack rather than callers. If B and C take different numbers of arguments, A doesn't know how many arguments to pop. So functions should pop their arguments off the stack themselves before they return.

2) B must restore its callee-save registers before jumping to C, which will save those registers itself if it clobbers them.

3) To accommodate variadic functions, there has to be a hidden argument to let callees know how many arguments were actually pushed by the caller, so they can pop the right number.

[jfoutz]

Good old 3imp might be interesting to you, http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Dybvig himself, you might recognize him as the author of the Scheme specification.

[cjh_]

Thanks, that document looks very impressive and will now sit at the top of my reading list :)

Oddly following that link gives me a 404 ('The requested URL /~dyb/papers/3imp.pdf‎ was not found on this server.', seems there is a trailing character '%E2%80%8E').

I was able to find it on google and open it, yielding the link http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

[jfoutz]

Oh weird. sorry about that. Thanks for fixing it.

[ufo]

Its more geared towards ML but I found Appel's Compiling with Continuations very interesting.