Moggiの計算言語

計算とモナドの概念 Moggiは、タイプ$の計算の概念をモデル化していますA
$、$ TA $、モナド$ T $を使用する。とりわけ、これは$ T eta $ルールを保証します:

$、 frac {x:A vdash a:TB} {x:A vを、y Leftarrow a 、、[y] =
a} $$

このルールは、同じ値を持つ別個の計算を防ぎます。 $ T eta
$ルールを生成しないモナドの弱体化した概念はありますか?この質問はすでに調査されていますか?私は単純なメタ言語のためのMoggiのルールから$
T eta $を落としても、他のルールはそのままにしておけば(特にpdfの表4)、ロジックに興味があります。

ベストアンサー

OPを悩ますものを理解することは興味深い問題です。まず第一に、OPによって提出された方程式は「異なる計算は同じ値を持つ」と言っているわけではない。例えば、計算

do _ <- putStr "foo"
   return 42

そして

do _ <- putStr "bar"
   return 42

both “have” value 42 but are different, since one
prints out foo そして the other bar.

問題は実際には他の場所、すなわち “計算に値がある”
という考え方で発生します。次のモナドを考えてみましょう:

    モナド:計算に値( Just v )があるか、まったく値を持たない(
    Nothing

  1. 非決定論的モナド:計算結果は(可能な)値の集合になります。それは価値があるということは何を意味していますか?それらのすべてがありますか?その1つは?

  2. 確率モナド:計算によって値の確率分布が得られます。繰り返しますが、このような計算にはどのような意味がありますか?

  3. 継続モナド:計算結果が継続します。 「価値がある」という継続はどういう意味ですか?

一般に、計算によって値、2つの値、可能な値などが返されるという考えを忘れた方がよいでしょう。

特定のモナドがあるかもしれませんが、すべてのモナドではなく、「値を持つ計算」について話すのが理にかなっています。

OPはまた、計算の内在的特徴(1つの計算が別のものと異なるステップ数をとる)がモナドで表現可能であることを示唆している。これは当てはまりますが、モナドでキャプチャしたいインテンシブ機能(メモリ使用量、時間)が何であれ、モナドで明示的に公開する必要があります。たとえば、これを行うことができます:

data Timed a = Timing (a, Integer)

instance Monad Timed where
    return x = Timing (x, 0)
    (>>=) (Timing (x, n)) f = (let Timing (y, m) = f x in Timing (y, n + m + 1))

x :: Timed Integer
x = do u <- return 14
       v <- return 3
       return (u * v)

y :: Timed Integer
y = do u <- return 14
       v' <- return 1
       v'' <- return 2
       v <- return (v' + v'')
       return (u * v)

Here x そして y both “have” value
42, but the timing is different since y
takes four steps to compute そして x takes just two.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です