FP and Performance

[Saxo]

Hello,

I read this article a while ago that compares the performance of quicksort programmed in an imperative way and in FP style: Benchmarking Scala Against Java Now the performance of the FP approach is about a factor 20 slower than the imperative one. This is something that really makes me think and recalls some phrase on a slide of a presentation by Andrey Breslav (creator of Kotlin), which is roughly like this: "FP makes many things simpler, sometimes for a high price".

The author is making the point that when performance drops to much you change from FP to imperative programming doesn't make sense to me. You have all the safeness and correctness because of FP. But there was a performance problem and thus only 30% of the code is imperative code. At the end you have 70% of the safeness and reliability and correctness of FP. Hm ...

Well, but that's not why I'm making this post. If I had to optimize performance for the quick sort case I would clone the list to be sorted (create new list and move the pointers over from the orinial list). Then I would do the imperative quick sort on the cloned list. This way I have a non-destructive approach, I can walk back on the stack in the debugger. I wonder whether other people would consider this simply nothing but a laugh or whether it makes somewhat sense.

What I would learn myself from FP is non-destructive programming aks no side effects, recursion, lazy evaluation, monads. I wouldn't try to be 100% pure and also do all changes of data on the stack and I would forget about functional collections and go with something like STM. Now I wonder whether that is a naive approach. But this is how I would create my own "religion". Am I the only guy observing that kind of "bad thoughts" going through my head? What do other people think about this?

Regards, Oliver

[Dennis Haupt]

and that's why the hybrid way wins

-------- Original-Nachricht --------
> Datum: Fri, 30 Nov 2012 05:48:47 -0800 (PST)
> Von: Saxo <jet...@web.de>
> An: scala...@googlegroups.com
> Betreff: [scala-user] FP and Performance

> Hello,
>
> I read this article a while ago that compares the performance of quicksort
> programmed in an imperative way and in FP style: Benchmarking Scala
> Against

> Java <http://java.dzone.com/articles/benchmarking-scala-against> Now the

