COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input macro[tur,cjs]
C00006 00003	\bite {\bf PVG-16 (STAN-CS-80-789):}
C00008 00004	\bite {\bf STAN-CS-80-790:}
C00010 00005	\bite {\bf STAN-CS-80-791 (CSL TR-166):}
C00014 00006	\bite {\bf STAN-CS-80-792 (CSL TR-167):}
C00016 00007	\bite {\bf HPP-80-3 (STAN-CS-80-793):}
C00018 00008	\bite {\bf HPP-80-4 (STAN-CS-80-794):}
C00019 00009	\bite {\bf STAN-CS-80-795:}
C00020 00010	\bite {\bf AIM-335 (STAN-CS-80-796):}
C00022 00011	\bite {\bf STAN-CS-80-797:}
C00024 00012	\bite {\bf STAN-CS-80-798:}
C00027 00013	\bite {\bf STAN-CS-80-799 (SLAC-PUB-2504):}
C00029 00014	\bite {\bf STAN-CS-80-800:}
C00030 00015	\bite {\bf 13:}
C00031 00016	\bite {\bf 14:}
C00032 00017	\bite {\bf 15:}
C00033 00018	\bite {\bf 16:}
C00034 00019	\bite {\bf 17:}
C00035 ENDMK
C⊗;
\input macro[tur,cjs]
\chapter{Stanford University Most Recent Computer Science Reports - 1980}{List Number 8, April}

Listed here are abstracts of the most recent reports published by the
Depart-ment of Computer Science at Stanford University.

{\bf To Request Reports:} Check the appropriate places on the enclosed order
form, and return the entire order form page (including mailing label) by
June 30, 1980.  In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first served basis.  If the code
(FREE) is printed on your mailing label, you will not be charged for hardcopy.
This exemption from payment is limited primarily to libraries.  (The costs
shown include all applicable sales taxes.  {\ic Please send
no money now, wait until you get an invoice}.)

{\bf Alternatively:} Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after the ``{\ic Most Recent CS Reports}'' listing) to 
{\ic National
Technical Information Service}, 5285 Port Royal Road, Springfield, Virginia 22161.
Stanford Ph.D. theses are available from {\ic University Microfilms}, 300 North
Zeeb Road, Ann Arbor, Michigan 48106.
$$\section\quad \section\quad \section\quad \section\quad \section\quad$$

\bite {\bf PVG-16 (STAN-CS-80-789):}
{\ic Ada Exceptions: Specification and Proof Techniques} by
D. C. Luckham and W. Polak,
19 pages, February 1980.  Cost:  $\$2.25$

A method of documenting exception propagation and handling in Ada programs
is proposed.  Exception propagation declarations  are introduced as a  new
component of  Ada specifications.   This  permits documentation  of  those
exceptions that can be propagated by a subprogram.  Exception handlers are
documented by entry assertions.  Axioms and proof rules for Ada exceptions
are given.  These rules are simple extensions of previous rules for Pascal
and define an  axiomatic semantics of  Ada exceptions.  As  a result,  Ada
programs specified according to the method can be analysed by formal proof
techniques for consistency with their specifications, even if they  employ
exception propagation and handling to achieve required results (i.e.   non
error situations).  Example verifications are given.

\bite {\bf STAN-CS-80-790:}
{\ic Databases in Healthcare} by
Gio Wiederhold,
76 pages, March 1980.  Cost: $\$3.85$

This report defines database design and implementation technology as
applicable to healthcare.  The relationship of technology to various
healthcare settings is explored, and the effectiveness on healthcare
costs, quality and access is evaluated.  A summary of relevant development
directions is included

Detailed examples of 5 typical applications (public health, clinical
trials, clinical research, ambulatory care, and hospitals) are appended.
There is an extended bibliography.

\bite {\bf STAN-CS-80-791 (CSL TR-166):}
{\ic MAINSAIL Language Manual} by
Clark R. Wilcox, Mary L. Dageforde, and Gregory A. Jirak,
247 pages, March 1980.  Cost: $\$8.65$

