wrapping mind around functional programming

On Tue, Jul 14, 2009 at 4:59 PM, Josh Stratton wrote:
> When developing a large program with data structures in data
> structures, does using a functional approach in scala slow performance
> for really large data structures?
>
> If class A holds a bunch of class Bs, which holds a bunch of class Cs
> and they're all immutable, does changing C require A to be rebuilt?
> Is this detrimental if A is up to 100 MBs large and is being down a a
> hundred times a second?  Like if a GUI slider is quickly changing the
> value of C's members?  Or is object copying usually negligible in
> terms of performance impact?  Does Scala have any type of way to
> reduce these kind of problems?
>
> Josh
>

It depends on the object graph and on the changes you are making.
But, if, for instance you are creating a new A and you are only
removing or adding a C to one of the B's then you can generally use
some combination of filtering for lazily removing

and mapping
and concatenation

to lazily add items just to the field containing your Cs and otherwise
copying the references for the other fields (no need to do a deep
copy, since they're immutable objects).

Rich

There are lots of smart ways that functional languages gain substantial efficiency with their data
structures, and even more smart ways that the JVM optimizes that kind of memory behavior. In
general, it is safe to assume that "these kind of problems" aren't a problem, and it's safe to move
forward without the FUD.

~~ Robert.

Josh Stratton wrote:
> When developing a large program with data structures in data
> structures, does using a functional approach in scala slow performance
> for really large data structures?
>
> If class A holds a bunch of class Bs, which holds a bunch of class Cs
> and they're all immutable, does changing C require A to be rebuilt?
> Is this detrimental if A is up to 100 MBs large and is being down a a
> hundred times a second? Like if a GUI slider is quickly changing the
> value of C's members? Or is object copying usually negligible in
> terms of performance impact? Does Scala have any type of way to
> reduce these kind of problems?
>
> Josh
>

That's probably where zippers come handy. 

2009/7/14 Josh Stratton <strattonbrazil@gmail.com>

When developing a large program with data structures in data
structures, does using a functional approach in scala slow performance
for really large data structures?

If class A holds a bunch of class Bs, which holds a bunch of class Cs
and they're all immutable, does changing C require A to be rebuilt?
Is this detrimental if A is up to 100 MBs large and is being down a a
hundred times a second?  Like if a GUI slider is quickly changing the
value of C's members?  Or is object copying usually negligible in
terms of performance impact?  Does Scala have any type of way to
reduce these kind of problems?

Josh

--
Thanks,
-Vlad

On Tuesday July 14 2009, Vlad Patryshev wrote:
> That's probably where zippers come handy.

And for a certain class of problems and representation schemes,
strategy-based term rewriting as pioneered by Stratego/XT [1] and
implemented in Scala by Kiama [2] is a tremendous advantage. I did
modify it to minimize the creation of new instances when sub-term
transformations don't alter the actual values returned and to operate
on non-case classes (actually, in stock form it works on any Product
sub-class, not just case classes).

[1]
[2]

Randall Schulz

> 2009/7/14 Josh Stratton
>
> > When developing a large program with data structures in data
> > structures, does using a functional approach in scala slow
> > performance for really large data structures?
> >
> > If class A holds a bunch of class Bs, which holds a bunch of class
> > Cs and they're all immutable, does changing C require A to be
> > rebuilt? Is this detrimental if A is up to 100 MBs large and is
> > being down a a hundred times a second? Like if a GUI slider is
> > quickly changing the value of C's members? Or is object copying
> > usually negligible in terms of performance impact? Does Scala have
> > any type of way to reduce these kind of problems?
> >
> > Josh

Short answer, it depends.
You can certainly have efficient data structures for functional manipulation. For instance, Scala's List is very efficient for that. For example, "head", "tail", and "::" are all constant-time. Now, "::" is constant time because many lists can point to the same tail, and that is possible because the List is not doubly-linked, so a "tail" doesn't know it's "head". And, by the same token, a "head :: tail" doesn't know if it isn't someone else's tail.
A functional Map can work by having "layers". If you add or change a key/value, you add a layer which is consulted first, with a reference to the structure it originated from. So even if a different key/value is found on lower layers, what is returned is the one on the higher layer.
There is lots of research into this kind of thing, to make these structures efficient. So it's possible, but you'd better either research about it, or use something that is ready.
Another way you can gain performance is through projections and lazy evaluation. Basically, when you use a projection you store the functions passed to map/filter/flatMap, instead of applying them to produce a new structure. This is particularly effective when you know you won't need all of the final result -- for instance, if you will only want the first element in the collection with a certain property (or up to that element).
As for lazy evaluation, it simply postpones the computation of some data to the time it is actually needed. Again, you save when you know not all of the data will be actually needed.
Now, for the GUI slider, in particular, it seems a projection is more appropriate. You don't actually "copy" the data structure, you just "view" it through a filter that makes it seems like what you want. In fact, on Scala 2.8 "projection" has been replaced with "view".

On Tue, Jul 14, 2009 at 8:59 PM, Josh Stratton <strattonbrazil@gmail.com> wrote:

When developing a large program with data structures in data
structures, does using a functional approach in scala slow performance
for really large data structures?

If class A holds a bunch of class Bs, which holds a bunch of class Cs
and they're all immutable, does changing C require A to be rebuilt?
Is this detrimental if A is up to 100 MBs large and is being down a a
hundred times a second?  Like if a GUI slider is quickly changing the
value of C's members?  Or is object copying usually negligible in
terms of performance impact?  Does Scala have any type of way to
reduce these kind of problems?

Josh

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

On Wed, Jul 15, 2009 at 9:59 AM, Josh Stratton wrote:
> When developing a large program with data structures in data
> structures, does using a functional approach in scala slow performance
> for really large data structures?

Its a worthwhile question.

Intuitively, it seems the limiting lower bound on the amount of data
that must be copied on update is log(N) of total data N. This is
assuming you use a tree or similar, where only the updated branch,
running back to the root, is copied. Other structures, especially
heavily interlinked one, will require much more than log(N).

If you look at the way functional programs structure data, its
typically using fine-grained, incrementally update-able structures
without back-refs (trees, singly linked lists, in contrast to arrays)
that can re-use part of their previous structure on copy.

Its sufficiently troubling to some people in the FP community that
projects like DDC, a Haskell dialect with mutable data & an effect
system, have been developed [http://www.haskell.org/haskellwiki/DDC].

>
> If class A holds a bunch of class Bs, which holds a bunch of class Cs
> and they're all immutable, does changing C require A to be rebuilt?

Yes, if you need to see A again with the change in C, you'll need to
copy it + everything in between.

> Is this detrimental if A is up to 100 MBs large and is being down a a
> hundred times a second?  Like if a GUI slider is quickly changing the
> value of C's members?  Or is object copying usually negligible in
> terms of performance impact?

Probably less than traditionally imagined. AFAIK the JVM's generation
GC in the young generation does work proportional to the quantity of
surviving live data, so short lived objects are cheap to cleanup.

Does Scala have any type of way to
> reduce these kind of problems?

- Selective use of mutable structures. (Note also: if you need to
communicate with the "outside world" (even other threads), some use of
mutable state is inevitable.)

- Zippers ("subjective" data structures), as has been mentioned

-Ben

If you're interested in further reading on the subject, I can't recommend [1] enough. It gives a through treatment of a wide variety of persistent immutable data structures, many of them implemented using laziness. The code is in ML (with Haskell version in an appendix), but all implementations are discussed thoroughly and in depth; it should be fairly easy to follow the code even with little ML/Haskell experience.

- Colin

[1] Purely Functional Data Structures. Okasaki, Chris. 1998 Cambridge University Press

On Wednesday July 15 2009, Colin Bullock wrote:
> If you're interested in further reading on the subject, I can't
> recommend [1] enough. It gives a through treatment of a wide variety
> of persistent immutable data structures, ...

Every time this recommendation comes up, I check the prices
on this book and decide not to purchase it.

Does it cover concepts that one might apply outside of writing
collections classes or other code that's usually found in libraries
already?

> - Colin
>
> [1] Purely Functional Data Structures. Okasaki, Chris. 1998 Cambridge
> University Press

Randall Schulz

Randall R Schulz wrote:
> Every time this recommendation comes up, I check the prices
> on this book and decide not to purchase it.
>
Your local university library probably has it. And that's really the best way to acquire it: it's
like Knuth, in that you hit places where the book is invaluable, but unless you're deep into the
bowels of a standard library, those places happen only on rare occasion.

> Does it cover concepts that one might apply outside of writing
> collections classes or other code that's usually found in libraries
> already?
>
Having read the book only after working in FP languages for a while, I found the value of the book
is less in the data structures themselves and more in the approach and exploration of how to think
and code in a functional way. Even with a fair amount of experience, Okasaki showed me some
patterns and approaches that I hadn't encountered/thought of before.

~~ Robert Fischer, Smokejumper IT Consulting.
Enfranchised Mind Blog http://EnfranchisedMind.com/blog

Check out my book, "Grails Persistence with GORM and GSQL"!
http://www.smokejumperit.com/redirect.html

Okasaki PhD thesis of the same title is available online: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

It's probably not a perfect substitute but it is readily available.

On Wed, Jul 15, 2009 at 9:52 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Wednesday July 15 2009, Colin Bullock wrote:
> If you're interested in further reading on the subject, I can't
> recommend [1] enough. It gives a through treatment of a wide variety
> of persistent immutable data structures, ...

Every time this recommendation comes up, I check the prices
on this book and decide not to purchase it.

Does it cover concepts that one might apply outside of writing
collections classes or other code that's usually found in libraries
already?


> - Colin
>
> [1] Purely Functional Data Structures. Okasaki, Chris. 1998 Cambridge
> University Press


Randall Schulz

--
http://erikengbrecht.blogspot.com/

On Wednesday July 15 2009, Robert Fischer wrote:
> Randall R Schulz wrote:
> > Every time this recommendation comes up, I check the prices
> > on this book and decide not to purchase it.
>
> Your local university library probably has it. And that's really the
> best way to acquire it: it's like Knuth, in that you hit places where
> the book is invaluable, but unless you're deep into the bowels of a
> standard library, those places happen only on rare occasion.

Given that for me the "local university library" is Stanford, that's
almost certainly true. (As far as I can tell, they get every single
volume of the LNCS and LNAI series!) I can even check things out of San
Jose State and they might have it, too, though they're nowhere near as
convenient to get to.

> > Does it cover concepts that one might apply outside of writing
> > collections classes or other code that's usually found in libraries
> > already?
>
> Having read the book only after working in FP languages for a while,
> I found the value of the book is less in the data structures
> themselves and more in the approach and exploration of how to think
> and code in a functional way. Even with a fair amount of experience,
> Okasaki showed me some patterns and approaches that I hadn't
> encountered/thought of before.

Thanks. I figure I'm maybe about a quarter of the way to really thinking
in a FP way at this point, so that's probably very worthwhile. For
whatever it might mean, I still routinely reach for mutable sets and
maps for transient calculations inside of my classes but mostly write
immutable types (and occassionally a mutable + immutable pair).

> ~~ Robert Fischer

Randall Schulz

> Okasaki PhD thesis of the same title is available online:
> http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
>
> It's probably not a perfect substitute but it is readily available.

Great, I'll start reading that.

So on the subject of appropriate times for OO and functional
paradigms, would writing a image manipulation program like gimp, for
example, be a poor choice for functional languages since the one huge
data array is constantly changing? Or since most GUI APIs are so
heavily dependent on state?

Looking over various types of applications, it seems that functional
languages fit nicely into any particular situation be it a web server
or ssh daemon. But does anyone consider certain types of programs
such as those involving complex GUIs a poor choice for functional
languages? I've done some reading on Reactive Functional Programming,
but it seems very abstract (possibly just because relatively few
people have done it).

Reading papers like Okasaki's, where he comments,

"Although some data structures
designed for imperative languages such as C can be quite easily adapted to a
functional setting, most cannot, usually because they depend in
crucial ways on assignments,
which are disallowed, or at least discouraged, in functional languages..."

Is designing a more elegant data structure than an OO paradigm a
significant bottleneck in functional programming to get the touted
benefits?

Josh

I agree to no such thing! :-)   Middle-end and high-end image manipulation programs often keep copies of original bitmaps, so that you manipulate the filters and transformations being applied -- change order, change parameters. The displayed image is a "preview" of the final result, but you are always working with the original bitmap. Of course, you do not reapply transformations that were not changed.   Most OO GUIs are surely heavily dependent on state. Of course, they are OO! Functional GUIs exists, though, and they are superior both in correctness -- as they are declarative in nature -- and in scalability through concurrency.
Functional Reactive Programming was not done "by a few people". Lisp Cells is widely succesful in the Lisp community, for instance. Of course, it's not common in the OO community -- it's functional!   And, no, I don't see any bottleneck with regard to designing functional data structures. Most code doesn't use anything more complex than collections, and you don't have to design those data structures.   Dealing with inheritance -- or not having it -- that is a drawback when adopting functional programming. And Scala's ability to deal with that is one of it's strongest points.
On Wed, Jul 15, 2009 at 1:34 PM, Josh Stratton <strattonbrazil@gmail.com> wrote:

> Okasaki PhD thesis of the same title is available online:
> http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
>
> It's probably not a perfect substitute but it is readily available.

Great, I'll start reading that.

So on the subject of appropriate times for OO and functional
paradigms, would writing a image manipulation program like gimp, for
example, be a poor choice for functional languages since the one huge
data array is constantly changing?  Or since most GUI APIs are so
heavily dependent on state?

Looking over various types of applications, it seems that functional
languages fit nicely into any particular situation be it a web server
or ssh daemon.  But does anyone consider certain types of programs
such as those involving complex GUIs a poor choice for functional
languages?  I've done some reading on Reactive Functional Programming,
but it seems very abstract (possibly just because relatively few
people have done it).

Reading papers like Okasaki's, where he comments,

"Although some data structures
designed for imperative languages such as C can be quite easily adapted to a
functional setting, most cannot, usually because they depend in
crucial ways on assignments,
which are disallowed, or at least discouraged, in functional languages..."

Is designing a more elegant data structure than an OO paradigm a
significant bottleneck in functional programming to get the touted
benefits?

Josh

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

> So on the subject of appropriate times for OO and functional
> paradigms, would writing a image manipulation program like gimp, for
> example, be a poor choice for functional languages since the one huge
> data array is constantly changing? Or since most GUI APIs are so
> heavily dependent on state?

If that's how the Gimp works, could you explain how undo is implemented?

> Most OO GUIs are surely heavily dependent on state. Of course, they are OO!
> Functional GUIs exists, though, and they are superior both in correctness --
> as they are declarative in nature -- and in scalability through concurrency.
> Functional Reactive Programming was not done "by a few people". Lisp Cells
> is widely succesful in the Lisp community, for instance. Of course, it's not
> common in the OO community -- it's functional!

Well, I guess "by a few people" is all relative, but if it's widely
successful in the Lisp community, would that still be a few people in
the 2000s? I've seen a handful of articles on the web that mention
functional programming losing community with the rise of OO, but also
from the rise of GUIs themselves. Are they just being naive and
functional programming was totally jipped because its GUIs were really
that much better? In "Lightweight GUIs for Functional Programming" by
Vullinghs et al, the first line says "Everybody wants to use graphical
user interfaces. And everybody wants to use functional programming
languages. Unfortunately, these concepts are hard to combine." I'm
not saying any of these statements are necessarily true, but it shows
I'm not the only one who views GUIs as heavily state based. Even
people on this mailing list have said as much. Do you consider
functional GUIs easier to develop as well?

Anyway, I guess I'll just have to dive into Lisp Cells when I feel
like seeing how GUIs in functional programs should work.

Thanks Daniel.

Josh

On Thu, Jul 16, 2009 at 2:34 AM, Josh Stratton wrote:
> So on the subject of appropriate times for OO and functional
> paradigms, would writing a image manipulation program like gimp, for
> example, be a poor choice for functional languages since the one huge
> data array is constantly changing?  Or since most GUI APIs are so
> heavily dependent on state?
>
> Looking over various types of applications, it seems that functional
> languages fit nicely into any particular situation be it a web server
> or ssh daemon.  But does anyone consider certain types of programs
> such as those involving complex GUIs a poor choice for functional
> languages?

The more I looked into functional programming techniques, the more I
discovered that simple axes like OO lang => Mutable, Stateful, vs
Functional language => Immutable, Stateless, do not describe the
design space accurately. "Functional" software has many imperative
regions and uses of mutable data. "OO" software has many functional
regions and immutable data.

Learning when to use functional vs imperative techniques, mutable vs
immutable data, and also how to keep the 2 cleanly separated, is the
main challenge, in my experience. In any language.

 I've done some reading on Reactive Functional Programming,
> but it seems very abstract (possibly just because relatively few
> people have done it).

My main knowledge of FRP is in Haskell. In that platform, is does
appear that FRP has struggled to stabilize and gain mainstream
acceptance. To date, I don't think any book on FRP has been published
either, which suggests a lack of adoption.

-Ben

It's just that many have done FRP, by many names. It's just the Haskell people who insists on proper names and theory-backed frameworks. :-)

On Wed, Jul 15, 2009 at 9:10 PM, Ben Hutchison <ben@playscapegames.com> wrote:

On Thu, Jul 16, 2009 at 2:34 AM, Josh Stratton<strattonbrazil@gmail.com> wrote:
> So on the subject of appropriate times for OO and functional
> paradigms, would writing a image manipulation program like gimp, for
> example, be a poor choice for functional languages since the one huge
> data array is constantly changing?  Or since most GUI APIs are so
> heavily dependent on state?
>
> Looking over various types of applications, it seems that functional
> languages fit nicely into any particular situation be it a web server
> or ssh daemon.  But does anyone consider certain types of programs
> such as those involving complex GUIs a poor choice for functional
> languages?

The more I looked into functional programming techniques, the more I
discovered that simple axes like OO lang => Mutable, Stateful, vs
Functional language => Immutable, Stateless, do not describe the
design space accurately. "Functional" software has many imperative
regions and uses of mutable data. "OO" software has many functional
regions and immutable data.

Learning when to use functional vs imperative techniques, mutable vs
immutable data, and also how to keep the 2 cleanly separated, is the
main challenge, in my experience. In any language.

 I've done some reading on Reactive Functional Programming,
> but it seems very abstract (possibly just because relatively few
> people have done it).

My main knowledge of FRP is in Haskell. In that platform, is does
appear that FRP has struggled to stabilize and gain mainstream
acceptance. To date, I don't think any book on FRP has been published
either, which suggests a lack of adoption.

