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

Hi all,

So I'm reading all this stuff about functional programming lately,
and it seems like the literature is often conflating two ideas:
that functional languages don't have variables, and that a function's
return value(s) are determined solely by the argument values.

Well, they are not the same thing. If a function doesn't have
access to global state, but its implementation *can* make
use of local variables, then it's going to have the parameters-
uniquely-determine-results property. Right?

So, can a language still be considered functional if it allows
for local variables? Do local variables really make it any harder
to reason about a function's implementation?

Marshall



Sun, 25 Dec 2005 13:29:45 GMT  
 local variables don't cause side effects

Quote:

> So, can a language still be considered functional if it allows
> for local variables? Do local variables really make it any harder
> to reason about a function's implementation?

Side effects within a function are just as hard to deal with as ones
at the top level.  Learn a functional language first, then start asking
weird questions.

David



Sun, 25 Dec 2005 14:35:05 GMT  
 local variables don't cause side effects

Quote:

> Well, they are not the same thing. If a function doesn't have
> access to global state, but its implementation *can* make
> use of local variables, then it's going to have the parameters-
> uniquely-determine-results property. Right?

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.)

Quote:
> So, can a language still be considered functional if it allows
> for local variables?

This depends a lot on the definition of the day for "functional" ;-)

However, at the interface level, the function will indeed be functional
(the more generally accepted term for that property is "referentially
transparent", which means it's irrelevant whether you substitute the
function directly into the call place or use the function name - i.e. a
reference to the actual function).

 > Do local variables really make it any harder

Quote:
> 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.)

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 :-)

Hope this helps.
Jo

P.S.: Don't let yourself be deterred by responses like those of David
Feuer - I don't know why he reacted in such a harsh manner.
Let me assure that I don't consider your question "weird". Actually it
made me rethink an aspect of my personal definition of "fundamental",
and I generally consider it good when I can sharpen my perception of
things by answering such questions :-)
JD



Sun, 25 Dec 2005 16:31:36 GMT  
 local variables don't cause side effects

Quote:

>  Hi all,

>  So I'm reading all this stuff about functional programming lately,
>  and it seems like the literature is often conflating two ideas:
>  that functional languages don't have variables, and that a function's
>  return value(s) are determined solely by the argument values.

>  Well, they are not the same thing. If a function doesn't have
>  access to global state, but its implementation *can* make
>  use of local variables, then it's going to have the parameters-
>  uniquely-determine-results property. Right?

Not necessarily -- here's an example in Scheme and Ocaml:

(define gensym
   (let ((state 0))
   (lambda ()
      (set! state (+ state 1))
      state)))

let gensym =
  let state = ref 0 in
  fun() ->
    (state := !state + 1;
     !state)

What this does, at the interpreter prompt:

  # gensym();;
  - : int = 1
  # gensym();;
  - : int = 2
  # gensym();;
  - : int = 3

We've defined a function gensym that has some local state (a counter)
that persists from call to call, but which doesn't access any global
state.

The general idea that you haven't quite wrapped your head around is
that functions are values too, and that you can define new functions
and return them as values. Since a closure can capture bindings, this
means that local state can "escape" the caller.

Quote:
> So, can a language still be considered functional if it allows for
> local variables? Do local variables really make it any harder to
> reason about a function's implementation?

A language can be considered functional even if it has variables and
side-effects, as both Scheme and ML do. IMO the two things that permit
programming in a functional style are the ability to create function
closures as first-class values, and tail recursion.

--
Neel Krishnaswami



Sun, 25 Dec 2005 20:07:51 GMT  
 local variables don't cause side effects

Quote:


> > So, can a language still be considered functional if it allows
> > for local variables? Do local variables really make it any harder
> > to reason about a function's implementation?

> Side effects within a function are just as hard to deal with as ones
> at the top level.  Learn a functional language first, then start asking
> weird questions.

If the noobs didn't come around at regular intervals and ask weird
questions, the experts would get bored. How would they know
what they know after a while? Epistemology would suffer. :-)

Marshall



Sun, 25 Dec 2005 22:43:36 GMT  
 local variables don't cause side effects

Quote:

> A language can be considered functional even if it has variables and
> side-effects, as both Scheme and ML do. IMO the two things that permit
> programming in a functional style are the ability to create function
> closures as first-class values, and tail recursion.

IMHO it's essential that you can conveniently program without side effects.
Working with immutable values, the essence of functional programming, may be
hard or easy depending on the language. Most modern languages, even those
not considered functional, make it easy (e.g. Python, Ruby) but not all
(e.g. Eiffel and languages without GC).

