Execution? Or Evaluation?
One of the most pervasive metaphors that dominates programming is the idea of execution. Programs execute, as do functions, as do the tiniest of assignment statements.
One purpose of FP is to defeat — or at least deflate — this metaphor.
The alternate metaphor that obtains in FP is evaluation. FP programs are basically calculators except that they are not over mere numbers but over arbitrarily complex data structures.
To do FP is to replace execution by evaluation.
Abstract? or Concrete?
The related flip is that whereas OOP-ers like their data structures to be abstract data types FP-ers try to keep all their data as concrete as possible.
ie the Java embarrassment that
int is not a proper class is flipped into a positive and pervades the language/paradigm. If we can keep all types concrete its a Good Thing!
Lets see a session
? 1 + 3
4 : ℤ
Simple calc model like python; though notice the type
? [1,2] ++ [3,4]
[1, 2, 3, 4] : ℒ.ℤ
So the calc model applies to list data structures as to nos uniformly
? [("Eggs", 12), ("Bread", 2)]
[("Eggs",12), ("Bread",2)] : ℒ.⦇ℒ.Char, ℤ⦈
More complex; notice that strings are just lists of
No spurious excess ontologies here!
? [("Eggs", 12), ("Bread", 2)] ++ [("PeanutButter", 1)]
[("Eggs",12), ("Bread",2), ("PeanutButter",1)] : ℒ.⦇ℒ.Char, ℤ⦈
And these more sophisticated data structures are as easily handled as the simplest; So far looks just like python
? [("Eggs", 12), ("Bread", 2)] ++ ["PeanutButter"]
ERROR: Type error in application
*** expression : [("Eggs",12),("Bread",2)] ++ ["PeanutButter"]
*** term : [("Eggs",12),("Bread",2)]
*** type : ℒ.⦇ℒ.Char, ℤ⦈]
*** does not match : ℒ.(ℒ.Char)
Whoops! Type error
Python etc will give the error but at a later inconvenient point
Now we move on
ctype Expr where
Plus, Mul : Expr → Expr → Expr
Lf : ℤ → Expr
ctype?? A concrete type.
They (trees) can be constructed
- trivially as an
Lf (leaf) wrapping an
ℤ to give a trivial tree
- Or take two trees
r and make
What does it mean that the type is concrete?
Plus.(Lf.2).(Lf.3) : Expr
This is trivial looking but actually deep
3:ℤ SELF-EVALUATES to
3:ℤ (the trivial case of evaluation)
Plus.(Lf.2).(Lf.3) : Expr self-evaluates to itself
Further just as
2+3 (non-trivially) evaluates to
Similarly for expression trees
If we want to say that the "2+3" tree is the l-subtree of the "(2+3)*5" tree
we could do
t1 = Plus.(Lf.2).(Lf.3)
t2 = Mul.t1.(Lf.5)
Mul.(Plus.(Lf.2).(Lf.3)).(Lf.5) : Expr
Finally an expression evaluator
eval.(Lf.x) = x
eval.(Plus.l.r) = eval.l + eval.r
eval.(Mul.l.r) = eval.l * eval.r
5 : ℤ
25 : ℤ
In short a tree data structure in 3 lines — NO IO NO MEMORY MGMT
And the exp-evaluator (or tree-interpreter) another 3 lines!