Re: [Scheme-reports] Query - Pairs and Lists

[Ray Dillinger <bear@x>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Regarding improper lists given to a routine expecting a
list;

John Cowan is right on this point.  I'm not disputing it,
I'm just sounding out some related issues.

Passing a structure which is not a list to a procedure that
is specified to work on lists gives a non-specified result.

Implentations may signal an error, but the cost of doing so
(especially in the case where there is no error) would be
high.

So high, in fact, that *guaranteeing* a signaled error would
invalidate the programmer's model of the time complexity
of the code. If such a guarantee were to be made, I'd want
the standard to explicitly warn about it and I'd go through
my copy of the standard stamping a performance warning on
every page that described a list procedure.

The simple recursive implementation of map, for example,
would become O(n-squared) in the length of the list rather
than O(n) if each recursive call to map had to check to
ensure that the rest of the list was a proper list before
proceeding (Hmmm, unless proper-list? memoized its results.
Which it could do, except we have call/cc, so it can't).

In another error case, these functions could also be given
cyclic lists, and simple implementations of them in that case
would result in *infinite* runtimes, which is undesirable. I
think it would be "reasonable" (though not strictly necessary)
for the standard to specify that cyclic lists (or lists with
cyclic tails) must result in signaled errors rather than
infinite runtimes.

Detecting cyclic lists can be done with an O(n) implementation,
in which half the iterations also advance a 'trailing' cons
cell and check it against the 'leading' or active cons cell
for eq?-ness, and that's IMO an "acceptable" performance
penalty for error checking against an infinite loop.

And if the "work" were being done on the 'trailing' rather
than the 'leading' cons cell, that implementation could also
detect and signal an error with an improper list *sometimes*
(when the 'leading' cons cell reached the end of the list).

Hmmm.  I know the standard isn't in the business of giving
performance or complexity guarantees. But for me at least,
being able to accurately guess upperbounds on space and/or
time complexity is a very important part of understanding a
language's design, and when I want to understand a language's
design I reach for the spec.  Hence my copies of language
specs often acquire a lot of after-the-fact markup if the
spec has requirements or common implementations have
strategies which incur performance penalties not obvious
from the design.

R6, unfortunately, acquired so much such markup that it
eventually became pretty useless as anything other than a
warning against using it.

So -- in this case, it makes me uncomfortable to think that
an implementation's fanaticism about error checking allows it
to implement the spec in a way that breaks the not-strictly-
specified "obvious" performance and complexity upperbounds
that inform the design.  But most implementations don't do
that, so I guess that's okay.

And on another hand, I can think of a perfectly good reason
for creating an implementation that guarantees detection of
cycles and could *sometimes* also detect improper lists.

So, anyhow, just ruminations I guess.

				Bear






-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJPU5uVAAoJEAOzWkqOibfNxFMH/0hqTza48psX7+C4M8uLuBG1
JAQRxMck4G80XpjWuW0wIET2lq14UMB8Ta2B42ubZutoO5gLp3OSctgocX2bJ/hg
qeAEiShJVUWIduExDuqLyANNM8CbuiO5BMaPCH1Yi8KiBzu+wwbXWHdaTUW6+45w
ZxVdIxE8OQ4FvTqIWzDDD6pZYIKmdfwk0iMzF+FsVLyBpWEYO8qNkKv+XdPy29+D
Dng4RefaKglFrOBOYyCwcpQeDo9BUV8V8mylZXO14H3iKOF0nZC+T/8GYNIBCTUe
J/7fpfOKMVZIp13n6Vo9Fnwljah+Lj/YixO1xOU4Aq5sdvjUQCvbCxEbFGtVens=
=eHC2
-----END PGP SIGNATURE-----

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports