javascript - トランポリンを継続パススタイルに適応させるには?

Question

以下は、右折りの単純な実装です。

const foldr = f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc 
    : f(x) (foldkr(f) (acc) (xs));

これは非末尾再帰であるため、トランポリンを適用できません。1 つのアプローチは、アルゴリズムを反復させ、スタックを使用して関数呼び出しスタックを模倣することです。

別のアプローチは、再帰を CPS に変換することです。

const Cont = k => ({runCont: k});

const foldkr = f => acc => ([x, ...xs]) =>
  Cont(k =>
    x === undefined
      ? k(acc)
      : foldkr(f) (acc) (xs)
          .runCont(acc_ => k(f(x) (acc_))));

非常に遅いため、これはまだ単純です。メモリ消費量の少ないバージョンを次に示します。

const foldkr = f => acc => xs => {
  const go = i =>
    Cont(k =>
      i === xs.length
        ? k(acc)
        : go(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_))));

  return go(0);
};

再帰呼び出しは末尾の位置にあるため、選択したトランポリンを適用できるはずです。

const loop = f => {
  let step = f();

  while (step && step.type === recur)
    step = f(...step.args);

  return step;
};

const recur = (...args) =>
  ({type: recur, args});

const foldkr = f => acc => xs =>
  loop((i = 0) => 
    Cont(k =>
      i === xs.length
        ? k(acc)
        : recur(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_)))));

これは機能しません。トランポリン呼び出しが継続内にあり、遅延評価されるためです。トランポリンを CPS で動作させるには、どのように適合させる必要がありますか?

score 6 · Accepted Answer

はい、はい、そしてはい (パート 2)

したがって、この答えはあなたの質問の核心に近づくと思います-再帰プログラムをスタックセーフにすることはできますか? 再帰が末尾の位置になくても? ホスト言語に末尾呼び出しの除去がない場合でも? はい。はい。はい、1 つの小さな要件があります...

私の最初の回答の最後は、一種の評価者として話しloop、次にそれがどのように実装されるかについての大まかなアイデアを説明しました。理論は良さそうですが、実際にこの手法が機能することを確認したかったのです。では、行きましょう！

重要なプログラム

フィボナッチはこれに最適です。二項再帰の実装は大きな再帰ツリーを構築し、どちらの再帰呼び出しも末尾位置にありません。このプログラムを正しく行うことができれば、loop正しく実装したという合理的な自信を持つことができます。

ここに小さな要件があります。関数を呼び出して再帰することはできません。の代わりにf (x)、次のように書きますcall (f, x) –

const add = (a = 0, b = 0) =>
  a + b

const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : add (recur (n - 1), recur (n - 2))
          : call (add, recur (n - 1), recur (n - 2))
    )

fib (10)
// => 55

しかし、これらcallとrecur関数は特別なものではありません。通常の JS オブジェクトのみを作成します –

const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

したがって、このプログラムではcall、2 つのに依存するがありrecurます。それぞれがさらにrecur別のを生成する可能性があります。確かに重要な問題ですが、実際には、明確に定義された再帰的なデータ構造を扱っているだけです。callrecur

書き込みloop

この再帰的なデータ構造を処理する場合、再帰的なプログラムとしてloop記述できれば簡単です。loopしかし、別の場所でスタックオーバーフローに遭遇するだけではないでしょうか? 確認してみましょう！

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? // todo: when given { type: recur, ... }
  : expr.type === call
      ? // todo: when given { type: call, ... }
  : k (expr) // default: non-tagged value; no further evaluation necessary

  return aux1 (f ())
}

したがってloop、ループする関数を取りますf。f計算が完了すると、通常の JS 値が返されることを期待しています。callそれ以外の場合は、またはのいずれかを返しrecur、計算を拡張します。

これらの todos は、記入するのがやや簡単です。

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    // todo: implement me

  return aux1 (f ())
}

直感的に、aux1(「補助的なもの」) は魔法の杖であり、 1 つの表現に手を振るexprと、resultが続きで戻ってきます。言い換えると -

// evaluate expr to get the result
aux1 (expr, result => ...)

recurorを評価callするには、まず対応するを評価する必要がありvaluesます。次のようなものを書きたいと思います–

// can't do this!
const r =
  expr.values .map (v => aux1 (v, ...))

