local variables don't cause side effects
Author Message
local variables don't cause side effects

Quote:

> Right.
> Uh, well, sort of. If you can construct references to local variables,
> and allow assignments via references, a function can indeed modify
> variables outside its scope, so you have to be rather careful about
> what you allow programmers to do with locals. But let me assume that
> all mechanisms that might modify a nonlocal variable were disabled, to
> keep the answer interesting ;-)

> But you don't need them. To transform an imperatively-written function
> into a functional version:
> 1) Whenever the imperative code reassigns to a local variable, just
> create another variable that will take up the new value.
> 2) Whenever there's a loop, move the loop body into a recursive helper
> function. (Note most loops that you'll encounter can be transformed
> into higher-order functions which will do the recursion for you. You
> don't have to reinvent the wheel in every case.)

Example: A function that computes 0 + 1 + 2 + ... + n, given natural
number n.

Incarnation #0:

fun triangle n =
var s := 0, i := 0
while i <= n do
s := s + i; i := i + 1
end while
s

Incarnation #1:

triangle n =
let fun myloop (s,i) =
if i<=n then
myloop (s+i,i+1)
else
(s,i)
in fst (myloop (0,0))

Remark: myloop could return just s and not both s and i - a human
certainly always performs this optimization, and so does an optimizing
compiler that knows live/dead variable analysis.  But conceivably
a naive de-sugarer would simply translate the while-loop into a helper
function that inputs all local variables and outputs all updated local
variables, and leave all the obvious optimizations to another stage.

Quote:
>  > Do local variables really make it any harder
> > to reason about a function's implementation?

> In automatic reasoning: yes.
> (Note that "automatic reasoning" is important when it comes to things
> like compiler optimization. The compiler must reason whether a given
> code transformation preserves the semantics of the program, after all.)

The de-sugaring from incarnation #0 to #1 can be done automatically;
afterwards it is just pure functional reasoning.  If it is deemed
"harder" simply because there is an extra step of de-sugaring, you are
of course technically right - electricity is not cheap during Summer
and in these days of privatization and de-regulation.  (Apologies to
those of you in Winter.)

Quote:
> For a human who's trying to understand a program piece, this depends:
> on prior experience of that human (i.e. whether he has an imperative
> or a functional background, and his general level of expertise); on
> the size of the function; on how clever the original writer of the
> function tried to be; etc.
> In general, it's much more difficult to write obscure code if function
> bodies are written functionally. For a team leader, this alone should
> be enough incentive to select a language that uses referential
> transparency inside of functions :-)

There are people who find incarnation #0 obscure - "variables!  Now I
won't be able to follow who modifies what and when! This is all magic
to me."

There are people who find incarnation #1 obscure - "functions!  Now I
won't be able to follow which value goes to which argument and how!
This is all Greek to me."

Tue, 27 Dec 2005 01:45:53 GMT
local variables don't cause side effects

Quote:

> Example: A function that computes 0 + 1 + 2 + ... + n, given natural
> number n.

> Incarnation #0:

>   fun triangle n =
>     var s := 0, i := 0
>     while i <= n do
>       s := s + i; i := i + 1
>     end while
>     s

> Incarnation #1:

>   triangle n =
>     let fun myloop (s,i) =
>               if i<=n then
>                 myloop (s+i,i+1)
>               else
>                 (s,i)
>     in fst (myloop (0,0))

Incarnation #2:
triangle n = n * (n + 1) / 2

Tue, 27 Dec 2005 03:43:32 GMT
local variables don't cause side effects
Marshall,

