Transcript Why Functional Programming Matters --- In an Object

Why Functional Programming
Matters --- In an Object-Oriented
World!
Matthias Felleisen
Rice University
What to Compare:
• Models of Computation
• Models of Programming
– Design
– Abstraction (Single Point of Control)
– Extensibility
• The Winner
• Lessons Learned
The Focus of OO and Functional Computation: Data
TAG
OO Computation:
manipulate data by sending
a message to an object and
waiting for an answer
FP Computation:
apply a primitive operation
to a piece of data
How can these two views possibly be related?
Two Simple Languages: FUN and OOPS
• FUN is (like ML/Scheme)
• OOPS is (like Java/Eiffel)
•
•
•
•
•
•
•
•
basic data: numbers ...
datatype
function definitions
expressions, including
– variables
– primitives: +, -, ...
– conditionals
– function application
– blocks
– assignment
basic data: numbers ...
class definitions, interfaces
method definitions
expressions, including
– variables
– primitives: +, -, …
– conditionals
– method application
– blocks
– assignment
Two Sample Programs (in lieu of Grammars):
datatype List = empty
| cons(first:int,rest:List)
add1*(l:List) =
case l of
empty : void;
cons :
l.first := l.first + 1;
add1*(l.rest)
end
interface List { add1* : -> void }
class Empty implements List {
void add1*() {}
}
class Cons(first:int, rest:List)
implements List {
void add1* () {
first := first+1;
rest.add1*(); }
}
The Computational Models
Given: a program
Wanted: a sequence of “states” that shows its behavior
A program is a
sequence of definitions
(datatype/functions or interface/classes)
an expression ( “main” )
A state is a program.
Definitions are Static, Expressions Capture the State:
Definitions :
Expression (Block)
the above let
definitions
x = new cons(1,empty)
for list,
in
cons,
x.first := 2
empty
end
Expression (Block)
let
x = new cons(2,empty)
in
void
end
Assumption: Definitions are well-formed according to
the rules of FUN and OOPS (scope, types, …)
Creating Data:
let
x=…
y=…
…
in
… new CC(x,BV) …
end
FUN Definitions:
datatype T = … CC(a:Ta, b:Tb) | ...
let
x=…
y=…
z = new CC(x,BV)
…
in
… z…
end
OOPS Definitions:
class CC(a:Ta, b:Tb) implements T {
…
}
Extracting Pieces:
let
x=…
y=…
z = new CC(x,BV)
…
in
… z.a …
end
FUN Definitions:
datatype T = … CC(a:Ta, b:Tb) | ...
let
x=…
y=…
z = new CC(x,BV)
…
in
… x…
end
OOPS Definitions:
class CC(a:Ta, b:Tb) implements T {
…
}
Mutating Data:
let
x=…
y=…
z = new CC(x,BV)
…
in
… z.a := y; …
end
FUN Definitions:
datatype T = … CC(a:Ta, b:Tb) | ...
let
x=…
y=…
z = new CC(y,BV)
…
in
… void …
end
OOPS Definitions:
class CC(a:Ta, b:Tb) implements T {
…
}
Calling Methods in OOPS:
let
x=…
y=…
z = new CC(x,BV)
…
in
… z. m(x,BV2)…
end
OOPS Definitions:
class CC(a:Ta, b:Tb) implements T {
…
T m(S s, U u) {
exp }
…
}
let
x=…
y=…
z = new CC(x,BV)
…
in
… exp [s=x,u=BV2,this=z]…
end
Example:
class CC(a:CC, b:int) implements T {
…
T m(CC s, U u) {
s.a := u; }
…
}
Calling Functions in FUN:
let
x=…
y=…
z = new CC(x,BV)
…
in
… m(z,x,BV2)…
end
FUN Definitions:
m(T t, S s, U u) = exp
let
x=…
y=…
z = new CC(x,BV)
…
in
… exp [t=z,s=x,u=BV2]…
end
Example:
m(CC t, CC s, int u) =
s.a := u
How about First-Class Functions?
let
x=…
y=…
…
in
… (lambda (x) exp)…
end
let
x=…
y=…
z = (lambda (x) exp)
…
in
… (z U) …
end
create
apply
let
x=…
y=…
z = (lambda (x) exp)
…
in
…z…
end
let
x=…
y=…
z = (lambda (x) exp)
…
in
… exp[z = U] …
end
How about Inheritance?
class A(X x, Y y) {
method1
method2
method3
}
class B(Z z) extends A {
method4
}
type elaboration
class A(X x, Y y) {
method1
method2
method3
}
class B(X x, Y y, Z z) {
method1
method2
method3
method4
}
How about Inheritance with Overriding?
class A(X x, Y y) {
method1
method2
method3
}
class B(Z z) extends A {
method1
method4
}
type elaboration
class A(X x, Y y) {
method1
method2
method3
}
class B(X x, Y y, Z z) {
method1
method2
method3
method4
}
Type Elaboration: The Global Picture
Object, Any
Class Derivation Path(s)
Models of Computation: Conclusion
• After type elaboration, the two pictures are nearly
indistinguishable
• In both models, creation, access, and mutation of
data proceeds in a coherent (“safe”) manner
• Tagged compound data are the essence of
computation -- the rest is terminology
The Focus of OO and Functional Computation: Data
method1
method2
function1
function2
method3
In OOPS, methods are
attached to data by a
physical link.
In FUN, functions are
attached to data by a
safety policy.
The effect: a completely safe treatment of data in both models
function2
Models of Programming
• What is a program
• How do people design programs in FUN, OOPS
– Data-driven designs
– Patterns
– How things relate
• How do people edit (“abstract”) and comprehend?
What is a Program?
Program
•
•
•
•
•
a batch-processing accounting software
an elevator controller (context: physical device)
a GUI with buttons and text fields and ... (context: monitor)
a space probe (context: devices, broadcast, …)
…
Designing Programs in a Data-Driven Fashion
• the shape of the program is determined by the
description of the class of input data
• flat: inexact numbers, chars, truth values, …
• compound: 2D 3D points, personnel records, …
• mixed: an animal is either a spider, an elephant, …
• arbitrarily large: a stack is either empty or a value
pushed onto a stack
Flat Data Collections: Numbers
3.141
1.0
.750
67857.
In FUN,
define a function.
In OOPS,
define a static method.
These things require domain knowledge and CS/SE isn’t going to help much.
Compound Data
An elephant has a name, an age, and a certain demand for space.
In FUN:
In OOPS:
datatype Elephant =
e of (name:String,
age:Number,
space: Number)
class Elephant (
name: String,
age: Number,
space: Number) {}
Compound Data and Programming
In FUN:
In OOPS:
datatype Elephant =
e of (name:String,
age:Number,
space: Number)
class Elephant (
name: String,
age: Number,
space: Number) {
fits_into(ele: Elephant,
cage_space: Number)
= ele.space < cage_space
}
fits_into(cage_space: Number) {
space < cage_space
In both cases, remember the available pieces!
Mixed Data (Union)
An animal is either (1) an elephant (2) a spider or (3) a monkey
In FUN:
In OOPS:
datatype Animal =
e of (name: String,
age: Number,
space: Number)
| s of (name: String, legs: Number)
| m of (name: String)
interface Animal {}
class Elephant (
name: String,
age: Number,
space: Number)
implements Animal {}
class Spider (name: String; legs: Number)
implements Animal {}
class Monkey(name:String)
implements Animal {}
Mixed Data and Programming
In FUN:
In OOPS:
datatype Animal =
e of (name: String,
age: Number,
space: Number)
| s of (name: String, legs: Number)
| m of (name: String)
interface Animal {
fits_into : Number -> Bool }
fits_into : Elephant Number -> Bool
fits_into(a: Animal, cage_sp: Number)
= case a of
e : a.space < cage_sp
s : true
m : false
class Elephant (
name: String,
age: Number,
space: Number) implements Animal {
fits_into(cage_sp: Number) {
space < cage_sp }
}
class Spider (name: String; legs: Number)
implements Animal {
fits_into(cage_sp: Number) {
true }
}
class Monkey(name:String)
implements Animal { … fits_into … }
Arbitrarily Large Data
A sequential file is either
(1) end of file
(2) a character followed by a sequential file.
A family tree is either
(1) empty
(2) a node consisting of a name, a family tree for the mother,
and a family tree for the father.
A directory has a name, a size, and a directory listing.
A directory listing is either
(1) empty
(2) a directory followed by directory listing
(3) a file followed by a directory listing
Arbitrarily Large Data and Data Definitions
In FUN:
In OOPS:
datatype FT = empty
| node (name: String,
father: FT,
mother: FT)
interface FT {}
class Empty implements FT {}
class Node(
name : String;
father : FT;
mother: FT)
implements FT {}
Arbitrarily Large Data and Programming
In FUN:
In OOPS:
datatype FT = empty
| node (name: String,
father: FT,
mother: FT)
interface FT {
depth: -> Number}
depth : FT -> number
depth(a_ft: FT) =
case a_ft of
empty: 0
node: depth(a_ft.father)
+
depth(a_ft.mother)
class Empty implements FT {
depth( ) { 0 }
}
class Node(
name : String;
father : FT;
mother: FT)
implements FT {
depth() {
father.depth() + mother.depth() }
}
Arbitrarily Large Data: the Interpreter Pattern
In FUN:
In OOPS:
layout data type definition
layout data type definition
one clause per variant
one clause per variant
deconstruct each variant
deconstruct (implicit)
use natural recursions
use natural recursions
dispatch via case
More Program Design: More Similarities
• mutually recursive data definitions
• parallel processing of arbitrarily large pieces of data
(multi-methods, parallel recursion)
• mutable data
– keeping track of “history”
– exchanging “history”
• concurrency/parallelism
• launching programs
– via batch
– via graphical interaction (modal or reactive)
– via devices
Launching Programs: Via Interaction
button
drop-down menu
Launching Programs: Via Interaction
In FUN:
In OOPS:
type Callback = Event GUI -> void
interface Callback {
execute : Event GUI -> void }
button1 : Callback
button1(e: Event, go : GUI) =
….
menu1 : Callback
menu1(e : Event, go : GUI) =
…
*** Menu(… menu1 …) ***
*** Button(… button1 …) ***
class Button1 ( ) implements Callback {
execute(e: Event, go : GUI) {
…. }
}
class Menu1 ( ) implements Callback {
execute(e : Event, go : GUI) {
…}
}
*** Menu(… Menu1( ) …) ***
*** Button(… Button1( ) …) ***
Launching Programs: the Command Pattern
• separate “view” from “model”
• store callback functions
– in FUN: use closures
– in OOPS: use instances of commands
(new ~ lambda, execute ~ apply)
• process data from GUI elements using methods
based on structural design, “history” design, ...
modal or reactive processing …
Abstraction (That’s not an UGLY word!)
• Abstracting is “editing”
• Abstracting means factoring out common pieces
• Abstracting helps maintaining code:
– need to comprehend code/invariant once
– fix errors once
– improve code once (algorithmic, style)
– add functionality once
• Abstracting affects the “bottom line”
• Software engineers: “single point of control”
Abstraction in FUN: Abstracting
F(a_list) =
case a_list of
empty :
cons:
a_list.first + F(a_list.rest)
SUM : list-of-numbers -> number
PI : list-of-numbers -> number
SUM(a_list) =
case a_list of
empty : 0
cons:
a_list.first + SUM(a_list.rest)
PI(a_list) =
case a_list of
empty : 1
cons:
a_list.first * PI(a_list.rest)
Abstraction in FUN: Specializing
MAKE : num (num num -> num) -> (list-of-numbers ->num)
MAKE(base, combine) =
let F(a_list) =
case a_list of
empty : base
cons: combine( a_list.first , F(a_list.rest))
in F
SUM : list-of-numbers -> number
PI : list-of-numbers -> number
SUM = MAKE(0,+)
PI = MAKE(1,*)
Abstraction in OOPS: Abstracting
abstract class Cart (x: double, y: double) {
}
bool closer_to(pt : Point) {
this.distance_to_O()
<=
pt.distance_to_O() }
class Cart (x: double, y: double) {
double distance_to_O() {
… something with square root
and squares of x and y … }
}
bool closer_to(pt : Point) {
this.distance_to_O()
<=
pt.distance_to_O() }
class Manhattan(x: double, y: double) {
double distance_to_O() {
… something with
x and y … }
}
bool closer_to(pt : Point) {
this.distance_to_O()
<=
pt.distance_to_O() }
Abstraction in OOPS: Specializing
abstract class PointA(x: double, y: double) {
abstract double distance_to_O()
}
bool closer_to(pt : Point) {
this.distance_to_O()
<=
pt.distance_to_O() }
class Cart (x: double, y: double)
extends PointA {
double distance_to_O() {
… something with square root
and squares of x and y … }
}
class Manhattan(x: double, y: double)
extends PointA {
double distance_to_O() {
… something with
x and y … }
}
Abstraction: Inheritance and the Template Pattern
• identify similar pieces of code, differences
• create abstraction
– in FUN: use higher-order function, application
– in OOPS: use inheritance, the Template pattern
• if most class extension use same hook, make it the
default and use overriding
Comprehending Code: Many Variants
An A-expression (A) is either
- a variable
- a numeric constant
- an addition: A + A
- a subtraction: A - A
- a multiplication: A * A
- a division: A / A
- an exponentiation: A ** A
- ...
A
x
5
+
-
*
/
**
…...
Comprehending Code: the Visitor Pattern
A
x
5
+
-
*
/
**
forfor+
for_num
for_var
…...
Comprehending Code: the Visitor Pattern vs Case
class A_Visitor(…) {
void for_variables(x: variable) …
void for_numbers(c: number) …
void for_plus(l: A, r: A) …
void for_minus(l: A, r: A) …
void for_times(l: A, r: A) …
void for_division(l: A, r: A) …
void for_exp(l: A, r: A) …
}
fun_for_A (x : A …) {
case x of
variable …
number …
plus …
minus …
times …
division …
exp …
}
Comprehension: Understanding “Functionality”
• collect those pieces of code that perform a function
• create body of code
– in FUN: functions and case do it naturally
– in OOPS: use call-forwarding and the
Visitor pattern
Black Box Extensibility: Adding Variants
An A-expression (A) is either
- a variable
- a numeric constant
- an addition: A + A
- a subtraction: A - A
- a multiplication: A * A
- a division: A / A
- an exponentiation: A ** A
And here are more A-expressions:
-- a sin-expression: sin(A)
A
x
5
+
-
*
/
**
sin
Black Box Extensibility: Adding or Modifying Functionality
An A-expression (A) is either
- a variable
- a numeric constant
- an addition: A + A
- a subtraction: A - A
- a multiplication: A * A
- a division: A / A
- an exponentiation: A ** A
We may want more methods than
the original product provides or we
may wish slightly different functionality.
A
x
5
+
-
*
/
**
sin
x
5
+
-
*
/
**
sin
Black Box Extensibility: More Cases
• what if we want visitors?
Krishnamurthi, Felleisen & Friedman ECOOP 98
• what if we have modules?
Flatt & Findler ICFP 98
• is it useful?
Kathi Bohrer (IBM) San Francisco Project
SYSTEMS Journal 97
Extensibility in the Functional World
• adding functions to a “black box” -- easy
• adding new variants to a “black box” -- difficult
• fake OO programming with protocols:
Krishnamurthi and Felleisen FSE98
Hudak and Liang POPL 95
Felleisen and Cartwright TACS 94
Steele POPL94
The Winner: What’s better and Why?
The Winner: A Comparison
FUN:
• a data-centered, safe model
of computation
• a data-centered model of
program design
• a rich “theory of programs”
OOPS:
• a data-centered, safe model
of computation
• a data-centered model of
program design
• a rich “practice of patterns”
but the amazing surprise: the “theory” and the “practice”
lead to nearly indistinguishable programs:
- data layout induces program layout
- iteration patterns or iterator functions
- few (true) assignments to reflect “real world” changes
(history or state)
- objects as “multi-bodied, multi-entry” closures
The Winner: Default Functionality
Your web server has 27 different parameters that can be tuned …
How do you tune them?
FUN:
• functions with many
parameters
• Fortran: entry points
• Common LISP: by-keyword
• Scheme: rest arguments
• Chez: case-lambda
• … but there is also Currying
OOPS:
• classes with many default
methods and instance
variables
• derived classes that override
just those few that need to
be modified
The Winner: Extensible Products
Your product should accommodate 435 business strategies in 47 countries ….
How do you accommodate them all?
FUN:
• complex programming
protocols
• problem with standard types
• … soft-typing works just fine
OOPS:
• default strategies
• extensibility patterns (hooks)
• derived classes that override
just those strategies that
need to be modified
The Winner: There isn’t One
• OOPS and FUN are equivalent for many situations
• FUN has a much richer theory
• OOPS provides the practical examples
More Comparisons:
• FUN
– has “lambda”, which
means it is simpler to
abstract
– functions are easier to
comprehend
– has “currying”, which
makes up for the shortcomings on extensibility
• Scheme has macros
• OOPS
– can accommodate many
defaults easily
– is good for producing
extensible systems
– lacks “functions” and
demands visitors
So What? How does this Help?
• programming: design, reasoning about programs
• language research: theory and implementation
• education: what to teach and how to teach it
Programming and Program Engineering
• pattern mining:
functional programmers have contemplated the
meta-level for much longer than oo programmers
• logic mining:
programming in a functional style facilitates
reasoning about programs; it is easy and natural to
program “functionally” in an oo language
Language Research
• type theory: parametric polymorphism, modules
• program analysis: abstract interpretation
• implementation: closures are simple objects,
functional programming environments are
semantically more sophisticated than OO
environments (repl, module managers)
Education: FUN first, OOPS later!
• functional programming is syntactically simpler than
object-oriented programming
• functional programming is more natural than objectoriented programming: append(list1,list2) versus
list1.append(list2)
• functional programming is traditionally more
interactive than object-oriented programming (repl)
Summary
• functional programming and object-oriented
programming are closely related
• their differences should lead to important synergies
• Let us take a closer look!
Thank You
Corky Cartwright
Dan Friedman
Matthew Flatt
Shriram Krishnamurthi
Robby Findler
Kim Bruce
Bob Harper
Ralph Johnson
Scott Smith
Phil Wadler