榆木语言编码错误

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的寄存器。