CODEWITHSUNDEEP
f#f#-interactive
user1072706
user1072706

Reputation: 573

Interpreting a function

I must come up with a function that evaluates an abstract syntax tree and returns the result of its evaluation.

evaluate will have type Exp -> int option

evaluate (Prod(Num 5, Diff(Num 6, Num 1)));; val it : int option = Some 25

@John Palmer How do i go about doing this? Can I use pattern matching? if so how would I do it in order to identify the operation that needs to be done.

Here is what i have come up with? I still dont understand the code per say. 

let rec evaluate = function
 | Num n -> Some n
 | Neg e -> match evaluate e with
 |Sum (a,b) -> evaluate(a) + evaluate(b)
 |Diff(a,b) -> evaluate(a) - evaluate(b)
 | Prod (a,b) -> evaluate(a) * evaluate (b) 
 |Quot (a,b) -> evaluate(a) / evaluate(b)

Upvotes: 2

Views: 462

Answers (3)

J D
J D

Reputation: 48687

I published a little interpreter written in OCaml for a tiny functional language here. Note the eval function in particular. Your problem is simpler because you don't have variables so you don't need the vars dictionary I had and you're always returning int results so you don't need the value union type.

To evaluate an integer expression you just evaluate the subexpressions and do something simple with them. This is most elegantly written as a pattern match:

type Expr =
  | Int of int
  | Neg of Expr
  | Add of Expr * Expr
  | Mul of Expr * Expr

let rec eval = function
  | Int n -> n
  | Neg f -> -eval f
  | Add(f, g) -> eval f + eval g
  | Mul(f, g) -> eval f * eval g

For example:

Mul(Int 2, Neg(Int 3)) |> eval

The advantage of pattern matching is that you can add more complicated actions based upon the contents and shape of the data structure. For example:

| Add(f, Neg g) -> eval f - eval g

Before you know it you're doing computer algebra.

Upvotes: 2

John Palmer
John Palmer

Reputation: 25516

Here are some hints to get started

let rec evaluate AST =
   match AST with
   |Prod(a,b) -> evaluate(a) * evaluate(b)
   |Num(a) -> a
   ....

EDIT

So I assume your data type looks like

type AST =
|Num of int
|Neg of AST
|Prod of AST * AST
|Diff of AST * AST
|Quot of AST * AST
|Sum of AST * AST

so you set up your AST (presumably you are parsing this from somewhere - which is a whole other question) with something like

let ast = Prod(Num 5, Diff(Num 6, Num 1))

then you can define evaluate as

let rec evaluate arg =
    match arg with
    |Num n -> n
    |Neg tree -> - (evaluate tree)
    |Sum (a,b) -> (evaluate a) + (evaluate b)
    |Prod(a,b) -> (evaluate a) * (evaluate b)
    |Quot(a,b) -> (evaluate a) * (evaluate b)
    |Diff(a,b) -> (evaluate a) - (evaluate b)

then call it and print the result with

printfn "%i" (evaluate ast)

Note that evaluate has to have type AST -> int as otherwise you will need to handle option cases - for example what is 2 * None or 2 + None

I am not sure what you mean by

how should i go about calling the recursive method on smaller inputs.

but hopefully this explains everything

Upvotes: 4

duffymo
duffymo

Reputation: 308848

Start by looking into grammars, lexers, and parsers to generate your AST for you. Once you have that, it's a simple matter of walking the tree and evaluating it.

Here's a link to one for F#:

http://www.quanttec.com/fparsec/

Upvotes: 2

Related Questions