This page is no longer maintained — Please continue to the home page at www.scala-lang.org

functional/immutable programming question

125 replies
Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Re: functional/immutable programming question
In many ways, actors encapsulate the original vision for Object-Oriented programming.  They're still very imperative in nature, based around pushing mutability into silos and then properly marshalling messages between them.
But Actors are just one paradigm for concurrency, you should also look at dataflow concurrency and FRP, not to mention forkJoin and the forthcoming parallel collections in Scala 2.9


On 16 November 2010 13:44, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Kevin (and others (?)),

> Wrong way round... you should define a part that uses side-effects ...

a question (also with the requirements of Andreas (concurrency) in mind
(in particular I was thinking of concurrency combined with state))

for those parts it is best to use actors for dealing with concurrency and state, right?
or is such an approach sometimes somewhat of an overkill?

Luc



On Tue, Nov 16, 2010 at 1:31 PM, Kevin Wright <kev [dot] lee [dot] wright [at] gmail [dot] com> wrote:
Wrong way round... you should define a part that uses side-effects, attempt to minimise/localise that, then parallelize the rest freely :)


On 16 November 2010 12:25, Daniel Gross <daniel [dot] gross [at] utoronto [dot] ca> wrote:
Hello Andreas,

I guess what you are writing is a bit surprising to me. I thought that
one of the key selling points for a functional language like Scala, is
the easy with which program execution can be distributed across
cores/processors.

It should be possible to clearly establish that a program, or at least,
a well designated portion of a program, can be parallelized without any
problems.

thanks,

Daniel

On Tue, 2010-11-16 at 12:47 +0100, Andreas Flierl wrote:
> Daniel Gross <daniel [dot] gross [at] utoronto [dot] ca> wrote:
> > Without yet really knowing Scala much (i just started to learn about the
> > language), perhaps it's worth defining three classes of programs a) pure
> > functional that are guaranteed to have no side-effects and b) mixed
> > programs, where side-effects are possible. And  b) could be further
> > classified into b.1) programs with well localized side effects and b.2)
> > hybrid programs.
>
> As far as I am concerned, all Scala programs fall under b as there is
> (currently) no way
> to guarantee purity in Scala (as far as I am aware).
>
> The key point here (for me) is in the "guarantee". The absence of
> unintended side effects (sounds like a bug to me) cannot be shown by
> testing. Testing can only show the presence of bugs. So we need
> something better. "Because the programmer says it is." does not qualify
> either. So it comes down to the compiler guaranteeing purity.
>
> > Perhaps this would imply defining different subsets of Scala and
> > libraries use.
> >
> > Any program of class a) would be guaranteed to run in a parallel
> > processing environment, while for b.1) a guarantee is contingent on
> > programmer properly dealing with the localized side effects. a program
> > of category b.2) has no guarantees and should be run in a non
> > parallelized environment.
>
> Side effects are not just about threads. Imagine a library that
> internally logs stuff to the disk. Your application uses this library
> while it writes its own data to the disk, knowing nothing about that
> side effect. The log file fills the disk -> ouch
> Of course this example may be rather constructed but you get the idea.
> :)
>
> Kind regards
> Andreas





--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda




--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination




--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Razvan Cojocaru 3
Joined: 2010-07-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

Sorry - not that I want to be called names like "language lawyer" :) but I
was trying to underline the choice of words: it's first about functions and
then "avoids state"... rather than "forbids state"...

So, the way I see it, no doubt "purity" allows some mathematical funk around
functions and figuring out correctness whatnot, but that's not what defines
"functional"...it just defines "purity"... which is obviously subject to
extremist thinking, factions and blog picketing bigots :)) I enjoyed that
part.

For me, "cross my heart and hope to die" combined with testing is good
enough to bless a library as "reasonably side effect free". Afterall, you
can hide readLn and printLn in a closet, library or monad, but they're still
there...

The real world has state and any program trying to model the real world will
have to stash some state somewhere... So, if you can pass functions around
and curry the suckers, then it's functional enough in my book. I even think
closures come extra...

Anyways, this is the view of the world coming from a very much imperative OO
background...and I think we again leave the specifics behind and go into
mythology here, thus have to stop.

cheers,
Razvan

-----Original Message-----
From: Andreas Flierl
Sent: Tuesday, November 16, 2010 9:03 AM
To: Razvan Cojocaru
Cc: scala-user [at] listes [dot] epfl [dot] ch
Subject: Re: [scala-user] Re: functional/immutable programming question

Razvan Cojocaru :
> Gents, again wikipedia to the rescue
(snip)

Thanks. :)

Already knowing wikipedia's definition, I mentioned the issue because
I've read these blog entries, which some of you may find interesting:

[1] http://www.drmaciver.com/2009/05/a-problem-of-language/
[2] http://www.codecommit.com/blog/scala/is-scala-not-functional-enough
[3] http://james-iry.blogspot.com/2009/05/erlang-is-not-functional.html
[4]
http://james-iry.blogspot.com/2010/03/robert-fischer-finally-admits-that...

Best regards
Andreas

Nick
Joined: 2010-10-22,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On 16/11/10 12:25, Daniel Gross wrote:
> I thought that one of the key selling points for a functional language like
> Scala, is the easy with which program execution can be distributed across
> cores/processors.

I'd like to mention an interesting point made by Clojure's author, Rich Hickey:
to paraphrase, (conventional) object orientation *encourages* mutable state,
which causes difficulties when used for parallel algorithms, because you have
lock and serialise access to all the shared state.

Does Scala have an answer to this point? Presumably it just aims to allow both
styles, without guaranteeing or mandating anything?

From: http://clojure.org/state

> OO is, among other things, an attempt to provide tools for modeling identity
> and state in programs (as well as associating behavior with state, and
> hierarchical classification, both ignored here). OO typically unifies
> identity and state, i.e. an object (identity) is a pointer to the memory that
> contains the value of its state. There is no way to obtain the state
> independent of the identity other than copying it. There is no way to observe
> a stable state (even to copy it) without blocking others from changing it.
> There is no way to associate the identity's state with a different value
> other than in-place memory mutation. In other words, typical OO has
> imperative programming baked into it! OO doesn't have to be this way, but,
> usually, it is (Java/C++/Python/Ruby etc).
>
> People accustomed to OO conceive of their programs as mutating the values of
> objects. They understand the true notion of a value, say, 42, as something
> that would never change, but usually don't extend that notion of value to
> their object's state. That is a failure of their programming language. These
> languages use the same constructs for modeling values as they do for
> identities, objects, and default to mutability, causing all but the most
> disciplined programmers to create many more identities than they should,
> creating identities out of things that should be values etc.

N

Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: Re: functional/immutable programming question

"Razvan Cojocaru" wrote:
(snip)
> it's first about functions and then "avoids state"... rather than "forbids state"...

Assuming wikipedia is always right and provides perfect (or undisputed)
definitions, this sounds reasonable to me.

(snip)
> For me, "cross my heart and hope to die" combined with testing is
> good enough to bless a library as "reasonably side effect free".

This is where we obviously disagree and why I brought up the (to me)
analog case of dynamic vs. static typing.

> Afterall, you can hide readLn and printLn in a closet, library or
> monad, but they're still there...
> The real world has state and any program trying to model the real
> world will have to stash some state somewhere...

Yes, preferably outside the language, allowing it to be pure. You could
do so many nice things with just that property. But again, we're leaving
Scala land here.

