Continuation Passing Style (CPS) and compile-time evaluation (and parallelism/concurrency)

[dumblob]

After reading nim-lang/RFCs#295 (comment) I immediately thought about Basil as this might come handy for code generation (see C implementation of CPS on few tens of lines a bit similar to Scheme).

The interesting thing I didn't realize until today (despite my craziness into parallelism & concurrency) is that CPS might make parallelism & concurrency easier to implement with guarantees (e.g. memory bounds) which are otherwise hard to achieve when using other techniques and looking for performance. This seems to be true though only if used extensively in compile time.

So I'm writing this as some of the links in https://github.com/weavers-guild/weave-io/tree/master/research might be really useful for Basil.

[elucent]

I've considered continuations before for Basil, primarily in the context of compile-time evaluation. I'm not sure I fully support arbitrary continuations at runtime - they're a bit tricky (can be hard to follow as a reader, and costly/complex to implement in native code esp. with concurrency). But I think it could be potentially interesting to support first-class continuations and environments somewhere down the line - it might be kind of difficult with the tree-walk style Basil's compile-time interpreter uses, but really the world is our oyster as far as compile-time features go.

Not super urgently worried about this though. I think we're content with a simple selection of structured control-flow features for the time being. I'm not concerned with safety to the point of worrying about statically-determining stack size, and at the moment I'm leaning a little more towards a message-passing model of concurrency.

Still super interesting to think about!

[dumblob]

and at the moment I'm leaning a little more towards a message-passing model of concurrency.

It's off-topic here, but I just want to say, that a highly constrained message-passing system can be made surprisingly efficient. The best I know is Weave which some would say is not really message passing but hey, they call it like that, so who cares. It's unbeliavably efficient per core and scales linearly in number of computational cores. It's all built around the extensive macro features of Nim.

Feel free to write about your thoughts regarding concurrency in Basil (probably in a separate issue) - I'll be more than happy to discuss it 😉 (disclaimer: I'm quite into it).

[elucent]

The other thing as it stands is that concurrency is a relatively low-priority feature for Basil. It complicates a tremendous number of things (notably, GC) and isn't critically necessary for Basil to function in certain environments. So it'll probably be some time before it is really considered for implementation, unfortunately.

[dumblob]

Take your time. Actually it sounds like you have some specific use cases for Basil in mind. Would you mind to write about it in more depth some time somewhere?