Skip to content

Support for compiling non-tail recursive functions

E. Rivas requested to merge er433/michelson/lambdarec into dev

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

Merge request reports

Loading