edu-fp

# Функциональное программирование

## Лекция 6-7

## Элементы неполной <br/> и в основном неверной истории языков программирования. <br/> Лямбда-исчисление

Пенской А.В., 2024

----

## План лекции

- Элементы неполной и в основном неверной истории языков программирования
    - Машина Тьюринга, Машина фон Неймана
    - Лямбда-исчисление
- Языки программирования высокого уровня
    - Структурное программирование.
    - Go To считать вредным
    - Нарушения структуры.
    - Объектно-ориентированные языки программирования
    - "Новинки"
- Законы развития (в том числе и технологий)
    - Диалектика Гегеля
    - Принцип развития иерархических систем Седова

---

## Вопрос на подумать

Возможно ли обойти произвольное бинарное дерево <br/> в $O(1)$ по памяти?

```c
struct BTree {
    BTree * left;
    BTree * right;
    int value;
}
```

----

![](figures/btree-in-memory.png)

[Обход бинарного дерева с константным количеством памяти](http://amazing-new-gate.blogspot.com/2010/06/blog-post_30.html) <br/> (Java, Smalltalk)

---

## Элементы неполной <br/> и в основном неверной истории языков программирования

*Disclaimer*:

- только элементы общей логики
- в основном mainstream
- голословно

---

## Машина Тьюринга

Машина Тьюринга включает:

- неограниченная двусторонняя лента, разделенная на ячейки
- устройство управления (головка записи-чтения), которое может находиться в конечном числе состояний.

Управляющее устройство может:

- перемещаться по ленте влево и вправо,
- читать и записывать в ячейки символы некоторого конечного алфавита.

</div><div class="col">

(императивное программирование)

![](figures/turing_machine_model_davey_2012.jpg)

</div></div>

----

1. обладает полнотой по Тьюрингу
2. не может быть реализована на практике
3. проблема остановки
4. данные и управление отделены
5. ориентирована на реализацию

----

### Машина фон Неймана

- Логическое развитие машины Тьюринга.
- Ключевые отличия:
    - адресация памяти
    - унифицированное представление/хранение инструкций/данных
    - много инструкций:
        - работа с памятью
        - арифметические и логические операции
        - управляющие операции

</div><div class="col">

![](figures/von-neumann.png)

</div></div>

----

### Пример программы

Программа — последовательность инструкций в памяти.

```text
| Address | Mnemonic       | Comment                                   |
| ------- | -------------- | ----------------------------------------- |
| 0400    | MOV CX, [0500] | CX <- [0500] ............................ |
| 0404    | MOV AX, 0001   | AX <- 0001 .............................. |
| 0407    | MOV DX, 0000   | DX <- 0000 .............................. |
| 040A    | MUL CX         | DX:AX <- AX * CX ........................ |
| 040C    | LOOP 040A      | Go To [040A] ............................ |
|         |                |   till CX->00 (CX <- CX - 1 on each step) |
| 0410    | MOV [0600], AX | [0600] <- AX ............................ |
| 0414    | MOV [0601], DX | [0601] <- DX ............................ |
| 0418    | HLT            | Stop Execution .......................... |
```

Факториал.

----

### Пример процесса

Процесс — очерёдность смены состояний процессора по мере выполнения команд.

Входные данные по адресу `0500` равны 3, выходные данные будут сохранены по адресам `[0600, 0601]`):

```text
1. {AX: -, CX: -, DX: -} Выполняется 0400 | MOV CX, [0500]
2. {AX: -, CX: 3, DX: -} Выполняется 0404 | MOV AX, 0001
3. {AX: 1, CX: 3, DX: -} Выполняется 0407 | MOV DX, 0000
    3.1. {AX: 1, CX: 3, DX: 0} Выполняется 040A | MUL CX
    3.2. {AX: 3, CX: 3, DX: 0} Выполняется 040C | LOOP 040A
                               CX не равно 0, переходим 040A.
    3.3. {AX: 3, CX: 2, DX: 0} Выполняется 040A | MUL CX
    3.4. {AX: 6, CX: 2, DX: 0} Выполняется 040C | LOOP 040A,
                               CX не равно 0, переходим 040A
    3.5. {AX: 6, CX: 1, DX: 0} Выполняется 040A | MUL CX
    3.6. {AX: 6, CX: 1, DX: 0} Выполняется 040C | LOOP 040A,
                               после декремента CX равно 0,
                               выполняем следующую инструкцию.
4. {AX: 6, CX: 0, DX: 0} Выполняется 0410 | MOV [0600], AX
5. {AX: 6, CX: 0, DX: 0} Выполняется 0414 | MOV [0601], DX
6. Выполняется 0418 | HTL, Остановить выполнение
```

----

1. Низкоуровневый язык программирования.
1. Зоопарк процессорных архитектур. Приоритет: простота и надёжность аппаратуры, ручная оптимизация.
1. Макроассемблер + кодогенерация.
1. Непереносимый код.
1. Неумение писать [оптимизирующие] компиляторы.

![](figures/forth.png)

---

## Лямбда-исчисление

Делали математики для математиков.

"Ненужно, так как не обладает C-подобным синтаксисом."

<dl>
  <dt> Lambda-calculus </dt>
  <dd>  is a way to represent a specific state of the computational process in the symbolic form or lambda-term. These terms are built up from variables and constants using function application and lambda abstraction operations. </dd>
</dl>
 
</div><div class="col">

![](figures/l-lambda.png)

</div></div>

Source: [John Harrison, Introduction to Functional Programming](https://www.cl.cam.ac.uk/teaching/Lectures/funprog-jrh-1996/all.pdf)

----

### Lambda-term

Every lambda term related to one of the following categories:

1. Arbitrary alphanumeric strings index represents **Variables**.
    - E.g., $x$, $y$, and $z$.
2. **Constants** also denote them by alphanumeric strings, leaving context to determine when they are meant to be constants.
    - E.g., $a$, $b$, $c$.
3. **Combinations** or function **application** ($s$ to an argument $t$; both these components $s$ and $t$ may themselves be arbitrary $\lambda$-terms.
    - E.g. $s\\;t$.
4. **Abstractions** of an arbitrary $\lambda$-term $s$ over a variable $x$ (which may or may not occur free in s).
    - E.g. $\lambda x.s$.

----

### Free and Bound Variables

We will denote the set of free variables in a term $s$ by $FV(s)$, and define it by recursion as follows:

- $FV(x) = \{x\}$
- $FV(c) = \emptyset$
- $FV(s\\;t) = FV(s) \cup FV(t)$
- $FV(\lambda x.s) = FV(s) - \{x\}$

Similarly we can define the set of bound variables in a term $BV(s)$:

- $BV(x) = \emptyset$
- $BV(c) = \emptyset$
- $BV(s\\;t) = BV(s) \cup BV(t)$
- $BV(\lambda x.s) = BV(s) \cup \{x\}$

----

### Lambda-term substituting

- $*[t/x]$ — substituting $x$ by $t$ in arbitrary term
- $x[t/x] = t$
- $y[t/x] = y$, if $x \ne y$
- $c[t/x] = c$
- $(s_1\\;s_2)[t/x] = s_1[t/x] \\; s_2[t/x]$
- $(\lambda x.s)[t/x] = \lambda x.s$
- $(\lambda y.s)[t/x] = \lambda y.(s[t/x])$, if $x \ne y$ and either $x \notin FV(s)$ or $y \notin FV(t)$
- $(\lambda y.s)[t/x] = \lambda z.(s[z/y][t/x])$, otherwise, where $z \notin FV(s) \cup FV(t)$

----

### Conversions of Lamda-terms

- **Alpha conversion**: $\lambda x.s \xrightarrow{\alpha} \lambda y.s[y/x]$ provided $y \notin FV(s)$.
    - E.g. $\lambda u.u\\;v  \xrightarrow{\alpha} \lambda w.w\\;v$.
- **Beta conversion**: $(\lambda x.s)\\;t \xrightarrow{\beta} s[t/x]$.
- **Eta conversion**: $\lambda x.t\\;x \xrightarrow{\eta} t$  provided $x \notin FV(t)$.
    - E.g. $\lambda u.v\\;u  \xrightarrow{\eta} v$.

----

### Reduction Order

<dl>
  <dt> Normal-order reduction </dt>
  <dd>  is the strategy in which one continually applies the rule for β-reduction in head position until no more such reductions are possible. At that point, the resulting term is in head normal form. One then continues applying a reduction in the subterms from left to the right. </dd>
</dl>
 
<dl>
  <dt> Applicative order reduction </dt>
  <dd>  one applies the internal reductions first and then only applies the head reduction when no more internal reductions are possible. </dd>
</dl>
 
Applicative order reduction may not terminate:

- $(\lambda x . y) \\; ((\lambda x.x \\; x \\; x) \\; (\lambda x .x \\; x \\; x))$
- $\rightarrow (\lambda x . y) \\; ((\lambda x . x \\; x \\; x) \\; (\lambda x . x \\; x \\; x) \\; (\lambda x . x \\; x \\; x))$
- $\rightarrow (\lambda x . y) \\; ((\lambda x . x \\; x \\; x) \\; (\lambda x . x \\; x \\; x) \\; (\lambda x . x \\; x \\; x) \\; (\lambda x . x \\; x \\; x))$
- $\rightarrow ...$

---

## Lambda-Calculus as a Programming Language

Lambda-calculus, with a little syntax sugar, allows us to resolve some computational tasks.

For that, they define:

1. truth values and the conditional statement
2. pairs and tuples
3. the natural numbers
4. recursive functions
5. $let$ expressions.

----

### Boolean and If Statement

$true \equiv \lambda x\\;y . x$

$false \equiv \lambda x\\;y . y$

$if \\; E \\; then \\; E_1 \\; else \\; E_2 \equiv E \\; E_1 \\; E_2$

How it works:

- $if \\; true \\; then \\; E_1 \\; else \\; E_2$
- $= true \\; E_1 \\; E_2$
- $= (\lambda x \\; y . x) \\; E_1 \\; E_2$
- $= E_1$

</div><div class="col">

And basic logic functions:

$not \\;p \equiv if \\; p \\; then \\; false \\; else \\; true$

$p \\; and \\; q \equiv if \\; p \\; then \\; q \\; else \\; false$

$p \\; or \\; q \equiv if \\; p \\; then \\; true \\; else \\; q$

</div></div>

----

### Pairs

$(E_1, E_2) \equiv \lambda f . f \\; E_1 \\; E_2$

$fst \\;p \equiv p \\; true$

$snd  \\;p \equiv p \\; false$

How it works:

- $fst \\; (p, q) = (p, q) \\; true$
- $= (\lambda f . f \\; p \\; q) \\; true$
- $= true \\; p \\; q$
- $= p$

----

### Natural Numbers

$n \equiv \lambda f \\; x . f^n \\; x$

</div><div class="col">

- $0 = \lambda f \\; x . x$
- $1 = \lambda f \\; x . f \\; x$
- $2 = \lambda f \\; x . f \\; (f \\; x) = \lambda f \\; x . f^2 \\; x$

</div></div>

And some arithmetic functions:

$SUC \equiv \lambda n \\; f \\; x . n \\; f \\; (f \\; x)$

$ISZERO \\; n \equiv n \\; (\lambda x . false) \\; true$

$m + n \equiv \lambda f \\; x . m \\; f \\; (n \\; f \\; x)$

$m * n \equiv \lambda f \\; x . m \\; (n \\; f) \\; x$

$PREFN \equiv \lambda f \\; p . (false, if \\; fst \\; p \\; then \\; snd \\; p \\; else \\; f \\; (snd \\; p))$

$PRE \\;n \equiv \lambda f \\; x . snd \\; (n, (PREFN \\; f) \\; (true, x))$

----

### Recursive functions

$Y \equiv \lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f \\; (x \\; x))$

How it works:

- $Y \\; f = (\lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f(x \\; x)))$
- $= (\lambda x . f \\; (x \\; x))(\lambda x . f \\; (x \\; x))$
- $= f \\; ((\lambda x . f \\; (x \\; x))(\lambda x . f \\; (x \\; x)))$
- $= f \\; (Y \\; f)$

----

### Factorial

- $fact (n) = if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; fact \\; (PRE \\; n)$
- $fact = \lambda n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; fact \\; (PRE \\; n)$
- $fact = (\lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)) \\; fact$
- $F = \lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)$
- $fact = Y \\; F$

---

## Factorial Example

----

### Factorial: Iteration 1

1. $fact \\; 3 \xrightarrow{fact} Y \\; F \\; 3$
1. $\xrightarrow{Y} (\lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f \\; (x \\; x))) \\; F \\; 3$
1. $\xrightarrow{\beta} (\lambda x . F \\; (x \\; x)) (\lambda x . F \\; (x \\; x)) \\; 3$
1. $\xrightarrow{\beta} F \\; ((\lambda x . F \\; (x \\; x)) \\; (\lambda x . F \\; (x \\; x))) \\; 3$
1. $\xrightarrow{backward \\; \beta} F \\; (Y \\; F) \\; 3$
1. $\xrightarrow{F} (\lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)) \\; (Y \\; F) \\; 3$
1. $\xrightarrow{\beta} (if \\; ISZERO \\; 3 \\; then \\; 1 \\; else \\; 3 \\; * \\; (Y \\; F) \\; (PRE \\; 3))$
1. $\xrightarrow{ISZERO 3} (if \\; false \\; then \\; 1 \\; else \\; 3 * (Y \\; F) \\; (PRE \\; 3))$
1. $\xrightarrow{if} false \\; 1 \\; (3 * (Y \\; F) \\; (PRE \\; 3))$
1. $\xrightarrow{false} (\lambda x \\; y . y) \\; 1 \\; (3 * (Y \\; F) \\; (PRE \\; 3))$
1. $\xrightarrow{\beta} 3 * (Y \\; F) \\; (PRE \\; 3)
    \xrightarrow{PRE \\; 3} 3 * (Y \\; F) \\; 2$

----

#### $ISZERO \\; 3 \xrightarrow{} false$

