From www@deja.com Fri Oct 8 15:39:55 1999
Message-ID: <7tls35$anr$1@nnrp1.deja.com>
To: oleg@pobox.com
Subject: Re: Acyclic infinite lists and Cantor
Date: Fri, 08 Oct 1999 22:43:52 GMT
Newsgroups: comp.lang.scheme,comp.lang.functional
References: <7rsikm$j87$1@nnrp1.deja.com> <7sbd3q$qhb$1@nnrp1.deja.com> <37F7FECE.438C8E03@ee.uwa.edu.au> <7tbmco$1oa$1@nnrp1.deja.com> <7tfvi8$2r8$1@nnrp1.deja.com>
X-Article-Creation-Date: Fri Oct 08 22:43:52 1999 GMT
X-Http-User-Agent: Mozilla/4.7 (Macintosh; I; PPC)
Sender: www@deja.com
Content-Length: 4122
Status: OR
Is it possible to express infinite and even uncountable sets in a
programming language? If it is, what good can it do?
To decide if computers can "do infinity", it seems important to recall
what computation means. Any computation is merely a symbol
manipulation. We have a sequence of symbols, and rules that allow to
replace a certain combination of symbols with another combination. We
apply the rules to the input sequence until none of them apply any
more (or we have performed enough/too many substitutions).
An arithmetical computation is a symbol manipulation as well. A
multiplication table is a good example: it is actually a set of rules
that tell how we can substitute a sequence "a * b" with another symbol
"c" (where a, b and c are symbols commonly denoted by digits or
sequences of digits, and called numbers).
BTW, from a very high point of view, the only things which "exist" are
the empty set and sets containing the empty set and other sets of
empty set. For _convenience_, we choose to denote some of these sets
with numerals such as "1", "2", ... From that point of view, there is
no conceptual difference between a natural number and a set of all
natural numbers. Both are sets; only the former has a convenient label
(a numeral), and computers are built with rules regarding these
labels. Manipulating natural numbers seems more "natural" than
dealing with cardinal numbers -- yet the fundamental (mental,
computer) activity is just the same: applying the rules.
However, one can define a special label (a bit pattern) representing
"Infinity" and a set of (re-writing) rules involving this
pattern. IEEE Floating-point standard does exactly that. It provides a
special representation for Infinity and defines rules like
a * Infinity --> Infinity (where a is a number and a >0)
-a * Infinity --> -Infinity
a/Infinity --> 0 (where a > 0)
etc. This is really quite helpful.
Another example: try to type in "E^(i Pi)" in Mathematica. Chances
are you get "-1" as the result. The computer thus was able to exactly
manipulate transcendental numbers "E" and "Pi". Furthermore, the
computer was able to "make sense" of "i", which some may say is heck
knows what. No wonder it is "unreal". Well, the computer simply had an
appropriate rewriting rule...
Infinite strings, trees and sequences seem like useless things. It
takes enormously long time to compute them, or to print or compare
them. However, in many situations a particular application examines
only a finite subset of a potentially infinite structure. Alas, often
one can't tell in advance how big this subset is: therefore, one can't
simply precompute it. It doesn't mean though that we have to compute
the whole infinite structure and then hand it over to the
application. We only need to make a "next" element available whenever
the application asks for one. Lazy computation is such a
remarkable invention indeed.
There is another advantage of representing an infinite data
structure with a pair State * NextState where
NextState = State -> Either (State * NextState) State
Sometimes it is possible to apply an operation to an infinite data
structure by performing a manipulation on the procedure NextState.
For example,
(define (succ n)
(cons n (delay (succ (+ 1 n)))))
(define nat (succ 1))
(define (l-map proc stream)
(if (null? stream) stream
(cons (proc (car stream))
(delay (l-map proc (cdr stream))))))
(define evens (l-map (lambda (x) (* 2 x)) nat))
The last statement took one infinite data series and multiplied it by
two, yielding another series. Thus we can pretty much manipulate data
series as if they were numbers. Note that after such a manipulation, a
procedure that used to always yield State * NextState may result in a
State. This means that we can, for example, add two infinite series
and have them cancel each other. Lambda Calculus is especially good
at these symbolic manipulations of "generating functions". Example is
forthcoming (in a lambda calculator with 'shortcuts' I just wrote).