Scheme language standardization process
-----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