1. $ISZERO \\; 3 \xrightarrow{ISZERO} 3 \\; (\lambda x . false) \\; true$
1. $\xrightarrow{number} (\lambda f \\; x . f^3 \\; x) \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false)^3 \\; true$
1. $\xrightarrow{number} (\lambda x . false) \\; (\lambda x . false)  \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false)  \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} false$

----

#### $PRE \\; 3 \xrightarrow{} 2$

1. $PRE \\; 3 \xrightarrow{PRE} \lambda f \\; x . snd(3 \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{number} \lambda f \\; x . snd( (\lambda f \\; x . f^3 \\; x) \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{\beta} \lambda f \\; x . snd( (PREFN \\; f)^3 \\; (true, x))$
1. $\xrightarrow{(PREFN \\; f)^3 \\; (true, x)}
       \lambda f \\; x . snd( (false, f^2 x) )$ `-- see below`
1. $\xrightarrow{snd} \lambda f \\; x . f^2 x$
1. $\xrightarrow{number} 2$

----

#### $(PREFN \\; f)^3 \\; (true, x) \xrightarrow{} (false, f^2 x)$

1. $(PREFN \\; f)^3 \\; (true, x)$
1. $\xrightarrow{power}
    PREFN \\; f \\; ((PREFN \\; f)^2 \\; (true, x))$
1. $\xrightarrow{(PREFN \\; f)^2 \\; (true, x)}
    PREFN \\; f \\; (false, f \\; x)$ `-- see below`
1. $\xrightarrow{PREFN}
              (\lambda f \\; p . (false, if \\; fst \\; p \\; then \\; snd \\; p \\; else \\; f \\; (snd \\; p))) \\\\
              f \\; (false, f \\; x)$
1. $\xrightarrow{\beta}
        (false, if \\; fst \\; (false, f \\; x) \\\\
        then \\; snd \\; (false, f \\; x) \\; else \\; f \\; (snd \\; (false, f \\; x))$
1. $\xrightarrow{snd . if . fst} (false, f \\; (f \\; x))$
1. $\xrightarrow{power} (false, f^2 x)$

---

### Factorial: Iteration 2

1. $3 * (Y \\; F) \\; 2$
    1. $(Y \\; F) \\; 2 \xrightarrow{Y} (\lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f \\; (x \\; x))) \\; F \\; 2$
    1. $\xrightarrow{\beta} (\lambda x . F \\; (x \\; x)) (\lambda x . F \\; (x \\; x)) \\; 2$
    1. $\xrightarrow{\beta} F \\; ((\lambda x . F \\; (x \\; x)) \\; (\lambda x . F \\; (x \\; x))) \\; 2$
    1. $\xrightarrow{backward \\; \beta} F \\; (Y \\; F) \\; 2$
    1. $\xrightarrow{F} (\lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)) \\; (Y \\; F) \\; 2$
    1. $\xrightarrow{\beta} (if \\; ISZERO \\; 2 \\; then \\; 1 \\; else \\; 2 \\; * \\; (Y \\; F) \\; (PRE \\; 2))$
    1. $\xrightarrow{ISZERO 2} (if \\; false \\; then \\; 1 \\; else \\; 2 * (Y \\; F) \\; (PRE \\; 2))$
    1. $\xrightarrow{if} false \\; 1 \\; (2 * (Y \\; F) \\; (PRE \\; 2))$
    1. $\xrightarrow{false} (\lambda x \\; y . y) \\; 1 \\; (2 * (Y \\; F) \\; (PRE \\; 2))$
    1. $\xrightarrow{\beta} 2 * (Y \\; F) \\; (PRE \\; 2)
    \xrightarrow{PRE \\; 2} 2 * (Y \\; F) \\; 1$
1. $3 * 2 * (Y \\; F) \\; 1$

----

#### $ISZERO \\; 2 \xrightarrow{} false$

1. $ISZERO \\; 2 \xrightarrow{ISZERO} 2 \\; (\lambda x . false) \\; true$
1. $\xrightarrow{number} (\lambda f \\; x . f^2 \\; x) \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false)^2 \\; true$
1. $\xrightarrow{number} (\lambda x . false) \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} false$

----

#### $PRE \\; 2 \xrightarrow{} 1$

1. $PRE \\; 2 \xrightarrow{PRE} \lambda f \\; x . snd(2 \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{number} \lambda f \\; x . snd( (\lambda f \\; x . f^2 \\; x) \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{\beta} \lambda f \\; x . snd( (PREFN \\; f)^2 \\; (true, x))$
1. $\xrightarrow{(PREFN \\; f)^2 \\; (true, x)}
       \lambda f \\; x . snd( (false, f \\; x) )$
1. $\xrightarrow{snd} \lambda f \\; x . f x$
1. $\xrightarrow{number} 1$

----

#### $(PREFN \\; f)^2 \\; (true, x) \xrightarrow{} (false, f \\; x)$

- $(PREFN \\; f)^2 \\; (true, x)$
- $\xrightarrow{power} PREFN \\; f \\; (PREFN \\; f \\; (true, x))$
- $\xrightarrow{(PREFN \\; f \\; (true, x))}
    PREFN \\; f \\; (false, x)$
- $\xrightarrow{PREFN}
              (\lambda f \\; p . (false, if \\; fst \\; p
              \\;\\; then \\; snd \\; p
              \\;\\; else \\; f \\; (snd \\; p))) \\\\
              f \\; (false, x)$
- $\xrightarrow{\beta}
        (false, if \\; fst \\; (false, x) \\;then \\; snd \\; (false, x) \\; else \\; f \\; (snd \\; (false, x)))$
- $\xrightarrow{snd . if . fst} (false, f \\; x)$

---

### Factorial: Iteration 3

1. $3 * 2 * (Y \\; F) \\; 1$
    1. $(Y \\; F) \\; 1 \xrightarrow{Y} (\lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f \\; (x \\; x))) \\; F \\; 1$
    1. $\xrightarrow{\beta} (\lambda x . F \\; (x \\; x)) (\lambda x . F \\; (x \\; x)) \\; 1$
    1. $\xrightarrow{\beta} F \\; ((\lambda x . F \\; (x \\; x)) \\; (\lambda x . F \\; (x \\; x))) \\; 1$
    1. $\xrightarrow{backward \\; \beta} F \\; (Y \\; F) \\; 1$
    1. $\xrightarrow{F} (\lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)) \\; (Y \\; F) \\; 1$
    1. $\xrightarrow{\beta} (if \\; ISZERO \\; 1 \\; then \\; 1 \\; else \\; 1 \\; * \\; (Y \\; F) \\; (PRE \\; 1))$
    1. $\xrightarrow{ISZERO 1} (if \\; false \\; then \\; 1 \\; else \\; 1 * (Y \\; F) \\; (PRE \\; 1))$
    1. $\xrightarrow{if} false \\; 1 \\; (1 * (Y \\; F) \\; (PRE \\; 1))$
    1. $\xrightarrow{false} (\lambda x \\; y . y) \\; 1 \\; (1 * (Y \\; F) \\; (PRE \\; 1))$
    1. $\xrightarrow{\beta} 1 * (Y \\; F) \\; (PRE \\; 1)
    \xrightarrow{PRE \\; 1} 1 * (Y \\; F) \\; 0$
1. $3 * 2 * 1 * (Y \\; F) \\; 0$

----

#### $ISZERO \\; 1 \xrightarrow{} false$

1. $ISZERO \\; 1 \xrightarrow{ISZERO} 1 \\; (\lambda x . false) \\; true$
1. $\xrightarrow{number} (\lambda f \\; x . f \\; x) \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} false$

----

#### $PRE \\; 1 \xrightarrow{} 0$

