Benjamin Lerner

Arrow Laws and Efficiency in Yampa

Benjamin Lerner, Paul Hudak

Papers and Downloads

• Project Proposal (pdf format)
  The initial proposal for this paper assumed that all the arrow laws would be straightforwardly provable, and therefore made no consideration of the possibility of efficiency or optimizations based on the laws.
• Final Paper (pdf format)
  In the course of proving the various arrow laws, we found that two of them in fact do not hold as strict equalities, and therefore some consideration is given to how this disparaty can be leveraged into possible optimizations.

Abstract

Yampa is a functional reactive language developed for the specific domain of robotic control. By combining both discrete events and time-varying signals, it incorporates the main types of actions and stimuli a robot likely encounters. To accomplish this, signals and events are represented by a signal function class, which is defined and implemented to be an instance of the Arrow class, which defines the operators associated with that abstraction.

The choice of an arrow as the underlying representation yields two benefits at the programmer's level. First, because of how the operators are defined, arrows do not suffer from the same space-leaks that prior implementations of Yampa did. Second, the patterns in which the operators combine arrows are intuitively similar to those found in circuit diagrams, and hence the correspondence between circuit programming of robots and arrow programming in Yampa is easier to appreciate.

We formally prove that the type SF (the basic signal function class used in Yampa), defined in [2] and implemented in [3], satisfies the arrow laws as defined in [5], for the purposes of showing that Yampa, which is built around the properties of this class, in fact is sound. Two of the nine laws are not satisfied in terms of strict equality; an evaluation function is defined under which those two laws do hold. As the two expressions involved in each law are not the same, some discussion is given as to which expression is more efficient, and its potential as an optimization for Yampa programs.

References

[1]

Paul Hudak, The Haskell School of Expression; Learning Functional Programming Through Multimedia, Cambridge University Press, 2000.

[2]

Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson, Arrows, Robots, and Functional Reactive Programming, Summer School on Advanced Functional Programming 2002, Oxford University, Lecture Notes in Computer Science, Springer-Verlag, 2003.

[3]

________, Yampa 0.9.1 Source Code, http://haskell.org/yampa/, 2003.

[4]

John Hughes, Generalising Monads to Arrows, Science of Computer Programming 37 (2000), no. 1—3, 67—111.

[5]

Ross Paterson, A New Notation for Arrows, International Conference on Functional Programming, ACM Press, September 2001, pp. 229—240.

[6]

________, Arrows and Computation, The Fun of Programming (Jeremy Gibbons and Oege de Moor, eds.), Palgrave, 2003, pp. 201—222.