主页 / coding / 问题 / 78380215
Accepted
NotAlfred
Asked: 2024-04-25 01:23:18 +0800 CST

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

  • 772

所以这个问题可能看起来太新手了，但我已经在读 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
            Const 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 编写的编译器或解释器如何在后期正确处理常量折叠？我很确定我走错了路......

haskell

1 个回答

  1. Best Answer

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

    Addition -> folderNum (+)
...
where folderNum :: (forall a. Num a => a -> a -> a) -> Expression
      folderNum op = case (lhs, rhs) of
        (Const (IntegerV a), Const (IntegerV b)) -> Const (IntegerV (op a b))
        (Const (FloatV a), Const (FloatV b)) -> Const (FloatV (op a b)) 
        else -> ...

    你走在正确的轨道上，但你必须做详细的案例工作，以匹配哪些二进制运算适用于哪些常量类型，大概是针对 Haskell 中支持你需要的操作的每个不同类型类。

    • 3

相关问题