-Ben

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

On Wednesday July 15 2009, Ben Hutchison wrote:
> ...
>
> The more I looked into functional programming techniques, the more I
> discovered that simple axes like OO lang => Mutable, Stateful, vs
> Functional language => Immutable, Stateless, do not describe the
> design space accurately. "Functional" software has many imperative
> regions and uses of mutable data. "OO" software has many functional
> regions and immutable data.

I fail to see how functional programming is anything but imperative.
Haskell, ML and (I assume) OCaml programs are still strongly and
explicitly sequential. You do not simply describe the characteristics
of what to compute, you tell it, procedurally, step by step how to
compute it. That is the definition of imperative programming and it
applies to C, C++, Java, Lisp, Scala, Haskell, Smalltalk, JavaScript
and many, many others.

Prolog is a closer to being declarative (the proper contrast to
imperative), but in practice one typically must write Prolog programs
that "guide" the Prolog interpreter's exploration of the problem space
through the use of things like cuts and by the simple expedient of
choosing the order of the literals in the body of a rule. The same goes
for rule-oriented systems such as OPS5, Mycin and their offspring
(which generally have the same expressive power as Prolog, namely that
of Horn clauses).

The only software I can think of that is really declarative are theorem
provers (including big honking ones like Cyc).

> Learning when to use functional vs imperative techniques, mutable vs
> immutable data, and also how to keep the 2 cleanly separated, is the
> main challenge, in my experience. In any language.

So the distinction is not imperative vs. functional, it's functional vs.
.

I once saw the Nqthm formalization of memcpy (from the C library). For
those that don't have a C programming background, that's a simple
memory copying routine. You tell it from and to where to copy and how
many bytes to copy. The formal logical characterization of what in C is
one line and in assembly maybe a few lines was a well over a hundred
lines of first-order logic.

Now consider what it would take to formalize any non-trivial C, C++ or
Java program. It's eminently intractable, and this is one big reason
that people are interested in functional programming languages. So you
can say something (anything) about what programs written in these
languages compute.

>  ...
>
> -Ben

Randall Schulz

Randall,

You wrote:

I once saw the Nqthm formalization of memcpy (from the C library). For
those that don't have a C programming background, that's a simple
memory copying routine. You tell it from and to where to copy and how
many bytes to copy. The formal logical characterization of what in C is
one line and in assembly maybe a few lines was a well over a hundred
lines of first-order logic.

This is one of the key reasons to look at domain specific logics. Formalization of memory concerns are the forte of logics like separation logic. The connectives of separation logic derive -- essentially -- from linear logic. They are dramatically more expressive, and hence come with a cost relative to theorem proviing. However, when scoped by the confines of certain computational problems (see smallfoot, for example), they provide excellent leverage and compression.

