Prototypes:
Object-Orientation,
Functionally

                   build = λ t m ↦ Y (m t)
                   inherit = λ c p u s ↦ c (p u s) s

François-René Rideau <fare@mukn.com>

http://github.com/metareflection/poof

LambdaConf 2024-05-06

PgDn: next PgUp: previous ↑ ↓ ← → ESC ⏎ Touchscreen: swipe down until you must swipe right

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Prelude: OO vs FP?

Language Wars: OO vs FP

Talking Past Each Other… for Decades

FP in Ivory Towers, OO in Industrial Slums

Videos, Books, Courses… all wrong

“Incommensurable paradigms” (Gabriel)

Prelude: OO vs FP?

Reluctant Peace: OO and FP

Yet, in practice: mutual adoption!

Modern OO languages adopted (limited) FP

Modern FP languages adopted (limited) OO

… Lisp: both unlimited since ~1976

Prelude: OO vs FP?

OO for FP

FP is my tribe — probably yours

Vast evidence that OO matters

FP can make its semantics simpler

Practical Precedent: Jsonnet (2014), Nix (2015)

Prelude: OO vs FP?

Scheme Workshop 2021 Paper

Why OO matters — Incremental Modularity

What OO is — Constructive Semantics in FP

Demystify fundamental concepts of OO

Prototypes before Classes, Purity before Mutation

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Introduction: Wherefore OO?

What OO isn’t about

Classes

“Encapsulation”, “Information Hiding”

Inheritance vs Composition

Mutation everywhere

Message Passing everywhere

Introduction: Wherefore OO?

What OO is about

Modularity: limited knowledge in

Incrementality: limited knowledge out

... Intralinguistically

A way to factor software

... to support Division of Labor

Introduction: Wherefore OO?

How OO does it

Ad Hoc Polymorphism

Open Recursion

... as First-Class (or Second-Class) Entities

Enabling Teamwork among Developers

Introduction: Wherefore OO?

Incremental Specification

Tree ⊂ Type

Binary_Tree ⊂ Tree

Balanced_Binary_Tree ⊂ Binary_Tree

Red_Black_Tree ⊂ Balanced_Binary_Tree

AVL_Tree ⊂ Balanced_Binary_Tree

Integer_Keyed_Tree ⊂ Tree

MyTree ⊂ Integer_Keyed_Tree ∩ AVL_Tree

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Minimal OO: Mixin Functions

Simplest OO Concept

Target = structures and algorithms to specify

Spec = modular increment of specification

build :: Spec → Target

inherit :: Spec → Spec → Spec

Minimal OO: Mixin Functions

Simplest Spec, modeled as a Function…

Output: partial(?) target, more elaborate than before
Input 2: partial target so far (incrementality)
Input 1: whole target (modularity)

type Spec = PreTarget → PreTarget → PreTarget

OK, but monomorphic, or even dynamically typed

type PreTarget = FiniteMap String Any

Minimal OO: Mixin Functions

Mixin Function: Simplest Spec (w/ subtyping)

type Mixin inherited used defined = 
    
  inherited → used → defined

build :: (top → self → self) → top → self
build = λ t m ↦ Y (m t)

inherit :: (i1⋂d2 → u1 → d1) → (i2 → u2 → d2) →    
        i2 → u1⋂u2 → d1⋂d2

inherit = λ c p u s ↦ c (p u s) s

Minimal OO: Mixin Functions

Is it OO at all? Aren’t objects records?

OO is usually about key-value records

Record = Product of indexed (or dependent) types

method, attribute, field, var, slot, property, member…

You can (and often do) have records without OO!

Minimal OO: Mixin Functions

Record (whether Target or not) (untyped)

rtop = λ _ ↦ error "No such method"

rcons = λ k v r m ↦ if k == m then v else r m

point = rcons 'a 3 (rcons 'b 4 rtop)

point 'a    ⟶   3

Minimal OO: Mixin Functions

Specifications for Records

kv = λ k v s t ↦ rcons k v t

point = build (inherit (kv 'a 3) (kv 'b 4)) rtop

point 'a    ⟶   3

Minimal OO: Mixin Functions

Non-Constant Specifications

method = λ k f s t ↦ rcons k (f s (t k)) t

