# let rec weng = ~wengcvmisccontactblog博客

## Where recursion hides

2022-09-02 # λ. Disclaim:

• This blog is a working draft.
• Not going to cover the duality of recursion and corecursion this time.
• Not going to cover functional graphs this time.
• Not going to discuss recursive types, though I think comparing between recursive types, recursive functions, and recursive expressions is interesting.

# λ. 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