(snip)

Thanks for sharing your opinion.

Best regards
Andreas

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Re: functional/immutable programming question
Oh Scala absolutely encourages immutability.
vals, case classes, the default collection types, etc.

On 16 November 2010 15:09, Nick <oinksocket [at] letterboxes [dot] org> wrote:
On 16/11/10 12:25, Daniel Gross wrote:
> I thought that one of the key selling points for a functional language like
> Scala, is the easy with which program execution can be distributed across
> cores/processors.

I'd like to mention an interesting point made by Clojure's author, Rich Hickey:
to paraphrase, (conventional) object orientation *encourages* mutable state,
which causes difficulties when used for parallel algorithms, because you have
lock and serialise access to all the shared state.

Does Scala have an answer to this point?  Presumably it just aims to allow both
styles, without guaranteeing or mandating anything?

From: http://clojure.org/state

> OO is, among other things, an attempt to provide tools for modeling identity
> and state in programs (as well as associating behavior with state, and
> hierarchical classification, both ignored here). OO typically unifies
> identity and state, i.e. an object (identity) is a pointer to the memory that
> contains the value of its state. There is no way to obtain the state
> independent of the identity other than copying it. There is no way to observe
> a stable state (even to copy it) without blocking others from changing it.
> There is no way to associate the identity's state with a different value
> other than in-place memory mutation. In other words, typical OO has
> imperative programming baked into it! OO doesn't have to be this way, but,
> usually, it is (Java/C++/Python/Ruby etc).
>
> People accustomed to OO conceive of their programs as mutating the values of
> objects. They understand the true notion of a value, say, 42, as something
> that would never change, but usually don't extend that notion of value to
> their object's state. That is a failure of their programming language. These
> languages use the same constructs for modeling values as they do for
> identities, objects, and default to mutability, causing all but the most
> disciplined programmers to create many more identities than they should,
> creating identities out of things that should be values etc.

N



--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: Re: functional/immutable programming question

Nick wrote:
> Does Scala have an answer to this point?

As a side note, Akka provides agents[1] and STM[2] inspired by Clojure
and its view on state for Java and Scala.

[1] http://doc.akkasource.org/agents-scala
[2] http://doc.akkasource.org/stm-scala

Razvan Cojocaru 3
Joined: 2010-07-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

But, on the subject of good enough, I think the approach taken in scala,
having collections.immutable vs collections.mutable is great. Side effects
are not usually about changing some global state but changing local
variables, meaning generally collections.

In a class, there's case classes and vals, allowing me to express
immutability requirements but not precluding an imperative mind from using
the language...

the virtues of immutability were acknowledged early on in java as well, just
look at the early versions of the pet store, with the "read-only" model and
the writeable model, I even forgot the names they used for that "pattern"...

So, if you design your structures properly and stick to
collections.immutable, then do you really care if a library has internal
state, given that it doesn't mess up your structures?

I would like to have something like the IO or the STM type constructors to
mark/contain side-effects and state changes but my method's signature could
as well simply use List or immutable.List and that makes it side-effect free
from my point of view, since it can't change the List I pass in...

Ahh, it could return a mutable.ArrayList, masquerading as an immutable.List
and then change its contents on a different thread, behind my back...yeah,
that's also possible and I can see why you'd compare that to a pointer
running berserk and thus ask that pointers be forever banned and crap be
collected automatically...

Confident that the one true constant is change,
Razvan

P.S. should we forward this to the scala-debate as a proposal to have two
flavors of "def" one like "val" and one like "var" and have the compiler
enforce it like a checked exception, up the call stack?

-----Original Message-----
From: Andreas Flierl
Sent: Tuesday, November 16, 2010 10:14 AM
To: Razvan Cojocaru
Cc: scala-user [at] listes [dot] epfl [dot] ch
Subject: Re: [scala-user] Re: functional/immutable programming question

"Razvan Cojocaru" wrote:
(snip)
> it's first about functions and then "avoids state"... rather than "forbids
> state"...

Assuming wikipedia is always right and provides perfect (or undisputed)
definitions, this sounds reasonable to me.

(snip)
> For me, "cross my heart and hope to die" combined with testing is
> good enough to bless a library as "reasonably side effect free".

This is where we obviously disagree and why I brought up the (to me)
analog case of dynamic vs. static typing.

> Afterall, you can hide readLn and printLn in a closet, library or
> monad, but they're still there...
> The real world has state and any program trying to model the real
> world will have to stash some state somewhere...

Yes, preferably outside the language, allowing it to be pure. You could
do so many nice things with just that property. But again, we're leaving
Scala land here.

(snip)

Thanks for sharing your opinion.

Best regards
Andreas

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Re: functional/immutable programming question

P.S. should we forward this to the scala-debate as a proposal to have two flavors of "def" one like "val" and one like "var" and have the compiler enforce it like a checked exception, up the call stack?

A better solution would be to have the compiler automatically keep track of the "purity" of functions, so it's pure if it's defined in Scala and only works with immutable values and other pure functions (I guess a mechanism could also be offered to flag Java methods as pure)
We could then use "guard" notation methods/functions we want to ensure are pure and on parameters that should only accept pure functions, similar to the way that @tailrec is used to sanity-check what you think is going on.  That way, it wouldn't be necessary to go and annotate each and every "pure" function as such.
I propose the "pure" keyword for this role :)Failing that, we could always use @pure
--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On 16/11/10 19:46, Kevin Wright wrote:
> It's hard to get deep into FP *without* terms like monad, monoid,
> endofunctor, catamorphism, etc. being involved.
>
> Then again, it's even harder to find any reference to these terms that
> doesn't use Haskell as the language-de-jour for explaining them.
Bollocks! I've written every single of those in Scala at least once.

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On 16/11/10 23:37, Razvan Cojocaru wrote:
> So my attempt at explaining how monads help encapsulate side-effects failed miserably... The part with "monoids in the category of endofunctors" was a joke as was fondling elephants.
>
Perhaps, but I have seen a beginner have monads successfully explained
to them as monoids in the category of endofunctors while on IRC (which
is profound in itself). There were no elephants.

Chris Marshall
Joined: 2009-06-17,
User offline. Last seen 44 weeks 3 days ago.
RE: Re: functional/immutable programming question
And also fluffy, furry, banana and unicorn.

> Date: Wed, 17 Nov 2010 08:20:20 +1000
> From: tonymorris [at] gmail [dot] com
>
> > It's hard to get deep into FP *without* terms like monad, monoid,
> > endofunctor, catamorphism, etc. being involved.
> >
> > Then again, it's even harder to find any reference to these terms that
> > doesn't use Haskell as the language-de-jour for explaining them.
>> Bollocks! I've written every single of those in Scala at least once.
>  
> --
> Tony Morris

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Re: functional/immutable programming question

I never denied that you can use 'em in Scala, just stated that it's hard to find good tutorials for someone with absolutely no prior experience...

On 16 Nov 2010 22:20, "Tony Morris" <tonymorris [at] gmail [dot] com> wrote:
> On 16/11/10 19:46, Kevin Wright wrote:
>> It's hard to get deep into FP *without* terms like monad, monoid,
>> endofunctor, catamorphism, etc. being involved.
>>
>> Then again, it's even harder to find any reference to these terms that
>> doesn't use Haskell as the language-de-jour for explaining them.
> Bollocks! I've written every single of those in Scala at least once.
>
>
> --
> Tony Morris
> http://tmorris.net/
>
>
Naftoli Gugenheim
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question


