1 of 35

Lecture 02

Syntax and Semantics:

Expressions, Functions

Programming Languages

UW CSE 341 - Winter 2022

2 of 35

Updates

Make sure to get OCaml set up

Materials in Software Setup on the course webpage
Reach out on the discussion board if you need help
Part of 341 and CSE is developing skills to quickly become productive in new environments

Homework 0 due Friday at 5PM
Homework 1 is posted

You can start the first few problems after today

I forgot to mention the Reading Notes for [most?] units

3 of 35

Syntax + Semantics

Syntax: how programs are written down

Roughly “spelling and grammar”

Semantics: what programs mean

Type checking : compile time (aka “static”) semantics
Evaluation : run time (aka “dynamic”) semantics

Both syntax and semantics matter

341’s view ≈ “Semantics give the essence of a PL. Syntax is more about taste.”

4 of 35

Why Two Semantics?

Type checking (static semantics) first makes a guarantee (proves invariant!)

Happens before a program starts to run

Evaluation (dynamic semantics) then runs the program

Because program type checks, many run-time errors impossible
Example: 1 + “hello”

There is no dynamic semantics for this [non-]program
We don’t care! Will never try to run a program that would evaluate such an expression

5 of 35

ML Carefully So Far

A program is just a sequence of bindings
Typecheck each binding in order

Using static environment from previous bindings

Evaluate each binding in order

Using dynamic environment from previous bindings

So far, only variable bindings

More kinds of bindings coming soon!

6 of 35

Expressions

Many kinds of expressions in OCaml

34 true xyz
e1 + e2 e1 < e2 if e1 then e2 else e3

Recursively defined → can be arbitrarily large

Expressions can have subexpressions that have subsubexpressions that have …

7 of 35

Defining Expressions: Syntax, Typing, Evaluation

Syntax : how to write down that kind of expression (keywords, etc.)
Semantics : what that kind of expression means

Type checking rules (“static semantics”)

Produces a type or reports an error

Evaluation rules (“dynamic semantics”)

Produces a value (or runs forever or raises an exception)
Only defined for well-typed expressions!

Systematic approach to defining / understanding programming languages!

8 of 35

Values

All values are expressions

But not all expressions are values!

Values are the “answers” returned by evaluation

A value always evaluates to itself immediately

Examples

12 27 13 are values of type int
true false are (the only) values of type bool

Expressions

Values

9 of 35

Variables

Syntax: sequence of letters, numbers, _, or ‘

Must start with a letter or _

Type Checking

Look up in current static environment
If found, return corresponding type
Else fail

Evaluation

Look up in current dynamic environment
Return corresponding value

Why no “else” case?

Type checking ensures variable always bound!

10 of 35

Addition

Syntax: e1 + e2

Where e1 and e2 are expressions

Type Checking

If has e1 has type int and e2 has type int
Then e1 + e2 has type int
Else, report error and fail

Evaluation

If e1 evaluates to value v1 and e2 evaluates to value v2
Then e1 + e2 evaluates to the sum of v1 and v2

But what if e1 or e2 do not evaluate to ints?

Type checking ensures they will be ints!

11 of 35

Comparison (less than)

Syntax: e1 < e2

Type Checking

Evaluation

12 of 35

Comparison (less than)

Syntax: e1 < e2

Where e1 and e2 are expressions

Type Checking

Evaluation

13 of 35

Comparison (less than)

Syntax: e1 < e2

Where e1 and e2 are expressions

Type Checking

If has e1 has type int and e2 has type int
Then e1 < e2 has type bool
Else, report error and fail

Evaluation

14 of 35

Comparison (less than)

Syntax: e1 < e2

Where e1 and e2 are expressions

Type Checking

If has e1 has type int and e2 has type int
Then e1 < e2 has type bool
Else, report error and fail

Evaluation

If e1 evaluates to value v1 and e2 evaluates to value v2
Then e1 < e2 evaluates to true if v1 is less than v2, and false otherwise

15 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Type Checking

Evaluation

16 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Where e1, e2, and e3 are expressions

Type Checking

Evaluation

17 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Where e1, e2, and e3 are expressions

Type Checking

If has e1 has type bool and e2 and e3 have the same type t
Then if e1 then e2 else e3 has type t
Else, report error and fail

Evaluation

18 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Where e1, e2, and e3 are expressions

Type Checking

If has e1 has type bool and e2 and e3 have the same type t
Then if e1 then e2 else e3 has type t
Else, report error and fail

Evaluation

Both branches must have the same type!

19 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Where e1, e2, and e3 are expressions

Type Checking

If has e1 has type bool and e2 and e3 have the same type t
Then if e1 then e2 else e3 has type t
Else, report error and fail

Evaluation

If e1 evaluates to true, then return result of evaluating e2
If e1 evaluates to false, then return result of evaluating e3

20 of 35

Conditionals (if-then-else)

Syntax: if e1 then e2 else e3

Where e1, e2, and e3 are expressions

Type Checking

If has e1 has type bool and e2 and e3 have the same type t
Then if e1 then e2 else e3 has type t
Else, report error and fail

Evaluation

If e1 evaluates to true, then return result of evaluating e2
If e1 evaluates to false, then return result of evaluating e3

