Transcript The Presentation

Intro to Functional
Programming in Scala
Joe Barnes
Senior Software Architect
System Design Division
October, 2013
Overview

Trends in software influencing the popularity

What is different about the paradigm?

How do I apply it?

More about Scala in particular
© 2013 Mentor Graphics Corp.
2
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Monad tutorial trend

In functional programming, a monad is a structure that
represents computations defined as sequences of steps.1

The number of monad tutorials has exploded in the past
10 years.
2
1Source:
2Source:
Wikipedia | Monad (functional programming)
Haskell.org | Monad tutorials timeline
© 2013 Mentor Graphics Corp.
3
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Moore’s Law

Moore's law is the observation that, over the history of
computing hardware, the speed of integrated
circuits doubles approximately every two years.

Moore's law is the observation that, over the history of
computing hardware, the number of transistors on
integrated circuits doubles approximately every two
years.

In fact, we’re no longer getting faster…
© 2013 Mentor Graphics Corp.
4
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Moore’s Law
Source: Herb Sutter | The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
© 2013 Mentor Graphics Corp.
5
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
The free lunch is over!
“ Instead of driving clock speeds and straight-line instruction
throughput ever higher, they are instead turning en masse to
hyperthreading and multicore architectures”
“Applications will increasingly need to be concurrent if they
want to fully exploit continuing exponential CPU throughput
gains”
“The vast majority of programmers today don’t grok
concurrency, just as the vast majority of programmers [25]
years ago didn’t yet grok objects”
Source: Herb Sutter | The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
© 2013 Mentor Graphics Corp.
6
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
As Jimmy McMillan would say…
CONCURRENCY
IS TOO DAMN HARD!!!
Source: http://www.troll.me/images/rent-is-too-damn-high/rent-is-too-damn-high.jpg
© 2013 Mentor Graphics Corp.
7
Your Initials, Presentation Title, Month Year
www.mentor.com
Company Confidential
Why is concurrency hard?
“The programmer must ensure read and write access to
objects is properly coordinated (or "synchronized") between
threads.”
- Java Concurrency | Wikipedia
“C++ has been designed for single thread programming, and
parallel programming requires a revolutionary rather than
evolutionary change. Two words: data races.”
- Bartosz Milewski
Source: Java Concurrency | Wikipedia
Source: Edward C++Hands | Bartosz Milewski
© 2013 Mentor Graphics Corp.
8
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Data races: The recipe
A data race occurs when two concurrent threads access a
shared variable and when
 at least one access is a write and
 the threads use no explicit mechanism to prevent the
accesses from being simultaneous.
Restated:
1.
Two concurrent threads
2.
At least one write
3.
Mechanism not used
Here to stay
Hmm…
Programmer error. Also here to stay
Source: Eraser: A Dynamic Data Race Detector for Multithreaded Programs | STEFAN SAVAGE, et al
© 2013 Mentor Graphics Corp.
9
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
We Want You
To Stop Using Variables
Source: Some random link via Google image search
© 2013 Mentor Graphics Corp.
10
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Revoke My Writes?!

1968 – Structured Programming
— Edsger Dijkstra writes “Go To Statement Considered Harmful”
— Revoked GoTo

1966 – Object Oriented Programming
— Ole-Johan Dahl and Kristen Nygaard create Simula 67
— Revoked function pointers

1957 – Functional Programming
— John McCarthy creates Lisp
— Revoked reassignment of variables values
Source: Three Paradigms | Uncle Bob @ 8th Light
© 2013 Mentor Graphics Corp.
11
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Two timelines
“Higher”
Levels
Theory
To
Practice
Source: Several random links via Google image search
© 2013 Mentor Graphics Corp.
12
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Dichotomies

Von Neumann vs. Lambda Calculus
— Manipulation of program state vs. Evaluation of mathematical
formulas

Object-oriented vs. Functional?
— False dichotomy per Martin Odersky (BDFL of Scala).
— Object-orientation and functional are perpendicular.
— Scala is both.

Imperative vs. Functional
— The dichotomy defined along the assignment axis.
© 2013 Mentor Graphics Corp.
13
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
That’s right. You have no writes.
ALL YOUR WRITES
ARE BELONG TO US!
© 2013 Mentor Graphics Corp.
14
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
How can we program this way?

Back to school…
What is a function?
© 2013 Mentor Graphics Corp.
15
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Function

Given a set S and a set T, a function f is a set of ordered
pairs taken from S ×T where each s from S appears exactly
once in f.

Given (s, t) ∈ f, we denote f(s) = t. f is said to “map s to t.”

Functions a.k.a. “mappings”

Given s ∈ S, f(s) is a defined value also known as t.

Can substitute the expression f(s) with t
— Referential Transparency!
© 2013 Mentor Graphics Corp.
16
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Function (visual)
T
S
A
1
B
2
3
4
5
f
C
D
E
F
f = { (1,D), (2,F), (3,A), (4,F), (5,C) }
f (1)  D, f (2)  F, f (3)  A, …
Identify any mutable state.
© 2013 Mentor Graphics Corp.
17
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Programming with only functions (Bash)

