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