Cheap and Secure Web Hosting Provider : See Now

# Variable programs and variable data

, ,
Problem Detail:

I'm reading "Sets for Mathematics" by Lawvere, and he uses the following metaphor at the end of section 1.3: "we will see...how any abstract set F of the right size can act as mappings between given abstract sets. (For example, in computers variable programs are just a particular kind of variable data.)"

The internet seems silent on these so called "variable programs". Has anyone heard of them/has an accessible introduction (at an introductory graduate level)? Extra bonus points if you can explain how this relates to sets and functions.

#### Answered By : Yuval Filmus

It seems that the authors refer to "functions as first-class variables". In functional languages you have variables which store functions. You can think of them as program variables since they store programs. On the other hand, if you look at how the programs are stored physically, then you get unstructured variable data.

Let's be more concrete. The (somewhat functional) programming language Python has a function `eval` which takes as argument a Python program. Consider the following code:

``prog = "sum([x for x in range(5)])" print eval(prog) ``

This prints \$10\$ (since in Python `range(5) = [0,1,2,3,4]`). Here `prog` is a program variable since it stores a program. On the other hand, `prog` is also just a mundane string (variable data). From the point of view of Python, unless you try to evaluate it ("cast" it into a program), `prog` is basically just a string.

If we use an enumeration of programs like in recursion theory, then program variables really are unstructured — they are just integers. If Python supported this convention then `prog` would be just some number with no apparent structure.

In the same way, a set-theoretic function is just another set, unless you treat it as a function. Given two sets \$A,B\$, we can construct the set which contains all mappings from \$A\$ to \$B\$; I don't quite understand why only the "size" (i.e., cardinality) of this set matters, but I guess you'll have to wait until Chapter 5. Perhaps they mean that with the correct encoding function, every set of the correct cardinality can be used as an index set for all mappings from \$A\$ to \$B\$, just like the enumeration of programs mentioned above.