> performance of the FP approach is about a factor 20 slower than the
> imperative one. This is something that really makes me think and recalls
> some phrase on a slide of a presentation by Andrey Breslav (creator of

> Kotlin <http://kotlin.jetbrains.org/>), which is roughly like this: "FP

[Oliver Ruebenacker]

Hello,

It would be good if those who advocate for using FP would make it
more clear, whether they advocate for using FP (a) sometimes, (b)
often, (c) most of the time or (d) always.

Because I keep having repeated discussions that go roughly like this:

Me: Why FP in this case?
OP: Thread safety, easier to reason, ...
Me: But in this case, it is much more complicated and slower.
OP: Here's a link to a video of Martin Odersky saying FP is better.

Take care
Oliver

--
IT Project Lead at PanGenX (http://www.pangenx.com)

"Stagnation and the search for truth are always opposites." - Nadezhda
Tolokonnikova

[Dennis Haupt]

i am somewhere between b and c. my rule is: if a side effect doesn't leave a function, it's still pure enough for me. it can get as dirty as you need, as long as it's local.

-------- Original-Nachricht --------
> Datum: Fri, 30 Nov 2012 09:47:29 -0500
> Von: Oliver Ruebenacker <cur...@gmail.com>
> An: Dennis Haupt <h-s...@gmx.de>
> CC: Saxo <jet...@web.de>, scala...@googlegroups.com
> Betreff: Re: [scala-user] FP and Performance

[Rex Kerr]

After viewing these sorts of things for a while, I think too much of a fuss is made over them.  You want to have both things in your toolbox.  So get both; use the appropriate one.

Conceptually, there isn't that much difference.  All computers are inherently mutable (they would be too big if they were write-once-read-many), so in the end even FP code ends up not being functional.  And any mutable code can be turned functional just by introducing a new variable each time something is mutated (though there may be more efficient ways to do things than this).

Practically, maintaining mutable code is like managing your memory manually.  Actually, I take that back: it _is_ managing your memory manually.  You explicitly say what you're reusing and how, with all the problems that are associated with manual management (i.e. forgetting what you've done or need to do to leave things in the correct state).  Sometimes it's the only good way to go (either for speed, or you need something that is easy to express manually); sometimes you are better off leaving that management to the computer instead.

  --Rex

P.S. The "easy to express manually" thing applies to other memory management also.  Converting a struct to an array of bytes is utterly trivial in C++.  In Java it's a sizable hassle.

[nicola...@gmail.com]

FP is about isolating effects. If you copy a list into a fresh array, sort the array in place and 

make a list out of this array, all effects are isolated and every visible piece of data, is actually a piece of 

immutable data,

So, I would not hesitate a second before doing so, if it is a bottleneck in a program.

It is even possible to make this approach provably functional if your type system enforces no side-effect.

For example, in Haskell, you could use an intermediate STArray. The type system would ensure that nobody sees

the effects from outside the quicksort.

FP is not about never using a reference, it is about having no transversal side-effects polluting a whole program.

Local effects are not a problem.

--
Sent from an IBM Model M, 15 August 1989.

[Simon Ochsenreither]

Wow, horrible article. The “idiomatic Scala” implementation of QuickSort doesn't even implement QuickSort.

I wish people would stop with this fundamentalistic non-sense of choosing the wrong tools for the job and then trying to derive any meaningful knowledge from it.

[Daniel Sobral]

I just want to make a small point here: if you want to sort, why are you sticking with quicksort for the functional algorithm? It's not like quicksort is the only sorting algorithm, nor even the most efficient one, and it's certainly not a good match for Scala FP. By all means, compare an imperative quicksort with a functional sorting algorithm if you want, but it's pretty damn silly to choose an algorithm that is particularly unsuited to strict FP for a benchmark.

As a side note, I hear quicksort with lazy FP is much better, but that's hearsay.

--
Daniel C. Sobral

I travel to the future all the time.

[Boris Hollas]

On 30.11.2012 14:48, Saxo wrote:
> <http://java.dzone.com/articles/benchmarking-scala-against> Now the

> performance of the FP approach is about a factor 20 slower than the
> imperative one. This is something that really makes me think and recalls

In the scala code, the filter function is applied twice to tail. This is
the easiest way to implement it in a functional way, it can be improved
by using a partition function that takes a predicate and a list and
returns two lists. The advantage for FP here is that the idiomatic
solution is easier to understand.

I believe that in practice the biggest problem in SE is not performance
but maintainability and QA. I know people who spend a lot of effort
optimizing their code in places where it makes little difference of when
compiler optimization may work equally well, and neglect QA. It should
be the other way: Concentrate on code quality and QA first, the use a
profiler to identify performance bottlenecks and optimize. If you have
to sort often, use the imperative version of a quick sort. Or use heap
sort, which always runs in O(n log n).

[Daniel Sobral]

On Fri, Nov 30, 2012 at 6:28 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:

     Hello,

On Fri, Nov 30, 2012 at 11:05 AM, Daniel Sobral <dcso...@gmail.com> wrote:
> I just want to make a small point here: if you want to sort, why are you
> sticking with quicksort for the functional algorithm? It's not like
> quicksort is the only sorting algorithm, nor even the most efficient one,
> and it's certainly not a good match for Scala FP. By all means, compare an
> imperative quicksort with a functional sorting algorithm if you want, but
> it's pretty damn silly to choose an algorithm that is particularly unsuited
> to strict FP for a benchmark.
>
> As a side note, I hear quicksort with lazy FP is much better, but that's
> hearsay.

  Is there any sorting algorithm of order n*log(n) that is suitable
for strict FP?

Merge sort is much better suited, for one, but I'm no expert on the topic. At least googling it would be advisable.

 

     Take care
     Oliver

--
IT Project Lead at PanGenX (http://www.pangenx.com)

"Stagnation and the search for truth are always opposites." - Nadezhda
Tolokonnikova

[Saxo]

 OP: Here's a link to a video of Martin Odersky saying FP is better.

People that won't develop an opinion of their own are a nuisance. I know ...

Practically, maintaining mutable code is like managing your memory manually.

I like this one. There is some truth in it.

For example, in Haskell, you could use an intermediate STArray. The type system would ensure
that nobody sees the effects from outside the quicksort.

This is interesting and in general a good idea for a language to have whether it is made for FP or not. One problem I have with cloning the list and then changing the clone is that the clone process is not thread-safe. I could put a mutex block in the list clone method, but if you put a mutex block around everything like that you might slow down the system.

As a side note, I hear quicksort with lazy FP is much better, but that's hearsay.

Well, the OOP variant is to have a class SortedCollection (as in Smalltalk). Whenever an element is added to it, it is moved to the right position so that the SortedCollection remains sorted. Because Java has this Array.sort(...) method and no SortedCollection (TreeSet is sorted, but people simply mostly do Array.sort, because they don't get educated about it). Problem with this is that the SortedCollection is not immutable in that sense.

I believe that in practice the biggest problem in SE is not performance
but maintainability and QA.

Yes, absolutely agree. It's just the factor 20 that made me think...

Saw today some Scala code I wanted to share:

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {
    def fmap[A, B](f: A ->> B): F[A] ->>> F[B]
}

Whenever I'm just saying to myself that I should give Scala a try now I see code like that and I just ask myself what the heck is this. I think I will give Scala a try in spite. If it's only some place where the Java glue code programmers, that think they are so good, can't follow you I'll be glad ..

Regards, Oliver

[nicola...@gmail.com]

On Sat, Dec 1, 2012 at 1:03 PM, Saxo <jet...@web.de> wrote:

 OP: Here's a link to a video of Martin Odersky saying FP is better.

For example, in Haskell, you could use an intermediate STArray. The type system would ensure
that nobody sees the effects from outside the quicksort.

This is interesting and in general a good idea for a language to have whether it is made for FP or not. One problem I have with cloning the list and then changing the clone is that the clone process is not thread-safe. I could put a mutex block in the list clone method, but if you put a mutex block around everything like that you might slow down the system.

A list should be immutable. So you can take all the time you want to clone it without it changing, that's one of the point

of persistent data-structures.

 

As a side note, I hear quicksort with lazy FP is much better, but that's hearsay.

Well, the OOP variant is to have a class SortedCollection (as in Smalltalk). Whenever an element is added to it, it is moved to the right position so that the SortedCollection remains sorted. Because Java has this Array.sort(...) method and no SortedCollection (TreeSet is sorted, but people simply mostly do Array.sort, because they don't get educated about it). Problem with this is that the SortedCollection is not immutable in that sense.

If you need something sorted all the time it is better to have a sorted data structures. If you need it sorted only once, 

it might be lest costly to sort it only once.

 

Saw today some Scala code I wanted to share:

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {
    def fmap[A, B](f: A ->> B): F[A] ->>> F[B]
}

Whenever I'm just saying to myself that I should give Scala a try now I see code like that and I just ask myself what the heck is this. 

Some advanced stuff that many programmers don't use.  From the look of it, it looks like a definition of a functor between two categories. 

http://en.wikipedia.org/wiki/Functor

One whose arrows are written ->> and another whose arrows are written ->>>. 

You don't need to understand that to go very far in FP, even if you want to have a practical use of advanced pure functional stuff, like monads or functors. 

(And a lot of advanced Scala users do not use this kind of things anyway.)

 

[Seth Tisue]

On Fri, Nov 30, 2012 at 9:47 AM, Oliver Ruebenacker <cur...@gmail.com> wrote:

> It would be good if those who advocate for using FP would make it
> more clear, whether they advocate for using FP (a) sometimes, (b)
> often, (c) most of the time or (d) always.
>
> Because I keep having repeated discussions that go roughly like this:
>
> Me: Why FP in this case?
> OP: Thread safety, easier to reason, ...
> Me: But in this case, it is much more complicated and slower.
> OP: Here's a link to a video of Martin Odersky saying FP is better.

Heh — pretty sure "OP" here is me.

In my case, it's "FP often", though I aspire to "FP most of the
time". I have no personal experience with doing real work
entirely in strict "FP all the time" style, although I know
people who work that way and seem to like it. In my talks I
almost always show pure-functional concepts and code, but that's
not because I never write imperative code myself. I do. It's just
that I assume we all already know how to do that, whereas FP
style is unfamiliar and so that's where the opportunities for
learning are -- certainly for myself, and hopefully for the
audience too.

In the lens talk, I chose the turtle graphics example because it
is a convenient way to present lenses -- not because I was trying
to demonstrate the value of coding in functional style. If that
had been my goal, the talk would have been very different.

In short, this was an FP how-to talk, not an FP advocacy talk. I tried
to be clear about that, but I'll try harder next time.

In the turtle graphics example, the lens-based code is in fact, as
you say, more complicated and slower. So why bother?

Well, the code in the slides is only about 50 lines. That's about
as much code as you can show in any talk. But what does the rest
of the system look like? In a real system with 1000 or 10,000 or
100,000 lines of code, whether your underlying domain classes are
mutable or immutable could have a variety of different profound
implications. Making the immutable choice could definitely lead
to an overall system that is actually simpler and faster. And I
think Martin in his talks actually does a good job of explaining
— as best he can in the space of 10 or 15 minutes in a talk
mostly devoted to other topics — why that might be. (If you don't
find Martin's explanations satisfying, then we could talk about that,
but you'll have to tell us what you find lacking.)

In my own experience with rewriting imperative code in functional
style, I've found that the resulting code is clearer, more maintainable,
more thread safe, and more testable, and I have more confidence
it is correct. But I also have plenty of working imperative code that
I leave alone because I don't see sufficient payoff from reworking it.
Acquiring good judgment about where the FP payoffs are biggest
is a matter of experience.

--
Seth Tisue | Northwestern University | http://tisue.net
developer, NetLogo: http://ccl.northwestern.edu/netlogo/

[Vlad Patryshev]

Saw today some Scala code I wanted to share:

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {
    def fmap[A, B](f: A ->> B): F[A] ->>> F[B]
}

This is pretty funny. Two categories have the same collection of objects (arbitrary A and B), but different collections of morphisms.

What is it good for, I wonder. Hope there is some kind of science there, not just c++ programmers going rogue.

[Russel Winder]

On Sat, 2012-12-01 at 02:39 -0200, Daniel Sobral wrote:
[…]

> Merge sort is much better suited, for one, but I'm no expert on the topic.
> At least googling it would be advisable.

Modified TimSort appears to be the sort of the moment; both Python and
Java have adopted it as the standard sort algorithm.

--
Russel.
=============================================================================
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel...@ekiga.net
41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@winder.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder

[Seth Tisue]

On Sun, Dec 2, 2012 at 12:55 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:
>> In short, this was an FP how-to talk, not an FP advocacy talk. I tried
>> to be clear about that, but I'll try harder next time.
>

> Well, if you issue statements like "we hate mutable objects" ;)

Yeah, so, half joking there. But half serious too.

*Suppose* we hate mutable objects and try to do without them. What
happens? I don't have all the answers, but I'm trying to learn.

All four of your questions below are excellent questions. Each one
would be a good basis for a whole discussion, book chapter, blog post,
or user group talk. (Maybe I'll actually try to develop a talk about
one or more of them...)

> First, objects often represent things in the real world. That seems
> to be the most intuitive approach. Things in the real world typically
> change. I can use a sequence of states instead, but how do I tie that
> sequence to the identity of the thing that changes? If I need to know
> the latest state, where do I look for it?

Two reading recommendations:

- James Hague, "Purely Functional Retrogames" blog post series,
beginning with http://prog21.dadgum.com/23.html . "I started thinking
about how to write trivial games, like Pac-Man or Defender, in a
purely functional manner. Then I realized that it wasn't performance
that was the issue, it was much more fundamental... I had no idea how
to structure the most trivial of games without using destructive
updates..."

- Paul Hudak's book The Haskell School of Expression: Learning
Functional Programming through Multimedia. All of the examples are
about animation and simulation — things that change over time.

The Hudak is a whole book so it takes a lot longer to read than the
Hague, but it's also a lot more concrete and detailed and is full of
actual working programs.

Rich Hickey is also very good on the subject of what domain modeling
looks like without using mutation.

> Second, how does FP scale with object composition? [...]
> universe.milkyWay.solarSystem.earth.unitedStates.massachusetts.cambridge.mit.stataCenter.starRoom.door.closed = true

Brief sketch of an answer:

Instead of modeling this as:

case class Door(..., closed: Boolean)

I would model it as:

case class Door(...)
case class DoorState(door: Door, closed: Boolean)

or if necessary, make the linkage indirect using keys:

case class Door(id: Long, ...)
case class DoorState(doorId: Long, closed: Boolean)

Hague covers this at greater length in the Purely Functional Retrogames series.

> Third, what about circular references? [...]

Instead of this:

case class Person(..., spouse: Person)

I'd have:

case class Person(...)
case class Marriage(spouse1: Person, spouse2: Person)

Thereby removing the circularity.

Again, see Hague. He writes: "In a functional language, the worst
thing you can do is create a large 'struct' containing all the data
you think you might need for an entity..."

Note that it's actually possible to create circular references between
immutable objects. Google "Scala immutable cycle", and/or see
https://groups.google.com/d/msg/scala-user/hibgYwDAzm8/yqLmW8KX55cJ .
But it seems to me like a trick I might occasionally reach for in
unusual situations, rather than something I'd routinely reach for.
(Actually, that whole thread I just linked to is relevant to all of
your questions.)

> Fourth, what about call-backs? Consider recording events in memory.
> A typical mutable approach would go like this: [...]

I've been thinking about this on and off since you (I think it was
you) asked it at the user group.

One common answer is to use the Writer monad. Multiple sources on the
web explain how to use Writer to do logging. For example, see Tony
Morris's http://blog.tmorris.net/the-writer-monad-using-scala-example/

But in order to do it this way, you have to write your code in monadic
style, using "for" to string everything through chained flatMap calls,
as shown in
Tony's post. But this seems to me like a heavy price to pay,
especially since monadic style is less elegant in Scala than it is in
Haskell.

So, I'm interested in what other answers exist. One answer that I
actually used recently in my work is to change the causation around.
Instead of having changed data trigger events, use an event to trigger
the data change in the first place. Then that same event can also be
used to trigger other things, including logging. So instead of the
chain of causation being:

alter state --> raise event --> listeners handle event

instead you do:

/-----> (construct new state)
raise event --
\-----> (listeners handle event)

Sorry, I know this is sketchy. I'll keep thinking about it and maybe
develop this at greater length later.

Hague touches on this same idea in part 4 of his series. "A clean
alternative is not to return new versions of anything, but to simply
return statements about what happened..."

See also Martin Fowler's article on "event sourcing":
http://martinfowler.com/eaaDev/EventSourcing.html
Also relevant: http://en.wikipedia.org/wiki/Command_pattern

[Daniel Sobral]

Seth has very good answers, but I'd like to add something about the first question.

You say that objects model things in the real world, and things in the real world change. Heraclitus went to the root of this when he said  “You never bathe in the same river twice.” It's not going to be the same river, nor will you be the same man. I man literally: you'll both be composed of completely different atoms (well, mostly, in your case). The name is the same, not the object itself.

So let's be less philosophical. Consider the stock for a book on Amazon. That's a non-strict natural number: it could be one, it could be five thousand, it could be zero. When the stock reduces or increases, the number itself doesn't change: zero will still be zero, even if the stock goes from zero to a hundred. That goes without saying, because most languages mandate immutable numbers. The question, then, is how do we go from representing the stock as "var stock: Int" to "val stock: Int"?

As it happens, whatever number is stored there is occasionally inconsistent, because what makes the stock go up or down is books physically going in or out of the warehouses. The information on the system will trail or lead the reality.

The thing is, when the stock changes, it doesn't make the old information invalid. The information that a book had five copies in stock does not become invalid when new books arrive. It just doesn't refer to the same point in time. At time T1, they had X copies, and at time T2 they had Y copies. Both numbers are valid, and it's perfectly valid for both to exist as immutable values at the same time. And, when you do code that way, you are much less susceptible to errors.

So, why would you ever represent it as "var stock: Int"? What does it gain? At most, it obscures the fact it is not the actual number, just a sampling of it in time.

[Alexandru Nedelcu]

Hi,

As a general rule of thumb, you do not implement Quicksort by hand,
unless you read a paper or two about it first. In the article the
functional version picks the "head" of the list as being the pivot.
That's actually terrible, since sorting in one of the most common
use-cases (an already sorted or almost sorted list, either ascending
or descending) will yield polynomial O(n^2) time complexity.

To blame is all the books giving that Quicksort version as some kind
of good example of FP code. It isn't.

--
Alexandru Nedelcu
http://bionicspirit.com

[Boris Hollas]

On 03.12.2012 08:47, Alexandru Nedelcu wrote:
> functional version picks the "head" of the list as being the pivot.
> That's actually terrible, since sorting in one of the most common
> use-cases (an already sorted or almost sorted list, either ascending

It isn't any better if you use the last element as pivot (as some
C-implementations do) and have an already sorted list. You can use
radomized quicksort or heap sort.

[ericacm]

Speaking of games implemented using FP, check out the series of blog posts "tetrix in Scala" by Eugene Yokota, starting at http://eed3si9n.com/tetrix-in-scala-day0.   Good stuff.

[Oliver Ruebenacker]

Hello,

On Mon, Dec 3, 2012 at 3:57 PM, ericacm <eri...@gmail.com> wrote:
> Speaking of games implemented using FP, check out the series of blog posts
> "tetrix in Scala" by Eugene Yokota, starting at
> http://eed3si9n.com/tetrix-in-scala-day0. Good stuff.

Is this considered FP? Aren't actors mutable objects?

Take care
Oliver

[ericacm]

Sorry - I should have been more clear.  His series of posts is not intended to be purely FP, but it does show off a lot of good FP practice.

[Detering Dirk]

> -----Ursprüngliche Nachricht-----

> Im Auftrag von Vlad Patryshev

>>          Saw today some Scala code I wanted to share:

> >

> >         trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {

> >             def fmap[A, B](f: A ->> B): F[A] ->>> F[B]

> >         }

>

> This is pretty funny. Two categories have the same collection of objects

> (arbitrary A and B), but different collections of morphisms.

>

> What is it good for, I wonder. Hope there is some kind of science there, not

> just c++ programmers going rogue.

 

I suppose it comes from:

https://hseeberger.wordpress.com/2010/11/25/introduction-to-category-theory-in-scala/

 

My spontaneous reaction to Oliver's conclusion on this code:

 

> Whenever I'm just saying to myself that I should give Scala a try now I see

> code like that and I just ask myself what the heck is this.

 

I am interested in science, and physics seems to be something one should

know a bit about. But every time I want to give it a try I see things like this:

http://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm#The_Algorithm

 

Or I open a popscience magazine and see things like this:

http://blog.streitenberger.net/wp-content/uploads/png/360GradPanoramasdesLHCamCERN_8BE2/lhc.jpg

 

No, seriously. Code like the one above is fascinating and scaring at the same time.

But it is not where to start from, this is where possibly(but not necessarily!) one day to land.

And this is presumably one of the best features of Scala and its community: It teaches you

new mind broadening things and makes you think differently. Step by step.

 

KR

Det

 

 

 

BITMARCK Software GmbH

Firmensitz: Paul-Klinger-Strasse 15, 45127 Essen

Geschaeftsfuehrer: Andreas Strausfeld

Registergericht: Amtsgericht Essen HRB 20680

 

 

***********************************************************************

 

Die Information in dieser E-Mail ist vertraulich und ist ausschliesslich

fuer den/die benannten Adressaten bestimmt. Ein Zugriff auf diese

E-Mail durch andere Personen als den/die benannten Adressaten ist

nicht gestattet. Sollten Sie nicht der benannte Adressat sein, loeschen

Sie bitte diese E-Mail.

 

[Oliver Ruebenacker]

Hello,

On Sun, Dec 2, 2012 at 10:07 PM, Seth Tisue <se...@tisue.net> wrote:
> On Sun, Dec 2, 2012 at 12:55 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:
>> Second, how does FP scale with object composition? [...]
>> universe.milkyWay.solarSystem.earth.unitedStates.massachusetts.cambridge.mit.stataCenter.starRoom.door.closed = true
>
> Brief sketch of an answer:
>
> Instead of modeling this as:
>
> case class Door(..., closed: Boolean)
>
> I would model it as:
>
> case class Door(...)
> case class DoorState(door: Door, closed: Boolean)
>
> or if necessary, make the linkage indirect using keys:
>
> case class Door(id: Long, ...)
> case class DoorState(doorId: Long, closed: Boolean)

What does that gain me? Are you suggesting the doorState is not part
of universe? Then who owns it?

>> Third, what about circular references? [...]
>
> Instead of this:
>
> case class Person(..., spouse: Person)
>
> I'd have:
>
> case class Person(...)
> case class Marriage(spouse1: Person, spouse2: Person)

But how does a person know which marriage they are part of?

> Thereby removing the circularity.

But you fail the requirements. If I pass you the object sally, how
can you find out who she's married to?

> Again, see Hague. He writes: "In a functional language, the worst
> thing you can do is create a large 'struct' containing all the data
> you think you might need for an entity..."

Yes, but what is the alternative? If I need to combine information
residing in multiple distinct objects, some other object needs to
obtain a reference to all of them. If that objects itself is
immutable, I just composed a large object.

> Note that it's actually possible to create circular references between
> immutable objects. Google "Scala immutable cycle", and/or see
> https://groups.google.com/d/msg/scala-user/hibgYwDAzm8/yqLmW8KX55cJ .
> But it seems to me like a trick I might occasionally reach for in
> unusual situations, rather than something I'd routinely reach for.
> (Actually, that whole thread I just linked to is relevant to all of
> your questions.)

Yes, it is possible if you have constructors calling each other.
Obviously won't scale well, though.

But that means that whoever is responsible for raising the event is
also responsible for both the construction of the new state and the
response of the listeners. That would be a lot of responsibilities for
a single objects. How can it be split?

> Hague touches on this same idea in part 4 of his series. "A clean
> alternative is not to return new versions of anything, but to simply
> return statements about what happened..."

And then let any one who needs to know the new state calculate it
for themselves?

Take care

[Daniel Sobral]

On Tue, Dec 4, 2012 at 12:19 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:

     Hello,

> case class Marriage(spouse1: Person, spouse2: Person)

  But how does a person know which marriage they are part of?

Best way around it is having the person not need to know which marriage they are part of. Whatever method you called on Person that needs to know Marriage perhaps could, instead, be on Marriage.

Now, if that's not viable or practical for some reason, two alternatives would be passing the Marriage object along the method call into Person, or having Person's method call return a function (Marriage) => T, which can then be used elsewhere by whoever has the marriage information.

In a sense, that isn't particularly different than how the reader or state monads work. And, speaking of state monad, you mentioned elsewhere something being part of the "universe". Well, there can be a "state" which encompasses all these things, but a state doesn't have circular dependencies on other states. Instead, it's self-contained, and new states are produced by calling methods that take an old state and produce a new state.

Notwithstanding any of that, circular dependencies are terrible even on purely OO systems, and principles such as SOLID steer away from designs that fall into that kind of situation.

 

> Thereby removing the circularity.

  But you fail the requirements. If I pass you the object sally, how
can you find out who she's married to?

Whose requirements? How can you know who Sally is married to? Sure, you can ask her, but you could also look up legal information where that is recorded. And, besides, Sally doesn't need to give you her husband when you ask her who he is -- she would usually just tell you the *name* of her husband. Same thing applies to object -- didn't you look to the real world for analogues of objects?

[Boris Hollas]

On 04.12.2012 17:27, Daniel Sobral wrote:
> > case class Marriage(spouse1: Person, spouse2: Person)
>
> But how does a person know which marriage they are part of?

I'm afraid there's no good solution for this in any imperative or
functional language. Marriage is a relation and you want all (in
western societies at most one) elements X that satisfy Marriage(bob, X).
This is an easy problem in Prolog however.

[Seth Tisue]

>>>>> "Oliver" == Oliver Ruebenacker <cur...@gmail.com> writes:

>> I would model it as:
>> case class Door(...) case class DoorState(door: Door, closed:
>> Boolean)

Oliver> What does that gain me? Are you suggesting the doorState is
Oliver> not part of universe? Then who owns it?

Hopefully something a lot less deeply nested than you've nested the Door
objects inside other things...! Separating the stuff about Door that
changes from the stuff that isn't going to change gives us the freedom
to store the state information somewhere else.

I think the James Hague series that I recommended, about Pac-Man, and
the Eugene Yokota series ericacm recommended (through day 4, you can
bail once he's eliminated the vars and starts moving on to actors stuff
and AI stuff), about Tetris, should give you ideas about what happens
next.

>> case class Person(...) case class Marriage(spouse1: Person,
>> spouse2: Person)

Oliver> But how does a person know which marriage they are part of?
Oliver> If I pass you the object sally, how can you find out who she's
Oliver> married to?

You'll need to also give me some other value in which I can look that
information up. A Set[Marriage], or a Map[Person, Marriage], or what
have you. In FP, it's normal for a class not to come packaged along
with all of the operations on it. It's normal for those operations to
exist as a separate functions (that perhaps require additional data).

Hopefully that Set or Map containing Marriage objects is itself
immutable. But if you want to use a mutable Set or Map, go ahead. At
least we've achieved an immutable Person class. We've gotten somewhere.
Perhaps in a future refactoring we would replace the mutable collection
with an immutable one. I'm always trying to push effects and mutability
out of my core code and towards the outer edges of my program, but I
don't consider myself to have failed if more work of this kind remains
left to do.

Eugene's series on Tetris walks you through a good example of this. In
day 1, he introduces a mutable "universe" type class called Stage, and
he gets his tests passing. Then in day 2, he refactors until his
"universe" class is an immutable one called GameState. Functions that
change state have type GameState => GameState. The tests only need to
be changed a little bit to pass, and then structuring his code this way
enables everything that happens later in the more advanced entries where
he tackles concurrency, AI, etc.

>> Again, see Hague. He writes: "In a functional language, the worst
>> thing you can do is create a large 'struct' containing all the data
>> you think you might need for an entity..."

Oliver> Yes, but what is the alternative? If I need to combine
Oliver> information residing in multiple distinct objects, some other
Oliver> object needs to obtain a reference to all of them. If that
Oliver> objects itself is immutable, I just composed a large object.

It's fine to have a large immutable collection, like a Map or Set or a
Vector. (For example, the Set[Marriage] I suggested earlier.) Thanks
to Bagwell, Okasaki, et al, we can update these cheaply, even if they
are very large. The updated copies share most of their structure with
the old copies, so there's very little waste.

What Hague suggests we avoid is having lots of fields in our case
classes. That's different. (Avoiding that isn't a law, just a good
rule of thumb.)

>> Hague touches on this same idea in part 4 of his series. "A clean
>> alternative is not to return new versions of anything, but to simply
>> return statements about what happened..."

Oliver> And then let any one who needs to know the new state
Oliver> calculate it for themselves?

If you're imagining lots of duplicated code, that certainly isn't
necessary. You'd have a function for computing the new state, that you
could call anywhere you needed it. See Eugene's Tetris series,
especially day 2.

>> So, One answer that I actually used recently in my work is to change

>> the causation around. Instead of having changed data trigger
>> events, use an event to trigger the data change in the first
>> place. Then that same event can also be used to trigger other

>> things, including logging. [...]

Oliver> But that means that whoever is responsible for raising the
Oliver> event is also responsible for both the construction of the new
Oliver> state and the response of the listeners. That would be a lot of
Oliver> responsibilities for a single objects. How can it be split?

I think in Scala we have lots of tools for keeping concerns separate in
our code and almost any of them might be relevant here. It isn't
obvious to me that there's a single most obvious shape for an answer to
take. But I don't see that there's any truly fundamental difficulty
here, either. If you still do, we could talk about it further, but I
think I've written enough for one day :-)

Curious, have you actually tried writing a program -- perhaps just a
small toy one -- in this style yet? Because if you haven't, if you
tried it you might discover that the complexities are fewer and the
difficulties less fundamental than you're imagining. Or, if you do try
it and get stuck, you could post your code and we'd have a more concrete
basis for discussion.

Only just found and skimmed it, but there's a blog post series called
"Towards an immutable domain model" at
http://blog.zilverline.com/2011/02/01/towards-an-immutable-domain-model-introduction-part-1/
that looks extremely relevant to this discussion. The example domain is
invoicing. ("The trick is to model all state changes of the invoice
explicitly as an event. This event becomes our explicit notion of
change...")

[Oliver Ruebenacker]

Hello,

On Wed, Dec 5, 2012 at 4:42 AM, Jed Wesley-Smith <j...@wesleysmith.io> wrote:
> Just like to say that being involved in performance engineering at Atlassian
> I've studied these things quite a lot, and there are often serious
> performance advantages to FP code.

Clearly, if the FP solution can do with a similar number of
operations and object creation as the alternatives, the FP solution is
superior. But what if the FP solution needs more operations and object
creations? How much is FP faster? A little? A lot?

> Also, new objects only reference older objects, so you don't need to
> traverse outside the new generation to find all references as almost no
> older objects can possibly reference new ones.

It's a bit more complicated. Object creations can overlap in FP.
Basically, A can refer to B as long as creation of B starts before
creation of A ends. That's how circular references can be created.

[cagdas senol]

I just want to share a benchmark for Object Allocation on 2.9 and 2.10
2.10 allocates almost 25-30 times less object thn 2.9(on some cases).

https://github.com/csenol/2.10.0-RC3-Benchmark

On Thu, Dec 6, 2012 at 9:25 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:
>
> Clearly, if the FP solution can do with a similar number of
> operations and object creation as the alternatives, the FP solution is
> superior. But what if the FP solution needs more operations and object
> creations? How much is FP faster? A little? A lot?

--
Cagdas Senol