Rectangle 27 0

scala How can a time function exist in functional programming?


As Jeffrey Burka mentioned in his comment: Here is the nice intro to the IO Monad straight from the HaskellWiki.

I find it useful to not call things like getting the current time "functions" but something like "procedures" (though arguable the Haskell solution is an exception to this).

In Haskell (a very pure one) all this stuff has to happen in something called the IO Monad - see here. You can think of it as getting another input (and output) into your function (the world-state) or easier as a place where "impureness" like getting the changing time happens.

Other languages like F# just have some impureness built in and so you can have a function that returns different values for the same input - just like normal imperative languages.

The crucial thing to realise about the IO monad in Haskell is that it is not just a hack to get around this problem; monads are a general solution to the problem of defining a sequence of actions in some context. One possible context is the real world, for which we have the IO monad. Another context is within an atomic transaction, for which we have the STM monad. Yet another context is in the implementation of a procedural algorithm (e.g. Knuth shuffle) as a pure function, for which we have the ST monad. And you can define your own monads too. Monads are a kind of overloadable semicolon.

The typical Haskell term is "action".

Yes and no.

but in this case this would be something like '() -> ...' (a constant function) and I would not call this a procedure - but call it as you wish :D

from the Haskell perspective classical "procedures" (things that have types like '... -> ()') are somewhat trivial as a pure function with ... -> () cannot do anything at all.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


(>>=) :: IO a -> (a -> IO b) -> IO b
data IO a = IO (RealWorld -> (a,RealWorld))
do
do currTime <- now
   putStrLn currTime
now >>= putStrLn

-1: I'm unhappy with the RealWorld smoke screen. Yet, the most important thing is how this purported object is passed on in a chain. The missing piece is where it starts, where the source or connection to the real world is -- it starts with the main function which runs in the IO monad.

>>= takes one action and a function that takes the result of this action and creates a new action out of this. The return type is the new action. For instance, let's pretend there is a function now :: IO String, which returns a String representing the current time. We can chain it with the function putStrLn to print it out:

@kaizer.se You can think of a global RealWorld object that is passed into the program when it starts.

All this is pure, as we map the mutation and information about the world outside to the RealWorld token. So each time, you run this action, you get of course a different output, but the input is not the same: the RealWorld token is different.

Basically, your main function takes a RealWorld argument. Only upon execution is it passed in.

I think the RealWorld metaphor doesn't work very well when starting to think about concurrency. When forking an IO action, does that mean that the entire world is copied? If so, how is it joined again? An analogy to an abstract version of Java's Runnable might be better (i.e. Runnables which you can never run yourself but only bind to functions to produce new runnables).

In Haskell one uses a construct called monad to handle side effects. A monad basically means that you encapsulate values into a container and have some functions to chain functions from values to values inside a container. If our container has the type:

The idea behind this is that each IO action mutates the outside state, represented by the magical token RealWorld. Using monads, one can chain multiple functions that mutate the real world together. The most important function of a monad is >>=, pronounced bind:

You see, the reason why they hide the RealWorld and only provide puny functions to change it like putStrLn, is so some Haskell programmer doesn't change RealWorld with one of their programs such that Haskell Curry's address and birth-date is such they become next-door neighbors growing up (this could damage the time-space continuum in such a way to hurt the Haskell programming language.)

we can safely implement IO actions. This type means: An action of type IO is a function, that takes a token of type RealWorld and returns a new token, together with a result.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


I am surprised that none of the answers or comments mention coalgebras or coinduction. Usually, coinduction is mentioned when reasoning about infinite data structures, but it is also applicable to an endless stream of observations, such as a time register on a CPU. A coalgebra models hidden state; and coinduction models observing that state. (Normal induction models constructing state.)

This is a hot topic in Reactive Functional Programming. If you're interested in this sort of stuff, read this: http://digitalcommons.ohsu.edu/csetech/91/ (28 pp.)

Your question was about modeling time-dependent behavior in a purely functional way, e.g., a function that returns the current system clock. You can either thread something equivalent to an IO monad through all the functions and their dependency tree to get access to that state; or you can model the state by defining the observation rules rather than the constructive rules. This is why modeling complex state inductively in functional programming seems so unnatural, because the hidden state is really a coinductive property.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


