View article

Strongly sequential systems, developed by Huet and Levy HL79], has formed the basis of equational programming languages. Experience with such languages so far suggests that even complex equational programs are based only on strongly sequential systems with constructors. However, these programs are not readily amenable for e cient parallel execution. This paper introduces a class of strongly sequential systems called path sequential systems. We show that path sequential programs are natural for parallel evaluation. In particular, path sequential systems permit matching and search for redexes to proceed independently along di erent paths in a term. Such independent search, which avoids excessive synchronization and communication overheads, is not possible in strongly sequential systems. We describe a sound and complete parallel normalization algorithm for path sequential program and analyze its complexity. We then discuss the issue of expressive power of path sequential systems. By presenting a simple, syntactic method to transform any strongly sequential system with constructors into an equivalent path sequential system, we establish that the two classes have equal expressive power. Finally, we discuss other notions of sequentiality based on traversal orders (such as O'Donnell's strong left-sequentiality) and show that all such notions of sequentiality are equivalent under our transformation.