Cheap and Secure Web Hosting Provider : See Now

Variable programs and variable data

, , No Comments
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.

Asked By : GraduateStudent

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23306

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback