[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bitwise logical operators



|   What would distinguish the "library"
|   section from the "language" section is that everything in the "library"
|   section could be expressed reasonably efficiently (O(1), though,
|   possibly, with somewhat large constants) in terms of language
|   primitives (except macros).
|
|The O(1) constraint is rather stringent.  SORT, a prototypical library
|function, would not conform, would it?  FFT's and databases come to
|mind as well.  I suppose one could hide linear factors by the use of
|MAP and FOR-EACH, but this would encourage convoluted algorithms for
|the sake of inclusion.

By "O(1)" I mean the relative performance of a hypothetical built-in
and its simulation in a library. SORT is Theta(N log N) regardless
of whether you put it in the standard library or the language.
Vectors, on the other hand, could not be simulated in time "O(1)"
if they weren't provided as primitives, so they should stay in the
"language" section.

Again, the purpose of having a separate library section would be
that implementors could choose to go with acceptable standard versions
of functions, or that they could choose to special-case commonly
used functions in the compiler.

For example, I would think that SIN should be part of the library (with
a reasonably portable implementation), but that high-performance
implementations would generate in-line code for it. Other candidates
for the library are multidimensional arrays, hash tables, and
non-generic arithmetic functions.

I'm no proposing this as a hard rule, but simply as what I consider
a "reasonable guideline".

					Thomas.