This requires:

- Garbage collection, so you can freely share identical substructures which
  occur often if an object is replaced with a similar one instead of
  mutating it in place.

- Efficient passing and returning objects by reference, because you do this
  a lot. A function returns a large structure instead of putting it in
  another mutable data structure. In practice this coincides with garbage
  collection.

- Data structures holding pure data - easily defined, constructible by
  expressions, and supported by libraries.

  Negative examples: In Eiffel an object's constructor is invoked by a
  statement initializing a variable, not by an expression. In C++ there
  are no tuples nor array literals, fortunately libraries can help a bit.
  Smalltalk makes functional programming harder because the standard library
  provides only imperative data structures - I think even Lisp-like lists
  would have to be defined from scratch if one wanted to program in the
  functional style.

--
   __("<         Marcin Kowalczyk

    ^^     http://qrnik.knm.org.pl/~qrczak/



Sun, 25 Dec 2005 22:58:33 GMT  
 local variables don't cause side effects

Quote:

> IMHO it's essential that you can conveniently program without side effects.
> Working with immutable values, the essence of functional programming, may be
> hard or easy depending on the language. Most modern languages, even those
> not considered functional, make it easy (e.g. Python, Ruby) but not all
> (e.g. Eiffel and languages without GC).

Imho Eiffel does allow functional programming much better than Ruby.
(If only because it allows programming much better.)

Quote:
>   Negative examples: In Eiffel an object's constructor is invoked by a
>   statement initializing a variable, not by an expression.

Eiffel includes creation expressions since quite a time.  Also it
includes first-class functions and the standard library provides some
higher-order-standard-function.

But traditionally Eiffel programmers have used a very imperative style,
and, consequently, standard libraries have not been very functional
either.  Probably this is because Eiffel's good structured programming
and abstraction mechanisms do take imperative programming very far
before it sucks.  Other languages (like Ruby) rather go for more
features than an overall good design.

Quote:
>  I think even Lisp-like lists would have to be defined from scratch
>  if one wanted to program in the functional style.

But Lisp-like lists is not what programming needs.  In Eiffel I am
programming with sequences (an immutable data structure, whose mutable
sister I call list), which are implemented in a class, and I don't care
how.  (Although I wrote the implementation.)  Instead of working CAR and
CDR (or head and tail), I'm using more powerful sequence combinators:
map, concat, filter.  Of course, there is also head and tail (although I
followed the Scheme convention and called them first and but_first,
because there's also last and but_last and all of them are similarly
efficient: constant amortized or logarithmic depending on the
implementation variant).

Bob.

PS: I'll post a link to my immutable Eiffel data structures, when the
library is finished.  They're really simpler and more flexible than
those in other languages.



Mon, 26 Dec 2005 00:40:20 GMT  
 local variables don't cause side effects

Quote:


>>   Negative examples: In Eiffel an object's constructor is invoked by a
>>   statement initializing a variable, not by an expression.

> Eiffel includes creation expressions since quite a time.

Are they standardized yet?

 > Also it

Quote:
> includes first-class functions and the standard library provides some
> higher-order-standard-function.

Yes - but Eiffel doesn't even attempt to keep the consequences of having
higher-order subroutines and side effects under controls.
It's powerful but too dangerous IMHO.

Quote:
> But traditionally Eiffel programmers have used a very imperative style,

Mostly because creation expressions are a rather late addition :-)

Quote:
> and, consequently, standard libraries have not been very functional
> either.  Probably this is because Eiffel's good structured programming
> and abstraction mechanisms do take imperative programming very far
> before it sucks.

I think it's more a question of mentality.
Eiffel was created in a strongly imperative mindset, attracted
imperative programmers, and caused the vast majority of library code to
be written imperatively.
Even the design philosophy of Eiffel is strongly imperative: there's a
sharp distinction between functions (returning values from an object)
and procedures (modifying the state of an object).

Another problem in Eiffel is its a-class-is-a-module-is-a-class
philosophy. A collection of routines that create and return functional
objects doesn't have an easy resting place. If you want to write (say) a
data structure library, you need two classes for every type: one to
define the actual type, one to define the constructor routines.
Not having creation expressions just added to the pain... (I know, I
tried exactly this two years ago, on a compiler that didn't support
creation expressions... this could be worked around, but being forced to
define a type when I just wanted a module drove me nuts as well).

 > Other languages (like Ruby) rather go for more

Quote:
> features than an overall good design.

I can't comment on Ruby, I don't know it.
I have read people singing its praise though.

