Scala Video by "Child" Programmer

173 views
Skip to first unread message

clay

unread,
Feb 8, 2012, 11:56:07 PM2/8/12
to The Java Posse
This is way too scripted and the childish exuberance is too calculated
to not be done by an adult, but nevertheless, this is a really neat
Scala video. It really showcases the conciseness and maintainability
benefits of functional programming:

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

Marco Faustinelli

unread,
Feb 9, 2012, 2:18:48 AM2/9/12
to The Java Posse

I must confess that I have made a vow never to attend any more
demonstration of programming power involving Fibonacci: it's just too
far from the average day job.

All this in spite that I realize very well the benefits of functional
programming (I even practise it in JS and Java) and that I am Italian
myself.

Selling FP is tough. Its best showcase to my knowledge is robust code
handling immutable data. But I wouldn't let a cute kid present it to
my colleagues :-)

Marco

[Btw my vow applies also to breeding rabbits and foxes]

clay

unread,
Feb 9, 2012, 10:35:32 AM2/9/12
to The Java Posse
I completely agree. This type of problem is completely artificial and
not representative of day to day programming tasks, but I still think
it's impressive anyway. Some day to day programming tasks probably can
be simplified with these types of programming constructs. Then again,
most custom C++/Java/C# code that I've encountered can be wildly
simplified and streamlined without a new programming language or
fancier abstractions.

On Feb 9, 1:18 am, Marco Faustinelli <marco_faustine...@yahoo.com>
wrote:

Casper Bang

unread,
Feb 9, 2012, 11:26:43 AM2/9/12
to java...@googlegroups.com
The Scala Fibonacci code performs 5-6 times worse than an imperative iterative Java implementation:

casper@workstation:~$ time java -cp /usr/share/java/scala-library.jar:. ScalaFib
4613732

real 0m0.243s
user 0m0.292s
sys 0m0.020s

casper@workstation:~$ time java JavaFib
4613732

real 0m0.052s
user 0m0.040s
sys 0m0.008s

Frankly, that's a much higher penalty than I would've thought. Lack of tail-recursion? (Scala 2.9, OpenJDK 1.6.0_23)

Btw. this functional style has also been possible in C# since .NET 3.0 (2006).

Simon Ochsenreither

unread,
Feb 9, 2012, 12:49:24 PM2/9/12
to java...@googlegroups.com
This is way too scripted and the childish exuberance is too calculated to not be done by an adult

You mean like the scripted live presentation in front of an audience with completely scripted questions?

Sometimes I really wonder why I'm still reading this mailing list...

Kevin Wright

unread,
Feb 9, 2012, 12:49:20 PM2/9/12
to java...@googlegroups.com
Lack of tail-recursion isn't the problem, boxing is.  It's more of an issue with the JVM than it is with scala, and it's something that you'll run into with any form of functional programming on the platform (including e.g. google guava).

I keep hearing rumours that Oracle want to fix this because it's crippling anyone who wants to use the JVM for *big* science-style clustered number crunching, and it's the kind of revenue stream they don't want to miss out on.  The fixnum proposal from John Rose is one possibility here: http://blogs.oracle.com/jrose/entry/fixnums_in_the_vm

Having said that, tail-recursion certainly helps, and any recursive solution will neatly avoid the issues of boxing.  For this reason, scala will automatically optimise any method that's capable of tail recursion, and even offers the @tailrec annotation so you can validate that the optimisation has indeed happened.


Finally: There's a few scala solutions here: http://en.literateprograms.org/Fibonacci_numbers_(Scala) - including one tail-recursive design that's a great deal simpler and easier to understand than the imperative alternative.  It should also run as fast, if not faster.

Cédric Beust ♔

unread,
Feb 9, 2012, 12:52:46 PM2/9/12
to java...@googlegroups.com

On Thu, Feb 9, 2012 at 9:49 AM, Kevin Wright <kev.lee...@gmail.com> wrote:
It's more of an issue with the JVM than it is with scala,

If this were true, then the Java version would be as slow as the Scala version, wouldn't it?

If, like you say, the issue is with boxing, then it's clearly related to the way Scala does its boxing and it has nothing to do with the JVM.

-- 
Cédric

Simon Ochsenreither

unread,
Feb 9, 2012, 12:58:50 PM2/9/12
to java...@googlegroups.com
If this were true, then the Java version would be as slow as the Scala version, wouldn't it?

If the Java version would actually do the same, then yes. But frankly I'm not expecting to see a lazily evaluated Stream in the Java version.

clay

unread,
Feb 9, 2012, 1:15:57 PM2/9/12
to The Java Posse
Using some in-code timers, I got 20 ms for the Scala version and 0 ms
for a imperative Java version that I wrote

I agree that the runtime performance issues of Scala are quite real
and substantial. The Java/Scala runtime performance gap is larger than
the Java/C performance gap from my experience. Scala also has
compilation type performance issues, which are arguably less
important.

Also, sure you can do some functional/immutable programming in C#, but
that's really not the strength of C# or a good choice for more serious
functional/immutable programming. Even if you prefer pure Microsoft
branded tech, F# is far better for that.

You can also do functional/immutable style designs in Java. Not as
elegantly as you could in Scala/Haskell/Clojure/OCaml/F#, but my team
is doing exactly that.

FYI, here is the Java code that I used:

public static void main(String[] args) {
long start = System.currentTimeMillis();
long sum = 0;

long val1 = 1;
long val2 = 2;

while (val2 <= 4000000) {
if (val2 % 2 == 0) {
sum += val2;
}

long next = val1 + val2;
val1 = val2;
val2 = next;
}

long duration = System.currentTimeMillis() - start;
System.out.println(String.format("sum = %d", sum));
System.out.println(String.format("duration = %d", duration));
}

And the Scala:

val start = System.currentTimeMillis();

def fib(x: Int, y: Int): Stream[Int] = {
x #:: fib (y, x + y)
}

val answer = fib(1, 2).takeWhile(n => n <= 4000000).filter(n => n % 2
== 0).sum
val duration = System.currentTimeMillis() - start;

println(answer)
println(duration);

Casper Bang

unread,
Feb 9, 2012, 1:56:19 PM2/9/12
to java...@googlegroups.com

On Thursday, February 9, 2012 7:15:57 PM UTC+1, clay wrote:
Also, sure you can do some functional/immutable programming in C#, but
that's really not the strength of C# or a good choice for more serious
functional/immutable programming. Even if you prefer pure Microsoft
branded tech, F# is far better for that.

True, but C# truly caters to a hybrid approach, functional when you can, imperative when you must (along with static when you can, dynamic when you must).
 
You can also do functional/immutable style designs in Java. Not as
elegantly as you could in Scala/Haskell/Clojure/OCaml/F#, but my team
is doing exactly that.

Since Java does not support yield in lazy iterators (as C# does), how to you push/pop the state?

FYI, here is the Java code that I used: 

Pretty much identical to the code I wrote. :)

clay

unread,
Feb 9, 2012, 3:16:55 PM2/9/12
to The Java Posse
I stand corrected. I didn't see that before. People are supposed to be
initially skeptical about this kind of thing. Here is the link he is
referring to:

http://youtu.be/6RwrT6N43lY

On Feb 9, 11:49 am, Simon Ochsenreither

clay

unread,
Feb 9, 2012, 5:41:21 PM2/9/12
to The Java Posse
Java is missing many features. I'd think the biggest blatantly missing
feature is first class functions which people commonly, but
incorrectly, label as "closures", which is a separate feature that
Java actually does have (although purists argue that the final
requirement makes them not "pure" closures).

Nevertheless, you can stilly apply many functional programming
concepts and immutable logic with Java (or any language). We are using
the Functional Java library which helps.

