###### tags: `MP`

# Wykład III

## Fragment do wykładu I tej tercji

Wcześniej przy języku dotyczącym operacji arytmetycznych mieliśmy tak, że wyjątki zwracaliśmy "krokowo". Jak mamy interpreter w postaci maszyny abstrakcyjnej to ten interpreter był ogonowy, a nie zagnieżdzony, jak to było wcześniej.

Ogonowy => wywołanie dalsze jest ostatnią rzeczą, którą robimy => jak napotkamy błąd to możemy od razu powiedzieć, że wynikiem działania całego programu jest błąd (wyrzucamy stos i kończymy działanie zwracając błąd), a nie, że musimy propagować błąd jak poprzednio

## Zejście poziom niżej z reprezentacją funkcji

Ostatnio: funkcje na poziomie interpretera były reprezentowane przez funkcje (Value -> Value).

**Jak miałaby wyglądać struktura danych (pierwszorzędowa + funkcja interpretująca) reprezentująca wszystko, co ta funkcja robi?**

Jak do tej pory wyglądało:

{lambda {x} e} env
(funV (lambda (v) (eval e (extend-env env x v))))

Chcemy to zareprezentować trójką [x, e, env]. Wtedy musimy zmienić apply:

(define (apply [v1 : Value] [v2 : Value]) : Value
	(type-case Value v1
		[(funV x b env)
		(eval b (extend-env env x v2))]
		[else ERROR]))

To jest już znacznie bliższe reprezentacji niskopoziomowej.

Te dwa interpretery mogłyby być równoważne, ale pokazanie tego nie jest proste (gdy damy to policzenia funkcję w pierwszym przypadku dostaniemy funkcję a w drugim strukturę z jakimiś danymi). Pokazanie równoważności by wymagało opisania kiedy struktura (domknięcie) jest równoważne.

**Ważne:** jeśli nie zadbamy o to, żeby wziąć odpowiednie środowisko, bo inaczej będzie dynamiczne typowanie zmiennych, i wynik funkcji zależy nie tylko od jej argumentów ale też momentu wywołania. Działają tak niektóre starsze dialekty Lispu, ponieważ na początku popełniono ten błąd i w tych dialektach to nadal zostało.

## Jak napisać silnię?

Jak mamy `define` albo `letrec` to nie ma problemu. Czy umiemy napisać silnię bez tego? (rekursja bez rekursji)

Użyjemy tych fanych aplikowanych do samych siebie lambd.

(define (silnia n)
  (let ([fact
         (λ (f) (λ (n) (if (= n 0)
                           1
                           (* n ((f f) (- n 1))))))])
    ((fact fact) n)))

Oczywiście zamiast define możemy użyć let, bo już w define nie korzystamy z rekursji.

## Nieskończona pętla:

(let ([w (lambda (x) (x x))])
	(w w))

Samo w sobie nie jest użyteczne, ale można wykorzystać to.

## Operator punktu stałego

Chcemy mieć taką funkcję `fix`, żeby `(fix f)` $\to$ `(f (fix f))`.

## Dokładamy `letrec` do naszego języka:

Wcześniej używaliśmy rzeczy z naszego metajęzyka do wykonywania rzeczy z języka, który interpretujemy.

env {letrec x e1 e2}
(letrec ([v (eval e1 (extend-env env x v))]) ;to nie zadziala, trzebaby to schowac pod lambde
	(eval e2 (extend-env x v)))

Problem: mamy język gorliwy i liczymy wszystko, co się da (nawet gdy nie jest to nam potrzebne).

Działa to:

{letrec f {lambda {y} ... f ...}}

Ale nie działa to:

{letrec x {+ x 1} env}

Jak naprawić?

env {letrec x e1 e2}
(letrec ([v (eval e1 (extend-env env x (lambda () v)))]) ;bezargumentowa lamda zwracajaca wartosc, zeby ta wartosc nie probowala sie liczyc wczesniej
	(eval e2 (extend-env x v)))

W ten sposób wyraziliśmy letrec'a z naszego języka letrec'iem z meta-języka.

## Można też zrobić letrec'a używając mutowalnego stanu