return k (expr.f (...r))

続きは何でしょう...？aux1私たちはそのように呼び出すことはできません.map. 代わりに、式の配列を取り、結果の値をその継続に渡すことができる別の魔法の杖が必要です。などaux –

// evaluate each expression and get all results as array
aux (expr.values, values => ...)

ミート＆ポテト

わかりました、これはおそらく問題の最も難しい部分です。入力配列の各式に対して、継続を呼び出して次の式にチェーンし、最終的に値をユーザー提供のaux1継続に渡す必要があります。k

// aux : (('a expr) array, 'a array -> 'b) -> 'b
const aux = (exprs = [], k) =>
  exprs.reduce
    ( (mr, e) =>
        k => mr (r => aux1 (e, x => k ([ ...r, x ])))
    , k => k ([])
    )
    (k)

これを最終的に使用することはありませんが、通常のaux表現で何をしているのかを理解するのに役立ちます。reduceappend

// cont : 'a -> ('a -> 'b) -> 'b
const cont = x =>
  k => k (x)

// append : ('a array, 'a) -> 'a array
const append = (xs, x) =>
  [ ...xs, x ]

// lift2 : (('a, 'b) -> 'c, 'a cont, 'b cont) -> 'c cont
const lift2 = (f, mx, my) =>
  k => mx (x => my (y => k (f (x, y))))

// aux : (('a expr) array, 'a array -> 'b) -> 'b
const aux = (exprs = [], k) =>
  exprs.reduce
    ( (mr, e) =>
        lift2 (append, mr, k => aux1 (e, k))
    , cont ([])
    )

すべてをまとめると、

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    exprs.reduce
      ( (mr, e) =>
          k => mr (r => aux1 (e, x => k ([ ...r, x ])))
      , k => k ([])
      )
      (k)

  return aux1 (f ())
}

ちょっとしたお祝いの時間 –

fib (10)
// => 55

でも少しだけ――

fib (30)
// => RangeError: Maximum call stack size exceeded

あなたの元の問題

を修正しようとする前に、質問のプログラムをもう一度見loopてみましょう。foldrloopcallrecur

const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : f (recur (i + 1), xs[i])
          : call (f, recur (i + 1), xs[i])
    )

そして、それはどのように機能しますか？

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => RangeError: Maximum call stack size exceeded

わかりました、それは動作しますがsmall、スタックを爆破しますlarge。しかし、これは私たちが期待していたことですよね？結局のところ、loop避けられないスタックオーバーフローにバインドされている単なる通常の再帰関数です...そうですか？

先に進む前に、自分のブラウザでこの時点までの結果を確認してください –

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// recur : * -> 'a expr
const recur = (...values) =>
  ({ type: recur, values })

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    exprs.reduce
      ( (mr, e) =>
          k => mr (r => aux1 (e, x => k ([ ...r, x ])))
      , k => k ([])
      )
      (k)

  return aux1 (f ())
}

// fib : number -> number
const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              )
    )

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : call (f, recur (i + 1), xs[i])
    )

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

console .log (fib (10))
// 55

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, large))
// RangeError: Maximum call stack size exc

跳ねるループ

関数を CPS に変換し、トランポリンを使用してそれらをバウンスすることについて、私はあまりにも多くの答えを持っています。この答えはそれほど焦点を当てていません。上記ではCPS の末尾再帰関数としてaux1andを使用しています。aux次の変換は、機械的な方法で行うことができます。

他の回答で行ったように、見つけたすべての関数呼び出しについて、にf (x)変換します。call (f, x)

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return aux1 (f ())
  return run (aux1 (f ()))
}

単純化されたトランポリンであるでreturn包みます–run

// run : * -> *
const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

そして、それは現在どのように機能していますか？

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

fib (30)
// 832040

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => (Go and see for yourself...)

以下のスニペットを展開して実行することにより、任意のJavaScript プログラムでスタックセーフな再帰を確認できます –

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// recur : * -> 'a expr
const recur = (...values) =>
  ({ type: recur, values })

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

// run : * -> *
const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

// fib : number -> number
const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              )
    )

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : call (f, recur (i + 1), xs[i])
    )

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

console .log (fib (30))
// 832040

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, large))
// YES! YES! YES!

