如何在haskell中为优化编译器执行常量折叠算法？

Question

所以这个问题可能看起来太新手了，但我已经在读 Steven Muchnick 的《高级编译器设计和实现》一书，在优化的第一章中谈到了常量折叠。

第一次尝试如下所示，但考虑到它需要类型类

Integral

和

Bits

，几乎不可能实现。

data Value
  = BoolV Bool
  | IntegerV Integer
  | FloatV Double
  | StringV String
  deriving (Show, Eq)

data Expression
  = Const Value
  | Temp Label
  | List [Expression]
  | Call Label [Expression]
  | BinOp Operator Expression Expression
  deriving (Show, Eq)

rerunOverIR :: Expression -> Expression
rerunOverIR = \case
  Const constant -> Const constant
  Temp temporary -> Temp temporary
  List list -> List list
  Call label args -> Call label (map rerunOverIR args)
  BinOp operator lhs rhs ->
    case operator of
      Addition -> folder (+)
      Subtraction -> folder (-)
      Multiplication -> folder (*)
      Modulo -> folder mod
      Division -> folder div
      BitwiseAnd -> folder (.&.)
      BitwiseOr -> folder (.|.)
      BitwiseXor -> folder xor
      ShiftRight -> folder shiftR
      ShiftLeft -> folder shiftL
      Equal -> folder (==)
      NotEqual -> folder (/=)
      Greater -> folder (>)
      GreaterEqual -> folder (>=)
      Less -> folder (<)
      LessEqual -> folder (<=)
      LogicalAnd -> folder (&&)
      LogicalOr -> folder (||)
      _ -> error $ "this operator doesn't exist " ++ show operator
    where
      folder op =
        case lhs of
          Const c1 -> case rhs of
            Const c2 -> Const $ op c1 c2
            expr -> rerunOverIR $ BinOp operator (Const c1) (rerunOverIR expr)
          e1 -> case rhs of
            rerunOverIR c2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (Const c2)
            e2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (rerunOverIR e2)

所以这次我尝试将表达式更改为以下，但结果更糟。

data Expression
  = Bool Bool
  | Integer Integer
  | Float Double
  | String String
  | Temp Label
  | List [Expression]
  | Call Label [Expression]
  | BinOp Operator Expression Expression
  deriving (Show, Eq)

所以我的问题是，用 Haskell 编写的编译器或解释器如何在后期正确处理常量折叠？我很确定我走错了路......

Answer 1

看起来你当然应该能够通过这样做来做到这一点，例如，

Addition -> case (lhs, rhs) of 
  (Const (IntegerV lhs), Const (IntegerV rhs)) -> Const (IntegerV (lhs + rhs))

并且对于每种情况都同样明确。

更简单地说，您可以专门化

folder

为每组有效类型提供单独的版本：例如，当两个参数都是

folderNum

或

Const (IntegerV ...)

时，它将匹配。您的方向是正确的，但您必须进行详细的案例工作，以匹配哪些二进制运算适用于哪些常量类型。