CODEWITHSUNDEEP
schemecontinuation-passing
rwallace
rwallace

Reputation: 33365

ANF conversion in continuation passing style

An algorithm for converting code from S-expressions to A-normal form is given at http://matt.might.net/articles/a-normalization/

The author has made the unusual choice of writing the algorithm in continuation passing style. (That is, it's not that the intermediate code is represented in CPS at any stage, but that the handwritten code to do the conversion, is written in CPS.)

It makes sense insofar as I can see how it works, and the continuation represents the body of each generated let, but it is intuitively surprising that CPS should be the clearest way for humans to write code.

Is this actually the clearest form of ANF conversion algorithm, or is there a known better way that doesn't use CPS?

Upvotes: 2

Views: 254

Answers (1)

John Clements
John Clements

Reputation: 17203

I took a look at the original paper, and (based on a cursory reading) the transformation there is formulated as a simple set of rewriting rules. There's nothing there that immediately suggests to me the need for CPS. Looking at Matt Might's blog post, it looks like his use of the continuation is more or less vanilla; that is, it's either passed to a recursive call or called with a "final result"... with the exception of the normalize-name function, which calls k in a non-tail position. So, technically this actually isn't quite CPS.

Either way, it looks to me like Matt was just writing it in CPS out of habit. I'm betting he'd be glad to answer your question, though; it might be a nice break from being the head of a gigantic medical foundation. :)

EDIT: apologies in advance if this answer doesn't add much to your knowledge; it may be that everything I'm saying you already know. Ta!

Upvotes: 3

Related Questions