Yes, it's possible for a pure function to return the time, if it's given that time as a parameter. Different time argument, different time result. Then form other functions of time as well and combine them with a simple vocabulary of function(-of-time)-transforming (higher-order) functions. Since the approach is stateless, time here can be continuous rather than discrete. This intuition is the basis of Functional Reactive Programming (FRP).

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


Prelude> System.Time.getClockTime >>= print
Fri Sep  2 01:13:23  () 2011

@Nawaz: The key thing to note here is that you cannot execute an action from within a function. You can only combine actions and functions together to make new actions. The only way of executing an action is to compose it into your main action. This allows pure functional code to be separated from imperative code, and this separation is enforced by the type system. Treating actions as first class objects also allow you to pass them around and build your own "control structures".

@sepp2k So, myList :: [a -> b] is a function? ;)

@trinithis Well, maybe I should have made it clearer that actions are also functions (just like all values in e.g. Haskell are functions, at least if you call constants nullary functions), but not all functions are actions. But I don't think the term action is misleading or imprecise. An action is a type of value which you can distinguish by its type, just like you can distinguish Ints by their type. I didn't drill too much into the type argument, partly because it's covered in other replies, partly because I wanted to focus on my point.

Another way to explain it is this: no function can get the current time (since it keeps changing), but an action can get the current time. Let's say that getClockTime is a constant (or a nullary function, if you like) which represents the action of getting the current time. This action is the same every time no matter when it is used so it is a real constant.

I don't know if this was any clearer than the other explanations, but it sometimes helps me to think of it this way.

It's not convincing to me. You conveniently called getClockTime an action instead of a function. Well, if you call so, then call every function action, then even imperative programming would become functional programmming. Or maybe, you would like to call it actional programmming.

Likewise, let's say print is a function which takes some time representation and prints it to the console. Since function calls cannot have side effects in pure functional language, we instead imagine that it is a function which takes a timestamp and returns the action of printing it to the console. Again, this is a real function, because if you give it the same timestamp, it will return the same action of printing it every time.

Not everything in Haskell is a function - that's utter nonsense. A function is something whose type contains a -> - that's how the standard defines the term and that's really the only sensible definition in the context of Haskell. So something whose type is IO Whatever is not a function.

Now, how can you print the current time to the console? Well, you have to combine the two actions. So how can we do that? We cannot just pass getClockTime to print, since print expects a timestamp, not an action. But we can imagine that there is an operator, >>=, which combines two actions, one which gets a timestamp, and one which takes one as argument and prints it. Applying this to the actions previously mentioned, the result is... tadaaa... a new action which gets the current time and prints it. And this is incidently exactly how it is done in Haskell.

So, conceptually, you can view it in this way: A pure functional program does not perform any IO, it defines an action, which the runtime system then executes. The action is the same every time, but the result of executing it depends on the circumstances of when it is executed.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


I am surprised that none of the answers or comments mention coalgebras or coinduction. Usually, coinduction is mentioned when reasoning about infinite data structures, but it is also applicable to an endless stream of observations, such as a time register on a CPU. A coalgebra models hidden state; and coinduction models observing that state. (Normal induction models constructing state.)

This is a hot topic in Reactive Functional Programming. If you're interested in this sort of stuff, read this: http://digitalcommons.ohsu.edu/csetech/91/ (28 pp.)

Your question was about modeling time-dependent behavior in a purely functional way, e.g., a function that returns the current system clock. You can either thread something equivalent to an IO monad through all the functions and their dependency tree to get access to that state; or you can model the state by defining the observation rules rather than the constructive rules. This is why modeling complex state inductively in functional programming seems so unnatural, because the hidden state is really a coinductive property.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


@Konrad: They do the same thing in the sense that both use type system features to abstract side effects, but that's about it. Note that it's very well to explain the IO monad in terms of a world type, but the Haskell standard doesn't actually define a world type and it's not actually possible to get a value of type World in Haskell (while it's very possible and indeed necessary in clean). Further Haskell does not have uniqueness typing as a type system feature, so if it did give you access to a World, it could not ensure that you use it in a pure way the way Clean does.

In Clean it would be a function, but the function would take a world value as its argument and return a fresh world value (in addition to the current time) as its result. The type system would make sure that each world value can be used only once (and each function which consumes a world value would produces a new one). This way the time function would have to be called with a different argument each time and thus would be allowed to return a different time each time.

In languages like Haskell and Clean, which are pure, the situation is different. In Haskell the current time would not be available through a function, but a so-called IO action, which is Haskell's way of encapsulating side effects.

Most functional programming languages are not pure, i.e. they allow functions to not only depend on their values. In those languages it is perfectly possible to have a function returning the current time. From the languages you tagged this question with this applies to scala and f# (as well as most other variants of ML).

This makes it sound as if Haskell and Clean do different things. From what I understand, they do the same, just that Haskell offers a nicer syntax (?) to accomplish this.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


// Exposes mutable time as immutable time (poorly, to illustrate by example)
// Although the insides are mutable, the exposed surface is immutable.
public class ClockStamp {
    public static readonly ClockStamp ProgramStartTime = new ClockStamp();
    public readonly DateTime Time;
    private ClockStamp _next;

    private ClockStamp() {
        this.Time = DateTime.Now;
    }
    public ClockStamp NextMeasurement() {
        if (this._next == null) this._next = new ClockStamp();
        return this._next;
    }
}
// Immutable. A result accompanied by a clockstamp
public struct TimeStampedValue<T> {
    public readonly ClockStamp Time;
    public readonly T Value;
    public TimeStampedValue(ClockStamp time, T value) {
        this.Time = time;
        this.Value = value;
    }
}

// Times an empty loop.
public static TimeStampedValue<TimeSpan> TimeALoop(ClockStamp lastMeasurement) {
    var start = lastMeasurement.NextMeasurement();
    for (var i = 0; i < 10000000; i++) {
    }
    var end = start.NextMeasurement();
    var duration = end.Time - start.Time;
    return new TimeStampedValue<TimeSpan>(end, duration);
}

public static void Main(String[] args) {
    var clock = ClockStamp.ProgramStartTime;
    var r = TimeALoop(clock);
    var duration = r.Value; //the result
    clock = r.Time; //must now use returned clock, to avoid seeing old measurements
}

(Keep in mind that this is an example meant to be simple, not practical. In particular, the list nodes can't be garbage collected because they are rooted by ProgramStartTime.)

@Strilanc Thanks for this. I think in imperative code, so it's interesting to see functional concepts explained this way. I can then imagine a language where this natural and syntactically cleaner.

@leftaroundabout you can sort of pretend that you have a monad in C# by implementing the bind function as a method called SelectMany, which enables the query comprehension syntax. You still can't program polymorphically over monads though, so it's all an uphill battle against the weak type system :(

@snim2 I'm not perfect. :P Take solace in the fact that the dirty mutableness doesn't affect the referential transparency of the result. If you pass the same 'lastMeasurement' in twice, you get a stale next measurement and return the same result.

In C# you could implement it like this:

Interesting, but that i++ in the for loop isn't referentially transparent ;)

It can absolutely be done in a purely functional way. There are several ways to do it, but the simplest is to have the time function return not just the time but also the function you must call to get the next time measurement.

Of course, it's a bit inconvenient to have to pass that last measurement in and out, in and out, in and out. There are many ways to hide the boilerplate, especially at the language design level. I think Haskell uses this sort of trick and then hides the ugly parts by using monads.

This 'ClockStamp' class acts like an immutable linked list, but really the nodes are generated on demand so they can contain the 'current' time. Any function that wants to measure the time should have a 'clockStamp' parameter and must also return its last time measurement in its result (so the caller doesn't see old measurements), like this:

You could in fact go the monad way in C# as well, thus avoiding the explicit passing of time stamps. You need something like struct TimeKleisli<Arg, Res> { private delegate Res(TimeStampedValue<Arg>); }. But code with this still wouldn't look as nice as Haskell with do syntax.

Note
Rectangle 27 0

scala How can a time function exist in functional programming?


Yes, it's possible for a pure function to return the time, if it's given that time as a parameter. Different time argument, different time result. Then form other functions of time as well and combine them with a simple vocabulary of function(-of-time)-transforming (higher-order) functions. Since the approach is stateless, time here can be continuous (resolution-independent) rather than discrete, greatly boosting modularity. This intuition is the basis of Functional Reactive Programming (FRP).

Note