Back to Questions
2.1k
views2
comments
On-demand recomputation of dependent values
f#functionalcompilerclasses

I’m new to functional programming and amazed how elegantly it can be for certain classes of problems that arise in my daily business. I have a problem that has been causing me headaches and insomnia for the last couple of days. I’ll try to present it abstractly and concisely enough to start a discussion.

The task is to write a compiler which maps a complex declarative data structure (project data) to an implementation using templates. During the computation software artifacts are derived as values based on values drawn from the declarative data structure and some of these computed artifacts are used to compute further artifacts.

The process of mapping involves some sequencing as well since some of the computed target values depend on previously computed target values. (e.g. when assigning unique labels to instructions or assigning a unique id to a code artifact and referencing it from other code artifacts.)

Nevertheless there is a clear data flow that defines partial ordering in which the elementary functions should be applied.

My problem is two-fold:

(1) How does the method of building up complex interdependent mappings using “simple” functions scale for large, composite data structures?
(2) Suppose there is a set of atomic change operations defined for the declarative data structure which I’m about to compile. (e.g. changing a value of a record field).
Is there any sensible way to orchestrate the chain of computation in such a manor that only those values will be recomputed which are affected by the atomic change?

Thanks for any supportive hint or comment.

.

Hi laczoka,

The problem you're describing also catched my interest. There is a fairly extensive body of work on this topic, under the name of "incremental computing" or "adaptive computing" or even "self adjusting computation". Basically there are libraries that allow you to build incremental computations, that in the background maintain a graph of all dependencies between variables. When one changes, only the dependant variables are recomputed. I believe they applied it to quicksort, among others, getting good efficiency results.

A short overview with links:

Adaptive functional programming:

[link:www.cs.cmu.edu]

Describes an ML library to make adaptive computations.

"Monads for incremental computing", a functional pearl: [link:www.carlssonia.org]

A re-implementation of the above library in Haskell using Monads; enjoys additional static safety.

Also check out Umut Acar's publications on "self adjusting computations" (settle on a name, already! ;) . He was one of the original authors of the first papers, and in his paper "Imperative self-adjusting computation" the model is generalized to non-functional settings (i.e. where each "incremental variable" can be written more than once).

All libraries are freely available on the web if you dig around. Porting such a library was going to be one of my pet projects, but you know...so much ideas, so little time...

Let us know how you progress!

cheers,

Kurt

By on 1/22/2009 12:53 PM ()

Hi Kurt,

thanks for the sources, I'll definitely have a look at them on the weekend. :)

"...so much ideas, so little time..."

Story of my life... :)

I'll keep you posted.

Thx,

L

By on 1/23/2009 12:03 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper