CODEWITHSUNDEEP
f#
user1594138
user1594138

Reputation: 1011

Parsing/Evaluating not to values, but saving the functions? So that parsing happens only once

I'm trying to implement spreadsheet like functionality where it maintains variables and updates them correctly when other variables or "cells" change.

The only implementation I have seen so far is one that stores the inputted data in a string and evaluates it, however when data changes and cells need to be recalculated it always needs to evaluate the strings again.

What I'm simply wondering is if it's possible at all to parse a string like Cell1 = "SQUARED (4)" into Cell1 = squared 4 So instead of the value being calculated into the cell, but the string needing to be run again and again when recalculations are necessary, it can instead save the actual functions and values somehow, somewhere, so that parsing and evaluating only needs to happen once.

If this isn't possible then I'll need to create a code-generator because I need things to be really fast and can't afford heavy performance loss. The speed of evaluation, compiling, ect, does not matter. It's the speed after all cells have been created, when the input data changes millions of times and propagates through the "spreadsheet" like system that matters.

So this is first of all just a yes or no question. If possible then any examples would of course be helpful. Edit: Well I guess it would be really helpful, since I can't figure this out myself.

Upvotes: 2

Views: 173

Answers (2)

Tomas Petricek
Tomas Petricek

Reputation: 243106

If you're interested in implementing something like a spreadsheet, then there are two things that might help.

  • Firstly, the Cellz project is a sample implementation of a spreadsheet in F#. It includes a simple parser for strings like "=SUM(A1:A10)" and builds an expression tree from these strings (and this is done just once). Secondly, it also includes an evaluator that calculates the value of an expression.

  • Secondly, Luca Bolognese had a few talks about the implementation of calculation framework called "Eden" where you describe computations in terms of cells and when a value in a cell changes, the change gets propagated automatically (and only dependent cells are recalculated). He will be speaking at TechMesh London 2012, but I think this has been recorded somewhere (but cannot find it).

The basic idea behind Eden is that a cell is represented as something that has a current value and an event that is triggered when the value changes:

type Cell<'T> =
  abstract Value : 'T  
  abstract Changed : IEvent<unit>

A cell that is created and mutated explicitly has mutable Value and triggers the event when the value is changed by the user:

type MutableCell<'T>(value:'T) = 
  let mutable currentValue = value
  let event = Event<unit>()
  member x.Value 
    with get() = currentValue
    and set(v) = 
        currentValue <- v
        event.Trigger()
  interface Cell<'T> with 
    member x.Value = currentValue
    member x.Changed = event.Publish

Then you can also construct cells that are produced as a result of some calculation. This is a topic for a talk or a blog post and not an SO answer, but a simple transformation that maps a value in a cell to another cell would look like this:

let map f (cell:Cell<_>) =
  let currentValue = ref (f cell.Value)
  cell.Changed.Add(fun () -> currentValue := f cell.Value) 
  { new Cell<_> with
      member x.Value = currentValue.Value
      member x.Changed = cell.Changed }

You need to be able to combine values from multiple cells etc.

Upvotes: 3

John Palmer
John Palmer

Reputation: 25516

There is a quite good example from Don Syme's blog on memoization - https://blogs.msdn.com/b/dsyme/archive/2007/05/31/a-sample-of-the-memoization-pattern-in-f.aspx?Redirected=true

You write this function

let memoize f =
    let cache = Dictionary<_, _>()    
    fun x ->    
        if cache.ContainsKey(x) then cache.[x]    
        else let res = f x    
             cache.[x] <- res    
             res

Then you can create a memoized function like:

let memoizedAppend =
    memoize (fun input ->
        printfn "Working out the value for '%A'" input
        String.concat ", " [ for i in 0 .. 9 -> sprintf "%d: %s" i input ])

Upvotes: 2

Related Questions