Programming with alternatives

I've come up with a new concept, called 'alternative programs', where expressions can have multiple alternatives. I wonder if there are any papers out there that discuss a similar concept. I'm having trouble defining the concept, but here is a try:

Every expression takes the form of a sequence of alternative expressions, syntactically enclosed within curly brackets and separated by commas (in the case of a single alternative, curly brackets are omitted).

The combination of two alternative expressions results in the cartesian product combination of their alternatives.

Example alternative expressions:


1 + 2         => 3
{1,2} + 3     => {1+3,2+3}         => {4,5}
1 {+,*} 2     => {1+2,1*2}         => {3,2}
{1,2} + {9,7} => {1+9,1+7,2+9,2+7} => {10,8,11,9}

I've taken the bold step to generalise the above into the following:

Consecutive alternatives in a sequence that are equal are compressed into singletons, then prefixed with a colon, together with the multiplicity of the consecutive equal alternatives. A compressed representation of a sequence is called the canonical representation of a sequence.

Next to that, multiplicities are of type rational and can be negative (where negative multiplicities are prefixed with an underscore). Luckily, the cartesian product of alternatives can be naturally defined over negative and rational multiplicities.

Example canonical representations:


{1,1,1/4:2,2,_1/2:2,1,_3,_3,_3,3,1} =>
{2:1,3/4:2,1,_2:3,1}

{1/2:1,1/4:2} + {4:3,_2:4}      => 
{2:(1+3),_(1+4),2+3,_1/2:(2+4)} =>
{2:4,_5,5,_1/2:6}               =>
{2:4,_1/2:6}

multiple worlds

There has been some work in this area with respect to logic programming; e.g. "Multilog: multiple worlds in logic programming" circa 1986. Array programming languages allow for similar operations if you can think of alternative sets as arrays of bounded sizes.

Not quite sure where you are going with this though. I mean, why expand out alternate worlds eagerly anyways? Perhaps its better to be fuzzy, and evaluate the program under different probabilities until you get a decent result (or better yet, use stochastic methods).

By Sean McDirmid at Thu, 2013-01-03 23:33 | login or register to post comments

Thanks for considering my

Thanks for considering my fuzzy concept.

My examples are eagerly evaluated because I wanted to demonstrate the semantics clearly. I believe the semantics do allow lazy evaluation. I might also choose to include a stochastic sampling operator that non-deterministically selects alternatives.

Your reference to 'multiple worlds' was helpful because I found an earlier LtU discussion on 'Worlds: Controlling the Scope of Side Effects'.

By Robbert van Dalen at Fri, 2013-01-04 09:12 | login or register to post comments

This looks like McCarthy's amb operator

See here for a simple account of it. McCarthy proposed this in (IIRC) 1963, and it's seen quite a lot of study since then, since it's very interesting both theoretically and practically.

By neelk at Fri, 2013-01-04 09:39 | login or register to post comments

It is very similar

The amb operator works very similar to what I'm after. Thanks for the reference.

It appears that there are two versions of the amb operator? One version non-deterministically picks a variant when evaluated, while the other version keeps all variants, until alternatives are pruned with the require operator.

By Robbert van Dalen at Fri, 2013-01-04 19:18 | login or register to post comments

Functional logic programming.

By Jules Jacobs at Fri, 2013-01-04 10:06 | login or register to post comments

alternatives

I love the idea of alternatives. I've often wished for this sort of built in operation.

If I can make a suggestion, the canonical representation makes a lot more sense if the result is not order preserving. I might default to 2 or more sets then this gets sorted and canonical, while with only 1 the return value is in order. So

  
{2,3,2} * 5 = {10,15,10}
{2,3,2} * {5} = {10:2,15}

_____

canonical representation is something I might just add to the datatype. Every object should have a canonical function which cleans it in a unique way which gets invoked by the sorter. I would suggest looking at the US Post Office mail standardization procedures for a good example of a canonical representation of something that is complex and non-mathematical. A good example to keep in mind.

By JeffB at Fri, 2013-01-04 13:20 | login or register to post comments

Nice suggestion

Your suggestion has made me reconsider the order-preserving of alternatives. Thanks for bringing it up.

I've decided to drop order-preserving sequences. So now, canonical representations of alternatives (and their combinations) become sorted multisets. Next to that, everything is evaluated against multisets.

Here are two some examples ([..] denotes a list):


{1,2} + {4,3}     => {4,2:5,6}  
[{1,2:3},5,{2,4}] => {[1,5,2],[1,5,4],2:[3,5,2],2:[3,5,4]}

By Robbert van Dalen at Fri, 2013-01-04 19:53 | login or register to post comments

This is easy to do with monads

This is easy to do with monads, and is indeed one of the earliest examples. See Section 8.1 of Comprehending Monads or Section 7.2 of The Essence of Functional Programming.

By Philip Wadler at Fri, 2013-01-04 15:45 | login or register to post comments

Prior art

First the amb combinator, now monads - what else is out there?

It is both exciting and humbling to know that there is so many prior art out there. I've still got a lot of research to do. Thanks.

The trouble is, google doesn't always give me the results I want. 'Non-deterministic programming' gives to many hits, while 'programming with alternatives' is obviously not hitting anything.

Does anyone care to share some specific google keywords that will point me to related research?

By Robbert van Dalen at Fri, 2013-01-04 20:07 | login or register to post comments

Functional Logic Programming +1

As already pointed... Alternatives are a defining feature of Functional Logic Programming. The Curry programming language is one of the most comprehensive in this area. You will probably be interested to see how the "Needed Narrowing" evaluation strategy tackles the problem of exponential combination of alternatives that would defeat a naive strict evaluation strategy.

By Arnaud Clere at Fri, 2013-01-04 21:45 | login or register to post comments

CLP(fd)

Try looking for constraint logic programming over finite domains, it's another extension / generalisation of Prolog semantics as with the other answers supplied. Using CLP(fd) over sets of integers gives the behaviour that you are defining.

By Andrew Moss at Sun, 2013-01-06 16:56 | login or register to post comments

{Icon, Prolog, Perl6}

If you haven't already, you'll probably want to check out the Icon programming language, where you can write a program like:


procedure main()
	every write( 1 + 2 )
	every write( (1|2) + 3 )
	every write( (add|mul)(1,2) )
	every write( (1|2) + (9|7) )

end

procedure add(x,y)
	return (x+y)
end

procedure mul(x,y)
	return (x*y)
end

...which produces the output you are looking for. Also check out Prolog:


(A=1;A=2),(B=9;B=7), X is A+B.

...and Perl6 junctions. Possibly add generator and iterators to your search terms. Finally, you might be interested in Programming Shorthands, and Screamer/Screamer+.

By Greg Buchholz at Fri, 2013-01-04 22:26 | login or register to post comments

Lambda the Ultimate

User login

Navigation