Difference between assignment, binding, and substitution?

Question

I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration, and citations from computer science wiki/articles/textbooks are welcome.

Answer 1

All three notions are related to variables. You can think of variables as named placeholders for some expression.

When introducing/declaring a new variable, you create a placeholder for an abstract expression (abstract in the sense that the variable does not represent a particular expression). Every variable declaration creates also a scope for that variable. A variable's scope is the part of the program that can refer to that variable. For example, in the line below (written in pseudocode)

add(a, b) = a + b;

variables a and b are being declared and their scope is the body of the add function. This means that any reference to a and b from within the body of add will refer to add's parameters. And any reference to a and b from outside the body of add will be meaningless (so you get a compilation error) or will refer to some other variables (which happen to have the same name, but have been declared outside of the function's body).

• Altogether, this behavior is summarized in the sentence "Once a variable is declared, it becomes bound within its scope". Or, specific to this example, add binds the two variables a and b.

There's a third variable being declared in the pseudocode above and that is the add variable. So add is another placeholder, but this time the expression that add represents is not abstract, but a concrete value: it is the function that takes two expressions and returns their sum. Thus,

• Assigning a value to a variable means that, while retaining the functionality of a placeholder, the variable does not represent some abstract expression any more, but an actual concrete expression.

The action of assigning an expression to a variable is closely related to substituting an expression for a variable. One difference is that variable assignment happens explicitly by the programmer at design time, while substitution is an internal mechanism of the language and happens at runtime. Another difference is that, while variable assignment is itself an expression (it is part of the syntax of a language) and keeps the variable in scope, substitution is an action over expressions (it transforms expressions) and it entirely wipes away all occurrences of a variable from that expression. In other words, it eliminates the variable.

The relation between assigned variables and substitution is that all variables that have been assigned a value are internally substituted by their assigned values. This does not mean that substitution is triggered only through variable assignment. Another way is through function application (look up "beta-reduction" for more details).