OK, so how do we program with functions?
$ find . -name *.java | xargs grep -l "function" | wc –l

Notice this script/program doesn’t have mutable state
© 2013 Mentor Graphics Corp.
18
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Programming with only functions (Excel)
Date
Station
4/23/2012 Sam's
5/4/2012 Shell
5/15/2012 Sam's
5/25/2012 Shell
6/1/2012 Chevron
6/11/2012 Shell
6/22/2012 Shell
7/10/2012 BP
7/26/2012 BP
8/5/2012 Chevron
8/5/2012 Chevron
8/20/2012 Chevron
8/31/2012 Shell
9/7/2012 Chevron
9/13/2012 Sam's
9/23/2012 Chevron
10/3/2012 Sam's
11/2/2012 Shell
11/19/2012 Sam's
12/10/2012 Sam's
12/27/2012 BP
Odometer Gallons Dollars
MPG
MPD
158907 11.098 $40.50
159165 19.742 $75.00
13.07
3.44
159329 11.407 $39.00
14.38
4.21
159601 17.226 $62.00
15.79
4.39
159790 12.289 $43.00
15.38
4.4
160146
22.36
$76.00
15.92
4.68
=
DIVIDE(SUM(-C2,
C3),D3)
160481 21.521 $71.00
15.57
4.72
160807 21.847 $67.51
14.92
4.83
161129 20.439 $66.00
15.75
4.88
18.005 $63.00
13.33 159165),19.742)
3.81
=161369
DIVIDE(SUM(-158907,
161560 10.861 $38.00
17.59
5.03
161856 20.962 $75.44
14.12
3.92
162122
18.09 $68.00
14.7
3.91
162282 11.971 $45.00
13.37
3.56
162432
7.726 $27.50
19.41
5.45
162611 13.833 $52.00
12.94
3.44
162884 18.232 $63.25
14.97
4.32
163181 19.863 $69.50= 13.07
14.95
4.27
163485 20.389 $64.00
14.91
4.75
163834 19.361 $60.00
18.03
5.82
164157 22.272 $71.25
14.5
4.53
fx
= DIVIDE(258,19.742)
© 2013 Mentor Graphics Corp.
19
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Referential Transparency

Find the roots/zeros of the equation ax 2 + bx + c.
object Math {
def roots(a:Double, b:Double, c:Double) = {
val discriminant = sqrt(b*b - 4*a*c)
val root1 = (-b - discriminant) / (2*a)
val root2 = (-b + discriminant) / (2*a)
(root1, root2)
}
}
© 2013 Mentor Graphics Corp.
20
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Partial ordering of evaluation
a
b
c
discriminant
root1
root2
Can run in parallel!
(root1, root2)
© 2013 Mentor Graphics Corp.
21
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Yeah, but sometimes we need variables

Produce the first 25 even natural numbers.
public class EvensJava {
public static List<Integer> first25() {
List<Integer> squares = new ArrayList<Integer>();
for(int i=1; i<=25; i++)
squares.add(i*2);
}
}
© 2013 Mentor Graphics Corp.
22
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Squares without variables: Scala
object EvensScala extends App {
val first25 = (1 to 25).map { i => i*2 }
}
object EvensScala extends App {
val first25 = (1 to 25).map(_*2)
}
object EvensScala extends App {
val first25 = (1 to 25).par.map(_*2)
}
© 2013 Mentor Graphics Corp.
23
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Calculate factorial: Java
public class FactorialJava {
public int looped(int n) {
if(n < 0) throw new IllegalArgumentException("n < 0");
int factorial = 1;
for(int i=1; i<=n; i++)
factorial *= i;
return factorial;
}
public int recursive(final int n) {
if(n < 0) throw new IllegalArgumentException("n < 0");
if(n <= 1) return 1;
else return n * recursive(n-1);
}
}
© 2013 Mentor Graphics Corp.
24
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Calculate factorial: Scala
class FactorialScala {
def recursive(n:Int):Int = {
require(n >= 0, "n < 0")
if(n <= 1) 1
else n * recursive(n-1)
}
def reduced(n:Int):Int = {
require(n >= 0, "n < 0")
(1 to n).reduceLeftOption(_ * _).getOrElse(1)
}
}
© 2013 Mentor Graphics Corp.
25
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
First n primes: Java
public class PrimesJava {
public List<Integer> first(int n) {
List<Integer> primes = new LinkedList<Integer>();
for(int i=2; primes.size() < n; i++) {
if(isPrime(i)) primes.add(i);
}
return primes;
}
public boolean isPrime(int n) {
boolean isPrime = true;
for(int i=2; i<n; i++) {
if(n % i == 0) {
isPrime = false;
break;
}
}
return isPrime;
}
}
26
© 2013 Mentor Graphics Corp.
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
First n primes: Scala
class PrimesScala {
def isPrime(n:Int) =
(2 to (n-1)).forall {
i => n % i != 0
}
def first(n:Int) = Stream.from(2).
filter(isPrime(_)).take(n)
}
© 2013 Mentor Graphics Corp.
27
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Persistent data structures
class Prepend extends FunSuite {
test("Prepend produces new instance") {
val oneTo3
= List(1, 2, 3)
val zeroTo3 = 0 +: oneTo3
assert(oneTo3.size
== 3)
assert(zeroTo3.size == 4)
assert(oneTo3 != zeroTo3)
}
}
© 2013 Mentor Graphics Corp.
28
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
But isn’t that inefficient??
val oneTo3
= List(1, 2, 3)
oneTo3
0
1
2
3
zeroTo3
val zeroTo3 = 0 +: oneTo3
© 2013 Mentor Graphics Corp.
29
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
So why Scala?

Compiles to plain-ol’ JVM byte code
— Fully interoperable with Java
— Leverage solid existing Java technologies
— Platform-independent

Multi-paradigm
— Arguably more OO than Java
–
–
–
–
No primitives
No static
Multiple inheritance
Even functions are objects!
— Idiomatically functional, but not strictly
– Can declare a var
— Be productively quickly, learn new paradigm gradually
© 2013 Mentor Graphics Corp.
30
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
So why Scala, continued…
Statically-typed with dynamically-typed syntax features

—
—
—
—
—
Richer type system than Java (Turing complete)
Type inference
Implicit conversions
Pattern matching
Malleable syntax allows domain-specific languages (DSL)
All of the aforementioned advantages of functional
programming

— Multi-processor scaling
High-productivity

— Dynamically-typed syntax features
— Typically takes one half to one third of the lines of code as Java1
1Source:
Research: Programming Style and Productivity | scala-lang.org
© 2013 Mentor Graphics Corp.
31
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Yay! The world’s problems solved!

No backwards compatibility across major releases
— Ex. Scala 2.9.x byte code incompatible with 2.10.x byte code
— Have to find and possibly recompile libraries to advance
— Deprecated features get obsoleted

Compiler slower than Java
— Does MUCH more for the developer than Java (see type system)
— Defacto build tool (sbt) keeps compiler in memory which helps

Less mature
— Tooling isn’t as stable
© 2013 Mentor Graphics Corp.
32
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Java/Scala timeline

1995 – Java 1.0 released by Sun.

1995 – Odersky begins work on OO/FP language targeting
the JVM. Efforts eventually lead to Java 1.5’s generics.

2001 – Odersky begins Scala from scratch due to
restrictions imposed by Java.

2003 – First release of Scala

2004 – Java 5.0 released

2006 – Scala 2 released

2011 – Typesafe launched to provide commercial support,
training, services for Scala.

2011 – Java 7 released; JVM includes InvokeDynamic.
Source: A Brief History of Scala | Martin Odersky
Source: Scala (programming language) | Wikipedia
© 2013 Mentor Graphics Corp.
33
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Scala sounds nice, but does it work?
Twitter used Scala to kill the fail whale!
Source: The Secret Behind Twitter’s Growth | MIT Technology Review
© 2013 Mentor Graphics Corp.
34
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Adoption
Source: Sneaking Scala Through the Back Door | Dianne Marsh
© 2013 Mentor Graphics Corp.
35
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Scala at Mentor Graphics?

Scala is NOT hereby endorsed by Mentor Graphics or
System Design Division for use in production code.

Adoption of Scala in production code is a division-level
decision.
© 2013 Mentor Graphics Corp.
36
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Where might Scala fit, then?

Find problems where Scala is a great fit
— Web applications
– Application state belongs in the DB.
— Static typing
– Consumption of generated code, such as SOAP calls
– Slow-running I/O-bound processes, such as building
– Anywhere compiler checking can detect changes in dependencies
— Domain-specific languages
– Any time you want code to read fluidly

Utilize Scala in non-production/controlled environments
— Hosted web applications
— Internal applications
— Testing
© 2013 Mentor Graphics Corp.
37
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Testing DSL example
"The dashboard" should {
"filter journal when searching" in {
search "Knees to elbows"
eventually { entries.size should be (1) }
Entry(1).title should be (workout2.title)
click on Entry(1).resultBtn
eventually { Entry(1).notes should be ("I completed the workout!") }
}
}
© 2013 Mentor Graphics Corp.
38
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
Taking the next step

Free online course!
— Functional Programming Principles in Scala
— Taught by Martin Odersky himself

Join the Scala User Group

Join the Scala Enthusiasts group on LinkedIn

Reference the Scala API

Ask questions at StackOverflow

Email me [email protected]
— User group?

Read my Scala ramblings
Image: Kool Aid Guy Wreaks Havoc at Presbyterian Seminary
© 2013 Mentor Graphics Corp.
39
JDB, Intro to Functional Programming in Scala, October 2013
www.mentor.com
Company Confidential
QUESTIONS?
© 2013 Mentor Graphics Corp.
www.mentor.com
Company Confidential