Как рекурсия должна быть закодирована в WebAssembly?
Я компилирую язык чистых тотальных функций в WebAssembly. Самая сложная из доступных конструкций — это примитивная рекурсия. Я немного поэкспериментировал, и кажется, что единственный жизнеспособный подход — это построить прыгающую абстрактную машину, которая марширует по какому-то байт-коду, превращая рекурсию в итерацию. Есть ли лучшая стратегия?
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
Ну можно конечно просто использовать рекурсию в Wasm, но хвост-рекурсивной она не будет. Из вашего вопроса не совсем ясно, является ли это требованием.
Расширение с явными хвостовыми вызовами было предложено для Wasm. Это предложение в настоящее время находится на «фазе 3» процесса предложения Wasm и было реализовано в V8 и (в настоящее время) Safari, что означает, что мы надеемся, что оно будет стандартизировано очень скоро.
До тех пор, да, вам придется использовать какой-то батут, если вы зависите от семантики хвостового вызова.
Я ценю этот ответ. Действительно, есть несколько предложенных улучшений, которые могли бы помочь: блоки с несколькими аргументами, базовые блоки, GC и хвостовые вызовы. Я не завишу от хвостовых вызовов, но моя рекурсия приведет к переполнению стека, если будет реализована наивно.
Ну, разве это не означает, что вы зависите от него? FWIW, блоки с несколькими аргументами уже являются стандартными. Однако я не уверен, какое предложение вы имеете в виду под базовыми блоками.
Моя семантика довольно абстрактна; Меня не интересуют стеки вызовов, потому что у категорий нет стеков вызовов. Именно WASM, а не я, заставляет меня избегать вызовов, чтобы избежать переполнения стека. Если бы в WASM были базовые блоки или несокращаемый поток управления, то я мог бы просто сделать суп из блоков, которые кодируют какую-то абстрактную машину, что было бы более эффективно, чем интерпретация байт-кода или сокращение графа.
Думаю, я бы принял ответ, в котором говорится «реализовать алгоритм Relooper»!
Я слышал, что в предстоящем выпуске GHC будет реализована поддержка серверной части WebAssembly. Думаю, я бы принял ответ, в котором говорится «скомпилировать в Haskell».