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

noitalmost wrote:


> Can a compiler do this sort of checking, or would the complexity get
> out of hand? I'm thinking that at least a limited form must be
> possible in order to do any sort of inter-procedural register
> allocation.


It might be helpful to look at how this is done in inlining and
specialisation, as similar analysis is needed. It should be easy to
adapt the algorithm in the paper below to your needs by adding checks
to enforce a purity policy rather than merely exploiting opportunities
for optimisation. I esp like the algorithm's linear performance. The
paper's title does not exaggerate!


Fast and Effective Procedure Inlining (Waddell, Dybvig)
http://www.cs.indiana.edu/~dyb/papers/tr484.ps.gz


My experience with implementing this algorithm is that it isn't
complex at all. The formal description in the paper may appear a
little complex at first, until you realise that it can be implemented
without using the purely functional CPS form used in the paper.
That's why it's a formal description, and not code. You don't need to
pass the store state around to make it work.


So, apart from this small bit of advice, it's pretty straightforward.
Just the regular kind of book keeping that compilers do. The algorithm
walks the AST, making records etc. The worst case performance is where
every part of the AST is visited twice, but you should get away with a
single pass just for checking a purity policy. It'll only get complex
if you want to implement the enhancements described later in the
paper, and you'll only need that for inlining and specialisation.


Alternately, ignore the algorithm itself and just borrow some
ideas from the operand/var records (page 3). That's where all
the book keeping takes place.

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