Computer and Information Science Faculty Research
https://scholarsbank.uoregon.edu/xmlui/handle/1794/3990
2024-03-29T09:19:24ZMacros That Work
https://scholarsbank.uoregon.edu/xmlui/handle/1794/28888
Macros That Work
Clinger, William D.; Rees, Jonathan
This paper describes a modified form of Kohlbecker's algorithm
for reliably hygienic (capture-free) macro expansion
in block-structured languages, where macros are source-tos-ource
transformations specified using a high-level pattern
language. Unlike previous algorithms, the modified algorithm
runs in linear instead of quadratic time, copies few
constants, does not assume that syntactic keywords ( e.g. if)
are reserved words, and allows local (scoped) macros to refer
to lexical variables in a referentially transparent manner.
Syntactic closures have been advanced as an alternative
to hygienic macro expansion. The problem with syntactic
closures is that they are inherently low-level and therefore
difficult to use correctly, especially when syntactic keywords
are not reserved. It is impossible to construct a pattern-based,
automatically hygienic macro system on top of syntactic
closures because the pattern interpreter must be able
to determine the syntactic role of an identifier (in order to
close it in the correct syntactic environment) before macro
expansion has made that role apparent.
may be viewed as a book-keeping
technique for deferring such decisions until macro expansion
is locally complete. Building on that insight, this paper unifies
and extends the competing paradigms of hygienic macro
expansion and syntactic closures to obtain an algorithm that
combines the benefits of both .
Several prototypes of a complete macro system for
Scheme have been based on the algorithm presented here.
9 pages
1991-01-01T00:00:00ZHow to Read Floating Point Numbers
https://scholarsbank.uoregon.edu/xmlui/handle/1794/28887
How to Read Floating Point Numbers
Clinger, William D.
Consider the problem of converting decimal scientific notation
for a number into the best binary floating point approximation
to that number, for some fixed precision. This
problem cannot be solved using arithmetic of any fixed precision.
Hence the IEEE Standard/or Binary Floating-Point
Arithmetic does not require the result of such a conversion
to be the best approximation.
This paper presents an efficient algorithm that always·finds
the best approximation. The algorithm uses a few extra
bits of precision to compute an IEEE-conforming approximation
while testing an intermediate result to determine
whether the approximation could be other than the best.
If the approximation might not be the best, then the best
approximation is determined by a few simple operations
on multiple-precision integers, where the precision is determined
by the input When using 64 bits of precision
to compute IEEE double precision results, the algorithm
avoids higher-precision arithmetic over 99% of the time.
The input problem considered by this papet is the inverse of
an output problem considered by Steele and White: Given
a binary floating point number, print a correctly rounded
decimal representation of it using the smallest number of
digits that will allow the number to be read without loss of
accuracy. The Steele and White algorithm assumes that the
input problem is solved; an imperfect solution to the input
problem, as allowed by the IEEE standard and ubiquitous
in current practice, defeats the purpose of their algorithm.
13 pages
1990-06-05T00:00:00ZBroadcast Time in Communication Networks
https://scholarsbank.uoregon.edu/xmlui/handle/1794/28458
Broadcast Time in Communication Networks
Blaha, Kenneth D.
Broadcasting is the information dissemination process whereby a set of messages is transmitted from one member to all other members of a communication
network . We model a communication network by a graph and place certain
restrictions upon the broadcasting process. Upper and lower bounds on the
time to broadcast m messages throughout a network of n members are determined.
Other time-related issues are addressed, including the estimation of time-optimal
segmentation o f messages which are to be broadcast .
14 pages
1979-05-01T00:00:00ZBroadcasting in Trees with Multiple Originators
https://scholarsbank.uoregon.edu/xmlui/handle/1794/28457
Broadcasting in Trees with Multiple Originators
Farley, Arthur M.; Proskurowski, Andrzej
Broadcasting is the information dissemination process in a communication network whereby all sites of the network become informed of a given message by calls made over lines of the network. We present an algorithm which, given a tree network and a time, determines a smallest set of subtrees covering sites of the network such that broadcast can be completed within the given time in each subtree. Information developed by the algorithm is sufficient to determine a satisfactory originator and calling scheme within each subtree.
13 pages
1980-01-01T00:00:00Z