Haskell 上で簡単なプログラミング言語を作る

Haskell 上で，モナド等を使わず素朴にプログラミング言語を作ってみます．

構文規則

このプログラミング言語には，"変数"，"定数"，"式", "文" が存在するとしましょう．

変数

変数は A, B, C, D, E, F の 6 つを用意します．
変数には値を代入したり，式として使うことができます．
ただし，今回は変数に代入できる値は整数値のみとします．

定数

定数は C0, C1, C2, C3, C4, C5, C6, C7, C8, C9 の 10 個を用意します．
それぞれ整数 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 を表す定数です．

式

式は次の 4 つのいずれかからなります．

• 変数
• 定数
• 式 + 式
• 式 - 式

例えば変数 A や定数 C0 はそのままで式になりますし，A + B や D + C5 なども式になります．
+, - は単純に式の値を足し算したり引き算することにします．

Haskell の都合上，+ は :+:, - は :-: と書くことにします．
(Haskell で値コンストラクタを中置する場合は名前をコロンで始めなければならない)

文

文は次の 5 つのいずれかからなります．

• 変数 := 式

代入文です．左辺の変数に右辺の式の値を代入します．

• IFEQ 式1 式2 文1 文2

分岐文です．式1 と 式2 の値が等しければ 文1 を実行し，そうでなければ 文2 を実行します．
(if 式1 == 式2 then 文1 else 文2)

• FOR 式 文

反復文です．式の値の回数だけ文を実行します．
式の値が 0 以下であれば何も実行しません．

• NOOP

なにもしない文です．

• 文1 :| 文2

順次実行文です．文1 を実行し，その次に 文2 を実行します．
本当はセミコロン ; のような区切り文字を使いたいのですが，Haskell の都合上 :| を使うことにします．

変数，定数，式，文のデータ型をつくる

変数

変数を表すデータ型は Var (variable) とします．
ghc 上で表示できるように Show のインスタンスにしておきます．
また，後で出てくる mcmd 函数内で比較を行うので Eq のインスタンスにもしておきます．

data Var = A | B | C | D | E | F
  deriving (Show, Eq)

定数

定数を表すデータ型は Cst (constant) とします．

data Cst = C0 | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9
  deriving (Show)

式

式を表すデータ型は Exp (expression) とします．

infixl 6 :+: 
infixl 6 :-:
data Exp = VAR Var | CST Cst | Exp :+: Exp | Exp :-: Exp
  deriving (Show)

ここで，infixl は演算子の左結合性宣言です．
この宣言を行った演算子 (ここでは :+: と -:-) は左結合になります．
即ち，a :+: b :+: c と書いた時 (a :+: b) :+: c と解釈されます．

また数字は結合の強さで，大きいほど結合が強くなります．例えば後で定義する :| は infixl 0 なので :+: より結合が弱くなります．
即ち，a :| b :+: c と書いた時 a :| (b :+: c) と解釈されます．

変数や定数はそのままで式になるとしましたが，Haskell の都合上変数や定数を式として扱うときはコンストラクタ VAR, CST で包むことにします．
即ち，A は変数ですが，VAR A は式です．

文

文を表すデータ型は Cmd (command) とします．

infixl 0 :|
infix 4 :=
data Cmd = Var := Exp
         | IFEQ Exp Exp Cmd Cmd
         | FOR Exp Cmd
         | NOOP
         | Cmd :| Cmd
  deriving (Show)

infix は結合の強さだけを宣言します．
:= は :| よりも強いですが :+: よりは弱いため
a :| b := c :+: d は a :| (b := (c :+: d)) と解釈されます．

環境

環境は，厳密に言うと変数の集合から値の集合への函数です．
ここでは，各変数 (A, B, C, D) から値をとりだすもの，と考えておきます．

今回は，変数の値として整数値 (Int) のみ入れられることにします．
Val (value) は値を表します．Var (variable) と間違えないでください．

type Val = Int

