Lambda the Ultimate

One is hypertalk (scripting language of the ancient and venerable HyperCard), in my final version before leaving Apple in 1992, statements such as:
put 3.14 in field display in 5 minutes
do myscript at 23:3:4
do anotherscript after myscript
put currentTime in field time every 30 seconds
msg "it's time" 10 seconds after startMessage

Were all valid hypertalk statements! Did this make it into Applescript?
I don't know.

Another SAOL, an unused part of the mpeg-4 standard, has what I think is the brilliant idea of rate variables, that get updated according to a precise schedule. They have a well thought out algebra for what happens when you combine variables from different rates in an expression. While their implementation is very domain specific with arate (audio rate) and krate (control rate) variables, the idea could be expanded to arbitrary rates.

I'd argue the underlying model of FRP, where values are functions from time to some base domain (even if implemented via actors/data flow), are desirable denotationally. Getting an imperative system (send this value through that channel) to play along is difficult - I would love to see something like Taha's breakdown of base vs reactive semantics in the RT-FRP paper to include something more interesting in the base and play with that.

You probably have thought of these, and they're very general, but it might be also be interesting into looking into executable subsets of temporal logics, work in modeling policy obligations, and general meta protocol modeling systems (where timeouts are crucial). Depending on your treatment of values changing over time, you may want to view them as channels with arbitrary (finite) order (which based on your above description, you do), in which case a lot of models in these areas no longer apply :)

Timed concurrent constraint programming and its relatives like the ntcc calculus introduce the notion of time steps or time units. In ntcc you can specify, for example, run process P somewhen during the next 100 time units, but wait at least 10 time units.

Various related literature is available online, including, the following

V. Saraswat, R. Jagadeesan, and V. Gupta. Timed Default Concurrent Constraint Programming. Journal of Symbolic Computation, 22(5-6), 1996.

C. Palamidessi and F. D. Valencia. A Temporal Concurrent Constraint Programming Calculus. In Principles and Practice of Constraint Programming – CP 2001. Springer, 2001.

On the theoretical front, there have been several efforts to integrate time into process calculi. The one I'm most familiar with is Timed CSP, which incorporates continuous time into CSP process models. S. Schneider, An Operational Semantics for Timed CSP, might be a good place to start. Schneider also has a fairly recent text book called "Concurrent and Real-Time Systems: The CSP Approach", the latter half of which covers Timed CSP. I gather that there are also "Timed" variants of CCS and the pi-calculus, although I'm less familiar with those. A slightly different approach (although I believe theoretically equivalent to the process calculi approaches) is to model systems in terms of networks of timed automata, as the Uppaal tool for real-time system verification does.

For the Actors model, Nielsen and Agha did some work on a Semantics for an Actor-Based Real-Time Language in the mid-to-late 90's. More recently, Berkeley's Ptolemy II modeling environment for real-time systems is nominally built on the Actors model, and the Ptolemy II team has done a lot of work on semantics.

Other researchers have extended specification languages with real-time capabilities. For example, Real-Time Maude (Ölveczky et al. Real-Time Maude: A Tool for Simulating and Analyzing Real-Time and Hybrid Systems), extends the Maude specification language with tools for specifying timed systems. Along similar lines, Smith et al., Structuring Real-Time Object-Z Specifications discusses how to extend Object-Z with a timed refinement calculus.

A Timed Semantics of Orc might be helpful.

you might check out Chris Date's Temporal Data and the Relational Model, for a thorough treatment of how to deal with time in a relational context. (In this book, time is treated as a discrete quantity; though the time quantum is unspecified--many examples use "day" as the time quantum; which is useless in practical applications).

Part of the difficulty in a proper treatment of time in computer systems is that time itself is difficult to deal with properly.

* Is it a discrete or a continuous quantity? Much recent physical evidence is pointing to "discrete" as the answer; and virtually all computer systems have discrete clocks anyway.
* What should the quantum be?
* Measuring and determining time--when is "now"?
* Synchronizatoin. If two different computers attempt to measure time at the same instant--do they get the same result?
* How do you specify things like intervals, durations of time, etc.
* Calendar and clock time--synching the abstract notion of time to the time measurement means used by humans.

That's all I have time for. :)

falcon: I'd like to say "send value X to object Y in 5 minutes."