MAINSAIL is a programming system designed for the development of large,
portable software systems.  The compiler and runtime system are themselves
written in MAINSAIL, so that only code generators and a few well-defined 
machine and operating-system dependent  routines need be rewritten to move
MAINSAIL to a new environment.  The language provides single and double
precision integer, floating point and ``bits'' data types, as well as 
descriptor-based strings, record pointers, and low-level data types ``address''
and ``charadr'' (character address).  All data structures are dynamically
allocated and automatically garbage collected when necessary to reclaim
storage space.  A novel approach to modules and intermodule communications
supports modules which are position independent, self loading and dynamically
linked, thereby avoiding any reliance on machine-dependent loaders and linkers.
A machine-independent file system model is supported across all implementations,
so that portable programs may utilize sequential and random file access
for both text and ``binary'' data.  An extensive set of compiletime features
including macros, source file inclusion, symbol table save and restore and
conditional compilation support the development of software systems which
may consist of hundreds of modules.  Low-level features, such as explicit
memory allocation, deallocation and access, and in-line assemby code,
provide the ability to bypass the MAINSAIL data structures when necessary.
Such features have made it possible to write even the machine-dependent
parts of the runtime system in MAINSAIL.  An extensive set of runtime
modules are provided as part of the standard environment, including
mathematical routines, file manipulation, i/o, conversions, string
manipulation, character handling, and low-level memory allocation and access.

\vfill
\endpartx
\bite {\bf STAN-CS-80-792 (CSL TR-167):}
{\ic MAINSAIL Implementation Overview} by
Clark R. Wilcox, Mary L. Dageforde, and Gregory A. Jirak,
70 pages, March 1980.  Cost: $\$3.70$

The MAINSAIL programming language and the supporting implementations have
been dveloped over the past five years as an integrated approach to a viable
machine-independent system suitable for the development of large, portable
programs.  Particular emphasis has been placed on minimizing the effort
involved in moving the system to a new machine and/or operating system.
For this reason, almost all of the compiler and runtime support is written
in MAINSAIL, and is utilized in each implementation without alteration.
This use of a high-level language to support its own implementation has
proved to be a significant advantage in terms of documentation and
maintenance, without unduly affecting the execution speed.  This paper gives
an overview of the compiler and runtime implementation strategies, and
indicates what an implementation requires for the machine-dependent and
operating-system-dependent parts.

\bite {\bf HPP-80-3 (STAN-CS-80-793):}
{\ic Representation of Knowledge} by
Avron Barr and James Davidson,
90 pages, March 1980.  Available in microfiche only.

This report is the section of the Handbook of Artificial Intelligence about
knowledge representation research.  The Handbook is a compendium of articles about
AI ideas, techniques, and systems intended for non-AI scientists, engineers, and
students.  The material in this report discusses the problems addressed in
knowledge representation research in AI and suggests some ways of comparing
the various representation schemes.  Additional articles describe the AI
representation techniques:  logic, procedural representations, semantic nets,
production systems, direct (analogical) representations, semantic primitives, and
frames.  The Handbook will be published later in 1980.  We have distributed this
manuscript before publication with the hope of obtaining comments and suggestions
from the AI community.

\bite {\bf HPP-80-4 (STAN-CS-80-794):}
{\ic The Role of Plans in Intelligent Teaching Systems} by
Michael Genesereth,
    pages.  Cost: $\$ $

\bite {\bf STAN-CS-80-795:}
{\ic The Letter S} by
Donald E. Knuth, 33 pages, April 1980.  Cost: $\$2.65$

This expository paper explains how the problem of drawing the letter S leads to
interesting problems in elementary calculus and analytic geometry. It also
gives a brief introduction to the author's METAFONT language for alphabet design.

\bite {\bf AIM-335 (STAN-CS-80-796):}
{\ic Essential E} by Arthur Samuel, 33 pages, March 1980.  Cost: $\$2.65$

This is an introductory manual describing the display-oriented text editor
E that s available on the Stanford A.I. Laboratory PDP-10 computer.  The
present manual is intended to be used as an aid for the beginner as well
as for experienced computer users who either are unfamiliar with the E
editor or use it infrequently.  Reference is made to the two on-line manuals
that help the beginner to get started and that provide a complete description
of the editor fr the experienced user.

