Computer and Information Science Faculty Research

Permanent URI for this collection

https://hdl.handle.net/1794/3990

For information about the department, please see the department's web site.

Browse

Browsing Computer and Information Science Faculty Research by Author "Clinger, William D."

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    How to Read Floating Point Numbers
    (University of Oregon, 1990-06-05) 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.
  • Thumbnail Image
    ItemOpen Access
    Macros That Work
    (University of Oregon, 1991-01) 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.
  • Thumbnail Image
    ItemOpen Access
    Revised 3.99 Report on the Algorithmic Language Scheme
    (University of Oregon, 2004-10) Clinger, William D.; Rees, Jonathan
    The report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form Ā· expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme. The introduction offers a brief history of the language and of the report. The first three chapters present the fundamental ideas of the language and describe the notational conventions used for describing the languageĀ· and for writing programs in the language. Chapters 4 and 5 describe the syntax and semantics of expressions, programs, and definitions. Chapter 6 describes Scheme's built-in procedures, which include all of the language's data manipulation and input/ output primitives. Chapter 7 provides a formal syntax for Scheme written in extended BNF, along with a formal denotational semantics. The report concludes with an example of the use of the language and an alphabetic index.