September 1981 - Vol. 24 No. 9
Features
The interface between a person and a computer can be looked at from either side. Programmers tend to view it from the inside; they consider it their job to defend the machine against errors made by its users. From the outside, the user sees his/her problems as paramount. He/she is often at odds with this complex, inflexible, albeit powerful tool. The needs of both people and machines can be reconciled; users will respond more efficiently and intelligently if they receive meaningful feedback. A “user-friendly” algorithm that covers a wide range of interactive environments and is typical of most operating systems and many application programs is presented.
The Cornell program synthesizer: a syntax-directed programming environment
Programs are not text; they are hierarchical compositions of computational structures and should be edited, executed, and debugged in an environment that consistently acknowledges and reinforces this viewpoint. The Cornell Program Synthesizer demands a structural perspective at all stages of program development. Its separate features are unified by a common foundation: a grammar for the programming language. Its full-screen derivation-tree editor and syntax-directed diagnostic interpreter combine to make the Synthesizer a powerful and responsive interactive programming tool.
An on-line algorithm for fitting straight lines between data ranges
Applications often require fitting straight lines to data that is input incrementally. The case where a data range [&agr;k, &ohgr;k] is received at each tk, t1 < t2 < … tn, is considered. An algorithm is presented that finds all the straight lines u = mt + b that pierce each data range, i.e., all pairs (m, b) such that &agr;k ≤ mtk + b ≤ &ohgr;k for k = 1, … , n. It may be that no single line fits all the ranges, and different alternatives for handling this possibility are considered. The algorithm is on-line, producing the correct partial result after processing the first k ranges for all k < n. For each k, the set of (m, b) pairs constitutes a convex polygon in the m-b parameter space, which can be constructed as the intersection of 2k half-planes. It is shown that the O(n logn) half-plane intersection algorithm of Shamos and Hoey can be improved in this special case to O(n).
Comparison of synonym handling and bucket organization methods
A theoretical description of the access times required in open addressing and external chaining is given. Values are calculated for different record and bucket sizes and load factors, and the corresponding values for the two methods are compared. Practical guidelines for determining bucket sizes and load factors are presented. It is proved that open addressing is almost always superior to external chaining and the optimal bucket size is between 1 and 4.
On sharing secrets and Reed-Solomon codes
Shamir's scheme for sharing secrets is closely related to Reed-Solomon coding schemes. Decoding algorithms for Reed-Solomon codes provide extensions and generalizations of Shamir's method.
Comments on price/performance patterns of U. S. computer systems
Several errors are noted in the formulation of econometric models describing computer price/performance patterns. An alternative model is presented which shows the effects of technological advances and computer size on price reduction.
Automatic extension of an ATN knowledge base
A computer program is described that acquires much of its knowledge from conversations among operators on Morse code radio networks. The system consists of a learning component and a language understander. The learning component extends a ‘core’ augmented transition network (ATN) knowledge base by generalizing from sentences taken from scripts of actual conversations. The extensions enable the understanding component to process a large number of sentences that are syntactically and semantically similar to the examples.
An abstract model of a processor is presented informally. The model can be used by itself to abstractly describe algorithms, or with a direct implementation to write and run programs, or as the foundation of a programming language. In the last case, a translator allows higher level descriptions of algorithms for the model.
Shuffle languages, Petri nets, and context-sensitive grammars
Flow expressions have been proposed as an extension of the regular expressions designed to model concurrency. We examine a simplification of these flow expressions which we call shuffle expressions. We introduce two types of machines to aid in recognizing shuffle languages and show that one such machine may be equivalent to a Petri Net. In addition, closure and containment properties of the related language classes are investigated, and we show that one machine type recognizes at least a restricted class of shuffle languages. Finally, grammars for all shuffle languages are generated, and the shuffle languages are shown to be context-sensitive.
