---
# System prepended metadata

title: Programmer som Data
tags: [PSD]

---

# 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 (*) 

```F# 
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*

````F#
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*. 


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

```F#
(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.
```F#
let emptyenv = [];;
```

The function *lookup: (stirng * int) list -> string -> int* look up a variable in an environment. 
```F#
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. 

````F#
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).

![](https://i.imgur.com/1E7uEoJ.png)


**Scope and Bound and Free variables**

The *scope* of a variable is that part of a program which it is visible. 
```F# 
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. 
```F#
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

```F# 
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

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

![](https://i.imgur.com/uwhNbcr.png)

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

![](https://i.imgur.com/UIwH9OI.png)

After this then the nonterminal Main is the start symbol. And gives rules to both nonterminals
Main and Expr ![](https://i.imgur.com/YD0QgcD.png)
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. 

![](https://i.imgur.com/f3ZmVmz.png)

**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**
```F#
    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

