let rec weng = ~weng cv misc contact blog 博客

Where recursion hides

2022-09-02

Ouroboros

λ. Disclaim:

λ. Material: Sum on the ground 

# let rec sum n = if n = 0 then 0 else n + sum (n-1);;
val sum : int -> int = <fun>
# sum 3;;
- : int = 6

def sum(n):
  return (0 if n == 0 else n + (sum (n-1)))

sum(3)

It’s common to define a recursive function: in the function body, we can use the function name to refer to itself.

λ. Observation 1: Anonymous recursive function

What if the supposed recursive function had no name?

After defining such a function, we can give it the name sum and use it.

let sum =
  fun n -> if n = 0 then 0 else n + <THIS_FUNCTION> (n-1)
  in
sum 3

I am not going to say the details in this post. The key is to use a fixed-point combinator e.g. Y. See rosettacode/Y_combinator#OCaml.

The answer is like this:

let sum' =
  y_comb (fun sum -> fun n -> if n = 0 then 0 else n + sum (n-1))
  in
sum' 3

(* the language doesn't really need `let`, we can have *)
(y_comb (fun sum -> fun n -> if n = 0 then 0 else n + sum (n-1))) 3

Observation 1: There are recursions with only functions.

λ. Observation 2 : Recursive name

Recursive acronym is common in computer land e.g. GNU = GNU's Not Unix. Real people don’t get stuck in reading this. They won’t really expand GNU in the previous expanded result forever.

Can we represent this in programs?

# let rec gnu () : string = gnu () ^ "'s Not Unix";;
val gnu : unit -> string = <fun>

# let rec gnu : string = gnu ^ "'s Not Unix";;
Line 1, characters 24-43:
Error: This kind of expression is not allowed as right-hand side of `let rec'

# type rec_name = {part1 : rec_name; part2 : string};;
type rec_name = { part1 : rec_name; part2 : string; }

# let rec gnu : rec_name = {part1 = gnu; part2 = "'s Not Unix"};;
val gnu : rec_name = {part1 = <cycle>; part2 = "'s Not Unix"}

# let rec circle_xs = 1 :: 2 :: circle_xs;;
val circle_xs : int list = [1; 2; <cycle>]

# List.(hd (tl (tl (tl circle_xs))));;
- : int = 2

In OCaml, if we treat it as a function, then we can define gnu : unit -> string. Application of this function diverges (runs into an infinite loop, or triggers a stack-overflow).

We cannot define a recursive string. However, we can define a recursive record or list. Recursive value is the first language extension of OCaml, stated here.

In Haskell, we are freer to define things recursively.

> gnu = gnu ++ "'s Not Unix"

# diverge
> take 3 gnu

> ung = "Xinu Ton \'s" ++ ung
> take 3 ung
"Xin"

> take 15 ung
"Xinu Ton 'sXinu"

Observation 2: There are recursions without functions.

λ. Observation 3: Mutation 

# let sum_cell = ref (fun _ -> 0);;
val sum_cell : ('_weak1 -> int) ref = {contents = <fun>}

# sum_cell := (fun n -> if n = 0 then 0 else n + !sum_cell (n-1));;
- : unit = ()

# let sum = !sum_cell;;
val sum : int -> int = <fun>

# sum 3;;
- : int = 6

Using mutation, the definition of a recursive function can be split into multiple steps. Think about the problem on THIS_FUNCTION in Observation 1. Now the function doesn’t need to know itself’s name THIS_FUNCTION immediately. By dereferencing that cell, the function can get itself.

Observation 3: There are recursions with mutations.

λ. Observation 4: Self-reference.

Any recursion has some sort of self-reference. In recursive functions and recursive names, the self-reference is direct in the syntax (a.k.a function body itself). In anonymous function and mutation-based recursion, the self-reference is not direct in the syntax.

λ. Observation 5: Somewhat lazy.

Expanding a recursive name lasts for-ever. Whether evaluating around a recursive expression terminates or not is case-by-case.

Haskell is famous for its call-by-need lazy evaluation. OCaml is an eager language. However, though not specified, evaluating recursive expression must involve some sort of laziness conceptually. OCaml also provides Lazy.t. With the Lazy.t, we can define more lazy things in OCaml.

# let rec gnu : string = gnu ^ "'s Not Unix";;
Line 1, characters 24-43:
Error: This kind of expression is not allowed as right-hand side of `let rec'

# let rec gnu : string Lazy.t = lazy ((Lazy.force gnu) ^ "'s Not Unix");;
val gnu : string lazy_t = <lazy>

# Lazy.force gnu;;
Exception: CamlinternalLazy.Undefined.

# type 'a stream = 'a streamcell Lazy.t and 'a streamcell = { head: 'a; tail: 'a stream };;
type 'a stream = 'a streamcell lazy_t
and 'a streamcell = { head : 'a; tail : 'a stream; }

# let rec ints n = lazy { head = n; tail = ints (n + 1) };;
val ints : int -> int stream = <fun>

OCaml’s lazy is weaker than Haskell’s native laziness. We cannot define direct a recursive string and lazy recursive string.

I started to think about these topics in mid-August. Last week, a thread [Caml-list] coinductive data types on OCaml mail-list asked about similar question. The stream example is from Xavier Leroy’s reply.

(t.b.c)

more: https://en.wikipedia.org/wiki/Let_expression https://www.cs.cornell.edu/Projects/CoCaml/

Where recursion hides