Lambda the Ultimate

Did I mention that the language will be dynamically typed :-) No effects, and yes, no monads.

...your previous blog entry, "I hate monads." :)

Good point. But I really am only interested in the single-result choice, not the "amb"-like choice. My motivation for considering choice is that I want to have parallel computation in the language via futures. It would be nice to have something like in AliceML awaitEither (a,b) in the language which evaluates either to a or b, depending on which future finishes computing first. Semantically, awaitEither(a,b) = choice a b, at least if futures are implemented transparently.

Well, if we're going to talk about terminology, my feeling is that "pure" has no place outside chemistry and perhaps pharmaceuticals. Elsewhere it seems to acquire a moral connotation that is unwarranted.

well, pure is used as an adjective / attribute to "functional" here. By the way, is anything in chemistry pure. I thought the pure stuff was physics :-)

Calling it something else is an option. But it shares a lot of valuable properties with "purely functional", for example for purposes of parallelization is behaves identically in that there are no side effects. In fact, the very definition of random implies that different calls to random will be independent of each other! So this means, that there is NO COMMUNICATION between different calls of random. If modeled by a monad, the monad would be the communication between different calls to random. You would then need to state the property that this communication behaves well by not communicating at all ...
Also, as I write in my blog, I think you can see "weakly purely functional" as "strongly purely functional" in disguise by just lifting the domain and range of the functions.

In the case of random choice, lifting the domain and the range corresponds to computing a distribution instead of a sample. So for your pure subset, why not just compute distributions?

As you mentioned, one way is to explicitly return some sort of "flat" representation of the distribution like "(50% : a, 50% : b)". Another way is to make your distribution a function that accepts an oracle, and thread that oracle through your sub-computations (either explicitly or using some sort of implicit parameters). For example, Haskell's System.Random.random function doesn't involve any effects or monads—it's deterministic given a particular random number generator state—IO is only involved at the top level of your program if you want to query the OS for a seed for your random number generator.

By the way, although randomly sampling from a distribution might not cause an effect on the execution of other threads, if you query an external random number source (as opposed to a deterministic oracle that was passed in as a parameter), the thread that requests the sample is itself subject to an effect caused by the external source of randomness. Whereas a pure computation neither causes nor is subject to effects.

While computing with measures is good for reasoning, I do not want it for computation itself, because it is too expensive. For reasoning, it is good though, because it explains how the function will behave when you call it often.

Always passing a seed around implies pseudo random generators. Nothing against them, but for a language definition I'd like real randomness. In "practice", one can imagine just including a new CPU instruction which generates a new random number whenever called. Apart maybe from caching issues this would not be different than any other CPU instruction!

Also, passing around an oracle, or a random seed is not good for reasoning about the program, because it makes it actually more difficult for reasoning about the program by creating a connection between the different random numbers, whereas for reasoning you need the independence of them.

As you mentioned, one way is to explicitly return some sort of "flat" representation of the distribution like "(50% : a, 50% : b)".

I am only familiar with it to the extent of playing around with the examples in the tutorial, but this sounds very much like the approach taken by IBAL.

Looks very interesting, I'll look into it.

See also Hansei.

can we start up a collection tin for getting Oleg's head on ice when the time comes?

Also, as I write in my blog, I think you can see "weakly purely functional" as "strongly purely functional" in disguise by just lifting the domain and range of the functions.

This sentence fills me with great fear: You can also see "imperative" as "strongly purely functional" by lifting the domain and range of the functions to include the implicit global state. Well, not that it matters—there's nothing wrong with imperative code—but, as others have mentioned, why call your language something that it's not?

Lol. You have a point there. I guess what I mean what is special about the way lifting is done in the case of random and choice is:

First you lift the result range. You do not need any new input arguments, so weakly pure functions become strongly pure functions by just changing the result range.

The lifting of the domain is done now only as a consequence of the result range lifting. So a weakly pure function really is a function, but at one particular run of the program you see only different manifestations of this function. Maybe a better name for "weakly pure function" would be "quantum function" :-)

A new name is a good idea, but I would like it somehow shorter than isolatable or contextless. What about "clean" :-)

Well, a probabilistic function is very often non-deterministic. For my purposes, it makes sense to treat probability and non-determinism in the same context.

What do you mean by x86-nondet? Tell me more.

A non-deterministic program just isn't probabilistic[1]. Say you have a non-deterministic program which chooses between the result 1 and a choice between the result 2 and itself (say, f = 1 | (2 | f)). Now, I'll wave non-termination away for a moment...

The result of the program is either 1, or 2. There are no probabilities involved - that's just how non-deterministic algorithms are defined.

The x86-nondet processor was a gift specially brought by by Rudolf and Clause a few days ago which I greatly appreciated. Unfortunately, it either gives tea or coffee and insists in smoking all my cigarettes. The coffee tastes lousy btw.

You cannot 'run' non-deterministic programs unless you have a non-deterministic machine, Turing or otherwise.*

Happy New Year!!!

[1] But you might firmly believe they are in the same complexity class, in which case, I'll jump on the band-wagon and firmly start believing similarly, if I didn't already.

[Edit: Actually you can see the difference easily in that f = (1|(2|f)) is equivalent to f = (1|2)|f non-deterministically, but certainly not so probabilistically if you assume a 50%/%50% chance distribution for choice |.]

[Edit2: *Ok, you can run them, but you end up with probabilistic behaviour, not non-deterministic in the mathematical sense.]