🚀 go-pugleaf

In article <2706@bruce.cs.monash.OZ.AU> mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) writes:
|
|let rec first n l =
|		if n = 0 then []
|		else (hd l).(first (n-1) (tl l))
|and rec length l =
|		if l = [] then 0
|		else 1 + length (tl l)
|in
|    length (first 2 [])
|
|In a strict language, the result is an error, due to the (tl []) in "first".
|
|In a lazy language (LML here), you get the result 2.
|
|If we replace those IFs with pattern matching, which is slightly
|stricter than it needs to be, we get a pattern match failure.
|
|The problem, in this case, is that "length" is passed a list of
|closures (of length 2) which are never evaluated, but which correspond
|to nonexistent list elements.
|
|Is this problem well known?  Has anyone any insight into what the
|language "should" do, and why?  Is it just a case of the increased
|freedom of laziness introducing a more subtle class of errors?

I don't think there's a good answer to your question (as it relates to
this example, anyway) unless it is clear what 'first' is intended to
mean.  The given definition for 'first' appears to be incorrect.

What is supposed to be the result of

	(first 2 [])

for example? A "correct" version of 'first' might be

	let rec cfirst n l =
			if n = 0 then []
			else if l = [] then []
			else (hd l).(cfirst (n-1) (tl l))

in which case the indicated behavior does not occur.

	Tom

blenko-tom@CS.YALE.EDU (Tom Blenko) writes:

>In article <2706@bruce.cs.monash.OZ.AU> mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) writes:
>|
>|let rec first n l =
>|		if n = 0 then []
>|		else (hd l).(first (n-1) (tl l))
>|and rec length l =
>|		if l = [] then 0
>|		else 1 + length (tl l)
>|in
>|    length (first 2 [])
>|
>|In a strict language, the result is an error, due to the (tl []) in "first".
>|
>|In a lazy language (LML here), you get the result 2.
>| [..]

>I don't think there's a good answer to your question (as it relates to
>this example, anyway) unless it is clear what 'first' is intended to
>mean.  The given definition for 'first' appears to be incorrect.

>What is supposed to be the result of

>	(first 2 [])

>for example? A "correct" version of 'first' might be

>	let rec cfirst n l =
>			if n = 0 then []
>			else if l = [] then []
>			else (hd l).(cfirst (n-1) (tl l))

>in which case the indicated behavior does not occur.


The intended definition is obviously:

	let rec first n l =
			if n = 0 then []
			else if l = [] then BOTTOM 
			else (hd l).(cfirst (n-1) (tl l))

where BOTTOM must be an unslightly polymorphic zero-arity function!! 
The example enlightens the pain of "lazy" languages (beside the
notion, which stands only for some implementation detail, but not
for a sematical concept). 

(-:

You folks of the lazy lobby (so silent about Mikes 
example?), have you ever written larger programs in NOR languages?
Of course you have, but no debugging was necessary, because
they have been totally correct from the beginning. 

Say, have you ever delegated a programming task in a NOR language
to someone else, for example, to a student, and then must use yourself
this service? Of course you have, but your students (or assistants,
to step upwards) always write totally correct programs, and so there
was no need to view hours all of your excellent code and figure out
at least a bug in a trivial function at a totally other place.

:-)

Very seriously, according to my experience pure "lazyness" seems 
not be the way to solve the "software-crisis". Some might imagine
marvelous debuggers buts thats an old argument of the von-Neumann 
fraction. 

I believe strictness introduces a kind of redundancy, which makes 
programs easier to understand, to valificate, to verify, and 
(consequently) to manipulate formally. There is only a small 
number of problems which are naturally normal-order (streams). 
The rest is only some kind of dirty programmer optimization 
(if I reduce "lazy" bool conjunction over a list, then it stops when 
the first FALSE occurs and something like this).

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Wolfgang Grieskamp 
wg@opal.cs.tu-berlin.de tub!tubopal!wg wg%opal@DB0TUI11.BITNET

response to Wolfgang Grieskamp's shot across the bows of lazy languages:-

I guess there'll be plenty of other responses, so I'm not going into the
whole lazy versus eager thing.  Three points though:-

1)  WG's BOTTOM should of course be TOP, there isn't an absence of information
    (or a nonterminating construct), there's an excess of information (the
    function's type requires the argument to have type non-nil-list, the
    argument type is nil-list, the inferred type would have to have both
    pieces of information which pushes it straight to the top of the type
    lattice).  Mostly, I prefer to call this sort of thing ERROR rather
    than TOP or BOTTOM  but BOTTOM is just plain wrong.

