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.
Title
The Power of Higher-Order Composition Languages in System Design
Published
2006-12-18
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
EECS-2006-189
Type
Text
Extent
129 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).