Amb In Python

last modified: July 8, 2008

From PythonTranslator, GabrieleRenzi raises the question of how to do (implementation of Amb is found in AmbInRuby):

amb = Amb.new
a, b, c, d = Array.new(4){amb.choose 1, 2, 3, 5, 7 },
if tot == a * b * c * d
  puts "#{tot}, == #{a}, * #{b}, * #{c}, * #{d},"
else
  amb.fail
end

if tot == a * b  * c
    puts "#{tot}, == #{a}, * #{b}, * #{c}, "
else
    amb.fail
end

gives:

105 == 1 * 3 * 5 * 7
105 == 1 * 3 * 7 * 5
105 == 1 * 5 * 3 * 7
105 == 1 * 5 * 7 * 3
105 == 1 * 7 * 3 * 5
105 == 1 * 7 * 5 * 3
105 == 3 * 1 * 5 * 7
105 == 3 * 1 * 7 * 5
105 == 3 * 5 * 1 * 7
105 == 3 * 5 * 7 * 1
105 == 3 * 5 * 7

This appears to be truncated...

For your amusement - AmbInPython. It could be made a lot more robust, but hey - it works without needing call/cc which is good because generators give me enough of a headache as it is, and anyway, only StacklessPython has continuations ;-):


Actually, that's not true anymore. As of Python 2.5, generators are now equivalent to coroutines. Since you can build continuations on top of coroutines, you can say Python 2.5+ has continuations.

OTOH, I don't know that anyone's actually written call/cc for Python yet. Come to think of it, it was probably possible in earlier versions by hacking sys._getframe. Hmm... ContinuationsInPython anyone?

--PaulMiller (a loyal pythonista)

The argument: I can build X in Y therefore I have X in Y fails. Beware the TuringTarpit, where it is possible to say anything but nothing of interest is easy to say. Language support for any feature, including continuations, implies a degree of syntactic simplicity in achieving it.


import random
class Amb(object):
    def __init__(self, choices=[], constraints=[], n=1,
                 msg="%s", error = "Failed!"):
        random.shuffle(choices)   # Non-determinism ;-)
        self.choices = choices
        self.constraints = constraints
        self.n = n
        self.msg = msg
        self.error = error

    def __iter__(self):
        fail = True
        for choice in self.choose(self.choices, self.n):
            if False not in [c(choice) for c in self.constraints]:
                if self.n == 1:
                    choice = choice[0]
                yield choice
                fail = False
        if fail:
            raise ValueError

    def choose(self, choices, n):
        if n == 0:
            yield []
        else:
            for i in range(len(choices)):
                for c in self.choose(choices[:i] + choices[i+1:],n-1):
                    if isinstance(choices[i],Amb):
                        try:
                            for elem in choices[i]:
                                yield [elem] + c
                        except ValueError:
                            pass
                    else:
                        yield [choices[i]] + c

    def format(self, msg, item):
        try:
            return msg%(item)
        except TypeError:
            try:
                return msg%tuple(item)
            except TypeError:
                print msg, item

    def get_one(self):
        for item in self:
            return self.format(self.msg, item)

    def __str__(self):
        try:
            return "\n".join([self.format(self.msg, item) for item in self])
        except ValueError:
            return self.format(self.error, self.choices)


import operator

def printchoices(n, total, choices):
    print Amb(choices,
              [lambda item: total==reduce(operator.mul,item)],
              n,
              "%s == "%total + "%s" + " * %s" * (n-1),
              "Can't multiply %s elements of "%n+"%s"+" to get %s."%total,
             )

mylist = [1,2,3,5,7]
printchoices(4, 105, mylist)
printchoices(3, 105, mylist) 
printchoices(2, 105, mylist) 
print "---"


w = Amb(["oo", "or", "og"])
x = Amb(["foo", "bar", "baz", "fob"])
y = Amb(["foe", "baf", "baz", "boaz","oaz"])
z = Amb(["o", "e", "i"])

print Amb([w,x,y,z],
          [lambda (a,b,c):(a+b).replace(c,"") == "fbaz"],
          n=3,
          msg="found: %s %s %s",
          error="No combinations match.")
print "---"


x = Amb(range(10))
y = Amb(range(10))
z = Amb(range(10))

a = Amb([x,y,z],
        [lambda (a,b,c): (0<a<=b<c) and (a**2 + b**2 == c**2)],
        n=3,
        msg="a==%s, b==%s, c==%s",
        error="No Pythagorean triples"
       )          

# This will print out 6 lines - a feature not a bug since
# There are 3*2*1 sets of identical combinations...
print a
print "---"
print a.get_one()
print "---"

print Amb()
print Amb([Amb(), Amb(), Amb()])
print Amb([Amb(), Amb(), Amb(), 1])
print Amb([Amb(), Amb(), Amb([Amb([1])]), Amb()])

Also see: AmbInRuby, PythonTranslator, AmbSpecialForm


CategoryPython


Loading...