several questions about this sml recursion function

Question

1. When f(x-1) is called, is it calling f(x) = x+10 or f(x) = if ...
2. Is this a tail recursion?

3. How should I rewrite it using static / dynamic allocation?

   let fun f(x) = x + 10
   in
       let fun f(x) = if x < 1 then 0 else f(x-1)
       in f(3)
       end
   end
   

Answer 1

Before addressing your questions, here are some observations about your code:

• There are two functions f, one inside the other. They're different from one another.

• To lessen this confusion you can rename the inner function to g:

  let fun f(x) = x + 10
  in
      let fun g(x) = if x < 1 then 0 else g(x-1)
      in g(3)
      end
  end
  

• This clears up which function calls which by the following rules: The outer f is defined inside the outer in-end, but is immediately shadowed by the inner f. So any reference to f on the right-hand side of the inner fun f(x) = if ... is shadowed because fun enables self-recursion. And any reference to f within the inner in-end is shadowed

---

• In the following tangential example the right-hand side of an inner declaration f does not shadow the outer f if we were using val rather than fun:

  let fun f(x) = if (x mod 2 = 0) then x - 10 else x + 10
  in
      let val f = fn x => f(x + 2) * 2
      in f(3)
      end
  end
  

  If the inner f is renamed to g in this second piece of code, it'd look like:

  let fun f(x) = if (x mod 2 = 0) then x - 10 else x + 10
  in
      let val g = fn x => f(x + 2) * 2
      in g(3)
      end
  end
  

  The important bit is that the f(x + 2) part was not rewritten into g(x + 2) because val means that references to f are outer fs, not the f being defined, because a val is not a self-recursive definition. So any reference to an f within that definition would have to depend on it being available in the outer scope.

  But the g(3) bit is rewritten because between in-end, the inner f (now g) is shadowing. So whether it's a fun or a val does not matter with respect to the shadowing of let-in-end.

• (There are some more details wrt. val rec and the exact scope of a let val f = ... that I haven't elaborated on.)

---

As for your questions,

1. You should be able to answer this now. A nice way to provide the answer is 1) rename the inner function for clarity, 2) evaluate the code by hand using substitution (one rewrite per line, ~> denoting a rewrite, so I don't mean an SML operator here).

   Here's an example of how it'd look with my second example (not your code):

      g(3)
   ~> (fn x => f(x + 2) * 2)(3)
   ~> f(3 + 2) * 2
   ~> f(5) * 2
   ~> (if (5 mod 2 = 0) then 5 - 10 else 5 + 10) * 2
   ~> (if (1 = 0) then 5 - 10 else 5 + 10) * 2
   ~> (5 + 10) * 2
   ~> 15 * 2
   ~> 30
   

   Your evaluation by hand would look different and possibly conclude differently.

2. What is tail recursion? Provide a definition and ask if your code satisfies that definition.

3. I'm not sure what you mean by rewriting it using static / dynamic allocation. You'll have to elaborate.