Best wishes,

--greg

On Wed, Jul 15, 2009 at 6:44 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Wednesday July 15 2009, Ben Hutchison wrote:
> ...
>
> The more I looked into functional programming techniques, the more I
> discovered that simple axes like OO lang => Mutable, Stateful, vs
> Functional language => Immutable, Stateless, do not describe the
> design space accurately. "Functional" software has many imperative
> regions and uses of mutable data. "OO" software has many functional
> regions and immutable data.

I fail to see how functional programming is anything but imperative.
Haskell, ML and (I assume) OCaml programs are still strongly and
explicitly sequential. You do not simply describe the characteristics
of what to compute, you tell it, procedurally, step by step how to
compute it. That is the definition of imperative programming and it
applies to C, C++, Java, Lisp, Scala, Haskell, Smalltalk, JavaScript
and many, many others.

Prolog is a closer to being declarative (the proper contrast to
imperative), but in practice one typically must write Prolog programs
that "guide" the Prolog interpreter's exploration of the problem space
through the use of things like cuts and by the simple expedient of
choosing the order of the literals in the body of a rule. The same goes
for rule-oriented systems such as OPS5, Mycin and their offspring
(which generally have the same expressive power as Prolog, namely that
of Horn clauses).

The only software I can think of that is really declarative are theorem
provers (including big honking ones like Cyc).


