FSharp.Data.Adaptive


FSharp.Data.Adaptive: adaptive data for F#

This library provides a simple yet powerful way to write incremental functional computations that can be connected to imperative sources on both input and output.

Examples include:

FSharp.Data.Adaptive focuses on 'adaptive values' and 'adaptive data' rather than reactive events.

Adaptive Values

Adaptive values (aval) are similar to cells in Excel spreadsheets. Consider a physics simulation such as the time taken for a ball to fall from a particular height. If you like think of sqrt (2.0 * height / gravity) as a formula in an Excel spreadsheet, where height and gravity are the names of other cells. The functional and adaptive forms are:

let timeToFloor height gravity = 
    sqrt (2.0 * height / gravity)

let adaptiveTimeToFloor height gravity =
    AVal.map2 (fun h g -> sqrt (2.0 * h / g)) height gravity

The AVal.map2 is glue to connect this formula to other cells, producing a new cell.

Now let's define the cells height and gravity, make them changeable (cval), that is, user-editable. Initially the inputs contain the values on Earth:

let height  = cval 10.0
let gravity = cval 9.81
let dropTime = adaptiveTimeToFloor height gravity

We can now observe the result of the output 'cell':

printfn "%.3fs" (AVal.force dropTime) // => 1.428s

The user (or something else in the system) can now adjusts the changeable inputs to the values for the moon:

transact (fun () -> gravity.Value <- 1.62)
printfn "%.3fs" (AVal.force dropTime) // => 3.514s

And now adjust to a height of 2000m on Jupiter:

transact (fun () ->
    gravity.Value <- 24.79
    height.Value <- 2000.0
)
printfn "%.3fs" (AVal.force dropTime) // => 12.703s

This example feels a lot like an Excel calculation, in which dependent cells get updated whenever changeable inputs change. Some important differences are

  1. All 'cells' are adaptive values
  2. 'Cells' are first-class values
  3. Changeable 'cells' are distinguished from computed
  4. In the above, each 'cell' gets named explcitly in program code, rather than using implicit naming on a sheet
  5. Some glue like AVal.map2 is needed to connect cells

  6. User code is responsible for making changes using transact

  7. Re-calc happens on-demand as outputs are observed

Some API elements you have seen so far are:

  • aval Adaptive Value. Adaptive cell whose value purely depends on other adaptive cells.
  • map map2 map3 Create a new aval whose value depends on the one (two, three) input aval(s).
  • cval Changeable Value. Adaptive cell whose value can be manually set. A cval is also an aval.
  • transact Set a cval's value within this scope.
  • force Read an aval's value.

Adaptive Collections

Cells in an Excel spreadsheet can only contain an individual value. What if a 'cell' could be an entire set, array, list or table? And what if the user makes incremental modifications to such a cell, adding a row, deleting a selection of elements and so on? Would the rest of the spreadsheet adjust to this incremental change in the collection, or would dependent cells recalculate over the entire new collection?

As seen in the examples above aval<'T> and cval<'T> are containers for single values that may change adaptively. A natural way of handling collections of values would be aval<Set<'T>>. However, this forces recalculation by iterating the entire collection. For example, a mapping function on the set would look like this:

let map (mapping: 'T1 -> 'T2) (set : aval<Set<'T1>>) =   
    set |> AVal.map (Set.map mapping)

Note the use of Set.map means that mapping will be executed for all elements of the set even if just a single element changes.

Instead, you use adaptive collections:

  • cset/ChangeableHashSet Adaptive modifiable input set.
  • aset/AdaptiveHashSet Adaptive set. Content depends on other adaptive cells.

Adaptive sets work on deltas instead of values. Here's an example illustrating asets:

let inputSet = cset [1;2;3]
let dependentSet =
    inputSet |> ASet.map (fun v -> printf "map %d, " v; v * 2)

printfn "%A" (AVal.force dependentSet.Content) // => map 1, map 2, map 3, HashSet [2; 4; 6]

We create an aset and specify a mapping function on the elements. The mapping is evaluated for each element individually, as illustrated by the three "map" prints.

Let's add an element to the set.

transact (fun () -> inputSet.Add 0)
printfn "%A" (AVal.force dependentSet.Content) // => map 0, HashSet [0; 2; 4; 6]

The mapping function is evaluated only once, for the newly added element! aset is an incremental data structure on the level of its contained elements.

transact (fun () -> inputSet.Remove 2)
printfn "%A" (AVal.force dependentSet.Content) // => HashSet [0; 2; 6]

There is no "map" print - the removal did not trigger an evaluation of the mapping function!

In addition to the unordered set, we also have implementations of the ordered list, called alist, and the key-value map, called amap.

Dynamic computation graphs and dynamic dependencies

An Excel spreadsheet has a static structure of cells with static dependencies. The API becomes more interesting when dynamic dependencies come into play. That is, adaptive values can dynamically decide whether or not to depend on something based on their content.

As an example, let's extend our computation by calculating the height of our ball at a certain point in time.

// simple utility calculating the height
let calcHeight (t : float) (h0 : float) (g : float) =
    printf "height after %.3fs: " t
    h0 - 0.5*g*t*t

let time = cval 0.5

let currentHeight = AVal.map3 calcHeight time height gravity
printfn "%.3fm" (AVal.force currentHeight) // => height after 0.500s: 1996.901m
printfn "%.3fm" (AVal.force currentHeight) // => 1996.901m
printfn "%.3fm" (AVal.force currentHeight) // => 1996.901m

Note that we snuck a little "height after" print into the utility calculation. This is for illustrative purposes: observe how the print occurs only when currentHeight needs to re-calculate its value. It happens only at initial calculation or when one of its inputs changes!

But, oh no! Someone could enter an invalid time (let's say -100s)!

transact (fun () -> time.Value <- -100.0)
printfn "%.3fm" (AVal.force currentHeight) // => height after -100.000s: -121950.000m  

We'd like to prevent that!

Let's rewrite the code using a dynamic dependency.

let currentHeightSafe =
    adaptive { 
        let! t = time
        if t <= 0.0 then 
            // whenever the time is negative the ball will just report its initial height.
            return! height :> aval<_>
        else
            // when the time is positive we use our utility to calculate the height at the current time.
            return! AVal.map2 (calcHeight t) height gravity
    }

printfn "%.3fm" (AVal.force currentHeightSafe) // => 2000.000m

The content of currentHeightSafe is now 2000.0, since our time is still negative and we decide to return the content of height. Observe the fact that there is no "height after" print! There's no need to run our utility calculation at this time.

What happens if we change the gravity back to earth?

transact (fun () -> gravity.Value <- 9.81)
printfn "%.3fm" (AVal.force currentHeightSafe) // => 2000.000m

Nothing changed, since currentHeightSafe currently does not depend on gravity. There is no "height after" print!

Okay, set the height to 10m again.

transact (fun () -> height.Value <- 10.0)
printfn "%.3fm" (AVal.force currentHeightSafe) // => 10.0m

Our value of currentHeightSafe got updated to represent the new value of height. There is still no "height after" print!

Finally, let's set the time to a positive value again.

transact (fun () -> time.Value <- 1.42785)
printfn "%.3fm" (AVal.force currentHeightSafe) // height after 1.428s: 0.000m

And there's our "height after" print. We decided to depend on the utility calculation again.

  • bind Create a dynamic dependency. The resulting aval may dynamically decide on which avals to depend.
  • Dependency graph. A chain of dependent avals.
  • Dynamic dependency graph. A dependency graph that includes dynamic dependencies.

This simple example demonstrates the capacity of avals to express dynamic dependency graphs. In this example, the system knew exactly that currentHeightSafe didn't depend on gravity/height as long as time was negative. As soon as time became positive, the system precisely maintained the resulting structure of the dependencies.

The advantage is immediately clear: If the dependencies contained heavyweight computations, the system ensures only the minimal amount of effort is expended for updates whenever a result is requested. Traditional reactive programming libraries typically struggle to model dynamic dependency graphs, but adaptive embraces them as its core motivation.

Implementation Details

Changeable, Adaptive and Constant

cval<'T> and cset<'T> also implement the unifying type aval<'T> and aset<'T> respectively. The changeable values can be used in places where adaptive value are expected (as seen in the example above). This helps the API to look nice.

The system distinguishes between two different kinds of objects:

Changeable input values, which are prefixed with the letter c (e.g. cval<'T>, cset<'T>), and can imperatively be modified by user-code.

And Dependent values, which are prefixed with the letter a (e.g. aval<'T>, aset<'T>). These cannot directly be modified but instead depend on other adaptive values.

Internally, there is a third kind of adaptive value: The constant value, which can never be changed. In our system these are not expressed on the type-level, but instead expose a property IsConstant. All combinators correctly propagate constants in the dependency graph (when possible) and therefore:

let shouldBeConstant = AVal.constant 5 |> AVal.map (fun v -> v * 10)
printfn "%A" (AVal.force shouldBeConstant)  // ==> 50
printfn "%A" shouldBeConstant.IsConstant // => true

Whenever values are not constant, combinators like AVal.map internally build a dependency graph that keeps track of dependencies between cells. This dependency graph is used to find out what needs to be re-computed whenever changes are fed into the system.

Supplying changes to changeable cells can be done using transact : (unit -> 'T) -> 'T. The function makes the dependency graph consistent according to the nature and scope of the changes.

Evaluation strategy, avoidance of re-execution

Our system uses a push-pull evaluation strategy, meaning that evaluation will (by default) be lazy. This is achieved via eagerly marking all affected values as outOfDate, and lazily making them upToDate whenever they're evaluated. We opted for lazy evaluation since it causes unneeded parts of the dependency graph to impose virtually no runtime overhead. Lazy evaluation also allows us to support (limited) concurrency in the system.

On the downside, the marking process (performed by transact) needs to mark all potentially affected values as outOfDate, even if their resulting value has not changed. However, we did our best to avoid re-execution of unchanged functions. Here's an example illustrating our system's behaviour in such a circumstance:

let someInput = cval 10
let someOutput = 
    someInput 
    |> AVal.map (fun v -> printf "%d %% 2 => " v; v % 2)
    |> AVal.map (fun v -> printf "%d * 10 => " v; v * 10)

printf "%A: " someOutput.OutOfDate; printfn "%A" (AVal.force someOutput) // => true: 10 % 2 => 0 * 10 => 0
transact (fun () -> someInput.Value <- 12)
printf "%A: " someOutput.OutOfDate; printfn "%A" (AVal.force someOutput) // => true: 12 % 2 => 0

Note that the v * 10 function doesn't get executed after the change, even though its result has been marked outOfDate. The system understood that the output wouldn't have changed either way.

Multiple items
namespace FSharp

--------------------
namespace Microsoft.FSharp
Multiple items
namespace FSharp.Data

--------------------
namespace Microsoft.FSharp.Data
namespace FSharp.Data.Adaptive
val timeToFloor: height: float -> gravity: float -> float
val height: float
val gravity: float
val sqrt: value: 'T -> 'U (requires member Sqrt)
<summary>Square root of the given number</summary>
<param name="value">The input value.</param>
<returns>The square root of the input.</returns>
<example id="log-example"><code lang="fsharp"> sqrt 2.0 // Evaluates to 1.414213562 sqrt 100.0 // Evaluates to 10.0 </code></example>
val adaptiveTimeToFloor: height: aval<float> -> gravity: aval<float> -> aval<float>
val height: aval<float>
val gravity: aval<float>
Multiple items
module AVal from FSharp.Data.Adaptive.CollectionExtensions

--------------------
module AVal from FSharp.Data.Adaptive
<summary> Operators related to the aval&lt;_&gt; type </summary>
val map2: mapping: ('T1 -> 'T2 -> 'T3) -> value1: aval<'T1> -> value2: aval<'T2> -> aval<'T3>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val h: float
val g: float
val height: cval<float>
type cval<'T> = ChangeableValue<'T>
<summary> Represents an adaptive value that can be changed by application code and Used in dependency-aware computations. </summary>
val gravity: cval<float>
val dropTime: aval<float>
val printfn: format: Printf.TextWriterFormat<'T> -> 'T
<summary>Print to <c>stdout</c> using the given format, and add a newline.</summary>
<param name="format">The formatter.</param>
<returns>The formatted result.</returns>
<example>See <c>Printf.printfn</c> (link: <see cref="M:Microsoft.FSharp.Core.PrintfModule.PrintFormatLine``1" />) for examples.</example>
val force: value: aval<'T> -> 'T
<summary> Evaluates the given adaptive value and returns its current value. This should not be used inside the adaptive evaluation of other AdaptiveObjects since it does not track dependencies. </summary>
val transact: action: (unit -> 'T) -> 'T
<summary> Executes a function "inside" a newly created transaction and commits the transaction. </summary>
property ChangeableValue.Value: float with get, set
<summary> Gets or sets the current value. Setting the value requires a Transaction to be active using `transact`. </summary>
val map: mapping: ('T1 -> 'T2) -> set: aval<Set<'T1>> -> aval<Set<'T2>> (requires comparison and comparison)
val mapping: ('T1 -> 'T2) (requires comparison and comparison)
val set: aval<Set<'T1>> (requires comparison)
Multiple items
val aval: AValBuilder
<summary> ComputationExpression builder for aval. </summary>

--------------------
type aval<'T> = IAdaptiveValue<'T>
<summary> An abbreviation for AdaptiveValue </summary>
Multiple items
union case ElementOperation.Set: 'T -> ElementOperation<'T>
<summary> Set the associated key to a specific value. </summary>

--------------------
module Set from Microsoft.FSharp.Collections
<summary>Contains operations for working with values of type <see cref="T:Microsoft.FSharp.Collections.Set`1" />.</summary>

--------------------
type Set<'T (requires comparison)> = interface IReadOnlyCollection<'T> interface IComparable interface IEnumerable interface IEnumerable<'T> interface ICollection<'T> new: elements: seq<'T> -> Set<'T> member Add: value: 'T -> Set<'T> member Contains: value: 'T -> bool override Equals: obj -> bool member IsProperSubsetOf: otherSet: Set<'T> -> bool ...
<summary>Immutable sets based on binary trees, where elements are ordered by F# generic comparison. By default comparison is the F# structural comparison function or uses implementations of the IComparable interface on element values.</summary>
<remarks>See the <see cref="T:Microsoft.FSharp.Collections.SetModule" /> module for further operations on sets. All members of this class are thread-safe and may be used concurrently from multiple threads.</remarks>


--------------------
new: elements: seq<'T> -> Set<'T>
val map: mapping: ('T1 -> 'T2) -> value: aval<'T1> -> aval<'T2>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val map: mapping: ('T -> 'U) -> set: Set<'T> -> Set<'U> (requires comparison and comparison)
<summary>Returns a new collection containing the results of applying the given function to each element of the input set.</summary>
<param name="mapping">The function to transform elements of the input set.</param>
<param name="set">The input set.</param>
<returns>A set containing the transformed elements.</returns>
<example id="set-map"><code lang="fsharp"> let set = Set.empty.Add(1).Add(2).Add(3) printfn $"The set with doubled values is {Set.map (fun x -&gt; x * 2) set}" </code> The sample evaluates to the following output: <c>The set with doubled values is set [2; 4; 6]</c></example>
val inputSet: cset<int>
type cset<'T> = ChangeableHashSet<'T>
<summary> An abbreviation for ChangeableHashSet </summary>
val dependentSet: aset<int>
Multiple items
module ASet from FSharp.Data.Adaptive.CollectionExtensions
<summary> Functional operators for aset&lt;_&gt; </summary>

--------------------
module ASet from FSharp.Data.Adaptive
<summary> Functional operators for aset&lt;_&gt; </summary>
val map: mapping: ('A -> 'B) -> set: aset<'A> -> aset<'B>
<summary> Adaptively maps over the given set. </summary>
val v: int
val printf: format: Printf.TextWriterFormat<'T> -> 'T
<summary>Print to <c>stdout</c> using the given format.</summary>
<param name="format">The formatter.</param>
<returns>The formatted result.</returns>
<example>See <c>Printf.printf</c> (link: <see cref="M:Microsoft.FSharp.Core.PrintfModule.PrintFormat``1" />) for examples.</example>
property IAdaptiveHashSet.Content: aval<HashSet<int>> with get
<summary> The current content of the set as aval. </summary>
member ChangeableHashSet.Add: value: 'T -> bool
member ChangeableHashSet.Remove: value: 'T -> bool
val calcHeight: t: float -> h0: float -> g: float -> float
val t: float
Multiple items
val float: value: 'T -> float (requires member op_Explicit)
<summary>Converts the argument to 64-bit float. This is a direct conversion for all primitive numeric types. For strings, the input is converted using <c>Double.Parse()</c> with InvariantCulture settings. Otherwise the operation requires an appropriate static conversion method on the input type.</summary>
<param name="value">The input value.</param>
<returns>The converted float</returns>
<example id="float-example"><code lang="fsharp"></code></example>


--------------------
[<Struct>] type float = System.Double
<summary>An abbreviation for the CLI type <see cref="T:System.Double" />.</summary>
<category>Basic Types</category>


--------------------
type float<'Measure> = float
<summary>The type of double-precision floating point numbers, annotated with a unit of measure. The unit of measure is erased in compiled code and when values of this type are analyzed using reflection. The type is representationally equivalent to <see cref="T:System.Double" />.</summary>
<category index="6">Basic Types with Units of Measure</category>
val h0: float
val time: cval<float>
val currentHeight: aval<float>
val map3: mapping: ('T1 -> 'T2 -> 'T3 -> 'T4) -> value1: aval<'T1> -> value2: aval<'T2> -> value3: aval<'T3> -> aval<'T4>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val currentHeightSafe: aval<float>
val adaptive: AValBuilder
<summary> ComputationExpression builder for aval. </summary>
val shouldBeConstant: aval<int>
val constant: value: 'T -> aval<'T>
<summary> Creates a constant adaptive value always holding the given value. The system internally propagates constants. </summary>
property IAdaptiveObject.IsConstant: bool with get
<summary> Indicates whether the IAdaptiveObject is constant </summary>
val someInput: cval<int>
val someOutput: aval<int>
property IAdaptiveObject.OutOfDate: bool with get, set
<summary> Indicates whether the object has been marked. This flag should only be accessed when holding a lock on the adaptive object. </summary>
property ChangeableValue.Value: int with get, set
<summary> Gets or sets the current value. Setting the value requires a Transaction to be active using `transact`. </summary>