Transcript presentation - Computer and Information Science

Multiparadigm Programming
in Scala
H. Conrad Cunningham
James C. Church
Computer and Information Science
University of Mississippi
What is Multiparadigm
Programming?
Definition:
A multiparadigm programming language provides
“a framework in which programmers can work in a
variety of styles, freely intermixing constructs from
different paradigms.” [Tim Budd]
Programming paradigms:


imperative versus declarative (e.g., functional, logic)
other dimensions – object-oriented, component-oriented,
concurrency-oriented, language-oriented
4 April 2009
2
Why Learn Multiparadigm
Programming?
Tim Budd:
“Research results from the psychology of
programming indicate that expertise in
programming is far more strongly related to the
number of different programming styles
understood by an individual than it is the number
of years’ experience in programming.”
The “goal of multiparadigm computing is to
provide ... a number of different problem-solving
styles” so that a programmer can “select a solution
technique that best matches the characteristics of
the problem to be solved”.
4 April 2009
3
Why Teach Multiparadigm
Programming?

Contemporary imperative and object-oriented
languages increasingly have functional
programming features, e.g.,
•
•

higher order functions (closures)
list comprehensions
New explicitly multiparadigm (objectoriented/functional) languages are appearing, e.g.,
•
•
Scala on the Java platform (and .Net in future)
F# on the .Net platform
4 April 2009
4
Scala
Programming language developed by Martin Odersky’s
team at EPFL in Switzerland
 Executes on the Java platform
 Integrates with Java
 Has growing usage (e.g., twitter.com)
Multiparadigm language
 Object-oriented (with generics and mixins)
 Functional (similar to Haskell and SML)
 Extensible (method calls as operators, currying, closures,
by-name parameters)
•
•

Actor-based concurrency-oriented programming
Language-oriented programming
Statically typed with Hindley-Milner type inference
4 April 2009
5
Scala References

Website http://www.scala-lang.org
•
•

Martin Odersky. Scala Tutorial for Java Programmers.
Martin Odersky. Scala By Example.
Martin Odersky, Lex Spoon, and Bill Venners.
Programming in Scala: A Comprehensive StepBy-Step Guide, Artima, Inc., 2009.

Books from Apress and Pragmatic Bookshelf in
May, O’Reilly in August, Cambridge late 2009
4 April 2009
6
Defining Hello World
object HelloWorld { // Mississippi version
def main(args: Array[String]){
println("Hey world!")
}
}




Singleton object named HelloWorld (also replaces
static methods and variables)
Method main defined (procedure)
Parameter args of type Array[String]
Array is generic class with type parameter
4 April 2009
7
Interpreting Hello World
> scala
This is a Scala shell.
Type in expressions to have them evaluated.
Type :help for more information.
scala> object HelloWorld {
| def main(args: Array[String]) {
|
println("Hey world!")
| }
|}
defined module HelloWorld
scala> HelloWorld.main(null)
Hey world!
unnamed0: Unit = ()
scala>:q
4 April 2009
8
Compiling & Executing Hello World
> scalac HelloWorld.scala
> scala HelloWorld
Hey world!
4 April 2009
9
Numbers are Objects

Consider expression 1 + 2 * 3 / x

Operators are method calls (like Smalltalk)

Operator symbols are identifiers

Expression above is same as
(1).+(((2).*(3))./(x))
4 April 2009
10
Functions are Objects
object Timer {
def oncePerSecond(callback:() => Unit){
while (true) {
callback(); Thread sleep 1000
} // 1-arg method sleep used as operator
}
def welcome() {
println("Welcome to CCSC:MS!")
}
def main(args: Array[String]) {
oncePerSecond(welcome)
}
}
4 April 2009
11
Timer Execution
scala> :l Timer.scala
Loading Timer.scala...
defined module Timer
scala> Timer.main(null)
Welcome to CCSC:MS!
Welcome to CCSC:MS!
Welcome to CCSC:MS!
…
4 April 2009
12
Anonymous Functions
object Timer {
def oncePerSecond(callback:() => Unit){
while (true) {
callback(); Thread sleep 1000
}
}
def main(args: Array[String]) {
oncePerSecond(
() => println("Welcome to CCSC:MS!") )
}
}
4 April 2009
13
Classes
class Complex(real: Double, imag: Double){
def re = real
def im = imag
}





