CPS, SSA, and ANF

Posted on by Heidy

My god! Two blog posts within the same week ? What has this world come to !? Or I’m just getting used to blogging…  After taking my sweet time adjusting to a temporary relocation in Egypt, my stagnant research progress is belatedly coming to an end. So here I am, leisurely sipping on my green tea, listening to Liszt’s tantalizing classical pieces, and reading numerous research papers on Programming Languages. While doing so, I ran across this blog entry that was quite fascinating. It’s definitely a good read for anyone who is interested to know the difference between Continuation Passing Style and Static Single Assignment. In my research project, my professor chose CPS for our implementation, and there is also a bit of a talk pertaining to whether or not we should use SSA in some aspects of it. The author of the aforementioned blog  mentioned Administrative Normal Form (ANF), a style that I definitely have not heard of yet. To my dismay, he didn’t provide an intricate explanation of ANF, which apparently abated the use of CPS in the 90’s.  So I took it upon myself to read “The Essence of Compiling with Continuations”, the paper where ANF was first introduced. Now, I’m not an expert in functional languages (yet!), so I was unsure to why many rejected ANF and persisted with CPS methodologies. Well, good news, there’s a paper for that.I’ll most likely leave this paper for the next blog post, I’ll mainly be discussing ANF today.

While reading a few papers related to ANF, I had to do quite a bit of research on lambda calculus. I’m  familiar with Beta-reductions and CPS, but many other aspects of lambda calculus were certainly unexplored waters. Thus, I have compiled a list of definitions, which are hopefully accurate, that will aide in my explanation of ANF.

Administrative Reduction: Administrative reductions produce CPS terms, “the reduction of the extraneous abstractions introduced by the transformation to obtain continuation-passing.”

Administrative Redex: Redex is short for “Reducible Expression” which is … well,  a reducible expression. They are unnecessary redexes produced by CPS conversion.

Normal Form: The lowest level of reduction, where an element cannot be reduced or re-written any further.

Strong Normalization: If a term is strongly normalized, then every possible reduction or re-write of the term inevitably terminates to a term in normal form.

Weak Normalization: If a term is weakly normalized, then there exists at least one possible reduction or re-write that will terminate a term in normal form.

ß-reduction (Beta)

Eta-conversion(I’ll be using the term “Eta” instead of the actual symbol since WordPress does not support it.)

Sabry and Felleisen produced ANF for source programs as a substitute for CPS. ANF directly corresponds to ßEta CPS terms. Every transformational step included in CPS aligns with a  transformation on “source terms” in ANF. The reduction relations corresponding  to the CPS administrative reductions were named  A-reductions. Sabry and Felleisen demonstrated that ßEta+A-reductions on a call-by-value language is equivalent to ßEta on a CPS’ed call-by-name language”. They also showed that A-reductions are strongly normalized, and a transformation utilizing A-normal form into a continuation-passing style term eliminates administrative redexes within produced term. Of course, any elimination of redexes leads to optimized transformation time. In short, ANF eliminates  intermediate steps that may be crucially necessary for CPS, creating a more implicit and clean representation. To see an example of ANF versus CPS, you should check out the example from the blog that I mentioned above.

I’ll discuss the advantages of CPS next time.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *