---
title: Wyklad 10
---
###### tags: `MP` `Wyklad`

##### Interpreter
*Interpreter będziemy rozumieć, jako program, który analizuje, interpretuje programy w jakimś innym języku programowania, np. C, Racket, reguły gramatyki bezkontekstowej*


* Interpreter działa na pewnej drzewiastej reprezentacji pewnych programów, fraz w pewnym języku.
Żeby interpreter dostał tą drzewiastą strukturę, to trzeba albo ją podać bezpośrednio ręcznie, albo trzeba zatrudnić coś, co weżmie tekst (s-wyrażenie, liste tokenów) i przetworzy nam na takie drzewko, o ile ten kawałek tekstu representuje poprawny program. Ten program to jest **parser** (front-end)

W naszym przypadku metajęzykiem (język w którym piszemy interpreter) to Plait.
###### arith.rkt

#lang plait

(module+ test
  (print-only-errors #t))

;; abstract syntax -------------------------------

(define-type Op
  (add)
  (sub)
  (mul)
  (div))

(define-type Exp
  (numE [n : Number])
  (opE [op : Op] [l : Exp] [r : Exp]))

;; parse ----------------------------------------

(define (parse [s : S-Exp]) : Exp
  (cond
    [(s-exp-match? `NUMBER s)
     (numE (s-exp->number s))]
    [(s-exp-match? `{SYMBOL ANY ANY} s)
     (opE (parse-op (s-exp->symbol (first (s-exp->list s))))
          (parse (second (s-exp->list s)))
          (parse (third (s-exp->list s))))]
    [else (error 'parse "invalid input")]))

(define (parse-op [op : Symbol]) : Op
  (cond
    [(eq? op '+) (add)]
    [(eq? op '-) (sub)]
    [(eq? op '*) (mul)]
    [(eq? op '/) (div)]
    [else (error 'parse "unknown operator")]))
                 
(module+ test
  (test (parse `2)
        (numE 2))
  (test (parse `{+ 2 1})
        (opE (add) (numE 2) (numE 1)))
  (test (parse `{* 3 4})
        (opE (mul) (numE 3) (numE 4)))
  (test (parse `{+ {* 3 4} 8})
        (opE (add)
             (opE (mul) (numE 3) (numE 4))
             (numE 8)))
  (test/exn (parse `{{+ 1 2}})
            "invalid input")
  (test/exn (parse `{+ 1})
            "invalid input")
  (test/exn (parse `{^ 1 2})
            "unknown operator"))
  
;; eval --------------------------------------

(define-type-alias Value Number)

(define (op->proc [op : Op]) : (Value Value -> Value)
  (type-case Op op
    [(add) +]
    [(sub) -]
    [(mul) *]
    [(div) /]))

(define (eval [e : Exp]) : Value
  (type-case Exp e
    [(numE n) n]
    [(opE o l r) ((op->proc o) (eval l) (eval r))]))

(define (run [e : S-Exp]) : Value
  (eval (parse e)))

(module+ test
  (test (run `2)
        2)
  (test (run `{+ 2 1})
        3)
  (test (run `{* 2 1})
        2)
  (test (run `{+ {* 2 3} {+ 5 8}})
        19))

;; printer ———————————————————————————————————-

(define (print-value [v : Value]) : Void
  (display v))

(define (main [e : S-Exp]) : Void
  (print-value (eval (parse e))))

###### Ciekawostki z Plait'a
* (trace name-func) - pokazuje historię wyłowania tej funckji
* Jeżeli nie mamy jeszcze zaimplementowanej jakiejś składni progarmu, ale chcielibyśmy, żeby wszystko fajnie się typowało, to używamy cztery kropki "...." Np.

(define (op->proc [op : Op]) : (Value Value -> Value)
  (type-case Op op
    [(add) +]
    [(sub) -]
    [(mul) *]
    [(div) ....])) : nie mamy jeszcze dzielenia :(

##### Maszyna abstrakcyjna
*Kontynuacja
Maszyna zawiera w każdym momencie pełną informację, co trzeba zrobić, żeby doliczyć się do wartości.
Jak to jest osiągane?
Do naszego stanu dokładamy stos, tzn control stack, żeby nie "zgubić" informację o tym, co trzeba zrobić, jak już policzymy wartość bierzącego wyrażenia.

Stos w naszym przypadku - to algebraiczny typ danych, który ma 3 konstruktory:
- pusty stos
- Może zawierać informację o tym (na swoim szczycie) następną rzecz, którą trzeba będzie policzyć, po tym co zaraz liczę to jest. Wyliczyć wartość wyrażenia, które było prawym argumentem operacji Op.
- Na stosie odłożyliśmy informację o tym, że chcemy wykonać operację op. Mamy wyliczoną wartość lewego poddrzewa(lewefo argumentu) no i resztę stosu

;; abstract machine ---------------------------

(define-type Stack
  (emptyS)
  (rightS [op : Op] [exp : Exp] [s : Stack])
  (leftS [op : Op] [val : Value] [s : Stack]))

Stan obliczeń jest opisany za pomocą argumentów evalAM, mianowicie: bierzące wyrażenie i stos.

- Jeżeli mamy stałą, to znaczy, ze mamy wartość.
Co trzeba zrobić?
Trzeba popatrzeć na stos, i zobaczyć co czekało na tą wartość, wyznaczyć odpowiednią "ramkę", która będzie kontynuować obliczenia.
- Mamy wyrażenie binarne. Powinniśmy policzyć lewe podwyrażenie, ale żeby nie zapomnieć o operatorze i o prawym podwyrażeniu, kładziemy to na stos

(define (evalAM [e : Exp] [s : Stack]) : Value
  (type-case Exp e
    [(numE n)
     (continueAM s n)]
    [(opE o e1 e2)
     (evalAM e1 (rightS o e2 s))]))
     
     

- (rightS op e s)
Na stosie leży informacja o tym, że mamy tam operację i jej prawy argument e, no to znaczy, że v, który dostalismy jest lewem argumentem operacji *op*. Ale teraz muszę policzyć ten prawy argument. No to teraz liczymy ten prawy argument. A na stosie odkładamy informację o tym, że tam już czeka wartość lewego argumentu i operator.

- (leftS op u s)
v w takim razie ma oznaczać wartość prawego argumentu operacji op. Czyli mam dwie wartosci *v* i *u*, tzn że mogę wykonać już operację.

(define (continueAM [s : Stack] [v : Value]) : Value
  (type-case Stack s
    [(emptyS)
     v]
    [(rightS op e s)
     (evalAM e (leftS op v s))]
    [(leftS op u s)
     (continueAM s ((op->proc op) v u))]))
  
(define (runAM [e : S-Exp]) : Value
  (evalAM (parse e) (emptyS)))
  

##### Maszyna wirtualna

Istnieje drugi model wykonywania programów, mianowicie z użyciem *kompilatora*.
Nadal mamy parser, który zamiena składnie konkretną na abstrakcyjną, ale w tym momencie nie dochodzi do interpretacji tego kodu tych wyrażen bezpośrednio, ale dochodzi do tłumaczenia na inny język, zwykle taki, który jest bliższy architekturze komputera.

To może być translacja (kompilacja), kompilacja do kodu pośredniego, kodu maszyny wirtualnej.
Maszyna wirtualna może wykonywać ten byte code efektywnie interpretując nasz kod w języku wejsciowym.

*Interpreter or machine* jak na obrazku może być
- maszyna wirtualna, która operuje na pewnym assemblerze "wysokiego poziomu", np byte-code'ie (maszyna wirtualna Javy)
- wykonanie instukcji na najniższym poziomie, czyli np. w assemblerze

(define-type Instr
  (pushI [n : Value])
  (opI [op : Op]))

(define-type-alias Code (Listof Instr))

;; stack

(define-type-alias StackVM (Listof Value))
(define mtS : StackVM empty)
(define (pushS [v : Value] [s : StackVM]) : StackVM
(cons v s))
(define (popS [s : StackVM]) : (Value * StackVM)
(type-case StackVM s
[empty
(error 'popS "empty stack")]
[(cons v s)
(pair v s)]))

(define (evalVM [c : Code] [s : StackVM]) : Value
(type-case Code c
[empty
(fst (popS s))]
[(cons i c)
(type-case Instr i
[(pushI n)
(evalVM c (pushS n s))]
[(opI op)
(let* ([n2-s2 (popS s)]
[n2 (fst n2-s2)]
[s2 (snd n2-s2)]
[n1-s1 (popS s2)]
[n1 (fst n1-s1)]
[s1 (snd n1-s1)]
[s0 (pushS ((op->proc op) n1 n2) s1)])
(evalVM c s0))])]))

(module+ test
(test/exn (evalVM (list (opI (add))) mtS)
"empty stack"))

;; compiler

(define (compile [e : Exp]) : Code
(type-case Exp e
[(numE n)
(list (pushI n))]
[(opE op e1 e2)
(append (compile e1)
(append (compile e2)
(list (opI op))))]))

System makr pozwala na konstruowanie form specjalnych.
define-syntax