[Haskell-cafe] Re: mathematical notation and functional programming

[Chung-chieh Shan]

On 2005-01-28T20:16:59+0100, Henning Thielemann wrote:
> On Fri, 28 Jan 2005, Chung-chieh Shan wrote:
> > But I would hesitate with some of your examples, because they may simply
> > illustrate that mathematical notation is a language with side effects --
> > see the third and fifth examples below.
> I can't imagine mathematics with side effects, because there is no order
> of execution.

To clarify, I'm not saying that mathematics may have side effects, but
that the language we use to talk about mathematics may have side
effects, even control effects with delimited continuations.

Shift and reset, and other delimited control operators such as control
and prompt (which date earlier than shift and reset), are neat.  Given
that we are talking about language semantics, you may be interested in
my paper at http://www.eecs.harvard.edu/~ccshan/cw2004/cw.pdf (which
quickly introduces shift and reset).

> > > F(x) = \int f(x) \dif x
> > >    where x shouldn't be visible outside the integral
> > (Not to mention that F(x) is only determined up to a constant.)
> right, so \int needs a further parameter for the constant

Or you can take integration to return a set of functions, and = as \in.
That's not actually how I would ultimately analyze things, but it seems
to be a start.

> People say, it is obvious what O(n^2) means. For me it is obvious that
> they probably want to pass a constant function in, because O takes a
> function as argument and because I know people often don't distinguish
> between constant functions and scalar values.  Then O(n) = O(n^2) because
> O(n) and O(n^2) denote the set of constant functions. :-)

I am interested in "descriptive mathematical notation" rather than
"prescriptive mathematical notation" (these are just my terms), in the
sense that I want to first ask people what they take certain existing
pieces of mathematical notation to mean, then figure out formal rules
that underlie these "obvious" interpretations.

> But what do you mean with 1/O(n^2) ? O(f) is defined as the set of
> functions bounded to the upper by f.  So 1/O(f) has no meaning at the
> first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x)
> (i.e. lifting from scalar reciprocal to the reciprocal of a function) and
> then as lifting from a reciprocal of a function to the reciprocal of each
> function of a set. Do you mean that?

Wait a minute -- would you also say that "1+x" has no meaning at the
first glance, because "x" is a variable whereas "1" is an integer, so
some lifting is called for?

> I never heard about shift and reset operators, but they don't seem to be
> operators in the sense of higher-order functions.

Right; they are control operators in the sense that call/cc is a control
operator.

> > With some more trickery underlying the equal sign, one can state
> > meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false.
> Sticking to the set definition of O we would need no tricks at all:
> O(\n -> n) \subset O(\n -> n^2)
> and
> O(\n -> n)  /=  O(\n -> n^2)

By "trickery" I meant taking "=" to not denote equality.  So for me,
taking "=" to denote the subset relation would count as a trick.

> > > f(.)
> > >    which means \x -> f x or just f
> >
> > I regard this as reset(f(shift k. k)).  Besides, even Haskell has (3+).
> 
> Hm, (3+) is partial application, a re-ordered notation of ((+) 3), which
> is only possible if the omitted value is needed only once. But I see
> people writing f(.) + f(.-t) and they don't tell, whether this means
>   (\x -> f x) + (\x -> f (x-t))
> or
>   (\x -> f x + f (x-t))
> In this case for most mathematicians this doesn't matter because in the
> above case (+) is silently lifted to the addition of functions.

Yes, so in my mind an environment monad is in effect (so to speak) here,
and the difference between the two meanings you pointed out is the
difference between

    liftM2 (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t)))

and

    (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t)))

(where import Monad and Control.Monad.Reader :).

> > But AFAIK, nobody ever promised that the mathematical notation used to
> > talk about functions must denote functions themselves.
> I found that using a notation respecting the functional idea allows very
> clear terms. So I used Haskell notation above to explain, what common
> mathematical terms may mean.

But Haskell notation does -not- respect the functional idea.  First
there's the issue of variables: to respect the functional idea we must
program in point-free style.  Second there's the issue of types: to
respect the (set-theoretic) functional idea we must abolish polymorphism
and annotate our lambda abstractions in Church style.  Surely we don't
want the meaning of our mathematical formulas to depend on the semantics
of System F(-omega)!

Or, as I would prefer, we could design our notation to be both intuitive
and formally tractable, without requiring that the concrete syntax of
our language directly correspond to the semantics of mathematics or
programming.  The (simply-typed, pure) lambda-calculus does that, at the
(very reasonable) cost of having us specify things like alpha-conversion
and substitution.

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
War crimes will be prosecuted. War criminals will be punished. And it
will be no defense to say, "I was just following orders."'
                    George W. Bush, address to the nation, 2003-03-17
      http://www.whitehouse.gov/news/releases/2003/03/20030317-7.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20050128/cd0c7571/attachment.bin