Remove `fun`, and use `let` to declare functions

[julianhyde]

Remove fun, and use val to declare functions (even functions that are recursive and/or have multiple arms). Introduce new nonrec keyword to explicitly specify that a value declaration or function declaration is non-recursive. After this change, rec is implicit if there is one or more argument, nonrec is implicit if there are no arguments.

For example,

fun factorial 1 = 1
   | factorial n = n * (factorial (n - 1))

becomes

val factorial 1 = 1
  | factorial n = n * (factorial (n - 1))

Currently, recursion works because fun desugars to let rec. After this change, rec would be implicit if there is one or more argument; nonrec would be implicit if there are no arguments.

The following is valid Standard ML and will remain valid Morel.

val x = "abc";
> val x = "abc" : string
val x = size x;
> val x = 3 : int

If we implement #307, val will become let, and the let ... end block will become { ... }.

[julianhyde]

and, to define multiple mutually recursive functions, will remain valid. Claude wrote the following about and in Standard ML and OCaml; our proposal would do the same, but not require rec.

me: Does does OCaml allow simultaneous definition of functions?

Claude: Yes, OCaml allows simultaneous (mutually recursive) definition of functions using the and keyword.

Syntax:

let rec function1 pattern = ...
    and function2 pattern = ...
    and function3 pattern = ...

Examples:

Example 1: Mutually recursive functions

let rec is_even n =
  if n = 0 then true
  else is_odd (n - 1)

and is_odd n =
  if n = 0 then false
  else is_even (n - 1)

Example 2: Mutually recursive types and functions

type expr =
  | Const of int
  | Add of expr * expr
  | Mul of expr * expr

let rec eval = function
  | Const n -> n
  | Add (e1, e2) -> eval e1 + eval e2
  | Mul (e1, e2) -> eval e1 * eval e2

and simplify = function
  | Add (Const 0, e) -> simplify e
  | Add (e, Const 0) -> simplify e
  | Mul (Const 1, e) -> simplify e
  | Mul (e, Const 1) -> simplify e
  | Add (e1, e2) -> Add (simplify e1, simplify e2)
  | Mul (e1, e2) -> Mul (simplify e1, simplify e2)
  | e -> e

Example 3: Multiple functions in a module

let rec parse_expr tokens =
  match tokens with
  | [] -> failwith "unexpected end"
  | _ -> parse_term tokens

and parse_term tokens =
  match tokens with
  | [] -> failwith "unexpected end"
  | _ -> parse_factor tokens

and parse_factor tokens =
  match tokens with
  | Num n :: rest -> (Const n, rest)
  | _ -> failwith "expected number"

Key points:

1. All functions must use rec - The first function uses let rec, not just let

2. Use and to connect definitions - Not semicolons or commas

3. All functions are in scope for each other - Each function can call any other in the group

4. Works with pattern matching too:

let rec f 0 = 1
      | f n = n * g (n - 1)

and g 0 = 0
    | g n = n + f (n - 1)

Standard ML comparison:

Standard ML also supports this with and:

fun is_even 0 = true
  | is_even n = is_odd (n - 1)

and is_odd 0 = false
  | is_odd n = is_even (n - 1);

Non-recursive simultaneous bindings:

You can also use and for non-recursive simultaneous bindings:

let x = 1
and y = 2
and z = 3

But in this case, none of the definitions can reference each other (they're all defined in terms of the previous scope):

let x = 10 in
let y = x          (* refers to outer x *)
and z = x + 1      (* also refers to outer x, not the y we just defined! *)
in y + z           (* result: 10 + 11 = 21 *)

This is different from sequential let:

let x = 10 in
let y = x in       (* refers to outer x *)
let z = y + 1 in   (* refers to the y we just defined *)
y + z              (* result: 10 + 11 = 21 *)

Summary:

• let rec ... and ... - mutually recursive functions (can call each other)
• let ... and ... - simultaneous non-recursive bindings (cannot reference each other)

The and keyword is essential for defining mutually recursive functions in OCaml.