CODEWITHSUNDEEP
treef#
John Doe
John Doe

Reputation: 19

F# expression tree interpreter implementation

I'm trying to construct a interpreter for an expression tree that can add or multiply in F#, but I'm having some trouble. I'm also trying to use option types so that the interpreter returns None if the variable isn't in the expression.

Here is the code I'm given. 

type Exptree =
  | Const of int
  | Var of string
  | Add of Exptree * Exptree
  | Mul of Exptree * Exptree

type Bindings = (string * int) list

let rec eval(exp : Exptree, env:Bindings) =  
  match exp with
  |

I'm confused on what to match exp with, since there are so many options. My idea is to look at Add and Mul, and try to strip it down on each recursion step until I get a integer, however I am completely lost.

Could I do something like?

match exp with
| Some(Add) -> int + int?
| Some(Mul) -> int * int?

Upvotes: 1

Views: 610

Answers (2)

TheInnerLight
TheInnerLight

Reputation: 12184

So, scrwtp is correct that Map<string, int> makes more sense for your set of bindings because you can then perform lookup in O (log n) time, rather than O (n) time with list.

The first part of the eval function is easy:

  1. If the value is a constant, we simply need to return Some of that constant.
  2. If the value is a variable, we need to look it up in the map, if the key exists, we return Some of the value. If they key does not exist, we return None. We can use Map.tryFind to do that.

We can do this part like this:

let rec eval bindings tree =
    match tree with
    |Const i -> Some i
    |Var varName -> Map.tryFind varName bindings

Performing addition and multiplication requires a bit more thought. In order to abstract combining two sub-trees, it makes sense to define a function which takes two options as arguments and allows you to apply a function to both results if they are both Some value. This is called the lift2 function and we can define it for Option:

/// Combines two option values using a supplied function
let lift2 f opt1 opt2 =
    match (opt1, opt2) with
    |Some val1, Some val2 -> Some <| f val1 val2
    |_ -> None

For more on the lift family of functions, see this great tutorial: http://fsharpforfunandprofit.com/posts/elevated-world/#lift

Now we can extend our eval function for the Addition and Multiplication cases by calling this function.

/// Evaluates the result of an expression tree
let rec eval bindings tree =
    match tree with
    |Const i -> Some i // Const always returns some value
    |Var varName -> Map.tryFind varName bindings // Returns some value if it exists in the binding table
    |Add (tree1, tree2) ->
        lift2 (+) (eval bindings tree1) (eval bindings tree2) // add expressions if both expressions return Some val
    |Mul (tree1, tree2) ->
        lift2 (*) (eval bindings tree1) (eval bindings tree2) // multiply expressions if both expressions return Some val

Now, the add case is using the lift2 function to say, if both sub-expressions evaluate to a real value, add the results together, otherwise to return None.

The multiplication case follows exactly the same logic, we've just swapped the operator.

A quick aside: As GuyCoder points out, a convenient way to build your binding table would then be to use the syntax:

let bindings = Map.ofList [("a",1); ("b",2); ("c",3)]

Upvotes: 4

mjsottile
mjsottile

Reputation: 191

Your Exptree type has four possible constructors: Const, Var, Add, and Mul. So, your match would be on those:

match exp with
| Const c -> 
| Var s ->
| Add (e1,e2) -> 
| Mul (e1,e2) ->

For each of those cases, you would do the appropriate operation (add, multiply, lookup a variable in the environment, return a constant). In the add and mul cases, you would interpret the result of the recursive invocation of eval on the subexpressions (e1 and e2) to see if the value is None or Some(s), and act on it accordingly.

Upvotes: 6

Related Questions