Quote:
> PS: I'll post a link to my immutable Eiffel data structures, when the
> library is finished.  They're really simpler and more flexible than
> those in other languages.

Ah - send me a note when you're done. It will be interesting to compare
ideas and mechanisms.

Regards,
Jo



Mon, 26 Dec 2005 02:37:04 GMT  
 local variables don't cause side effects

Quote:

> > A language can be considered functional even if it has variables and
> > side-effects, as both Scheme and ML do. IMO the two things that permit
> > programming in a functional style are the ability to create function
> > closures as first-class values, and tail recursion.

> IMHO it's essential that you can conveniently program without side effects.
> Working with immutable values, the essence of functional programming, may be
> hard or easy depending on the language. Most modern languages, even those
> not considered functional, make it easy (e.g. Python, Ruby) but not all
> (e.g. Eiffel and languages without GC).

Ruby is a weird little language. It definitely strongly encourages a
higher-order style of programming -- it has a feature called
"iterators" which is basically a way of passing a function to a
routine as an implicit argument. But it doesn't have tail calls.

I think that FP techniques are soaking into the open-source PL-hacker
community, and this is great news. Maybe the next big scripting
language will have support for tail call optimization.

Quote:
>  This requires:

>  - Garbage collection, so you can freely share identical substructures
>    which occur often if an object is replaced with a similar one instead
>    of mutating it in place.

I had just kind of assumed this was necessary to implement closures.

Quote:
>    Negative examples: In Eiffel an object's constructor is invoked by a
>    statement initializing a variable, not by an expression. In C++ there
>    are no tuples nor array literals, fortunately libraries can help a bit.

I'm very surprised that creation expressions weren't in Eiffel from
the start -- the progress of programming language design can, in many
ways, be seen as making more and more things anonymous. Eg, in
assembly language, you have to explicitly name all temporaries, but in
fortran, you can have arithmetic and boolean expressions. In Pascal
and C, you have to name all your functions, but in Scheme and ML, you
can have anonymous functions, etc etc.

--
Neel Krishnaswami



Mon, 26 Dec 2005 02:58:56 GMT  
 local variables don't cause side effects

Quote:

> Imho Eiffel does allow functional programming much better than Ruby.
> (If only because it allows programming much better.)

What Ruby lacks wrt. functional programming? I know it doesn't provide
functional data structures in the library, e.g. it has no immutable list
type (with constant time cons & tail) or dictionary type (with logarithmic
time non-destructive insertion and deletion). But most "non-functional"
languages don't provide them either and Ruby has the needed language
features, and its syntax is sufficiently expression-oriented.

Eiffel is in minority with returning values from functions by assigning them
to the special variable called Result. Of course it's as expressible as the
most common styles (function body being an expression or having the return
statement), but it doesn't feel functional :-)

Quote:
> Eiffel includes creation expressions since quite a time.

Good to know. It didn't when I read about it (about two years ago).

Quote:
> Also it includes first-class functions and the standard library provides
> some higher-order-standard-function.

Can you wrap in functions expressions and statements written inline, with
arbitrary free variables? Or is it still only the "bind some arguments
and/or the receiver of a method" feature called agents?

