Lecture 23

​

FP vs. OOP Decomposition;

Double Dispatch

Programming Languages

UW CSE 341 - Winter 2023

Breaking Things Down

• In Functional Programming (FP), we decompose programs into functions that perform some operation
• In Object-oriented Programming (OOP), we decompose programs into classes that give behavior to some data
• Key Insight: these are exactly opposite
• In a technical sense
• So different they are not different at all...

Summary

• FP and OOP fill out the same “matrix” in different ways:
• If we put data variants in rows and operations in columns, then:
• FP organizes programs “by column”
• OOP organizes programs “by row”
• Which is better? Depends on:
• What changes/extensions are most likely
• Personal taste (?) for problem domain
• But things get tricky for OOP when we have >= 2 arguments
• Solved within OOP paradigm with double [multiple] dispatch idiom

“The Expression Problem”

• Famous example in the PL field: expressions for a small language
• Different expression variants : int constants, additions, negations, ...
• Different operations to perform : eval, to_string, has_zero, ...
• Leads to a matrix of variant/operation pairs
• In any PL, programmer must define behavior for all matrix positions

FP Approach = “By Column”

• Use a recursive variant type with 1 constructor per variant
• Or similar approach with dynamic typing (e.g., Racket structs)
• “Fill out the grid” with one function per column
• Each function has a branch for each row
• Can share branches if appropriate (e.g., wildcard patterns)

See code!

OOP Approach = “By Row”

• Define a class with 1 abstract method per operation
• In dynamic typing, this can be conceptual, not explicit
• “Fill out the grid” with subclass per row
• Each class has a method for each column
• Can share methods if appropriate (e.g., method in shared superclass)

See code!

A Big Course Punchline

• FP and OOP are doing the same thing in exact opposite way:
• Organize the program by-row or by-column
• Which is better depends on application domain and team aesthetics
• Regardless of program structure, can help to “think both ways”
• Code layout is important, but impossible to meet all needs
• Tools help present other code views

Extensibility

• Designing programs for extensibility is difficult
• The future is often hard to predict
• What if we need to add a new kind of expression variant?
• Annoying in FP and easy in OOP
• What if we need to add a new operation?
• Annoying in OOP and easy in FP

???

???

FP Extensibility

• FP: easy to add new operation, e.g., no-neg-constants
• FP: annoying to add new expression variant, e.g., Mult
• Have to revisit all old operations implementations to add a case
• OCaml type-checker does help by giving a to-do list (if avoided wildcard patterns)

See code!

???

😃

???

😭

😭

😭

OOP Extensibility

• OOP: easy to add new variant, e.g., Mult
• OOP: annoying to add new operation,e.g., no-neg-constants
• Have to revisit all old classes to add a method
• Java type-checker does help by giving a to-do list (if avoided default implementations in superclass)

???

???

😭

😃

😭

😭

See code!

Extensibility is Difficult

• If you know new operations are coming, use FP
• In OOP, can plan ahead with advanced techniques like the Visitor Pattern
• If you know new variants are coming, use OOP
• In FP, can plan ahead with advanced techniques like an “Other of ‘a” constructor
• Some languages try to support both well, but there are trade-offs in approaches
• See Scala as an example

Thoughts on extensibility

• Reality: we often don’t know how we or others will want to extend/change program behavior in the future
• Extensibility has downsides
• Extensible code is harder to understand and maintain
• Must always think about the future
• Must always reason about correctness with respect to unknown extensions
• Thus we often end up with features to restrict extensibility, e.g., final classes in Java

Binary Operations and OOP’s “Double Dispatch”

• What if we have a binary operation that depends on >1 variants?
• A different matrix: pair of variants, not variants and operations
• Easy in FP: just pattern match on pair of arguments
• More complicated in OOP...

add

Example

• Enrich our expression language with String and Rational
• Change the Add operation to allow recursive results to be any combination of Int, String, and Rational
• If >= 1 argument is a string, then string concatenation, else math
• Now the “eval for Add” square of our first matrix requires implementing another 3x3 matrix

add

Binary Operations Easy in FP

• Just pattern match on the pair of values
• 9 cases in 9 branches

See code!

add

Now try OOP...

• Starts okay: Each value class should have an add-value method the eval method of can add% can use
• Each class handles 3 of 9 cases, where this is the first argument

(define add% …

(define/public (eval)

(send (send _e1 eval) add-value (send _e2 eval)))

​

(define int% …

(define/public (add-value other) …)

(define string% …

(define/public (add-value other) …)

(define rational% …

(define/public (add-value other) …)

Uh-oh

• Each add-value implementation knows variant of this but not the variant of other
• Needs to know, right?
• Tempting/works to use is-a? but reverting to half-FP style
• NOT allowed on Homework 7

​

(define int% …

(define/public (add-value other)

(cond [(is-a? other int%) … ] ; get other’s i and +

[(is-a? other string%) …] ; get other’s s and concat

[(is-a? other rational%) …] ; get other’s n,d and math

[#t (error …)])))

Another way

• OOP has a consistent answer for whenever you think you need a cond with is-a? branches:
• Instead, each class should define a method to do the computation
• You should call that method, relying on dynamic dispatch
• But here that computation needs will need to have the other add argument and know its variant
• In add-value, that other argument is this
• And each class knows its variant
• double-dispatch trick/idiom gets the callee the information it needs

Double-dispatch

• int%, string%, and rational% each define add-int, add-string, add-rational
• 9 total methods, 1 for each case of adding values
• add-X takes an X that is the left-argument to addition
• this is the right-argument
• First dispatch: add%’s eval calls add-value of left argument
• Second dispatch: add-value implementation calls correct method of right argument with caller’s this for callee’s other

See code!!

Why am I teaching you this?

• Honestly, partly to belittle full commitment to OOP
• Full commitment to any approach leads to unnecessary wizardry
• To show a sophisticated idiom that requires really understanding dynamic dispatch
• Implementing The Visitor Pattern, which helps do FP-style decomposition in OOP languages, uses double dispatch
• To contrast with multimethods (optional material ahead)

Works in Java too

In a statically typed OOP language, double-dispatch works without problem:

​

abstract class Value extends Exp {

abstract Value addValue(Value other);

abstract Value addInt(Int other);

abstract Value addString(MyString other);

abstract Value addRational(Rational other);

}

class Int extends Value { … }

class Strng extends Value { … }

class Rational extends Value { … }

See code!

[optional material ahead]

​

[We won’t test you on what remains in this lecture and it’s not on the homework]

But this will improve your understanding of:

• Java
• Static overloading
• Dynamic dispatch
• Double dispatch

So don’t be surprised if you find yourself looking for this material some day :-)

Java, in more common practice

Because Java has static overloading, no need to give different names to methods that take different types of arguments

​

Can make double dispatch seem even more magical/confusing, but same thing:

• First dispatch “only knows” its argument has type Value
• Second dispatch passes this which has a more specific type like Rational
• Static overloading is weird: this has a different static type in inherited code

​

​

abstract class Value extends Exp {

abstract Value add(Value other);

abstract Value add(Int other);

abstract Value add(MyString other);

abstract Value add(Rational other);

}

See code!

What if instead...

What if we could implement 9 add-value methods and have:

​

​

Pick the right 1 of the 9 with one dispatch?

This would require dynamic dispatch on the receiver and the argument

• Racket and Java do dynamic dispatch only on the receiver
• This semantics is called multimethods; has support in some languages
• Multimethods have pluses and minuses; are not static overloading

(define add%

…

(define/public (eval)

(send (send _e1 eval) add-value (send _e2 eval)))

add