> Learning when to use functional vs imperative techniques, mutable vs
> immutable data, and also how to keep the 2 cleanly separated, is the
> main challenge, in my experience. In any language.

So the distinction is not imperative vs. functional, it's functional vs.
<something that defies formal characterization>.

I once saw the Nqthm formalization of memcpy (from the C library). For
those that don't have a C programming background, that's a simple
memory copying routine. You tell it from and to where to copy and how
many bytes to copy. The formal logical characterization of what in C is
one line and in assembly maybe a few lines was a well over a hundred
lines of first-order logic.

Now consider what it would take to formalize any non-trivial C, C++ or
Java program. It's eminently intractable, and this is one big reason
that people are interested in functional programming languages. So you
can say something (anything) about what programs written in these
languages compute.


>  ...
>
> -Ben


Randall Schulz

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com

I wouldn't call it sequential in Haskell, though certain patterns are
obviously sequential. Enter a trivial example that someone can throw
away as being too trivial:

foldl (+) 0 $ map (*2) [1..10]
110

In Haskell, the compiler is free to evaluate each element of map (*2)
[1..10] in any order it pleases, as many times as it wants, because
the result will be the same. So if it's cheaper to recalculate it
than suffer a cache miss, the compiler can choose to recalculate it.

In contrast, the Java code for the same thing:

int result = 0;
for (int a = 1; a < 11; a++)
{
result += a * 2;
}

cannot be reordered by the compiler, unless the compiler (or JIT) can
prove that there are no side effects (easy for this case, tricky in
general). Worse, the code *reads* as a sequence of operations,
instead of an expression.

Even in more mainstream languages, like C#, it's hard to be right
while saying that the language is sequential.

using System.Linq;

new[]{1,2,3}.Select(x => x / 0) does not throw an exception, though
forcing the result will.

For me, the important distinction is that in functional code, f(x)
gives the same result every time you call it with the same x.

