Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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 = {Cataldo, James Adam},
    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},
    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.

<p>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.

<p>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.

<p>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.}
}

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