CODEWITHSUNDEEP
ocaml
user10661584
user10661584

Reputation:

What is "let rec (-) x y = y - x in 1 - 2 - 3" doing?

I saw let (-) x y = y - x in 1 - 2 - 3 and let rec (-) x y = y - x in 1 - 2 - 3 these two examples in a book about ocaml. When I saw the former one, I thought I understood the trick behind until I saw the latter function. It seems that the latter function is having some stack overflow problem, but why is it the case? How does ocaml evaluate these two expressions separately?

Upvotes: 0

Views: 167

Answers (2)

ivg
ivg

Reputation: 35260

The let expression has syntax is let <name> = <expr1> in <expr2> and it defines <name> to be bound to <expr1> in <expr2>. The <name> itself is not visible in the scope of <expr1>, in other words it is not recursive by default. And that feature could be (and often used) to give the same names the new meaning, e.g., this is the canonical OCaml code,

let example () = 
  let name = "Alice" in
  let name = "Professor " ^ name in
  print_endline name

The same technique approach is used in the let (-) x y = y - x in 1 - 2 - 3, where we redefine the (-) in terms of the original (-) operator which is still seen untouched in the scope of the y - x expression.

However, when we add the rec keyword to the let definition then the name is immediately visible in the scope of the currently defined expression, e.g., 

let rec (-) x y = y - x
(*       ^          | *) 
(*       |          | *)
(*       +----------+ *)

here - in x - y refers to the currently defined function, so we have a recursive definition that says that x minus y is y minus x - a bogus definition.

Upvotes: 0

Aadit M Shah
Aadit M Shah

Reputation: 74234

It might be helpful to rename the let bound functions.

let (-) x y = y - x
in 1 - 2 - 3

(* The above expression is equivalent to the following. *)

let f x y = y - x
in f (f 1 2) 3

(* Which reduces to the following. *)

let f x y = y - x
in 3 - (2 - 1)

Note that the function we defined, let (-) x y, is different from the function which we use in the definition, y - x. This is because let without rec doesn't bind the function name within the definition. Hence, the (-) operator in the definition is the native minus operator. Therefore, the result is 2.

Now, consider the second example.

let rec (-) x y = y - x
in 1 - 2 - 3

(* The above expression is equivalent to the following. *)

let rec f x y = f y x
in f (f 1 2) 3

Now, what does f 1 2 reduce to? It reduces to f 2 1, which reduces to f 1 2, which reduces to f 2 1, and so on ad infinitum. Now, in a language without tail call optimization this would result in a stack overflow error. However, in OCaml it should just run forever without returning.

Upvotes: 1

Related Questions