Abstractions and algorithms are at the heart of computational thinking. In this talk I will discuss the evolution of the theory and practice of programming language and compiler design through the lens of computational thinking. Many of the key concepts in this area were introduced at the ACM Symposium on the Theory of Computing.

This research explores the psychology of programming and the pedagogical environment in a certificate granting urban immigrant engineer retraining program in New York City. The program is aimed at teaching under-represented immigrant engineer students to learn how to program in the Java programming language. The programming concepts and the fostered pedagogical environment were implemented in three-hour evening sessions over 15 weeks in which the students were encouraged to develop programming communities while working on computational thinking concept strands. The research findings that we report are threefold. First, we report on how we fostered building programming concepts into the curriculum into a set of activities specifically designed for an immigrant engineer retraining program with students ranging in backgrounds. We found that at that the program curriculum must be flexible enough for student learning regardless of the fact that a student may miss sessions. Second, we report on how an effective pedagogical environment, which fosters student-centered learning, was promoted so that the students could construct their own meanings of the programming concepts. Third, we report on implementation strategies unique to a retraining program, such as specific environmental constraints as well as how sessions were partitioned into components that fostered computational thinking while learning Java. Our findings provide unique insights into intervention constraints for an urban retraining program which can be used to guide and inform further retraining computer learning program research.

La presente investigación tiene como propósito establecer cómo un material educativo digital (MED), aporta a mejorar las habilidades en el desarrollo de algoritmos con problemas matemáticos, pertenecientes a una parte operativa del pensamiento computacional, en estudiantes de primer semestre de la materia lógica de programación del Instituto Colombiano de Aprendizaje ¿INCAP¿. Para el estudio se diseñó e implemento el MED ¿Evolución,¿ conformado por retos aritméticos y algorítmicos. Mediante la metodología de estudio de caso, se evidencia que los participantes no cuentan con suficientes bases matemáticas y/o pensamiento algorítmico necesarios para solucionar los retos planteados. Se encontró que al ejecutar reiterativamente un reto, los participantes no solo apropian las operaciones matemáticas básicas, sino que además logran dar solución a los algoritmos utilizados en el MED, ratificando la potencialidad de las TIC como herramientas mediadoras que permiten motivar y mejorar el aprendizaje.

The concern location problem is to identify the source code within a program related to the features, requirements, or other concerns of the program. This problem is central to program development and maintenance. We present a new technique called prune dependency analysis that can be combined with existing techniques to dramatically improve the accuracy of concern location. We developed CERBERUS, a potent hybrid technique for concern location that combines information retrieval, execution tracing, and prune dependency analysis. We used CERBERUS to trace the 360 requirements of RHINO, a 32,134 line Java program that implements the ECMAScript international standard. In our experiment, prune dependency analysis boosted the recall of information retrieval by 155% and execution tracing by 104%. Moreover, we show that our combined technique outperformed the other techniques when run individually or in pairs.

There is a growing consensus that crosscutting concerns harm code quality. An example of a crosscutting concern is a functional requirement whose implementation is distributed across multiple software modules. We asked the question, "How much does the amount that a concern is crosscutting affect the number of defects in a program?" We conducted three extensive case studies to help answer this question. All three studies revealed a moderate to strong statistically significant correlation between the degree of scattering and the number of defects. This paper describes the experimental framework we developed to conduct the studies, the metrics we adopted and developed to measure the degree of scattering, the studies we performed, the efforts we undertook to remove experimental and other biases, and the results we obtained. In the process, we have formulated a theory that explains why increased scattering might lead to increased defects.