type Env =  Var -> Val

また，プログラムが開始した段階での初期の環境を作っておきましょう．
各変数の初期値は 0 とします．

initEnv :: Env
initEnv A = 0
initEnv B = 0
initEnv C = 0
initEnv D = 0
initEnv E = 0
initEnv F = 0

全ての初期値が同じなので次のように書けます．

-- 上のかわり
initEnv :: Env
initEnv _ = 0

意味函数の作成

意味函数は，式や文から意味を読み取る函数です．
ここでは，式の値を読んだり文を実行する函数として作成します．

式に対する意味函数

式の値を読むには，式中で使われている変数の値が必要です．
即ち，式を読むには変数の値を読み出すもの，環境が必要です．

函数 mexp :: Exp -> Env -> Val は式 (Exp) と環境 (Env) から値 (Val) を読み出します．

変数 1 つからなる式のときは，環境から変数の値が読み出せるので簡単です．

mexp :: Exp -> Env -> Val
mexp (VAR x) env = env x

また定数 1 つからなる式の時は，その定数の値を読みます．
定数は環境に依存しないので，環境は使いません．

-- mexp の続き
mexp (CST C0) _ = 0
mexp (CST C1) _ = 1
mexp (CST C2) _ = 2
mexp (CST C3) _ = 3
mexp (CST C4) _ = 4
mexp (CST C5) _ = 5
mexp (CST C6) _ = 6
mexp (CST C7) _ = 7
mexp (CST C8) _ = 8
mexp (CST C9) _ = 9

式1 :+: 式2, 式1 :-: 式2 の形をした式は，それぞれの式を読んで結果を足し引きします．

-- mexp の続き
mexp (exp1 :+: exp2) env = mexp exp1 env + mexp exp2 env
mexp (exp1 :-: exp2) env = mexp exp1 env - mexp exp2 env

以上をまとめると mexp は次のようになります．

-- mexp 全体
mexp :: Exp -> Env -> Val
mexp (VAR x) env = env x
mexp (CST C0) _ = 0
mexp (CST C1) _ = 1
mexp (CST C2) _ = 2
mexp (CST C3) _ = 3
mexp (CST C4) _ = 4
mexp (CST C5) _ = 5
mexp (CST C6) _ = 6
mexp (CST C7) _ = 7
mexp (CST C8) _ = 8
mexp (CST C9) _ = 9
mexp (exp1 :+: exp2) env = mexp exp1 env + mexp exp2 env
mexp (exp1 :-: exp2) env = mexp exp1 env - mexp exp2 env

文に対する意味函数

文を実行するということは，変数の値を変化させることになります．
即ち，文を実行するということは環境を変化させることになります．

函数 mcmd :: Cmd -> Env -> Env は文 (Cmd) を実行し，環境 (Env) を新しいものに変化させます．

まず代入文 変数 := 式 を考えます．
この文は式の値を変数に代入しています．
つまり，まず式の値を mexp で読み，その結果をもとに変数の値を，即ち環境を変えます．

mcmd :: Cmd -> Env -> Env
mcmd (var := exp) env = newenv
  where val = mexp exp env    -- 式の値を読む
        newenv x              -- 新しい環境 (変数から値を読む函数) の作成
          | x == var  = val
          | otherwise = env x -- 変更する以外の変数についての環境は元のまま

次に分岐文 IFEQ 式1 式2 文1 文2 です．これは単純に各式の値を mexp で読み，等しければ 文1 を，等しくなければ 文2 を実行します．

-- mcmd の続き
mcmd (IFEQ exp1 exp2 cmdt cmdf) env = 
  if mexp exp1 env == mexp exp2 env
    then mcmd cmdt env
    else mcmd cmdf env

反復文 FOR 式 文 は，まず式の値を mexp で読み，それが 0 より大きければ文を 1 度実行 (mcmd cmd env) し，式の値を 1 つ小さくします (exp :-: CST C1)．
then 節では，新しい環境として mcmd cmd env の結果を与えていることに注意してください．

-- mcmd の続き
mcmd (FOR exp cmd) env = 
  if mexp exp env > 0
    then mcmd (FOR (exp :-: CST C1) cmd) (mcmd cmd env)
    else env

上の FOR の実装では，ループ中に FOR 内の式の値が変わることを許していますが，それを許さない (FOR でループする回数はループ中は固定する) のであれば次のように書けます．

-- FOR についての異なる実装
mcmd (FOR exp cmd0) env0 = loop (mexp exp env0) cmd0 env0
  where loop times cmd env
          | times > 0 = loop (times - 1) cmd (mcmd cmd env)
          | otherwise = env

何もしない文 NOOP は，何も実行しないので，もとの環境をそのまま返します．

-- mcmd の続き
mcmd NOOP env = env

最後に，順次実行文 文1 :| 文2 はただ 文1, 文2 を順番に実行すれば OK です．
文1 を実行した時点で環境が変わるかもしれないので，文2 にはその新しい環境 (つまり mcmd cmd1 env の結果) を与えます．

-- mcmd の続き
mcmd (cmd1 :| cmd2) env = mcmd cmd2 (mcmd cmd1 env)

以上をまとめると mcmd は次のようになります．

-- mcmd 全体
mcmd :: Cmd -> Env -> Env
mcmd (var := exp) env = newenv
  where val = mexp exp env
        newenv x
          | x == var  = val
          | otherwise = env x
mcmd (IFEQ exp1 exp2 cmdt cmdf) env = 
  if mexp exp1 env == mexp exp2 env
    then mcmd cmdt env
    else mcmd cmdf env
mcmd (FOR exp cmd0) env0 = loop (mexp exp env0) cmd0 env0
  where loop times cmd env
          | times > 0 = loop (times - 1) cmd (mcmd cmd env)
          | otherwise = env
mcmd NOOP env = env
mcmd (cmd1 :| cmd2) env = mcmd cmd2 (mcmd cmd1 env)

プログラム実行用の函数

プログラム全体は文でできているので mcmd で実行できますが，初期環境を与えて実行する run 函数を作成しておきます．

type Program = Cmd

run :: Program -> Env
run cmd = mcmd cmd initEnv

Env の実態は Var -> Val という函数だったので，このままでは表示しにくいです．
そこで，実行終了後の変数の値を全て表示する函数も作成しておきましょう．

result :: Program -> [Val]
result cmd =
 let env = run cmd
 in  [env A, env B, env C, env D, env E, env F]

プログラムを作り実行してみる

例 1: 1 + 2 の計算

1 + 2 を計算するプログラムを作ってみます．

1. 変数 A に 1 (つまり C1) を代入
2. 変数 B に 2 (つまり C2) を代入
3. 変数 C に A + B (つまり A :+: B) の結果を代入

ということで，プログラムは次のようになります．

program1 :: Program
program1 = A := CST C1 :| B := CST C2 :| C := VAR A :+: VAR B

見やすいように :| で改行すると次のようになります．

program1 :: Program
program1 = 
  A := CST C1 :|
  B := CST C2 :|
  C := VAR A :+: VAR B

ここで，A だったり VAR A だったりするのは要求されているのが変数 (Var) なのか式 (Exp) なのかという違いによります．

実行してみましょう．

ghci

*Main> result program1
[1,2,3,0,0,0]

変数 C (左から 3 番目) に答えが入っているのがわかります．

例 2: 1 から 9 までの数をたす

1. 変数 A に 0 (つまり C0) を代入
2. 変数 B に 0 (つまり C0) を代入
3. 以下の内容を 9 回ループする

• 変数 B に B :+: C1 を代入 (B の値を 1 増やす)
• 変数 A に A :+: B を代入

program2 :: Program
program2 = 
  A := CST C0 :|
  B := CST C0 :|
  FOR (CST C9) (
    B := VAR B :+: CST C1 :|
    A := VAR A :+: VAR B
  )

