Tomáš Petříček, 309 (3rd floor)
petricek@d3s.mff.cuni.cz
https://tomasp.net | @tomaspetricek
https://d3s.mff.cuni.cz/teaching/nprg077
.fsx
file.fsproj
with .fs
sourceslet rec
Lazy<T>
to represent lazy valuestype Value =
| Number of int
type Expression =
| Constant of int
| Binary of
string *
Expression *
Expression
val evaluate :
Expression -> Value
Expression
is the source
code that user writes
Value
is what we
get as the result
evaluate
takes expression
and returns value
type Value =
| ValNum of int
type Expression =
| Constant of int
| Binary of
string *
Expression *
Expression
| Variable of string
type VariableContext =
Map<string, Value>
val evaluate :
Expression -> VariableContext -> Value
Adding variables and variable context
Variable can store only values (call-by-value)
evaluate
takes context
(* Functions *)
let f = (fun x -> 10 + x)
f 32
(* Tuples *)
let t = (1, "hi")
fst t
snd t
(* Unions *)
let c1 = Case1(10)
let c2 = Case2(32)
match c1 with
| Case1 n -> n + 32
| Case2 n -> n + 10
Functions but only with single argument
Tuples of two element with getters
Unions without tag name with two cases
(* Let bindings *)
let x = 10 in x * 32
(* Let desugaring *)
(fun x -> x * 32) 10
(* Conditionals *)
if e then 10 else 32
(* Both are expressions *)
1 + (if e then 41 else 1)
1 + (let x = 1 in x + x)
(* Currying *)
let add = fun a -> fun b -> a + b
in (add 10) 32
let
is a syntactic sugar
Everything (if
and let
too) is an expression
Functions that return functions (currying) if you need multiple parameters
Lexical
Based on static block structure in code
Function value needs to capture variables (closure)
Dynamic
Based on dynamic evaluation structure
Formally specify how expression evaluate
Substitution-based
We do not need variable context!
Call-by-value (strict)
Evaluates function arguments first (ML)
Call-by-name (lazy)
Evaluates arguments when needed (Haskell)
Simple numerical evaluator as the starting point
This has already been done for you :-)
Add unary operators (-) and conditional
We only have numbers, so treat 1
as true
Functions and application
Tricky! Closure needs to capture variables!
Let binding as syntactic sugar
Evaluate let
by treating it as apply/lambda
Add a simple data type - tuples
New value, constructor and destructor
Add more data types - unions
New value, constructor and destructor (match)
Add support for recursion
Needs Lazy<Value>
in variable context to work
Add unit and create a list value
Case1(Const(1), Case1(Const(2), Case2(Unit)))
Implement call-by-name semantics
Change variable context to store expressions
Implement evaluation by substitution
Toy approach, but you learn the semantics
A tiny functional programming language interpreter
Value
and Expression
Tomáš Petříček, 309 (3rd floor)
petricek@d3s.mff.cuni.cz
https://tomasp.net | @tomaspetricek
https://d3s.mff.cuni.cz/teaching/nprg077