環境
IBM の OLP (線形プログラミングのモデリング言語) に大まかに似た EDSL を実装しようとしています。
コード
Haskell EDSL コード
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleInstances #-}
-- Numbers at the type level
data Peano = Zero | Successor Peano
-- Counting Vector Type. Type information contains current length
data Vector peanoNum someType where
Nil :: Vector Zero someType
(:+) :: someType
-> Vector num someType
-> Vector (Successor num) someType
infixr 5 :+
-- Generate Num-th nested types
-- For example: Iterate (S (S Z)) [] Double => [[Double]]
type family Iterate peanoNum constructor someType where
Iterate Zero cons typ = typ
Iterate (Successor pn) cons typ =
cons (Iterate pn cons typ)
-- DSL spec
data Statement =
DecisionVector [Double]
| Minimize Statement
| Iteration `Sum` Expression
| Forall Iteration Statement
| Statement :| Statement
| Constraints Statement
infixl 8 `Sum`
infixl 3 :|
data Iteration =
String `In` [Double]
| String `Ins` [String]
data Expression where
EString :: String -> Expression
EFloat :: Double -> Expression
(:?) :: Vector n Expression -> Iterate (n) [] Double -> Expression
(:*) :: Expression -> Expression -> Expression
Lt :: Expression -> Expression -> Expression
Gt :: Expression -> Expression -> Expression
Id :: String -> Expression
infixr 5 `Lt`
infixr 5 `Gt`
infixr 6 :*
infixr 7 :?
test :: Statement
test =
let rawMaterial = 205
products = ["light", "medium", "heavy"]
demand = [59, 12, 13]
processes = [1, 2]
production = [[12,16], [1,7], [4,2]]
consumption = [25, 30]
-- foo = (EId "p" :+ EId "f" :+ Nil) `Subscript` production
-- bar = (EId "p" :+ Nil) `Subscript` cost
run = []
cost = [300, 400]
in
DecisionVector run :|
Minimize
(Sum ("p" `In` processes)
((Id "p" :+ Nil) :? cost :*
(Id "p" :+ Nil) :? run)) :|
Constraints
(Sum ("p" `In` processes)
((Id "p" :+ Nil) :? consumption :*
(Id "p" :+ Nil) :? run `Lt` EFloat rawMaterial) :|
Forall ("q" `Ins` products)
(Sum ("p" `In` processes)
((Id "q" :+ Id "p" :+ Nil) :? production :*
(Id "p" :+ Nil) :? run `Gt`
(Id "q" :+ Nil) :? demand)))
instance Show Statement where
show (DecisionVector v) = show v
show (Minimize s) = "(Minimize " ++ show s ++ ")"
show (i `Sum` e) = "(" ++ show i ++ " `Sum` " ++ show e ++ ")"
show (Forall i e) = "(Forall " ++ show i ++ show e ++ ")"
show (sa :| sb) = "(" ++ show sa ++ show sb ++ ")"
show (Constraints s) = "(Constraints " ++ show s ++ ")"
instance Show Iteration where
show (str `In` d) = "(" ++ show str ++ " `In` " ++ show d ++ ")"
show (str `Ins` d) = "(" ++ show str ++ " `Ins` " ++ show d ++ ")"
instance Show Expression where
show (EString s) = "(EString " ++ show s ++ ")"
show (EFloat f) = "(EFloat " ++ show f ++ ")"
show (Lt ea eb) = "(" ++ show ea ++ " `Lt` " ++ show eb ++ ")"
show (Gt ea eb) = "(" ++ show ea ++ " `Gt` " ++ show eb ++ ")"
show (ea :* eb) = "(" ++ show ea ++ " :* " ++ show eb ++ ")"
show (Id s) = "(Id " ++ show s ++ ")"
show (vec :? dbl) = "(" ++ show vec ++ " :? " ++ "dbl" ++ ")"
instance Show (Vector p Expression) where
show (Nil) = "Nil"
show (e :+ v) = "(" ++ show e ++ " :+ " ++ show v ++ ")"
-- eval_opl :: Statement -> [Double]
EDSL と OPL の比較
let rawMaterial = 205
products = ["light", "medium", "heavy"]
demand = [59, 12, 13]
processes = [1, 2]
production = [[12,16], [1,7], [4,2]]
consumption = [25, 30]
-- foo = (EId "p" :+ EId "f" :+ Nil) `Subscript` production
-- bar = (EId "p" :+ Nil) `Subscript` cost
run = []
cost = [300, 400]
in
DecisionVector run :|
Minimize
(Sum ("p" `In` processes)
((Id "p" :+ Nil) :? cost :*
(Id "p" :+ Nil) :? run)) :|
Constraints
(Sum ("p" `In` processes)
((Id "p" :+ Nil) :? consumption :*
(Id "p" :+ Nil) :? run `Lt` EFloat rawMaterial) :|
Forall ("q" `Ins` products)
(Sum ("p" `In` processes)
((Id "q" :+ Id "p" :+ Nil) :? production :*
(Id "p" :+ Nil) :? run `Gt`
(Id "q" :+ Nil) :? demand)))
oplコードに対応
float rawMaterial = 205;
{string} products = {"light","medium","heavy"};
float demand[products] = [59,12,13];
{string} processes = {"1","2"};
float production[products][processes] = [[12,16],[1,7],[4,2]];
float consumption[processes] = [25,30];
float cost[processes] = [300,400];
dvar float+ run[processes];
minimize sum (p in processes) cost[p] * run[p];
constraints {
sum (p in processes) consumption[p] * run[p] <= rawMaterial;
forall (q in products)
sum (p in processes) production[q][p] * run[p] >= demand[q];
}
関連セクション
(:?) :: Vector n Expression -> Iterate (n) [] Double -> Expression
としても
instance Show Expression where
[...]
show (vec :? dbl) = "(" ++ show vec ++ " :? " ++ "dbl" ++ ")"
問題の説明
OPL は配列サブスクリプションにブラケットを使用します。次の表記法を使用して、サブスクリプションを EDSL にマップしようとしました
((Id "p" :+ Id "f" :+ Nil) :? consumption
これは、次の意味で OPL に対応します。
consumption[p][f]
前者では、 (Id "p" :+ Id "f" :+ Nil) は、ベクトルの長さに関する型レベル情報を含む Vector 型の値を構築します。コンストラクタ :? の定義によると、 Iterate (n) [] Double は [[Double]] に展開されることがわかります。これは期待どおりにうまく機能します。ただし、生成された構文ツリーを使用するには、実際の値に対してパターン マッチを行う必要があります。
show (vec :? dbl) = "(" ++ show vec ++ " :? " ++ "dbl" ++ ")"
問題: 上記の行は機能しますが、実際のデータの使用方法がわかりません。パターンマッチのやり方は？とにかくデータを使用することさえ可能ですか？明らかな dbl の置換
(Iterate (Successor (Successor Zero)) [] Double)
動作しません。また、データ ファミリを構築しようとしましたが、任意にネストされた Double のすべてのリストのファミリを再帰的に作成する方法がわかりませんでした。
Double
[Double]
[[Double]]
[[[Double]]]
...