On Thu, Nov 11, 2010 at 4:53 PM, Sciss <contact [at] sciss [dot] de> wrote:
i find it telling that terms such as "stateless" or "stateful" are used, where the state
 is exactly the frozen time, the moment inbetween change, where if you speak in
 terms of process, you would typically use the term "change"  and "transition" and
 inversely the "states" become the holes between transitions.


I think this perspective is a nice way of looking at it. The functional paradigm and the stateful paradigm are two halves of a whole; the question is which is implicit and which is explicit. In functional programming, you describe the transformations: how to get from point A to point B. That's what a function is. A way to get from the input values to the return type. You make these explicit, and then you run your program. What happens? The computer, a state simulator (byte mover), steps through your logic and applies it to the current state (RAM, video memory, IO...) In imperative, mutable-state programming, you deal with "what's the state right now" directly, and although you organize this code inside functions, your focus is on the "stateful" half of the equation, and the transitioning is more taken for granted. Does that make any sense?
Sciss
Joined: 2008-12-17,
User offline. Last seen 28 weeks 5 days ago.
Re: functional/immutable programming question

this is what i'd do in the stm:

def registerClient( c: Client )( implicit tx: Txn ) { clients.transform( _ + c )}

world.topology.registerClient( clnt )

versus

val world2 = world1.copy( topology = world1.topology.copy( clients = world1.territory.clients + clnt ))

which in my reading is bottom-up versus top-down, the former being way easier to oversee in this kind of scenario... basically any kind of scenario which is modules dynamically interconnected and no god object needing to have total knowledge of sub-parts. for instance, i still find MVC a great approach of OOP and this doesn't seem very suited for purely functional programming. but maybe i'm just not familiar with how i would do this other than path-copying which is prohibitive after you cross two or three layers.

best, -sciss-

Am 16.11.2010 um 23:42 schrieb Naftoli Gugenheim:

>
>
> On Thu, Nov 11, 2010 at 4:53 PM, Sciss wrote:
> i find it telling that terms such as "stateless" or "stateful" are used, where the state
> is exactly the frozen time, the moment inbetween change, where if you speak in
> terms of process, you would typically use the term "change" and "transition" and
> inversely the "states" become the holes between transitions.
>
>
> I think this perspective is a nice way of looking at it. The functional paradigm and the stateful paradigm are two halves of a whole; the question is which is implicit and which is explicit.
> In functional programming, you describe the transformations: how to get from point A to point B. That's what a function is. A way to get from the input values to the return type. You make these explicit, and then you run your program. What happens? The computer, a state simulator (byte mover), steps through your logic and applies it to the current state (RAM, video memory, IO...)
> In imperative, mutable-state programming, you deal with "what's the state right now" directly, and although you organize this code inside functions, your focus is on the "stateful" half of the equation, and the transitioning is more taken for granted.
> Does that make any sense?
>

Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

On Tue, Nov 16, 2010 at 4:02 PM, Sciss wrote:
> versus
> val world2 = world1.copy( topology = world1.topology.copy( clients = world1.territory.clients + clnt ))

would haskellian monad-related-do-notation help here?

Sciss
Joined: 2008-12-17,
User offline. Last seen 28 weeks 5 days ago.
Re: functional/immutable programming question

how would that look like? this kind of line would typically be executed by some interactive event coming e.g. from a GUI, a sensor, or a network client. so this world2 = is not your top-level main() but somewhere encoded in the reactions of your system.

Am 17.11.2010 um 00:15 schrieb Raoul Duke:

> On Tue, Nov 16, 2010 at 4:02 PM, Sciss wrote:
>> versus
>> val world2 = world1.copy( topology = world1.topology.copy( clients = world1.territory.clients + clnt ))
>
> would haskellian monad-related-do-notation help here?

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

On 17/11/10 10:15, Raoul Duke wrote:
> On Tue, Nov 16, 2010 at 4:02 PM, Sciss wrote:
>
>> versus
>> val world2 = world1.copy( topology = world1.topology.copy( clients = world1.territory.clients + clnt ))
>>
> would haskellian monad-related-do-notation help here?
>
I refer back to, and propose as an exercise, the following. The
haskell-monad-do-notation corresponds to Scala's for-comprehensions,
which you can certainly use on this structure (try it!):

case class State[S, A](f: S => (S, A)) {
// Exercise 1
def map[B](k: A => B): State[S, B] = error("todo")

// Exercise 2
def flatMap[B](k: A => State[S, B]): State[S, B] = error("todo")

def run(s: S) = f(s)._2

def exec(s: S) = f(s)._1

// more useful stuff
}

object State {
def unit[S, A](a: => A): State[S, A] = error("todo")
}

Razvan Cojocaru 3
Joined: 2010-07-28,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question
Yeah, makes sense to me. 
I have long held the belief that a workflow/activity diagram and a state diagram are two sides of same coin... 
Thanks,Razvan
On 2010-11-16, at 6:42 PM, Naftoli Gugenheim <naftoligug [at] gmail [dot] com> wrote:



On Thu, Nov 11, 2010 at 4:53 PM, Sciss <contact [at] sciss [dot] de (contact [at] sciss [dot] de" rel="nofollow">contact [at] sciss [dot] de)> wrote:
i find it telling that terms such as "stateless" or "stateful" are used, where the state
 is exactly the frozen time, the moment inbetween change, where if you speak in
 terms of process, you would typically use the term "change"  and "transition" and
 inversely the "states" become the holes between transitions.


I think this perspective is a nice way of looking at it. The functional paradigm and the stateful paradigm are two halves of a whole; the question is which is implicit and which is explicit. In functional programming, you describe the transformations: how to get from point A to point B. That's what a function is. A way to get from the input values to the return type. You make these explicit, and then you run your program. What happens? The computer, a state simulator (byte mover), steps through your logic and applies it to the current state (RAM, video memory, IO...) In imperative, mutable-state programming, you deal with "what's the state right now" directly, and although you organize this code inside functions, your focus is on the "stateful" half of the equation, and the transitioning is more taken for granted. Does that make any sense?
Vincent Marquez
Joined: 2010-07-08,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question
I really don't believe it does Scala any to promote its' 'functional/immutable' aspects as a concurrent/parallel silver bullet.  As my code has slowly migrated from 'java style' to a more functional, idiomatic 'scala style', I've appreciated the benefit of a functional style and immutability for readability and conciseness.  
However, due to the fact that there is no 'functional purity' (in the closest sense you can, lets be honest, not even haskell(io/STM) or clojure(stm) are 'pure'), you can't reason about how safe concurrent operations are.  The Actor model, while establishing a nice clear boundary between data in threads (or microthreads, implementation doesn't really matter) operating concurrently, doesn't prevent you from deadlocks or race conditions.
Now I'll venture into somewhat controversial territory. I'll make the claim that immutability and immutable data structures alone don't give any benefit to concurrent operations.  You still need a way to rectify multiple threads operating on what once was the same structure.  How do you merge the multiple heads of a linked list back into one?  This is handled in Clojure and Haskell with a form of STM. 
Unfortunately, that doesn't buy you much either. To steal from Cliff Click's argument, STM fails in the same way locks do: the challenge with both is at which granularity do you wrap your atomic (or lock) keyword?  You can enforce just as much safety with locks as STM by wrapping everything in a synchronized block (or having a global mutex), locking only gets hard when you need performance. If you aren’t fine grained enough, you have contention issues, too fine grained and you have race conditions. Same with STM in the sense that you wrap too much with your Atomic blocks, and suddenly you have live-locks/infinite retries…
All in all, I think it does a disservice to the community to spread the myth that immutability and/or functional purity is a concurrency silver bullet.  They are both fantastic features for building robust and readable software, but for other reasons.   We (as an entire community of software engineers) *still* have the concurrency dragon to slay.  
--Vincent




