Writing an "eval" function with new data type

Learning
1

@zshipko @lindig
Hello,
I am trying to write an eval function to evaluate all forms of expressions.

let rec eval (env: environment) (e: expr) : value = 
match e with
| Val v -> v
| Add (e1, e2) -> 
 (match eval env e1, eval env e2 with
    | Int i1, Int i2 -> Int (i1 + i2)
    | _,_            -> raise(Failure "Incompatible values on Add")
)
| Let (n, bexpr, body) ->
  let bexpr_v = eval env bexpr in
  eval ((n,bexpr_v)::env) body
| App (e1, e2) ->  ?? (*Apply a function to an expression*)
| If (e1, e2, e3) ->  ?? (*If ...then... else...*)
| LetRec (n, dexpr, body) -> ??
| Lambda (n, expr) -> ??

How can come up with an idea of writing eval for App and Lambda?
Thank you!

2

Think about whether your value type is sufficient if you have lambda expressions in your language.

3

@lindig
Hello,
My value type currently has Int of int, Bool of bool and closure of stringexprexpr.
What else do i need to think more about eval lambda?
Thank you.

4

You didn’t show the type definition – I was speculating that it might be difficult to represent a lambda value. There are several choices. By any chance, is this a homework exercise?

5

@lindig
Hello,
It is not a homework. I am learning ocaml by myself and I am working on exercises I collect on the Internet. Thank you.

6

@lindig
I think I figured out lambda.
How about If? I think I have to match it with something but I am not quite sure.
Thank you.

7

An if expression yields a value that is computed by evaluating one of the branches. To decide which branch, the guarding expression must be evaluated first. If you have boolean values, the guarding expression should yield a boolean. I think this is easier than lambda expressions or function application.

1 Like
8

I got that part. I am on the LetRec function.
Should I use something like Ref and declare a new value type i.e

type value = Int of int | Bool of bool | Closure of string*expr*env | Ref of value ref ?

Thank you!
@lindig

9

As your TA in the course CSCI2041 at the University of Minnesota Twin Cities campus, I dispute this. We’ll talk in lab on Tuesday.

16 Likes
10

Hi - this is a homework assignment from my course, but it is a common problem. The choice of names exactly matches the ones in our assignment. If you did find it on the internet, can you tell me where that was? Thanks.

-Eric

4 Likes