Pure function notation

[si14]

There are a lot of optimization opportunities coming from the ability to distinguish pure functions from unpure. The most important one (IMO) is deforestation: when you have something like sum(transpose(transpose(generate_random_matrix(M, N)) * SCALAR)), you can optimize away an entire matrix construction if you know that sum consumes matrix, generate_random_matrix builds one and all functions that was applied to generated matrix are pure. So it would be handy to have an ability to say that the particular function is pure.

[ViralBShah]

We have had a fair amount of discussion in the past about this. It's good to have this issue to discuss so that it remains on the priority list.

[StefanKarpinski]

@si14: do you mean the ability to annotate a function as pure or for the compiler to determine that the function is pure?

[StefanKarpinski]

Oh, nevermind. I just read the issue subject and it's clear. I once proposed procedure for impure and function for pure, but it was deemed that it would drive users coming from many programming languages and backgrounds completely crazy.

[JeffBezanson]

Yeah, it's good to be able to declare functions pure (optional, unchecked declaration). Even C has that now.

[ViralBShah]

I guess the interface could be @pure function.... What happens if functions marked pure are actually not pure? Would the program run slower, or would it give wrong answers, or undefined behaviour?

-viral

On 20-Feb-2012, at 11:53 PM, JeffBezanson wrote:

Yeah, it's good to be able to declare functions pure (optional, unchecked declaration). Even C has that now.

---

Reply to this email directly or view it on GitHub:
#414 (comment)

[ivanmantova]

If we can't be sure the procedure is indeed pure, we wouldn't be able to optimize it without risking (potentially really bad) undefined behavior.

As for possible optimizations, something like C++ AMP comes to mind.

[StefanKarpinski]

Pure functions would only be allowed to call other pure functions — calling and impure function would be an error (probably run-time, but maybe compile-time). That way you can be sure a function is pure. Each intrinsic would need to be marked as pure or impure; likewise, one would want to be able to indicate whether each ccall is pure or impure. Of course one could lie or be mistaken there, in which case all hell could break loose, but that's what you get for lying.

[si14]

@StefanKarpinski
The question here is balance between let's say Haskell (where all of your functions have controlled side effects and they are reflected in signatures) and JS (where you don't have any control on types). Your architecture looks sane enough (quite easy to implement and a lot of errors would be handled at compile time). Moreover, it can be expanded to an arbitrary "effect system" when you can annotate functions with "effects" like "memory allocation", "mutates arguments" or "can throw exception", with effects propagating through the call stack (the only problem here is that such feature would probably cause a lot of noise in the source file without proper effect inference — maybe one can generate "intermediate" file with all inferred types and effects shown so programmer can check if everything is right). There are a lot of possibilities in the effect system world, for example you can warn your user if he puts some "allocating" function in the tight loop (and this is clearly bad for performance).

[si14]

Here is an example of what I mean: #249 — this "!" is in fact an "effect".

[si14]

And here is an example of "deforestation" optimization: http://arma.sourceforge.net/ . This library uses C++ templates to implement such optimization, and as you can see here http://arma.sourceforge.net/speed.html it's fast.

[StefanKarpinski]

Armadillo is really, really interesting. We've talked a lot about doing things like this to avoid creation of temporaries when executing linear algebra code. The main limiting factor actually has been a collective aversion to doing things that are not dead obvious and dead simple — I'd much rather give the programmer the ability to write this easily in an explicit way than to have the compiler do it automatically in a clever way that might not be obvious to the programmer.

At some point (a while ago), I was arguing for the ! at the end of function names to be enforced — effectively what we're talking about with pure versus impure. The idea was that all functions without a ! at the end would be required to be pure while functions with ! at the end would be allowed to be impure. This idea didn't go over too well, however, I think largely because it was deemed to draconian to force people to put ! everywhere that a side-effect might happen. I wasn't even talking about I/O either, just things that affect global state.

[si14]

@StefanKarpinski , the thing that you are talking about is somewhat different from doing IO, for example. There are different aspects of "purity" and it would be better to have a uniform way to denote different aspects of function behaviour. Let me show you an example in a form of pseudocode.

def first(&a)[mutates]:
    a += 1

def second()[io]:
    print "hello world"

def third()[???]:
    a = 1
    first(a)
    second()

Let's think about this ???. Should we propogate "mutates" effect to the third function? Clearly not. What about "io" effect? Looks like so, because if we now that function will make some IO we can't optimize it away because of unused return, for example. Both first and second are impure, but their impurities are different and so does optimization that can be done on them.
Another examples of impurity are memory allocation or exceptions that can be thrown. And, again, that should be handled by compiler in a different ways.

[StefanKarpinski]

Annotating things in that much detail is a non-starter. It's way too much book-keeping to foist on the programmer. The language has to be usable by people who don't know and don't care what different kinds of functional impurity are. On the other hand, if the compiler can compute and track all of these things for the programmer, then it's cool.

[si14]

@StefanKarpinski Of course compiler can infer effects, it's the whole point :) Moreover, compiler should do it even if programmer explicitly annotate function in some way to control if programmer was mistaken. Look, rules for inferring effects are kinda easy (though different for different effects): some will simply propagate through functions (like "allocation" one — you can't build a function that uses allocating function and don't allocate itself), some will be little harder to infer (like "mutates it's arguments" — "outer" function will be "mutative" only if it passes it's arguments to "mutative" function), but it's definitely useful.
BTW, we can meet in IRC to discuss in more realtime fashion :)

[StefanKarpinski]

I'll hop on IRC at some point, but can't today. I'm on vacation in Buenos Aires...