0

[mutually recursive functions] With the addition of LAMBDA_REC does anyone know a better way of compiling mutually recursive functions than the following (example w/ is_odd and is_even):

let rec fix f x = f (fix f) x

type env = 
  { is_even : int -> bool
  ; is_odd : int -> bool 
  }

type open_env = 
  { is_even : env -> int -> bool
  ; is_odd : env -> int -> bool
  }

let fix_env = fix (fun self env : env -> 
  { is_even = (fun x -> env.is_even (self env) x)
  ; is_odd = (fun x -> env.is_odd (self env) x)
  })

let open_env = 
  { is_even = (fun env n -> if n = 0 then true else not (env.is_odd (n - 1)))
  ; is_odd = (fun env n -> if n = 0 then false else not (env.is_even (n - 1)))
  }

let env = fix_env open_env

Question from Slack

1 Answer 1

0

in this example, with LIGO, something like this seems significantly better, but not sure if (or how well) it works generally:

type is_even_odd_arg =
  | Is_even of int
  | Is_odd of int

type is_even_odd_ret =
  | Is_even of bool
  | Is_odd of bool

[@inline] let get_is_even_exn (x : is_even_odd_ret) : bool =
  match x with
  | Is_even b -> b
  | _ -> failwith ()

[@inline] let get_is_odd_exn (x : is_even_odd_ret) : bool =
  match x with
  | Is_odd b -> b
  | _ -> failwith ()

let rec is_even_odd (x : is_even_odd_arg) : is_even_odd_ret =
  match x with
  | Is_even n ->
    if n = 0
    then Is_even true
    else Is_even (not (get_is_odd_exn (is_even_odd (Is_odd (n - 1)))))
  | Is_odd n ->
    if n = 0
    then Is_odd false
    else Is_even (not (get_is_even_exn (is_even_odd (Is_even (n - 1)))))

let is_even (n : int) : bool =
  get_is_even_exn (is_even_odd (Is_even n))

let is_odd (n : int) : bool =
  get_is_odd_exn (is_even_odd (Is_odd n))


(* to measure code size: *)

type env = 
  { is_even : int -> bool
  ; is_odd : int -> bool 
  }

let main (_ : unit * env) : operation list * env =
  ([], {is_even = is_even; is_odd = is_odd})

Here is a version of your attempt that compiles in LIGO btw:

let rec fix (type a b) (f : (a -> b) -> (a -> b)) (x : a) : b = f (fix f) x

type env = 
  { is_even : int -> bool
  ; is_odd : int -> bool 
  }

type open_env = 
  { is_even : env -> int -> bool
  ; is_odd : env -> int -> bool
  }

let fix_env = fix (fun (self : open_env -> env) (env : open_env) : env -> 
  { is_even = (fun x -> env.is_even (self env) x)
  ; is_odd = (fun x -> env.is_odd (self env) x)
  })

let open_env = 
  { is_even = (fun (env : env) n -> if n = 0 then true else not (env.is_odd (n - 1)))
  ; is_odd = (fun (env : env) n -> if n = 0 then false else not (env.is_even (n - 1)))
  }

let env = fix_env open_env

(* to measure code size: *)

let main (_ : unit * env) : operation list * env =
  ([], env)

this is 1939 bytes vs 450 bytes for mine Answer from Tom Jack in Slack.

Followup Q:

How does this scale with an increase in the number of functions?

I would expect that match becomes nasty with lots of functions?

Answer:

or is bad but I'd be a little surprised if it's worse than yours

mut1.tz:

{ parameter unit ;

  storage (pair (lambda %is_even int bool) (lambda %is_odd int bool)) ;

  code { DROP ;

         LAMBDA

           (lambda

              (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                    (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

              (pair (lambda int bool) (lambda int bool)))

           (lambda

              (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                    (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

              (pair (lambda int bool) (lambda int bool)))

           { LAMBDA

               (pair (lambda

                        (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                              (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                        (pair (lambda int bool) (lambda int bool)))

                     (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                           (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))))

               (pair (lambda int bool) (lambda int bool))

               { UNPAIR ;

                 SWAP ;

                 LAMBDA

                   (pair (pair (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                     (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                               (lambda

                                  (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                        (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                  (pair (lambda int bool) (lambda int bool))))

                         int)

                   bool

                   { UNPAIR ;

                     UNPAIR ;

                     DIG 2 ;

                     DUP 2 ;

                     DIG 3 ;

                     SWAP ;

                     EXEC ;

                     DIG 2 ;

                     CDR ;

                     SWAP ;

                     EXEC ;

                     SWAP ;

                     EXEC } ;

                 DUP 3 ;

                 DUP 3 ;

                 PAIR ;

                 APPLY ;

                 LAMBDA

                   (pair (pair (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                     (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                               (lambda

                                  (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                        (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                  (pair (lambda int bool) (lambda int bool))))

                         int)

                   bool

                   { UNPAIR ;

                     UNPAIR ;

                     DIG 2 ;

                     DUP 2 ;

                     DIG 3 ;

                     SWAP ;

                     EXEC ;

                     DIG 2 ;

                     CAR ;

                     SWAP ;

                     EXEC ;

                     SWAP ;

                     EXEC } ;

                 DUP 4 ;

                 DUP 4 ;

                 PAIR ;

                 APPLY ;

                 DIG 2 ;

                 DIG 3 ;

                 DROP 2 ;

                 PAIR } ;

             DUP 2 ;

             APPLY ;

             SWAP ;

             DROP } ;

         LAMBDA_REC

           (lambda

              (lambda

                 (pair (lambda %is_even

                          (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                          (lambda int bool))

                       (lambda %is_odd

                          (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                          (lambda int bool)))

                 (pair (lambda %is_even int bool) (lambda %is_odd int bool)))

              (lambda

                 (pair (lambda %is_even

                          (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                          (lambda int bool))

                       (lambda %is_odd

                          (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                          (lambda int bool)))

                 (pair (lambda %is_even int bool) (lambda %is_odd int bool))))

           (lambda

              (pair (lambda %is_even

                       (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                       (lambda int bool))

                    (lambda %is_odd

                       (pair (lambda %is_even int bool) (lambda %is_odd int bool))

                       (lambda int bool)))

              (pair (lambda %is_even int bool) (lambda %is_odd int bool)))

           { LAMBDA

               (pair (pair (lambda

                              (lambda

                                 (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                       (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                 (pair (lambda int bool) (lambda int bool)))

                              (lambda

                                 (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                       (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                 (pair (lambda int bool) (lambda int bool))))

                           (lambda

                              (lambda

                                 (lambda

                                    (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                          (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                    (pair (lambda int bool) (lambda int bool)))

                                 (lambda

                                    (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                          (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                    (pair (lambda int bool) (lambda int bool))))

                              (lambda

                                 (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                                       (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool)))

                                 (pair (lambda int bool) (lambda int bool)))))

                     (pair (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))

                           (lambda (pair (lambda int bool) (lambda int bool)) (lambda int bool))))

               (pair (lambda int bool) (lambda int bool))

               { UNPAIR ;

                 UNPAIR ;

                 DIG 2 ;

                 DUP 2 ;

                 DIG 3 ;

                 SWAP ;

                 EXEC ;

                 DIG 2 ;

                 SWAP ;

                 EXEC ;

                 SWAP ;

                 EXEC } ;

             DUP 3 ;

             DUP 3 ;

             PAIR ;

             APPLY ;

             SWAP ;

             DIG 2 ;

             DROP 2 } ;

         SWAP ;

         EXEC ;

         LAMBDA

           (pair (lambda int bool) (lambda int bool))

           (lambda int bool)

           { LAMBDA

               (pair (pair (lambda int bool) (lambda int bool)) int)

               bool

               { UNPAIR ;

                 SWAP ;

                 PUSH int 0 ;

                 DUP 2 ;

                 COMPARE ;

                 EQ ;

                 IF { DROP 2 ; PUSH bool False }

                    { PUSH int 1 ; SWAP ; SUB ; SWAP ; CAR ; SWAP ; EXEC ; NOT } } ;

             DUP 2 ;

             APPLY ;

             SWAP ;

             DROP } ;

         LAMBDA

           (pair (lambda int bool) (lambda int bool))

           (lambda int bool)

           { LAMBDA

               (pair (pair (lambda int bool) (lambda int bool)) int)

               bool

               { UNPAIR ;

                 SWAP ;

                 PUSH int 0 ;

                 DUP 2 ;

                 COMPARE ;

                 EQ ;

                 IF { DROP 2 ; PUSH bool True }

                    { PUSH int 1 ; SWAP ; SUB ; SWAP ; CDR ; SWAP ; EXEC ; NOT } } ;

             DUP 2 ;

             APPLY ;

             SWAP ;

             DROP } ;

         PAIR ;

         EXEC ;

         NIL operation ;

         PAIR } }

vs

mut2.tz

{ parameter unit ;

  storage (pair (lambda %is_even int bool) (lambda %is_odd int bool)) ;

  code { DROP ;

         LAMBDA_REC

           (or (int %is_even) (int %is_odd))

           (or (bool %is_even) (bool %is_odd))

           { IF_LEFT

               { PUSH int 0 ;

                 DUP 2 ;

                 COMPARE ;

                 EQ ;

                 IF { DROP 2 ; PUSH bool True }

                    { PUSH int 1 ;

                      SWAP ;

                      SUB ;

                      RIGHT int ;

                      EXEC ;

                      IF_LEFT { DROP ; UNIT ; FAILWITH } {} ;

                      NOT } ;

                 LEFT bool }

               { PUSH int 0 ;

                 DUP 2 ;

                 COMPARE ;

                 EQ ;

                 IF { DROP 2 ; PUSH bool False ; RIGHT bool }

                    { PUSH int 1 ;

                      SWAP ;

                      SUB ;

                      LEFT int ;

                      EXEC ;

                      IF_LEFT {} { DROP ; UNIT ; FAILWITH } ;

                      NOT ;

                      LEFT bool } } } ;

         LAMBDA

           (pair (lambda (or int int) (or bool bool)) int)

           bool

           { UNPAIR ;

             SWAP ;

             RIGHT int ;

             EXEC ;

             IF_LEFT { DROP ; UNIT ; FAILWITH } {} } ;

         DUP 2 ;

         APPLY ;

         LAMBDA

           (pair (lambda (or int int) (or bool bool)) int)

           bool

           { UNPAIR ;

             SWAP ;

             LEFT int ;

             EXEC ;

             IF_LEFT {} { DROP ; UNIT ; FAILWITH } } ;

         DUP 3 ;

         APPLY ;

         DIG 2 ;

         DROP ;

         PAIR ;

         NIL operation ;

         PAIR } }

or-combs don't solve the big problem with or (to me) -- which is that to construct a value you have to mention the entire tree of types other than the one you want.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.