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

Question

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

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

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

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

我尝试使用 select 条件重写：

(module
       (export "fib" (func $fib))
     (func $fib (param [=11=] i32) (result i32)
            (select
                   (return
                    (i32.const 1)
                    )
                  (return
                   (i32.add
                    (call $fib
                          (i32.sub
                           (get_local [=11=])
                           (i32.const 2)
                           )
                          )
                    (call $fib
                          (i32.sub
                           (get_local [=11=])
                           (i32.const 1)
                           )
                          )
                    )
                   )
                (i32.lt_s
                 (get_local [=11=])
                 (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)))

Copy/paste 进行演示 here

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

const { fib } =
  wasmInstance.exports

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

输出

尽管如此，这里的实现与您的完全不同。您的程序需要指数计算时间和 space 而上述程序的要求是线性的。

通过检查您对 (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)))

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

Recursive Fibonacci in text WebAssembly

recursion

webassembly