Re: Functions in programming

[Michael Shulman <shulman@math.uchicago.edu>]

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
>
>
>