Support for compiling non-tail recursive functions
Motivation and Context
Right now recursive functions are compiled into iterative loops. This is good, but currently we only support tail-recursive functions.
Michelson now supports a new instruction LAMBDA_REC
that allows to encode recursive functions directly.
Description
This MR implements LAMBDA_REC
generation for those recursive functions that are not tail-recursive.
Types of changes
-
Bug fix (non-breaking change which fixes an issue) -
New feature (non-breaking change which adds functionality) -
Breaking change (fix or feature that would cause existing functionality to not work as expected) -
Performance improvement (non-breaking change that improves performance) -
None (change with no changelog)
Changelog
Now non-tail-recursive functions can be compiled. E.g.
$ cat lambdarec.mligo
let rec fib (n : int) : int =
if n <= 1 then
1
else
fib (n - 1) + fib (n - 2)
let rec cat (type a) (xs : a list) (ys : a list) : a list =
match xs with
| [] -> ys
| (x :: xs) -> x :: (cat xs ys)
$ ligo compile expression cameligo "cat [fib 1; fib 2; fib 3] [fib 4; fib 5; fib 6; fib 7]" --init-file lambdarec.mligo
{ 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 }
Checklist:
-
Changes follow the existing coding style (use dune @fmt
to check). -
Tests for the changes have been added (for bug fixes / feature). -
Documentation has been updated. -
Changelog description has been added (if appropriate). -
Start titles under ## Changelog
section with #### (if appropriate). -
There is no image or uploaded file in changelog -
Examples in changed behaviour have been added to the changelog (for breaking change / feature).
Edited by E. Rivas