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

Martin Rodgers <mcr@wildcard.demon.co.uk>
Sat, 12 Mar 2011 17:37:30 +0000

          From comp.compilers

Related articles
In a Pascal-like language, would being able to declare a subroutine as noitalmost@cox.net (noitalmost) (2011-03-11)
Re: In a Pascal-like language, would being able to declare a subroutin gah@ugcs.caltech.edu (glen herrmannsfeldt) (2011-03-11)
Re: In a Pascal-like language, would being able to declare a subroutin bobduff@shell01.TheWorld.com (Robert A Duff) (2011-03-11)
Re: In a Pascal-like language, would being able to declare a subroutin pdjpurchase@googlemail.com (1Z) (2011-03-11)
Re: In a Pascal-like language, would being able to declare a subroutin gah@ugcs.caltech.edu (glen herrmannsfeldt) (2011-03-12)
Re: In a Pascal-like language, would being able to declare a subroutin comp.lang.misc@inglorion.net (Robbert Haarman) (2011-03-12)
Re: In a Pascal-like language, would being able to declare a subroutin mcr@wildcard.demon.co.uk (Martin Rodgers) (2011-03-12)
Re: In a Pascal-like language, would being able to declare a subroutin noitalmost@cox.net (noitalmost) (2011-03-15)
Re: In a Pascal-like language, would being able to declare a subroutin wclodius@los-alamos.net (2011-03-15)
Re: In a Pascal-like language, would being able to declare a subroutin mcr@wildcard.demon.co.uk (Martin Rodgers) (2011-03-16)
Re: In a Pascal-like language, would being able to declare a subroutin sinu.nayak2001@gmail.com (Srinivas Nayak) (2011-03-16)
Re: In a Pascal-like language, would being able to declare a subroutin massimo_dentico@hotmail.com (Massimo A. Dentico) (2011-03-18)
Re: In a Pascal-like language, would being able to declare a subroutin gah@ugcs.caltech.edu (glen herrmannsfeldt) (2011-03-19)
[1 later articles]
| List of all articles for this month |

From: Martin Rodgers <mcr@wildcard.demon.co.uk>
Newsgroups: comp.compilers
Date: Sat, 12 Mar 2011 17:37:30 +0000
Organization: Compilers Central
References: 11-03-032
Keywords: design, optimize
Posted-Date: 12 Mar 2011 23:22:05 EST

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.


Post a followup to this message

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