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

Robert A Duff <bobduff@shell01.TheWorld.com>
Fri, 11 Mar 2011 16:41:15 -0500

          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)
[5 later articles]
| List of all articles for this month |

From: Robert A Duff <bobduff@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Fri, 11 Mar 2011 16:41:15 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 11-03-032
Keywords: syntax, optimize
Posted-Date: 11 Mar 2011 19:55:16 EST

noitalmost <noitalmost@cox.net> writes:


> I was thinking of something like:
> pure function foo(x,y : int) int
> begin
> ...
> end;
>
> Then foo isn't allowed to modify its parameters or to reference
> (except possibly through a parameter) or modify any non-local
> variables. I was thinking of this as a kind of user directive to the
> compiler, like const in C++. "Compiler, this is what I intend, now
> make sure that it's actually enforced."


Ada has something like that. Look up "pragma Pure".


SPARK has "globals annotations" -- every procedure/function is marked
with which globals it reads and writes. If there are none, then it's
pure.


> I put "purely functional" in quotes because I'm using the term pretty
> loosely, since assignments and such would be allowed inside foo. But
> they all have to be to local variables (i.e. not to an alias whose
> data is in some outer scope).


Right -- it's pure from the caller's perspective.


> Can a compiler do this sort of checking, or would the complexity get
> out of hand?


Yes, Ada compilers do it. But rules are needed to make it transitive
(a pure function can't call an impure one).


>...I'm thinking that at least a limited form must be
> possible in order to do any sort of inter-procedural register
> allocation.


I don't see how inter-procedural register allocation is relevant.


The purposes of this feature are to make the code easier to understand,
and to allow the compiler to remove duplicate calls. E.g., if
"F(X)" occurs in a loop, and the compiler can prove that X is
not modified in the loop, it can move the call outside the loop.
(Well, it has to be careful of zero-trip loops.)
Also removing calls when the result is dead.


> My apologies if this is a stupid question. Since I've never seen such
> a thing implemented, I fear that it just might be.


Not a stupid question!


> [See http://publib.boulder.ibm.com/infocenter/ratdevz/v7r6/index.jsp?topic=/com.ibm.ent.pl1.zos.doc/topics/ibma1d111005551.htm -John]


My understanding is that this feature of PL/1 is a promise to the
compiler. That is, the compiler doesn't check that it's true. Is
that correct? The disadvantage is that if you make a mistake, the
program does the wrong thing. The advantage is that you can have pure
memoizing functions and the like (it has a side effect, but that side
effect doesn't matter to the caller).


GNAT (the GNU Ada compiler) has a feature called "pragma
Pure_Function", which is more like the PL/1 feature (unless I am
misremembering how PL/1 does it). That is, pragma Pure_Function is a
promise to the compiler.


- Bob
[Yes, in PL/I it's an assertion. There's no reason that a compiler
couldn't check for obvious problems, but I suspect that the general
issue of deciding whether a procedure is REDUCIBLE quickly reduces
to the intractable halting problem. -John]



Post a followup to this message

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