fp oop

Why Functional Programming Matters --- In an Object-Oriented World!: 

Why Functional Programming Matters --- In an Object-Oriented World! Matthias Felleisen Rice University

What to Compare:: 

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: 

The Focus of OO and Functional Computation: Data How can these two views possibly be related?

Two Simple Languages: FUN and OOPS: 

Two Simple Languages: FUN and OOPS FUN is (like ML/Scheme) basic data: numbers ... datatype function definitions expressions, including variables primitives: +, -, ... conditionals function application blocks assignment OOPS is (like Java/Eiffel) basic data: numbers ... class definitions, interfaces method definitions expressions, including variables primitives: +, -, … conditionals method application blocks assignment

Two Sample Programs (in lieu of Grammars):: 

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: 

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:: 

Expression (Block) Expression (Block) Definitions are Static, Expressions Capture the State: Definitions : the above definitions for list, cons, empty Assumption: Definitions are well-formed according to the rules of FUN and OOPS (scope, types, …)

Creating Data: : 

Creating Data: let x = … y = … … in … new CC(x,BV) … end let x = … y = … z = new CC(x,BV) … in … z … end FUN Definitions: datatype T = … CC(a:Ta, b:Tb) | ... OOPS Definitions: class CC(a:Ta, b:Tb) implements T { … }

Extracting Pieces: : 

Extracting Pieces: let x = … y = … z = new CC(x,BV) … in … x… end FUN Definitions: datatype T = … CC(a:Ta, b:Tb) | ... OOPS Definitions: class CC(a:Ta, b:Tb) implements T { … } let x = … y = … z = new CC(x,BV) … in … z.a … end

Mutating Data: : 

Mutating Data: let x = … y = … z = new CC(y,BV) … in … void … end FUN Definitions: datatype T = … CC(a:Ta, b:Tb) | ... OOPS Definitions: class CC(a:Ta, b:Tb) implements T { … } let x = … y = … z = new CC(x,BV) … in … z.a := y; … end

Calling Methods in OOPS: : 

Calling Methods in OOPS: let x = … y = … z = new CC(x,BV) … in … exp [s=x,u=BV2,this=z]… 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 … z. m(x,BV2)… end Example: class CC(a:CC, b:int) implements T { … T m(CC s, U u) { s.a := u; } … }

Calling Functions in FUN: : 

Calling Functions in FUN: let x = … y = … z = new CC(x,BV) … in … exp [t=z,s=x,u=BV2]… end FUN Definitions: m(T t, S s, U u) = exp let x = … y = … z = new CC(x,BV) … in … m(z,x,BV2)… end Example: m(CC t, CC s, int u) = s.a := u

How about First-Class Functions? : 

How about First-Class Functions?

How about Inheritance? : 

How about Inheritance? class A(X x, Y y) { method1 method2 method3 } class B(Z z) extends A { method4 }

How about Inheritance with Overriding? : 

How about Inheritance with Overriding? class A(X x, Y y) { method1 method2 method3 } class B(Z z) extends A { method1 method4 }

Type Elaboration: The Global Picture: 

Type Elaboration: The Global Picture Object, Any Class Derivation Path(s)

Models of Computation: Conclusion : 

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: 

The Focus of OO and Functional Computation: Data function1 function2 function2 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

Models of Programming : 

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? : 

What is a 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: 

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: 

Flat Data Collections: Numbers 1.0 3.141 67857. .750 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: 

Compound Data An elephant has a name, an age, and a certain demand for space. In FUN: datatype Elephant = e of (name:String, age:Number, space: Number) In OOPS: class Elephant ( name: String, age: Number, space: Number) {}

Compound Data and Programming: 

