# Programmer som Data

###### tags: `PSD`

## Lecture 1

### 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.

## Lecture 2

### Chapter 3: From Concrete Syntax to abstract syntax

**Lexers, Parsers and Generators**

A *lexer* or *scanner* is a program that reads characters from a text file and assembles them into a stream of *lexical tokens or lexemes*.
It usually ignores the amount of whitespace, carriage returns, tabulation characters and page breaks between non-black symbols.

A *parser* is a program that accepts a stream of lexical tokens from a lexer, and builds an abstract syntax tree (AST) representing that stream of tokens.

A *lexer generator* is a program that convets a parser specification into a lexer (which recognizes tokens described by the regular expression)
// fslex

A *parser generator* is a program that converts a parser specification into a parser.
// fsyacc


This is a bottom-uo parser: LR parser.
characterized by reading characters from the Left and making derivations from the Right-most nonterminal.

**Grammars in parser specifications**

A context free grammar has four components:
1. terminal symbol: e.g. x, 12, "foo"
2. nonterminal symbol: A
3. start symbol: S
4. grammar rules or productions of the form A::= tnseq. where tnseq is a sequence of terminal/nonterimal symbols.

An informal grammar for our expression language

Expr ::= NAME
     |INT
     |- INT 
     |(Expr)
     |let NAME = Expr in Expr end
     |Epxr * Expr
     |Epxr + Expr
     |Epxr - Expr

**Parser specification for expressions**
A complete parser specification for the expression language is found in Exprpar.fsy

First it declares the tokens/terminal symbolsm CSTINT, NAME, and so on...
followed by a declaration of operators associativity and precedence.


After this then the nonterminal Main is the start symbol. And gives rules to both nonterminals
Main and Expr 
The expressions in curly braces on the right describe what result will be produced by a succesful parse.

The purpose of parsing is to produce an abstract syntax representation by reading a text file (concrete syntax)

To summarize, the curly braces contain F# expressions that produce the result of a successful parse. They are sometimes called semantic actions.

### BCD
This is about the math behind.
See dmat notes instead.

## Lecture 4

## Chapter 4: First-order functional language

A functional programming language is one in which the evaluation of expressions and function calls the primary means of computation.


**Examples and abstract syntax**

we will extend our expression language.

two examples:

Prim("+", Var "z", CstI 8)

Letfun("f", "x", Prim("+", Var"x", CstI 7), Call(Var "f", CstI 2))

The component of a function binding Letfun (f, x fbody, letBody) in have the concrete syntax let f x = fbody in letBody end

f is the function name
x is the parameter name
fBody is the function body, or function right-hand side
letBody is the let-body

**Run-time values: integers and closures**

A function closure is a tuple (f, x, fbody, fDeclEnv) consisting of the name of the function, the name of the function parameter, the function body expression and the function declaration environment.

**A simple environment implementation**

    type 'v env = (string * ´v) list;;

we will use a simple environment representation: a list of pairs where each pair (k,d) contains a key k and some data d.

### Lecture notes from slides

**LR versus LL parsing**

LR:
- read input from Left to right, make derivations from Rightmost nonterminal
- buttom-up parsing
- difficult to hand-write parsers
- no grammar transformation required.

LL:
- read input from Right to left, make derivations from Leftmost nonterminal
- top-down parsing

**Parser state **

## Higher-order functions

## Lecture 7

### Chapter 7: Impereative Language