Semantica per un interprete in OCaml

[morenaria]

Buongiorno,
devo implementare in OCaml un interprete per un linguaggio di programmazione, in particolare ho che nel linguaggio considerato le espressioni "possono avere side-effects", ovvero esiste un'espressione di assegnamento "variabile = espressione" (in sintassi astratta, questo è un costruttore EAssign of (ide * expr) per il tipo expr delle espressioni). La semantica delle espressioni, a partire dal suo stesso tipo, deve dunque essere corretta in modo da prevedere questo caso.
Pertanto EAssign modifica lo stato, assegnando la variabile all'identificatore. Le altre espressioni però non modificano lo stato, per cui la loro semantica deve restituire lo stato non modificato.

Il mio dubbio è proprio su come scrivere la semantica delle espressioni, nel caso in cui non modifichino lo stato, ad esempio Eplus (l'espressione che somma due interi). Ho sempre visto la semantica delle espressioni scritta come funzione che ha un intero o un booleano in output, non come uno stato. Cosa deve fare questa funzione? Prende e sputa lo stesso stato, e nel mezzo che succede?
Sono un po' confusa...qualcuno potrebbe chiarirmi un po' le idee?

[Crispolto]

Buongiorno! In generale una espressione con side-effects sarà una funzione che prende un certo numero di parametri e uno stato e restituirà una coppia (valore, stato). Penso che in OCaml sia possibile rappresentare una coppia di dati di tipo diverso in qualche modo, probabilmente con una tupla.

La somma sarà una funzione che prende 3 parametri in input e ritorna una tupla (valore, stato). Come dici tu, nel caso della somma, lo stato viene preso e ritornato immediatamente in output come elemento della tupla. Gli altri due parametri invece verranno sommati e restituiti come ulteriore elemento della tupla.

[apatriarca]

Per valutare il valore di una qualsiasi espressione con side-effects dovrai quindi ricevere in ingresso lo stato e restituire lo stato aggiornato e un risultato. In altri termini, un qualsiasi "step" del tuo calcolo avrà come tipo "stato -> valore * stato". Consideriamo a questo punto una espressione del tipo "Eplus of expr * expr" potresti quindi fare qualcosa come segue (non conosco Ocaml bene per cui potrei aver sbagliato qualcosa nella scrittura ma spero si capisca l'idea)

eval expr s = match expr with
   Eplus (e1, e2) -> let (e1v, s1) = eval e1 s in let (e2v, s2) = eval e2 s1 in (e1v + ev2, s2)
(* ... *)

Nota come lo stato sia passato alla prima espressione e questa possa modificarlo prima di eseguire la seconda espressione. Se si suppone che le due espressioni non abbiano side-effects si può passare lo stesso stato alle due valutazioni e poi anche al valore di ritorno e si avrebbe il vantaggio che non c'è una dipendenza tra la valutazione delle due espressioni (potrebbero essere valutate in qualsiasi ordine).

[morenaria]

"apatriarca":Nota come lo stato sia passato alla prima espressione e questa possa modificarlo prima di eseguire la seconda espressione.

Ma in questo caso lo stato risulta modificato, cosa che noi non vogliamo fare, o sbaglio?
Mi sembra che l'unico modo di lasciare lo stato invariato sia di prenderlo in input e ritornarlo, come dice Crispolto...provo a fare una bozza di codice.

[apatriarca]

Il problema sono i due addendi. Se questi avessero side-effects allora anche la somma la avrebbe. Se non vuoi che le due espressioni possano avere side-effects allora puoi usare s ovunque e ignorare i valori restituiti dalle due espressioni per lo stato.

[morenaria]

let rec esem = exp -> env -> store -> (env * store) fun e ev st ->
      match e with
   Eint i -> 
          if i < 0 
          then negative_natural_number_error ()
          else Int i ev st
 | Eplus (e1,e2) -> 
        (let s1 = esem e1 ev st in
         let s2 = esem e2 ev st in
         match (s1,s2) with
           (Int i1,Int i2) -> Int (i1 + i2) ev st
         | _ -> type_error ())
 | Eassign (i,e) ->
	let s = esem e ev st in
	(match apply_env ev i with
	  L l ->
	    let st1 = update st l s in
	    (ev,st1)
	| _ -> not_a_location_error i)

Che dite?

[apatriarca]

(Int i1,Int i2) -> Int (i1 + i2) ev st

Non mi convince.. Se ho capito bene dal tuo codice Int ha 3 argomenti ma tu stai facendo il match con solo uno.. Ho esperienza principalmente con Haskell che mi darebbe errore. Hai provato ad usare il tuo codice?

Pensavo inoltre ci fosse anche in qualche modo la possibilità di usare i valori che sono stati assegnati.