ReaderTパターンで言語処理系のenvを作る
このノートはhsとpursが混合しているので注意
昔書いたhsに、pursで書き足しているので。
↓たぶんだけど間違ってる
Haskellでevalを作るときにenvの実装にはいくつかの方法が思いつく
IORefを使う ref
Stateを使う
IORefとReaderを使う
これ
そもそもReaderモナドとは
Readerモナドは読み取り専用のStateモナドで、各所からGlobal定数にアクセスしたいときなどに使う
Readerを使わなくても、全ての関数の引数に持ち回せば実現できるが、こんな感じになる
evalを作成するときにReaderを使うことでenvを持ち回らずにenvにアクセスができるので簡潔な実装になる
実際、Readerモナドは、昔はEnvironment Monadと呼ばれていたらしい
IORef & Readerについて
この組み合わせのことを「ReaderTパターン」と呼ぶ
状態がネストしたりと、程々に複雑で、変更が局所的な場合に用いると良い ref
Readerモナドのみでは、環境から読み込むことしか出来ない
しかし、evalではAssignなど環境を書き換える必要も出てくる
そこでIORefと組み合わせる
ReaderとIORefを組み合わせることで、
Readr→envを持ち回さなくていい
IORef→envの書き換えができる
環境を表す型を定義する
purs(hs)import Data.List (List(..))
import Control.Monad.Reader.Trans (ReaderT)
import Effect.Ref as Ref
type Env = Map String Expr
type EnvRef = Ref.Ref (List Env)
newtype ExprEnv a = ExprEnv (ReaderT EnvRef Effect a)ホントは1行でも書けるが、扱いやすさのために3つにわけて定義している
Env が1階層の環境 EnvRef が親の環境も含む環境 Expr は自分で定義した言語処理系のASTの型のこと Map , List , Ref , ReaderT を使っていることいずれもポイントとなる1つずつ見ていく
Map String AST についてこれは1階層の環境の、変数名と式のMapになる
イメージ的には
これが
jsconst a = 2
const b = trueこうなる
Env.hs{ ("a", ExprInt 2), ("b", ExprBool True) }冗長になるので、
Map.fromList [..] を { .. } と表記している List Env についてlocal目線で、親の環境も含めた環境になる
Listの先頭要素が今の環境で、2つ目の要素が親の環境、3つ目がそのまた親の環境、..になる
こうすることで、親の環境と名前が被るときも区分して保存することができる
イメージ的には
このとき
js// 視点①
const a = 2
const b = 10
const c = () => {
// 視点②
const a = 200
return a * b
}こうなる
Env.hs-- 視点①のList Env
[ { ("a", ExprInt 2), ("b", ExprInt 10), ("c", ExprFn ..) } ]Env.hs-- 視点②のList Env
[ { ("a", ExprInt 200)}
, { ("a", ExprInt 2), ("b", ExprInt 10), ("c", ExprFn ..) }
]どこの視点で見るかによって
List Env の内容が変わるということもポイント「アプリケーション全ての環境」を保持しているわけではない
その視点から参照しうる部分だけを保持しておけば十分
関数
c の中で、 a と b の演算を行っているが、その際に今の環境にその変数があるならソレを使う(
a )今の環境にその変数がないなら親の環境を探す(
b )とやっていけば、仕様通りの実装ができることがわかる
Ref.Ref (..) について List Env 自体を Ref で囲んでいる順番を変えて、
List (Ref.Ref Env) にするというケースもある例えばMake a Lispのhs実装はそうやってる
Ref.Ref String とすれば、そこに任意の文字列を可変参照できるのと同様に、 Ref.Ref (List Env) とすれば、環境をまるごと可変参照できるようになる ReaderT EnvRef Effect a についていわゆるReaderTパターンの定義
EnvRef を参照できるように第2引数に定義している環境から読み込むタイミングはいつか
envから読み込む
Var x : その変数束縛されている値を読み込む App f x : その関数名に束縛されているargとbodyを読み込む書き込む
Assign v x : 変数名に、値や関数を束縛する Lambda arg body : argにbodyを束縛する App f x : 仮引数に実引数を束縛する参考