Re: In a Pascal-like language, would being able to declare a subroutine as "purely functional" be of any value?

noitalmost wrote:


> On Saturday, March 12, 2011 12:37:30 pm Martin Rodgers wrote:
>> Fast and Effective Procedure Inlining (Waddell, Dybvig)
>> http://www.cs.indiana.edu/~dyb/papers/tr484.ps.gz
>
> This was designed for "higher-order languages". Does it apply to a
> Pascal-like language? It'll take me quite a while to decipher the
> paper. I have a hard time understanding lisp-style algorithms.


While the code examples are in Scheme, there's nothing Scheme-specific
about the algorithm. The Scheme core, which is all that's use here, is
very small and simple. In fact, you can see just how simple it is in
the formal definition of the algorithm. In a real compler, this core
language would be larger, but I'm sure the authors kept it simple for
clarity.


This is why it should be easy to adapt to other languages. My
experience using the algorithm is that enriching the AST helped
greatly. I was also struck by how little of it was specific to
Scheme. For example. if the language your compiler uses doesn't allow
statements that can return a value, which I think may be the case,
then just ignore those parts of the paper.


BTW, some of those LET optimisations might apply to C expressions that
use the comma operator. Just move a local variable up a lexical level,
or several. So long as there are no other references to that variable,
they should be equivalent.


However, even in a Pascal-like language, you can get code looking like
this when you inline functions, so your compiler should use an AST
structure that will be equivalent to the Scheme expressions in this
paper.


This may be why some Lisp programmers dismiss Scheme as an "Algol"
relative. ;) I think that's a bit harsh, and bordering on language
advocacy, but there's a good point deep down in there. Inside a
compiler, we sometimes find these odd similarities. Well, I know I
do, but that may be because I like building an AST before or even
instead of generating strings of machine-like instructions. The more I
care about the quality of the code my compilers emit, the more I'm
pushed toward using multi-pass algorithms. I find using trees makes
writing multi-pass compilers much easier, so the ideal compiler
structure for me is
"string->tree->tree->tree/graph->tree/graph...string". Whenever I've
tried using strings anywhere between the input and output, it gets
much harder. However, maybe I just find it hard to work with strings!
There are uses for them inside a compiler, but my understanding is
that they use similar algorithms to those for
parsers. I.e. string<->tree conversions. So it can be done, but I've
never tried it.


Anyway, questions like that are unrelated to your question, so I'll
stop there. I've rambled enough about trees. I was just trying to make
the point that I don't see anything here that is specific to Lisp-like
languages.


I will note that it took *me* a while to decipher the paper, but
mainly because of the formal notation for the unrestrained version of
the algorithm. It took me a long time to convince myself that I didn't
need to use the CPS form in my implementation. You won't need to do
that deep analysis yourself if you take my word for it.


As I said earlier, since you don't need to implement algorithm itself
just to do purity analysis and checks, you should just take what you
can from the paper and not worry about the rest. I used a lot more of
it because I used it as the backbone for the AST-processing part a
compiler. It was a very powerful tool for me, but if your compiler
does the optimisations in a later phase, your AST processing may be
much simpler.

Return to the comp.compilers page.
Search the comp.compilers archives again.