SML: "Behind the scenes" of immutable variables?

Question

I have a question about Standard ML (SML). I've read that SML has variables that do not vary. When a value is bound to a variable, it is set for life and cannot be changed.

My question: how does it work "behind the scenes"; i.e. in memory. For example, if ran the following program:

val a = 5;
val a = a + 1;

Will the interpreter allocate a new place in memory for the 'new' a?

What are the benefits of this idea? It feels like it is less efficient than a programming language such as C.

Answer 1

val a = 5
val a = a + 1

Will the interpreter allocate a new place in the memory for the 'new' a?

Yes, exactly.

SML has two things, value bindings, and mutable references (as variables are in e.g. C).

What you describe are value bindings, and their value cannot vary in the same scope.

Here the value of a does not vary, it is shadowed by another a, creating a new scope with the old a hidden. So if you use the old a and shadow a, the usage of the old a does not change. A more illustrative example:

val a = 5
fun f x = x + a
val a = 10
val b = f 1  (* = 6, not 11 *)

What the benefits of this idea?

There are two ideas in your example (value bindings and shadowing), so I want to make sure that I answer the right question:

1. Value bindings instead of mutable references means that named values don't change across their lifetime. This is good, because reasoning about your code is easier then. To find the value of a binding, you can go to its definition, and you'll know that it never changed value since then.

   You can make value bindings vary by feeding values to functions. You can think of it as a variable in a mathematical sense, but not in the sense of a mutable reference. So they only vary in the context of being input parameters to a function. For example,

   fun factorial 0 = 1
     | factorial n = n * factorial (n - 1)
   

   Here n is a value binding and a variable in the mathematical sense, but not a mutable reference.

2. Shadowing means that named values can be hidden by other named values of the same name. This is not really a good feature, as it may cause confusion. Just as naming things well is important, not giving two things the same name is equally important.

   Many functional programming languages do not allow shadowing.

   For example, in Erlang the following is an error:

   f(X) ->
       A = 5,
       A = 6,
       X + A.
   

   And in Haskell, the following is an error:

   f :: Int -> Int
   f x = x + a
     where
       a = 5
       a = 6
   

SML does have variables but they do not vary.

Right, so that's true for value bindings, which are the most common in SML. "Immutable variables" can cause confusion because "variable" can mean both "mutable reference" and "function parameter".

SML having both functional and imperative language features also does have mutable references:

val a = ref 5
fun f x = x + !a
val _ = a := 10
val b = f 1  (* 11, not 6 *)

Here ref : 'a -> 'a ref creates a reference and ! : 'a ref -> 'a dereferences it.

These are just as dangerous as in other languages; perhaps less so because you won't accidentally mix 'a and 'a ref as the type system will raise an error. Syntactically they're a little impractical, but this should serve as a reminder that you should be wary of their usage. :-)

Answer 2

Variables do vary in SML, in the same way that variables vary in mathematics. That is, in general they can stand for different values in different circumstances. For example,

fun f x =
  let val a = x + 1 in ... end

Here, the value of a varies with x. This is the original meaning of the word "variable" in mathematics.

What you cannot do is mutate a variable. The same variable will always stand for the same value in a given scope. There are many advantages for making immutability the default, e.g., it prevents entire classes of mistakes and it is much easier to reason about a program, especially when nested functions are involved.

You can still have mutation, but in ML that is a separate concept and more explicit. You need to use references:

let
  val r = ref 1
in
  f (!r);
  r := 2;
  f (!r)
end

Finally, your example demonstrates a completely different phenomena, namely shadowing of declarations. That is not something that is exclusive to ML, your program is similar to the following in C:

{
  const int a = 5;
  {
    const int a = a + 1;
  }
}

The only real difference is that in C, using a on the right-hand side of the second declaration makes it recursively refer to the (yet undefined) second a, whereas in SML declarations are non-recursive by default, such that the a on the right refers to the first declaration.

Because it makes programs more confusing for the human reader, it is not recommended to use shadowing in programs, in neither language. You can always avoid it by renaming one of the variables.