Functional Programming GUIs (part 2) - Arrowized FRP

Functional Reactive Programming (FRP) is a declarative method of creating systems that react to changes of the environment over time. The initial work of Elliott and Hudak¹ introduces two type of inputs to the system as values that change over time (time varying values): behaviors and events. Behaviors are continuous varying values:

while events are discrete values:

The first type of value helps modeling physical systems for instance, where phenomena like position, velocity, acceleration depend on continuous input while events help model situations with discrete inputs, like GUI interactions with a user. The focus of the first formulation of FRP was animation (the original implementation is called FRAN - functional reactive animation) and this is the reason for this work to be focused on continuous values.

The original implementation is very expressive and flexible, posing no significant difficulties in understanding or implementation while being composable. However, it allowed accumulation of events in the event system due to the lazy nature of the host implementation language - Haskell - which only evaluates a value when it is explicitly requested by the effect system. This could potentially lead to memory exhaustion causing a problem called space leaks. When the events are finally evaluated they create an execution bottleneck that leads to longer execution time known as a time leak or a global delay. For the continuous counterpart it required frequent sampling of the input space that triggered extraneous re-renderings of the entire system for no modifications or only partial modifications of the system state, a problem known as unnecessary update. The implementation also allowed defining behaviors that depended on past values (causing memory leaks) or future values (breaking causality, thus not implementable).

Subsequent updates to the classical FRP utilize the observation that the discrete case of the event system is isomorphic to the continuous case for optional values:

Maybe a = Just a | Nothing;
Event a = Behavior (Maybe a)

leading to both events and behaviors being represented by a signal:

With this new data type it is possible to introduce a more restrictive language as a reactive front-end with a more flexible compilation target language that allows to limit the problem surface for the space and time leaks, as well as for the unnecessary updates.

These approaches, while working, lose some of the expresiveness of the classical FRP. The efforts to reclaim this expresiveness while maintaining the safety guarantees lead to arrowized FRP.

An arrow is the generalization of a function at type level in a pure functional programming language. In a category theory interpretation of arrows that suits computing best (where \(V\) is \(Set\) ) they are monoids in the category of bifunctors \(C^{op} \times C \rightarrow V\) where \(V\) is a symmetric closed monoid and \(C\) is \(V\)-enriched ². This allows arrows to compose while retaining some context of the computation in the chaining.

Arrowized FRP overcomes the limitations of classical, real-time and event-based FRP by restricting access to signals to avoid time and space leaks and by reclaiming the expressiveness of classical FRP through the properties of an arrow. It defines a datataype

that abides by the arrow laws. Because the signal types available to the programmer are specified at the source level and their constructors are not available for direct usage the usage of signals is both restricted to avoid leaks and respect causality. Even with these measures, leaks are still possible in the host implementation due to the instant update assumption³ that states that the semantics of arrows can be respected as long as sampling interval for updates goes to 0.

Czaplicki uses the concept of signal arrows in the creation of his Elm language to disallow folds from the past of signals that drop signals during the fold. For this reason the type representing a signal in Elm is only an applicative functor, not a monad (join-ing would be flattening the signal). At the same time, a signal is isomorphic to an arrow from the World (environment) to the value \(\alpha\)):

This interpretation gives the backend compiler the flexibility to use the arrow interface to interpret the reactive interface (foldp and lift).

Citing difficulties in adoption of the language (A farewell to FRP, Czaplicki, E., May 10 2016 ) Czaplicki moves Elm with version 0.17 away from FRP in 2016, favoring a message-passing concurrent approach similar to Erlang.

While arrowized FRP presents good compositional properties when representing signals as arrows a practical implementation that does not leak time and memory will impose significant limits on these properties. Arrows impose a point-free style that is notoriously difficult for programmers. Defining lambda calculus in terms of arrows to allow decoupling of computations implies adding separate arrow interface functions for function application, choice and feedback and making concurrent arrows naturally flows towards the Erlang actor model. Arrows compose using arrow transformers (a generalization of monad transformers), but these structures imply unwrapping the nesting levels to perform the desired effect and consume the effect stack. However, some arrow based combinations might still yield good results as a means to pass along application state in an effect composition chain.

Functional Programming GUIs (part 1)

Programming GUIs poses a number of interesting problems and has known over the years a number of interesting solutions both in the imperative programming paradigm and in the functional one.

For one it is considered unacceptable for a graphical interface to block while some work is being performed due to usability reasons and thus entails the existence of at least two threads of computing, one for background work and one for interface updates. Serializing the actions and their results in a consistent and predictable manner has been a challenge for programmers for various reasons, ranging from complexity of the state and state update dependency calculations to displaying proper results to the user.

In recent years versions of a functional approach to the problem – namely FRP¹ – have known a great deal of success being implemented in imperative languages mainly due to providing a good structure to Single Page Applications written in javascript. This is an indication that there is a great interest in the simplicity provided by the functional framework to the overall process of structuring an application.

As popular as the approach is it still does not fulfill the age-old promise of perfect decoupling of components in programming nor the one of minimizing the cognitive burden on the programmer when trying to achieve this decoupling. Moreover, complexity appears to be the single most frequent cause of software errors, leading to less stable software. Due to concurrency this issue is especially prevalent in GUI programming.

The scope of the present inquiry is thus multi-folded. We want to find a solution that presents these characteristics:

• it is expressive enough so it can model a GUI program with all its aspects
• it is composable such that larger programs can be constructed from smaller GUI components (thus having a functional basis)
• it restricts complexity to the component being implemented, thus reducing programmer cognitive burden
• it is type-safe, reducing to the minimum the runtime faults
• it has at least moderate performance characteristics for today’s standards

As secondary objective we also aim to implement the chosen solution in a proof-of-concept application that will allow us to evaluate how ergonomic is the proposed solution.

We compare three selected approaches to this problem and we analyze them with respect to the research objective.

Arrows are generalization of morphisms with a container component such that decidability is easily implemented based on the contained value. Arrowized FRP² composes well, is expressive and type-safe but has known problems with space and time leaks.

Algebraic event handlers³ are a recent approach to handling composition in the presence of effects. Effects in a program form a free monad that can be folded using an algebra (the free monad’s catamorphism). The program is a tree that is folded to the program’s result. As for the composition of effects and handlers, effects can be tagged in a composed effect and can be folded based on the tag. Effect handlers look very promising but there are questions with regard to both composability and performance.

And lastly monad-comonad pairings⁴ act as pairs of space-movement to describe computations in a GUI program. The pairing of two functors expresses the connection between the two contexts of the functors that allow them to cancel each other out in the process of interpretation to obtain a context-free value. In the case of a comonad-monad pairing the monad can peel off one layer of comonad context that it consumes to move inside the space defined by the comonad. The objections to the approach are, just as in the case of effect handlers related to performance and composition. Comonads use Comonad transformers to compose effects and transformer stacks have problems with the nesting of effect stacks.

Welcome

Hello, there! We are WhiteCity Code, a Romanian software development company. We do web, mobile, IoT and desktop development and we like to keep things interesting by dvelving into challenging projects.

We are happy to make your acquaintance!

You can expect to read here about out latest projects, Clojure, Scala, Haskell, Elm, Java, Vue.js, React, iOS, Android and Linux. We maintain ChatPiper, WhiteRCPT and Ytravel (Clojure-based).

Looking forward to you reading us!