Scala is the real imperative/functional hybrid language. You can code
completely imperative/OO/Java-style and you can code completely
functionally. C#, is ahead of Java in terms of functional type
features, but it is still primarily a imperative/OO language with some
functional features added on to it.


On Feb 9, 12:56 pm, Casper Bang <casper.b...@gmail.com> wrote:
> True, but C# truly caters to a hybrid approach, functional when you
> can, imperative when you must (along with static when you can, dynamic when
> you must).
>

Kevin Wright

unread,
Feb 9, 2012, 5:47:30 PM2/9/12
to java...@googlegroups.com
Bringing this back to the real world, did someone say imperative?  Lets try declarative for a change :)

import math._
val phi = (1+sqrt(5))/2.0d
def fib(n: Int) = round(pow(phi,n)/sqrt(5))

(0 to 10) map (fib)
// = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

I would have used BigDecimal for accuracy, but that would need me to use JScience or equivalent or roll my own pow, sqrt, and round functions - a bit overkill for such a simple example!

Rest assured that +, /, etc. work just fine for BigDecimals in Scala, and therein lies the real power of the language; the stuff that should be simple remains so, unhindered by boilerplate.

Kevin Wright

unread,
Feb 9, 2012, 6:00:18 PM2/9/12
to java...@googlegroups.com

2012/2/9 Cédric Beust ♔ <ced...@beust.com>


On Thu, Feb 9, 2012 at 9:49 AM, Kevin Wright <kev.lee...@gmail.com> wrote:
It's more of an issue with the JVM than it is with scala,

If this were true, then the Java version would be as slow as the Scala version, wouldn't it?

If it was false then an imperative version in Scala would be slower than an imperative version in Java, and a functional version that suffered boxing/unboxing in Java (using java 8 closures, lambdaj, or guava) would be blindingly fast.

That simply isn't the case...

 
If, like you say, the issue is with boxing, then it's clearly related to the way Scala does its boxing and it has nothing to do with the JVM.

Boxing is done by using Integer.valueOf() and related methods.  This is a facility provided by the platform and is nothing to do with Scala.

However, there are efforts underway to work around these limitations.  We already have specialisation that can avoid boxing in many cases (at the cost of larger classes with lots of overloading), this is one case where Scala goes against popular misconception and is the faster of the two languages.  There's also been some interesting discussion on the mailing lists recently about other ways to take such things even further.

 
-- 
Cédric


Ricky Clarkson

unread,
Feb 9, 2012, 6:10:37 PM2/9/12
to java...@googlegroups.com
Bear in mind that Fibonacci is Euler Problem 2.  He'll be doing things a lot more interesting for day-to-day programming (unless you churn out no-brainer webapps all day) if he gets to the later problems.  A couple of days ago I used some of my functional skills to trot out a parser that gives the number of parameters in a SQL stored procedure, in my day job, for a real though somewhat trivial problem.  It worked second time and was very easy to write.  All the code fits on one screen, it handles nested parentheses easily, and that's without even leaving Java. :)

(I forgot about -- single line comments, so it really worked third time, not second)
--
Skype: ricky_clarkson


--
You received this message because you are subscribed to the Google Groups "The Java Posse" group.
To post to this group, send email to java...@googlegroups.com.
To unsubscribe from this group, send email to javaposse+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.


Casper Bang

unread,
Feb 10, 2012, 12:05:34 AM2/10/12
to java...@googlegroups.com
On Thursday, February 9, 2012 11:47:30 PM UTC+1, KWright wrote:
Bringing this back to the real world, did someone say imperative?  Lets try declarative for a change :)

import math._
val phi = (1+sqrt(5))/2.0d
def fib(n: Int) = round(pow(phi,n)/sqrt(5))

(0 to 10) map (fib)
// = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

That also looks like a completely different algorithm. 
 
I would have used BigDecimal for accuracy, but that would need me to use JScience or equivalent or roll my own pow, sqrt, and round functions - a bit overkill for such a simple example!

