[pypy-dev] Re: [pypy-svn] r22640 - pypy/dist/pypy/lib/logic
Ben.Young at risk.sungard.com
Ben.Young at risk.sungard.com
Wed Jan 25 14:41:03 CET 2006
Hi,
Did you mean to put something GPL'd into PyPy? I thought PyPy has a
licence equivalent to Python?
Cheers,
Ben
pypy-svn-bounces at codespeak.net wrote on 25/01/2006 12:50:29:
> Author: auc
> Date: Wed Jan 25 13:50:25 2006
> New Revision: 22640
>
> Added:
> pypy/dist/pypy/lib/logic/distributor.py
> Modified:
> pypy/dist/pypy/lib/logic/computationspace.py
> pypy/dist/pypy/lib/logic/test_computationspace.py
> pypy/dist/pypy/lib/logic/test_unification.py
> pypy/dist/pypy/lib/logic/test_variable.py
> pypy/dist/pypy/lib/logic/unification.py
> pypy/dist/pypy/lib/logic/variable.py
> Log:
> (ale, auc)
> * add distributor from logilab constraint solver
> * adapt it
> * method to get vars by name
> * tests
>
>
> Modified: pypy/dist/pypy/lib/logic/computationspace.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/computationspace.py (original)
> +++ pypy/dist/pypy/lib/logic/computationspace.py Wed Jan 25 13:50:25
2006
> @@ -141,15 +141,15 @@
> ## Choose
> ## ------
>
> -## Y=choose(N) waits until the current space becomes stable, blocks the
> -## current thread, and then creates a choice point with N alternatives
> -## in the current space. The blocked choose call waits for an
> -## alternative to be chosen by a commit operation on the space. The
> -## choose call only defines how many alternatives there are; it does
> -## not specify what to do for an alternative. Eventually, choose
> -## continues its execution with Y=I when alternative I (1=<I=<N) is
> -## chosen. A maximum of one choice point may exist in a space at any
> -## time.
> +## Y=choose(N) waits until the current space becomes stable, blocks
> +## the current thread, and then creates a choice point with N
> +## alternatives in the current space. The blocked choose call waits
> +## for an alternative to be chosen by a commit operation on the
> +## space. The choose call only defines how many alternatives there
> +## are; it does not specify what to do for an alternative. Eventually,
> +## choose continues its execution with Y=I when alternative I
> +## (1=<I=<N) is chosen. A maximum of one choice point may exist in a
> +## space at any time.
>
> ## Ask
> ## ---
> @@ -180,6 +180,9 @@
> class Unprocessed:
> pass
>
> +class Working:
> + pass
> +
> class Failed:
> pass
>
> @@ -200,20 +203,30 @@
> self.store = Store()
> self.status = Unprocessed
> self.root = self.store.var('root')
> - self.store.bind(self.root, program(self.store))
> + self.store.bind(self.root, program(self))
> +
> + def _stable(self):
> + #XXX: really ?
> + return self.status in (Failed, Succeeded, Merged)
> +
> + def _distributable(self):
> + pass
> + #return not self._stable
> +
> + def set_distributor(self, dist):
> + self.distributor = dist
>
> def ask(self):
> # XXX: block on status being not stable for threads
> if self._stable():
> return self.status
> + #return self.store.nb_candidates()
> else:
> #TBD
> return self.status
>
> - def _stable(self):
> - return self.status in (Failed, Succeeded, Merged)
> -
> def process(self):
> + self.status = Working
> try:
> self.store.satisfy_all()
> except ConsistencyFailure:
> @@ -221,9 +234,10 @@
> else:
> self.status = Succeeded
>
> -
> - def branch(self):
> + def make_child(self):
> return ComputationSpace(self.program, parent=self)
>
> -# def choose(self, alternative):
> -
> + def choose(self, alternative):
> + """distribute the domains to new spaces
> + create the spaces"""
> +
>
> Added: pypy/dist/pypy/lib/logic/distributor.py
>
==============================================================================
> --- (empty file)
> +++ pypy/dist/pypy/lib/logic/distributor.py Wed Jan 25 13:50:25 2006
> @@ -0,0 +1,172 @@
> +# (c) 2000-2001 LOGILAB S.A. (Paris, FRANCE).
> +# http://www.logilab.fr/ -- mailto:contact at logilab.fr
> +#
> +# This program is free software; you can redistribute it and/or
> modify it under
> +# the terms of the GNU General Public License as published by the
> Free Software
> +# Foundation; either version 2 of the License, or (at your option) any
later
> +# version.
> +#
> +# This program is distributed in the hope that it will be useful, but
WITHOUT
> +# ANY WARRANTY; without even the implied warranty of
> MERCHANTABILITY or FITNESS
> +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for
> more details.
> +#
> +# You should have received a copy of the GNU General Public
Licensealong with
> +# this program; if not, write to the Free Software Foundation, Inc.,
> +# 59 Temple Place - Suite 330, Boston, MA 02111-1307
> +# USA.
> +
> +"""
> +distributors - part of Logilab's constraint satisfaction solver.
> +"""
> +
> +__revision__ = '$Id: distributors.py,v 1.25 2005/01/14 15:16:21 alf Exp
$'
> +
> +import math, random
> +
> +def make_new_domains(domains):
> + """return a shallow copy of dict of domains passed in argument"""
> + domain = {}
> + for key, value in domains.items():
> + domain[key] = value.copy()
> + return domain
> +
> +class AbstractDistributor(object):
> + """_distribute is left unimplemented."""
> +
> + def __init__(self, nb_subspaces=2):
> + self.nb_subspaces = nb_subspaces
> + self.verbose = 0
> +
> + def findSmallestDomain(self, domains):
> + """returns the variable having the smallest domain.
> + (or one of such varibles if there is a tie)
> + """
> + domlist = [(dom.size(), variable ) for variable, dom in
> domains.items()
> + if dom.size() > 1]
> + domlist.sort()
> + return domlist[0][1]
> +
> + def findLargestDomain(self, domains):
> + """returns the variable having the largest domain.
> + (or one of such variables if there is a tie)
> + """
> + domlist = [(dom.size(), variable) for variable, dom in
> domains.items()
> + if dom.size() > 1]
> + domlist.sort()
> + return domlist[-1][1]
> +
> + def nb_subdomains(self, domains):
> + """return number of sub domains to explore"""
> + return self.nb_subspaces
> +
> + def distribute(self, domains, verbose=0):
> + """do the minimal job and let concrete class distribute
variables
> + """
> + self.verbose = verbose
> + replicas = []
> + for i in range(self.nb_subdomains(domains)):
> + replicas.append(make_new_domains(domains))
> + modified_domains = self._distribute(*replicas)
> + for domain in modified_domains:
> + domain.reset_flags()
> + return replicas
> +
> + def _distribute(self, *args):
> + """ method to implement in concrete class
> +
> + take self.nb_subspaces copy of the original domains as argument
> + distribute the domains and return each modified domain
> + """
> + raise NotImplementedError("Use a concrete implementation of "
> + "the Distributor interface")
> +
> +class NaiveDistributor(AbstractDistributor):
> + """distributes domains by splitting the smallest domain in 2 new
domains
> + The first new domain has a size of one,
> + and the second has all the other values"""
> +
> + def __init__(self):
> + AbstractDistributor.__init__(self)
> +
> + def _distribute(self, dom1, dom2):
> + """See AbstractDistributor"""
> + variable = self.findSmallestDomain(dom1)
> + values = dom1[variable].get_values()
> + if self.verbose:
> + print 'Distributing domain for variable', variable, \
> + 'at value', values[0]
> + dom1[variable].remove_values(values[1:])
> + dom2[variable].remove_value(values[0])
> + return (dom1[variable], dom2[variable])
> +
> +
> +class RandomizingDistributor(AbstractDistributor):
> + """distributes domains as the NaiveDistrutor, except that the
unique
> + value of the first domain is picked at random."""
> +
> + def __init__(self):
> + AbstractDistributor.__init__(self)
> +
> + def _distribute(self, dom1, dom2):
> + """See AbstractDistributor"""
> + variable = self.findSmallestDomain(dom1)
> + values = dom1[variable].get_values()
> + distval = random.choice(values)
> + values.remove(distval)
> + if self.verbose:
> + print 'Distributing domain for variable', variable, \
> + 'at value', distval
> + dom1[variable].remove_values(values)
> + dom2[variable].remove_value(distval)
> + return (dom1[variable], dom2[variable])
> +
> +
> +class SplitDistributor(AbstractDistributor):
> + """distributes domains by splitting the smallest domain in
> + nb_subspaces equal parts or as equal as possible.
> + If nb_subspaces is 0, then the smallest domain is split in
> + domains of size 1"""
> +
> + def __init__(self, nb_subspaces=3):
> + AbstractDistributor.__init__(self, nb_subspaces)
> + self.__to_split = None
> + def nb_subdomains(self, domains):
> + """See AbstractDistributor"""
> + self.__to_split = self.findSmallestDomain(domains)
> + if self.nb_subspaces:
> + return min(self.nb_subspaces,
domains[self.__to_split].size())
> + else:
> + return domains[self.__to_split].size()
> +
> + def _distribute(self, *args):
> + """See AbstractDistributor"""
> + variable = self.__to_split
> + nb_subspaces = len(args)
> + values = args[0][variable].get_values()
> + nb_elts = max(1, len(values)*1./nb_subspaces)
> + slices = [(int(math.floor(index * nb_elts)),
> + int(math.floor((index + 1) * nb_elts)))
> + for index in range(nb_subspaces)]
> + if self.verbose:
> + print 'Distributing domain for variable', variable
> + modified = []
> + for (dom, (end, start)) in zip(args, slices) :
> + dom[variable].remove_values(values[:end])
> + dom[variable].remove_values(values[start:])
> + modified.append(dom[variable])
> + return modified
> +
> +class DichotomyDistributor(SplitDistributor):
> + """distributes domains by splitting the smallest domain in
> + two equal parts or as equal as possible"""
> + def __init__(self):
> + SplitDistributor.__init__(self, 2)
> +
> +
> +class EnumeratorDistributor(SplitDistributor):
> + """distributes domains by splitting the smallest domain
> + in domains of size 1."""
> + def __init__(self):
> + SplitDistributor.__init__(self, 0)
> +
> +DefaultDistributor = DichotomyDistributor
>
> Modified: pypy/dist/pypy/lib/logic/test_computationspace.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/test_computationspace.py (original)
> +++ pypy/dist/pypy/lib/logic/test_computationspace.py Wed Jan 25
> 13:50:25 2006
> @@ -2,24 +2,27 @@
> import variable as v
> import constraint as c
> import computationspace as cs
> +import distributor as di
> from py.test import raises
>
> -def satisfiable_problem(store):
> - s = store # i'm lazy
> +def satisfiable_problem(computation_space):
> + cs = computation_space
> + s = cs.store
> x, y, z, w = (s.var('x'), s.var('y'),
> s.var('z'), s.var('w'))
> s.set_domain(x, c.FiniteDomain([2, 6]))
> s.set_domain(y, c.FiniteDomain([2, 3]))
> s.set_domain(z, c.FiniteDomain([4, 5]))
> - s.set_domain(w, c.FiniteDomain([1, 4, 5]))
> + s.set_domain(w, c.FiniteDomain([1, 4, 5, 6, 7]))
> s.add_constraint(c.Expression([x, y, z], 'x == y + z'))
> s.add_constraint(c.Expression([z, w], 'z < w'))
> - # we don't know yet how to
> # set up a distribution strategy
> + cs.set_distributor(di.DichotomyDistributor())
> return (x, w, y)
>
> -def unsatisfiable_problem(store):
> - s = store # i'm lazy
> +def unsatisfiable_problem(computation_space):
> + cs = computation_space
> + s = cs.store
> x, y, z, w = (s.var('x'), s.var('y'),
> s.var('z'), s.var('w'))
> s.set_domain(x, c.FiniteDomain([2, 6]))
> @@ -28,8 +31,8 @@
> s.set_domain(w, c.FiniteDomain([1]))
> s.add_constraint(c.Expression([x, y, z], 'x == y + z'))
> s.add_constraint(c.Expression([z, w], 'z < w'))
> - # we don't know yet how to
> # set up a distribution strategy
> + cs.set_distributor(di.DichotomyDistributor())
> return (x, w, y)
>
>
> @@ -56,5 +59,23 @@
> assert spc.ask() == cs.Unprocessed
> spc.process()
> assert spc.ask() == cs.Failed
> -
> -
> +
> + def test_distribute(self):
> + spc = cs.ComputationSpace(satisfiable_problem)
> + spc.process()
> + domains = dict([(var, var.dom) for var in spc.store.vars
> + if var.dom])
> + new_domains = spc.distributor.distribute(domains)
> + x, y, z, w = (spc.store.get_var_by_name('x'),
> + spc.store.get_var_by_name('y'),
> + spc.store.get_var_by_name('z'),
> + spc.store.get_var_by_name('w'))
> + assert new_domains == [{x: c.FiniteDomain([6]),
> + y: c.FiniteDomain([2]),
> + z: c.FiniteDomain([4]),
> + w: c.FiniteDomain([5])},
> + {x: c.FiniteDomain([6]),
> + y: c.FiniteDomain([2]),
> + z: c.FiniteDomain([4]),
> + w: c.FiniteDomain([6, 7])}]
> +
>
> Modified: pypy/dist/pypy/lib/logic/test_unification.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/test_unification.py (original)
> +++ pypy/dist/pypy/lib/logic/test_unification.py Wed Jan 25 13:50:25
2006
> @@ -21,7 +21,7 @@
>
> def test_already_in_store(self):
> x = u.var('x')
> - raises(v.AlreadyExists, u.var, 'x')
> + raises(v.AlreadyInStore, u.var, 'x')
>
> def test_already_bound(self):
> x = u.var('x')
>
> Modified: pypy/dist/pypy/lib/logic/test_variable.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/test_variable.py (original)
> +++ pypy/dist/pypy/lib/logic/test_variable.py Wed Jan 25 13:50:25 2006
> @@ -24,10 +24,14 @@
> def setup_method(self, meth):
> u._store = u.Store()
>
> -
> def test_no_same_name(self):
> x = u.var('x')
> - raises(v.AlreadyExists, u.var, 'x')
> + raises(u.AlreadyInStore, u.var, 'x')
> +
> + def test_get_by_name(self):
> + x = u.var('x')
> + assert x == u._store.get_var_by_name('x')
> + raises(u.NotInStore, u._store.get_var_by_name, 'y')
>
> def test_one_thread_reading_one_var(self):
> cons = Consumer()
>
> Modified: pypy/dist/pypy/lib/logic/unification.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/unification.py (original)
> +++ pypy/dist/pypy/lib/logic/unification.py Wed Jan 25 13:50:25 2006
> @@ -120,7 +120,8 @@
>
> import threading
>
> -from variable import EqSet, Var, VariableException, NotAVariable
> +from variable import EqSet, Var, \
> + VariableException, NotAVariable, AlreadyInStore
> from constraint import FiniteDomain, ConsistencyFailure
>
> #----------- Store Exceptions ----------------------------
> @@ -132,9 +133,9 @@
> def __str__(self):
> return "%s is already bound" % self.name
>
> -class AlreadyInStore(VariableException):
> +class NotInStore(VariableException):
> def __str__(self):
> - return "%s already in store" % self.name
> + return "%s not in the store" % self.name
>
> class OutOfDomain(VariableException):
> def __str__(self):
> @@ -169,9 +170,9 @@
> (also called determined variables)."""
>
> def __init__(self):
> - # mapping of names to vars (all of them)
> self.vars = set()
> - self.names = set()
> + # mapping of names to vars (all of them)
> + self.names = {}
> # set of all constraints
> self.constraints = set()
> # consistency-preserving stuff
> @@ -193,7 +194,7 @@
> raise AlreadyInStore(var.name)
> print "adding %s to the store" % var
> self.vars.add(var)
> - self.names.add(var.name)
> + self.names[var.name] = var
> # put into new singleton equiv. set
> var.val = EqSet([var])
>
> @@ -203,6 +204,12 @@
> if var.is_bound():
> raise AlreadyBound
> var.dom = FiniteDomain(dom)
> +
> + def get_var_by_name(self, name):
> + try:
> + return self.names[name]
> + except KeyError:
> + raise NotInStore(name)
>
> #-- Constraints -------------------------
>
>
> Modified: pypy/dist/pypy/lib/logic/variable.py
>
==============================================================================
> --- pypy/dist/pypy/lib/logic/variable.py (original)
> +++ pypy/dist/pypy/lib/logic/variable.py Wed Jan 25 13:50:25 2006
> @@ -7,13 +7,13 @@
> def __init__(self, name):
> self.name = name
>
> -class NotAVariable(VariableException):
> +class AlreadyInStore(VariableException):
> def __str__(self):
> - return "%s is not a variable" % self.name
> + return "%s already in store" % self.name
>
> -class AlreadyExists(VariableException):
> +class NotAVariable(VariableException):
> def __str__(self):
> - return "%s already exists" % self.name
> + return "%s is not a variable" % self.name
>
> #----------- Variables ----------------------------------
> class EqSet(set):
> @@ -32,7 +32,7 @@
>
> def __init__(self, name, store):
> if name in store.names:
> - raise AlreadyExists(name)
> + raise AlreadyInStore(name)
> self.name = name
> self.store = store
> # top-level 'commited' binding
> @@ -98,16 +98,10 @@
> def add_constraint(self, constraint):
> self.constraints.add(constraint)
>
> - #---- Concurrent public ops --------------------------
> + is_bound = _is_bound
>
> - def is_bound(self):
> - try:
> - self.mutex.acquire()
> - res = self._is_bound()
> - finally:
> - self.mutex.release()
> - return res
>
> + #---- Concurrent public ops --------------------------
> # should be used by threads that want to block on
> # unbound variables
> def get(self):
> _______________________________________________
> pypy-svn mailing list
> pypy-svn at codespeak.net
> http://codespeak.net/mailman/listinfo/pypy-svn
>
More information about the Pypy-dev
mailing list