This is actually a great question.  Pay no attention to the functional
programming curmudgeons (referential transparency isn't a religion,
it's a tool).

From the outside, a function that has no side-effects or dependence on
external state or I/O is referentially transparent and can be treated
uniformly regardless of whether its internal implementation is purely
functional or locally imperative.

From the inside -- when you get to evaluating the function's body --
whether the code is purely functional or (at least partly) imperative
has a huge impact on your evaluation strategy.  For example, lazy
evaluation can be a reasonable strategy when evaluation functional
code, whereas evaluation order must be precise and explicit in
imperative code.

In a language that supports both paradigms, being able to distinguish
"functional functions" and "imperative functions" is very valuable.
For one example, in an implicitly parallelizing compiler, a call to a
purely functional function can be handed off to another thread; if
many such calls exist in a region of code with no intermingled
side-effects, then N calls can be handed off to N independent CPU's
without worrying about their global evaluation order -- even if those
functions happen to use locally imperative code internally (for
example, by manipulating a local heap that's discarded upon return).

I've been able to mix and match both paradigms in an experimental
compiler and am very happy with the results.  My feeling is that for
real-world development projects carried out by mainstream programmers
(i.e. games, graphical user interfaces, large-scale server apps),
imperative features are essential to a language's success.

But allowing both functional and imperative approaches to be mixed, in
the local-vs-global approach you suggest, gives you the best of both
worlds.

Tue, 27 Dec 2005 09:33:50 GMT
local variables don't cause side effects
Quote:
>> If you can construct references to local variables,

and allow assignments via references, a function can indeed modify
variables outside its scope, so you have to be rather careful about
what you allow programmers to do with locals. But let me assume that
all
mechanisms that might modify a nonlocal variable were disabled, to
keep

For those interested, there is a great body of research on this topic,
the general idea being that multiple heaps can exist; pointers carry
around "which heap do I point to" information, and one is prevented
(at the typechecking level) from writing to someone else's heap.

Quote:
>> But you don't need them. To transform an imperatively-written

function
into a functional version:
1) Whenever the imperative code reassigns to a local variable, just
create another variable that will take up the new value.
2) Whenever there's a loop, move the loop body into a recursive helper
function. (Note most loops that you'll encounter can be transformed
into
higher-order functions which will do the recursion for you. You don't
have to reinvent the wheel in every case.) <<

This works for the case of loops within a single function which
"update" loop variables during iteration.  Such constructs can always
be translated into tail-recursive functions quite easily.

