Remembering everything - a new(?) idea for a new PL


For my master thesis I'm designing a new programming language for a specific domain related to data processing.

One of the neat features I'd like to include in the language would be the concept of memory, in that each variable would remember its past values and the interval it held them. This can simplify lot's of queries as time itself is central in this domain.

Anyway, being just a graduate student, I know this idea must not be new. However, the most similar topic I was able to dig were temporal databases and temporal query languages. I wonder if there is anything else. Also, I wonder if it is possible for the compiler to analyze the program and find out how much memory it really needs to keep. Comments?


Luís Pureza

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Linear logic

If you transform your program to a linear form, so each assignment is taken to create a new variable which is only assigned once, you have something similar to what you want - at least in terms of recording each value and its extent. I've been sort of playing with something similar for simulations - quite often you want to record at least a significant subset of the states for replay or visualisation, and being able to schedule an event in the past makes handling collisions easier, but way too busy in my day job to write anything up.

Semantics of Idealised Algol

The Abramsky-McCusker semantics of types for Reynolds' Idealised Algol work this way: linear types are time series, mapping times to values, where `!' types never change [1]. One could use this semantics as a basis for a clean extension of idealised algol with some sort of versioned dereference function, which takes a variable and a time stamp.

[1]: Samson Abramsky and Guy McCusker (1997). Linearity, Sharing and State: a Fully Abstract Game Semantics for Idealized Algol with active expressions (.ps.gz). In O'Hearn and Tennent (eds.), Algol-like languages. Two volumes, Birkhauser.

Perhaps take a look at

Perhaps take a look at adaptive languages (blelloch/acar/shankar/cooper) that facilitate memoization and then maybe older transparent persistence systems (there might be parts dipping into logging file systems).

I can't recall anything about explicit time intervals that doesn't quickly fall into DB land, logic, or is too domain specific for me (not to say these are bad things!).

An Elephant Never Forgets

Elephant was a John McCarthy's project, perhaps it can inspire you. It was previously discussed on LtU and mentioned in this interview.

From the implementation

From the implementation perspective, this sounds similar to omniscient debuggers.

A little better (eg,

A little better (eg, MzTake), because you don't need to remember everything, and thus can make the time/space bounds on these fragments (eg, RT-FRP)..

History variables

Ryan Mallon's MS Thesis, The Semantics, Formal Correctness and Implementation of History Variables in an Imperative Programming Language, might be a useful resource for you. In his implementation previous values are indexed by assignment-depth rather than time, but his scheme may be able to be adapted to allow access by time intervals (I haven't studied it in enough depth to know for certain).

Time Warp Operating System

Also you might have a look at Jefferson's work in the Time Warp Operating System. Key idea from your perspective is that old variable values are only interesting for as long as they remain reachable by the computation. TWOS offers one strategy for how to integrate the necessary dependency tracking with speculative computation.

Once you get your head around the idea Jefferson is contemplating, then go look at register rename architectures and their associated dataflow controls. A properly done register rename machine implements essentially what Jefferson describes, but without hazard of unbounded rollback, because it has a stable retirement strategy for completed instructions. The difference is that conventional register rename does not contemplate loosely or moderately coupled parallelism, where Jefferson's work does.

My feeling is that Jefferson's work has been under-regarded, and is worth a look.

Talk to Emile van Sebille

Talk to Emile van Sebille about Nicles.

Tangible Program Histories

Todd Proebsting and Ben Zorn did some work they called Tangible Program Histories, which is similar to what you are describing.

However, I'm wondering if simple streams (in the Scheme/Haskell sense of lazily-evaluated lists) might serve your purposes. Instead of "assigning" the value 7 to variable x, you push 7 onto the list history_of_x. The "current value" of x would then be the head of that list, but you can always get at past values by digging down through the rest of the list.

In a somewhat similar but more specialized vein, you may want to look at digital signal processing, particularly the implementation of FIR and IIR filters. This is a domain where a limited history of certain variables must be maintained, and there are methods for determining just how much history is needed (ie, the filter order). Depending on what sort of data you're processing, you may be able to express your problem as a signal processing system.

Versioned STM

I've always imagined that Software Transactional Memory would be relatively easy to extend to support versioned cells. With enough structure-sharing and some favoring of functional programming instead of mutable state, it might even be managed efficiently.

I've often thought it would be a more useful feature at the blurring edges between PL and Operating System - the ability to perform atomic updates to multiple files and automatically version them.