評価の可視化

を使用して単純な式を評価し、その魔法foldrがどのように機能するかを確認できるかどうかを見てみましょう–loop

const add = (a, b) =>
  a + b

foldr (add, 'z', [ 'a', 'b' ])
// => 'zba'

括弧の強調表示をサポートするテキストエディターにこれを貼り付けることで、従うことができます–

// =>
aux1
  ( call (add, recur (1), 'a')
  , identity
  )

// =>
aux1
  ( { call
    , f: add
    , values:
        [ { recur, values: [ 1 ]  }
        , 'a'
        ]
    }
  , identity
  )

// =>
aux
  ( [ { recur, values: [ 1 ]  }
    , 'a'
    ]
  , values => aux1 (add (...values), identity)
  )

// =>
[ { recur, values: [ 1 ]  }
, 'a'
]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (add (...values), identity))

// beta reduce outermost k
(k => (k => (k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => k ([ ...r, x ])))) (r => aux1 ('a', x => k ([ ...r, x ])))) (values => aux1 (add (...values), identity))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => k ([ ...r, x ])))) (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ])))

// beta reduce outermost k
(k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 ({ recur, values: [ 1 ]  }, x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...r, x ]))) ([])

// =>
aux1
  ( { recur, values: [ 1 ]  }
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ 1 ]
  , values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ 1 ]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 (1, x => k ([ ...r, x ])))) (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => k ([])) (r => aux1 (1, x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 (1, x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([])

// =>
aux1
  ( 1
  , x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])) (1)

// =>
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], 1 ])

// =>
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ 1 ])

// =>
aux1
  ( f (...[ 1 ])
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( f (1)
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( call (add, recur (2), 'b')
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( { call
    , f: add
    , values:
        [ { recur, values: [ 2 ] }
        , 'b'
        ]
    }
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ { recur, values: [ 2 ] }
    , 'b'
    ]
  , values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ { recur, values: [ 2 ] }
, 'b'
]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => (k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => k ([ ...r, x ])))) (r => aux1 ('b', x => k ([ ...r, x ])))) (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => k ([ ...r, x ])))) (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost k
(k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 ({ recur, values: [ 2 ] }, x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...r, x ]))) ([])

// =>
aux1
  ( { recur, values: [ 2 ] }
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ 2 ]
  , values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ 2 ]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 (2, x => k ([ ...r, x ])))) (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => k ([])) (r => aux1 (2, x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 (2, x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([])

// =>
aux1
  ( 2
  , x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])) (2)

// spread []
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], 2 ])

// beta reduce outermost values
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ 2 ])

// spread [ 2 ]
aux1
  ( f (...[ 2 ])
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( f (2)
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( 'z'
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])) ('z')

// spread []
(r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], 'z' ])

// beta reduce outermost r
(r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ 'z' ])

// =>
aux1
  ( 'b'
  , x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], x ])) ('b')

// spread ['z']
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], 'b' ])

// beta reduce outermost values
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ 'z', 'b' ])

// =>
aux1
  ( add (...[ 'z', 'b' ])
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( add ('z', 'b')
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( 'zb'
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])) ('zb')

// spead []
(r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], 'zb' ])

// beta reduce outermost r
(r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ 'zb' ])

// =>
aux1
  ( 'a'
  , x => (values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], x ])) ('a')

// spead ['zb']
(values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], 'a' ])

// beta reduce values
(values => aux1 (f (...values), identity)) ([ 'zb', 'a' ])

// spread [ 'zb', 'a' ]
aux1
  ( f (...[ 'zb', 'a' ])
  , identity
  )

// =>
aux1
  ( f ('zb', 'a')
  , identity
  )

// =>
aux1
  ( 'zba'
  , identity
  )

// =>
identity ('zba')

// =>
'zba'

閉鎖は確かに素晴らしいです。上で、CPS が計算をフラットに保つことを確認できます。各ステップでaux、aux1、または単純なベータ削減が見られます。これが私たちがloopトランポリンをすることを可能にするものです。

そして、これが私たちが二度漬けする場所callです。を使用してing 計算call用のオブジェクトを作成しますが、によって処理されるも吐き出します。このために別のタグを作成することもできました (作成する必要があったかもしれません) が、両方の場所で使用できるほど十分に汎用的でした。loopauxaux1callruncall

