# Lecture 1

###### tags: `PSD`

## Chapter: introduction

- object language is a language we study (c++, latin)
- meta language is the language in which we conduct our discussions (Danish, english)

**Expressions without variables**
first let us consider expressions consisting only of integers constants and two arguments (dyadic) operators (+) and (*)

type expr =
    |CstI of int 
    |Prim of string * expr * epxr

A value of type expr is an *abstract syntax tree* that represents an expression.

| Expression | Representation |
| ---------- |:--------------------------------------------- |
| 17 | CstI 17 |
| 3-4 | Prim("-", CstI 3, CstI 4) |
| 7*9+10 | Prim("+", Prim("*", CstI 7, CstI 9), CstI 10) |

An expression can be evaluated to an integer by a function *eval : expr -> int*

let rec eval (e:expr) : int =
    match e with 
    |CstI i            -> i
    |Prim("+", e1, e2) -> eval e1 + eval e2
    |Prim("-", e1, e2) -> eval e1 - eval e2
    |Prim("*", e1, e2) -> eval e1 * eval e2
    |_                 -> failwith "unknown primitive"

The eval function is an *interpreter* for "programs" in the expression language.

**Expressions with Variables**

We extend our expression language with variables such as *x* and *y*.

type expr =
    |CstI of int 
    |Var of string
    |Prim of string * expr * epxr

| Expression | Representation |
| ---------- |:---------------------------------------------- |
| 17 | CstI 17 |
| x | Var "x" |
| 3+a | Prim("+", CstI 3, Var "a") |
| b*9+a | Prim("+", Prim("*", Var "b", CstI 9), Var "a") |

We also need to extend our interpreter of expressions: The eval function.

We do this by giving eval an extra arguement (env).
an environment.

The role of the environment is to associate a value with a variable. It is a map/dictionary.

(string * int)
let env = [("a", 3); ("c", 78); ("baf", 666); ("b", 111)];;

An empty invironment, which does not map any variable to anything is represented by the empty aossociation list.

let emptyenv = [];;

The function *lookup: (stirng * int) list -> string -> int* look up a variable in an environment.

let rec lookup env x = 
    match env with 
    |[]        -> failwith (x + "not found")
    |(y, v)::r -> if x=y then v else lookup r x;; 

Our new eval function which takes an expression and an environment.
It uses the lookup function to determine the value of a variable or failes.

let rec eval (e:expr) (env: (string * int) list) : int =
    match e with 
    |CstI i            -> i
    |Var x             -> lookup env x
    |Prim("+", e1, e2) -> eval e1 env + eval e2 env
    |Prim("-", e1, e2) -> eval e1 env - eval e2 env
    |Prim("*", e1, e2) -> eval e1 env * eval e2 env
    |_                 -> failwith "unknown primitive"

The lookup function will return the first value associated with a variable.
if env is ```F# [("x", 11); ("x",22)];;```
then ```F# lookup env "x"```is 11 and not 22.

**Syntax and Semantics**

two kinds of syntaxs
1. Concrete syntax
2. Abstract syntax

two kinds of semantics
1. Dynamic semantics
2. Static semantics

## Chapter 2: Interpreters and Compilers

**Interpreter & compilers**
An *interpreter* executes a program on some input --> producing an output/result.
It is usaually itself a program.

For any interpreter we must distinguish the interpreted language L from the implementation language I.
L = language of the program being executed. e.g. expr
I = language in which the interpreter is written e.g. F#)

The interpreter is often called an abstract machine or virtual machine.

A *compiler* takes an input from a source program and generates as output another program (target program) that can be executed.
For any compiler we must distinguish three languages
1. the source language S (e.g. expr) of the input program
2. The target language T (e.g. texpr) of the output program
3. the implementation language I (e.g. F#) of the compiler itself.

The compiler does not execute the program.
After the target program as been generated it must be executed by a machine or interpreter which can execute program written in language T.

Here we can distinguish between
- compile-time
- (what time the source program is compiled into target program) and
- run-time
- (what time the target program is executed on actual inputs to produce a result).


**Scope and Bound and Free variables**

The *scope* of a variable is that part of a program which it is visible.

let f x = x + 3

the scope of x in this F# function is definition is just the function body x+3.

A language is *static scoped* if the scope of the bindings follow the syntactic structure of the program.
// Hvad betyder det helt konkret?

A language is *nested scope* if an inner scope may create a "hole" in an outer scope by declaring a new variable with the same name.

let f x = (let x = 8 in x * 2) + (x+3)

Here the second binding of x hides the first one in x*2 but not in x+3 so f(1) = (8*2)+(1+3)=20

A variable is *bound* if it occurs within the scope of a binding for that variable and *free* otherwise.

**Expressions with Let-bindings and Static Scope**

We add the let-binding to our language expr

type expr =
    |CstI of int 
    |Var of string
    |Let od string * expr * epxr
    |Prim of string * expr * epxr

We can use the same lookup function as earlier.
We can evaulate ```let x = erhs in ebody end```as follows
1. evaulate the right-hand side erhs in the same env as the entire let-binding.
2. obtain the value xval for x
3. create a new environment env1 by adding the association (x,xval) and interpret the let-body ebody in that env.
4. return the same result as the result of the let-binding

let rec eval (e:expr) (env: (string * int) list) : int =
    match e with 
    |CstI i               -> i
    |Var x                -> lookup env x
    |Let (x, erhs, ebody) ->
        let xval = eval erhs env
        let env1 = (x,xval)::env
        eval ebody env1
    |Prim("+", e1, e2)    -> eval e1 env + eval e2 env
    |Prim("-", e1, e2)    -> eval e1 env - eval e2 env
    |Prim("*", e1, e2)    -> eval e1 env * eval e2 env
    |_                    -> failwith "unknown primitive"

**Closed expressions**
An expression is closed if no variable occurs free in the expression.

To test if an expression is closed see page 16 in the book for the code.

A constant is always closed.
A varible occurrence x is closed in vs if x appears in vs.

**Integer addresses instead of names**

For effeiciency, symbolic variables names are replaced by variable addresses in real machine code and most interpreters.

type texpr =
    |TCstI of int 
    |TVar of int 
    |TLet of texpr * texpr
    |TPrim of string * texpr * tepxr

we define an abstract syntax texpr for target expressions that uses integer variables indexes.

Now we can define tcomp : expr -> string list -> texpr
A compiler from expr to texpr.

let rec tcomp (e: expr) (cenv: string list) : texpr =
    match e with
    |CstI i -> TCstI i
    |Var x -> TVar (getindex cenv x)
    |Let (x, erhs, ebody) -> 
        let cenv1 = x::cenv
        TLet(tcomp erhs cenv, tcomp ebody cenv1)
    |Prim(ope, e1, e2) -> 
        TPrim(ope, tcomp e1 cenv, tcomp e1 cenv)

**Stack machines for expression evaluation**

Expression/functional programs are often evaluated by a stack machine.
A stack machine = an interpreter that implements an abstract machine.