実行結果

ghci

*Main> result program2
[45,9,0,0,0,0]

例3: 掛け算

変数 A と変数 B の値を掛け算し，変数 C に代入する．
例えば以下の例は 7 × 4

program3 :: Program
program3 = 
  A := CST C7 :|
  B := CST C4 :|
  C := CST C0 :|
  FOR (VAR B) (C := VAR C :+: VAR A)

実行結果

ghci

*Main> result program3
[7,4,28,0,0,0]

例4: 正負判定

FOR 文の式の値が 0 以下のときは何も実行しない仕様を利用して正負判定しています．
変数 A の値が 0 か正数なら変数 B に 1 を， A が負数なら B に 0 を代入しています．

program4 :: Program
program4 =
  A := CST C5 :| -- A は 5

  IFEQ (VAR A) (CST C0)
    (B := CST C1)
    (
       C := VAR A :|
       FOR (VAR A) (
         C := VAR C :-: CST C1
       ) :|
       IFEQ (VAR C) (CST C0) (B := CST C1) (B := CST C0)
    )

実行結果

*Main> result program4
[5,1,0,0,0,0]

作成したソースコード全体

data Var = A | B | C | D | E | F
  deriving (Show, Eq)

data Cst = C0 | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9
  deriving (Show)

infixl 6 :+: 
infixl 6 :-:
data Exp = VAR Var | CST Cst | Exp :+: Exp | Exp :-: Exp
  deriving (Show)

infixl 0 :|
infix 4 :=
data Cmd = Var := Exp
         | IFEQ Exp Exp Cmd Cmd
         | FOR Exp Cmd
         | NOOP
         | Cmd :| Cmd
  deriving (Show)

type Val = Int

type Env =  Var -> Val

initEnv :: Env
initEnv _ = 0

mexp :: Exp -> Env -> Val
mexp (VAR x) env = env x
mexp (CST C0) _ = 0
mexp (CST C1) _ = 1
mexp (CST C2) _ = 2
mexp (CST C3) _ = 3
mexp (CST C4) _ = 4
mexp (CST C5) _ = 5
mexp (CST C6) _ = 6
mexp (CST C7) _ = 7
mexp (CST C8) _ = 8
mexp (CST C9) _ = 9
mexp (exp1 :+: exp2) env = mexp exp1 env + mexp exp2 env
mexp (exp1 :-: exp2) env = mexp exp1 env - mexp exp2 env

mcmd :: Cmd -> Env -> Env
mcmd (var := exp) env = newenv
  where val = mexp exp env
        newenv x
          | x == var  = val
          | otherwise = env x
mcmd (IFEQ exp1 exp2 cmdt cmdf) env = 
  if mexp exp1 env == mexp exp2 env
    then mcmd cmdt env
    else mcmd cmdf env
mcmd (FOR exp cmd0) env0 = loop (mexp exp env0) cmd0 env0
  where loop times cmd env
          | times > 0 = loop (times - 1) cmd (mcmd cmd env)
          | otherwise = env
mcmd NOOP env = env
mcmd (cmd1 :| cmd2) env = mcmd cmd2 (mcmd cmd1 env)

type Program = Cmd

run :: Program -> Env
run cmd = mcmd cmd initEnv

result :: Program -> [Val]
result cmd =
 let env = run cmd
 in  [env A, env B, env C, env D, env E, env F]


program1 :: Program
program1 = 
  A := CST C1 :|
  B := CST C2 :|
  C := VAR A :+: VAR B

program2 :: Program
program2 = 
  A := CST C0 :|
  B := CST C0 :|
  FOR (CST C9) (
    B := VAR B :+: CST C1 :|
    A := VAR A :+: VAR B
  )

program3 :: Program
program3 = 
  A := CST C7 :|
  B := CST C4 :|
  C := CST C0 :|
  FOR (VAR B) (C := VAR C :+: VAR A)

