Interpreter with Ocaml

Question

I write an interpreter with Ocaml but when i try :

sem(Let("Somma",Fun("x",Sum(Den "x",Eint(5))),Let("pipa",Pipe(Seq(Den "Somma",Nil)),Apply(Den "pipa",Eint(42)))),(emptyenv Unbound));;

the resault is an error : "Exception: Match_failure ("",1,41)

I think that error is in applyPipe but I don't understand where and why there is Where did i wrong?

this is my code :

type exp =
    .
    .
    .
    | Fun of ide * exp
    | Apply of exp * exp  
    | Letrec of ide * ide * exp * exp
    | Etup of tuple (*Tupla come espressione*)
    | Pipe of tuple (*Concatenazione di funzioni*)
    | ManyTimes of int * exp (*Esecuzione iterata di una funzione*)
and tuple = 
    | Nil (*Tupla vuota*)
    | Seq of exp * tuple (*Tupla di espressioni*)
;;

type eval= 
    | Int of int 
    | Bool of bool 
    | Unbound 
    | RecFunVal of ide * ide * exp * eval env
    | Funval of efun
    | ValTup of etuple
and efun = ide * exp * eval env
and etuple =
    | Nil
    | Seq of eval * etuple
;;

    let rec sem ((ex: exp), (r: eval env)) = match ex with
         .
         .
         .
         | Let(i, e1, e2) -> sem(e2, bind (r, i, sem(e1, r)))
         | Fun(i,a) -> Funval(i,a,r)
         | Letrec(f, i, fBody, letBody) ->
              let benv = bind(r, f, (RecFunVal(f, i, fBody, r)))
               in sem(letBody, benv)    
         | Etup(tup) -> (match tup with
            | Seq(ex1, tupla) ->
                let evex1 = sem(ex1, r) in
                let ValTup(etupl) = sem(Etup(tupla), r) in
                ValTup(Seq(evex1, etupl))
            | Nil -> ValTup(Nil))
         | Apply(Den f, arg1) ->
            (let fclosure= sem(Den f, r) in
               match fclosure with
                 | Funval(arg, fbody, fDecEnv) ->
                     sem(fbody, bind(fDecEnv, arg, sem(arg1, r)))
                 | RecFunVal(f, arg, fbody, fDecEnv) ->
                     let aVal= sem(arg1, r) in
                     let rEnv= bind(fDecEnv, f, fclosure) in
                     let aEnv= bind(rEnv, arg, aVal) in
                       sem(fbody, aEnv)
                 | _ -> failwith("non functional value"))
        | Apply(Pipe tup, arg) -> applyPipe tup arg r
        | Apply(_,_) -> failwith("not function")
        | _ -> failwith("non implementato")

    and applyPipe tup argo r = (match tup with 
        | Seq(Den f, tupla) -> 
            let appf = Apply(Den f,argo) in
                applyPipe tupla appf r
        | Nil -> sem(argo,r)
        | _ -> failwith("Not a valid Pipe"))
    ;;

The complete code is there : http://pastebin.com/VgpanX51 Please help me thaks

It looks like that you didn't show the relevant code, as the code that actually fails will pattern-match over a string value, and the string that is passed to it is empty, that is not anticipated by the code, hence the error. — ivg

ivg ivg · Accepted Answer · 2017-02-06T18:30:23

When you compile (or evaluate in a toplevel) an OCaml program, a typechecker will emit warnings about all pattern matches that are irrefutable, i.e., such patterns that may raise a Match_failure exception.

What you should do, is to go through all warnings and fix them.

There are quite a few irrefutable matches in your code, e.g., the sem function final match Apply(_,_) -> failwith("not function") will only catch Apply terms, but will not catch all others, adding something like _ -> failwith "unimplemented" will fix it.

QA

the error is in the try-code or in my interpreter?

It is in the interpreter, you didn't include all possible cases in your pattern-matching code.

.I do extend the typechecker

You don't need to. The typechecker verifies whether you anticipated all possible cases, for example, let's take the simple example:

type abc = A | B | C

let string_of_abc abc = match abc with
  | A -> "A"
  | B -> "B"

When you will try to compile (or interpret) the above code the typechecker will tell you:

Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
C
type abc = A | B | C

So, it gives you a hint, that you forgot to match with the C constructor, so the expression string_of_abc C will terminate with a Match_failure exception.

You can follow the hints and add the cases one-by-one. Given your example, the pattern matching in the sema function is incomplete, and the type checker hits you with the following:

Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
(Pipe _|ManyTimes (_, _))

And indeed, you missed the case with Pipe, so when the interpreter sees

Pipe(...)

It can't find a match, as according to your code you're expecting the Pipe constructor only as a first argument to Apply, when in your example, you're actually passing it as a second argument to Let.

Interpreter with Ocaml

1 Answers

QA