この記事では、レイジーコンピューティングとは何か、それらを何に使用できるか、そしてそれらを使用する際のパフォーマンスの低下を回避する方法について説明しようとします。
レイジーコンピューティングとは何ですか？
怠notではない通常のプログラミング言語では、計算は厳密です。つまり、関数自体の実行前に関数の引数が評価されます。
たとえば、いくつかの抽象的な厳密なプログラミング言語では：
max(5+3, 4*4) ->
max(8, 4*4) ->
max(8, 16)
16
また、Haskellなどの遅延言語では、計算が延期されます。 すべての計算（一部のI / O関数を除く）はすぐには実行されませんが、実際には必要になるまで延期されます。
Haskellの同じ例：
max (5+3) (4*4) ->
let x = 5+3; y = 4*4 in if x >= y then x else y ->
let x = 8; y = 4*4 in if 8 >= y then 8 else y ->
let x = 8; y = 16 in if 8 >= 16 then 8 else 16 ->
16
この例は、部分式（5 + 3および4 * 4）の計算が最後まで、つまり、比較する必要がある瞬間まで延期されたことを明確に示しています。
ここで、計算を実行した「力」は、コンソールへの出力、つまり IO。 しかし、これが唯一の方法ではありません。
約束
次の例をご覧ください。
let z = (sum [1..10], reverse "haskell") in ...
（さらに、zが一部で使用されると仮定します。そうでない場合、式はまったく評価されません）
zは約束（eng。thunk）であり、計算値ではありません。
サンプルzと比較するとどうなりますか？
let z = (sum [1..10], reverse "haskell") (x, y) = z in ...
最初に、zは前の例のように単純なプロミスですが、コンパイラがzがパターンに実際に一致することを確認できるように、zは次の形式に「拡張」する必要があります：
(**, **)
。 xとyは、ペアzのコンポーネントに対応するプロミスです。
サンプルとの比較をもう1つ追加します。
let z = (sum [1..10], reverse "haskell") (x, y) = z 'l':ys = y in ...
yがリストであることを確認するために、コンパイラはそれを次の形式に評価します。
** : **
次に、彼は最初の約束を計算します：
'l' : **
yが 'l'で始まるリストであることを確認し、パターンに一致します：
'l':ys = 'l':**
この例では、ysはリストyの残りに対応するプロミスになります。
すべての例でzの計算の深さがどのように変化したかを見てみましょう。
**
(**, **)
(**, 'l':**)
zは部分的に計算されました。ご想像のとおり、Haskellのほとんどすべての値はこの方法で計算できます。 たとえば、ペアの最小の計算は、コンストラクターを評価することです
(**, **)
。 リストの場合、これは
**:**
または[]です。 しかし、この形式の数字は存在しません-それらは計算されるかされないかのどちらかです。
値が完全に計算されていない場合、彼らはそれが弱い頭部正規形 （WHNF）にあり、完全に計算されている場合、 正規形にあると言います 。 WHNFの値は、完全に計算されると「標準形」になります。 たとえば、画面にzを表示すると、その標準形は
(55,"lleksah")
ます。 明らかに、コンストラクタに引数がない値はWHNFに入れることはできません。 つまり、Bool、Ord、IntなどのタイプにはWHNFがなく、Maybe、[a]、Etherなどのタイプがあります。 持っています。
遅延関数
関数は引数が遅延的で厳密です。 遅延-引数を計算せず、厳密-任意の深さまで計算します。 ある引数では関数が遅延し、別の引数では厳密になる可能性があることに注意してください。 もちろん、ほとんどの関数は何らかの方法で引数を使用する必要があり、これは計算を意味します。 たとえば、長さ関数。 リストの長さを調べるには、値ではなくコンストラクタを計算する必要があります。 つまり、
length **
は、「
length (** : ** : ** : [])
」のように「拡張」されます。
関数が引数で遅延しているかどうかを確認する簡単な方法があります。 未定義の引数の代わりに渡すだけで、結果がエラーの場合、関数はこの引数で厳密になり、そうでない場合は遅延します。
エラーになりません：
const 5 undefined
Just undefined
これらは次のようになります。
length undefined
head undefined
遅延パターン比較
関数は遅延するだけでなく、サンプルとの比較もできます。 既に調査したサンプルとの厳密な比較とは対照的に、怠け者は計算を約束しません。つまり、コンパイル中にそれらを「展開」しません。
例：
> let f ~(x, y) = 1
> f undefined
1
ここで
~(x, y)
は遅延パターンです。 遅延関数の引数と同じプロパティがあります：未定義の引数を渡すと、エラーは発生しません。
このようなサンプルとの比較は、Control.Arrowで確認できます。
(***) fg ~(x, y) = (fx, gy)
> (const 1 *** const 2) undefined
(1, 2)
ただし、型に1つのコンストラクターがある場合にのみ、遅延パターンを使用する必要があることを覚えておく必要があります。
例：
head' :: [a] -> a
head' ~[] = undefined
head' ~(x:xs) = x
必要になるまで関数引数を計算する必要がないことを指摘したので、目の前にあるもの、つまり空のリストまたはそのリンクの1つを見つけることはできません。 最初の式では反論できないパターンを使用したため、関数は常に未定義を返します。
レイジーコンピューティングの使用
需要計算
遅延コンピューティングの最も明白な利点は、何かが必要でない場合、計算されないことです。
例：
(&&) False _ = False
(&&) True a = a
and関数の最初の引数がFalseの場合、結果がFalseになることがすでに明らかな場合、なぜ2番目の引数を計算しますか？ おそらく、2番目の引数の意味を調べるには、多くの時間のかかる計算が必要になりますが、これは遅延計算を使用して回避できます。
最小の3つのリストアイテムを検索するとします。
Haskellでは、これは次のように実行できます。
take 3 (sort xs)
しかし、厳密な言語では、リスト全体をソートする必要があるため、これは無駄です。 しかし、遅延計算では、リストを3番目の要素にソートして停止します。これは、計算を続行する意味がないためです。
メモ化
次の機能を検討してください。
plus a = a+a
> plus (5+3)
16
5と3の合計は何回計算されましたか？ 正解：一度。 最初は（5 + 3）-単なる約束ですが、プラス関数に渡されると計算され、彼の答えが約束そのものに取って代わりました。 aの値が2度要求されたとき、プログラムは計算を行わずに、前の約束から完成した結果を取得しました。 これは、レイジーコンピューティングの最も重要なプロパティの1つであるメモ化です。 遅延言語のプロミスは一度だけ計算され、計算の結果はプロミスを「上書き」するため、プログラムは再度計算する必要なく、答えを簡単に見つけることができます。
レイジーコンピューティングのこの特性は、動的プログラミングのアプリケーションを見つけます。これは、記事「 ダイナミックプログラミングとレイジーコンピューティング 」でよく示されています。
無限のループデータ構造
遅延コンピューティングのもう1つのかなりよく知られているアプリケーションは、無限のデータ構造の作成です。
> [1, 3..] !! 10
21
ここで、奇数の無限リストを作成し、その10番目の要素を取得します。
例はもっと複雑です：
> fibs = 1:1:zipWith (+) fibs (tail fibs)
> fibs !! 100
573147844013817084101
無限リストの作成は、それらがすぐに計算されないためにのみ可能です。 2番目の例では、fibsは最初に
1:1:**
になりますが、このリストの次の要素を要求すると、プログラムはニーズが満たされるまで
1:1:**
を満たさなければなりません。 1つの約束が他の約束を生み出す可能性があるため、短いリストと約束から、フィブナッチはフィボナッチ数の巨大なチェーンに変わる可能性があります。
次に、循環データ構造に進みましょう。
data List a = List {value :: a, next :: List a}
このタイプの2つの要素をリングに接続して、あるオブジェクトの次のフィールドが別のフィールドを指すようにする方法を教えてください。
命令型言語でこれを行いたい場合、ポインターを使用しますが、Haskellにはポインターはありません。 それでは、そのような構造を作成する方法は？
非常にシンプル：
let x = List "x" y
y = List "y" x
in x
以上です。 List nextフィールドは遅延型であるため（型コンストラクタは同じ関数であり、引数は遅延型であることを覚えておく必要があります）、このような「リング」を作成しても、構造全体を計算しようとしてプログラムがフリーズすることはありません。
> value . next $ x
"y"
レイジーI / O
単純なI / O関数だけが本当に厳密で、残りは怠zyです。 これにより、バッファを使用せずに、パイプライン上でファイルをオンザフライで読み書きできます。
例：
import Data.Char
main = print . map toUpper =<< getContents
プログラムは、到着時にテキストを大文字で表示します。
レイジーコンピューティングの使用に関する問題
記事全体を通して、「約束」という用語を使用して遅延計算の単位を意味しましたが、実際にはこれは単なる抽象概念ではありません。 コンパイルされたHaskellプログラムは、実際にメモリ内およびスタック上のスペースを占有するプロミスを使用します。 つまり、ガベージコレクション、メモリ割り当て、およびプロミスの開発が、従来のコンピューティングのコストに追加されます。 これは、レイジーコンピューティングの主な問題です-読み書きができないため、パフォーマンスの大幅な低下、スタックオーバーフロー、および高いメモリ消費を支払うことができます。
しかし、計算の遅延を少なくする方法があります。これを考慮します。
シーケンス
この簡単な例を考えてみましょう。
main = print . sum' $ [1..1e6] sum' [] = 0 sum' (l:ls) = l + sum' ls
ここで、1から1e6までの数字の合計を見つけて、コンソールに出力します。 ただし、プログラムを実行しようとすると、次のメッセージが表示されます。
$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
スタックオーバーフローが発生するのはなぜですか？ 合計関数がどのように計算されるか見てみましょう：
1 + (1 + (1 + ... (1 + sum' [])))
sum' ls
計算
sum' ls
遅れるため、スタック上のスペースを占有する入れ子になったたくさんのプロミスを取得します。 これを取り除くためには、累積ではなく、何らかの形で約束を計算する必要があります。 このために、seq関数があります。 2つの引数を取ります。最初の引数が評価され、2番目の引数が返されます。 ここで適用してみましょう。
最初に、末尾の再帰を使用するためにsum関数を書き換えます。
main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = go (l + n) ls
これで、加算を計算することは難しくありません：
main = print . sum' $ [1..1e6] sum' ls = go 0 ls where go n [] = n go n (l:ls) = let s = l + n in s `seq` go s ls
Seqは、後で加算するのではなく、量を強制的に計算します。
$ ./test
5.000005e11
これでエラーは発生しません。
少し複雑な例を試してみましょう。要素の合計に加えて、その数も計算します。
main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `seq` go t ls
$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
再び同じ間違い。 しかし、なぜですか？ 金額を計算しましたか？
seqの1つのプロパティについて説明します。WHNFの値を計算します。 前述のように、通常の数値にはWHNFがないため、加算はseqによって完全に計算されました。 しかし、この場合、WHNFを持つペア、つまり
(**, **)
を計算しようとしています。 そのため、約束はまだ積み上げられており、スタックオーバーフローが発生します。 seqを使用して、フィールドを強制的に計算できます。
main = print . sum' $ [1..1e6] sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let s = l + n d' = d + 1 in s `seq` d' `seq` go (s, d') ls
$ ./test
(5.000005e11,1000000)
少しいですが、動作します。 何かを完全に計算する必要がある状況はそれほどまれではないため、このために特別なモジュールが作成されました。 試してみましょう：
import Control.DeepSeq (deepseq) main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (n, d) [] = (n, d) go (n, d) (l:ls) = let t = (l + n, d + 1) in t `deepseq` go t ls
deepseq関数は、正規形までの値を完全に計算します。
バングパターン
厳密さをより便利に示すために、コンパイラー拡張機能-Bangパターンが作成されました。 引数の重大度を感嘆符で示すことができます。 この拡張機能を使用して、次のようにコードを書き換えることができます。
{-# LANGUAGE BangPatterns #-} main = print . sum' $ [1..10^6] sum' :: [Integer] -> (Integer, Int) sum' ls = go (0, 0) ls where go (!n, !d) [] = (n, d) go (!n, !d) (l:ls) = go (l + n, d + 1) ls
すべてが以前と同じように機能します。
バングパターンを使用すると、関数の引数だけでなく、次のようなデータ構造のフィールドの重大度も指定できます。
{-# LANGUAGE BangPatterns #-} data SPair ab = SPair !a !b deriving Show main = print . sum' $ [1..10^6] sum' :: [Integer] -> SPair Integer Int sum' ls = go (SPair 0 0) ls where go (SPair nd) [] = SPair nd go (SPair nd) (l:ls) = go (SPair (l + n) (d + 1)) ls
$ ./test
SPair 500000500000 1000000
SPairは厳格なカップルです。 そのフィールドの値は常に計算されますが、これも約束の累積を許可しません。
おわりに
この記事では、レイジーコンピューティングに対処する方法を説明しようとしました。 読んだ後、遅延計算をどこでどのように適用するのが最適か、なぜそれらが必要なのかを理解し始めることを願っています。
使用材料のリスト
ハスケル/怠
プロファイリングと最適化