Checking understanding of: "Variable" v.s. "Value", and "function" vs "abstraction"

Question

(This question is a follow-up of this one while studying Haskell.)

I used to find the notion between "variable" and "value" confusing. Therefore I read about the wiki-page of lambda calculus as well as the previous answer above. I come out with below interpretations.

May I confirm whether these are correct? Just want to double confirm because these concept are quite basic but essential to functional programming. Any advice is welcome.

Premises from wiki:

Lambda Calculus syntax
exp → ID
| (exp)
| λ ID.exp // abstraction
| exp exp // application

(Notation: "<=>" equivalent to)

Interpretations:

1. "value": it is the actual data or instructions stored in computer.
   "variable": it is a way locating the data, a value-replacing reference , but not itself the set of data or instruction stored in computer.
   "abstraction" <=> "function" ∈ syntactic form. (https://stackoverflow.com/a/25329157/3701346)
   "application": it takes an input of "abstraction", and an input of "lambda expression", results in an "lambda expression".
   "abstraction" is called "abstraction" because in usual function definition, we abbreviate the (commonly longer) function body into a much shorter form, i.e. a function identifier followed by a list of formal parameters. (Though lambda abstractions are anonymous functions, other functions usually do have name.)

2. "variable" <=> "symbol" <=> "reference"
   a "variable" is associated with a "value" via a process called "binding".

3. "constant" ∈ "variable"
   "literal" ∈ "value"
   "formal parameter" ∈ "variable"
   "actual parameter"(argument) ∈ "value"

4. A "variable" can have a "value" of "data" => e.g. variable "a" has a value of 3

5. A "variable"can also have a "value" of "a set of instructions" => e.g. an operator "+" is a variable

Answer 1

"value": it is the actual data or instructions stored in computer.

You're trying to think of it very concretely in terms of the machine, which I'm afraid may confuse you. It's better to think of it in terms of math: a value is just a thing that never changes, like the number 42, the letter 'H', or the sequence of letters that constitutes "Hello world".

Another way to think of it is in terms of mental models. We invent mental models in order to reason indirectly about the world; by reasoning about the mental models, we make predictions about things in the real world. We write computer programs to help us work with these mental models reliably and in large volumes.

Values are then things in the mental model. The bits and bytes are just encodings of the model into the computer's architecture.

"variable": it is a way locating the data, a value-replacing reference , but not itself the set of data or instruction stored in computer.

A variable is just a name that stands for a value in a certain scope of the program. Every time a variable is evaluated, its value needs to be looked up in an environment. There are several implementations of this concept in computer terms:

• A stack frame in an eager language is an implementation of an environment for looking up the values of local variable, on each invocation of a routine.
• A linker provides environments for looking up global-scope names when a program is compiled or loaded into memory.

"abstraction" <=> "function" ∈ syntactic form.

Abstraction and function are not equivalent. In the lambda calculus, "abstraction" a type of syntactic expression, but a function is a value.

One analogy that's not too shabby is names and descriptions vs. things. Names and descriptions are part of language, while things are part of the world. You could say that the meaning of a name or description is the thing that it names or describes.

Languages contain both simple names for things (e.g., 12 is a name for the number twelve) and more complex descriptions of things (5 + 7 is a description of the number twelve). A lambda abstraction is a description of a function; e.g., the expression \x -> x + 7 is a description of the function that adds seven to its argument.

The trick is that when descriptions get very complex, it's not easy to figure out what thing they're describing. If I give you 12345 + 67890, you need to do some amount of work to figure out what number I just described. Computers are machines that do this work way faster and more reliably than we can do it.

"application": it takes an input of "abstraction", and an input of "lambda expression", results in an "lambda expression".

An application is just an expression with two subexpressions, which describes a value by this means:

1. The first subexpression stands for a function.
2. The second subexpression stands for some value.
3. The application as a whole stands for the value that results for applying the function in (1) to the value from (2).

In formal semantics (and don't be scared of that word) we often use the double brackets ⟦∙⟧ to stand for "the meaning of"; e.g. ⟦dog⟧ = "the meaning of dog." Using that notation:

⟦e1 e2⟧ = ⟦e1⟧(⟦e2⟧)

where e1 and e2 are any two expressions or terms (any variable, abstraction or application).

"abstraction" is called "abstraction" because in usual function definition, we abbreviate the (commonly longer) function body into a much shorter form, i.e. a function identifier followed by a list of formal parameters. (Though lambda abstractions are anonymous functions, other functions usually do have name.)

To tell you the truth, I've never stopped to think whether the term "abstraction" is a good term for this or why it was picked. Generally, with math, it doesn't pay to ask questions like that unless the terms have been very badly picked and mislead people.

"constant" ∈ "variable"

"literal" ∈ "value"

The lambda calculus, in and of itself, doesn't have the concepts of "constant" nor "literal." But one way to define these would be:

• A literal is an expression that, because of the rules of the language, always has the same value no matter where it occurs.
• A constant, in a purely functional language, is a variable at the topmost scope of a program. Every (non-shadowed) use of that variable will always have the same value in the program.

"formal parameter" ∈ "variable"

"actual parameter"(argument) ∈ "value"

Formal parameter is one kind of use of a variable. In any expression of the form λv.e (where v is a variable and e is an expression), v is a formal variable.

An argument is any expression (not value!) that occurs as the second subexpression of an application.

A "variable" can have a "value" of "data" => e.g. variable "a" has a value of 3

All expressions have values, not just variables. For example, 5 + 7 is an application, and it has the value of twelve.

A "variable"can also have a "value" of "a set of instructions" => e.g. an operator "+" is a variable

The value of + is a function—it's the function that adds its arguments. The set of instructions is an implementation of that function.

Think of a function as an abstract table that says, for each combination of argument values, what the result is. The way the instructions come in is this:

1. For a lot of functions we cannot literally implement them as a table. In the case of addition it's because the table would be infinitely large.
2. Even for functions where we can enumerate the cases, we want to implement them much more briefly and efficiently.

But the way you check whether a function implementation is correct is, in some sense, to check that in every case it does the same thing the "infinite table" would do. Two sets of instructions that both check out in this way are really two different implementations of the same function.

Answer 2

1. The word "abstraction" is used because we can't "look inside" a function and see what's going on for the most part so it's "abstract" (contrast with "concrete"). Application is the process of applying a function to an argument. This means that its body is run, but with the thing that's being applied to it replacing the argument name (avoiding any capture). Hopefully this example will explain better than I can (in Haskell syntax. \ represents lambda): (\x -> x + x) 5 <=> 5 + 5 Here we are applying the lambda expression on the left to the value 5 on the right. We get 5 + 5 as our result (which then may be further reduced to 10). A "reference" might refer to something somewhat different in the context of Haskell (IORefs and STRefs), but, internally, all bindings ("variables") in Haskell have a layer of indirection like references in other languages (actually, they have even more indirection than that in a way because of the non-strict evaluation).

2. This mostly looks okay except for the reference issue I mentioned above.

3. • In Haskell, there isn't really a distinction between a variable and a constant.

   • A "literal" usually is specifically a constructor for a value. For example, 20 constructs the the number 20, but a function application (\x -> 2 * x) 10 wouldn't be considered a literal for 20 because it has an extra step before you get the value.

   • Right, not all variables are parameters. A parameter is something that is passed to a function. The xs in the lambda expressions above are examples of parameters. A non-example would be something like let a = 15 in a * a. a is a "variable" but not a parameter. Actually, I would call a a "binding" here because it can never change or take on a different value (vary).

   • The formal parameter vs actual parameter part looks about right.

4. That looks okay.

5. I would say that a variable can be a function instead. Usually, in functional programming, we typically think in terms of functions and function applications instead of lists of instructions.

I'd like to point out also that you might get in trouble by thinking of functions as just syntactic forms. You can create new functions by applying certain kinds of higher order functions without using one of the syntactic forms to construct a function directly. A simple example of this is function composition, (.) in Haskell

(f . g) x = f (g x)   -- Definition of (.)

(* 10) . (+ 1)    <=>   \x -> ((* 10) ((+ 1) x))   <=>   \x -> 10 * (x + 1)

Writing it as (* 10) . (+ 1) doesn't directly use the lambda syntax or the function definition syntax to create the new function.