\documentclass{llncs}

%% Unicode support
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{autofe}

\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{a4}
\usepackage{epstopdf}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{color}


%% Code
\usepackage{inconsolata}
\usepackage{minted}
\usepackage{fancyvrb}
\usemintedstyle{default}
\newminted{haskell}{gobble=4,mathescape,fontfamily=tt,fontsize=\footnotesize,xleftmargin=\parindent}
\newmint{haskell}{mathescape,fontfamily=tt,fontsize=\footnotesize}



%% Metainformation
%% PDF stuff
\usepackage{datetime}
\usepackage{ifpdf}
\ifpdf
\pdfinfo{
    /Author (J.P.PizaniFlor)
    /Title (Review of Push-Pull Functional Reactive Programming)
    /Keywords (FRP, Functional Reactive Programming, Monads, Applicative, Haskell)
    /CreationDate (D:\pdfdate)
}
\fi

\title{A review of ``Push-Pull Functional Reactive Programming''}

\date{\today}

\author
{
    J.P.~Pizani Flor\inst{1}
}

\institute{
    \inst{1}
    Department of Information and Computing Sciences, Utrecht University - The Netherlands \\
    e-mail: j.p.pizaniflor@students.uu.nl
}


%% The document itself
\begin{document}
    \bibliographystyle{splncs}

    \maketitle

    \section{Introduction}
    \label{sec:intro}

        The paper ``Push-Pull Functional Reactive Programming'', by Conal Elliott, discusses
        Functional Reactive Programming (FRP), a technique developed around 1996 and which can be
        applied to the design of Graphical User Interfaces in a purely functional fashion, and is
        highly expressive and elegant. However, the FRP paradigm had not found (until then) an
        efficient implementation.

        On the way to implement FRP more efficiently, the author first redefines and organizes FRP
        semantics in terms of very well-known type classes (\emph{Functor}, \emph{Applicative} and
        \emph{Monad}). Then the central FRP concepts of \emph{Behavior} and \emph{Event} are given
        new definitions and are made instances of these type classes. Finally, using these new
        definitions a more efficient, push-pull (hybrid between data-driven and demand driven)
        implementation for FRP is derived.


    \section{FRP Fundamentals}
    \label{sec:frpfundamentals}
        Functional Programming Programming (FRP) is in short the functional embodiment of Reactive
        Programming, a paradigm of programming that sees computation through the establishment of
        dataflows and the propagation of changes in values through these dataflows. One good example
        of a reactive programming setting is a spreadsheet program, where a change in the value of
        one cell might cause \emph{reactions}, triggering the values of other cells and so forth, in
        a cascade of change propagation. One application realm which is said to fit FRP very well is
        the programming of Graphical User Interfaces (GUIs).

        FRP derives its expressiveness from 2 fundamental concepts, which can be embodied in types:
        a type with dynamic values, i.e, \emph{values over time}, and a type representing an
        ``event source'', which is just a (infinite) stream of values, paired with the point in time
        when they occur. Elements of the first datatype (dynamic values) are traditionally called
        \emph{behaviors} and elements of the second datatype are called \emph{events}. One example
        of a behaviour would be the position of an object in an animation. When in the context of a
        GUI, a simple example of an event source would be the user's mouse clicks.


    \section{Packaging FRP in standard typeclasses}
    \label{sec:frptypeclasses}
        In the original formulation of FRP there was a family of functions ($lift_{n}$)
        that ``lifts'' a function over values to a function over behaviors. We can define
        $lift_{1}$ with an instance of the Functor typeclass, which -- considering the
        semantic domain of behavior to be a function of time -- has the following definition:
        \begin{haskellcode}
    instance Functor ((->) t) where
        fmap f g = f . g
        \end{haskellcode}

        The denotational semantics of fmap (and of every other operation involving behaviors)
        can be defined with the help of the function ``at''. The ``semantic instance'' for Functor
        bellow is not a real instance, but establishes a law which any implementation must comply
        with, and is:
        \begin{haskellcode}
    instance Functor Behavior where  -- semantic instance
        at (fmap f b) = fmap f (at b)
        \end{haskellcode}

        With the Functor instance for behaviors, we can write $lift_{1}$. With an
        additional instance for Applicative, it is also possible to define any of the functions
        in the family $lift_{n}$. As the semantic domain of behaviors is a function of time, the
        Applicative instance of functions is helpful when defining the semantics of behaviors.
        \begin{haskellcode}
    instance Applicative ((->) t) where
        pure    = const
        f <*> g = \t -> (f t)(g t)

    instance Applicative Behavior where  -- semantic instance
        at (pure a)    = pure a
        at (bf <*> bx) = at bf <*> at bx
        \end{haskellcode}

        In this way the denotational semantics of a behavior and operations over behaviors are
        nicely composed using instances of standard Haskell typeclasses, and the semantics is
        precisely specified \emph{without being mixed with implementation concerns}. This is an
        important point made by the author, as this freedom allows the more efficient implementation
        presented on this paper.

        In the same way done with behaviors, the concept of \emph{Event} (or event source) can also
        be package in instances of standard typeclasses. The \emph{monoid} instance for Event is
        analogous to the list monoid, and the monoid functions ``mempty'' and ``mappend'' replace
        classic FRP's ``neverE'' and ``(.|.)'', which are the
        never-occurring event and an operation to merge two event sources. In the semantic monoid
        instance for Event it is also made clear that time-ordering is preserved in the merging
        operation. The functor instance for Event is also straightforward, and the semantic instance
        expresses that mapping a function over an event changes only the values, leaving occurrence
        times intact:
        \begin{haskellcode}
    instance Functor Event where  -- semantic instance
        occs (fmap f e) = map (\\(t, v) -> (t, f v)) (occs e)
        \end{haskellcode}

        The monad instance for Event is more interesting, and we can come to the need of a monad
        instance by thinking about applications where there is a Event-valued event source, Event
        (Event a). Such an event source can be used to model scenarios where some events might cause
        a new event source to ``come alive''. In the paper the example is given of an Asteroids
        game, where hitting an asteroid might cause it to break in multiple pieces, which collisions
        must be tracked -- thus, one event is able to ``spawn'' an event source.

        Usually monad instances are defined by writing the functions \emph{return} and \emph{bind},
        but in this case a different approach is taken: a monad instance can equivalently be defined
        by the functions \emph{fmap} and \emph{join}. The Functor instance already takes care of
        fmap, and the definition of join below ``flattens'' a nested Event, making sure that the
        inner events do not occur before the outer Event brought that source to life. The
        denotational semantics of join is again defined in terms of the occs function:
        \begin{haskellcode}
    join :: Event (Event a) -> Event a
    occs (join ee) = foldr merge [] . map delayOccs . occs ee
        \end{haskellcode}


    \section{Problems in current implementations}
    \label{sec:problems}
        The main goal of the paper is to provide a more efficient implementation for FRP. The
        redefinition of FRP concepts in terms of standard typeclasses, along with the precise
        definition of its denotational semantics was only a means to achieve this goal. Now, with
        this precisely-defined semantics in hand, we can attack the following problems:

        \begin{itemize}
            \item Merging two event sources involves comparing the occurrence times in both of them
                (to maintain time-ordering). This can cause the handling of two events to happen
                only when the \textbf{later} of the two arrives. This can be solved by embedding
                \emph{partial information} in the values used as time, and is achieved in this paper
                with the abstraction called ``future values''
            \item The semantics of the \emph{switcher} function involve searching an event source
                for events which occurrence time match certain criteria. This search becomes
                costlier as time goes on. In most use cases of FRP, time evolves in a monotonically
                increasing way, and exploring this fact can improve implementation efficiency.
            \item The definition of behaviors as functions impose an inefficient implementation. In
                the paper, a new representation is introduced for behaviors, making explicit the
                non-reactive and constant phases.
        \end{itemize}


    \section{Future values and future times}
    \label{sec:futures}
        To simplify the semantics of events and improve its implementation, as well as provide a
        better representation for time, the concept of ``future values'' is introduced. A future
        value is just a value with an associated time (in which it is bound to be ``available''. By
        taking the semantics of a future value to be a pair, the functor instance is just a partial
        applied pairing and the semantic function is a functor morphism (a function that
        \emph{preserves the structure} of the functor).
        \begin{haskellcode}
    type F a = (T, a)  -- T must satisfy some pre-requisites defined later
    force :: Future a -> F a

    instance Functor ((,) t) where
        fmap f (t, v) = (t, f v)  -- straightforward functor instance

    instance Functor Future where  -- semantic instance
        force (fmap f u) = fmap f (force u)
        \end{haskellcode}

        The Applicative instance for Future is also somewhat straightforward, but has an additional
        requirement: the time type, T, must be a monoid, so that we can use \emph{mempty} as the
        time of (pure a), and \emph{mappend} to combine the times of 2 future values. Furthermore,
        the definition of mempty must be a lower bound for T (T must be Bounded), and mappend must
        choose the maximum between two times. Besides that, the definition holds no surprise, and
        the semantics is defined so that \emph{force} is an Applicative morphism.

        Further instances of Monad and Monoid are given for future values in the paper, along with
        corresponding semantics. It is interesting to note that the semantics given might be
        directly used as implementation if the type of future times chosen satisfies the following
        properties:
        \begin{itemize}
            \item Is ordered and bounded, i.e, a member of the typeclasses Ord and Bounded
            \item Is a monoid in which \emph{mempty} is minBound and \emph{mappend} is max.
            \item The structure of the type must reveal partial information on times, so that
                comparisons can be performed even when the times are not yet fully known.
        \end{itemize}

        These three requirements can be embodied in three newtypes, with Max and AddBounds
        having pretty straightforward Monoid, Ord and Bounded instances, respectively. The innermost
        newtype in this onion-like structure (Improving) is describe in more detail later, and
        provides partial information in time representation.
        \begin{haskellcode}
    type FTime = Max (AddBounds (Improving Time))
        \end{haskellcode}


    \section{Separating the reactive and non-reactive parts of behaviors}
    \label{sec:behaviorredefine}
        One of the biggest problems posed by the author FRP implementations is the demand-driven
        model, caused by the implementation of (reactive) behaviors simply as a function of time.
        However, this is not the only possible implementation: as noticed by the author, a behavior
        has several non-reactive \emph{phases}, punctuated by events. Then, if we can view behaviors
        through a datatype that makes this distinction explicit, we can exploit this in an
        implementation (for example, only one sample is needed to represent a constant phase). The
        new representation proposed for (reactive) behaviors is built on top of two concepts,
        reactive values and time functions, each embodied in a Haskell datatype.

        Reactive values are discrete ``step'' functions, with time as their domain, and are defined
        by an initial value and some discrete changes, represented exactly by an FRP Event.
        \begin{haskellcode}
    data Reactive a = a `Stepper` Event a
        \end{haskellcode}

        Reactive values have pretty straightforward instances for Functor, Applicative and Monad,
        and its semantic function (\emph{rat}, which translates a reactive value into a reactive
        behavior) is a morphism on the Functor, Applicative and Monad instances.

        Now, in-between the moments of discrete change, the value of a behavior can change according
        to a non-reactive (and possibly continuous) function of time. Even though we might represent
        the concept of a function directly as a Haskell function, this is not very useful. The
        authors chose to create a datatype of time functions, in which two cases are distinguished:
        the case in which the function is constant and the case in which it's not (this allows for
        optimization in the common use case of constant functions):
        \begin{haskellcode}
    data Fun t a = K a | Fun (t -> a)
        \end{haskellcode}

        Off course there are also neat instances of Functor, Applicative and Monad for the Fun
        datatype, and its semantic function (\emph{apply}, which just corresponds to usual
        function application) is a morphism over the instance of all these type classes.

        Having these two component in hand (reactive values and time functions), (reactive)
        behaviors can be given a new definition:
        \begin{haskellcode}
    type Behavior = Reactive . Fun Time  -- the dot is type-level composition, as below
    newtype (h . g) a = O (h (g a))
        \end{haskellcode}

        This means that behaviors are, in essence, reactive values in which the values themselves
        are time functions. In the common case of step functions, for example, each time function is
        simply a constant. Instances of Functor and Applicative are given for the type-level
        composition operator, which (together with the instances for Reactive and Fun) give us
        Functor and Applicative functionality for free for this new behavior representation.


    \section{Events redefined and monotonic time sampling}
    \label{sec:eventsmonotonic}
        After the definitions of future values (a value and a time when it will occur) and reactive
        values (an initial value and a sequence of discrete changes), we can define Event quite
        elegantly by using these two concepts:
        \begin{haskellcode}
    newtype Event a = Ev (Future (Reactive a))
        \end{haskellcode}

        That means that an Event is a time and a value (the first occurrence) and a sequence of
        discrete changes. This corresponds intuitively with the original definition of Events, in
        terms of lists of occurrences, but solves a subtle problem which impacts performance: By
        using a list of occurrences as a model for Event, we had to test the list for emptiness when
        merging two Events. This test results in a Bool, which can provide no partial information
        and thus must wait before all occurrences arrive before yielding a result.

        After this redefinition of Event, the paper goes on to discuss a very important optimization
        for implement FRP efficiently: \emph{monotonic sampling}. The key observation is that, even
        though the semantics of FRP don't restrict behaviors -- and they can be applied to time values
        in any order (they are just a function of time) -- in \emph{real-world situations} behaviors
        are evaluated with monotonically increasing times as arguments. Thus, making this usage
        pattern explicit and exploiting it might result in bug efficiency gains.

        The paper goes on to discuss how to render behaviors forward in time. For this we first need
        functions that take ``sinks'' (functions that have \texttt{IO ()} as counter-domain) and
        consume Reactive values and Events:
        \begin{haskellcode}
    sinkR :: Sink a -> Reactive a -> IO b
    sinkE :: Sink a -> Event a -> IO b
        \end{haskellcode}

        Their implementation is simple, and they are mutually recursive: sinkR immediately renders
        the initial value and then proceeds to render the nested Event (the ``tail''). The function
        sinkE waits (blocks) until the first occurrence time $t_{0}$ and then proceeds to render
        the nested Reactive value.

        The whole ``puzzle'' on how to render a behavior forward in time is almost complete, there
        being only a single missing piece -- how to render a time function. With this piece in
        place, an implementation of how to render a behavior forward in time finally comes together:
        \begin{haskellcode}
    sinkN :: Sink a -> Behavior a -> IO b
    sinkN snk (O rf) = newTFunSink snk >>= flip sinkR rf
        \end{haskellcode}

        We first create a sink for time functions, then use sinkR to render each of the time
        functions in the sequence (the Reactive sequence). And how does this sink for time functions
        behave? Well, if the function is constant, its value is rendered just once (using the snk
        parameter). If the function is truly time-dependent, a thread is spawned which samples and
        renders its value periodically.


    \section{Partial information on occurrence times}
    \label{sec:partialtime}
        If we refer back to the end of section \ref{sec:futures}, a mention is made to a type
        constructor \texttt{Improving}, in the definition of the type of future times. Applying this
        constructor to a time type yields a type containing partial information, and thus allowing
        for comparisons between future times to evaluate before either of them has fully arrived.

        The name of the type constructor mentioned in section \ref{sec:futures} (\texttt{Improving})
        is not a coincidence, as the abstraction used by the author to solve this problem is that of
        \emph{Improving values}, invented by Warren Burton in 1989. An improving value can be seen
        as a sequence of lower bounds ending up in an exact value (in our case a time).

        The author further improves on improving values (no pun intended) by establishing a method
        with which to compare two future times. It is assumed that we have a function that can
        compare an exact value with an improving value. Then faced with the comparison between two
        future times $t_{a} \leq t_{b}$ we can do it in two ways:
        \begin{enumerate}
            \item Extract the exact time from $t_{a}$ and compare it with $t_{b}$
            \item Extract the exact time from $t_{b}$ and compare it with $t_{a}$
        \end{enumerate}

        Now, these methods will result in the same value, but not at the same time. The problem is
        that if $t_{a} \leq t_{b}$ then the first method will be quicker, otherwise the second. How
        to solve this? Well, both approaches are attempted in parallel and whichever one finishes
        first is returned. This parallel implementation is done by using Concurrent Haskell and a
        \texttt{MVar}.


\end{document}
