The design and implementation of high level programming language features for pattern matching in real-time.

High-level programming language features simplify software development by eliminating many low-level programming concerns and by providing programmers with useful abstractions to simplify description and analysis of their programs. This dissertation discusses briefly some of the special needs of structural pattern-matching programs that must execute in real time and suggests language features to support these needs. These language features are implemented in an experimental version of the Icon programming language and examples of how these language features can be used are presented. This dissertation also presents and discusses the implementation of these language mechanisms, including the implementation of a new algorithm for garbage collecting linked data structures and strings in real time. One of the new language features is a stream data type, which allows programmers to perform pattern matching directly on sequences of data values produced by external sources, without requiring explicit read operations to bring the data into memory before analyzing it. Other new language features provide the ability to create and manipulate concurrent Icon processes, between which the stream data type serves as the principal mechanism for interprocess communication. Stream and concurrent process manipulation mechanisms integrate naturally with each other and with the existing mechanisms of the Icon programming language. Sequential Icon programs are, for the most part, unaffected by the new language capabilities