.  
On Tue, Nov 16, 2010 at 4:58 PM, Razvan Cojocaru <pub [at] razie [dot] com> wrote:
Yeah, makes sense to me. 
I have long held the belief that a workflow/activity diagram and a state diagram are two sides of same coin... 
Thanks,Razvan
On 2010-11-16, at 6:42 PM, Naftoli Gugenheim <naftoligug [at] gmail [dot] com> wrote:



On Thu, Nov 11, 2010 at 4:53 PM, Sciss <contact [at] sciss [dot] decontact [at] sciss [dot] de> wrote:
i find it telling that terms such as "stateless" or "stateful" are used, where the state
 is exactly the frozen time, the moment inbetween change, where if you speak in
 terms of process, you would typically use the term "change"  and "transition" and
 inversely the "states" become the holes between transitions.


I think this perspective is a nice way of looking at it. The functional paradigm and the stateful paradigm are two halves of a whole; the question is which is implicit and which is explicit. In functional programming, you describe the transformations: how to get from point A to point B. That's what a function is. A way to get from the input values to the return type. You make these explicit, and then you run your program. What happens? The computer, a state simulator (byte mover), steps through your logic and applies it to the current state (RAM, video memory, IO...) In imperative, mutable-state programming, you deal with "what's the state right now" directly, and although you organize this code inside functions, your focus is on the "stateful" half of the equation, and the transitioning is more taken for granted. Does that make any sense?

Detering Dirk
Joined: 2008-12-16,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

Tony Morris wrote:
>
> Bollocks! [...]
>

Impressing. For me as a non-native english speaker you even act as a living
synonym dictionary, teaching me always new words for the concept of
"nonsense" :-) .

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Re: functional/immutable programming question
For anyone not knowing the origin of all the elephant references, and the phrase "a monad is a monoid in the category of endofunctors"
Look no further:http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html
http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.htmlhttp://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html http://james-iry.blogspot.com/2007/11/monads-are-elephants-part-4.html
Thanks again James!


On 17 November 2010 09:26, Det2 <Dirk [dot] Detering [at] bitmarck [dot] de> wrote:


Tony Morris wrote:
>
> Bollocks! [...]
>

Impressing. For me as a non-native english speaker you even act as a living
synonym dictionary, teaching me always new words for the concept of
"nonsense" :-) .
--
View this message in context: http://scala-programming-language.1934581.n4.nabble.com/functional-immutable-programming-question-tp3037504p3046341.html
Sent from the Scala - User mailing list archive at Nabble.com.



--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: functional/immutable programming question

I refer back to, and propose as an exercise, the following. The
haskell-monad-do-notation corresponds to Scala's for-comprehensions,
which you can certainly use on this structure (try it!):

case class State[S, A](f: S => (S, A)) {
   // Exercise 1
   def map[B](k: A => B): State[S, B] = error("todo")

   // Exercise 2
   def flatMap[B](k: A => State[S, B]): State[S, B] = error("todo")

   def run(s: S) = f(s)._2

   def exec(s: S) = f(s)._1

   // more useful stuff
}

object State {
   def unit[S, A](a: => A): State[S, A] = error("todo")
}


All we need now is a follow-up email with the answers in place, and *an explanation as to why they're the correct answers*.
It's the explanation, one that doesn't presume Haskell exposure,  that's so hard to find online...  --
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 17/11/10 19:35, Kevin Wright wrote:
>
>
> I refer back to, and propose as an exercise, the following. The
> haskell-monad-do-notation corresponds to Scala's
> for-comprehensions, which you can certainly use on this structure
> (try it!):
>
> case class State[S, A](f: S => (S, A)) { // Exercise 1 def
> map[B](k: A => B): State[S, B] = error("todo")
>
> // Exercise 2 def flatMap[B](k: A => State[S, B]): State[S, B] =
> error("todo")
>
> def run(s: S) = f(s)._2
>
> def exec(s: S) = f(s)._1
>
> // more useful stuff }
>
> object State { def unit[S, A](a: => A): State[S, A] = error("todo")
> }
>
>
> All we need now is a follow-up email with the answers in place, and
> *an explanation as to why they're the correct answers*.
>
> It's the explanation, one that doesn't presume Haskell exposure,
> that's so hard to find online...
>
> -- Kevin Wright
>
> mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
> kev [dot] lee [dot] wright [at] gmail [dot] com (<mailto:kev [dot] lee [dot] wright [at] gmail [dot] com>) pulse / skype: kev.lee.wright
> twitter: @thecoda
>

If you can write the answers, such that the code compile0s
(type-checks) and satisfies the following four properties, then you
have the correct answers.

1) forall f a. unit(a) flatMap f === f(a)
2) forall s. s flatMap (unit(_)) === s
3) forall s f g. (s flatMap f) flatMap g === s flatMap (x => f(x)
flatMap g)
4) forall s f. s flatMap (x => unit(f(x)) === s map f

Haskell exposure is not going to help you either way.

Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: functional/immutable programming question

Hi Vincent,

Vincent Marquez wrote:
> I really don't believe it does Scala any to promote its'
> 'functional/immutable' aspects as a concurrent/parallel silver bullet.

(snip)

> All in all, I think it does a disservice to the community to spread
> the myth that immutability and/or functional purity is a concurrency
> silver bullet.

to be honest, I've read that claim nowhere. Noone ever spoke of the
silver bullet, as far as I am aware. I agree that it is no silver
bullet. What they say is that immutability (and functional purity) make
concurrency a lot easier. That coincides perfectly with my own
experience. I've written a couple of things over the years in imperative
style and years later in a functional style (whatever exactly that is).
My first attempts were rather impossible to transform into something
that used multiple processors and still had good throughput. With the
newer things it was e.g. enough to map tasks via
scala.actor.Futures.future and awaitAll (quasi map-reduce or fork-join)
because the tasks themselves had no side effects. That is, I could make
the parallel version by changing 2 lines of code...

> However, due to the fact that there is no 'functional purity' (in the
> closest sense you can, lets be honest, not even haskell(io/STM) or
> clojure(stm) are 'pure'), you can't reason about how safe concurrent
> operations are.  
Exactly my point of view. For now, we'll have to live with "good enough
is OK".

> The Actor model, while establishing a nice clear
> boundary between data in threads (or
> microthreads, implementation doesn't really matter) operating
> concurrently, doesn't prevent you from deadlocks or race conditions.
Exactly my thoughts. What I really like is akka's dataflow
concurrency[1]. It brings determinism to concurrency. When you run the
same code, it either always deadlocks or never. It is no silver bullet
either, but it helps me a lot to reason about things.

> and readable software, but for other reasons.   We (as an entire
> community of software engineers) *still* have the concurrency dragon
> to slay.  

Absolutely. But I find it incredibly easier to tackle with functional
tools and immutable/persistent data structures at my disposal.

Thanks for sharing your opinion.

Kind regards
Andreas

[1]
http://www.scalablesolutions.se/akka/api/0.10/akka-core/se/scalablesolutions/akka/dataflow/DataFlow$.html

P.S.
Sadly akka's dataflow feature is not really documented at the moment.
Best thing I found is the somewhat outdated summary at
https://github.com/jboner/scala-dataflow

P.P.S
There are probably papers about dataflow concurrency (I think the
concept is quite old), but I don't know them. :)

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Re: functional/immutable programming question
All,

> "a monad is a monoid in the category of endofunctors"

I have seen this statement several times already in emails to this group
(often as a kind of joke (to make programmers afraid of monads(?)))

I also looked at the origin in James blog posts:

Wadler tries to appease critics by explaining that
"a monad is a monoid in the category of endofunctors, what's the problem?"

clearly also also a joke

I just wanted to say that this statement is not true.

The composition of monads is not necessarily a monad.

Philip Wadler wrote a paper "Combining Monads" in 1992 (with David King)

One year later, 1993, I wrote a paper (with Mark P. Jones)
http://web.cecs.pdx.edu/~mpj/pubs/composing.html
showing a counter example

see section 6.4.2. for the following (somewhat contrived counter) example
where I show that (as far as monad laws are concerned)
composing with the List monad is problematic

? (prod . map (join . map prod)) [[[[[1],[3]]]],[[[[4]]],[[[2]]]]]
[[1, 4], [1, 2], [3, 4], [3, 2]]
? (join . map prod . prod) [[[[[1],[3]]]],[[[[4]]],[[[2]]]]]
[[1, 4], [3, 4], [1, 2], [3, 2]]

see http://www.cwru.edu/artsci/math/wells/pub/ttt.html (1983)
for the monad composition laws above

not that it all matters to much :-)


--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Stefan Langer
Joined: 2009-10-23,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

2010/11/17 Vincent Marquez :
> [...]  The Actor model, while establishing a nice clear boundary
> between data in threads (or microthreads, implementation doesn't really
> matter) operating concurrently, doesn't prevent you from deadlocks or race
> conditions.[...]
Actually I do not believe this to be true. The problem with deadlocks
and race conditions only occurs if you are sharing data between
threads. If you are having two distinct actors / processes and they
receive immutable data then you do not have a lock in anyway which
again means you cannot have a racing or deadlock situation.
Now the implementation in Scala makes this fuzzy as the actor
implementation allowes you to shares data under the hood. There is no
true isolation between data. Although you can implement it in forms of
immutable messages and asynchronouse message delivery.

Taking Erlang as an example the vm makes it quite hard (almost
impossible) to share data and you have to serialize messages between
processes. In this condition it is impossible to produce deadlock or
race conditions. (Except maybe if you pass a message and wait for a
return message but the receiver doesn't send you one. This is also a
deadlock situation but on a much higher abstraction layer and
indicates a semantical error in your program in my eyes. This is not
what I'm talking about when I refer to deadlocks in this thread)
The only thing that can occur is process starvation meaning you are
giving the system so much to do that it is not capable of creating
more processes. But this is a general problem and applies to non
concurrent programs as well (e.g. CPU Time, Memory, etc...).

My 2cts.
-Stefan

Roland Kuhn
Joined: 2008-12-26,
User offline. Last seen 3 years 14 weeks ago.
Re: functional/immutable programming question

Hi Stefan,

it is good that you acknowledge that not all problems are solved by the
actor pattern. However I disagree with your distinction: deadlocks and
race conditions may be shifted to a higher level of abstraction, but
they are real problems nevertheless. Limiting your definition of these
words in order to be able to say that some aspect of the problem is
solved only distracts from the fact that other aspects of the very same
problem remain valid. Even Erlang does not remove the necessity for
careful design and implementation.

(sorry for the rant, it's just that I think it very rarely is a good
idea to tell people that they're safe)

Regards,

Roland

Am 17.11.2010 15:06, schrieb Stefan Langer:
> 2010/11/17 Vincent Marquez:
>> [...] The Actor model, while establishing a nice clear boundary
>> between data in threads (or microthreads, implementation doesn't really
>> matter) operating concurrently, doesn't prevent you from deadlocks or race
>> conditions.[...]
> Actually I do not believe this to be true. The problem with deadlocks
> and race conditions only occurs if you are sharing data between
> threads. If you are having two distinct actors / processes and they
> receive immutable data then you do not have a lock in anyway which
> again means you cannot have a racing or deadlock situation.
> Now the implementation in Scala makes this fuzzy as the actor
> implementation allowes you to shares data under the hood. There is no
> true isolation between data. Although you can implement it in forms of
> immutable messages and asynchronouse message delivery.
>
> Taking Erlang as an example the vm makes it quite hard (almost
> impossible) to share data and you have to serialize messages between
> processes. In this condition it is impossible to produce deadlock or
> race conditions. (Except maybe if you pass a message and wait for a
> return message but the receiver doesn't send you one. This is also a
> deadlock situation but on a much higher abstraction layer and
> indicates a semantical error in your program in my eyes. This is not
> what I'm talking about when I refer to deadlocks in this thread)
> The only thing that can occur is process starvation meaning you are
> giving the system so much to do that it is not capable of creating
> more processes. But this is a general problem and applies to non
> concurrent programs as well (e.g. CPU Time, Memory, etc...).
>
> My 2cts.
> -Stefan

Stefan Langer
Joined: 2009-10-23,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

I'm actually not saying people are safe. But the Actor model does
solve the shared data and thread synchronisation problem.
It does not safe you from a communication error. The same could occur
if you do not have a concurrent problem and you are doing a loop
waiting for a condition to be true which never happens due to an erro,
this will leave you in an endless loop.
So waiting on a message and never receiving it is something totally
different from waiting on a lock to gain access to a resource which is
there but you can't get it cause somebody else is holding on to it.

-Stefan

2010/11/17 Roland Kuhn :
> Hi Stefan,
>
> it is good that you acknowledge that not all problems are solved by the
> actor pattern. However I disagree with your distinction: deadlocks and race
> conditions may be shifted to a higher level of abstraction, but they are
> real problems nevertheless. Limiting your definition of these words in order
> to be able to say that some aspect of the problem is solved only distracts
> from the fact that other aspects of the very same problem remain valid. Even
> Erlang does not remove the necessity for careful design and implementation.
>
> (sorry for the rant, it's just that I think it very rarely is a good idea to
> tell people that they're safe)
>
> Regards,
>
> Roland
>
> Am 17.11.2010 15:06, schrieb Stefan Langer:
>>
>> 2010/11/17 Vincent Marquez:
>>>
>>> [...]  The Actor model, while establishing a nice clear boundary
>>> between data in threads (or microthreads, implementation doesn't really
>>> matter) operating concurrently, doesn't prevent you from deadlocks or
>>> race
>>> conditions.[...]
>>
>> Actually I do not believe this to be true. The problem with deadlocks
>> and race conditions only occurs if you are sharing data between
>> threads. If you are having two distinct actors / processes and they
>> receive immutable data  then you do not have a lock in anyway which
>> again means you cannot have a racing or deadlock situation.
>> Now the implementation in Scala makes this fuzzy as the actor
>> implementation allowes you to shares data under the hood. There is no
>> true isolation between data. Although you can implement it in forms of
>> immutable messages and asynchronouse message delivery.
>>
>> Taking Erlang as an example the vm makes it quite hard (almost
>> impossible) to share data and you have to serialize messages between
>> processes. In this condition it is impossible to produce deadlock or
>> race conditions. (Except maybe if you pass a message and wait for a
>> return message but the receiver doesn't send you one. This is also a
>> deadlock situation but on a much higher abstraction layer and
>> indicates a semantical error in your program in my eyes. This is not
>> what I'm talking about when I refer to deadlocks in this thread)
>> The only thing that can occur is process starvation meaning you are
>> giving the system so much to do that it is not capable of creating
>> more processes. But this is a general problem and applies to non
>> concurrent programs as well (e.g. CPU Time, Memory, etc...).
>>
>> My 2cts.
>> -Stefan
>
>

Aydjen
Joined: 2009-08-21,
User offline. Last seen 1 year 28 weeks ago.
Re: functional/immutable programming question

Am Mittwoch, den 17.11.2010, 16:51 +0100 schrieb Stefan Langer
:
> So waiting on a message and never receiving it is something totally
> different from waiting on a lock to gain access to a resource which is
> there but you can't get it cause somebody else is holding on to it.

Please forgive me if I am being ignorant here, but I'd call both a
deadlock, just on different levels of abstraction.

Kind regards
Andreas

Erik Engbrecht
Joined: 2008-12-19,
User offline. Last seen 3 years 18 weeks ago.
Re: functional/immutable programming question
Agreed.  Pushing a problem up a level of abstraction doesn't mean you can declare it solved.


On Wed, Nov 17, 2010 at 10:56 AM, Andreas Flierl <andreas [at] flierl [dot] eu> wrote:

Am Mittwoch, den 17.11.2010, 16:51 +0100 schrieb Stefan Langer
<mailtolanger [at] googlemail [dot] com>:
> So waiting on a message and never receiving it is something totally
> different from waiting on a lock to gain access to a resource which is
> there but you can't get it cause somebody else is holding on to it.

Please forgive me if I am being ignorant here, but I'd call both a
deadlock, just on different levels of abstraction.

Kind regards
Andreas



--
http://erikengbrecht.blogspot.com/
Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: functional/immutable programming question

Agreed.  Pushing a problem up a level of abstraction doesn't mean you can declare it solved.
 Especially if the problem is "too much abstraction" :)
 --
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Stefan Langer
Joined: 2009-10-23,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

Granted it is not solved but it is definetly made more explicit.

2010/11/17 Erik Engbrecht :
> Agreed.  Pushing a problem up a level of abstraction doesn't mean you can
> declare it solved.
>
>
> On Wed, Nov 17, 2010 at 10:56 AM, Andreas Flierl wrote:
>>
>> Am Mittwoch, den 17.11.2010, 16:51 +0100 schrieb Stefan Langer
>> :
>> > So waiting on a message and never receiving it is something totally
>> > different from waiting on a lock to gain access to a resource which is
>> > there but you can't get it cause somebody else is holding on to it.
>>
>> Please forgive me if I am being ignorant here, but I'd call both a
>> deadlock, just on different levels of abstraction.
>>
>> Kind regards
>> Andreas
>
>
>
> --
> http://erikengbrecht.blogspot.com/
>

Stefan Langer
Joined: 2009-10-23,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

Why do you think that Actors are too much abstraction?. The isolation
they provide gives you a much cleaner boundary then actually having
direct interaction between data in my opinion. This is actually
something STM does as well. It gives you a clear boundary between your
data and their data.

I'm not saying that it makes it less complex but it makes it more
explicit at which points your data changes.

2010/11/17 Kevin Wright :
>
>> Agreed.  Pushing a problem up a level of abstraction doesn't mean you can
>> declare it solved.
>
>
> Especially if the problem is "too much abstraction" :)
>
> --
> Kevin Wright
>
> mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
> pulse / skype: kev.lee.wright
> twitter: @thecoda
>
>

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: functional/immutable programming question


Why do you think that Actors are too much abstraction?. 

I don't.  It was a reference to the semi-famous saying that:
"every problem in computer science can be solved with another layer of abstraction, except too much abstraction."

Wish I knew who first came up with that one, it sounds like something that Knuth would say.
--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Java Artisan
Joined: 2010-07-20,
User offline. Last seen 2 years 15 weeks ago.
Funtional programming reading

Hello,

Can somebody guide me to an accessible introduction in functional
programming ? Something a Scala newbie should have read at least ! :-)

Thanks !

Jan

grossd
Joined: 2010-11-15,
User offline. Last seen 1 year 49 weeks ago.
Re: Funtional programming reading

A while back I watched quite a few lectures on the introduction to
functional programming, by Biran Harvey at U of Berkley, that i though
was very good.

http://www.youtube.com/watch?v=zmYqShvVDh4

perhaps thats useful.

Daniel

On Wed, 2010-11-17 at 18:43 +0100, Jan Goyvaerts wrote:
> Hello,
>
> Can somebody guide me to an accessible introduction in functional
> programming ? Something a Scala newbie should have read at least ! :-)
>
> Thanks !
>
> Jan

Jason Zaugg
Joined: 2009-05-18,
User offline. Last seen 38 weeks 5 days ago.
Re: Funtional programming reading

I recommend Eric Meijer's series on functional programming, on Channel 9.

http://channel9.msdn.com/Shows/Going+Deep/Lecture-Series-Erik-Meijer-Fun...

-jason

On Wed, Nov 17, 2010 at 6:47 PM, Daniel Gross wrote:
> A while back I watched quite a few lectures on the introduction to
> functional programming, by Biran Harvey at U of Berkley, that i though
> was very good.
>
> http://www.youtube.com/watch?v=zmYqShvVDh4
>
> perhaps thats useful.
>
> Daniel
>
> On Wed, 2010-11-17 at 18:43 +0100, Jan Goyvaerts wrote:
>> Hello,
>>
>> Can somebody guide me to an accessible introduction in functional
>> programming ? Something a Scala newbie should have read at least ! :-)
>>
>> Thanks !
>>
>> Jan
>
>
>

Stefan W.
Joined: 2008-09-10,
User offline. Last seen 46 weeks 2 days ago.
Re: Re: functional/immutable programming question

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Razvan Cojocaru schrieb:

> The real world has state and any program trying to model the real world
> will have to stash some state somewhere...

The real world has cats, too. Does that mean, that every program that
models the real world has to stash some cats somewhere?

- --

Tschööö--->...Stefan
- ---------------------------
Don't visit my homepage at:
http://home.arcor-online.net/hirnstrom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkzkAYwACgkQQeATqGpDnRq16ACfTL22KqWQvuPCovGB5anTIRO5
9IwAoIf744aj/XorW2lN3FzdatnBKYz4
=AwvS
-----END PGP SIGNATURE-----

Graham Matthews
Joined: 2009-12-22,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question
Functional programming is not about stateless programming, it is about passing state *explicitly* (this is commonly referred to as "stateless", but that is a misnomer). Imperative programming passes state *implicitly* which is commonly referred to as "stateful", again a misnomer.
graham
On Nov 17, 2010, at 8:23 AM, Stefan Wagner wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Razvan Cojocaru schrieb:

The real world has state and any program trying to model the real world
will have to stash some state somewhere...

The real world has cats, too. Does that mean, that every program that
models the real world has to stash some cats somewhere?

- --

Tschööö--->...Stefan
- ---------------------------
Don't visit my homepage at:
http://home.arcor-online.net/hirnstrom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkzkAYwACgkQQeATqGpDnRq16ACfTL22KqWQvuPCovGB5anTIRO5
9IwAoIf744aj/XorW2lN3FzdatnBKYz4
=AwvS
-----END PGP SIGNATURE-----


Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On Wed, Nov 17, 2010 at 11:35 AM, Graham Matthews
wrote:
> Functional programming is not about stateless programming, it is about
> passing state *explicitly* (this is commonly referred to as "stateless", but
> that is a misnomer). Imperative programming passes state *implicitly* which
> is commonly referred to as "stateful", again a misnomer.

+1

tho

1) well, functional programing is perhaps really only about making
functions be "first-class". everything beyond that is maybe personal
choice, religion, favourite flavour.

2) well, to be furtherly pedantic: imperative programming can do
either whereas pure functional doesn't, so in some sense imperative is
the superset of functional. so imperative doesn't *always* pass state
implicitly. (and in reality most so-called functional programming
languages end up supporting mutation, and people end up using it, so
it is kinda rare to be purely functional.)

??

sincerely.

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 18/11/10 05:45, Raoul Duke wrote:
> On Wed, Nov 17, 2010 at 11:35 AM, Graham Matthews
> wrote:
>> Functional programming is not about stateless programming, it is
>> about passing state *explicitly* (this is commonly referred to as
>> "stateless", but that is a misnomer). Imperative programming
>> passes state *implicitly* which is commonly referred to as
>> "stateful", again a misnomer.
>
> +1
>
> tho
>
> 1) well, functional programing is perhaps really only about making
> functions be "first-class". everything beyond that is maybe
> personal choice, religion, favourite flavour.

Functional programming is programming with functions. This has nothing
to do with anything being "first-class."

>
> 2) well, to be furtherly pedantic: imperative programming can do
> either whereas pure functional doesn't, so in some sense imperative
> is the superset of functional. so imperative doesn't *always* pass
> state implicitly. (and in reality most so-called functional
> programming languages end up supporting mutation, and people end up
> using it, so it is kinda rare to be purely functional.)