E is commonly used for writing computer programs and for preparing reports
and memoranda.  It is not a document editor, although it does provide some
facilities for getting a document into a pleasing format.  The primary emphasis
is that of speed, both in terms of the number of key strokes required of the user
and in terms of the demands made on the computer system.  At the same time, E
is easy to learn and it offers a large range of facilities that are not available
on many editors.

\bite {\bf STAN-CS-80-797:}
{\ic Read-Only Transactions in a Distributed Database}
by Hector Garcia-Molina and Gio Wiederhold, 25 pages, April 1980.
Cost: $\$2.40$

A read-only transaction or query is a transaction which does not modify
any data.  Read-only transactions could be processed with general transaction
processing algorithms, but in many cases it is more efficient to process
read-only transactions with special algorithms which take advantage of the
knowledge that the transaction only reads.  This paper defines the various
consistency and currency requirements that read-only transactions may have.
The processing of the different classes of read-only transactions in a distributed
database is discussed.  The concept of {\ic R} insularity is introduced to
characterize both the read-only and update algorithms.  Several simple update
and read-only transaction processing algorithms are presented to illustrate
how the query requirements and the update algorithms affect the read-only
transaction processing algorithms.

\bite {\bf STAN-CS-80-798:}
{\ic The Compilation of Regular Expressions into Integrated Circuits}
by Robert W. Floyd and Jeffrey D. Ullman, 28 pages, April 1980.
Cost: $\$2.50$

We consider the design of integrated circuits to implement arbitrary regular
expressions.  In general, we may use the McNaughton-Yamada algorithm to convert
a regular expression of length $n$ into a nondeterministic finite automaton with
at most $2n$ states and $4n$ transitions.  Instead of converting the
nondeterministic device to a deterministic one, we propose two ways of 
implementing the nondeterministic device directly.  First, we could produce
a PLA (programmable logic array) of approximate dimensions $4n \times 4n$
by representing the states directly by columns, rather than coding the states
in binary.  This approach, while theoretically suboptimal, makes use of
carefully developed technology and, because of the care with which PLA
implementation has been done, may be the preferred technique in many real
situations.  Another approach is to use the hierarchical structure of the
automation produced from the regular expression to guide a hierarchical
layout of the circuit.  This method produces a circuit
$0(\sqrt{n})$ on a side and is, to within a constant factor, the best that
can be done in general.

\bite {\bf STAN-CS-80-799 (SLAC-PUB-2504):}
{\ic Multidimensional Additive Spline Approximation}
by Jerome H. Friedman, Eric Grosse, and Werner Stuetzle, 22 pages, May 1980.
Available in microfiche only.

We describe an adaptive procedure that approximates a function of many
variables by a sum of (univariate) spline functions $s↓m$ of selected linear
combinations $a↓m \mult x$ of the coordinates
$$\phi(x) = \sum↓{1≤m≤M} s↓m(a↓m \mult x).$$
The procedure is nonlinear in that not only the spline coefficients but also
the linear combinations are optimized for the particular problem.  The sample
need not lie on a regular grid, and the approximation is affine invariant,
smooth, and lends itself to graphical interpretation.  Function values,
derivatives, and integrals are cheap to evaluate.

\bite {\bf STAN-CS-80-800:}
{\ic Deciphering a Linear Congruential Encryption}
by Donald E. Knuth, 10 pages, April 1980.  Cost: $\$2.00$

It is shown that the multiplier, increment, and starting value of a linear
congruential random number generator on a binary computer can be deduced
from the leading bits of the ``random'' numbers generated.

\bite {\bf 13:}

\bite {\bf 14:}

\bite {\bf 15:}

\bite {\bf 16:}

\bite {\bf 17:}
$$\section\quad \section\quad \section\quad \section\quad \section\quad$$

% ∞∞∞∞∞∞∞∞∞
\vfill\end
% ∞∞∞∞∞∞∞∞∞