Compound Data and Programming In FUN: datatype Elephant = e of (name:String, age:Number, space: Number) fits_into(ele: Elephant, cage_space: Number) = ele.space < cage_space In OOPS: class Elephant ( name: String, age: Number, space: Number) { fits_into(cage_space: Number) { space < cage_space } In both cases, remember the available pieces!

Mixed Data (Union): 

Mixed Data (Union) An animal is either (1) an elephant (2) a spider or (3) a monkey In FUN: datatype Animal = e of (name: String, age: Number, space: Number) | s of (name: String, legs: Number) | m of (name: String) In OOPS: 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: 

Mixed Data and Programming In FUN: datatype Animal = e of (name: String, age: Number, space: Number) | s of (name: String, legs: Number) | m of (name: String) fits_into : Elephant Number -> Bool fits_into(a: Animal, cage_sp: Number) = case a of e : a.space < cage_sp s : true m : false In OOPS: interface Animal { fits_into : Number -> Bool } 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: 

Arbitrarily Large Data

Arbitrarily Large Data and Data Definitions: 

Arbitrarily Large Data and Data Definitions

Arbitrarily Large Data and Programming: 

Arbitrarily Large Data and Programming

Arbitrarily Large Data: the Interpreter Pattern: 

Arbitrarily Large Data: the Interpreter Pattern In FUN: layout data type definition one clause per variant deconstruct each variant use natural recursions dispatch via case In OOPS: layout data type definition one clause per variant deconstruct (implicit) use natural recursions

More Program Design: More Similarities: 

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: 

Launching Programs: Via Interaction drop-down menu button

Launching Programs: Via Interaction: 

Launching Programs: Via Interaction In FUN: type Callback = Event GUI -> void button1 : Callback button1(e: Event, go : GUI) = …. menu1 : Callback menu1(e : Event, go : GUI) = … *** Menu(… menu1 …) *** *** Button(… button1 …) *** In OOPS: interface Callback { execute : Event GUI -> void } 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 : 

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!): 

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 : 

Abstraction in FUN: Abstracting SUM : list-of-numbers -> number SUM(a_list) = case a_list of empty : 0 cons: a_list.first + SUM(a_list.rest) PI : list-of-numbers -> number PI(a_list) = case a_list of empty : 1 cons: a_list.first * PI(a_list.rest)

Abstraction in FUN: Specializing : 

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

Abstraction in OOPS: Abstracting : 

Abstraction in OOPS: Abstracting 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: 

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() } }

Abstraction: Inheritance and the Template Pattern: 

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: 

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 - ...

Comprehending Code: the Visitor Pattern: 

Comprehending Code: the Visitor Pattern A x 5 + - * / ** …... for- for+ for_num for_var

Comprehending Code: the Visitor Pattern vs Case: 

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”: 

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: 

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 A x 5 + - * / ** And here are more A-expressions: -- a sin-expression: sin(A)

Black Box Extensibility: Adding or Modifying Functionality: 

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 A We may want more methods than the original product provides or we may wish slightly different functionality.

Black Box Extensibility: More Cases: 

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: 

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: What’s better and Why?

The Winner: A Comparison: 

The Winner: A Comparison a data-centered, safe model of computation a data-centered model of program design a rich “theory of programs” 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 FUN: OOPS:

The Winner: Default Functionality: 

The Winner: Default Functionality functions with many parameters Fortran: entry points Common LISP: by-keyword Scheme: rest arguments Chez: case-lambda … but there is also Currying classes with many default methods and instance variables derived classes that override just those few that need to be modified FUN: OOPS: Your web server has 27 different parameters that can be tuned … How do you tune them?

The Winner: Extensible Products: 

The Winner: Extensible Products complex programming protocols problem with standard types … soft-typing works just fine default strategies extensibility patterns (hooks) derived classes that override just those strategies that need to be modified FUN: OOPS: Your product should accommodate 435 business strategies in 47 countries …. How do you accommodate them all?

The Winner: There isn’t One: 

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: : 

More Comparisons: FUN has “lambda”, which means it is simpler to abstract functions are easier to comprehend has “currying”, which makes up for the short-comings 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? : 

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: 

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: 

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!: 

Education: FUN first, OOPS later! functional programming is syntactically simpler than object-oriented programming functional programming is more natural than object-oriented programming: append(list1,list2) versus list1.append(list2) functional programming is traditionally more interactive than object-oriented programming (repl)

Summary: 

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 : 

Thank You Corky Cartwright Dan Friedman Matthew Flatt Shriram Krishnamurthi Robby Findler Kim Bruce Bob Harper Ralph Johnson Scott Smith Phil Wadler