fs@rex.cs.tulane.edu (Frank Silbermann) (07/26/90)
David Gudeman: > ... Bottom is _not_ an error result, > so a program transformation is not allowed > to change a terminating program into a non-terminating program. To refute a common assumption, I must say: _Bottom_ is NOT synonymous with nontermination!!!! We are dealing with a DECLARATIVE paradigm, and nontermination is an _operational_ concept. BOTTOM simply means "undefined" -- nothing more. Nontermination is just one possible way for this to happen. The language designer is free to interpret any syntax he pleases as being undefined. Joe Keane: > I think the question is whether a list > should be allowed to have elements which raise exceptions. This is a matter of taste, and "chacun a son gout." It does seem inconsistent, however, to permit _functions_ which raise exceptions on certain arguments, but to forbid _lists_ from raising exceptions on certain elements. Ramarao Kanneganti: > Error is more informative than bottom. > Would you equate abort(5) with bottom, > simply because abort is unhandled? But it _is_ handled, at least to the extent of returning an error code. If you want your system to return error codes, then a _complete_ denotational semantics would put error codes into the domain. This done, an error code is no different, in principle, from any other atomic value. If you want its occurrance to halt computation, then operations must be strict, so as to detect and propagate the error. If you want a lazy language, you can compute lazy lists which may contain error codes as list-members. > But, if you want to give maximal information, it should be error. Maximal information should not be confused with metalogical information. Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA
gudeman@cs.arizona.edu (David Gudeman) (07/27/90)
In article <3936@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes:
]To refute a common assumption, I must say:
]
] _Bottom_ is NOT synonymous with nontermination!!!!
]
]We are dealing with a DECLARATIVE paradigm,
]and nontermination is an _operational_ concept.
Hmm. 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. And yes, such a statment
is relative to the method of evaluation.
It is important to distinguish between semantics and operations, but
lets not fall into the trap of thinking that it's "impure" or "dirty"
to discuss operations and semantics at the same time. When discussing
optimization you _have_ to discuss semantics and operation at the same
time. Both are involved in the specification of the problem.
This does bring up a point though. 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.
--
David Gudeman
Department of Computer Science
The University of Arizona gudeman@cs.arizona.edu
Tucson, AZ 85721 noao!arizona!gudemanfs@rex.cs.tulane.edu (Frank Silbermann) (07/27/90)
>] _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
gudeman@cs.arizona.edu (David Gudeman) (07/27/90)
In article <3940@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes:
]Some nonterminating programs in the lambda calculus
]do NOT denote bottom (e.g. the fixpoint operator).
My intepreter stops when it finds a head normal form.
]The language of denotational semantics
]is a much more realistic basis for functional programming
]than the pure untyped lambda calculus.
OK.
]... 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.
Why just for a student compiler? Sounds to me like a generally good
thing to have. (BTW, remind me to tell you the story sometime about
the progammer who told me he wrote a program to detect all infinite
loops in FORTRAN programs :-)
]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?
Well, if you are going to give the language a formal semantics (an
exercise of arguable value) then you might as well give a formal
semantics to the various program analyses and transformations. What's
good for the goose is good for the abstract interpretation I always
say...
--
David Gudeman
Department of Computer Science
The University of Arizona gudeman@cs.arizona.edu
Tucson, AZ 85721 noao!arizona!gudemanfs@rex.cs.tulane.edu (Frank Silbermann) (07/27/90)
>] Some nonterminating programs in the lambda calculus >] do NOT denote bottom (e.g. the fixpoint operator). David Gudeman: <23574@megaron.cs.arizona.edu> gudeman@cs.arizona.edu > My intepreter stops when it finds a head normal form. That doesn't mean it has been fully computed. Don't you find it frustrating to write a program to prepare a list, only to find that the interpreter will only say that the result is a kind of ordered pair, without specifying its components? The attempt to fully simplify (compute) an expression (program) will often fail to nonterminate, not just when the result is bottom, but when the result is only partially defined, or even infinite. The idea that only terminating computations matter is one of my pet peeves, actually. >] ... 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? > Well, if you are going to give the language a formal semantics > (an exercise of arguable value) then you might as well > give a formal semantics to the various program analyses > and transformations. What's good for the goose is good > for the abstract interpretation I always say... If you incorporate the effects of the optimizations into your denotational semantics, you might as well just give an operational semantics instead. Denotational semantics is a _functional_ notation for _declaratively_ describing a language's constructs. If the words `declarative' and `functional' don't ring a bell for you, I wonder why you are interested in functional programming in the first place! Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA
gudeman@cs.arizona.edu (David Gudeman) (07/28/90)
In article <3943@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes: > >If you incorporate the effects of the optimizations >into your denotational semantics, you might as well >just give an operational semantics instead. >Denotational semantics is a _functional_ notation >for _declaratively_ describing a language's constructs. I don't think you understand what I'm saying. I suggesting that (1) the denotational semantics are intended to give a rigorous mathematical meaning to a program. (2) it would be nice if the interpreter for the language was --in some sense-- an implementation of the semantics. (3) if you identify all error results together in the semantics, then the interpreter is _not_ an implementation of the semantics, because the interpreter (hopefully) produces informative messages on errors. So (4) the semantics should specify the information content of error messages. This is all fine a good, but there are a lot of optimizations that make it impossible to give informative error messages because information is lost during the course of the optimization. So are we to be left with an optimizing compiler that no longer implements the semantics? Well if you think formal semantics are important for the developement environment (the interpreter) then presumably you think it is good for the production code (the compiler). So, you either need a different semantics or you need to specify the semantic effect of an optimization. In general the _semantic_ effects of optimization involves no more than making some error results into less-defined error results. Some error results may be changed into "undefined". I'm not suggesting that you somehow specify the optimizations in the semantics, only that you specify the semantics of optimized programs. >If the words `declarative' and `functional' >don't ring a bell for you, I wonder why you are interested >in functional programming in the first place! I know what "declarative" and "functional" mean (as well as anyone). I don't think they are synonyms for "good". It is not possible to make a pure declarative language that is adequate for general-purpose programming. However, many of the notations and optimizations that come out of the functional language research are useful in their own right. I'm not religious about functional programming but I'm interested in it; so I guess the answer is that I'm not a member of the church, but I attend services on the off chance that it might be good for my soul. -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
fs@rex.cs.tulane.edu (Frank Silbermann) (07/28/90)
<23593@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman): > I don't think you understand what I'm saying. > I suggesting that (1) the denotational semantics > are intended to give a rigorous mathematical meaning to a program. And, in the case of "functional" languages, to show just in what sense the language is functional (i.e. do the "function definitions" actually denote functions). > (2) it would be nice if the interpreter for the language was > --in some sense-- an implementation of the semantics. > (3) if you identify all error results together in the semantics, > then the interpreter is _not_ an implementation of the semantics, > because the interpreter (hopefully) produces informative > messages on errors. Depends on whether you consider these messages to be metalogical comments _about_ the interpretation, or whether error messages are considered to be _part of_ the interpretation, i.e. data that other parts of the program can use. > I know what "declarative" and "functional" mean (as well as anyone). > I don't think they are synonyms for "good". >... I'm not religious about functional programming > but I'm interested in it; so I guess the answer is that > I'm not a member of the church, but I attend services > on the off chance that it might be good for my soul. Well said! Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA
jgk@osc.COM (Joe Keane) (07/28/90)
In article <3936@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes: >Maximal information should not be confused with metalogical information. In article <3940@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes: >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. This is clearly a useful feature to have. >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. I agree that if the interpreter has all this extra information, but it's not available to user programs, then it's not part of the language. My question is, why would you want to do this? Suppose in the language i write a nifty windowing system including an interactive debugger with flashy graphics, sophisticated tracing, source-level debugging, the works. I'm debugging a program which gets into a detectable infinite loop. The run-time system detects this, spits out a nasty error message in Chinese on the line printer down the hall, and my computer ceases to work henceforth. A lot of good that does me. You've got the information, so put it in the language. You get a new language, which is isomorphic to the old one if you don't use the new features. I don't see what's wrong with that.
gudeman@cs.arizona.edu (David Gudeman) (07/29/90)
In article <3940@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes: > >>] _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... Which was answered fairly effectively, so let me take another tack. The distinguishing feature of bottom is that you don't know what it is when you have it. But if your program terminates, then you know what you have, so what you have isn't bottom. It _doesn't_ work to say that the result is still bottom because it was undefined in the language definition, because then you can prove that bottom = x for whatever x the program produced, and from that you can prove that x = y for any x and y. This seems to me to prove pretty conclusively that bottom implies nontermination. The other side is a little more complex, since it is certainly the case that there are non-terminating programs that produce useful results. But when are the results produced? You can't say that the results are produced when the computation terminates because it won't. But you can say that the result of the program is an infinite sequence of some sort, and that you can look at any desired prefix of the sequence. Then you have a non-terminating program that produces a value distinguishable from bottom. So it is not true that non-termination implies bottom. Well, I was half right. -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
fs@rex.cs.tulane.edu (Frank Silbermann) (08/05/90)
>> (... if an interpreter detects blatant infinite loops ...) >> 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 looping? >> >> As long as the program is forbidden to make use of >> the extra metalogical information, >> it need not be considered a change in the language. >> So bottom need not imply nontermination. In article <3207@osc.COM> jgk@osc.COM (Joe Keane) writes: > Granted, if the extra information is not available > to user programs, then it's not part of the language. > My question is, why would you want to do this? It's all a matter of perspective. When I run my C programs under a debugger, I _could_ consider myself to be using a new language -- the error behavior _is_ different. But I prefer to consider the language and the debugging environment as two distinct parts of the system. When the interpreter stops my program upon seeing `cdr(5)' and tells me what line of the program it was executing, it seems clear to me that this is metalogical information. The program cannot be aware of its own line numbers and still maintain _referential transparancy_. Yet, I find this information critically useful in debugging. Therefore, I consider statements such as `cdr(5)' to be undefined (bottom) in the semantics, and I view error messages as being the output of a rudimentary debugger which my translator invokes by default. By separating the error messages from the semantics, I can view programs in certain languages as being composed of mathematical assertions -- and to me this is what _functional programming_ is all about. Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA