榆木語言編碼錯誤

Question

type Expr = Const Float | Var String| Add Expr Expr| Mult Expr Expr 

list = [3,1,4] 

polyX : List Float -> Expr 
polyX coeffs = polyHelper <| map Const <| coeffs 
polyHelper: List Expr -> Expr 
polyHelper e = case e of 
    [x] -> x 
    (x::xs) -> Add x(Mult(Var "x")(polyHelper xs)) 
    [] -> Const 1 

type Instr = LoadImmediate RegisterNumber --put value here 
          RegisterValue --the value 

      | Addition  RegisterNumber --put result here 
          RegisterNumber --first thing to add 
          RegisterNumber --first thing to multiply 

      | Multiply  RegisterNumber --put result here 
          RegisterNumber --first thing to multiply 
          RegisterNumber --second thing to multiply 

type RegisterNumber = Int 
type RegisterValue = Float 

expr2Code : Expr -> List Instr 
expr2Code expr = e2C 1 expr 

e2C result expr = case expr of 
       Const x -> ((LoadImmediate(result+2))x) 
       Add expr1 expr2 -> (Addition result result (result+1))::(e2C result expr2)++(e2C result expr1) 
       Mult expr1 expr2 -> (Mult result result(result+1))::(e2C result expr2)++(e2C result expr1) 
       Var x -> [] 

我在分配時遇到困難。

問：

假設你將看到的唯一變量是x，它已經在寄存器2安排的結果到達將在寄存器1的計算結束，並使用根據需要爲其他值註冊3和4。編寫輔助函數e2C來完成。

我的T.A說我現在有的代碼會編譯，但它不會解決問題。

任何人都可以告訴我如何修復代碼，以便解決問題嗎？

Answer 1

讓它編譯

那麼，你是TA是錯的，那個代碼片段不能編譯。這裏有一個編譯版本：

type Expr 
    = Const Float 
    | Var String 
    | Add Expr Expr 
    | Mult Expr Expr 

type Instr 
    = LoadImmediate RegisterNumber --put value here 
        RegisterValue --the value 
    | Addition  RegisterNumber --put result here 
        RegisterNumber --first thing to add 
        RegisterNumber --first thing to multiply 
    | Multiply  RegisterNumber --put result here 
        RegisterNumber --first thing to multiply 
        RegisterNumber --second thing to multiply 

type alias RegisterNumber 
    = Int 

type alias RegisterValue 
    = Float 

list : List Float 
list = 
    [3,1,4] 

polyX : List Float -> Expr 
polyX coeffs = 
    polyHelper <| List.map Const <| coeffs 

polyHelper: List Expr -> Expr 
polyHelper e = 
    case e of 
    [x] -> 
     x 

    (x::xs) -> 
     Add x (Mult (Var "x") (polyHelper xs)) 

    [] -> 
     Const 1 

expr2Code : Expr -> List Instr 
expr2Code expr = 
    e2C 1 expr 

e2C : RegisterNumber -> Expr -> List Instr 
e2C result expr = 
    case expr of 
    Const x -> 
     [LoadImmediate (result+2) x] 

    Add expr1 expr2 -> 
     Addition result result (result+1) 
     :: e2C result expr2 ++ e2C result expr1 

    Mult expr1 expr2 -> 
     Multiply result result (result+1) 
     :: e2C result expr2 ++ e2C result expr1 

    Var x -> 
     [] 

我已經更多地根據style guide格式化代碼。我發現你的代碼之前，以下問題編譯：

1. polyX使用不合格map功能，但目前還沒有進口，所以你應該使用合格List.map。
2. 類型RegisterNumber和RegisterValue是類型別名。使用type alias這些，否則你定義構造Int和Float爲完全獨立的類型RegisterNumber和RegisterValue，而不是與那些在類型Int and Float`。
3. Const分支e2C沒有返回列表，但case的其他分支是。
4. Mult分支e2C正在使用Mult而不是Multiply作爲結果，它是Expr而不是Instr。

得到它的工作

免責聲明：檢查你詐騙學校/課程規定。根據我的經驗，學生只能提交自己寫的解決方案。關於解決方案的高層討論通常是可以的，複製代碼很可能不會。根據學校的欺詐規定，這個答案可能會過於詳細。引用您的來源並不總是足夠的！

給出你可以做的三條指令，將結果從一個寄存器移到另一個寄存器並不容易。這將需要僞造指令，如[LoadImmediate freeRegister 0, Addition moveToThisRegister MoveFromThisRegister freeRegister]。所以你不能優雅地創建一個精細的編譯器，而且你可能不需要，因爲你只被要求完成幫助函數e2C。

因此，我們正在尋找簡單，非一般的解決方案。您需要對獲取的Expr進行一些假設。請注意，polyX僅生成左側不確定的加法和乘法運算（Const或Var）。這是我們將利用的財產。

因此，如果您先執行右側表達式，然後爲該表達式賦予相同的結果寄存器，那麼您的左側仍有兩個空閒寄存器（3和4）。一致地使用其中的一個，然後在結果寄存器和所選的空閒寄存器之間進行操作。

當沒有移動操作時，將變量x的值移到不同的寄存器是很難看的。但它是相當普遍的，所以我們使用剩餘的空閒寄存器將0加到變量x的值上，並將該值保存到我們應該將結果放入的寄存器中。這會給您以下實現：

registerOfX : RegisterNumber 
registerOfX = 2 

freeRegister1 : RegisterNumber 
freeRegister1 = 3 

freeRegister2 : RegisterNumber 
freeRegister2 = 4 

e2C : RegisterNumber -> Expr -> List Instr 
e2C resultRegister expr = 
    case expr of 
    Const value -> 
     [LoadImmediate resultRegister value] 

    Add expr1 expr2 -> 
     e2C resultRegister expr2 
     ++ e2C freeRegister1 expr1 
     ++ [Addition resultRegister freeRegister1 resultRegister] 

    Mult expr1 expr2 -> 
     e2C resultRegister expr2 
     ++ e2C freeRegister1 expr1 
     ++ [Multiply resultRegister freeRegister1 resultRegister] 

    Var "x" -> 
     [LoadImmediate freeRegister2 0, Addition resultRegister registerOfX freeRegister2] 

    Var _ -> 
     "Cannot handle " 
     ++ toString expr 
     ++ ", we only know of " 
     ++ toString (Var "x") 
     |> Debug.crash 

最後一點說明，因爲這已經是一個很長的答案。你會看到這段代碼導致一些冗餘的LoadImmediate 4 0指令。您可以通過執行類似LoadImmediate freeRegister2 0 :: case expr of ...的操作將信號指令添加到列表的前面。然後，您可以在一條指令中將變量x移動到寄存器。任何進一步的指令最小化都需要額外的步驟，最好在其他輔助函數中完成，否則你需要通過在Mult (Var "x") expr2上直接匹配來使代碼不那麼普遍，並直接使用變量x的寄存器。