But that's not the case, in general, with imperative code.  For
example, if one desires the ability to dynamically allocate local
objects within a function and manipulate those objects as well as
mutable references to them, in that function, and in other nested
functions, with the general ability to update such references through
closures, then the translation to purely functional code is far more
complex.  Haskell has solved the problem in purely functional exposure
of a behind-the-scenes native implementation quite elegantly (google
functional typesafe verifyably divergence-free mechanism is an open
research problem that probably requires a more advanced type system to
solve.

Overall, I think the notion of "translating arbitrary imperative
programs into purely functional ones" is a very valuable way of
conceptualizing, theorizing, and reasoning about things like mutable
references and exceptions.  But it shouldn't be considered an
implementation technique, because it's vastly more complex and less
efficient than just exposing imperative functionality in the language
itself.

Tue, 27 Dec 2005 09:49:17 GMT
local variables don't cause side effects

Quote:

> Incarnation #2:
> triangle n = n * (n + 1) / 2

You're beside the point.
replacing an algorithm with an entirely different one.

Regards,
Jo

Tue, 27 Dec 2005 17:32:06 GMT
local variables don't cause side effects

Quote:

>> Incarnation #2:
>> triangle n = n * (n + 1) / 2

> You're beside the point.
> replacing an algorithm with an entirely different one.

if the compiler or interpreter knows that the arguments are integers, then
this is the best optimization and it would be fine, if the system could do
it automatically, perhaps with an integrated math CAS system for symbolic
calculation.

--

http://www.frank-buss.de, http://www.it4-systems.de

Tue, 27 Dec 2005 17:59:52 GMT
local variables don't cause side effects

Quote:

>>>Incarnation #2:
>>>triangle n = n * (n + 1) / 2

>>replacing an algorithm with an entirely different one.

> if the compiler or interpreter knows that the arguments are integers, then
> this is the best optimization and it would be fine, if the system could do
> it automatically, perhaps with an integrated math CAS system for symbolic
> calculation.

It's not worth the effort.
It would take more effort to teach compilers to apply the right
transformations, than simply to write down the simpler algorithm.

Computers are no substitute for mental effort. I'm not sure how long it
will take until they are, but I fear this will happen within the next
Not that mental laziness in itself is bad, but I shudder at the
consequences in the political arena. (Well, that's definitely going
off-topic now.)

Regards,
Jo

Tue, 27 Dec 2005 18:33:37 GMT
local variables don't cause side effects

Quote:

> There are people who find incarnation #0 obscure - "variables!  Now I
> won't be able to follow who modifies what and when! This is all magic
> to me."

> There are people who find incarnation #1 obscure - "functions!  Now I
> won't be able to follow which value goes to which argument and how!
> This is all Greek to me."

It strikes me that the thing about #1 that will cause consternation in some
people isn't functions; it's recursion.

Probably it's been a long time since anyone here hard a hard time thinking
about recursion, but it's a real sticking point in teaching programming.
I don't think loops with variables produce the same level of difficulty.

Marshall

Tue, 27 Dec 2005 23:20:36 GMT
local variables don't cause side effects

Quote:

> For one example, in an implicitly parallelizing compiler, a call to a
> purely functional function can be handed off to another thread; if
> many such calls exist in a region of code with no intermingled
> side-effects, then N calls can be handed off to N independent CPU's ...

I find this possibility fascinating. It seems clear that available architectures
influence the development of computer languages, and vice versa. We
are entering an era where clustering is available to the home user;
what impact this might have on languages is interesting to speculate on.
My suspicion is that computing models that are easier to paralellize
will become more popular.

Quote:
>  My feeling is that for
> real-world development projects carried out by mainstream programmers
> (i.e. games, graphical user interfaces, large-scale server apps),
> imperative features are essential to a language's success.

> But allowing both functional and imperative approaches to be mixed, in
> the local-vs-global approach you suggest, gives you the best of both
> worlds.

Right on!

Marshall

Tue, 27 Dec 2005 23:28:15 GMT
local variables don't cause side effects

Quote:

> Probably it's been a long time since anyone here hard a hard time thinking
> about recursion, but it's a real sticking point in teaching programming.
> I don't think loops with variables produce the same level of difficulty.

Yes they do.
I found it quite unnerving that I had to write bogus things like
"I = I + 1" to increment the loop variable.

At a more fundamental level, assuring that a loop works is just as
simple or easy as assuring that a recursion Does the Right Thing. Loops
and recursion are equivalent in so many ways that I'm somewhat surprised
that recursion is still considered more difficult to teach (and maybe
it's really harder to understand - for some reasonable definition).

Regards,
Jo

Wed, 28 Dec 2005 00:55:33 GMT
local variables don't cause side effects

Quote:

>>For one example, in an implicitly parallelizing compiler, a call to a
>>purely functional function can be handed off to another thread; if
>>many such calls exist in a region of code with no intermingled
>>side-effects, then N calls can be handed off to N independent CPU's ...

> I find this possibility fascinating.

Don't hold your breath: home users have little if any use for that.
Unless they are heavily into {*filter*}, in which case the CPU load is most
likely split between mainboard and graphics card, which is a scenario
that's quite the opposite of parallelizing function calls.

That's just a side note. The *real* problem is that handing off
computations to a different processor often entails more work than just
stacking the call. Compilers may try to predict which calls should be
parallelized and which shouldn't, but mispredictions in that area will
quickly eat up the advantages gained here.

Besides, you usually don't have N processors, you have at most two.
Maybe four, in the next five years or so - but I wouldn't bet on that.
Besides, even with SMP, if two processors share the same memory bus,
memory latencies tend to eat up another gob of the performance advantage.

In principle, it's all a great idea. In practice, there are so many
little hurdles that take away a percent here, a percent there that it's
not so great anymore.

Quote:
>>But allowing both functional and imperative approaches to be mixed, in
>>the local-vs-global approach you suggest, gives you the best of both
>>worlds.

The one thing that I've been missing for two years now is that nobody
has yet shown a convincing example of this:
How to write code that
a) is (possibly heavily) imperative
b) has a purely functional interface
c) allows the compiler to infer (b) even in the presence of (a).

