What if I told you that a spreadsheet could be a library instead of an application? What would that even mean? How do we distill the logic behind spreadsheets into a reusable abstraction? My mvc-updates
library answers this question by bringing spreadsheet-like programming to Haskell using an intuitive Applicative
interface.
The central abstraction is an Applicative
Updatable
value, which is just a Fold
sitting in front of a Managed
Controller
:
data Updatable a =
forall e . On (Fold e a) (Managed (Controller e))
The Managed
Controller
originates from my mvc
library and represents a resource-managed, concurrent source of values of type e
. Using Monoid
operations, you can interleave these concurrent resources together while simultaneously merging their resource management logic.
The Fold
type originates from my foldl
library and represents a reified left fold. Using Applicative
operations, you can combine multiple folds together in such a way that they still pass over the data set just once without leaking space.
To build an Updatable
value, just pair up a Fold
with a Managed
Controller
:
import Control.Foldl (last, length)
import MVC
import MVC.Updates
import MVC.Prelude (stdinLines, tick)
import Prelude hiding (last, length)
-- Store the last line from standard input
lastLine :: Updatable (Maybe String)
lastLine = On last stdinLines
-- Increment every second
seconds :: Updatable Int
seconds = On length (tick 1.0)
What's amazing is that when you stick a Fold
in front of a Controller
, you get a new Applicative
. This Applicative
instance lets you combine multiple Updatable
values into new derived Updatable
values. For example, we can combine lastLine
and seconds
into a single data type that tracks updates to both values:
import Control.Applicative ((<$>), (<*>))
data Example = Example (Maybe String) Int deriving (Show)
example :: Updatable Example
example = Example <$> lastLine <*> seconds
example
will update every time lastLine
or seconds
updates, caching and reusing portions that do not update. For example, if lastLine
updates then only the first field of Example
will change. Similarly, if seconds
updates then only the second field of Example
will change.
When we're done combining Updatable
values we can plug them into mvc
using the updates
function:
updates :: Buffer a -> Updatable a -> Managed (Controller a)
This gives us back a Managed
Controller
we can feed into our mvc
application:
viewController :: Managed (View Example, Controller Example)
viewController = do
controller <- updates Unbounded example
return (asSink print, controller)
model :: Model () Example Example
model = asPipe $
Pipes.takeWhile (\(Example str _) -> str /= Just "quit")
main :: IO ()
main = runMVC () model viewController
This program updates in response to two concurrent inputs: time and standard input.
$ ./example
Example Nothing 0
Test<Enter>
Example (Just "Test") 0 <-- Update: New input
Example (Just "Test") 1 <-- Update: 1 second passed
Example (Just "Test") 2 <-- Update: 1 second passed
ABC<Enter>
Example (Just "ABC") 2 <-- Update: New input
Example (Just "ABC") 3 <-- Update: 1 second
quit<Enter>
$
Spreadsheets
The previous example was a bit contrived, so let's step it up a notch. What better way to demonstrate spreadsheet-like programming than .. a spreadsheet!
I'll use Haskell's gtk
library to set up the initial API, which consists of a single exported function:
module Spreadsheet (spreadsheet) where
spreadsheet
:: Managed -- GTK setup
( Updatable Double -- Create input cell
, Managed (View Double) -- Create output cell
, IO () -- Start spreadsheet
)
spreadsheet = ???
You can find the full source code here.
Using spreadsheet
, I can now easily build my own spread sheet application:
{-# LANGUAGE TemplateHaskell #-}
import Control.Applicative (Applicative, (<$>), (<*>))
import Lens.Family.TH (makeLenses)
import MVC
import MVC.Updates (updates)
import Spreadsheet (spreadsheet)
-- Spreadsheet input (4 cells)
data In = I
{ _i1 :: Double
, _i2 :: Double
, _i3 :: Double
, _i4 :: Double
}
-- Spreadsheet output (4 cells)
data Out = O
{ _o1 :: Double
, _o2 :: Double
, _o3 :: Double
, _o4 :: Double
}
makeLenses ''Out
-- Spreadsheet logic that converts input to output
model :: Model () In Out
model = asPipe $ loop $ \(I i1 i2 i3 i4) -> do
return $ O (i1 + i2) (i2 * i3) (i3 - i4) (max i4 i1)
main :: IO ()
main = runMVC () model $ do
(inCell, outCell, go) <- spreadsheet
-- Assemble the four input cells
c <- updates Unbounded $
I <$> inCell <*> inCell <*> inCell <*> inCell
-- Assemble the four output cells
v <- fmap (handles o1) outCell
<> fmap (handles o2) outCell
<> fmap (handles o3) outCell
<> fmap (handles o4) outCell
-- Run the spread sheet
liftIO go
return (v, c)
You can install this program yourself by building my mvc-updates-examples
package on Github:
$ git clone https://github.com/Gabriel439/Haskell-MVC-Updates-Examples-Library.git
$ cd Haskell-MVC-Updates-Examples-Library
$ cabal install
$ ~/.cabal/bin/mvc-spreadsheet-example
Or you can watch this video of the spreadsheet in action:
The key feature I want to emphasize is how concise this spreadsheet API is. We provide our user an Applicative
input cell builder and a Monoid
output cell builder, and we're done. We don't have to explain to the user how to acquire resources, manage threads, or combine updates. The Applicative
instance for Updatable
handles all of those trivial details for them. Adding extra inputs or outputs is as simple as chaining additional inCell
and outCell
invocations.
Reactive animations
We don't have to limit ourselves to spread sheets, though. We can program Updatable
graphical scenes using these same principles. For example, let's animate a cloud that orbits around the user's mouse using the sdl
library. Just like before, we will begin from a concise interface:
-- Animation frames for the cloud
data Frame = Frame0 | Frame1 | Frame2 | Frame3
-- To draw a cloud we specify the frame and the coordinates
data Cloud = Cloud Frame Int Int
-- mouse coordinates
data Mouse = Mouse Int Int
sdl :: Managed -- SDL setup
( View Cloud -- Draw a cloud
, Updatable Mouse -- Updatable mouse coordinates
)
The full source is located here.
In this case, I want to combine the Updatable
mouse coordinates with an Updatable
time value:
main :: IO ()
main = runMVC () (asPipe cat) $ do
(cloudOut, mouse) <- sdl
let seconds = On length (tick (1 / 60))
toFrame n = case (n `div` 15) `rem` 4 of
0 -> Frame0
1 -> Frame1
2 -> Frame2
_ -> Frame3
cloudOrbit t (Mouse x y) = Cloud (toFrame t) x' y'
where
x' = x + truncate (100 * cos (fromIntegral t / 10))
y' = y + truncate (100 * sin (fromIntegral t / 10))
cloudIn <- updates Unbounded (cloudOrbit <$> seconds <*> mouse)
return (cloudOut, cloudIn)
cloudOrbit
is defined as a pure function from the current time and mouse coordinates to a Cloud
. With the power of Applicative
s we can lift this pure function over two Updatable
values (mouse
and seconds
) to create a new Updatable
Cloud
that we pass intact to our program's View
.
Like before, you can either run this program yourself:
$ git clone https://github.com/Gabriel439/Haskell-MVC-Updates-Examples-Library.git
$ cd Haskell-MVC-Updates-Examples-Library
$ cabal install
$ ~/.cabal/bin/mvc-spreadsheet-example
... or you can watch the video:
Under the hood
mvc-updates
distinguishes itself from similar libraries in other languages by not relying on a semantics for concurrency. The Applicative
instance for Updatable
uses no concurrent operations, whatsoever:
instance Applicative Updatable where
pure a = On (pure a) mempty
(On foldL mControllerL) <*> (On foldR mControllerR)
= On foldT mControllerT
where
foldT = onLeft foldL <*> onRight foldR
mControllerT = fmap (fmap Left ) mControllerL
<> fmap (fmap Right) mControllerR
onLeft (Fold step begin done) =
Fold step' begin done
where
step' x (Left a) = step x a
step' x _ = x
onRight (Fold step begin done) =
Fold step' begin done
where
step' x (Right a) = step x a
step' x _ = x
In fact, this Applicative
instance only assumes that the Controller
type is a Monoid
, so this trick generalizes to any source that forms a Monoid
.
This not only simplifies the proof of the Applicative
laws, but it also greatly improves efficiency. This Applicative
instance introduces no new threads or buffers. The only thread or buffer you will incur is in the final call to the updates
function, but expert users can eliminate even that overhead by inlining the logic of the updates
function directly into their mvc
program.
Lightweight
The mvc-updates
library is incredibly small. Here's the entire API:
data Updatable = forall e . On (Fold e a) (Controller e)
instance Functor Updatable
instance Applicative Updatable
updates :: Buffer a -> Updatable a -> Managed (Controller a)
The library is very straightforward to use:
- Build
Updatable
values - Combine them using their
Applicative
instance - Convert them back to a
Managed
Controller
when you're done
That's it!
The small size of the library is no accident. The Updatable
abstraction is an example of a scalable program architecture. When we combine Updatable
values together, the end result is a new Updatable
value. This keeps the API small since we always end up back where we started and we never need to introduce additional abstractions.
There is no need to distinguish between "primitive" Updatable
values or "derived" Updatable
values or "sheets" of Updatable
values. The Applicative
interface lets us unify these three concepts into a single uniform concept. Moreover, the Applicative
interface is one of Haskell's widely used type classes inspired by category theory, so we can reuse people's pre-existing intuition for how Applicative
s work. This is a common theme in Haskell where once you learn the core set of mathematical type classes they go a very, very long way.
Conclusion
Hopefully this post will get you excited about the power of Applicative
programming. If you would like to learn more about Applicative
s, I highly recommend the "Applicative Programming with Effects" paper by Conor McBride and Ross Paterson.
I would like to conclude by saying that there many classes of problems that the mvc-updates
library does not solve well, such as:
- build systems,
- programs with computationally expensive
View
s, and: Updatable
values that share state.
However, mvc-updates
excels at:
- data visualizations,
- control panels, and:
- spread sheets (of course).
You can find the mvc-updates
library up on Hackage or on Github.
Look up constraint programming... :-)
ReplyDeleteI'm a little bit familiar with constraint programming, but the main thing I look for in a programming paradigm are programming interfaces inspired by category theory or abstract algebra (i.e. monoids, functors, categories, etc.). Are there analogs of that in constraint programming?
DeleteConstraint programming systems show you that "spreadsheets" can be implemented (simply) as libraries without the need for any of category theory or abstract algebra.
DeleteSo these don't add anything substantive here, apart from pleasing your personal palate (which is a perfectly fine thing to do).
I don't use mathematics for the sake of using mathematics. The purpose behind structuring programs mathematically is to compose small bits of mathematical functionality, each of which is correct in isolation, to build larger mathematical structures which are still correct.
DeleteSure, you can always whip up some specialized and non-mathematical solution, but these will rarely generalize to more complex problems well. They will usually solve some very specific problem very well, but the moment you deviate from the problem it was intended to solve it will become very brittle.
Even the very example you give (constraint programming systems) demonstrates this issues. Constraint programming lacks the resource management sophistication of `mvc-updates`, where as you combine updatable values it automatically merges their resource management logic, and it's not clear to me how I would extend it with this feature, whereas with `mvc-updates` it was trivial because it took the principled approach.
No one cares about constraint programming. Nice article though.
DeleteThis comment has been removed by the author.
Delete@Russel: considering that Gabriel implemented spreadsheet-like programming (and spreadsheet = one-way dataflow constraints), I'd say at least one person cares about constraint programming, enough to do a (somewhat simplistic) implementation.
DeleteThen there are the million plus iOS/Mac programmers using AutoLayout and KVO/Bindings. AutoLayout is based on the Cassowary constraint solver, KVO/Bindings is equivalent to a simple one-way constraint solver (without formulae)
And finally, spreadsheets are the most wide-spread form of programming, and again, spread-sheets = one-way dataflow constraints.
So you have a funny definition of "nobody" :-)
@Gabriel: what do you mean with "resource management"? Considering the wide variety of constraint systems, are you certain that none have this? In fact, mvc-updates seems quite limited compared to most constraint systems I am aware of.
This comment has been removed by the author.
ReplyDeleteLooks great! I don't understand it yet, but I will, soon! ;)
ReplyDeleteHas anyone went so far and implemented a spreadsheet app (expanding on your example)? I would like to do that because I always wanted to have my own light-version of Excel.
Also it seems, there are similarities to functional reactive programming (maybe solving similar problems).
Nobody has implemented an actual spread sheet application on top of this yet.
DeleteThere are some similarities to functional reactive programming. This answer on Stack Overflow was part of the inspiration for this library (and the second example):
http://stackoverflow.com/a/1028642/1026598
Gabriel, you say that mvc-updates "excel at spread sheets" but as far as I see it deals only with finite and fixed number of Updatables which does not look like spread sheets which could contain variable and possibly huge number of cells.
ReplyDeleteAm I correct at that of if I'm wrong how could you model variable number of updatables using mvc-updates? Or maybe there is something outside of this library which could make it possible in some comparatively easy way?
BTW Thanks for all your writings - I (and probably many others too) get a lot from reaging them.
You can model a variable number of updatables if they all store the same type of value. For example, assuming you have a sequence of updatable values of type:
Deleteexample :: Seq (Updatable a)
... you can turn that into an updatable sequence of values by using `Data.Traversable.sequenceA`:
sequenceA example :: Updatable (Seq a)
Under the hood this will generate a minimal update tree where each primitive update of an `a` triggers O(log N) downstream updates to build the new `Seq a`, where N is the size of the original sequence.
The reason I use `Seq` instead of list is because it has a much more efficient implementation of `sequenceA`.