Class primary constructor combined with class body
Parameters of class private constants within class
Parameterless methods re and im
Return types of re and im inferred from expression
(cannot be inferred for recursive functions)
Thus more concise syntax
4 April 2009
14
Method Overriding
// Complex.scala
class Complex(real: Double, imag: Double) {
def re = real
def im = imag
override def toString =
re + (if (im < 0.0) "" else "+") +
im + "i“
}



Classes extend class AnyRef by default
Methods must explicitly override parent method
if expressions
4 April 2009
15
Using Classes and Objects
scala> :load Complex.scala
Loading Complex.scala...
defined class Complex
scala> val x = new Complex(1,-3)
x: Complex = 1.0-3.0i
scala> x.toString
res0: java.lang.String = 1.0-3.0i
4 April 2009
16
Case Classes
abstract class Tree // Expression Trees
case class Sum(l: Tree, r: Tree)
extends Tree
case class Var(n: String) extends Tree
case class Const(v: int) extends Tree





Algebraic data types as in functional languages
Keyword new not needed to create instances (objects)
Getters defined automatically for constructor parameters
equals method defined on structure of instances
Pattern matching can be used to decompose
4 April 2009
17
Pattern Matching
object Expressions {
type Environ = String => Int
def eval(t: Tree, env: Environ): Int = t match {
case Sum(l,r) => eval(l,env) + eval(r,env)
case Var(n)
=> env(n)
case Const(v) => v
}
def derive(t: Tree, v: String): Tree = t match {
case Sum(l,r)
=> Sum(derive(l,v),
derive(r,v))
case Var(n) if (v == n) => Const(1)
case _
=> Const(0)
}
4 April 2009
18
Test Expression Trees
def main(args: Array[String]) {
val exp: Tree =
Sum(Sum(Var("x"),Var("x")),
Sum(Const(7),Var("y")))
val env: Environ =
{ case "x" => 5 case "y" => 7 }
println("Expression: " + exp)
println("Evaluation with x=5, y=7: " +
eval(exp,env))
println("Derivative relative to x:\n " +
derive(exp, "x"))
println("Derivative relative to y:\n " +
derive(exp, "y"))
}
}
4 April 2009
19
Execute Expression Trees
scala> :load Expressions.scala
Loading Expressions.scala...
…
scala> Expressions.main(null)
Expression:
Sum(Sum(Var(x),Var(x)),Sum(Const(7),Var(y)))
Evaluation with x=5, y=7: 24
Derivative relative to x:
Sum(Sum(Const(1),Const(1)),Sum(Const(0),Const(0)))
Derivative relative to y:
Sum(Sum(Const(0),Const(0)),Sum(Const(0),Const(1)))
4 April 2009
20
Defs, Vals, and Vars
Three types of identifier definitions
def defines functions with parameters; RHS
expression evaluated each time called
val defines unchanging values; RHS expression
evaluated immediately to initialize
var defines storage location whose values can be
changed by assignment statements; RHS
expression evaluated immediately to initialize
4 April 2009
21
Traits
trait Ord { // Order comparison operators
def < (that: Any): Boolean // abstract
def <=(that: Any): Boolean =
(this < that) || (this == that)
def > (that: Any): Boolean =
!(this <= that)
def >=(that: Any): Boolean =
!(this < that)
}
 Like Java interfaces except can have concrete methods
 Can be “mixed-in” to class
 Note < abstract; others defined with < and equals