This is very untrue, misleading, common and (I have found) difficult
to "unteach".

There is no superset. A pure functional language like Haskell does
imperative programming *a whole lot better than most imperative
languages*. In other words, there is an embedded "DSL" (if you'll
allow the degenerate jargon) in Haskell that is an imperative
language. Let me repeat that -- Haskell, a pure functional language,
has an imperative language embedded within it.

This imperative programming language just happens to *kick serious
arse over most other imperative languages*. It allows first-class IO
action values. It has type inference and a clean unintrusive syntax
for imperative programming. Try doing that Java with your redundant
types, parentheses and semi-colons. -- no actually don't (I've seen
first-hand what happens when JSR teams try something useful).

By this argument, you could successfully argue that pure functional
programming is a superset of imperative programming. This is also
untrue (and obviously, both cannot be true). I'll leave the flawed
logic as a somewhat perverted exercise and expel no more breath on it.

The important question is not "which dogma" you decide to associate
with, but understanding the practical implications of the assessment.
You don't "decide to use or not to use imperative programming." Which
solution, regardless of our projections, is most practical in the
scenario? Are you using Java? Python? Then good luck getting any
compositionality out of your programs -- concede the point as you
accept those implications (or don't to some extent -> Functional
Java). It's not a dichotomy; it's a continuum and there are
implications to be accepted all the way along it. The question is
complex to answer and too often I see a misidentification of the
essential attributes that should contribute to making that decision.
In this fallacious case, it's easy -- any conclusions are at best,
coincidentally true.

Let's not harp on.

I'm quite sure I have posted the State data structure and the
associated monad several times now. I'm not sure why it's not sinking
in (perhaps it was ignored). Did you see the S type variable? Imagine
now that S=Universe. There you have it -- a pure functional
programming construct embedded in an imperative language such as Scala.

For example, if we suppose:

* A wrapper on State[Universe, _]:
type IO[A] = State[Universe, A]

* a function readFile which takes a FileName and normally returns a
type FileContents instead is denoted:
readFile: FileName => IO[FileContents]

* a function writeFile which takes a FileName, FileContents and
returns Unit:
writeFile: FileName => FileContents => IO[Unit]

then look at this program:

val x: IO[Unit] =
for(apples <- readFile("apples.txt")
bananas <- readFile("bananas.txt"))
yield writeFile("applesandbananas.txt")(apples ++ bananas)

An imperative-looking program without any side-effects!

Hope this helps.

PS: I note an earlier statement that "the real world has state." This
fallacy is of a similar ilk and ironically, departs from anything
resembling the real world. A meta-fallacy about the real world is
something I encounter all too often in programming to such an extent
that I now find it quite boring.

>
> ??
>
> sincerely.

Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

hi Tony,

thanks for being a foil here, it is helpful.

On Wed, Nov 17, 2010 at 1:14 PM, Tony Morris wrote:
> Functional programming is programming with functions. This has nothing
> to do with anything being "first-class."

thanks, my connotation vs. denotation, point taken.

>> 2) well, to be furtherly pedantic: imperative programming can do
>> either whereas pure functional doesn't, so in some sense imperative
>> is the superset of functional. so imperative doesn't *always* pass
>> state implicitly. (and in reality most so-called functional
>> programming languages end up supporting mutation, and people end up
>> using it, so it is kinda rare to be purely functional.)
>
> This is very untrue, misleading, common and (I have found) difficult
> to "unteach".

i believe i see what you are getting at. but i feel that it isn't
exactly about what i was trying to say:

1) somebody said what i read as 'imperative implicitly changes state
where as functional explicitly has to thread it'.

2) i tried to say that you can eschew mutation in an imperative
language and return things, just like you'd have to do in a functional
language.

3) further, a pure functional language doesn't let you do mutation;
you can only return things.

4) therefore for the question of how the state changes, the options
you have imperatively are a superset of those you have functionally.

5) there is no #5.

i believe i understand that one can make fp look like imp via do
notation, but that is sugar, not side-band mutation; you don't have to
worry about locking stuff for example. further, i agree that one can
embed fp inside imp, but that doesn't seem to me to argue that fp is
the superset.

sincerely, and hoping to still learn further.

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: Re: functional/immutable programming question
A few minor remarks Tony,

let me first say that, deep in my heart, I am a pure functional programmer

we can, of course, have endless discussions about vaguely defined vocabulary
and sentences produced with it, and, I have to confess, I'm also not fully defining
my vocabulary and the sentences that I produce with it

> Functional programming is programming with functions. This has nothing
> to do with anything being "first-class."

maybe, in the sense that functions are values, the are "first class" in, afaik,
all mainstream languages that, by most programmers, are called functional
languages

as far as Haskell is all about programming with functions, it certainly benefits
from 'this functions being "first class" aspect' [ higher order functions, ... ]

> A pure functional language like Haskell does
> imperative programming *a whole lot better than most imperative
> languages*. In other words, there is an embedded "DSL" in Haskell
> that is an imperative language.

by the way, now you suddenly talk about pure functional languages, but,
aside of that, what exactly do you mean by imperative,

I think you refer to Haskell's monad based do syntax (similar
to Scala's for loop syntax), but, if you write something like

tick :: State Int Int
tick = do n <- get
put (n+1)
return n

this code may look imperative (especially because of the do keyword),
but, behind the scenes it does not do the same imperative thing as as, say,
an assignment in Java (in Haskell everything is final)

