OCAML, Part I: Syntax, Semantics, and Computation in Programming

OCAML, PART I

We are going to learn a new language What does that mean ?

Five Aspects of Learning a PL

Syntax: Programs as Phrases

Syntax. Programs are phrases written in an artificial language Languages are made of symbols That are combined according To grammatical rules Syntax defines The grammatically well-written phrases of a language

Ex. - let x = let in x . let x = 5 in length (5) . let x = 5 in x+ x well-written and tmeaningful not well-written well - written but meaningless

Semantics: Meaning of Programs

Semantics · Among well-written phrases (= programs), what are The meaning ful ones ? finite combinations of symbols well-written phrases meaningful phrases . What is the meaning of a program?

Denotational Semantics

· Denotational sermantics [let plus x = x+X Programs = syntax for mathematical objects " denotations I = double function in mathsyntax math let twice x= xxx let twice1 x= 2 Ax g ( x ) = 2 . x let twice 2 x = xxx-0

Operational Semantics

· OPERATIONAL SEMANTICS Programs = syntax + computational content meaning (dynamic) Op semantics explains how computers understand programs Dynamic Semantics: how programs are evaluated e -> l' <0, C? - > <= ' C'>

Static Semantics

Static Semantics: syntax also carries a meaninglet for x = x+ x La foo is a function that has an input with a notion of addition -> static semantics usually given via type systems

Course Structure: Syntax, Statics, Dynamics

In This course: 1 syntax ex. l1, l2, es expressions, Ron if-Men-else (e, en, (3) expression 2 statics e. : bool @3: 2 Cs : 2 :f. Der-else (C, e, (3) : 2 3 Dynamics if-Rem-else (true, Cz, (, ) -> Cz : f-Mon-elro(false, la, es) -> e3 b-ob' if- Rep-else (b, C2,(3) -> if-Ram-else (b', (2,ps)

Implementing a Language: Syntax, Static, Dynamic

ms All of That tells us what needed to implement a language syntax ms if- Ren-else 1 1 e3 syntax-tree (abstract syntax) lexer, parser, ... static semantics , ~> type-checking type - inference ty-infer (if-Ran-olse (e, la, es) = let ty2= ty-infer (e.) ty == ty-infer (2) ty3 : 17- infer (es) in :f ty1 =10018 ty2 = ty3 Their ty3 dynamic sermanties na interpreter eval ( if - then-else (, le, ; ) = let b = eval (1) in if b == true then eval (es) else eval (es)

IDIOMS

What we the patterns That people fluent in the language use to solve problems? Ex. Use Java-style expressions in Ocaml does not work well, although you can do that read good code no learning by doing - look for beautiful code experience

LIBRARIES

-> not covered in This course ToolsBuilding blocks

Expressions

Program Structure in Functional Programming

2. What is a program in FD? (cf. paradigm) In imperative programming, programs are built out of statements instructions - commande 1 expressions - Imary syntactic categories while (3+5 == 0) : expression ~> leaves state unchanged ; just at: Thelic L x : = x + 1 a command -> determines a change in the state of the machine Ih FP, programs are expressions as no command, to statement, ... => no state ( ?! ) Programming as advanced algebra Computation as calculation

Expression Properties: Syntax, Semantics, Execution

Any expression has a syntax sermanlics (C1+Cz, if-Ron-else (e, c,e3), let x= e, in ez, .... ) static = meaning of an expression " at least " , without when non-executed when executed dyharmic What does it mean to execute an expression? computation = calculation

Computation as Calculation Example

Ex. High- school Calculate (1+2)} = Simplify (1+2)? to simplet expressions until the simplest is achieved expression value (1+2) ?- > 3' - 313 computation - 9

Computation and Values

Computation = reduce an expression Until a value is reached , if any Value = an expression That cannot be further reduced Exp Val eval (e) = v evaluation OCAME interpreter (Utop) is a generalised calculator eval (e) expe

OCAML EXPRESSIONS

Integers

OCAML( AML EXPRESSIONS - integris values : 0 , 1 , 2 , - 1 , - 2 , . . exp : C+++2 , l,xl2 ... typing: int evaluation : ...

Booleans

value: true, false - booleans / - exp : if e. Then ez else e3 , 0,88 es , . .. typing: bool evaluation: e . = true if e. then er else es IN value : 3. 19 , ..

Floats

- float L, to evaluate " if ", Rom ez else " - evaluate e, to a value b · if b is true, Ren evaluate es and return Re result 1 xp C+ +. l2, P,t. C2. .. typing: floot evaluation : ... · otherwise, evaluate es and return the result

OCaml Expression Evaluation Process

What does OCaml do when we give it an expression e ? + 1 Massage syntax of e : 3+2 3 2 2 Type-inference ~> infer the type of e . No need for the programmer to write the type ( but better if you do that) Jard does the same ; Type inference is done by the compiler Python infer types ~> before program execution (na static) at dynamic time - Find lots of bugs without waisting resources

Relation Between Statics and Dynamics

Relation between stalies and dynamics (R. Milner) " Well-typed programs do not go wrong " re: 2 e->c' re: 2 re: 2 => either e is a valve 아 1 c'. e -se' computation can progress no error during computation

DEFINITIONS

Let x = 42 Definition

D EFINITIONS Among expressions, we have definitions let x = 42 T variable evaluating let x = 42 gives val x : int = 42 " we have the value 42 , of type int, which is bound to the name x " If we know evaluate x, we just get az

Syntax and Dynamics of Let Definitions

Syntax : let x = e L) expression 1 identifier (variable) Dynamics . We need first to introduce the notion of an environment n = stores of variables /identifiers with associated values e.g. n= [x-03, y-02] · We evaluate expressions within environments . To evaluate let x=e in environment y do: · evaluate e in environment y, obtaining value v . bind v to x in y, i.e. build y [x]]]

Definitions as Expressions

Comments 1. Are definitions expressions! Not really · Definitions do not evaluate to a value ~s just update the environment · Definitions do not have static semantics . We cannot use definitions as expressions ( let x = 42 ) + 3 Exp Dif Vel 3. Are definitions expressions ? Yes, actually Definitions are syntactic sugar for let-in expressions let x = 42 ih 3+x continuationA definition is a let-in exp. " without" continuation (i.e. with trivial continuation). Syntax. e : = ... \ let x = e in e Statics. rte . : 2, Po x: 2, 1 l2 : 22 } More of That later [+ let x= e, in ez. 22 Dynamics S n[x~> v1] lt C3 => V2 y 11 let x= e, in e3 => V2

VARIABLES AND IMMUTABILITY

Immutable Variables in Functional Programming

VARIABLES AND IMMUTABI Variables in FP are immutable: They are name/place holders for values, as in math let x = 42 ; let x = 1 ; ->error: x already defined Immutability smokes code much safier

Referential Transparency

REFERENTIAL TRANSPARENCY: an expression and the value it computer (requires absence of ale equivalent side effects) e[e] = ([v] whenever e=>N Counter example : ( [e] = c/x e = x: = 0; 42 Ther e[e] => error e [42] => 42/42

Equational Reasoning

EQUATIONAL REASONING: reason about code using systems of equations let x = e. in er ) 211 e2 if x not a variable in e, dead-code optimisation not valid if variables are mutable not valid if variables are imutable Suppose we start with xH1. (x := 0; 3) + 1/x ¥ 1/x+ (x := 0:3) 1 . Easy to parallelise code Immutability sometimes difficult to digest. in FP " objects " do not change sort ((1,3,23) creates a new list [ 1 , 2 , 3 ]

Updating Structures with Immutability

Suppose we have a structure " person " Pippo = { age: 99, Hanne : " Pippo" } want to update the age of Pippo to 100 next-year (Pippo) does not change Pippo. A new structure is created , exactly like Pippo , but with age 100

LET EXPRESSIONS

Sintassi, Statica, Dinamica

LET EXPRESSIONS Sintassi e : : = . .. 1 let x = e inc L) variabile / identificatore Statica Pre 1 : 21 P, x: 2, Fl3 :?? Pr let == e, 1h e2 : 22 sostituzione Dinamica e => v, C2 [V1/x]=>V2 1et x=e, in l? = > ~? Se e, ha tipo 2, ed C2 ha tipo 22 assumendo che abbia tipo 21, allora let x= e, in c2 ha tipo 22. per valutare let x=C, ire2: · valutare e, ad vi · sostituire v, por x in Cz ottenendo nuova espressione cí · valutare e: dd v2 · restituire V2

Let Expression Example

Ex let x = 2+1 im x + 39 -> let x =3 in ×+39 -> (x+39) [3/x] 3+ 39 -> 92 NB lel x = e, in ez è effettivamente una espressione: (let x=3 in ×+x) + 2 (let x=3 in xxx) + if (let x= true in x) Then O else 2 V (let x= 3) + 2 X

Scope

Variable Scope and Meaning

Scope Lo scopo di una variabile determina la porzione di codice dove la variabile/horme è meaningful let x= 92 in x + (let y = 2 in scope diy [x+ y) scope di x Al di fuori dello scope, la variabile è "non dichiarata", e non può quindi essere valutata

Overlapping Scopes

Possiamo avere overlapping de scope let x= 5 in ( (let x= 6 in x) + x )

VARIABLE RENAMING

Renaming in Mathematics and OCaml

VARIABLE RENAMING In matermatica, la scelta delle variabili usate nelle definizioni è irrilevante f (x) = x+1 C stessa fumesone S (x) = >+1 Lo stesso accade in Ocaml con le let-expression : let x = e, in la let y = e, in c2 [Y/x] > y non sia già usata } stessa espressione, purchè renaming

Free and Bound Variables

Ex. let x = 3 in xxx let y = 3 in y+y lega (bind) x in ez, e quindi Diciamo che let x= e, in Cz che x è legata in C2. Diversamente diciamo che x è libera let x= 5 in ( let x = 6 in xxx) + x T scopo La sostituzione elv/x] agisce solo sulle occorrenze libere di x let x= 5 in (lot x=6 in x+x) +x -> ((let x=6 In xxx)+x) [5/x] (let x= 6 in xxx) [5/x] + x [5/x] = La qui x è legata; NON avviene alcuna sostituzione qui x è libera; possiamo sostituite( let x = 6 in x+x) + 5 -> (x+x) [6/x]+5 -> (6 + 6) +5 12+ 5 ->17 Questo è consistente col principio di (a)-renaming let x= c, in 12 =2 let y = e1 in e2 [Y/x] ( y fresca) Infatti let x = 5 in (let x=6 in x+x) + x 8 let x = 5 in (let y= 6 in y +y ) + x

ESERCIZIO

Variable Shadowing and Scope

ESERCIZIO Se scriviamo nell'interprete let x = 1 ; let x= 2 ; valuta x = 2 : int immulabilità ?! let x = 1 in -> zucchero sintattico let x = 2 in × allora spazio in memoria, chiamato x, in cui salva 1 -> allora altro spazio in memoria, sempre col nome x, in cui salva 2 quale spazio di memorio vado a vedere, visto che ca te sono 2 col home x ? scope statico as Quello definito dal binder sinTatticamente polu vicino