With N routers in a network running the open shortest path first (OSPF) routing protocol a network topology update can generate on the order of N/sup 2/ LSA packets. This phenomenon, known as the LSA N-squared problem, severely degrades network performance and scalability. Hierarchical OSPF network architectures have been proposed to reduce the number of link state advertisements (LSA) that are generated by a network topology update. We show that equal-size areas minimize the number of LSAs. Then we derive the optimal number of areas and the size of areas to create the network producing the minimal number of LSAs. Finally we show that the optimal network architecture reduces the number of LSAs from O(N/sup 2/) to O(/sup 3//spl radic/(N/spl middot/N)).

This paper discusses some of the major technical obstacles standing in the way of achieving cost-effective universal access to multimedia information stored in globally distributed knowledge repositories.Opportunities for contributions from the database research community are highlighted.

The international telecommunications system is the world's largest distributed computing system, offering a wide range of services and service features.Telecommunications service providers are eager to offer new services on this infrastructure, but the development of these new services is hampered by interactions of the service features among the different services.Undetected and undesirable feature interactions cause confusion and dissatisfaction among the users of services and add delay and expense to the development and deployment of new services.This panel reviews the progress that has been made in anticipating and controlling undesirable feature interactions in telecommunications services.This paper sets the stage by discussing the impact of the feature interaction problem on the different phases of the software development lifecycle.

A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing.>

Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help construct efficient code generators. Twig transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming. Twig has been used to specify and construct code generators for several experimental compilers targeted for different machines.

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.

We present a family of data structures that can process a sequence of insert, delete, and lookup instructions such that each lookup and deletion is done in constant worst-case time and each insertion is done in constant expected time. The amount of space used by each data structure is proportional to the maximal number of elements that need to be stored at any moment in time.

We show that tree pattern matching has significant advantages in the specification and implementation of efficient code generators. We present a top-down tree-matching algorithm that is particularly well suited to code generation applications. Finally, we present a new back-end language that incorporates tree pattern matching with dynamic programming into a uniform framework for the specification and implementation of efficient code generators.

Several papers have recently dealt with techniques for proving area-time lower bounds for VLSI computation by “crossing sequence” methods. A number of natural questions are raised by these definitions.

We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem arising in the theory of relational databases.

Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-phone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved.

We consider the question of how powerful a relational query language should be and state two principles that we feel any query language should satisfy. We show that although relational algebra and relational calculus satisfy these principles, there are certain queries involving least fixed points that cannot be expressed by these languages, yet that also satisfy the principles. We then consider various extensions of relational algebra to enable it to answer such queries. Finally, we discuss our extensions to relational algebra in terms of a new programming language oriented model for queries.

Many database queries can be formulated in terms of expressions whose operands represent tables of information (relations) and whose operators are the relational operations select, project, and join. This paper studies the equivalence problem for these relational expressions, with expression optimization in mind. A matrix, called a tableau, is proposed as a natural representative for the value of an expression. It is shown how tableaux can be made to reflect functional dependencies among attributes. A polynomial time algorithm is presented for the equivalence of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.

Abstract This paper describes the design and implementation of awk, a programming language which searches a set of files for patterns, and performs specified actions upon records or fields of records which match the patterns. Awk makes common data selection and transformation operations easy to express; for example, is a complete awk program that prints all input lines whose length exceeds 72 characters. The program prints each input line with the first field replaced by its logarithm. The program prints all lines in which the first field is different from the first field of the previous line. Patterns may include boolean combinations of regular expressions and of relational operators on strings, numbers, fields, variables, and array elements. Actions may include: the same matching constructions as in patterns; arithmetic and string expressions and assignments; if‐else, while, and for statements; formatted output; and multiple output streams.

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is lossless ) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

The design of several database query languages has been influenced by Codd's relational algebra. This paper discusses the difficulty of optimizing queries based on the relational algebra operations select, project, and join. A matrix, called a tableau, is proposed as a useful device for representing the value of a query, and optimization of queries is couched in terms of finding a minimal tableau equivalent to a given one. Functional dependencies can be used to imply additional equivalences among tableaux. Although the optimization problem is NP-complete, a polynomial time algorithm exists to optimize tableaux that correspond to an important subclass of queries.

This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields. A partial-match query is a specification of values for zero or more fields of a record, and the answer to a query is a listing of all records in the file whose fields match the specified values. A design is considered in which the file is stored in a set of bins. A formula is derived for the optimal number of bits in a bin address to assign to each field, assuming the probability that a given field is specified in a query is independent of what other fields are specified. Implications of the optimality criterion on the size of bins are also discussed.

Many useful database queries can be formulated in terms of expressions whose operands are relations and whose operators are the relational operations select, project, and join. This paper investigates the computational complexity of optimizing relational expressions of this form under a variety of cost measures. A matrix, called a tableau, is proposed as a conventient representative for the value of an expression. Functional dependencies can be used to imply additional equivalences among tableaux. The optimization problem is shown to be NP-complete, but we can give a polynomial time algorithm to optimize tableaux that correspond to an important subclass of expressions.

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, not all joins are semantically meaningful. This paper gives an efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. Similar techniques also apply to the case where data dependencies are multivalued.