... and this discussion can go on and on ...


Luc


Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question
On 18/11/10 07:49, Luc Duponcheel wrote:
paxft [at] mail [dot] gmail [dot] com" type="cite">A few minor remarks Tony,

let me first say that, deep in my heart, I am a pure functional programmer

we can, of course, have endless discussions about vaguely defined vocabulary
and sentences produced with it, and, I have to confess, I'm also not fully defining
my vocabulary and the sentences that I produce with it

> Functional programming is programming with functions. This has nothing
> to do with anything being "first-class."

maybe, in the sense that functions are values, the are "first class" in, afaik,
all mainstream languages that, by most programmers, are called functional
languages

as far as Haskell is all about programming with functions, it certainly benefits
from 'this functions being "first class" aspect' [ higher order functions, ... ]

> A pure functional language like Haskell does
> imperative programming *a whole lot better than most imperative
> languages*. In other words, there is an embedded "DSL" in Haskell
> that is an imperative language.

by the way, now you suddenly talk about pure functional languages, but,
aside of that, what exactly do you mean by imperative,

I think you refer to Haskell's monad based do syntax (similar
to Scala's for loop syntax), but, if you write something like

tick :: State Int Int
tick = do n <- get
          put (n+1)
          return n

this code may look imperative (especially because of the do keyword),
but, behind the scenes it does not do the same imperative thing as as, say,
an assignment in Java (in Haskell everything is final)

... and this discussion can go on and on ...

Hi Luc,
I believe you are restating my point, but a little differently and perhaps even more succinctly for some. Specifically, it raises the question, "just what is imperative programming?" While important to some, I personally find it an uninteresting question and prefer to restate the question to provoke an examination of the practical benefits. I'm hoping to appease the audience for which this is an important question, while alluding to the practical implications as you have done in your "imperative looking" example.

I wish to emphasise that "imperative programming is a superset of functional programming" is not only a fallacy, but a very destructive one in that it can impair potential for understanding.


-- 
Tony Morris
http://tmorris.net/

Raoul Duke
Joined: 2009-01-05,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On Wed, Nov 17, 2010 at 2:39 PM, Tony Morris wrote:
> even more succinctly for some. Specifically, it raises the question, "just
> what is imperative programming?" While important to some, I personally find
> it an uninteresting question and prefer to restate the question to provoke
> an examination of the practical benefits. I'm hoping to appease the audience

it sounds to me like you advocate denotations of functional, but use
connotations of imperative.

> I wish to emphasise that "imperative programming is a superset of functional
> programming" is not only a fallacy, but a very destructive one in that
> it can impair potential for understanding.

http://lambda-the-ultimate.org/node/3465

sincerely.

Graham Matthews
Joined: 2009-12-22,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question
On Nov 17, 2010, at 2:39 PM, Tony Morris wrote:
Hi Luc,
I believe you are restating my point, but a little differently and perhaps even more succinctly for some. Specifically, it raises the question, "just what is imperative programming?" While important to some, I personally find it an uninteresting question and prefer to restate the question to provoke an examination of the practical benefits. I'm hoping to appease the audience for which this is an important question, while alluding to the practical implications as you have done in your "imperative looking" example.


Ok so I would turn it around.
A functional program language is one in which *all* functions are *guaranteed* to be referentially transparent (RT) -- so 
for *all* functions, f, if x = y then f(x) = f(y)
Some people call this programming with "mathematical" functions.
An imperative programming language is one which doesn't make such a guarantee.
If you wondering how I/O can possibly be referentially transparent, there are two standard approaches.
First the Clean (the programming language) approach :-
a) I/O functions take a "World" as an argument, and return a new "World" as a result. b) the "World" type is a uniqueness type, guaranteeing the world gets single threaded, and that functions cannot access intermediate "world" results (hence the condition part of RT is trivially satisfied since two worlds are never equal).
Second the Haskell approach :-
a) Haskell functions don't do I/O, they return actions that when run, do do I/O.b) the Haskell I/O monad type is abstract -- functions taking I/O types cannot access any of the intermediate I/O states (again RT is trivially satisfied).
graham
Jesper Nordenberg
Joined: 2008-12-27,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

Graham Matthews skrev 2010-11-17 23:58:
> A functional program language is one in which *all* functions are
> *guaranteed* to be referentially transparent (RT) -- so

Uhm, this definition would exclude a lot of programming languages
normally considered functional, for example ML, OCaml, F#, Lisp etc.

/Jesper Nordenberg

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question
On 18/11/10 08:58, Graham Matthews wrote:
1AE9A5A2-B61C-4D3A-9774-9D8E29F2D238 [at] orangedogconsulting [dot] com" type="cite"> On Nov 17, 2010, at 2:39 PM, Tony Morris wrote:
Hi Luc,
I believe you are restating my point, but a little differently and perhaps even more succinctly for some. Specifically, it raises the question, "just what is imperative programming?" While important to some, I personally find it an uninteresting question and prefer to restate the question to provoke an examination of the practical benefits. I'm hoping to appease the audience for which this is an important question, while alluding to the practical implications as you have done in your "imperative looking" example.


Ok so I would turn it around.
A functional program language is one in which *all* functions are *guaranteed* to be referentially transparent (RT) -- so 
for *all* functions, f, if x = y then f(x) = f(y)
Some people call this programming with "mathematical" functions.
An imperative programming language is one which doesn't make such a guarantee.
If you wondering how I/O can possibly be referentially transparent, there are two standard approaches.
First the Clean (the programming language) approach :-
a) I/O functions take a "World" as an argument, and return a new "World" as a result.  b) the "World" type is a uniqueness type, guaranteeing the world gets single threaded, and that functions cannot access intermediate "world" results (hence the condition part of RT is trivially satisfied since two worlds are never equal).
Second the Haskell approach :-
a) Haskell functions don't do I/O, they return actions that when run, do do I/O. b) the Haskell I/O monad type is abstract -- functions taking I/O types cannot access any of the intermediate I/O states (again RT is trivially satisfied).
graham
There is also the approach of Disciple (DDC).

-- 
Tony Morris
http://tmorris.net/

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: functional/immutable programming question

On 18/11/10 08:56, Raoul Duke wrote:
> On Wed, Nov 17, 2010 at 2:39 PM, Tony Morris wrote:
>
>> even more succinctly for some. Specifically, it raises the question, "just
>> what is imperative programming?" While important to some, I personally find
>> it an uninteresting question and prefer to restate the question to provoke
>> an examination of the practical benefits. I'm hoping to appease the audience
>>
> it sounds to me like you advocate denotations of functional, but use
> connotations of imperative.
>
I simply advocate exploring interesting questions and I prefer not to
labour boring questions. I'm not sure how to make this clearer.

Jesper Nordenberg
Joined: 2008-12-27,
User offline. Last seen 42 years 45 weeks ago.
Re: functional/immutable programming question

Luc Duponcheel skrev 2010-11-17 22:49:
> by the way, now you suddenly talk about /pure/ functional languages, but,
> aside of that, what exactly do you mean by /imperative/,

Wouldn't it be reasonable to think of "imperative" as a sequence of
steps performed to produce a result? The difference is that in Haskell
this sequencing is made explicit in the type system through the use of
monads, but in most commonly used programming languages it's not
reflected in the types, but instead built into the language as statements.

/Jesper Nordenberg

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland