OCaml functions passing in one less argument

Question

I'm looking at solutions for a homework and the code implements an OCaml function that takes in two arguments but when its called, it's only passed one argument.

let rec func2 r x = match r with
  | [] -> []
  | (nt,rhs)::t -> if nt = x then rhs::(func2 t x) else func2 t x;;

let func1 r = fun x -> func2 r x;;

I would be calling func1 on a grammar rule like below by calling ( func1 awksub_rules )

let awksub_rules = [
  Expr, [T"("; N Expr; T")"];
  Expr, [N Num];
  Num, [T"0"];
  Num, [T"1"]
]

Expr and Num are just nonterminal types already defined and the T symbol means a terminal type.

I'm confused because func1 only takes in awksub_rules as an argument but the function declaration has two functions.

The intended output would be

function 
  | Expr -> [[T"("; N Expr; T")"]; [N Num]]
  | Num -> [[T"0"]; [T"1"]]

I can see that func1 correctly returns a function and that func2 handles checking whether the left hand side (Expr or Num) is the same so it can concatenate to the list. But I have no idea what is passed into x.

Answer 1

When func1 is called with one argument, it returns another function, let's call it func3:

let func3 = func1 awksub_rules

At this point, there is no argument x yet. This new function still expects this argument to be passed in.

When you call this new function, you will pass in the value of x, and the computation will commence:

let result = func3 Num

I also would like to point out that func1 and func2 are logically equivalent because of the mechanism in ML called "partial application". That is, you can use func2 everywhere you use func1, and with same effect:

let func3 = func2 awksub_rules
let result = func3 Num

Answer 2

Fyodor Soikin's answer explains why func1 and func2 are logically the same. However, I don't want you to come away from this thinking that there is some magical language feature called "partial application". To stretch your mind, you need to understand how this arises from how functions work in OCaml.

In the ML languages, there is no such thing as a "function that takes in two arguments". Every function in ML takes exactly one argument (not zero, not two, not three; always one). The OCaml syntax

let rec func2 r x = ...

is syntactic sugar for

let rec func2 = function r -> function x -> ...

i.e. it is simply a definition of a function that returns another function. That's why the type of the function will be something like a -> b -> c (-> is right-associative, so that is the same as a -> (b -> c)) -- it says that it's a function that takes an a, and returns a function of type b -> c.

When you go to apply this function, what you think of as passing in two arguments, like func2 foo bar, is actually (because function application is left-associative) (func2 foo) bar, i.e. it is first applying func2 to the expression foo, and the result of that, a function, will then be applied to the expression bar.

The practice of taking in "multiple arguments" by taking in one argument and returning a function that takes another argument, etc. is called "currying". OCaml and other ML languages provide convenient syntax for defining curried functions (as you can see above, the common syntax let in OCaml allows you to define curried functions simply as listing the parameters next to each other), whereas in other languages, writing curried functions would require more verbose syntax. It's so convenient that, most of the time, we forget about it and think of it as multiple arguments. But it's always important to remember what it really means.

(Note that the OCaml compiler may or may not optimize curried functions into machine code functions that take multiple arguments, but that's an implementation detail that you shouldn't care about at the language level.)