Shadowing and Nested function

Question

I want to understand how the mechanism of Shadowing and Nested function work. For example:

let func y =
    let dup y = y + y
    let z = dup y
    let dup y =
        let dup z =
            let y = y * z
            y
        let z = y
        y
    dup z + z;;

val func : int -> int

> func 3;;
val it : int = 12

Can someone explain what happen here?

Answer 1

Your code is equivalent to the following, where I've simply numbered instances of your names to help you visualize how shadowing is occurring.

let func y0 = 
  let dup0 y1 = y1 + y1
  let z0 = dup0 y0
  let dup1 y2 = 
    let dup2 z1 = 
      let y3 = y2 * z1 
      y3
    let z2 = y2 
    y2 
  dup1 z0 + z0

This can be further simplified, of course. Since dup2 and z2 are never used, dup1 is equivalent to let dup1 y2 = y2, and the whole function is equivalent to

let func y0 =
  let dup0 y1 = y1 + y1
  let z0 = dup0 y0
  dup1 z0 + z0

Which is equivalent to

let func y0 =
  let z0 = y0 + y0
  z0 + z0

by substitution. This is the same as

let func y0 = 4 * y0

Does this help?

Answer 2

I think @kvb gives a very good explanation showing how the code evaluates. The code combines nested functions and shadowing in a pretty confusing way :-). I think it is useful to look at the two concepts separately.

Shadowing allows you to hide a value by a new value in the let declaration or a value binding in the match construct. It means that you'll no longer be able to access the original value. Here is a simpler example:

let foo num =
  let num = num + 20 // Line 2
  let num = num * 2  // Line 3
  num

Here, we declare a function that takes an argument named num. Let's say we call the function with 1 as the argument. On the second line, we declare a new value with the same name - initialized to 1 + 20 which is 21. The third line again declares a new value and initializes it to 21 * 2 (because it sees the last declared num symbol, which has value 21). On the line 4, we again access the last declared num symbol and we return 42.

This is useful mainly whan you have some calculation that calculates some new value that should be use by all subsequent calculations. Shadowing allows you to hide the previous value, so there is no danger you will accidentaly use the original one.

Nested functions are quite useful when you need to do some local utility calculation that uses parameters of the outer function. For example:

let times x nums = 
  let timesUtil y = y * x
  for n in nums do
    printfn "%d" (timesUtil n)

Here we declare a utility nested function timesUtil that multiplies any number by the value x (which is the argument of the times function). Then we can use it later (on the last line) to do the operation without having to pass the x value as an argument again. So, the main interesting thing about nested functions is that they can access values declared by the outer function.