Previous work on optimal code generation has usually assumed that the underlying machine has identical registers and that all operands fit in a single register or memory location. This paper considers the more realistic problem of generating optimal code for expressions involving single and double length operands, using several models of register-pair machines permitting both single and double word instructions. With register-pair machines a new phenomenom arises that is not present in optimal code generation for single register machines: In an optimal evaluation of an expression it may be necessary to oscillate back and forth between evaluating subexpressions of the expression.A linear-time optimal code generation algorithm is derived for a register-pair machine in which all registers are interchangeable. The algorithm is based on showing that for this model there is an optimal evaluation sequence with limited oscillation between the sub-trees dominated by the children of a given node. For other machine models including the familiar even-odd register-pair machine, optimal evaluation sequences can always require unlimited oscillation.

This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their worst-case behavior is analyzed. For one register machines, an optimal code generation algorithm is given whose time complexity is linear in the size of an expression and exponential only in the amount of sharing.

Abstract A minimal rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuits. Unfortunately, at present no practical algorithm is known for constructing these trees in general. We present two algorithms, each requiring a number of operations proportional to only a low degree polynomial in the number of points to be interconnected, for the special cases in which all the points of A lie on a small number of parallel lines or on the boundary of a rectangle.

Easy as the task may seem, many compilers generate rather inefficient code. Some of the difficulty of generating good code may arise from the lack of realistic models for programming language and machine semantics. In this paper we show that the computational complexity of generating efficient code in realistic situations may also be a major cause of difficulty in the design of good compilers.

The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols.

This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic programming algorithm is then presented which produces optimal code for any machine in this class; this algorithm runs in time linearly proportional to the size of the input.

Trees in an n-node forest are merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of $O(n)$ such instructions can be processed “on-line” in $O(n\log n)$ steps on a random access computer. If we can accept our answer “off-line”, that is, no answers need to be produced until the entire sequence of instructions has been seen, then we may perform the task in $O(n\alpha (n))$ steps, where $\alpha (n)$ is the very slowly growing inverse Ackermann function defined in [14]. A third algorithm solves a problem of intermediate complexity. We require the answers on-line, but we assume that all tree merging instructions precede the information requests. This algorithm requires $O(n \log \log n)$ time. We apply the first on-line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. We show how this computation can be performed in $O(n\log n)$ steps.

We discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. After defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive a necessary and sufficient condition which can be used to prove the optimality of any code generation algorithm for expression trees on this class. We then present a dynamic programming algorithm which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.

In [1], Kennedy conjectures that for every n node reducible flow graph, there is a sequence of nodes (with repetitions) of length O(nlogn) such that all acyclic paths are subsequences thereof. Such a sequence would, if it could be found easily, enable one to do various kinds of global data flow analyses quickly. We show that for all reducible flow graphs such a sequence does exist, even if the number of edges is much larger than n. If the number of edges is O(n), the node listing can be found in O(nlogn) time.

We investigate the evaluation of an $(n - 1)$st degree polynomial at a sequence of n points. It is shown that such an evaluation reduces directly to a simple convolution if and only if the sequence of points is of the form $b, ba,ba^2 , \cdots ,ba^{n - 1} $ for complex numbers a and b (the so-called “chirp transform”). By more complex reductions we develop an $O(n\log n)$ evaluation algorithm for sequences of points of the form \[ b + c + d,\quad ba^2 + ca + d,\quad ba^4 + ca^2 + d, \cdots \] for complex numbers a, b, c and d. Finally we show that the evaluation of an $(n - 1)$st-degree polynomial and all its derivatives at a single point requires at most $O(n\log n)$ steps.

We propose a new architecture for dynamic memories in which the contents of any cell in memory can be accessed by applying a sequence of two primitive memory operations. The advantage of our memory over previous designs is its fast sequential access. Any word in an n cell memory can be accessed in 0(log n) steps. However, once two consecutive words have been accessed, following words can be accessed in one step per word.