2)  Almost all the code I've ever written has been splattered with "if you
    ever get here, generate an error". Hope+ even had the type ERROR 
   added to it to permit this style of programming. The flagship machine
   design included tag bits with every value, one of which indicated that
   the value had type "ERROR" and our parallel emulators implemented it.
    Most large software systems have this sort of programming, and we're
   quite happy when no errors are generated because those bits don't get
   executed.  Lazy languages allow this style of programming, just as
   imperative languages did, but eager languages effectively prevent it

3)  Why should it be assumed that the presence of a construct which, if
   evaluated, leads to an error or a nonterminating computation is a bug?
   I don't much like the original program, but if it's what the programmer
   intended there's no bug in it. For nice examples of bottom, some of us
   program with infinite lists all the time (and intentionally write
   non-terminating loops in imperative languages too). 

Tom Thomson

Mike McGaughey)
>>>	Are there situations where lazy evaluation is *too* lazy?
>>>	The following example (due to Lloyd Alison) shows what I mean:
>>>	Let
>>>		rec first n l be
>>>			if n = 0 then [] else (hd l).(first (n-1) (tl l))
>>>	and
>>>		rec length l be
>>>			if l = [] then 0 else 1 + length (tl l)
>>>	in	length (first 2 [])
>>>
>>>	In a strict language, the result is an error,
>>>	due to the (tl []) in "first".
>>>	In a lazy language (LML here), you get the result 2.
>>>
>>>	The problem, in this case, is that "length"
>>>	is passed a list of closures (of length 2)
>>>	which are never evaluated, but which correspond
>>>	to nonexistent list elements.
>>>	 What "should" the language do, and why?

Tom Blenko:
>>	I don't think there's a good answer to your question
>>	(as it relates to this example, anyway) unless it is clear
>>	what 'first' is intended to mean.
>>	What is supposed to be the result of `(first 2 [])', for example?

In a lazy language, you have two choices.
You can define the result to be "bottom",
(the least-defined domain element, according to the partial-order).
This approach emphasizes flexibility at the expense of safety,
and is therefore appropriate in a language for building prototypes.
Or, you can use strong typing to catch all such operations
at compile-time and reject such programs as illegal.  
This approach emphasizes safety at the expense of flexibility,
and is therefore more appropriate for building a production system.

Wolfgang Grieskamp:
>	The intended definition is obviously: ...

If the language was defined via an operational semantics,
then whatever result the standard implementation provides
is the correct result, by definition.  However,
here there seem to be doubt as to whether
the result is really what the implementor intended.

Such questions are less likely to arise when
the language is defined via denotational semantics.
Rather than defining the constructs implicitly
via a black-box implementation, denotational semantics
gives the intended meaning more directly.
This is surely one of the motivations its development.

Wolfgang Grieskamp:
>	According to my experience pure "lazyness" seems 
>	not be the way to solve the "software-crisis".
>	I believe strictness makes programs easier to understand,
>	to valificate, to verify, and (consequently) to manipulate formally.
>	There is only a small number of problems which are naturally
>	normal-order (streams). 

One of my research projects is a language offering
_both_ lazy and strict constructs, so the programmer
can consider the situation and choose appropriately.

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

In article <2706@bruce.cs.monash.OZ.AU> mmcg@bruce.cs.monash.OZ.AU (Mike
McGaughey) writes:
>Are there situations where lazy evaluation is *too* lazy?
>
>The following example (due to Lloyd Alison) shows what I mean:
>
>let rec first n l =
>		if n = 0 then []
>		else (hd l).(first (n-1) (tl l))
>and rec length l =
>		if l = [] then 0
>		else 1 + length (tl l)
>in
>    length (first 2 [])
>
>In a strict language, the result is an error, due to the (tl []) in "first".
>
>In a lazy language (LML here), you get the result 2.

The whole idea of being lazy is that you do as little work as possible.  The
constraint is that that you can't change the return values or side effects of
an expression.  One thing that you are allowed to do is change bottom into
some valid value, as long as you're consistent.  I won't explain this, except
to point out that a program which gets stuck can't contradict one that does
something useful.

Many functional languages are weak in exception handling.  For example, one
whose name i won't mention says that if you get any error, you lose, the
result is the same as bottom.  In a language like this, it is valid for the
example expression to return 2, for the reason given above.

Now suppose we're in a language with real exception handling.  It's only a
matter of terminology whether you count an exception as a kind of return
value, a side effect, or something different.  Given the constraint above, the
implementation must examine the expression far enough to determine whether it
will raise an exception.  This is exactly what you'd expect.  If it doesn't,
it's broken.

In summary, i think exception handling is an important part of any language.
In particular, defining errors to be the same as bottom is an unwise thing to
do, and this example points out some of the consequences.

In article <3913@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann)
writes:
>In a lazy language, you have two choices.
>You can define the result to be "bottom",
>(the least-defined domain element, according to the partial-order).
>This approach emphasizes flexibility at the expense of safety,
>and is therefore appropriate in a language for building prototypes.
>Or, you can use strong typing to catch all such operations
>at compile-time and reject such programs as illegal.  
>This approach emphasizes safety at the expense of flexibility,
>and is therefore more appropriate for building a production system.

I don't agree with this dichotomy.  Specifically, i don't like either of the
alternatives.  There are better ways to handle the problem.

Despite what some people say, i don't think strong typing is such a good deal.
It catches obvious errors, but doesn't do you any good against less obvious
bugs.  In the example given, strong typing is no help, unless perhaps your
typing system includes the length of a list.  The problem is how to predict
and deal with run-time errors.

In article <3188@osc.COM> jgk@osc.COM (Joe Keane) writes:
>
>	Suppose we're in a language with real exception handling.
>	It's only a matter of terminology whether you count an exception
>	as a kind of return value, a side effect, or something different.

>	In particular, defining errors to be the same as bottom
>	is an unwise thing to do ...

If you "handle" an exception then it is no longer an error
-- just another possible result.  Semantically speaking,
an error is an _unhandled_ exception.  Since it is unhandled,
why not declare the result to be `undefined' (i.e. is bottom)?