Rest assured that +, /, etc. work just fine for BigDecimals in Scala, and therein lies the real power of the language; the stuff that should be simple remains so, unhindered by boilerplate.

Java is horribly stuck in legacy, it should've had a decimal (base 10) type ages ago, but I digress. What I don't understand is, if Scala suffers from runtime penalties approaching an order of magnitude for this simple problem, under which conditions does it start to pay off automagically? Perhaps the culprit here is that Fibonacci is inherently a linear/serial problem, so prime number factorization might be a better example?!

/Casper

clay

unread,
Feb 10, 2012, 1:02:45 AM2/10/12
to The Java Posse
If you want to calculate the nth term of the fibonacci sequence
without calculating all the preceding terms, the closed form solution
would be ideal. But for this problem, you actually want to walk the
full fibonacci sequence in order, so that really isn't appropriate.

Josh Berry

unread,
Feb 10, 2012, 1:08:29 AM2/10/12
to java...@googlegroups.com
On Fri, Feb 10, 2012 at 12:05 AM, Casper Bang <caspe...@gmail.com> wrote:
> Java is horribly stuck in legacy, it should've had a decimal (base 10) type
> ages ago, but I digress. What I don't understand is, if Scala suffers from
> runtime penalties approaching an order of magnitude for this simple problem,
> under which conditions does it start to pay off automagically? Perhaps the
> culprit here is that Fibonacci is inherently a linear/serial problem, so
> prime number factorization might be a better example?!

I think in this case the benefit of Scala is if you try and add a few
zeros to the max number you are looking at more than it is
performance. Changing the Scala code to work on BigInt level values
is trivial. Changing the Java is a pain in the neck. (Not
impossible, by any measure, just annoying.)

Also, I'm not entirely sure what you are aiming for in this. The
speed of both of these solutions is quite nice, by any measure. If
you are doing any "non-trivial" application you are most likely
hitting other bottlenecks than number crunching ability.

Kevin Wright

unread,
Feb 10, 2012, 2:50:40 AM2/10/12
to java...@googlegroups.com


On Friday, 10 February 2012, Casper Bang wrote:
On Thursday, February 9, 2012 11:47:30 PM UTC+1, KWright wrote:
Bringing this back to the real world, did someone say imperative?  Lets try declarative for a change :)

import math._
val phi = (1+sqrt(5))/2.0d
def fib(n: Int) = round(pow(phi,n)/sqrt(5))

(0 to 10) map (fib)
// = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

That also looks like a completely different algorithm. 
 

That was (at least partly) my point!  The Java/Scala solutions that have been discussed so far are *also* very different algorithms.

It's disingenuous to compare two different solutions in two different languages and then attribute any speed difference to the language used.  Comparing apples and oranges doesn't really help anyone.

Yes, the amenability of functions as a first-class concept in Scala can expose you to the cost of boxing, and this should be avoided in tight loops and performance sensitive code.  But used sensibly it can be very powerful in places where there *isn't* a performance bottleneck, such as the map operation in the last line of my example.

 
I would have used BigDecimal for accuracy, but that would need me to use JScience or equivalent or roll my own pow, sqrt, and round functions - a bit overkill for such a simple example!

Rest assured that +, /, etc. work just fine for BigDecimals in Scala, and therein lies the real power of the language; the stuff that should be simple remains so, unhindered by boilerplate.

Java is horribly stuck in legacy, it should've had a decimal (base 10) type ages ago, but I digress. What I don't understand is, if Scala suffers from runtime penalties approaching an order of magnitude for this simple problem, under which conditions does it start to pay off automagically? Perhaps the culprit here is that Fibonacci is inherently a linear/serial problem, so prime number factorization might be a better example?!

Indeed!  That would be a good candidate for a tail-recursive solution :)
 
/Casper




--
Kevin Wright
mail: kevin....@scalatechnology.com
gtalk / msn : kev.lee...@gmail.com
vibe / skype: kev.lee.wright
steam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

Reply all
Reply to author
Forward
0 new messages