recursion - 文本 WebAssembly 中的递归斐波那契数列

Question

我一直在玩弄文本 WebAssembly，并想编写一个递归斐波那契数计算器。

我有一个可用的版本，但它使用单个分支 if 语句来检查基本情况:

(module
 (export "fib" (func $fib))
  (func $fib (param $0 i32) (result i32)
  (if
   (i32.lt_s
    (get_local $0)
    (i32.const 2)
   )
   (return
    (i32.const 1)
   )
  )
  (return
   (i32.add
    (call $fib
    (i32.sub
      (get_local $0)
      (i32.const 2)
    )
   )
    (call $fib
      (i32.sub
       (get_local $0)
       (i32.const 1)
     )
    )
   )
  )
 )
) 

我在这里用 wabt 测试了这个:https://webassembly.github.io/wabt/demo/wat2wasm/

我尝试使用 select conditional 重写它:

(module
       (export "fib" (func $fib))
     (func $fib (param $0 i32) (result i32)
            (select
                   (return
                    (i32.const 1)
                    )
                  (return
                   (i32.add
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 2)
                           )
                          )
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 1)
                           )
                          )
                    )
                   )
                (i32.lt_s
                 (get_local $0)
                 (i32.const 2))))
     )

这编译为 .wasm，但它没有按预期运行，只是返回基本情况。我用 if-then-else 尝试了类似的版本，但无济于事。为什么单分支的结果与双分支条件有任何不同？

Answer 1

你给了我一个学习 wasm 的理由。我还不能回答你关于单分支 if 的问题，但我可以向你展示一个有效的 fib 函数。

(module
  (func $fib2 (param $n i32) (param $a i32) (param $b i32) (result i32)
    (if (result i32)
        (i32.eqz (get_local $n))
        (then (get_local $a))
        (else (call $fib2 (i32.sub (get_local $n)
                                   (i32.const 1))
                          (get_local $b)
                          (i32.add (get_local $a)
                                   (get_local $b))))))

  (func $fib (param i32) (result i32)
    (call $fib2 (get_local 0)
                (i32.const 0)   ;; seed value $a
                (i32.const 1))) ;; seed value $b

  (export "fib" (func $fib)))

复制/粘贴以进行演示 here

const wasmInstance =
  new WebAssembly.Instance (wasmModule, {})

const { fib } =
  wasmInstance.exports

for (let x = 0; x < 10; x = x + 1)
  console.log (fib (x))

输出

0
1
1
2
3
5
8
13
21
34

就其值(value)而言，此处的实现与您的完全不同。您的程序需要指数级的计算时间和空间，而上述程序的要求是线性的。

通过检查您对 (call $fib ...) 的使用，这一点很明显。在您的程序中，对 $fib 的一次调用有可能产生 两次 对 $fib 的额外调用，每个调用都有可能产生两次 对 $fib 的调用，等等。 $fib2 最多只能一次调用自己。

---

虽然性能稍逊一筹，但当然可能实现指数过程

(module
  (func $fib (param $n i32) (result i32)
    (if (result i32)
        (i32.lt_s (get_local $n)
                  (i32.const 2))
        (then (get_local $n))
        ;; recursive branch spawns _two_ calls to $fib; not ideal
        (else (i32.add (call $fib (i32.sub (get_local $n)
                                           (i32.const 1)))
                       (call $fib (i32.sub (get_local $n)
                                           (i32.const 2)))))))

  (export "fib" (func $fib)))