Communication, especially voice communication, continues to play an ever central role in improving business efficiency, customer service, and worker productivity. Technologies such as SIP and Web Services are transforming communication applications by providing primitives that can be integrated into business process flows. Meanwhile, enterprises present dynamic complex environments with strict requirements for communication solutions. In this talk, we examine the interplay between technologies and communication needs.

Abstract In this note, we show how a few UNIX™ commands can be combined to create a flexible reference assembler that automatically maintains the consistency of cross references in manuscripts. The reference assembler can be used in conjunction with any text formatter.

Article Free Access Share on An ideal model for recursive polymorphic types Authors: David MacQueen Bell Laboratories, Murray Hill, New Jersey Bell Laboratories, Murray Hill, New JerseyView Profile , Gordon Plotkin Department of Computer Science, University of Edinburgh, Edinburgh EH9 3J2 Department of Computer Science, University of Edinburgh, Edinburgh EH9 3J2View Profile , Ravi Sethi Bell Laboratories, Murray Hill, New Jersey Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1984 Pages 165–174https://doi.org/10.1145/800017.800528Online:15 January 1984Publication History 79citation712DownloadsMetricsTotal Citations79Total Downloads712Last 12 Months48Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A defining characteristic of “functional” specifications is the absence of assignments: updates of tables and data structures are expressed by giving the relationship between the new and old values. An obvious implementation allocates separate space for new and old values and may consume a lot of storage. However, even when updates of attributes like symbol tables are expressed functionally, we would like to avoid making copies of the symbol table during attribute evaluation. In other words, if possible, the implementation should have a single global copy of the table that is updated using assignments. Since the value of the global copy changes during computation, the order of evaluation has to be chosen carefully. In this paper, we partition attributes into classes, the problem being to determine if there exists an evaluation order that allows each class to share a global storage area. The solution extends to handle symbol tables for block structured languages.

Abstract Some parser generators allow the user to attach actions, consisting of executable code, to syntax rules. Actions are usually in the local programming language, so they are simply copied into the generated parser. However, we show two situations in which it is convenient to allow actions to be in a different notation. A preprocessor is used to translate such notations into the local programming language. A preprocessor must know where to find actions and how to translate them. We show how these two activities can be programmed separately. Often, the user only has to worry about the second part: once the parser generator is known, the placement of the actions is known as well, so routines for finding actions can be separately compiled and linked in. Examples in the paper are based on the parser generator Yacc, but the approach is not limited to Yacc, or even to parser generators. Certain compositions of syntax‐directed translations can be implemented by preprocessing actions.

The evaluation of anthmeuc expressions on both register-oriented and stack-oriented machines can be stud~ed using the same model because registers can be treated as a stack during the evaluation of express~on trees, without loss m code efficiency The machine model in this paper has a hardware stack m which all computatmns take place.Reg~ster-regmer and regmer-memory instructions are modeled by considering four possible instrucuons for each binary operator, depending on whether one or two operands are taken from the stack and on whether the left or the right operand ~s on top of the stack.There is a cost assocJated wtth each operation code, as well as costs for accessing a value in a register or in memory.The mtmmum cost of computing an expression tree ~s used to compare machines.The comparisons fall into two classes (1) By keeping the instruction set fixed, the effect of increasing the number of registers is studied.(2) Various machines are compared with a machine that has all four kinds of operation instructmns and an arbitrarily deep stack.As part of the framework that allows the comparisons to be performed, a parametenzed algonthm for determining the number of stores that must occur in an optimal computation is developed This algorithm forms the basis of an opttmal code generation algorithm.

A combmator called a pipe is proposed for combining functions in a hnear order.Examples suggest that semantic rules using pipes are easy to read and understand, even for readers with little knowledge of semantics The readability is a consequence ot the operational mtunion associated with pipes The operatJonal v~ew is that each function connected by a pipe is handed a finite sequence of values Each function takes zero or more arguments from the right end of the sequence, replaces the arguments by zero or more results, and passes the sequence to the next function The new idea is that a function may skip over some number of values before picking up its arguments.This approach Is suited to expressing the composition of operations on machine states in a programming language.Pipes allow continuation semantics to be written with direct operators instead of the operator having to worry about its continuation, the second function in a pipe is essentially a continuation of the first m connection is established between functions connected by pipes and more traditional continuation semantics.

This paper is a demonstration of a semantics-directed compiler generator.We focus on the part of a compiler between syntax analysis and code generation.A language is specified by adding semantic rules in a functional notation to the syntax of the language.Starting with a small sublanguage of while statements, statement constructs of the C programming language are added in stages.Using a small ad hoc code generator, a compiler is automatically constructed from the semantics.The semantic description is analogous to a syntax-directed construction of a flow diagram for a program.By analogy with grammars and parser generators, minimal knowledge of the underlying theory is required.For the control flow aspects of languages, efficient compilers can quickly be generated.

