Lecture 21

​

FP vs. OOP for the Expression Problem

+

Victory Lap

Programming Languages

UW CSE 341 - Winter 2021

Updates 2021-03-12

• Homework 7 due today by 5pm!
• Quiz 2 next Wednesday
• Don’t forget course evals!

The Expression Problem

Breaking Things Down

• In Functional Programming (FP) we break programs down into functions that perform some operation
• In Object-oriented Programming (OOP) we break programs down into classes that give behavior to some data
• Key Insight: these are “opposites” in a technical sense

Summary

• Both FP and OOP can 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 are most likely
• Things get tricky for OOP when we have >= 2 arguments ⇒ double dispatch

“The Expression Problem”

• Famous example from research community: expressions for a small language
• Different expression variants : integer constants, additions, multiplications, ...
• Different operations to perform : eval, to_string, has_zero, ...
• Leads to a matrix of variants X operations
• Implementation requires “filling out the matrix” by specifying what to do in each case

FP Approach = “By Column”

• Use a recursive variant type with one constructor per expression variant
• “Fill out the grid” with one function per column
• Each function pattern matches and has one variant case per row

See code!

OOP Approach = “By Row”

• Define an abstract class with 1 method per operation
• “Fill out the grid” with one class per row
• Each class implements one method per column

See code!

Punchline

• FP and OOP are doing the same thing in opposite ways: by-row vs. by-col
• Which is better depends on application domain and team aesthetics
• Code layout is important, but impossible get perfect

Extensibility

• Designing programs for later maintenance and extensibility is difficult
• What if we need to add a new kind of expression variant?
• What if we need to add a new operation?
• FP and OOP each make one of this easy and other annoying...

???

???

FP Extensibility : Ops Easy, Variants Annoying

• FP: easy to add new operation, e.g., no_neg_constants
• FP: annoying to add new expression variant, e.g., Mul
• Have to revisit all old operations implementations to add a case
• Compiler does help by giving a “TODO” list

See code!

???

😃

???

😭

😭

😭

OOP Extensibility : Ops Annoying, Variants Easy

• OOP: easy to add new expression variant, e.g., Mul
• OOP: annoying to add new operation,e.g., no_neg_constants
• Have to revisit all old class to add a method
• The Visitor Pattern can help mitigate this challenge

See code!

???

???

😭

😃

😭

😭

Extensibility is Difficult

• If you know new operations are coming, use FP
• If you know new variants are coming, use OOP
• If both, some languages try to support, but it’s a hard (research) problem
• Reality : we rarely know how we will need to change our code
• Extensibility “cuts both ways”:
• Reusable code is harder to understand and maintain, must always be thinking about future
• Thus we often end up with features to restrict extensibility, e.g., final in Java

Binary Operations and OOP’s “Double Dispatch”

• What if we have a binary operation that depends on both variants?
• Easy in FP: just pattern match on both arguments.
• More complicated in OOP, we know which variant this is, but not other

Add

Example: add a String and a Rational

• Need to update eval for Add to handle any pair of values
• String concatenation if either argument is a string, “math” otherwise
• Now just definite Add is a whole (different) matrix!

Add

Binary Operations Easy in FP

• Just pattern match on the pair of values

Add

See code!

Binary Operations Tricky in OOP

• Starts out OK: use OOP to call some add-values method
• Each value class handles three out of nine cases
• Tempting to use is-a? (“instanceof”) to branch on class of arg, BUT
• This is not “OOP style” -- we should never very rarely need to inspect types!
• Alternative: notice that add-values in Int needs the type of its argument
• OOP always solves this problem by via dynamic dispatch to “do the right thing”
• But now we to “tell” arg what type this is… but we know that!
• Add separate methods on arg that “know” type, pass this

See code!

Double Dispatch

• Our trick to get around “knowing an arg’s type” is called Double Dispatch
• All the value classes (Int, String, Rational) must define a method to handle all variants
• add_int, add_string, add_rational, ...
• Example: Int’s add-value calls arg.add_int(this)

See code!

Takeaways

• A fully commitment to OOP can lead to some strange code
• The Visitor Pattern (not shown) can clean up code and mitigate some of these challenges
• Double dispatch rarely used in practice outside of the Visitor Pattern
• Studying double dispatch deepens our understanding of dynamic dispatch

Victory Lap

First: THANK YOU!

• Great class, despite very trying times! Thanks for making it fun 🙏

​

• Huge thanks to the course staff!! They are PHENOMENAL!! 🤩

​

• Thanks to Jared for all the jokes 😂

341 Course Themes

• Big focus on FP:
• No mutation most of the time (!)
• First-class functions and closures + how to implement them (MUPL!)
• “Each-of” types and pattern matching
• The “exact opposite” of OOP in a sense
• Sound static static typing prevents many errors
• But will always be approximate!
• Modularity is essential to organizing large code bases
• Language features help enforce by enabling us to establish and maintain invariants

What’s Next?

• More classes
• Resources for independent study
• Grad school
• Industry

PL Courses @ UW

• CSE 401 : Compilers
• CSE 505 : Grad PL
• CSE 490P : Advanced PL by JRW (see videos from Spring 2020)

​

• Other related courses:
• CSE 331 : Software Design and Implementation
• CSE 403 : Software Engineering
• CSE 507 : Computer-aided Reasoning for Software

Other Resources

• Structure and Interpretation of Computer Programs
• “SICP” -- an incredible classic
• Learn lots more about interpreters

​

• Learn other “weird” languages: Haskell, Prolog, Rust, Agda, …

​

• Software Foundations
• Intro to Verification in the Coq proof assistant

The End

• Many, many thanks again!!!
• Keep in touch and let me know about your future PL adventures :)

​

​