program4 :: Program
program4 =
  A := CST C5 :| -- A は 5

  IFEQ (VAR A) (CST C0)
    (B := CST C1)
    (
       C := VAR A :|
       FOR (VAR A) (
         C := VAR C :-: CST C1
       ) :|
       IFEQ (VAR C) (CST C0) (B := CST C1) (B := CST C0)
    )

課題

今回は定数を C0, C1, C2, C3, C4, C5, C6, C7, C8, C9 の 10 個としましたが，例えば

data Cst = Cst Int
  deriving (Show)

などとしてプログラムを変更してみてください．

また，よりよい if や for などの制御構造，その他命令を考えてみてください．

他，モナド等を使って書きなおすことも出来ると思います．

おまけ

おまけ 1

変数に自由に名前を付けられるように，また定数として Int 型の値を使えるように (上の課題) 変更してみました．

data Var = Var String
  deriving (Show, Eq)

data Cst = Cst Int
  deriving (Show)

infixl 6 :+: 
infixl 6 :-:
data Exp = VAR Var | CST Cst | Exp :+: Exp | Exp :-: Exp
  deriving (Show)

infixl 0 :|
infix 4 :=
data Cmd = Var := Exp
         | IFEQ Exp Exp Cmd Cmd
         | FOR Exp Cmd
         | NOOP
         | Cmd :| Cmd
  deriving (Show)

type Val = Int

type Env =  Var -> Val

initEnv :: Env
initEnv _ = 0

mexp :: Exp -> Env -> Val
mexp (VAR v) env = env v
mexp (CST (Cst c)) _ = c
mexp (exp1 :+: exp2) env = mexp exp1 env + mexp exp2 env
mexp (exp1 :-: exp2) env = mexp exp1 env - mexp exp2 env

mcmd :: Cmd -> Env -> Env
mcmd (var := exp) env = newenv
  where val = mexp exp env
        newenv x
          | x == var  = val
          | otherwise = env x
mcmd (IFEQ exp1 exp2 cmdt cmdf) env = 
  if mexp exp1 env == mexp exp2 env
    then mcmd cmdt env
    else mcmd cmdf env
mcmd (FOR exp cmd0) env0 = loop (mexp exp env0) cmd0 env0
  where loop times cmd env
          | times > 0 = loop (times - 1) cmd (mcmd cmd env)
          | otherwise = env
mcmd NOOP env = env
mcmd (cmd1 :| cmd2) env = mcmd cmd2 (mcmd cmd1 env)

type Program = Cmd

run :: Program -> Env
run cmd = mcmd cmd initEnv

result :: Program -> String -> Val
result cmd str = run cmd (Var str)


program1 :: Program
program1 = 
  Var "A" := CST (Cst 1) :|
  Var "B" := CST (Cst 2) :|
  Var "C" := VAR (Var "A") :+: VAR (Var "B")

program2 :: Program
program2 = 
  Var "A" := CST (Cst 0) :|
  Var "B" := CST (Cst 0) :|
  FOR (CST (Cst 9)) (
    Var "B" := VAR (Var "B") :+: CST (Cst 1) :|
    Var "A" := VAR (Var "A") :+: VAR (Var "B")
  )

program3 :: Program
program3 = 
  Var "X" := CST (Cst 7) :|
  Var "Y" := CST (Cst 4) :|
  Var "Z" := CST (Cst 0) :|
  FOR (VAR (Var "Y")) (Var "Z" := VAR (Var "Z") :+: VAR (Var "X"))

program4 :: Program
program4 =
  Var "num" := CST (Cst 5) :| -- num は 5

  IFEQ (VAR (Var "num")) (CST (Cst 0))
    (Var "res" := CST (Cst 1))
    (
       Var "tmp" := VAR (Var "num") :|
       FOR (VAR (Var "num")) (
         Var "tmp" := VAR (Var "tmp") :-: CST (Cst 1)
       ) :|
       IFEQ (VAR (Var "tmp")) (CST (Cst 0))
         (Var "res" := CST (Cst 1))
         (Var "res" := CST (Cst 0))
    )

