dobesv
last posted Nov. 9, 2015, 7:13 p.m.
String formatting / interpolation
String interpolation seems like a fun language feature - that is, having a syntax like "I see ${n} apples" where a local variable n is substituted into the string at the appropriate place.
However, I think this makes localization more difficult. The python approach of putting the substitutions afterwards is probably better.
FRP is a very conceptual model for writing interactive applications but it has some challenges in efficient implementation - the memory requirements of keeping a complete or even partial history of all inputs are too great.
In lazy languages like Haskell this history might be kept accidentally because unevaluated expressions can keep references to older states.
So now FRP implementations don't give you the whole list. Instead you provide a function that the runtime applies to new events (and optionally a past and present state).
Applicative Functor
An Applicative Functor is a class which provides a pair of operations - one that lifts values into an instance of the functor, and one which lifts functions into mappings of the functor.
In a category theory sense the Applicative Functor is a functor from the language's objects and functions to the category of instances of the functor and mappings of that functor.
This is in addition to the interpretation of the Functor itself as a category theory style functor from classes (using the Functor's type constructor to translate the class) and functions (translating a function to a function that maps over instances of the functor).
Compared to CFG (control-flow graph)
- In the CFG, the procedure is broken into basic blocks, whereas in VSDG the entire procedure can be one big graph. This makes code motion simpler in VSDG as you just have to adjust the dependencies.
- In the CFG, state dependencies are explicit, so it's hard to know whether it is safe to re-order instructions inside a basic block, or basic blocks within a procedure. In VSDG the state dependency is explicit so there is more freedom to reorder code.
Interesting reading about the "helper class" as an anti-pattern. Basically this is saying that functions/static methods are an anti-pattern in Java and C#.
- http://blogs.msdn.com/b/nickmalik/archive/2005/09/06/461404.aspx
- http://blogs.msdn.com/b/nickmalik/archive/2005/09/07/462054.aspx
The recommendation is to replace a helper class with static methods, with a helper object which you get by dependency injection. Or in an even more extreme case replace the function with a new object that performs the operation.
Two kinds or partial results: failure and non-termination
Two different kinds of partial programs seem to be the most commonly discussed:
- Functions that fail because the result is undefined (division by zero, subtraction from infinity, invalid list index)
- Functions that never return (the omega function, the sum of an infinite list)
There are some functions that could fit in either category, depending on implementation.
For example, an implementation of division that doesn't check for zero in the denominator could run forever adding zero to the denominator.
For partial functions in the first category, we can easily convert them into total functions by making the return value capture the partial result. For division we can return either a quotient result or a division by zero marker. The person doing the division must check whether it was successful before continuing too far.
Partial functions that may never return, however, are a different beast. Proving that they are total is impossible to do in general in the presence of general recursion so one must restrict recursion in some way to prevent these.
Total functional programming is probably unpopular because dealing with every possible partial function explicitly is a nuisance and not being able to recurse freely can cause some code contortions to make things fit a limited recursion capability.
FRP is a very conceptual model for writing interactive applications but it has some challenges in efficient implementation - the memory requirements of keeping a complete or even partial history of all inputs are too great.
In lazy languages like Haskell this history might be kept accidentally because unevaluated expressions can keep references to older states.
So now FRP implementations don't give you the whole list. Instead you provide a function that the runtime applies to new events (and optionally a past and present state).
Church Encoding is like the Visitor Pattern
Church Encoding is like the visitor pattern, especially for booleans, lists, and so on.
Boolean is the most obvious - a Church Boolean is a function that takes two functions, one to call if the boolean is true and one to call if the boolean is false. The visitor pattern version would be for boolean to accept a visitor with two methods.
For lists there are a few alternate variations in lambda calculus, but it's not hard to imagine a visitor pattern implementation that calls back to an empty nullary visitor or a nonEmpty binary visitor method.
Many plugins don't check for errors until you save, but the Java plugin checks as you type. It schedules the build as a background job. It is quite advanced.
When you define a function inside another function, if you don't explicitly mark it as "local" it will be assigned to a global variable, i.e.
function b()
print("goodbye!")
end
function a()
function b()
print("hello!")
end
end
b() -- "goodbye!"
a() -- over-writes b
b() -- "hello!"
This is not a good thing.
Streams by this user that have been favorited by others.
Banjo
String formatting / interpolation
String interpolation seems like a fun language feature - that is, having a syntax like "I see ${n} apples" where a local variable n is substituted into the string at the appropriate place.
However, I think this makes localization more difficult. The python approach of putting the substitutions afterwards is probably better.
FRP is a very conceptual model for writing interactive applications but it has some challenges in efficient implementation - the memory requirements of keeping a complete or even partial history of all inputs are too great.
In lazy languages like Haskell this history might be kept accidentally because unevaluated expressions can keep references to older states.
So now FRP implementations don't give you the whole list. Instead you provide a function that the runtime applies to new events (and optionally a past and present state).
If an application has internal state of some sort, it can "fold" over the event stream with a subroutine taking the current internal state plus a new event to yield a new internal state.
One can imagine the output of an application as a function of its initial state plus a stream of events to produce an output. As new events occur, the function can be re-run to update the application output.
Function Reactive Programming (FRP) is a style of functional programming where an application is a function from inputs to outputs.
FRPWorks - Nu Game Engine
"The Nu Game Engine is a game development platform that aims to drastically reduce the cost of game development by providing a superior programming model for games via Iterative Functional Reactive Programming (IFRP). While the engine is still pre-1.0, the implementation has matured enough to prove both the efficacy and viability of pure functional programming in indie games in terms of performance, programmability, and reliability."
This repository hosts several projects, including -
- the Nu Game Engine
- a cross-platform F# 2D game engine built in the functional style. Uses SDL2 and Farseer Physics.
- the small but potentially useful F# code library Prime (interesting features, but lacks unit tests).
- the sample game BlazeVector.
Links:
Sly FRP
Sly is a free software game engine written in Guile Scheme. It provides an abstraction layer above SDL and OpenGL for common game programming requirements such as:
- Animation
- Shaders
- Sprites
- Tilesets
- Scene graph
- Keyboard/mouse/joystick input
- Scripting
Sly differentiates itself from most other game engines by encouraging live coding and emphasizing functional reactive programming.
As of August 2015, seems to be under active development.
Links:
Type should not change the meaning of expressions
In Scala, types often change the meaning of something. For example, if you assign a expression into a lazy method parameter it's automatically made into a thunk. If you call a method that takes no parameters, the parens are optional. I think this is a bad idea ... it's extra complexity.
In Haskell, too, the static type environment is used to resolve type-class invokations. This includes the expected target type of the expression. I think this is a lot of complexity to consider when reading code - you have to not only know the type of an expression, but also the type expected of that expression by whatever it is being passed to.
In Banjo I want to keep it relatively simple. There's no overloading based on static parameter types or return types, only the actual runtime value matters for resolving a slot value, just like in Javascript and other dynamic languages.
FRP Now!
I'm not sure I understand everything but my rough understanding of FRPNow! is ...
Rather than model events always as a stream of events as in most other FRP papers I have read, they consider events individually as a sort of future or promise. The Event acts in many ways like a Behavior of Maybe and they even provide a function "fromJust" which converts a Behavior of Maybe to an Event.
When an async operation starts, the Event is marked as not having occurred yet and having neither time nor value (or infinite future time and undefined value). When the async operation completes, the Event is marked complete and has a timestamp and value.
To create an event stream ala Classic FRP events, they can start with an initial event (say, "read keyboard") and then "unfold" the stream so that the "tail" of the stream is a behavior that depends on the "head" of stream being already available and re-runs the same IO operation over and over.
Behaviors are actually modeled in terms of events - there's the "current" value and an Event for the "future" behavior which will have a new current value and a new Event for the future (recursively).
The rest of the work seems to be how to make this model work efficiently in Haskell without space leaks, which does seem to introduce a fair amount of incidental complexity.
Links:
Debugging by beta expansion
One idea I've had for debugging in a pure language would be to back-trace the computation of a value.
For example if you're looking in the reactor at a value, while debugging it could be annotated with the actual function call that produced it. So you could expand that value into a function call ... and the look at its arguments and possibly expand one or more of them to work your back to where there might have been a problem. It wouldn't have to run in this mode all the time ... it should be possible to "re-run" the last frame in this mode to yield these annotated values instead of the usual vanilla values.
Python FRP
Another interesting paper about FRP in Python:
http://www.cs.jhu.edu/~roe/padl2014.pdf
Abstract. We present our experiences integrating Functional Reactive Programming (FRP) into a new host language, Python, and a variety of computational contexts: a game engine, a GUI system, and an embedded controller. We demonstrate FRP principles extended to a dynamic environment and the integration of object-oriented libraries into the reactive environment. A number of FRP semantic issues are addressed in a straight-forward way to produce an elegant combination of FRP and object-oriented programming. In particular, reactive proxies integrate traditional objects with the reactive world and event-triggered reactors allow reconfiguration of the network of reactive proxies and interaction with the outside world. This work demonstrates that FRP can serve as a unifying framework that simplifies programming and allows novices to build reactive systems. This system has been used to develop a wide variety of game programs and reactive animations in a summer camp which introduces programming concepts to teenagers.
Fran
One of Conal Elliot's first implementations of FRP in Haskell:
http://conal.net/fran/tutorial.htm
Fran stands for "Functional Reactive Animation".
Applicative Functor
An Applicative Functor is a class which provides a pair of operations - one that lifts values into an instance of the functor, and one which lifts functions into mappings of the functor.
In a category theory sense the Applicative Functor is a functor from the language's objects and functions to the category of instances of the functor and mappings of that functor.
This is in addition to the interpretation of the Functor itself as a category theory style functor from classes (using the Functor's type constructor to translate the class) and functions (translating a function to a function that maps over instances of the functor).
Functor
A functor is a container-like data structure that allows one to apply a function to all its contents.
That is, for a list or an option type, the map operation returns a new list or option where the given function was applied to the contents of the object.
Or, looking at it another way, you can compose a "functor" with a function such that any value that "come out" of the data structure are passed through the function of your choice. From this perspective the data structure is used like a (partial) function composed with another function.
Input APIs can look synchronous
An FRP I/O read can be considered referentially transparent if reads are repeatable; that is, the data you read is treated as a snapshot, and multiple (filesystem/network) reads from the same snapshot return the same value. Then only writes need to be handled as procedural.
Time, or some snapshot identifier, must be a parameter to the read operation for this to actually be referentially transparent.
Monadic FRP
Monadic FRP is an alternative approach to FRP, sample implementation in Haskell.
http://homepages.cwi.nl/~ploeg/sfrpdocs/
Note that FRPNow! (below) is the successor to this paper.
Flux Architecture
Facebook has been teaching about the Flux architecture it uses for web apps, which is kind of FRP-based. Some useful ideas there for how applications / games can be structured.
Compared to CFG (control-flow graph)
- In the CFG, the procedure is broken into basic blocks, whereas in VSDG the entire procedure can be one big graph. This makes code motion simpler in VSDG as you just have to adjust the dependencies.
- In the CFG, state dependencies are explicit, so it's hard to know whether it is safe to re-order instructions inside a basic block, or basic blocks within a procedure. In VSDG the state dependency is explicit so there is more freedom to reorder code.
Optimizing Compilation with the VSDG - by Alan C. Lawrence
This technical report describes in detail the VSDG, the PDG (program dependence graph), and CFG (control-flow graph) program representations. It describes a way to generate a PDG from a VSDG, and a CFG from a PDG, resulting in a linear program from a VSDG.
The Value State Dependence Graph (VSDG) is a high-level intermediate representation for software procedures. It represents values as having an operation plus inputs plus a virtual "state" input used to ensure the ordering of side-effects is explicitly maintained. It makes many optimizations simple, but is very difficult to convert into linear code efficiently.
FRP as an end-to-end web solution
One interesting area of exploration is the use of FRP / SAC for web applications. If one could respond to changes to the database and user inputs in a reactive manner and send down to the web client just enough information to update the current display, that would seem to be a very advanced and efficient manner of operation.
Kawa's approach to quantities and binary arithmetic
http://www.gnu.org/software/kawa/internals/numbers.html
Kawa is a scheme dialect with the Scheme numerical tower enhanced with support for units of measure.
For binary operators, Kawa calls a method of the left-hand object. That object tries to see if it has been given an object type it recognises; if not, it will fallback to calling a "reversed" version on the right-hand side. The "reversed" version should not fall back yet again.
Froc
Froc is a library for functional reactive programming in OCaml.
The interface is similar to FrTime and FlapJax, but (of course) typed, implementing a monad of changeable values. The implementation is data-driven, using the dynamic dependency graphs of Acar et al.’s self-adjusting computation.
Froc can be used with ocamljs, and with the included froc-dom library can be used for web browser programming.
And an article on "How Froc Works":
http://ambassadortothecomputers.blogspot.ca/2010/05/how-froc-works.html
Functional Reactive Programming in Scheme with guile-2d
http://dthompson.us/functional-reactive-programming-in-scheme-with-guile-2d.html
Intro to FRP Slides
Edward Amsden's slides talking about FRP, for those new to the subject:
Continuation-based FRP in Haskell
A simple FRP implementation in Haskell using continuations:
http://www.paolocapriotti.com/blog/2012/06/04/continuation-based-relative-time-frp/
FRP Performance Trade-Offs
For FRP (and self-adjusting computation), performance and memory usage depends on many factors.
In order to be successful, an FRP system must be able to tune and optimize these aspects of the program to strive towards having the same performance characteristics as an application where updates are processed by hand by a programmer.
Signal Granularity
In the simplest form, the whole program can be re-run completely on every update. In this case there may be some inefficiency as some values will be recomputed unnecessarily. Also, if events are represented as streams, then the entire history of events might be reprocessed. This is the original approach to implementing Classic FRP, also referred to as "pull FRP". The drawback here is that recomputing everything becomes too slow.
On the other side of the spectrum, every calculated value might be a separate signal / subprogram and only the values that depend on a changed input are recalculated on an update. However, in this case there is a very high overhead in keeping track of every intermediate value and its dependents, typically exceeding the savings had from avoiding unnecessary computation. This is more like the initial implementation of FrTime, it might be referred to referred to as "push FRP".
More recent works in FRP try to find a way to combine and balance the push and pull approach, typically by making the programmer manually specify which is which (as in Elm) or by matching it to some existing boundary, like a function boundary (in the lowering transformation for FrTime).
Signal Dependencies / Evaluation Strategy
As part of slicing a program into signals, there is some flexibility available in terms of how a computation can be broken down into steps (sequentialization) or signals (dependency analysis).
For example, if the application performs a transformation of each element of a list and returns a new list, the elements of the new list could depend on the entire input list (corresponding to an eager evaluation strategy) or only on the corresponding element in the input list (corresponding to a lazy evaluation strategy).
A more lazy evaluation strategy should reduce the cost of an incremental update, but it may also result in a higher memory overhead to keep cached values and dependencies.
Why "folding over event streams" makes sense in FRP
I just had a light-bulb go off about why folding over a list would work as a way to deal with events in FRP.
The reason is this - the FRP implementation is conceptually updating the list of events, and recomputing only the part of the list affected by the change (i.e. the tail of the list). However, the fold doesn't keep track of past parts of the list, and the runtime also need only remember the tail of list so it can update it, so those old events in the list can be garbage collected (in theory) since there are no references to them.
Conal Elliott
Conal coined the term FRP and has been developing this style of programming since a long time ago, at least at Microsoft developing ActiveVRML in 1996.
He has mainly done FRP implementation embedded in Haskell, such as Fran and Reactive.
You can read his blog here: http://conal.net/
LuaGravity
LuaGravity is a reactive version of Lua. It's not actually FRP because lua is a procedural language, but interesting nevertheless.
https://thesynchronousblog.wordpress.com/2008/08/17/a-first-glance-at-luagravity/
FrTime
FrTime (aka "Father Time") is a Scheme / Racket dialect that automatically updates outputs that depend on time-varying inputs. It does this by changing the program to monitor what signals are used during the evaluation of a given expression and constructing a dynamic dependency graph from that.
Then, it updates the inputs based on events and those updates are propagated through the dependency graph to update the outputs.
Links:
- Embedding Dynamic Dataflow in a Call-by-Value Language http://cs.brown.edu/~sk/Publications/Papers/Published/ck-frtime/
- FrTime: Functional Reactive Programming in PLT Scheme http://cs.brown.edu/research/pubs/techreports/reports/CS-03-20.html
Elm
Elm is a programming language / system based on Functional Reactive Programming that has been making some headway:
The Elm language is an eager, pure, statically typed, functional language with syntax based mainly on Haskell.
In Elm you explicitly construct a Signal graph and return it back to the runtime for interpretation; the signal graph does not change while the application is running.
Adaptive Functional Programming / Self-Adjusting Computation
AFP / Self-Adjusting Computation is closely related to FRP - the outputs are adjusted in response to changes in the inputs. This is very similar to the way FrTime works.
- Self-Adjusting Computation - Umut Acar (2005) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.7647&rep=rep1&type=pdf
- Adaptive Function Programming - Umut Acar (2002) http://www.cs.cmu.edu/~blelloch/papers/ABH06.pdf
- A Proposal for Parallel Self-Adjusting Computation - Matthew Hammer, Umut Acar (2007) https://www.cs.umd.edu/~hammer/papers/damp07.pdf
- Self-Adjusting Machines http://www.cs.umd.edu/~hammer/selfadjmachines/self-adjusting-machines--hammer2012.pdf
- More papers and implementations for C and ML here: http://www.umut-acar.org/self-adjusting-computation
Re-frame (ClojureScript)
An FRP library for ClojureScript, the ReadMe has a lot of good links about FRP.
Inverse dependency graph
In FrTime (and probably other FRP systems) an inverse depedency graph is used to update signals efficiently. When an event occurs, new values are inserted into the signals at the root of the (inverse) graph - if a signal's value has changed, any signals that depend on that signal will also be updated, propagating all the way to the leaves of that inverse dependency graph. Finally, the runtime can observe the new values of those final signals to update the outside world.
Thoughts by this user that have been liked by others.
Elm
Elm is a programming language / system based on Functional Reactive Programming that has been making some headway:
The Elm language is an eager, pure, statically typed, functional language with syntax based mainly on Haskell.
In Elm you explicitly construct a Signal graph and return it back to the runtime for interpretation; the signal graph does not change while the application is running.
Why "folding over event streams" makes sense in FRP
I just had a light-bulb go off about why folding over a list would work as a way to deal with events in FRP.
The reason is this - the FRP implementation is conceptually updating the list of events, and recomputing only the part of the list affected by the change (i.e. the tail of the list). However, the fold doesn't keep track of past parts of the list, and the runtime also need only remember the tail of list so it can update it, so those old events in the list can be garbage collected (in theory) since there are no references to them.
Intro to FRP Slides
Edward Amsden's slides talking about FRP, for those new to the subject: