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.

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.

It IS shown that two widely different notions of program equivalence coincide for the language of recurslve definitions with simplification rules The first is the now classical equivalence for fixed-point semantics.The other is purely operational in nature and is much closer to a programmer's intuition of program equivalence KEY WORDS AND PHgASES semantics of programming languages, algebraic semantics, subtree replacement systems CR CATEGORIES: 4 2, 5 2, 5 24

In this paper, we show that two widely different notions of program equivalence coincide for the language of recursive definitions with simplification rules. The first one is the now classical equivalence for fixed-point semantics. The other one is purely operational in nature and is much closer to a programmer's intuition of program equivalence.

Let An be the average number of registers required for evaluating arithmetic expressions of size n, or, equivalently, the minimal stack needed for exploring binary trees with n nodes. We give explicit expressions for An and related quantities and show that: An = log4(n) + C + E(log4n) + o(1) where C = 1/2 - γ + 2/2 log2 + log2Π 0.292 and E is continuous, periodic with period 1, with average value 0 and amplitude less than .05.