したがってaux (...)、およびaux1 (...)およびベータ削減が表示されている場所の上では、それらをそれぞれおよび(x => ...) (...)に置き換えるだけです。これらをに渡すだけです — 任意の形状または形式のスタックセーフな再帰。そのような単純なcall (aux, ...)call (aux1, ...)call (x => ..., ...)run

チューニングと最適化

loopは小さなプログラムですが、スタックの心配から心を解放するために膨大な量の作業を行っていることがわかります。loopが最も効率的でない場所もわかります。特に、非常に多くの残りのパラメーターとスプレッド引数 ( ...) に気付きました。これらは高価であり、それらなしで書くことができればloop、大きなメモリと速度の向上が期待できます –

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
  { switch (expr.type)
    { case recur:
        // rely on aux to do its magic
        return call (aux, f, expr.values, k)
      case call:
        // rely on aux to do its magic
        return call (aux, expr.f, expr.values, k)
      default:
        return call (k, expr)
    }
  }

  // aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
  const aux = (f, exprs = [], k) =>
  { switch (exprs.length)
    { case 0: // nullary continuation
        return call (aux1, f (), k) 
      case 1: // unary
        return call
          ( aux1
          , exprs[0]
          , x => call (aux1, f (x), k) 
          )
      case 2: // binary
        return call
          ( aux1
          , exprs[0]
          , x =>
            call
              ( aux1
              , exprs[1]
              , y => call (aux1, f (x, y), k) 
              )
          )
      case 3: // ternary ...
      case 4: // quaternary ...
      default: // variadic
        return call
          ( exprs.reduce
              ( (mr, e) =>
                  k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
              , k => call (k, [])
              )
          , values => call (aux1, f (...values), k)
          )
    }
  }

  return run (aux1 (f ()))
}

...そのため、ユーザーが 4 つ以上のパラメーターを持つループまたは継続を記述する場合にのみ、rest/spread ( ) に頼るようになりました。.reduceこれは、最も一般的なケースで使用される、非常に高価なバリアディアックリフトを回避できることを意味します。また、switchチェーンO(1)された三項?:式O(n).

これによりの定義がloop少し大きくなりますが、このトレードオフはそれだけの価値があります。予備測定では、速度が 100% 以上向上し、メモリが 50% 以上削減されたことが示されています。

// before
fib(30)      // 5542.26 ms (25.7 MB)
foldr(20000) //  104.96 ms (31.07 MB)

// after
fib(30)      // 2472.58 ms (16.29 MB)
foldr(20000) //   45.33 ms (12.19 MB)

もちろんloop、最適化できる方法は他にもたくさんありますが、この演習のポイントは、それらすべてを示すことではありません。loopは、必要に応じてリファクタリングを行うための快適さと自由を提供する、明確に定義された純粋な関数です。

パート 3 を追加:ループの能力を高める

score 5 · Accepted Answer

最初のテールコール (パート 1)

最初に、末尾の位置で繰り返されるようにループを記述します

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

small2 つの入力とが与えられた場合large、テストしますfoldr-

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => RangeError: Maximum call stack size exceeded

しかし、トランポリンを使用しているのに、なぜ失敗するのlargeでしょうか? 簡単な答えは、巨大な遅延計算を構築したためkです...

loop
  ( ( i = 0
    , k = identity // base computation
    ) =>
      // ...
      recur // this gets called 20,000 times
        ( i + 1
        , r => k (f (r, xs[i])) // create new k, deferring previous k
        )
  )

終了条件では、最終的k(init)に遅延計算のスタックを起動する呼び出し、20,000 の関数呼び出しが深く、スタックオーバーフローをトリガーします。