環境という函数を更新していくだけで，変数の値を保存しておくデータ型を作る必要がないのがおもしろいです．

おまけ 2

State を使って書きなおしてみました．

import Control.Monad.State

data Var = Var String
  deriving (Show, Eq)

data Cst = Cst Int
  deriving (Show)

infixl 6 :+: 
infixl 6 :-:
data Exp = VAR Var | CST Cst | Exp :+: Exp | Exp :-: Exp
  deriving (Show)

infixl 0 :|
infix 4 :=
data Cmd = Var := Exp
         | IFEQ Exp Exp Cmd Cmd
         | FOR Exp Cmd
         | NOOP
         | Cmd :| Cmd
  deriving (Show)

type Program = Cmd

type Val = Int

type Env =  Var -> Val


mexp :: Exp -> State Env Val
mexp (VAR v) = gets $ \env -> env v
mexp (CST (Cst c)) = return c
mexp (exp1 :+: exp2) = liftM2 (+) (mexp exp1) (mexp exp2)
mexp (exp1 :-: exp2) = liftM2 (-) (mexp exp1) (mexp exp2)


mcmd :: Cmd -> State Env ()
mcmd (var := exp) = do
  val <- mexp exp
  env <- get
  put $ \x -> if (x == var) then val else env x
mcmd (IFEQ exp1 exp2 cmdt cmdf) = do
  a <- mexp exp1
  b <- mexp exp2
  if a == b then mcmd cmdt else mcmd cmdf
mcmd (FOR exp cmd) = mexp exp >>= loop
  where loop times
          | times > 0 = mcmd cmd >> loop (times - 1)
          | otherwise = mcmd NOOP
mcmd NOOP = return ()
mcmd (cmd1 :| cmd2) = mcmd cmd1 >> mcmd cmd2


initEnv :: Env
initEnv = const 0

run :: Program -> Env
run cmd = execState (mcmd cmd) initEnv

result :: Program -> String -> Val
result cmd str = run cmd (Var str)


program1 :: Program
program1 = 
  Var "A" := CST (Cst 1) :|
  Var "B" := CST (Cst 2) :|
  Var "C" := VAR (Var "A") :+: VAR (Var "B")

program2 :: Program
program2 = 
  Var "A" := CST (Cst 0) :|
  Var "B" := CST (Cst 0) :|
  FOR (CST (Cst 9)) (
    Var "B" := VAR (Var "B") :+: CST (Cst 1) :|
    Var "A" := VAR (Var "A") :+: VAR (Var "B")
  )

program3 :: Program
program3 = 
  Var "X" := CST (Cst 7) :|
  Var "Y" := CST (Cst 4) :|
  Var "Z" := CST (Cst 0) :|
  FOR (VAR (Var "Y")) (Var "Z" := VAR (Var "Z") :+: VAR (Var "X"))

program4 :: Program
program4 =
  Var "num" := CST (Cst 5) :| -- num は 5

  IFEQ (VAR (Var "num")) (CST (Cst 0))
    (Var "res" := CST (Cst 1))
    (
       Var "tmp" := VAR (Var "num") :|
       FOR (VAR (Var "num")) (
         Var "tmp" := VAR (Var "tmp") :-: CST (Cst 1)
       ) :|
       IFEQ (VAR (Var "tmp")) (CST (Cst 0))
         (Var "res" := CST (Cst 1))
         (Var "res" := CST (Cst 0))
    )

env を引きずりまわしているのが見えなくなったので簡潔になりましたが，読みやすいかどうかは微妙です．
mcmd (cmd1 :| cmd2) = mcmd cmd1 >> mcmd cmd2 あたりが面白いですね．

参考

横内寛文 (1994)『プログラム意味論』共立出版．