2009/7/16 Randall R Schulz :
> On Wednesday July 15 2009, Ben Hutchison wrote:
>> ...
>>
>> The more I looked into functional programming techniques, the more I
>> discovered that simple axes like OO lang => Mutable, Stateful, vs
>> Functional language => Immutable, Stateless, do not describe the
>> design space accurately. "Functional" software has many imperative
>> regions and uses of mutable data. "OO" software has many functional
>> regions and immutable data.
>
> I fail to see how functional programming is anything but imperative.
> Haskell, ML and (I assume) OCaml programs are still strongly and
> explicitly sequential. You do not simply describe the characteristics
> of what to compute, you tell it, procedurally, step by step how to
> compute it. That is the definition of imperative programming and it
> applies to C, C++, Java, Lisp, Scala, Haskell, Smalltalk, JavaScript
> and many, many others.
>
> Prolog is a closer to being declarative (the proper contrast to
> imperative), but in practice one typically must write Prolog programs
> that "guide" the Prolog interpreter's exploration of the problem space
> through the use of things like cuts and by the simple expedient of
> choosing the order of the literals in the body of a rule. The same goes
> for rule-oriented systems such as OPS5, Mycin and their offspring
> (which generally have the same expressive power as Prolog, namely that
> of Horn clauses).
>
> The only software I can think of that is really declarative are theorem
> provers (including big honking ones like Cyc).
>
>
>> Learning when to use functional vs imperative techniques, mutable vs
>> immutable data, and also how to keep the 2 cleanly separated, is the
>> main challenge, in my experience. In any language.
>
> So the distinction is not imperative vs. functional, it's functional vs.
> .
>
> I once saw the Nqthm formalization of memcpy (from the C library). For
> those that don't have a C programming background, that's a simple
> memory copying routine. You tell it from and to where to copy and how
> many bytes to copy. The formal logical characterization of what in C is
> one line and in assembly maybe a few lines was a well over a hundred
> lines of first-order logic.
>
> Now consider what it would take to formalize any non-trivial C, C++ or
> Java program. It's eminently intractable, and this is one big reason
> that people are interested in functional programming languages. So you
> can say something (anything) about what programs written in these
> languages compute.
>
>
>>  ...
>>
>> -Ben
>
>
> Randall Schulz
>

>> So on the subject of appropriate times for OO and functional
>> paradigms, would writing a image manipulation program like gimp, for
>> example, be a poor choice for functional languages since the one huge
>> data array is constantly changing?  Or since most GUI APIs are so
>> heavily dependent on state?
>
> If that's how the Gimp works, could you explain how undo is implemented?

I was still thinking about this issue, so I decided to crack open gimp
and look at it. I do think gimp will consistently save images, but
most of the time I believe it is just altering a mutable buffer like I
mentioned. For example, it might save off an image and start
modifying the new buffer directly. Then when the user hits undo, gimp
just swaps back to the previous one. So if I click and drag my mouse
around the screen and let me, it will only be mutating the current
buffer and not the original.

I think it's more apparent on complex filters, where it's altering the
image pixel by pixel. If you slide a slider around, you'll see the
image consistently redraw. You can move the slider over a bit and
when the filter gets a third of the way down, move it again and the
image will start redrawing from the top.

I imagine that's how other applications like CAD might work, where
they copy an object, mutate it to a new position with every mouse
drag, and then replace the new object with the old one (and its
original position) on undo. That way you're not creating a new mesh
every single drag of the mouse but just on the press and releases,
which seems a lot less expensive.

Josh

On Monday July 27 2009, Josh Stratton wrote:
> >> So on the subject of appropriate times for OO and functional
> >> paradigms, would writing a image manipulation program like gimp,
> >> for example, be a poor choice for functional languages ...?
> >
> > If that's how the Gimp works, could you explain how undo is
> > implemented?
>
> I was still thinking about this issue, so I decided to crack open
> gimp and look at it. I do think gimp will consistently save images,
> but most of the time I believe it is just altering a mutable buffer
> like I mentioned. For example, it might save off an image and start
> modifying the new buffer directly.

I think you could make the case that, at a suitable level of
granularity, these images are still being handled like immutable
objects. The fact that millions of pixels need to be recomputed to
create a is merely a low-level implementation detail at the level of
the code that operates on images as a whole.

> ...
>
> Josh

Randall Schulz

> There are lots of smart ways that functional languages gain substantial
> efficiency with their data structures, and even more smart ways that the JVM
> optimizes that kind of memory behavior.  In general, it is safe to assume
> that "these kind of problems" aren't a problem, and it's safe to move
> forward without the FUD.

It seems these problems would be caused by the bottleneck of
allocating and copying memory, correct? So if I were to be working
with a large array (~100MB) and each operation on each element became
relatively more and more expensive, these
allocating/copying/creating/destroying issues become more negligible,
right?

On that topic, looking at examples of List.map(), which returns
another immutable list, would this function be any faster than
iterating through the list with a foreach or is it just more concise?
I've seen a few examples that try to create thread pools that handle
their own mapping. Is this functionality not provided in Scala
somewhere like a pmap function in other languages? It seems that a
fast parallel mapping would be significant in offsetting any minor
bottlenecks using immutable structures, right?

Josh