Path: utzoo!attcan!uunet!jarthur!elroy.jpl.nasa.gov!sdd.hp.com!samsung!rex!fs
From: fs@rex.cs.tulane.edu (Frank Silbermann)
Newsgroups: comp.lang.functional
Subject: Re: BOTTOM !== NONTERMINATION
Message-ID: <3940@rex.cs.tulane.edu>
Date: 26 Jul 90 20:08:53 GMT
References: <23552@megaron.cs.arizona.edu>
Organization: Computer Science Dept., Tulane Univ., New Orleans, LA
Lines: 46


>]		_Bottom_ is NOT synonymous with nontermination!!!!
>]		We are dealing with a DECLARATIVE paradigm,
>]		and nontermination is an _operational_ concept.

David Gudeman:		gudeman@cs.arizona.edu <23552@megaron.cs.arizona.edu>
>	Well, I'd have to say that bottom _is_ synonymous
>	with nontermination if the only programs
>	that are defined to represent bottom
>	are those whose evaluation will never terminate.
>	This is the case in the lambda calculus, for example.

Some nonterminating programs in the lambda calculus
do NOT denote bottom (e.g. the fixpoint operator).
The language of denotational semantics
is a much more realistic basis for functional programming
than the pure untyped lambda calculus.
Who wants to program in a language that has no concrete data-types?
In the area of denotational semantics,
you can make any primitive function produce bottom
for certain inputs, so long as everything
is monotonic and continuous.

>	It might be a good idea _not_ to limit the idea of bottom
>	and let it include more general undefined operations
>	such as out-of-range references and whatever peculiar
>	things might result from that.  In this case, it would be
>	allowable for some program optimizations to change
>	an error result into bottom.  For example,
>	an optimization that removes bounds checking from array
>	references might be allowed even though it has the potential
>	of changing an error result into practically anything.

Or vice-versa.  Though we cannot solve the halting problem,
you _might_ want to build into a students' compiler
routines to catch the most obvious form of infinite looping,
and replace the bad subcomputation with the bottom symbol.
Must the result be considered as a different language,
just because the interpreter is _sometimes_ able to tell you
that the program denotes bottom, instead of just letting it loop?
True, there is some extra metalogical information provided,
but as long as the program is forbidden to make use of it,
it need not be considered a change in the language.

	Frank Silbermann	fs@rex.cs.tulane.edu
	Tulane University	New Orleans, Louisianna  USA