Abstract Functional Reactive Programming (FRP) is a high-level declarative language for programming reactive systems. Previous work on FRP has demonstrated its utility in a wide range of application domains, including animation, graphical user interfaces, and robotics. FRP has an elegant continuous-time denotational semantics. However, it guarantees no bounds on execution time or space, thus making it unsuitable for many embedded real-time applications. To alleviate this problem, we recently developed Real-Time FRP (RT-FRP), whose operational semantics permits us to formally guarantee bounds on both execution time and space.
In this paper we present a formally verifiable compilation strategy
from a new language based on RT-FRP into imperative code. The new
language, called Event-Driven FRP (E-FRP), is more tuned to the
paradigm of having multiple external events. While it is smaller
than RT-FRP, it features a key construct that allows us to compile the
language into efficient code. We have used this language and its
compiler to generate code for a small robot controller that runs on a PIC16C66
micro-controller. Because the formal specification of compilation
was crafted more for clarity and for technical convenience, we describe
an implementation that produces more efficient code.
Abstract We review the basics of functional programming,
and give a brief introduction to emerging techniques and approaches relevant
to building real-time software. In doing so we attempt to explain
the relevance of functional programming concepts to the real-time applications
domain. In particular, we address the use of types to classify properties
of real-time computations.
Abstract Fruit is a new graphical user interface library
for Haskell based on a formal model of user interfaces. The model identifies
signals (continuous time-varying values) and signal transformers (pure
functions mapping signals to signals) as core abstractions, and defines
GUIs compositionally as signal transformers. In this paper, we describe
why we think a formal denotational model of user interfaces is useful,
present our model and prototype library implementation, and show some example
programs that demonstrate novel features of our library.
Abstract Functional reactive programming (FRP) is a declarative programming paradigm where the basic notions are continuous, time-varying behaviors and discrete, event-based reactivity. FRP has been used successfully in many reactive programming domains such as animation, robotics, and graphical user interfaces. The success of FRP in these domains encourages us to consider its use in real-time applications, where it is crucial that the cost of running a program be bounded and known before run-time. But previous work on the semantics and implementation of FRP was not explicitly concerned about the issues of cost. In fact, the resource consumption of FRP programs in the current implementation is often hard to predict.
As a first step towards addressing these concerns, this paper presents Real-Time FRP (RT-FRP), a statically-typed language where the time and space cost of each execution step for a given program is statically bounded. To take advantage of existing work on languages with bounded resources, we split RT-FRP into two parts: a reactive part that captures the essential ingredients of FRP programs, and a base language part that can be instantiated to any generic programming language that has been shown to be terminating and resource-bounded. This allows us to focus on the issues specific to RT-FRP, namely, two forms of recursion. After presenting the operational explanation of what can go wrong due to the presence of recursion, we show how the typed version of the language is terminating and resource-bounded.
Most of our existing FRP programs are expressible directly in RT-FRP.
The rest are expressible via a simple mechanism that integrates RT-FRP
with the base language.
Abstract Functional programming languages are not generally associated with computationally intensive tasks such as computer vision. We show that a declarative programming language like Haskell is effective for describing complex visual tracking systems. We have taken an existing C++ library for computer vision, called XVision, and used it to build FVision (pronounced ``fission''), a library of Haskell types and functions that provides a high-level interface to the lower-level XVision code. Using functional abstractions, users of FVision can build and test new visual tracking systems rapidly and reliably. The use of Haskell does not degrade system performance: computations are dominated by low-level calculations expressed in C++ while the Haskell ``glue code'' has a negligible impact on performance.
FVision is built using functional reactive programming (FRP) to express
interaction in a purely functional manner. The resulting system demonstrates
the viability of mixed-language programming: visual tracking programs continue
to spend most of their time executing low-level image-processing code,
while Haskell's advanced features allow us to develop and test systems
quickly and with confidence. In this paper, we demonstrate the use of Haskell
and FRP to express many basic abstractions of visual tracking.
Abstract Functional Reactive Programming (FRP) is a declarative programming model for constructing interactive applications based on a continuous model of time. FRP programs are described in terms of behaviors (continuous, time-varying, reactive values), and events (conditions that occur at discrete points in time).
This paper presents Frappé, an implementation of FRP in the Java
progamming language. The primary contribution of Frappeé is its
integration of the FRP event/behavior model with the Java Beans event/property
model. At the interface level, any Java Beans component may be used as
a source or sink for the FRP event and behavior combinators. This provides
a mechanism for extending Frappé with new kinds of I/O connections
and allows FRP to be used as a high-level declarative model for composing
applications from Java Beans components. At the implementation level, the
Java Beans event model is used internally by Frappé to propagate
FRP events and changes to FRP behaviors. This allows Frappé applications
to be packaged as Java Beans components for use in other applications,
and yields an implementation of FRP well-suited to the requirements of
event-driven applications (such as graphical user interfaces).
This paper gives a denotational semantics to FRP, and discusses the connection between the semantics and a stream-based implementation.
Abstract Functional Reactive Programming, or FRP, is a general framework for programming hybrid systems in a high-level, declarative manner. The key ideas in FRP are its notions of behaviors and events. Behaviors are time-varying, reactive values, while events are time-ordered sequences of discrete-time event occurrences. FRP is the essence of Fran, a domain-specific language embedded in Haskell for programming reactive animations, but FRP is now also being used in vision, robotics and other control systems applications.
In this paper we explore the formal semantics of FRP and how it relates
to an implementation based on streams that represent (and therefore
only approximate) continuous behaviors. We show that, in the limit
as the sampling interval goes to zero, the implementation is faithful to
the formal, continuous semantics, but only when certain constraints on
behaviors are observed. We explore the nature of these constraints,
which vary amongst the FRP primitives. Our results show both the
power and limitations of this approach to language design and implementation.
As an example of a limitation, we show that streams are incapable of representing
instantaneous predicate events over behaviors.
Abstract In this paper, we demonstrate how Functional Reactive Programming (FRP), a framework for the description of interactive systems, can be extended to encompass parallel systems. FRP is based on Haskell, a purely functional programming language, and incorporates the concepts of time variation and reactivity.
Parallel FRP serves as a declarative system model that may be transformed
into a parallel implementation using the standard program transformation
techniques of functional programming. The semantics of parallel FRP include
non-determinism, enhancing opportunities to introduce parallelism. We demonstrate
a variety of program transformations based on parallel FRP and show how
a FRP model may be transformed into explicitly parallel code. Parallel
FRP is implemented using the Linda programming system to handle the underlying
parallelism. As an example of parallel FRP, we show how a specification
for a web-based online auctioning system can be transformed into a parallel
implementation.
An overview of Frob from the Haskell side.
Abstract We present our experiences using a purely functional
language, Haskell, in what has been traditionally the realm of low-level
languages: robot control. Frob (Functional Robotics) is a
domain-specific language embedded in Haskell for robot control. Frob is
based on Functional Reactive Programming (FRP), as initially developed
for Fran, a language of reactive animations. Frob presents the interaction
between a robot and its stimuli, both onboard sensors and messages from
other agents, in a purely functional manner. This serves as a basis for
composable high level abstractions supporting complex control regimens
in a concise and reusable manner.
A paper on Haskell for vision and tracking.
Abstract We describe the enhancement of XVision, a large library of C++ code for real-time vision processing, into FVision (pronounced \,ssion"), a fully-featured domainspeci,c language embedded in Haskell. The resulting prototype system substantiates the claims of increased modularity, e,ective code reuse, and rapid prototyping that characterize the DSL approach to system design. It also illustrates the need for judicious interface design: relegating computationally expensive tasks to XVision (pre-existing C++ components), and leaving modular compositional tasks to FVision (Haskell). At the same time, our experience demonstrates how Haskell's advanced language features (speci,cally parametric polymorphism, lazy evaluation, higher order functions and automatic storage reclamation) permit a rapid DSL design that is itself highly modular and easily modi,ed. Overall, the resulting hybrid system exceeded our expectations: visual tracking programs continue to spend most of their time executing low level image-processing code, while Haskell's advanced features allow us to quickly develop and test small prototype systems within a matter of a few days and to develop realistic applications within a few weeks.
Keywords: Domain-specic languages, Functional programming, Modularity,
Code reuse, Computer vision, Haskell.
An overview of Frob from the robotics side.
Abstract We have applied methodologies developed for domain-specific
embedded languages to create a highlevel robot control language called
Frob,
for Functional Robotics. Frob supports a programming style that
cleanly separates the what from the how of a robotic control
program. That is, the what is a simple, easily understood definition
of the control strategy using groups of equations and primitives which
combine sets of these control system equations into a complex system. The
how
aspect of the program addresses the unpleasant details, such as the method
used to realize these equations, the connection between the control equations
and the sensors and effectors in the robot, and communication with other
elements of the system. Frob is a system that supports rapid prototyping
of new control strategies, enables software reuse through composition,
and defines a system in a way that can be formally reasoned about and transformed.
Abstract A domain specific language (DSL) allows one to develop software for a particular application domainquickly and effectively, yielding programs that are easy to understand, reason about, and maintain. Onthe other hand, there may be a significant overhead in creating the infrastructure needed to support aDSL. To solve this problem, a methodology is described for building domain specific embedded lan-guages (DSELs), in which a DSL is designed within an existing, higher-order and typed, programming lan-guage such as Haskell or ML. In addition, techniques are described for building modular interpreters andtools for DSELs. The resulting methodology facilitates reuse of syntax, semantics, implementation code, soft-ware tools, as well as look-and-feel.
Keywords: software reuse, modularity, abstrac-tion, domain specific
languages, functional languages, formal methods.
Abstract Fran (Functional Reactive Animation) is
a collection of data types and functions for composing richly interactive,
multi-media animations. The key ideas in Fran are its notions of behaviors
and events. Behaviors are time-varying, reactive values, while events
are sets of arbitrarily complex conditions, carrying possibly rich information.
Most traditional values can be treated as behaviors, and when images are
thus treated, they become animations. Although these notions are captured
as data types rather than a programming language, we provide them with
a denotational semantics, including a proper treatment of real time, to
guide reasoning and implementation. A method to effectively and efficiently
perform event detection using interval analysis is also described,
which relies on the partial information structure on the domain of event
times. Fran has been implemented in Hugs, yielding surprisingly good performance
for an interpreter-based system. Several examples are given, including
the ability to describe physical phenomena involving gravity, springs,
velocity, acceleration, etc. using ordinary differential equations.