For example, I'd like to use imperative data structures to build
functional containers. No way, even though I'm prepared to annotate all
the loops with loop invariants to help the compiler along...

Regards,
Jo

Wed, 28 Dec 2005 01:03:28 GMT
local variables don't cause side effects

On Fri, 11 Jul 2003 19:03:28 +0200

Quote:

> >>But allowing both functional and imperative approaches to be mixed,
> >>in the local-vs-global approach you suggest, gives you the best of
> >>both worlds.

> The one thing that I've been missing for two years now is that nobody
> has yet shown a convincing example of this:
> How to write code that
> a) is (possibly heavily) imperative
> b) has a purely functional interface
> c) allows the compiler to infer (b) even in the presence of (a).

> For example, I'd like to use imperative data structures to build
> functional containers. No way, even though I'm prepared to annotate
> all the loops with loop invariants to help the compiler along...

You may be interested in Aleksandar Nanevski's paper "A Modal Calculus
for Effect Handling" (http://www-2.cs.cmu.edu/~aleks/).  It is quite
theoretical, but I believe it addresses the issue you raise.  Perhaps in
a few years we can hope to get some languages that incorporate these new
ideas.

Benjamin

Wed, 28 Dec 2005 01:39:20 GMT
local variables don't cause side effects

Quote:

>>The one thing that I've been missing for two years now is that nobody
>>has yet shown a convincing example of this:
>>How to write code that
>>a) is (possibly heavily) imperative
>>b) has a purely functional interface
>>c) allows the compiler to infer (b) even in the presence of (a).

>>For example, I'd like to use imperative data structures to build
>>functional containers. No way, even though I'm prepared to annotate
>>all the loops with loop invariants to help the compiler along...

> You may be interested in Aleksandar Nanevski's paper "A Modal Calculus
> for Effect Handling" (http://www-2.cs.cmu.edu/~aleks/).

Thanks for the pointer.
A bit too theoretical for my taste, but then this is obviously an open
research issue so I'll have to wait until this all solidifies into a
usable framework.

(I do have my own ideas in this area, but not being a researcher I don't
get paid to follow them up to anything useful. Pity, but...)

Regards,
Jo

Wed, 28 Dec 2005 01:55:01 GMT
local variables don't cause side effects

Quote:

> > if the compiler or interpreter knows that the arguments are integers, then
> > this is the best optimization and it would be fine, if the system could do
> > it automatically, perhaps with an integrated math CAS system for symbolic
> > calculation.
> It's not worth the effort. It would take more effort to teach compilers
> to apply the right transformations, than simply to write down the
> simpler algorithm.

It depends -- you only have to teach the compiler once, whereas the
algorithm will be human optomized many many times, by many different
people.

Wed, 28 Dec 2005 06:13:27 GMT
local variables don't cause side effects

Quote:

> At a more fundamental level, assuring that a loop works is just as
> simple or easy as assuring that a recursion Does the Right Thing. Loops
> and recursion are equivalent in so many ways that I'm somewhat surprised
> that recursion is still considered more difficult to teach (and maybe
> it's really harder to understand - for some reasonable definition).

I think it comes down to people simply being uncomfortable with abstract
thought. If you try and reason about recursion the same way you would a
loop, by mentally executing it, it can be quite confusing. It takes
practice to have enough faith in logic to let go and reason comfortably