読み進める前に、以下のスニペットを展開して、同じページにいることを確認してください -

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const recur = (...values) =>
  ({ recur, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// RangeError: Maximum call stack size exceeded

遅延オーバーフロー

ここで見られる問題は、20,000 個の関数を一緒compose(...)に使用した場合に発生する可能性がある問題と同じです -pipe(...)

// build the composition, then apply to 1
foldl ((r, f) => (x => f (r (x))), identity, funcs) (1)

または同様の使用comp-

const comp = (f, g) =>
  x => f (g (x))

// build the composition, then apply to 1
foldl (comp, identity, funcs) 1

確かに、スタックセーフであり、20,000 の関数を構成できますが、大規模な構成を呼び出すとfoldlすぐに、スタックを吹き飛ばす危険があります。今それを比較してください -

// starting with 1, fold the list; apply one function at each step
foldl ((r, f) => f (r), 1, funcs)

...計算が延期されないため、スタックを吹き飛ばしません。代わりに、最後のステップに到達するまで、1 つのステップの結果が前のステップの結果を上書きします。

実際、私たちが書くとき -

r => k (f (r, xs[i]))

これを見る別の方法は -

comp (k, r => f (r, xs[i]))

これにより、問題がどこにあるかが正確に強調されるはずです。

可能な解決策

call簡単な解決策の 1 つは、トランポリンで遅延計算を平坦化する別のタグを追加することです。したがって、のように直接関数を呼び出す代わりに、次のようf (x)に記述しますcall (f, x)-

const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          // k (init) rewrite as
          ? call (k, init)
          : recur
              ( i + 1
              // r => k (f (r, xs[i])) rewrite as
              , r => call (k, f (r, xs[i]))
              )
   )

-タグ付けされた値に作用するようにトランポリンを変更しcallます-

const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

最後に、large入力がスタックをオーバーフローしていないことがわかります -

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => (Press "Run snippet" below see results ...)

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

const recur = (...values) =>
  ({ recur, values })
  
const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? call (k, init)
          : recur
              ( i + 1
              , r => call (k, f (r, xs[i]))
              )
   )
   
const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// (Press "Run snippet" to see results ...)

おっと、あなたは独自のエバリュエーターを構築しました

上記、recurおよびcall魔法の機能のように見えます。しかし実際には、単純なオブジェクトrecurを作成し、すべての作業を行っています。このように、はとの式を受け入れるタイプのエバリュエーターです。このソリューションの 1 つの欠点は、呼び出し元が常にまたはテール位置を使用することを期待していることです。そうしないと、ループは正しくない結果を返します。call{ ... }looplooprecurcall recurcall

これは、再帰メカニズムをパラメーターとして具体化する Y コンビネーターとは異なり、recurここのような末尾のみの位置に限定されません -

const Y = f => f (x => Y (f) (x))

const fib = recur => n =>
  n < 2
    ? n
    : recur (n - 1) + recur (n - 2) // <-- non-tail call supported
    
console .log (Y (fib) (30))
// => 832040

1 つのY欠点はもちろん、関数を呼び出して再帰を制御するため、JS の他のすべての関数と同様にスタックセーフではないことです。結果はスタックオーバーフローです -

console .log (Y (fib) (100))
// (After a long time ...)
// RangeError: Maximum call stack size exceeded

recurでは、テール以外の位置でサポートし、スタックセーフを維持することは可能でしょうか? 確かに、十分に賢い人loopは再帰式を評価できるはずです -

const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              ) 
    )

fib (30)
// expected: 832040

loopcallは、入力式、などを評価するための CPS 末尾再帰関数になります。次に、トランポリンrecurを置きます。効果的にカスタム言語の評価者になります。これで、スタックのことはすべて忘れることができます。唯一の制限はメモリです!looploop

あるいは -

const fib = (n = 0) =>
  n < 2
    ? n
    : call
        ( (a, b) => a + b
        , call (fib, n - 1)
        , call (fib, n - 2)
        )

loop (fib (30))
// expected: 832040

この関連する Q&Aでは、JavaScript で型なしラムダ計算の正規順序エバリュエーターを作成します。ホスト言語の実装効果 (評価戦略、スタックモデルなど) から解放されたプログラムを作成する方法を示します。ここでは Church-encoding を使用していますが、ここではとを使用していますcallがrecur、手法は同じです。

数年前、私は上記のテクニックを使ってスタックセーフなバリエーションを書きました。それを復活させ、後でこの回答で利用できるようにすることができるかどうかを確認します。今のところ、loop評価者は読者の演習として残しておきます。

PART 2 追加: ループ評価器

代替ソリューション

この関連する Q&Aでは、スタックセーフな継続モナドを構築します。

javascript - トランポリンを継続パススタイルに適応させるには?

3 に答える 3

Related

Reference