4 April 2009
22
Date Class with Mixin Trait Ord
class Date(y: Int, m: Int, d: Int)
extends Ord {
def year = y
def month = m
def day
= d
override def toString(): String =
year + "-" + month + "-" + day
// need definition of < and equals
}


Can only extend only one class or trait
May mix-in additional classes using keyword with
4 April 2009
23
Date Class Equals Method
override def equals(that: Any): Boolean =
that.isInstanceOf[Date] && {
val o = that.asInstanceOf[Date]
o.day == day && o.month == month &&
o.year == year
}



isInstanceOf[T] checks whether object is an instance
of the given type T
asInstanceOf[T] casts static type to T if compatible
with dynamic type of object
Value of last statement of function is returned
4 April 2009
24
Date Class < Method
def <(that: Any): Boolean = {
if (!that.isInstanceOf[Date])
error("Cannot compare " + that +
" and a Date")
val o = that.asInstanceOf[Date]
(year < o.year) ||
(year == o.year &&
(month < o.month ||
(month == o.month && day < o.day)))
}
4 April 2009
25
DateTest
object DateTest {
def main(args: Array[String]) {
val x = new Date(1,1,2000)
val y = new Date(12,31,2001)
println("x = " + x)
println("y = " + y)
println("x < y: " + (x<y))
println("x > y: " + (x>y))
}
}
4 April 2009
26
DateTest Output
>
x
y
x
x
scala DateTest
= 1-1-2000
= 12-31-2001
< y: true
> y: false
4 April 2009
27
Scala Functions






Are first-class values – i.e., functions are objects
Can be higher-order – take functions as arguments
or return them as result
Can be anonymous
May be curried – take arguments one at a time,
allowing partial application
Are often passed in a closure – with references to
free variables they maninpulate
Provide ability to build powerful libraries of
higher-order functions
4 April 2009
28
Curried Functions
scala> def add(x: Int, y: Int) = x + y
add: (Int,Int)Int
scala> add(1,3)
res0: Int = 4
scala> def addc(x: Int)(y: Int) = x + y
addc: (Int)(Int)Int
scala> addc(1)(3)
res1: Int = 4
4 April 2009
29
Partial Application
scala> def addc(x: Int)(y: Int) = x + y
addc: (Int)(Int)Int
scala> val z = addc(1) _
z: (Int) => Int = <function>
scala> z(3)
res2: Int = 4
4 April 2009
30
Closures
scala> val inc = 10
inc: Int = 10
scala> def incre(x: Int) = x + inc
incre: (Int)Int
scala> def app(y: Int, g: (Int=>Int)) = g(y)
app: (Int,(Int) => Int)Int
scala> app(13,incre)
res0: Int = 23
4 April 2009
31
List Processing
// Not actual Scala API code
abstract class List[+A]{ …
def map[B](f: (A)=> B): List[B] =
this match {
case Nil
=> this
case x::xs => f(x)::xs.map(f)
}
…
}
case object Nil extends List[Nothing]
case final class ::[B]
(private hd: B, val tl: List[B])
extends List[B]
4 April 2009
32
Using List Map
scala> val xs = List(3,4,5)
xs: List[Int] = List(3, 4, 5)
scala> val triples = xs.map(x => 3*x)
triples: List[Int] = List(9, 12, 15)
4 April 2009
33
More List Processing
// Not actual Scala API code
abstract class List[+A]{ …
def filter(p: (A) => Boolean): List[A] =
this match {
case Nil
=> this
case x::xs =>
if (p(x)) x::xs.filter(p)
else xs.filter(p)
}
…
}
4 April 2009
34
Using List Filter
scala> val xs = List(3,4,5,6)
xs: List[Int] = List(3, 4, 5, 6)
scala> val evens = xs.filter(x => x%2==0)
evens: List[Int] = List(4, 6)
4 April 2009
35
Other Higher Order List Methods

flatMap

foldLeft, foldRight

reduceLeft, reduceRight

takeWhile, dropWhile

span, break

foreach
4 April 2009
36
For Comprehensions
scala> for(i <- 1 to 30;
|
j <- List(2,3,5,7);
|
if i % j == 0) yield (i,j)
res0: Seq.Projection[(Int, Int)] =
RangeG((2,2), (3,3), (4,2), (5,5), (6,2),
(6,3), (7,7), (8,2), (9,3), (10,2),
(10,5), (12,2), (12,3), (14,2), (14,7),
(15,3), (15,5), (16,2), (18,2), (18,3),
(20,2), (20,5), (21,3), (21,7), (22,2),
(24,2), (24,3), (25,5), (26,2), (27,3),
(28,2), (28,7), (30,2), (30,3), (30,5))
4 April 2009
37
Actors in Scala
4 April 2009
38
Motivation



Concurrency is hard!
Real World is parallel and distributed.
Erlang's notion of a process:



Concurrent processes should pass messages to other
processes rather than share memory.
Erlang's processes are part of the language.
Scala's actors are part of the library.
4 April 2009
39
Actors




Actors act independent of other actors.
Actors have mailboxes.
Actors communicate by sending messages to
other actors.
Actors will check their mailbox and react to their
messages.
4 April 2009
40
Message in a Bottle

Any object can be sent to an Actor
case object myMessageObject
...
myActor ! myMessageObject
4 April 2009
41
Please Mr. Postman

How urgent is it?
react: I need it now!
 receiveWithin: I need it soon!
 receive: I'll wait.


All three methods will perform pattern matching
on the objects received.
4 April 2009
42
Overacting
import scala.actors._
object SillyActor extends Actor {
def act() { // Defines how our actor acts
for (i <- 1 to 5) {
println(“I'm acting!”)
Thread.sleep(1000)
}
}
}
...
SillyActor.start() // Begins acting
4 April 2009
43
Vegetable Launcher
case object Tomato
case object Lettuce
object VegetableLauncher extends Actor {
def act() {
for (i <- 1 to 5) {
VegetableCatcher ! Tomato
// Send it!
Thread.sleep(1000)
VegetableCatcher ! Lettuce // Send it!
Thread.sleep(1000)
}
}
}
4 April 2009
44
Vegetable Catcher
object VegetableCatcher extends Actor {
def act() {
loop {
react { // Non-blocking call
// Pattern Matching
case Lettuce =>
println(“I caught a lettuce!”)
case Tomato =>
println(“I caught a tomato!”)
}
}
}
}
4 April 2009
45
Lights, Camera, ...
VegtableLauncher.start()
VegtableCatcher.start()
SillyActor.start()
I'm acting!
I caught a tomato!
I'm acting!
I caught a lettuce!
I'm acting!
I caught a tomato!
I'm acting!
I caught a lettuce!
I'm acting!
I caught a tomato!
I caught a lettuce!
I caught a tomato!
I caught a lettuce!
I caught a tomato!
I caught a lettuce!
4 April 2009
46
Dining Philosophers




Five philosophers compete for limited resources.
Deadlocks are possible.
Solution implemented with a waiter.
11 actors total:
5 philosophers
 5 chopsticks (A mutex actor)
 1 waiter (A singleton object actor)

4 April 2009
47


The waiter only allows four to sit. After that,
names are on the wait list.
Philosophers must still wait for chopsticks after
sitting.
4 April 2009
48
Six Messages
import scala.actors._
import scala.actors.Actor._
import java.util.Random
// Philosopher and Waiter communication
case object NeedToEat
case object HaveASeat
case object DoneEating
// Philosopher and Chopstick communication
case object NeedChopstick
case object HeresAChopstick
case object GiveBackChopstick
4 April 2009
49
Chopstick “Mutex”
class Chopstick extends Actor {
def act() {
loop {
react {
case NeedChopstick =>
sender ! HeresAChopstick
receive {
case GiveBackChopstick =>
1
}
}
}
}
}
4 April 2009
50