1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
# Spørgsmål
## Scheme Del
- Er `number?` ikke en higher order function
## Alt Andet
# Mixed
*Parameters* is in the declaration, and *arguments* are the things actually passed.
## Rewriting Rules
**Alpha** is when the parameters of an expression are renames to a otherwise free name.
**Beta** is the most important as it describes the application of functions.
Here we replace the abstraction like `(lambda ...)` or `sum` and replace it with the body.
The arguments are placed in the body according to the parameters.
**Eta** says that functions that just pass arguments to other functions can be substritued by its body.
# Scheme lek. 1
Programming paradigm
: A pattern that serves as a *school of through* for programming.
Programming technique
: Related to how a problem is solved, one example being divide and conquer.
Programming style
: How to express ourselves with a programming language, relating to elegance and coding style.
Programming culture
: A combination of paradigm, styles, and techniques. Often related to a family of programming langauges.
## Imperative Programming
An incremental change of programming state over time, through an execution of computations is steps.
Very similar to normal recipies such as food etc.
Abstraction for a traditional Von Neumann computer.
## Object Oriented Programming
OOP tries to model after the real world and the human interaction with it.
Here data is *encapsulated* in objects, thereby giving a sense of *information hiding*.
This internal data or the object state is then changes by commands or methods, which are called with *message passing*.
Objects are then grouped in classes, which represent concepts.
Classes are organized with *inheritance* hierachies.
## Functional Programming
Different from imperative programming in that data is unmutable, thereby relying on copies.
Also times plays an very minor role.
### Types Functional Programming
Comes in a typed variant, where every expressions have a vel defined type.
These types can be found *type inference*.
Often provides very powerfull type systems.
## Logic Programming
Very different from all the other in that it is based on mathematical logic (predicate logic).
Here we define the properties of a solution, and not how it is found.
Thereby the language implementation finds the best algorithm and data-structured to use.
## Self-Evaluating
Anything that is not a list or a symbol.
Thus anything that just evaluates to itself such as the string "foo".
For example if the variable `v` maps to `"v"`, does not mean that `v` is self evaluating.
This is becuase `v` and `"v"` is not the same.
Numbers and strings are self-evaluated.
# Scheme lek.2
Referential transparency
: Hvis to expressions er lig hinnanden, kan de også udbyttes med hinnanden.
## Y Combinator
How do we encode loops in lambda calculus.
A loop is something that does nothing but run itself.
```
loop = (x: x x) (x: x x)
```
Her kan vi se at hvis vi tager og applier den anden function is den første, får vi det samme som der var før.
Man kan derfor blive ved med at apply for evigt.
We want to define a general recursive, which we can use to define any recursive function.
Such a function would look like:
```
rec f = f(rec f)
```
Unwinding this will apply the function f infinitely.
Thus we want to encode `rec` without recursion.
The factorial function can then be written as.
```
fac = rec (f: n: if (n == 1) 1 (n * (f (n-1))))
```
Therefore `n * (f (n-1))` is therefore the non recursive part of factorial.
`rec` can be defined with.
```
rec = f: (x: (f x x)) (x: (f x x))
```
This is *y-combinator*.
# Scheme lek.3
Trampolining
: Run multiple computations "simutaniusly" by jumping back and fourth.
## Continuation Passing Style
This is where the return value of a function is parsed to another function instead of returning.
```lisp
(define (add a b k)
(k (+ a b)))
```
This has several advantages:
- Function in CSP are always tail recursive.
- Function in CSP do not need call/cc.
## Meta-Circular Scheme Interpreter
A interpreter written in scheme itself instead of another language like C.
# Scheme lek.4 Evaluation Ordering
It should not matter in which order we apply reductions, as we should always come to the same value or results.
However it may be possible for orderins to newer come to a conclusions, but instead do infinite loops.
**Normal Form** is an expression is on normal when it cannot be reduced further by the use of eta or beta reduction.
Intuitively this is the value of an expression.
A normal form of an expression is unique, however some expressions do not have a normal form.
**Weak Head Normal Form** is close to normal form.
However it is not explained further in the slides.
## Normal Order
Is where the outer leftmode reduction is done first.
Therefore doing an *evaluation by need*.
**Lazy evaluation** is an implementation of normal order reduction, which avoid repeated calculations of subexpressions.
## Applicative Order
The innermost reduction is done first, implementing an *eager evaluation*.
## Church Rosser Statements
> If `e1 <=> e2` then there exists an e3 such that `e1 <=> e3` and `e2 <=> e3`.
Dette betyder at beta og eta conversion er *confluent*.
> If `e0 => ... => en` and `en` is on normal form, then there exists a normal order reduction from `e0` to `en`.
Therefore normal order is the post powerful reduction
## Scheme Delayed Evaluation
`(delay expr)` is used to delay the evaluation of `expr`, by returning a promise.
The value of this can then be extracted with `(force promise)`.
|