Do other implementations support that, besides the commercial implementation
associated with Bertrand Meyer (I think there is a "main" implementation
which drives the language development, and it's not open source)?

Quote:
> PS: I'll post a link to my immutable Eiffel data structures, when the
> library is finished.  They're really simpler and more flexible than
> those in other languages.

Aha, so you can program in the functional style in Eiffel provided that you
use a non-standard library which isn't finished yet? :-)

One side is language features: function closures, some equivalent of
algebraic types, ability to freely share immutable subcomponents. The other
side is the library - the need of reinventing functional data structures
and making them fit the rest of the library.

For example it would be a pity if the method returning sequence length used
in the standard library was compatible only with flat mutable sequences
(being declared in some superclass which provides an array-like interface),
or if iteration protocol relied on random-access indexing (as python used
to do).

How to emulate algebraic types in Eiffel? E.g. imagine a tree representing
an intermediate form of a code inside a compiler. Do I have to define each
case in a separate file? Can I write an ML-style case expression (or at
least a statement) - matching just the top level class is enough, but I
want the access "constructor arguments" of particular cases in their
respective branches?

For example let's take an OCaml function I've actually used (Pair is one of
constructors of a large algebraic type). How would it look like in Eiffel
in functional style?

let rec flattenExprs = function
  | [] -> []
  | Pair (_, x, y) :: rest -> flattenExprs (x :: y :: rest)
  | x :: rest -> x :: flattenExprs rest

--
   __("<         Marcin Kowalczyk

    ^^     http://qrnik.knm.org.pl/~qrczak/



Mon, 26 Dec 2005 06:27:20 GMT  
 local variables don't cause side effects

Quote:

> [lots of relevant critique of Eiffel as a not really functional language snipped]

The point of the agent stuff in Eiffel is not making Eiffel a functional
language. It's making Eiffel more useful - not of particular interest
here in clf, but still a laudable intention.
An immutable data structure library would be somewhat interesting, just
to point out that functional data structures have begun making their way
into imperative languages. (Eiffel is still massively imperative. You
can't guarantee that an object is immutable, it might be of a subtype
with mutators added to the class. The main designer of the language will
accept ideas only on a thrice-per-decade basis, so it's unlikely that
he'll ever joint the functional bandwagon - which is a Bad Thing if you
believe in functional programming, and a Good Thing if you believe in
multiple paradigms being explored, the failing paradigms still useful as
a contrast to the succeeding ones. Besides, making Eiffel a "clean
functional language" would require ripping out its type conformance
rules and rewriting all the base libraries and all the applications
written in it - nothing that's even remotely feasible.)

Regards,
Jo



Mon, 26 Dec 2005 06:34:33 GMT  
 local variables don't cause side effects

Quote:
> Aha, so you can program in the functional style in Eiffel provided that you
> use a non-standard library which isn't finished yet? :-)

A little unfair I think, (and yes I did notice the "smiley").

An equivalent point is that you can program in the imperative style in
Haskell provided that you use the Monad library which is still under
research and development.

And the difference is?



Mon, 26 Dec 2005 16:09:01 GMT  
 local variables don't cause side effects

Quote:


>> If a function doesn't have
>> access to global state, but its implementation *can* make
>> use of local variables, then it's going to have the parameters-
>> uniquely-determine-results property. Right?

> Not necessarily -- here's an example in Scheme and Ocaml:

> (define gensym
>    (let ((state 0))
>    (lambda ()
>       (set! state (+ state 1))
>       state)))

> let gensym =
>   let state = ref 0 in
>   fun() ->
>     (state := !state + 1;
>      !state)

This is not a counter example, IMHO, because the state reference is
global to the actual function expression (even though its scope is
restricted to it).

I think Marshall is right with his conjecture. E.g. consider Haskell's
ST monad, which you can run locally. But as others pointed out, that
does not necessarily imply anything.

| Andreas

--

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.



Mon, 26 Dec 2005 18:06:47 GMT  
 local variables don't cause side effects

Quote:

> An equivalent point is that you can program in the imperative style in
> Haskell provided that you use the Monad library which is still under
> research and development.

> And the difference is?

That Haskell monads aren't under research anymore?

I'm sure that there's a lot of reasearch underway concerning monads, but
I'd be rather surprised if there were no usable, useful stable subset of
the monad library. Last time I looked, there wasn't even a defacto
language standard for agents (Eiffel's variant of closures).
Since I have left the Eiffel community (and lost most of my interest in
Eiffel as well), I don't know how things have been progressing in the
last, say, three or four months.

Regards,
Jo



Mon, 26 Dec 2005 20:55:30 GMT  
 local variables don't cause side effects

Quote:


>> Aha, so you can program in the functional style in Eiffel provided that you
>> use a non-standard library which isn't finished yet? :-)

> A little unfair I think, (and yes I did notice the "smiley").

> An equivalent point is that you can program in the imperative style in
> Haskell provided that you use the Monad library which is still under
> research and development.

> And the difference is?

One major difference, if I understand the debate correctly, is that the
Monad library is part of the Haskell 98 standard -- any *standard
conforming* implementation *must* include Monad and IO facilities.

William



Tue, 27 Dec 2005 01:06:05 GMT  
 
 [ 83 post ]  Go to page: [1] [2] [3] [4] [5] [6]

 Relevant Pages 

1. problem with FOR statement (side effect on control variable)

2. Forth's popularity, side-effect

3. do GUI's require side effects?

4. Walt's side effect order changed by -g

5. don't understand cause of `sysread': Bad file descriptor (Errno::EBADF)

6. local variable and local variable in block behave differently

7. Local files don't load

8. FEATURE REQUEST: 'my' local variables

9. FEATURE REQUEST: 'my' local variables

10. 'local' to trap undeclared variables

11. Dialogs and side effects

12. Pattern for side effects

 

 
Powered by phpBB® Forum Software