I did exactly that in college (the second time around) around 1988 or so. But my time metric was a virtual clock as opposed to a real one, so I could advance time of "now" to be the time of the earliest message to be delivered next.

I used an actor model with async queues; the event passing model I thought of then is the same one I've evolved since, except I no longer bother to worry about time. (I only added the time scheduling part because I had a prof that wanted an engine that could be applied to do simulations, so I made it possible to model propagation delay.)

I don't follow academic research at all, preferring to work out anything I do from first principles. So I can't point you at anything. But I suggest just adding time of delivery to an actor model will work fine, as long as your runtime copes with adjudicating store and forward requirements (or you'll have a memory exhaustion denial of service problem) and mediates real time problems of not being able to suddenly execute more instructions per second than hardware supports (so you can't pack more computation into a time slice than you have resources).

If your system is distributed, you'll need to work out what it means to sync clocks, and what to do given ambiguous time data. (You mustn't promise semantics to users of your service you can't deliver.)

Anyway, if you have some kind of async event queueing engine, you can pretty easily model whatever you want, with one or more queues acting as delayed delivery services if you want timed delivery. You just can't deliver in the past (unless you're determined to do virtual rollbacks or something).

I'd expect your hard problems to be in pruning streams for QoS in media, if that's the application you have in mind.

Thanks folks for all the great links. It'll take me a while to get through them all.

Scott, I have a book by Date which includes a chapter on temporal data. I'll have to look that up again.

I have worked a little with 'streaming' databases, such as Coral8. They have some basic support for time, such as delaying the output of a query by X milliseconds, but their 'time' operations are rather limited. I have been trying to follow the "Complex Event Processing" research. CEP researchers seem to be doing some work in _recognizing_ patterns over time, but not in generating events according to one's schedule.

Interestingly, I have found some good ideas from APIs for animation. JavaFx's "dur" operator, Java's TimingFramework, etc.

The Power of Events is an interesting book. It has some basic operations for time. As far as I can tell, the ideas in this book are related to some sort of event calculus...I'll have to look up the reference when I get home.

My motivation for time based systems is financial trading systems. Much of the code I have seen so far is a hodge-podge of overly imperative, hence, overly complex set of call-back functions, timers, Thread.sleeps, etc. I can describe ideas in one or two sentences, yet it takes thousands of lines of user level code to put these ideas into computers. If an API was based on the ideas of Haskell's Parsec or SPJ's 'Financial Contracts,' I bet day-to-day programming for us programmers would become much more enjoyable. That was the reason I went looking for some basic primitives and ways of combining them. Making sure that these primitives could work with Events and Time equally well.

I just hope the FRP researchers make Time more explicit.

You may wish to have a look at Chronolog
http://hopl.murdoch.edu.au/showlanguage2.prx?exp=2225
http://www.dsto.defence.gov.au/publications/2905/

(sorry couldn't find a free-for-download paper)

Or some of the languages in and around the Lucid family such as Lucid Synchrone and Lustre:

http://www-sop.inria.fr/mimosa/rp/ROS/Tt-SM.html
http://www.artist-embedded.org/docs/Events/2007/Between_Control_and_Software/Slides/MarcPouzet.pdf
http://www.esterel-technologies.com/technology/scientific-papers/
http://www.cs.um.edu.mt/~synchrone05/Presentations/12-MarcPouzet.pdf

Objective-C (at least using the Cocoa Foundation Library on OSX, which I'm most familiar with) has the ability to send messages to any object after an arbitrary time delay like so:

[obj performSelector: @selector(blah) withObject: nil afterDelay: 25];

(the delay parameter is described as seconds from now)

I'm not sure if that counts as first class though, although it is implemented in NSObject so it works with just about everything.

Conal Elliot's recent blog posts on reactive futures may be of interest. This is the first in the series: http://conal.net/blog/posts/future-values/

On the one hand it's a fairly practical discussion, but on the other, by looking at how to render the abstraction in terms of standard typeclasses, there's an implicit process of formalization as well.

How are futures different than single-assignment variables in data-flow languages (e.g. Id)?

I'm surprised that no one has mentioned hardware description languages such as VHDL where time is integral in system descriptions. Tecnically these are not programming languages, but interesting anyway.