fudgeX = method 'x 

      λ self next ↦ (self 'fudge) * next

multXY = method 'p 

      λ self _ ↦ (self 'x) * (self 'y)

Minimal OO: Mixin Functions

Mixins as simplest functional model for OO

Theory: Bracha & Cook, “Mixins” 1990 (w/ records)

Practice: Jsonnet 2014, Nix 2015 (w/ records, untyped)

Types: Oliveira 2009 (w/o records)

Plenty of less simple, less pure precedents

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Inheritance

Mixin Inheritance: The First shall be Last

Simplest form of inheritance… given FP

Relies on higher-order functions, fixed-points, laziness

Requires more elaborate types than usual for FP
       … or dynamic types, unpopular within FP

Historically discovered last ’90, deployed recently 2006

Inheritance

Single Inheritance: Historical First

“prefix class” in Simula ’67, Smalltalk ’71

type Gen self = self → self                    (top is given)

buildGen :: Gen self → self                    (= Y itself!)

inheritGen :: Mixin s t → Gen t → Gen s

You can apply / cons mixins but not compose / append them

Inheritance

Mixin Inheritance beats Single

Mixin Inheritance: write once, use many

More for less: More expressive, more incremental

For use in many contexts, you need stricter types:

    type Mixin self super = ∀ eself, esuper ⇒ 
      
  eself ⊂ self ⇒ esuper ⊂ super ⇒ 
          
    eself ⊂ esuper ⇒ eself → esuper → eself

Inheritance

Problem: Mixin Dependencies

Pre-composing mixins leads to
       [Z K1 C O A O B O K3 A O B O D O K2 D O E O]

Post-composing mixins decreases modularity

Inheritance

Keep Mixin Dependencies Modular?

What if you change K3 ?

Manual curation:
             - users must update when dependencies change
             - users must track transitive dependencies

Modularity: implementation computes precedence list
             - users needn’t update when dependencies change
             - users need only track direct dependencies

Inheritance

Not a Problem for Single Inheritance

Single Inheritance too inexpressive to have the issue

Only one direct super, no duplicate transitive super

“prefix” property: precedence list for super-spec is a suffix

Flavors precedence list reverse of Simula “prefix” class list

Inheritance

Multiple Inheritance beats Mixin

Automatically linearize the DAG into a precedence list

e.g. [Z K1 K3 K2 C A B D E O]

Inheritance

Multiple Inheritance: Precedence Lists

easy precedence lists: [O] [A O] [B O] [C O]

bad precedence lists:
                     [K1 C O A O B O]
                     [Z K1 K2 K3 A B C D E O]

C3: preserve coherence properties
                     [K1 C A B O]
                     [Z K1 C K3 A K2 B D E O]

Inheritance

Combining Multiple and Single Inheritance

Specs with “prefix” property enable optimizations

CLOS: “class” vs “struct”. Scala: “trait” vs “class”

C4: additional coherence property for “prefix” specs

Optimal combination — implemented in Gerbil Scheme

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

OO with(out) Objects

Specifications: OO without Objects

So far, no Class, no Object!

Only Spec (no record) and Target (no inheritance)

Sufficient to produce… these slides

Yet, we recognize (almost?) all of OO

Entire Field a Misnomer… “Inheritance” > “OO”

OO with(out) Objects

Targets beyond Records

Specs for arbitrary “Records”,
       … with very different representations

Specs for numerical functions, for integers, etc.

But Records allow intermediate aspects of any type
       … without weird low-level encodings

OO with(out) Objects

Modular Extensibility

Spec for a vast DAG of Records

Which records in the DAG are extension points?

None | Exponential explosion | All of them

Or maybe stage all extensions before computation?

OO with(out) Objects

Conflation: Proto = Spec × Target

Ubiquitous Extensibility at every level

Every “Prototype” is both Spec and Target
       Proto = Spec × Target

Purity ⇒ Target unique up to observation

THAT is what Prototype OO calls an “object”

OO with(out) Objects

Prototype OO

An “object” (or “instance”) is a Prototype (for a Record)

Prototype is first-class entity conflating Spec and Target

Mutable: Ani ’76, ThingLab ’77, T ’82, Self ’86, JS ’95

Pure: Jsonnet 2014, Nix 2015

OO with(out) Objects

Conflation: Specs beyond Mixins

multiple inheritance:
       Spec = Mixin ? ? × (List Spec)

default values:
       Spec = Mixin ? ? × (List Spec) × Record ?

More: “No Such Message” handler, Assertions, Types…

OO with(out) Objects

Conflation: Targets beyond Records

Target can be Conflation of Record, Function, etc.

Callable objects (Smalltalk, T, CLOS, C++, Scala, Java, etc.)

Proxies for any “kind” value

“Pure OO”: No privileged builtins

OO with(out) Objects

Secret to Semantic Simplicity

Recognizing two distinct entities, Spec and Target

Conflation without Distinction = Confusion
       Lack of awareness ⇒ formalizations that miss the point

Conflation with Distinction = Simplicity
       “reasonable” semantics, superior ergonomics

Jsonnet (2014) [“Components” in T (1982)]

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Class = Proto Type Top

Where are the Classes?

Simula ’67, Smalltalk, C++, CLOS, Java, C#, Python…

So much in common with Prototype OO… yet so different!

Is Class OO even the same paradigm?

What relationship between Prototypes and Classes?

Class = Proto Type Top

Type descriptors!

Target = descriptor for Type and functions (SML module)

Spec = add or override methods for Type

Spec vs Target = Abstract Class vs Concrete Class

Class = Proto Type Top

Class OO

An “object” (or “instance”) is
       an element of a Class (seen as its Target Type)

A class is a second-class Prototype for a Type

Mutable: Simula ’67, Smalltalk ’71, Flavors ’82, C++ ’85

Pure: OCaml(?) ’96, OOHaskell 2005

Class = Proto Type Top

From Type Descriptor to Type

Staging, Existential types, Dependent types…

Most PLs have limited type-level computations

Mixin vs single- vs multiple- inheritance matter

Singleton Class a bit like Prototype, but lacking dynamism

Class = Proto Type Top

Class vs Typeclass

Class vs Typeclass, vtable vs “dictionary”

Pre-vtable constructor vs burden of dictionary

Type-directed synthesis as meta-level computation

Haskell Typeclasses: good modularity, bad incrementality

Automated translation, see LIL (2012)

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

(Im)Pure Challenges

Pure Functional Specs and Targets

Eager Y: only function targets, no sharing, recomputations

Lazy Y: any (delayed) value, sharing, no recomputations

Target as Computation vs Value (CBPV 1999)

Fixed-Point as co-inductive vs inductive

(Im)Pure Challenges

Pure? Identity for DAG

Multiple Inheritance in Nix: no === for DAG

Unique tag: non-determinism? side-effect?

“Solutions”: State? Monads? Opaque tag? Explicit labels?

Labeling convention: moving computation to wetware

(Im)Pure Challenges

Issues with Side-Effects

Many targets for a same spec? Cloning vs Sharing?
       Dynamically modify a super? a list of supers?

Class OO: all prototypes are pure… at compile-time

Linearity: more Optimizations, harder Enforcement

Caching: more Sharing, harder Invalidation

(Im)Pure Challenges

Pure? Non-local specification increments

Multimethods, Mutually recursive classes, Friend classes?

Haskell problem: orphan typeclass targets

Hack: side-effect global table, hope for no conflict

Nix solution: the Open Loop is Global

(Im)Pure Challenges

Advanced OOP, purely?

Optics: generalize method to use lens

Advice, CLOS, AOP, before/after/around methods

Method combination: list, and, +, or user-specified

Any advanced topic in OOP?

Prototypes: Object-Orientation, Functionally

Plan of the Talk

Prelude: OO vs FP?
Introduction: Wherefore OO?
Minimal OO: Mixin Functions
Inheritance
OO with(out) Objects
Class = Proto Type Top
(Im)Pure Challenges
Conclusion: OO is FP

Conclusion: OO is FP

Paper: OO Systems in λ-calculus

Simple Constructive Semantics of OO in pure FP

Demystify fundamental concepts of OO

Prototypes before Classes, Purity before Mutation

Why it matters, Why it’s that way

Conclusion: OO is FP

Key Concepts

Incrementality & Modularity… intralinguistically

Mixin Functions, compose (append) beyond apply (cons)

Multiple inheritance:     modular dependencies

Conflation:      Proto = Spec × Target

Class = Proto Type Top

Conclusion: OO is FP

Why did I care about Prototype OO?

Great Usenet Flamewars of OO vs FP

Talking Past Each Other… for Decades

The paper I wished I could have read younger

Lisp had it all the 1970s

Conclusion: OO is FP

Why So Much Blindness?

Industry doesn’t care enough about Correctness

Academia doesn’t understand Programming In The Large

Both like to ignore the Human Factor

All get stuck in their paradigms

Conclusion: OO is FP

Inhabiting Constraints — But Which?

Every task involves constraint,

Solve the thing without complaint;

There are magic links and chains

Forged to loose our rigid brains.

Structures, strictures, though they bind,

Strangely liberate the mind.

— James Falen, as quoted by dughof

Conclusion: OO is FP

Meta-Thesis

Humility, not fanaticism

Incommensurable paradigms? Go wider!

Simplicity matters

λ’s for Semantics, macros for Syntax

Conclusion: OO is FP

Thank You!

Theory:          https://github.com/metareflection/poof

Practice:       https://github.com/fare/gerbil-poo

OO in 30 loc — 80 loc with multiple inheritance

Hire me!       <fare@mukn.com>