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

[Chung-chieh Shan]

Henning Thielemann <lemming at henning-thielemann.de> wrote in article <Pine.LNX.4.44.0501261011020.25777-100000 at peano.math.uni-bremen.de> in gmane.comp.lang.haskell.cafe:
> Over the past years I became more and more aware that common mathematical
> notation is full of inaccuracies, abuses and stupidity. I wonder if
> mathematical notation is subject of a mathematical branch and whether
> there are papers about this topic, e.g. how one can improve common
> mathematical notation with the knowledge of functional languages.

I would like to know too!

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.

> Things I'm unhappy about are for instance
> f(x) \in L(\R)
>    where f \in L(\R) is meant

(I'm not sure what you are referring to here -- is there a specific L
that you have in mind?)

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

> O(n)
>    which should be O(\n -> n) (a remark by Simon Thompson in
>                                The Craft of Functional Programming)

I'm worried about this analysis, because would O(1) mean O(\n -> 1), and
1/O(n^2) mean 1/O(\n -> n^2)?  And what about the equal sign in front of
most uses of big-O notation?  I would rather analyze this notation as

    O = shift k. exists g. g is an asymptotically bounded function
                           and k(g(n))

where "shift" is Danvy and Filinski's control operator (paired with
"reset").  This way, we can use (as people do)

    reset(f(n) = 2^{-O(n)})

to mean that

    exists g. g is an asymptotically bounded function
              and f(n) = 2^{-g(n)*n}.

Note that the argument to g is not specified in the original notation,
and neither is the reset explicit.  But the parentheses in "O(n)" is now
regarded as mere multiplication (making "O-of-n" a mispronunciation).

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.

> a < b < c
>    which is a short-cut of a < b \land b < c

What do you think of [a,b,c] for lists?

> f(.)
>    which means \x -> f x or just f

I regard this as reset(f(shift k. k)).  Besides, even Haskell has (3+).

> All of these examples expose a common misunderstanding of functions, so I
> assume that the pioneers of functional programming also must have worried
> about common mathematical notation.

But AFAIK, nobody ever promised that the mathematical notation used to
talk about functions must denote functions themselves.  To take another
example, even though programs are morphisms, we don't always program
in point-free style.  And the English word "nobody" does not denote
anybody!

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