Implement Amb and Require The Challenge

Implement amb and its sister statement require in whatever language you wish. See http://community.schemewiki.org/?amb for an example implementation in Scheme. You can rename them to a and r.

amb statements select a value passed to it arbitrarily, and require statements written after amb contain conditionals that limit the possibilities that amb will return, as the conditionals must evaluate to true. statements The pseudocode

fun rand() {
    return amb(1, 2, 3, 4)
}


will return whatever the computer feels like as long as it is 1, 2, 3 or 4. However the pseudocode

fun arbitary2 {
    x = amb(1, 2, 3, 4)
    y = square(x)
    require(even(y))
    return x
}


can only ever eventually return 2 or 4, but a user may not know which one will return. Depending on implementation, 2 may always be returned, or 4, or 2 is returned 3% of the time and so on. require can be called any time after amb is called as long as both statements are in the same program, even outside of the scope of amb, so

fun foo() {
    amb(1,2,3,4)
}
x = foo()
y = foo()
require(x &gt; y)


is valid and x will never be less than y when the program successfully terminates. The degree to which this is possible varies language by language, so try your best to implement this. The following code should not successfully terminate:

amb(1, 2, 3, read("notes.txt"))
require(false)
print("this will never be printed")


The actual names and exact syntax of amb and require don't matter. For example, if your implementation is in assembly, then having amb read from predefined registers is legitimate as long as the essence of amb is preserved, and require can checked whether a certain register contains a certain value.

Try your best and have fun!

Scoring

This has been changed from popcon to code-golf, so make your implementations short! Least number of characters wins. Don't cheat and rename existing implementations. Any submission which does something to the effect of:

#define r rename
#define a amb


will be disqualified.
Scala, 406/377 Bytes

I offer two golfed versions of my implementation, one that chooses the value randomly and one that (somehow) abuses the task description and always returns the first legal value. It's up to you, with one to consider (the latter one is shorter, obviously):

trait A[X]{def g=scala.util.Random.shuffle(l).head;def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e&lt;-a.l;f&lt;-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=&gt;Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}
trait A[X]{def g=l(0);def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e&lt;-a.l;f&lt;-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=&gt;Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}


This versions are more or less just golfed versions of my initial submission (some implementations have changed slightly, but the interfaces were quite stable). Therefore I will not explain it any further but refer to my initial post. Just have in mind that everything that was "for convenience" now disappeared. And a lot of renaming happened. The only difference is that pairs are now a bit like new amb-values: If you define conditions on top of pairs this will never effect the underlying values (nevertheless, manipulating the underlying values will still affect the pairs).

To give you a hint on how to use this versions, here is a short testing code I used while golfing:

  val m = new M
  val a1 = m.a(List(1, 2, 3, 4, 5))
  val a2 = m.a(List(4, 5, 6))
  val a12 = m.p(a1, a2)
  m.r(m.o(a12, (p:(Int, Int)) =&gt; p._1 &gt; p._2))
  m.r(m.o(a1, (e: Int) =&gt; e%2==1))

  println(a1.l)
  println(a2.l)
  println(a12.l)
  println(a12.g)


As you can see, the offered functions are now instance-methods, hence, you need an instance of M to interact with my library (this saved me one glorious byte).

Note that my ungolfed version (which I will not update any more) now includes natural syntax for the most common Int- and Boolean-operations.



(my initial submission)

Right before posting this answer the Mathematica answer was stated and it looks as if my solution is based on similar assumptions. Nevertheless, I will offer my solution, too, because I didn't copied the former answer as it wasn't there when I started.

I didn't tried to recreate a natural syntax (like: (amb(1, 2, 3) + 3) * 5, etc), but this would be possible if you like to implement the necessary implicit conversions. I chose the functional way as you will see later.

Let's start with the two keywords:

import ambiguous.AmbOps.op

object Amb {
  def amb[A](args: A*): AmbType[A] =
        new BasicAmb[A](args.toList)
  def require(amb: AmbType[Boolean]): Unit =
        amb.del(false)
  def require[A](amb: AmbType[A], predicate: A =&gt; Boolean): Unit =
        require(op(amb, predicate))
  def require[A, B](amb: AmbType[(A, B)], predicate: (A, B) =&gt; Boolean): Unit =
        require(op(amb, predicate))
}


The amb-method is quite straight forward, you provide some values and get some container, that may return a value back (more on that later).
I offer three require methods but they are all based on the first one, so the others are just for convenience. Let me explain the first one (the others will become clear as you read on): If you have some boolean amb-Container and call require, all false values are eliminated.

But how is an amb-value of arbitrary type converted into a boolean value? By offering a conversion-policy:

object AmbOps {
  def op[A, B](amb: AmbType[A], op: A =&gt; B): AmbType[B] =
        new OpAmb[B, A](amb, op)
  def op[A, B, C](amb: AmbType[(A, B)], op: (A, B) =&gt; C): AmbType[C] =
        new OpAmb[C, (A, B)](amb, p =&gt; op(p._1, p._2))
  def pair[A, B](ambA: AmbType[A], ambB: AmbType[B]): AmbType[(A, B)] =
        new AmbPair[A, B](ambA, ambB)
}


Assume we have some numerical amb-value and want to square each element, then just call op with a corresponding function: op(amb(1, 2, 4), (e: Int) =&gt; e * e) // returns a value equivalent to amb(1, 4, 16) Following the same scheme you can convert the elements to boolean values for example with op(amb(1, 2, 4), (e: Int) =&gt; e%2 == 0)

If you have several amb-values and you want to define conditions between them, it isn't that easy to do with my approach when only using amb, require and op. Therefore I defined the method pair. With pair you can create tuples/pairs out of two amb-values (or any number if you again pair pairs with other values or pairs). If you then define conditions on top of this tuples, the illegal pairs will be eliminated. But the original values aren't always manipulated. Only if this process leads to the situation that one element from one of the initial amb-values is no longer legal in any tuple, than this value is completely eliminated from the initial amb-value. If now some other amb-value (or pair) is based on this manipulated amb-value, the dependent value will also miss the deleted element.

That means that if you need a pair of values fulfilling a condition, you have to get an element from the pair-value and you cannot always rely on the original values, but I think this is a acceptable limitation.

Just for convenience there is an additional op-method for tuples.

Now we have to dig deeper into the technical details of the amb-containers:

import scala.util.Random

trait AmbType[A] {
  def get: A = {
    if (list.isEmpty)
      throw new IllegalStateException("no value left")
    else list(Random.nextInt(list.length))}
  private[ambiguous] def list: List[A]
  private[ambiguous] def del(a: A): Unit
}

class BasicAmb[A](private var args: List[A]) extends AmbType[A] {
  override private[ambiguous] def list: List[A] = args
  override private[ambiguous] def del(a: A): Unit = { args = args.filterNot(_ == a)}
}

class OpAmb[A, B](amb: AmbType[B], op: B =&gt; A) extends AmbType[A] {
  override private[ambiguous] def list: List[A] = amb.list.map(op)
  override private[ambiguous] def del(a: A): Unit = amb.list.filter(op(_) == a).foreach(amb.del)
}

class AmbPair[A, B](ambA: AmbType[A], ambB: AmbType[B]) extends AmbType[(A, B)] {
  private var deleted: List[(A, B)] = List()
  override private[ambiguous] def list: List[(A, B)] =
    ambA.list.flatMap(a =&gt; ambB.list.map(b =&gt; (a, b))).diff(deleted)
  override private[ambiguous] def del(a: (A, B)): Unit = {
    deleted ::= a
    ambA.list.filter(a =&gt; !list.exists(_._1 == a)).foreach(a =&gt; {ambA.del(a); deleted = deleted.filterNot(_._1 == a)})
    ambB.list.filter(b =&gt; !list.exists(_._2 == b)).foreach(b =&gt; {ambB.del(b); deleted = deleted.filterNot(_._2 == b)})
  }
}


I don't want to say too much about the classes but one thing is worth mentioning: If you create pairs of two amb-values and define some conditions on top of them and afterwards define some further conditions on top of one of the original values, the pair-class misses to check if an element of the not-changed original value may be deleted as it doesn't appear as part of one pair any more. So some further observer-pattern would be great.

Now let's take a look on how to use this:

// create amb-values by invoking amb
val a = amb(1, 2, 3, 4)

// do some maths on a value
val b = op(a, (e: Int) =&gt; e + 2)

// define some conditions
require(b, (e: Int) =&gt; e%3 == 0)
// or first apply the condition to the value and afterwards pass the value to require
val filtered = op(b, (e: Int) =&gt; e%3 == 0)
require(filtered)

// pair values
val paired = pair(a, amb("hello", "welcome"))
// note that the amb-value a now only contains the elements 1 and 4 as the former requirement eliminated the other two

// state a condition on pairs
require(paired, (a: Int, b: String) =&gt; b.length % a == 0)
// now the amb-value a only contains the element 1 as there was no string with length divisible by 4

// query a value from our pairs (by calling get)
val selected = paired.get
// at this point only two pairs are left, so selected will always be either (1, "hello") or (1, "welcome")
val number = selected._1
val greetings = selected._2