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@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@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@codespeak.net http://codespeak.net/mailman/listinfo/pypy-svn