The Power of Higher-Order Composition Languages in System Design
James Adam Cataldo
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-189
December 18, 2006
http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-189.pdf
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.
Advisor: Edward A. Lee and S. Shankar Sastry
BibTeX citation:
@phdthesis{Cataldo:EECS-2006-189,
Author = {James Adam Cataldo},
Title = {The Power of Higher-Order Composition Languages in System Design},
School = {EECS Department, University of California, Berkeley},
Year = {2006},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-189.html},
Number = {UCB/EECS-2006-189}
}
EndNote citation:
%0 Thesis %A Cataldo, James Adam %T The Power of Higher-Order Composition Languages in System Design %I EECS Department, University of California, Berkeley %D 2006 %8 December 18 %@ UCB/EECS-2006-189 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-189.html %F Cataldo:EECS-2006-189