Make an analogy with mathamatics.  Consider the function f(x) = 5/x.
What is the value of the function at x=0?  `Error' or `undefined'?

It is a design issue as to whether you make the programmer
handle exceptions explicitly, or whether the language implicitly
tacks on exception-handling routines.  I have no argument
with those who advocate implicit exception-handling mechanisms
(though the increased expressiveness requires a more complicated language).

	Frank Silbermann	fs@rex.cs.tulane.edu

In article <3926@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes:
>If you "handle" an exception then it is no longer an error
>-- just another possible result.  Semantically speaking,
>an error is an _unhandled_ exception.  Since it is unhandled,
>why not declare the result to be `undefined' (i.e. is bottom)?

Error is much more than bottom. Bottom is least informative. If you
sitting in front of a terminal you notice when the program doesn't
come back with any thing, or if it comes back with an error message.
Error is more informative than bottom. Would you equate abort(5) with
bottom, simply because abort is unhandled?

>
>Make an analogy with mathamatics.  Consider the function f(x) = 5/x.
>What is the value of the function at x=0?  `Error' or `undefined'?
>

It can be a matter of choice of how you define the function f. But, if
you want to give maximal information, it should be error.  Suppose you
have a domain with a chain like, a <= b <= c. After getting the result
b, in the further query, you get an error. Do you still call the
result b? I claim that it is an error element, and it is above b. But
any function which is strict in bottom is also strict in error, so any
choice will be consistent.


>	Frank Silbermann	fs@rex.cs.tulane.edu

	thanks,
	Ramarao Kanneganti	rama@rice.edu

In article <10268@brazos.Rice.edu> rama@titan.rice.edu (Ramarao Kanneganti) writes:
>result b? I claim that it is an error element, and it is above b. But
>any function which is strict in bottom is also strict in error, so any
>choice will be consistent.
Strange way of putting it.  
Trouble is assigning a meaning to "strict in error".
Normally "strict" means "does not transform bottom or top", and "strict in
bottom" means "does not transform bottom".  So "strict in error", by analogy,
would mean "does not transform error"; if that's what you meant, I am in 
TOTAL DISagreement with you - the information in the error can be used to derive
a result.
On the other hand, maybe you meant that any program that was going to try to
evaluate bottom would try to evaluate the error that occurred in the place
where the bottom would otherwise have been, ie if you were going to hit a 
bottom then you'ld hit an error if that particular bottom were turned into 
that; then I would agree with you.
 
Maybe if we are going to discuss both errors and strictness we need a definition
for phrases like "strict in error"?  Or maybe we shouldn't use such phrases?