When several transactions read and write ~tems in a database, the question of consistency of the database arises.Consistency ~s maintained if transacUons are serial, the read and write acuons of a transacuon execute complete!ybefore the actions of the next transaction begin A particular history of interleaved read and write actions belonging to several transactions ~s correct if it ~s equivalent to a serial history.Since senahzablhty of hlstones is known to be NP-complete, subclasses of senahzable histories have been stu&ed.One such class consists of htstones senahzable in a strict sense, transacuons that are already m serial in a history must remain m the same relative order When there are no useless actions m a history, it is shown that strict sermlizabdity can be determined m polynomial time If useless actions are permitted, then strict serializabihty becomes NP-complete The above results apply to two-step transactions m which there ~s a read step followed by a wnte step Each step revolves some subset of the items m the database.W~th mulustep transactions stnct senahzabd~ty ~s NP-complete even ff there are no useless actions Categories and Subject Descriptors F.

Consider the connection between denotational semantics for a language with goto statements and flow diagrams for programs in such a language. The main point of interest is that the denotational semantics uses a recursively defined environment to give the meaning of labels, while a flow diagram merely has a jump to the appropriate program point. A simple reduction called “indirection elimination” strips away the environment from the denotational semantics and extracts an expression with cycles that is very close to the flow diagram of a program. The same idea applies to associating bodies with recursive procedures, or to any construct whose semantics is not wedded to the syntax. In addition to being a useful data structure and conceptual device, expressions with cycles are well defined mathematical objects—their semantics can be given by unfolding them into infinite structures that have been well studied. The practicality of the elimination of environments has been tested by constructing a trial implementation, which serves as the front end of a semantics directed compiler generator. The implementation takes a denotational semantics of a language and constructs a “black box” that maps programs in the language into an intermediate representation. The intermediate representation is a circular expression.

When several transactions (processes) read and write items in a database, the question of consistency of the database arises. Consistency is maintained if transactions are serial: all actions of a transaction execute completely before the actions of the next transaction begin. A particular history of interleaved actions belonging to several transactions is correct if it is equivalent to a serial history. We provide a natural framework for studying serializability that encompasses models that have been considered in the literature. A history is represented by a dag in which there is a vertex for each instantaneous value taken by an item in the database. The main tool for determining serializability are "exclusion rules" which determine implied orderings between vertices. For example, a vertex that uses a value must be serialized before the value is overwritten. An exclusion closure -- the result of applying the rules as long as possible -- can be constructed in time cubic in the number of vertices. Since determining serializability is NP-complete, exclusion closures cannot always decide serializability, but useful sufficient conditions can be proven. Exclusion closures allow the largest known classes of polynomially serializable histories to be properly extended. When studying serializability it is not necessary to work solely with the dag containing instantaneous values of all items. Three abstractions of the dag are presented which correspond to models of transactions and to "version graphs" in the literature. Since serializability of histories is known to be NP-complete, subclasses of serializable histories have been studied. One such class consists of histories serializable in a strict sense: transactions that are already in serial in a history must remain in the same relative order. When there are no useless actions in a history, strict serializability can be determined in polynomial time. If useless actions are permitted then strict serializability becomes NP-complete. The above results apply to two step transactions in which there is a read step followed by a write step, Each step involves some subset of the items in the database. With multistep transactions strict serializability is NP-complete even if there are no useless actions.

Given a sequence $n_1 , \cdots ,n_m $ of positive integers, what is the smallest number of additions needed to compute all m integers starting with 1? This generalization of the addition chain ($m = 1$) problem will be called the addition-sequence problem. We show that the sequence $\{ 2^0 ,2^1 , \cdots ,2^{n - 1} ,2^n - 1\} $ can be computed with $n + 2.13\sqrt n + \log n$ additions, and that $n + \sqrt n - 2$ is a lower bound. This lower bound result is applied to show that the addition-sequence problem is NP-complete.

Abstract A declaration mechanism is proposed that allows common type information to be factored into a type expression, yet allows related but distinct types to be declared together. The mechanism is a unification of declarations in Pascal and C. The choice of syntax is quite important. The proposed syntax uses a postfix operator for dereferencing pointers instead of the prefix operator * for pointer dereferencing in C.

On and off over the period of about a year I have worked on a semantic specification for the C programming language My objective was to construct a readable and precise specification of C, aimed at compiler writers, maintainers, and language pundits. This paper is a report on the project.

