Hi Andrew, (Caveat: I'm not an expert in this field, although I find it fascinating, so I hope that the experts who are listening will forgive and correct any misstatements.) I think your answer ("a function defined on the empty set corresponds to a function that can never be called") is almost right. A programming function having n arguments x_1,...,x_n can be represented by a set-theoretic function whose domain is an n-ary cartesian product: A_1 \times ... \times A_n --> B where A_i is the set of values in the type of the variable x_i, and B is the output type of the function. Thus, for instance, a function of two variables with type Int whose output is type Real would be represented by Z \times Z --> R where Z is the set of integers and R the set of real numbers (or maybe the set of floating-point values, depending on what "Real" means to your compiler). Of course, the set-theoretic function is "extensional," meaning it only knows what output results from each list of inputs rather than how that output is computed; thus many different pieces of code will denote the same function. The fancy word for this is "denotational semantics." Now setting n=0, we see that a programming function of no arguments is represented by a morphism 1 --> B where 1, a one-element set, is a zero-ary cartesian product. In other words, it is just a constant (global) element of B. The way to represent a function with empty domain in programming is as a function whose input is of a -type- that admits no values. Thus, this function "can never be called" because there is no argument that you can give it. Normal programming languages do not generally come with predefined types that admit no values, since such types are evidently not very useful! You can define a good approximation to such a type in an OO language by writing a class whose only constructor throws a fatal error; thus there will be no possible "values" having that type. Of course, there will then be many different "functions" in the programming sense that you could write whose domain is such a type, but they will all have the same denotation, namely the unique function from the empty set to the set of values of their output type. By the way, this all assumes that your programming functions are "strict" in the "call-by-value" sense that all their arguments must be completely computed before the function is allowed to execute. However, if you allow "lazy" functions which can ignore some of their input, which exist in some programming languages, then there can be plenty of different functions defined on an "empty" type. For instance, in a lazily evaluated language the function with one input of an empty type and defined by "return 3" can still be evaluated and will promptly return 3. Since it never -uses- its input, the lazy language won't even bother trying to figure out what that input is, and hence won't encounter the fatal error that the input doesn't exist. In denotational semantics, this is modeled by working, not in a category of sets, but in a category of a special sort of -posets-. Among other properties, these posets always have bottom elements, which represent the "undefined" value, but the functions between them are not required to preserve the bottom elements. Such a category generally has no initial object; the "empty" type corresponds to the one-element poset, but there are in general many functions out of this object. Best, Mike On Fri, Mar 13, 2009 at 6:29 AM, Andrew Stacey <andrew.stacey@math.ntnu.no> wrote:
Here's a question for those who know about translating between category theory for mathematicians and category theory for computer programmers.
In class today I was discussing functions with domain the empty set. The students don't have much background in formal set theory (and none in category theory though I'm doing my best to sneak it in where I can) so they were trying to get to grips with the idea that the _are_ functions from the empty set, but just not very many of them.
Afterwards, one student asked about how this related to functions as used in computer programming. It seemed from what he said that he had some understanding of the formal relationship between functions in mathematics and functions in computer programs - beyond them having the same name. He said that a function that takes no input is known as a "constant function" and so wasn't sure how to fit the two notions together.
I, on the other hand, am at the level of "Ooo, look! Mathematicians and computer programmers both use the word 'function'. So do biologists and event organisers. Maybe we should organise a function whose function would be to investigate all these different uses.' so I didn't know what answer to give.
The best that I could think of was that program functions have a 'hidden' input: the fact that they have been called. So a function defined on the empty set corresponds to a function that can never be called.
Can anyone help me straighten this out?
Extra kudos for answers that I can just pass on to the student!
Thanks,
Andrew Stacey