Variable programs and variable data

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.

• Maybe they mean self-modifying code? – Raphael Apr 1 '14 at 7:28

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.

• Thanks! This makes sense, and seems to fit in with the section. I think the size is the only thing that matters only because all sets of the same cardinality are "set isomorphic". I guess, like you said, Chapter 5 may have more to say on that. – GraduateStudent Apr 1 '14 at 3:01