Let G be a directed graph such that for each vertex v in G, the successors of v are ordered Let C be any equivalence relation on the vertices of G.The congruence closure C* of C is the finest equivalence relation containing C and such that any two vertices having corresponding successors equivalent under C* are themselves equivalent under C* Efficient algorithms are described for computing congruence closures in the general case and in the following two special cases.0) G under C* is acyclic, and (it) G is acychc and C identifies a single pair of vertices.The use of these algorithms to test expression eqmvalence (a problem central to program verification) and to test losslessness of joins in relational databases is described KEY WORDS AND PHRASES common subexpresslon, congruence closure, decision procedure, expression equivalence, graph algorithm, lossless join, relational database, theory of equality, unification, uniform word problem CR CATEGORIES 4 12, 4.33, 4 34, 5.24, 5 25, 5 32

Previous results have shown that it ~s easy to generate optimal code from express,on trees, and that optimal code generauon becomes very difficult ff arbitrary common subexpress,ons are handled In this paper a class of expressions containing restricted common subexpressions from which optimal code can be generated effictentty is studied.These expressions are represented by a class of series-parallel graphs, which the authors call collapsible graphs, that mchide trees and are general enough to permit large common subexpresslons, but from which optmml code can be generated m polynomml time for a class of stack machines KEY WORDS AND PHRASES" reg,ster allocaUon, code generation, polynomml algorithm, series-parallel graphs, common subexpresslons, stack machines CR CATEGORIES. 4 12, 5.25 15, lq.Elaborating on (b) above, Bruno and Sethi [11] show that the problem of generating optimal code for a one-register machine is NP-complete.Aho et al. [5] add that even when all common subexpressions have exactly one operaUon, optimal code generation is NPcomplete for a one-register machine and also for an infinite-register machine. 1 Since the stack machines we consider are a generalization of one-register machines, the NP-completeness results from [5, 11] carry-over to stack machines.

The problem of transforming one semantic description for a language into another related description of the same language is considered.Since direct and continuation semantics have been studied in some detail, they are obvious test-beds for suggesting the problems that might be encountered in the process.One of the problems is that the semantic objects in two descriptions of a language may be quite dissimilar.For example, function values of procedures in direct semantics are quite different from function values in continuation semantics.MiMe and Reynolds have defined predicates which can be used to relate the two kinds of function values.Starting with such predicates, transformations are defined, and it is then shown that the transformations preserve the predicates.The transformations are used to construct continuation semantics, starting from a direct semantics of a language with procedures called by value.

The classical common subexpression problem in program optimization is the detection of identical subexpressions. Suppose we have some extra information and are given pairs of expressions ei1=ei2 which must have the same value, and expressions fj1≠fj2 which must have different values. We ask if as a result, h1=h2, or h1≠h2. This has been called the uniform word problem for finitely presented algebras, and has application in theorem-proving and code optimization. We show that such questions can be answered in O(nlogn) time, where n is the number of nodes in a graph representation of all relevant expressions. A linear time algorithm for detecting common subexpressions is derived. Algorithms which process equalities, inequalities and deductions on-line are discussed.

Stratght line programs with assignment statements involving both simple and array variables are considered Two such programs are equivalent if they compute the same values as a function of the inputs.Testing the equivalence of array programs ts shown to be NP-hard If array variables are updated but never subsequently referenced, equivalence can be tested in polynomial time Programs without array varmbles can be tested for equivalence in expected linear t~me

Condmonal expressions of the form "if E=F then G else H," where E,F,G,H may themselves be such expressions, have long been used to describe the semantics of assignments.We consider the problem of deciding if two nested condmonals of the above form compute the same values Three transformahons are used to solve the problem A dtstrtbutwe transformation converts any conditional to the sampler form if A =B then G else H, where A and B are variables rather than expressions.An trnphed test transformation finds all tests in subexpresslons whose outcome as Jmphed by prevtous tests.Finally, the useless test transformation is used to reduce expressions of the form if A =B then C else C to C When all tests are between variables and the expressions are represented by trees, then equivalence of expressions can be tested in polynomial time The remaining cases have been shown elsewhere to be NP-hard

Suppose you are approached by a computer designer who wants to select a machine architecture and instruction set that is desirable from a compiler writers standpoint. What would you recommend, and why? We give a limited answer to the above question. We focus on the computation of arithmetic expressions like a−b+c. When computing a−b we need different instructions depending on where a and b are to be found. On a programmable calculator for example, a or b may be on the stack, or stored in some memory register. We also need instructions that copy values from one place to another. Algorithms that generate code for arithmetic expressions tend to treat general purpose registers as a stack. Moreover, results about machines that perform all arithmetic in a hardware stack are directly applicable to machines with general purpose registers. We therefore start our study of instruction sets by looking at stack machines. We compare machines based on the number of instructions needed to compute a given expression. We then turn to algorithms that generate optimal programs for computing expressions on the various machines.