1. $PRE \\; 1 \xrightarrow{PRE} \lambda f \\; x . snd(1 \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{number} \lambda f \\; x . snd( (\lambda f \\; x . f \\; x) \\; (PREFN \\; f) \\; (true, x))$
1. $\xrightarrow{(PREFN \\; f)^ \\; (true, x)}
       \lambda f \\; x . snd( (false, x) )$
1. $\xrightarrow{snd} \lambda f \\; x . x$
1. $\xrightarrow{number} 0$

----

#### $PREFN \\; f \\; (true, x) \xrightarrow{} (false, f \\; x)$

- $PREFN \\; f \\; (true, x)$
- $\xrightarrow{PREFN}
        ((\lambda f \\; p . (false, if \\; fst \\; p \\; then \\; snd \\; p \\; else \\; f \\; (snd \\; p))) \\\\ f \\; (true, x))$
- $\xrightarrow{\beta}
        (false, if \\; fst \\; (true, x) \\; then \\; snd \\; (true, x) \\; else \\; f \\; (snd \\; (true, x)))$
- $\xrightarrow{true . if} (false, snd \\;  (true, x))$
- $\xrightarrow{snd} (false, x)$

---

#### Factorial: Iteration 4

1. $3 * 2 * 1 * (Y \\; F) \\; 0$
    1. $(Y \\; F) \\; 0 \xrightarrow{Y} (\lambda f . (\lambda x . f \\; (x \\; x)) (\lambda x . f \\; (x \\; x))) \\; F \\; 0$
    1. $\xrightarrow{\beta} (\lambda x . F \\; (x \\; x)) (\lambda x . F \\; (x \\; x)) \\; 0$
    1. $\xrightarrow{\beta} F \\; ((\lambda x . F \\; (x \\; x)) \\; (\lambda x . F \\; (x \\; x))) \\; 0$
    1. $\xrightarrow{backward \\; \beta} F \\; (Y \\; F) \\; 0$
    1. $\xrightarrow{F} (\lambda f \\; n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; f \\; (PRE \\; n)) \\; (Y \\; F) \\; 0$
    1. $\xrightarrow{\beta} (if \\; ISZERO \\; 0 \\; then \\; 1 \\; else \\; 0 \\; * \\; (Y \\; F) \\; (PRE \\; 0))$
    1. $\xrightarrow{ISZERO 0} (if \\; true \\; then \\; 1 \\; else \\; 0 * (Y \\; F) \\; (PRE \\; 0))$
    1. $\xrightarrow{if} true \\; 1 \\; (0 * (Y \\; F) \\; (PRE \\; 0))$
    1. $\xrightarrow{false} (\lambda x \\; y . x) \\; 1 \\; (0 * (Y \\; F) \\; (PRE \\; 0))$
    1. $\xrightarrow{\beta} 1$
1. $3 * 2 * 1 * 1$

----

#### $ISZERO \\; 0 \xrightarrow{} true$

1. $ISZERO \\; 0 \xrightarrow{ISZERO} 0 \\; (\lambda x . false) \\; true$
1. $\xrightarrow{number} (\lambda f \\; x . x) \\; (\lambda x . false) \\; true$
1. $\xrightarrow{\beta} true$

----

### Factorial: Fold Stack

1. $fact \\; 3 \xrightarrow{fact} 3 * 2 * 1 * 1$
    1. $3 * 2
        \xrightarrow{*} \lambda f \\; x . 3 (2 f) x
        \xrightarrow{number} \lambda f \\; x . (\lambda f \\; x . f^3 x) (2 f) x$
    1. $\xrightarrow{\beta} \lambda f \\; x . (2 f)^3 x
         \xrightarrow{number} \lambda f \\; x . ((\lambda f \\; x . f^2 x) f)^3 x$
    1. $\xrightarrow{\beta} \lambda f \\; x . ((\lambda x . f^2 x))^3 x
        \xrightarrow{\beta} \lambda f \\; x . (f^2)^3 x
        \xrightarrow{\beta} \lambda f \\; x . f^6 x$
    1. $\xrightarrow{number} 6$
1. $\xrightarrow{3*2} = 6 * 1 * 1$
    1. $6 * 1
        \xrightarrow{*} \lambda f \\; x . 6 (1 f) x
        \xrightarrow{number} \lambda f \\; x . (\lambda f \\; x . f^6 x) (1 f) x$
    1. $\xrightarrow{\beta} \lambda f \\; x . (1 f)^6 x
         \xrightarrow{number} \lambda f \\; x . ((\lambda f \\; x . f x) f)^6 x$
    1. $\xrightarrow{\beta} \lambda f \\; x . ((\lambda x . f x))^6 x
        \xrightarrow{\beta} \lambda f \\; x . f^6 x$
    1. $\xrightarrow{number} 6$
1. $\xrightarrow{6*1} = 6 * 1$
1. $\xrightarrow{6*1} = 6$

<!-- - $= (\lambda n . if \\; ISZERO \\; n \\; then \\; 1 \\; else \\; n \\; * \\; fact \\; (PRE \\; n))

(\lambda f \\; x . f \\; f \\; (f \\; x))$ -->

---

## Языки программирования высокого уровня

Высокий уровень это:

- абстрактный от процессора,
- но не всегда абстрактный от контроллера (процессор + периферия),
- cтруктурное программирование,
- декларативное прог. (что бы это не значило).

Изменчивое понятие, а не термин.

</div><div class="col">

![](figures/declarative-programming.png)

- Есть низкоуровневые языки с высокоуровневыми возможностями (Forth).

</div></div>

---

[Теорема Бёма — Якопини](https://ru.wikipedia.org/wiki/Теорема_Бёма_—_Якопини)

----

### Структурное программирование

Было: последовательность инструкций.

Стало: последовательность структурных блоков.

- одна точка входа

```haskell
    fac n = fac' n 1
    fac' n acc = undefined
    ```

- одна точка выхода
    - `continue`
    - `break`
    - `return`

</div><div class="col">

![](figures/structural-programming.png)

![](figures/structural-programming-proc.png)

</div></div>

----

## Go To Statement <br/> Considered Harmful

(Edsger Dijkstra)

Низкоуровневое программирование и Go To позволяют:

- тонкая ручная оптимизация;
- оптимальный код;
- разного рода хаки.

А чем Go To плох?

![](figures/goto.png)

----

### Как описать текстом текущий шаг программы?

| Структурное | Низкоуровневое   |
| ----------- | ---------------- |
| 1           | 1 |
| 2           | 2 |
| 3.5         | 4.5 |
| 8           | 4.8 |
| 8[1].10     | 4.9.10 |
| 12          | 4.9.10.9.10.9.12 |

</div><div class="col">

![](figures/goto-process-step.png)

</div></div>

---

## Go To. Может быть полезен?

<div>

1. Конечные автоматы.
2. Выход из вложенных циклов.
3. Освобождение ресурсов.

</div>

----

### Go To. Конечные автоматы

![](figures/goto-fsm-scheme.png)

![](figures/goto-fsm.png)

----

### Go To. Выход из вложенных циклов

Подходы к реализации:

1. использование флагов
1. использование именованных циклов
1. использование Go To

</div><div class="col">

![](figures/goto-nested-loop.png)

</div></div>

----

### Go To. Освобождение ресурсов

Подходы к реализации:

1. использование флагов (запрет использования `return`)
1. использование Go To
1. использование defer (см. на след. слайде)

</div><div class="col">

![](figures/goto-free-resource.png)

</div></div>

----

#### Go lang. Освобождение ресурсов. Defer

![](figures/golang-defer.png)

---

## Вопреки структуре. Exceptions

Позволяет выполнить прыжок вверх по иерархии вызова функций.

- as **flow control structures**
    - OCaml, Python, Ruby
    - Python's iterators throw StopIteration exceptions
- only to **handle abnormal, unpredictable, erroneous situations**
    - C++, Java, C#, Common Lisp

</div><div class="col">

![](figures/exception-stack.png)

</div></div>

----

### Деление и исключения (Python)

```python
def div(a, b):
    return a / b

data = [(1, 2), (3, 0), (5, 6)]

# One by one

results = []
for a, b in data:
    tmp = f"{a} / {b} = "
    try:
        tmp += str(div(a, b))
    except ZeroDivisionError:
        tmp += "Division by zero"
    results.append(tmp)

for res in results: print(res)
```

```python
# => 1 / 2 = 0.5
# => 3 / 0 = Division by zero
# => 5 / 6 = 0.8333333333333334
```

</div><div class="col">

```python
# All at once
results = []
try:
    for a, b in data:
        x = f"{a} / {b} = {div(a, b)}"
        results.append(x)
except ZeroDivisionError:
    print("Stop: Division by zero")

for res in results: print(res)
```

```python
# => Stop: Division by zero
# => 1 / 2 = 0.5
```

</div></div>

----

### "Убегание" исключения из контекста

```python
# All at once, with map
try:
    def f(ab):
        a, b = ab
        return f"{a} / {b} = {div(a, b)}"
    result = map(f, data)
except ZeroDivisionError:
    print("Stop: Division by zero")

for line in result: print(line)
```

```python
# => 1 / 2 = 0.5
# => Traceback (most recent call last):
# => .........
# =>     return a / b
# => .........  ~~^~~
# => ZeroDivisionError: division by zero
```

---

### Деление (CLisp)

```lisp
(let* ((data '((1 2) (3 0) (5 6)))
       (result (map 'list (lambda (ab) (apply #'/ ab)) data)))
  (print result))
; => arithmetic error DIVISION-BY-ZERO signalled
```

```lisp
(defun div-expr (a b) (format nil "~A / ~A = ~A" a b (/ a b)))

(div-expr 1 2)
; => "1 / 2 = 1/2"

(div-expr 1 0)
; => arithmetic error DIVISION-BY-ZERO signalled
```

----

### Деление и условия (CLisp) /1

Состояние ~ условие, но не требует разворачивания стека.

```lisp
;; One by one
(let* ((data '((1 2) (3 0) (5 6)))
       (result nil))
  (loop for ab in data
        do (push (handler-case
.................. (apply #'div-expr ab)
.................. (division-by-zero (e)
.................... (format nil "~A / ~A = Division by zero" (car ab) (cadr ab))))
................ result))
  (print result))
```

```lisp
; => ( "5 / 6 = 5/6"
;      "3 / 0 = Division by zero"
;      "1 / 2 = 1/2" )
```

----

### Деление и условия (CLisp) /2

```lisp
;; All at once
(let* ((data '((1 2) (3 0) (5 6)))
       (result nil))
  (handler-case
    (loop for ab in data
          do (push (apply #'div-expr ab)
.................. result))
    (division-by-zero (e) (print "Stop: Division by zero")))
  (print result))
```

```lisp
; => "Stop: Division by zero"
; => ( "1 / 2 = 1/2" )
```

----

### Деление, условия, обработка (CLisp) /1

```lisp
(defun div-expr-with-restart (a b)
  (format nil "~A / ~A = ~A" a b
    (restart-case
      (/ a b)
      (use-value (value) value))))

(div-expr-with-restart 1 2) ; => "1 / 2 = 1/2"
(div-expr-with-restart 1 0) ; => arithmetic error DIVISION-BY-ZERO signalled

(let* ((data '((1 2) (3 0) (5 6)))
       (result nil))
  (loop for ab in data
        do (push
............ (handler-case
.............. (apply #'div-expr-with-restart ab)
.............. (division-by-zero (e)
................ (format nil "~A / ~A = Division by zero" (car ab) (cadr ab))))
............ result))
  (print result))
```

```lisp
; => ( "5 / 6 = 5/6"
;      "3 / 0 = Division by zero"
;      "1 / 2 = 1/2" )
```

----

### Деление, условия, обработка (CLisp) /2

```lisp
(defun div-expr-with-restart (a b)
  (format nil "~A / ~A = ~A" a b (restart-case (/ a b)
.................................. (use-value (value) value))))

(let* ((data '((1 2) (3 0) (5 6)))
       (result nil))
  (handler-case (loop for ab in data
..................... do (push (apply #'div-expr-with-restart ab)
.............................. result))
    (division-by-zero (e) (print "Stop: Division by zero")))
  (print result))
```

```lisp
; => "Stop: Division by zero"
; => ( "1 / 2 = 1/2" )
```

----

### Деление, условия, перезапуск <br/> (CLisp)

```lisp
(defun div-expr-with-restart (a b)
  (format nil "~A / ~A = ~A" a b (restart-case (/ a b)
.................................. (use-value (value) value))))

(let* ((data '((1 2) (3 0) (5 6)))
       (result nil))
  (handler-bind
      ((division-by-zero
        (lambda (c) (invoke-restart 'use-value "Division by zero"))))
    (loop for ab in data
          do (push (apply #'div-expr-with-restart ab)
.................. result)))
  (print result))
```

```lisp
; => ( "5 / 6 = 5/6"
;      "3 / 0 = Division by zero"
;      "1 / 2 = 1/2" )
```

---

## Вопреки структуре. Vars Scope

### Lexical Scope

![](figures/lexical-scope.png)

Scope переменных

- "визуальный" $\uparrow$
- по стеку вызова $\longrightarrow$

</div><div class="col">

### Dynamic Scope

```clojure
(ns foo.lib)
(def ^:dynamic *token* :default-token)
(defn login [] (str "login " *token*))

(login) ; => "login :default-token"

(binding [*token* :other-token]
  (login)) ; => "login :other-token"

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(ns foo.main)

(foo.lib/login) ; => "login :default-token"

(binding [foo.lib/*token* :main-token]
  (foo.lib/login)) ; => "login :main-token"

(set! foo.lib/*token* :new-def-token)

(foo.lib/login) ; => "login :new-def-token"

(binding [foo.lib/*token* :main-token]
  (foo.lib/login)) ; => "login :main-token"
```

<div>

---

## Некоторые забытые тенденции

1. Отсутствие эталонных реализаций языков.
1. Зоопарки компиляторов и виртуальных машин.
1. Диалекты языков программирования.
1. Компилятор — коммерческий проект.
1. RMS на них нет!

</div><div class="col">

![](figures/rms-photo.jpg)

</div></div>

<div>

![](figures/rms-msg.jpg)

</div>

----

## Объектно-ориентированные языки программирования

"Ласточки": С++, Java, C#, Python/Ruby.

- Полиморфизм и re-use.
- Автоматическая работа с памятью. Garbage collector.
- Managed code.

![](figures/polymorphism.png)

</div><div class="col">

![](figures/garbage-collector.jpg)

</div></div>

----

### "Новинки"

1. **Golang** — язык для тупеньких, минимизация overhead (compile-, run-time), многопоточность
2. **Rust** — безопасность и формальные гарантии, zero-cost abstraction
3. **Kotlin** — работа над ошибками, долой математиков, интеграция, практика
4. **Typescript** — работа над ошибками, интеграция, строгая типизация
5. **Clojure** — интеграция вместо своего мира, редизайн под новые условия, многопоточность
6. **Elixir** — снижение самобытности, современный внешний вид
7. **Haskell** (новое) — планомерное развитие статических гарантий и промышленного использования, акцент на математике

Что забыл?

----

#### Общие моменты новинок

- Современная статическая (не как в C или Java) или гибридная типизация.
- Актуализация языков и стандартных библиотек современным потребностям.
- Адаптация к новым условиям и железу.

---

## Законы развития <br/> (в том числе и технологий)

Источник:

[Диалектика Гегеля и Закон Седова <br/> как способ верификации IT трендов <br/> с примерами из Автоматизации тестирования](https://m.youtube.com/watch?v=g8bkugcGeDg)

----

### Диалектика Гегеля

![](figures/hegel-dialecric.png)

----

### Принцип развития иерархических систем Седова

В сложной иерархически организованной системе рост разнообразия на верхнем уровне обеспечивается ограничением разнообразия на предыдущих уровнях, и наоборот, рост разнообразия на нижнем уровне разрушает верхний уровень организации.

![](figures/platform-disaggregation.png)