Only evaluate one of the branches!

Both branches must have the same type!

21 of 35

The Foundation We Need

Lots more types, expressions, and bindings

“Interesting” programs soon 😉

Syntax, type checking, and evaluation will continue to guide us

For HW1: functions, tuples, lists, options, local bindings
Earlier problems need fewer features

Will not need

Mutation (aka assignment): use recursion and/or new variables
Statements: use expressions
Loops: use recursion

22 of 35

Functions

Most important building block in the whole course

Functions let us abstract some computation by parameterizing over parts of an expression
Like Java methods, have arguments and result

But no classes, this, returns, etc.

Example function binding and function call

let max ((x:int),(y:int)) =

if x > y then x else y

max (3,17)

23 of 35

Example With Recursion

let rec pow ((x:int),(y:int)) =

if y = 0

then 1

else x * pow(x,y-1)

let cube (x:int) =

pow(x,3)

let sixtyfour = cube 4

let fortytwo = pow(2,4) + pow(4,2) + cube 2 + 2

24 of 35

Heads Up: Recursion!

If you’re not comfortable with recursion yet, you will be soon 😉

We’ll write many recursive functions in lecture and homework
Mostly over recursive data structures like lists (next lecture)

“Makes sense” because recursive calls solve “simpler” problems
Recursion “more general” than loops

We won’t write a single loop in OCaml
Easy to simulate loops with recursion
Loops often (not always) obscure simple, elegant solutions

25 of 35

Six questions

Three questions for a new language construct:

syntax, typing rules, evaluation rules

We have two new language constructs:

function bindings, function calls

26 of 35

Function Bindings

Syntax, with or without rec:

let f ((x1 : t1),…,(xN : tN)) = e

let rec f ((x1 : t1),…,(xN : tN)) = e

Where:

f, x1, …, xN are variable names
t1, …, tN are types
e is an expression

27 of 35

Meta-syntax

We use [...] to indicate some syntax is optional

Like rec
So the syntax for function bindings is

let [rec] f ((x1 : t1),…,(xN : tN)) = e

But the presence/absence of rec does matter

It affects the typing rules and evaluation rules!
Just saying it is correct function-binding syntax with or without it

28 of 35

Actually

This is a simplified-for-now syntax story:

Can write the return type if you want (example code won’t): let [rec] f ((x1 : t1),…,(xN : tN)) : t = e
Can omit argument types (and we will after Homework 1): let [rec] f (x1,…,xN) = e
Will see a different, more common, way to do multiple arguments later

Note: Be careful on argument syntax -- slight errors produce strange messages or behavior

29 of 35

Function Bindings: Type Checking

let [rec] f ((x1 : t1),…,(xN : tN)) = e

If has e has type t in the static environment containing:

The “enclosing” (up to this point) static environment
x1 ↦ t1, …, xN ↦ tN arguments and their types
If “rec” is given, f ↦ t1 * … * tN -> t

Then add f ↦ t1 * … * tN -> t to the static environment

Else, report error and fail

30 of 35

Function Bindings : Need Function Types!

New kind of type! f : t1 * … * tN -> t
Argument types t1, …, tN separated by *
Result type t after the arrow

How this is used for type-checking function bindings:

f has this type in the rest of program (not in earlier bindings!)
Arguments available in e, but not after (unsurprising)
Calling f evaluates e, so return type of f is type of e
“Magic” for now (study in a few weeks!):

Type-checker figures out t even when f is recursive

31 of 35

Function Bindings: Evaluation Rules

let [rec] f ((x1 : t1),…,(xN : tN)) = e

Evaluation rules:

Nothing to do! Function are values!

Real story a bit more nuanced, but we will get to it 😉

Add f to the dynamic environment so later expressions can call

f is bound to the function being defined here

And for recursion, if rec is present, then f also bound within e

32 of 35

Function Calls

Syntax: f (e1,…, eN)

Where f, e1, …, eN are expressions

(will generalize this a bit later)

Type Checking:

If:

f has type f : t1 * … * tN -> t
e1 has type t1
…
eN has type tN

Then f (e1,…, eN) has type t

33 of 35

Function Calls

e0 (e1,…, eN)

Evaluation

Evaluate e0 in current dynamic environment

Since e0 type checked, the result will be a function
So the result is some let [rec] f ((x1:t1),…,(xN:tN)) = e

In current dynamic environment, evaluate e1 to value v1, … , eN to value vN
The e0 (e1,…, eN) call now evaluates to the result of evaluating e

In an extended dynamic environment with x1 ↦ v1, …, xN ↦ vN

Technically: extend dynamic environment where f was defined.

But more on this later!

34 of 35

Heads Up: Function Gotchas

Be careful with argument declaration and argument passing

Else confusing error messages

Remember: cannot refer to later bindings

So helper functions must come first
Mutual recursion is handled specially

35 of 35

So much power in 6 questions

Three questions per language construct: syntax, typing rules, evaluation rules

Two new language constructs: function bindings, function calls

Most important building block in the entire course

let rec pow ((x:int),(y:int)) =

if y = 0

then 1

else x * pow(x,y-1)

let cube (x:int) =

pow(x,3)

let sixtyfour = cube 4