解釋函數

Question

我必須拿出一個取值爲抽象語法樹，並返回其評估結果的函數。

評價將具有類型經驗 - > INT選項

評估（PROD（民5，DIFF（民6，序號1）））;; VAL它：INT選項=約25

@約翰 - 帕爾默 我如何去這樣做？我可以使用模式匹配嗎？如果是的話，我將如何做，以確定需要完成的操作。

以下是我已經想出了？我仍然不明白每個說的代碼。

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) 

Answer 1

下面是一些提示，上手

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

編輯

所以我假設你的數據類型看起來像

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

所以您設置AST（想必你是從某個地方解析這個 - 這是一個其他的問題薦）喜歡的東西

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

，那麼你可以定義評估爲

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) 

然後調用它，並

printfn "%i" (evaluate ast) 

注意打印結果evaluate必須有類型AST -> int另有你將需要處理選項的情況下 - 比如什麼是2 * None或2 + None

我不知道你所說的

我應該如何去調用遞歸方法上較小的投入是什麼意思。

但希望這將尋找到的語法，詞法分析器，和解析器來生成AST爲你解釋一切

Answer 2

開始。一旦你有了這些，走樹和評估它是一件簡單的事情。

下面是一個鏈接，F＃：

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

Answer 3

我發表書面OCaml中一個小小的功能性語言here一點解釋。特別注意eval函數。你的問題是簡單，因爲你沒有變數，所以你不需要vars字典我有和你總是返回int結果，所以你不需要value聯合類型做。

要評估一個整數表達式，您只需評估子表達式並對它們做一些簡單的操作。這是最優雅的寫作模式匹配：

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 

例如：

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

模式匹配的好處是，你可以添加基於數據結構的內容和形狀更復雜的動作。例如：

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

在知道它之前，你在做computer algebra。