 # Beginner question on code style in Base

I am reading the code in Base. https://github.com/janestreet/base/blob/master/src/array.ml has

``````  module Insertion_sort : Sort = struct
let sort arr ~compare ~left ~right =
(* loop invariant:
[arr] is sorted from [left] to [pos - 1], inclusive *)
for pos = left + 1 to right do
(* loop invariants:
1.  the subarray arr[left .. i-1] is sorted
2.  the subarray arr[i+1 .. pos] is sorted and contains only elements > v
3.  arr[i] may be thought of as containing v

Note that this does not allocate a closure, but is left in the for
loop for the readability of the documentation. *)
let rec loop arr ~left ~compare i v =
let i_next = i - 1 in
if i_next >= left && compare (get arr i_next) v > 0
then (
set arr i (get arr i_next);
loop arr ~left ~compare i_next v)
else i
in
let v = get arr pos in
let final_pos = loop arr ~left ~compare pos v in
set arr final_pos v
done
;;
end
``````

Questions:

1. What does the comment “is left in the loop” refer to?
2. What is the advantage to having `let rec loop arr ~left ~compare i v` when `arr`, `left`, `compare`, and `v` are constant? That is, why is the loop not simply `let rec loop i`?

I would guess it refers to the fact that `loop` is defined inside the `for` loop, rather than outside, even though in principle it could have been.

It’s for performance, I think. Writing it the second way would mean allocating a closure for the values of the variables that aren’t passed as arguments. Besides the direct cost of allocating, allocation gives the garbage collector a chance to run.

That’s exactly the idea. We are generally very careful about performances for such core functions.

That’s also why we are pushing for flambda at Jane Street: so that we can write nice simple code and let the compiler do all these optimisations for us 