We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve syntactic ambiguities. We show how efficient LL and LR parsers can be constructed directly from certain classes of these specifications.

Trees in an n node forest are to be merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of O(n) instructions can be processed “on line” in O(n log n) steps on a random access computer.

We present a new transformation that reduces the size and increases the speed of ${\text{LR}}(k)$ parsers. This transformation can be applied to all ${\text{LR}}(k)$ parsers including those produced by Knuth’s and DeRemer’s techniques. The transformation causes the parser to avoid reductions by productions of the form $A \to B$, where A and B are nonterminals.

We present a new transformation that reduces the size and increases the speed of LR(k) parsers. This transformation can be applied to all LR(k) parsers including those produced by Knuth's and DeRemer's techniques. The transformation causes the parser to avoid reductions by productions of the form A → B where A and B are non-terminals.

Two generalizations of the simple precedence grammars are considered.The first, the weak precedence grammars, are shown to generate exactly the simple precedence languages.The second, the "simple" mixed strategy precedence grammars, are shown to generate exactly the deterministic context-free languages.Algorithms for their implementation are given, and the complexity of these algorithms studied.

We consider economical representations for the path information in a directed graph. A directed graph $G^t $ is said to be a transitive reduction of the directed graph G provided that (i) $G^t $ has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than $G^t $ satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.

We assume three types of syntax errors can debase the sentences of a language generated by a context-free grammar: the replacement of a symbol by an incorrect symbol, the insertion of an extraneous symbol, or the deletion of a symbol. We present an algorithm that will parse any input string to completion finding the fewest possible number of errors. On a random access computer the algorithm requires time proportional to the cube of the length of the input.

We provide a set of transformations capable of transforming a straight line program into any other equivalent one assuming no algebraic laws hold. We then show that optimization of straight line code under “reasonable” cost criteria can always be accomplished by applying sequences of these transformations in a prescribed order.

We consider methods of modifying LR(k) parsers [1] while preserving the ability of that parsing method to detect errors at the earliest possible point on the input. Two transformations are developed, and the methods of Korenjak [2] and DeRemer [3] are expressed in terms of these transformations. The relation between these two methods is exposed. Proofs are for the most part omitted, but can be found in [4].

ABSTP~CT.A formal model is presented for paging algorithms under /-order nonstationary assumptions about program behavior.When processing a program under paging in a given memory, a given paging policy generates a certain (expected) number of page calls, i.e., its "cost."Under usual assumptions about memory system organization, minimum cost is always achieved by a demand paging algorithm.The minimum cost for /-order program behavior assumptions is expressed as a dynamic programming problem whose solution yields an optimal replacement algorithm.Solutions are exhibited in several 0-order cases of interest.Paging algorithms that implement and approximate the minimum cost are discussed.

We consider a program schema that models straight line intermediate level code. A complete set of equivalence preserving transformations on programs is found for the case in which programs are equivalent if and only if their output functions are identical. This result is extended to the case in which programs are deemed equivalent if their output functions can be shown equivalent under a fixed set of algebraic laws.

Two schemes for the specification of translations on a context-free grammar are proposed. The first scheme, called a generalized syntax directed translation (GSDT), consists of a context free grammar with a set of semantic rules associated with each production of the grammar. In a GSDT an input word is parsed according to the underlying context free grammar, and at each node of the tree, a finite number of translation strings are computed in terms of the translation strings defined at the descendants of that node. The functional relationship between the length of input and length of output for translations defined by GSDT's is investigated.

article Free Access Share on Nested Stack Automata Author: Alfred V. Aho Bell Telephone Laboratories, Inc., Murray Hill, New Jersey Bell Telephone Laboratories, Inc., Murray Hill, New JerseyView Profile Authors Info & Claims Journal of the ACMVolume 16Issue 3July 1969 pp 383–406https://doi.org/10.1145/321526.321529Published:01 July 1969Publication History 104citation1,223DownloadsMetricsTotal Citations104Total Downloads1,223Last 12 Months64Last 6 weeks14 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages.

Broadly speaking, an automaton can be considered to be an abstract device consisting of an input tape, a finite state control, and some type of auxiliary memory. Automata have been classified according to the structure of the auxiliary memory and the manner in which information can be stored and retrieved from this memory.