Trle structures are a convenient way of indexing files in which a key consists of a number of attributes Records correspond to leaves in the trle Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values The size of a trle for a file depends on the order in which attributes are tested It is shown that determining minimal size tries IS an NP-complete problem for several variants of tries and that, for tries m which leaf chains are deleted, determining the trie for which average access time is minimal is also an NP-complete problem These results hold even for files in which attribute values are chosen from a binary or ternary alphabet KE] WORDS AND PHRASES reformation retrieval, trle indexes, trte size, average search time, complexity CR CATEGORIES 3 74, 4 33, 5 25

Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of different speeds. The new algorithm is optimal for independent tasks on any number of processors and for arbitrary task systems on two processors, but not on three or more processors, even for trees. By taking the algorithm as a heuristic onmprocessors and using the ratio of the lengths of the constructed and optimal schedules as a measure, an upper bound on its performance is derived in terms of the speeds of the processors. It is further shown that 1.23√mis an upper bound over all possible processor speeds and that the 1.23√mbound can be improved at most by a constant factor, by giving an example of a system for which the bound 0.35√mcan be approached asymptotically.

Coffman and Graham give an algorithm to schedule unit execution time task systems nonpreemptively. On two processors, their algorithm is optimal. We show that in general, if $\omega$ is the length of a schedule produced by their algorithm and $\omega_0$ the length of an optimal schedule, then $\omega / \omega_{0} \leqq 2 - 2/m$, where m is the number of processors. The preemptive equivalent of the above algorithm has been considered by Muntz and Coffman. Again we show that the ratio of the lengths of theirs and an optimal schedule is bounded by $2 - 2/m$. In both the nonpreemptive and the preemptive cases there exist task systems for which the ratio $2 - 2/m$ can be approached arbitrarily closely. On a small number of machines, $2 - 2/m$ is not too far from 1. In particular, as noted above, on two machines the ratio is 1.

Trie structures are a convenient way of indexing files in which keys are specified by values of attributes. Records correspond to leaves in the trie. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trie for a file depends on the order in which attributes are tested. We show that determining minimal size tries is an NP-complete problem for several variants of tries. For tries in which leaf chains are deleted we show that determining the trie for which average access time is minimal is also an NP-complete problem. Our results hold even for files in which attribute values are chosen from a binary or ternary alphabet.

Straight line programs in which array elements can be referenced and set are considered. Two programs are equivalent if they compute the same expression as a function of the inputs. Testing the equivalence of programs with arrays is shown to be NP-complete, while programs without arrays can be tested for equivalence in linear time. Equivalence testing takes polynomial time when programs have either no references or no assignments to array elements.

In this paper we shall generalize Graham's result so as to include a parameter characterizing the number of tasks assigned to processors by the LPT rule. The new result will show that the worst-case performance bound for LPT sequencing approaches unity approximately as 1+1/k, where k is the least number of tasks on any processor, or where k is the number of tasks on a processor whose last task terminates the schedule. Thus, we shall have a result very similar to the parameterized bounds for bin-packing heuristics [JDUGG]. We shall also obtain out of the analysis an alternate proof of Graham's result.

The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

This paper considers simple, LISP-like languages for the recursive definition of functions. We focus on the connections between formal computation rules for calculation with recursive definitions, and the mathematical semantics of such definitions. A computation rule is correct when it is capable of computing the least fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.

Consider a directed acyclic graph (dag) D with n nodes and e edges. D represents a task system; a node corresponds to a task, and an edge $(x,y)$ means that task x must be finished before task y can be started. We shall restrict attention to systems in which all tasks require the same processing time. Coffman and Graham give an algorithm for determining nonpreemptive schedules on two processors for such systems. The first part of their algorithm assigns unique labels to nodes. The second part uses these labels to construct a list schedule (in the sense of Graham). The time taken for each part is $O(n^2 )$. We give an algorithm to determine the labeling in $O(n + e)$ steps. Similar algorithms have independently been devised to test undirected graphs for chordality. We give a second algorithm to construct a schedule from the labeling in $O(n\alpha (n) + e)$ steps. $\alpha (n)$ is an almost constant function of n.

This paper considers simple LISP-like languages for the recursive definition of functions, focusing upon the connections between formal computation rules for calculation and the mathematical semantics of recursive definitions. A computation rule is correct when it is capable of computing the minimal fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.

Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors. A variation of their algorithm is adapted for processors of different speeds. The algorithm is shown to be optimal on two processors for arbitrary task systems, but not on three or more processors even for trees. Taking the algorithm as a heuristic on m processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, we show that, on identical processors, its performance is bounded by 2 - 2/m. Moreover 2 - 2/m is a best bound in that there exist task systems for which this ratio is approached arbitrarily closely. On processors of different speeds, we derive an upper bound of its performance in terms of the speeds of the given processor system and show that @@@@1.5m is an upper bound over all processor systems. We also give an example of a system for which the bound @@@@m/2 @@@@2 can be approached asymptotically, thus establishing that the @@@@1.5m bound can at most be improved by a constant factor.

No abstract available.

The search for efficient register allocation algorithms dates back to the time of the first FORTRAN compiler for the IBM 704. The model we use in this paper is a single processor with an arbitrarily large number of general registers. The objective is to use as few registers as possible, under the,constraint that no stores into memory are permitted. The programs under consideration are sequences of assignment instructions. We show that, given a program and an integer k, determining if the program can be computed using k registers is polynomial complete. It should be noted that k can be any integer.

A striking example of practical tradeoffs between storage space and execution time is provided by the IBM 1401 Fortran compiler.

The central notion in a replacement system is one of a transformation on a set of objects. Starting with a given object, in one “move” it is possible to reach one of a set of objects. An object from which no move is possible is called irreducible. A replacement system is Church-Rosser if starting with any object a unique irreducible object is reached. A generalization of the above notion is a replacement system ( S , ⇒, ≡), where S is a set of objects, ⇒ is a transformation, and ≡ is an equivalence relation on S . A replacement system is Church-Rosser if starting with objects equivalent under ≡, equivalent irreducible objects are reached. Necessary and sufficient conditions are determined that simplify the task of testing if a replacement system is Church-Rosser. Attention will be paid to showing that a replacement system ( S , ⇒, ≡) is Church-Rosser using information about parts of the system, i.e. considering cases where ⇒ is ⇒ 1 ∪ ⇒ 2 , or ≡ is (≡ 1 ∪ ≡ 2 ) * .

In this paper we study the problem of scheduling a set of independent tasks on m ≥ 1 processors to minimize the mean finishing-time (mean time in system). The importance of the mean finishing-time criterion is that its minimization tends to reduce the mean number of unfinished tasks in the system. In the paper we give a reduction of our scheduling problem to a transportation problem and thereby extend the class of known non enumerative scheduling algorithms [1]. Next we show that the inclusion of weights (weighted mean finishing-time) complicates the problem and speculate that there may be no non enumerative algorithm for this case. For the special case of identical processors we study the maximum finishing-time properties of schedules which are optimal with respect to mean finishing-time. Finally we give a scheduling algorithm having desirable properties with respect to both maximum finishing-time and mean finishing-time.

The search for efficient algorithms for register allocation dates back to the time of the first Fortran compiler for the IBM 704. Since then, many variants of the problem have been considered; depending on two factors: (1) the particular model for registers, and (2) the definition of the term “computation of a program” e.g. whether values may be computed more than once. We will show that several variants of the register allocation problem for straight line programs are polynomial complete. In particular we consider, (1) the case when each value is computed exactly once, and (2) the case when values may be recomputed as necessary. The completeness of the third problem considered is surprising. A straight line program starts with a set of initial values, and computes intermediate and final values. Suppose, for each value, the register that value must be computed into is preassigned. Then, (3) the problem of determining if there is a computation of the straight line program, that computes values into the assigned registers, is polynomial complete.

Straight line programs are essentially sequences of assignment statements. A general program consists of straight line segments with flow of control between these segments. The interfaces between a straight line segment and the rest of the program place constraints on register allocations for the segment. These constraints may render a register allocation for a straight line program unrealizable. An algorithm is given to determine if a register allocation for a straight line program is realizable. It is shown that the algorithm takes 0(n3) steps, where n is the number of statements in the program. An unrealizable assignment may be made realizable by introducing stores into memory at appropriate points. It is shown how the minimum number of such stores may be found.

The problem of evaluating arithmetic expressions on a machine with N ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An algorithm for evaluation of expressions under this assumption is proposed, and it is shown to take the shortest possible number of instructions. It is then assumed that certain operators are commutative or both commutative and associative. In this case a procedure is given for finding an expression equivalent to a given one and having the shortest possible evaluation sequence. It is then shown that the algorithms presented here also minimize the number of storage references in the evaluation.