Is (probabilistic) non-determinism pure ?

I am currently designing my own programming language (as many other visitors of this site are doing, too, I guess :-)). I want it to have a purely functional subset. I decided to include "random" and "choice" in this purely functional subset. My reasons why (probabilistic) non-determinism should still be considered (weakly) purely functional are outlined here in my blog. I am very interested in your opinions on this topic!

Comment viewing options

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

It is what it is

I think you'd be better off encapsulating it as an effect if you have some such notion in your language.


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

I should have noticed...

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

choice vs. random

The choice operator normally implies that there can be any number of results to a call (zero, one or more). Whereas random always returns a single result. The question on the choice operator is how you handle anything other than a single result (e.g. backtracking or computation spaces).

choice as simplification of awaitEither

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.

What is the benefit in diluting the term "pure"?

What do you gain by labelling this concept "pure" with a prefix that means "not-really"? Why not just call them something else? Sampling a random process is not repeatable, nor does it possess referential transparency (as you mention). It is something that behaves as if it is accessing internal state or some kind of I/O. In you post you argue that these are "implementation" aspects rather than the "semantics" of random sampling - but they affect the behaviour of the operation, and the ways in which this operation can be manipulated into other forms.

Given that random sampling doesn't seem to fit into the notion of a pure operation, why are you trying to shoehorn it into that label? Why not just call it something else? Treating a random sample as some kind of computational step may actually hinder you - it behaves like a communication channel. What is the benefit in analysing it as a special case for pure operations instead of treating it as an Effect, or a Monad, or a Channel?

Keeping Terms Where They Belong

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.

pure outside chemistry

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 :-)

Pure or something else ?

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.

Sample vs. Distribution

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.

Computing with Measures

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.

Flat representation of distributions

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

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?

Functional, but with implicit domain

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.

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 better term

Instead of overloading the word "pure" and inviting arguments over meaning, why not invent a better term for what you want? Isolatable? Contextless?

A new name is a good idea,

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

Non-determinism != Probabilistic

For one. And probabilistic isn't pure, but probabilistic.

Wow! Speaking in riddles here?

A probabilistic pure language is fine.

A probabilistic impure language is fine.

A probabilistic non-deterministic language is fine, but hard to implement. (Unless you confine yourself to small programs, or happen to have the latest x86-nondet processor. I own one ;) )

A (probabilistic) non-deterministic language where non-determinism equals some sort of probability is just a misnomer.

[My 2cts, Happy New Year!!!]

Well, a probabilistic

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.

These are just definitions

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.]