EECS technical reports

Conditions of Use

Archive Home Page

The Power of Higher-Order Composition Languages in System Design

Cataldo, James Adam
Technical Report Identifier: EECS-2006-189
December 18, 2006

Abstract: This dissertation shows the power of higher-order composition languages in system design. In order to formalize this, I develop an abstract syntax for composition languages and two calculi. The first calculus serves as a framework for composition languages without higher-order components. The second is a framework for higher-order composition languages. I prove there exist classes of systems whose specification in a higher-order composition language is drastically more succinct than it could ever be in a non-higher-order composition language.

To justify the calculus, I use it as a semantic domain for a simple higher-order composition language. I use it to reason about higher-order components in this more practical language and use n-level clock distribution networks as a class of systems whose description must grow exponentially in a non-higher order composition language, but whose description grows linearly with n in a higher-order composition language.

As a prototype higher-order composition language, I developed the Ptalon programming language for Ptolemy II. I explain how components can be built in Ptalon, and I give several examples of models built as a higher-order components in this language. These examples span several domains in system design: control theory, signal processing, and distributed systems.

Unlike functional languages, where higher-order functions are infused with a program's execution semantics, the ability to provide scalable higher-order mechanism is completely separated from execution semantics in higher-order composition languages. As a design technique, higher-order composition languages can be used to provide extremely scalable system descriptions.