Welcome, guest | Sign In | My Account | Store | Cart

This extends the previous "pythologic" recipe with resolution, based on unification and greattly inspired by the AIMA books and examples.

The author is not a python expert and expects to see this contribution further discussed and developed.

Python, 310 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#
# pythologic2.py
#
# Add logic programming (Prolog) syntax and *resolution* into Python.
# 
# (c) 2004 Francisco Coelho
# after (c) 2004 Shai Berger
# and AIMA examples
#

import string
import copy
 
class Struct:
    def __init__(self, database, head, subs):
        """
        The head and subs are essential - what makes this struct.
        The database should only be used while structs are constructed,
        and later removed.
        """
        self.database = database
        self.head = head
        self.subs = subs

    def __pos__(self):
        """
        unary + means insert into database as fact
        """
        self.database.add_fact(self)

    def __invert__(self):
        """
        unary ~ means insert into database as query
        """
        self.database.add_query(self)

    def __lshift__(self, requisites):
        """
        The ideal is
        consequent(args) << cond1(args1),...
        for now we must do with
        consequent(args) << [cond1(args1),...]
        """
        self.database.add_conditional(self, requisites)

    def __str__(self):
        subs = map (str, self.subs)
        return str(self.head) + "(" + string.join(subs,',') + ")"

class Symbol:
    def __init__ (self, name, database):
        self.name = name
        self.database = database
            
    def __call__(self, *args):
        return Struct(self.database, self, args)
            
    def __str__(self):
        return self.name

class Constant(Symbol):
    """
    A constant is a name. Its value is its name too.
    """
    def value(self): return self.name

class Variable(Symbol):
    pass


def symbol(name, database):
    if (name[0] in string.uppercase):
        return Variable(name,database)
    else:
        return Constant(name, database)
	
class Database:
    def __init__(self, name):
        self.name= name
        self.facts = []
        self.conditionals = []
        self.queries = []
            
    def add_fact(self, fact):
        self.facts.append(fact)

    def add_query(self, query):
        self.queries.append(query)
            
    def add_conditional(self,head,requisites):
        if not(isinstance(requisites, list)):
            requisites = [requisites]
        self.conditionals.append((head,requisites))

    def __str__(self):
        factsStr= string.join(map(str, self.facts),'\n')
        condsStr= ''
        for (h,r) in self.conditionals:
            condsStr = condsStr +  "%s << %s\n"%(h,string.join( map(str, r), ', '))
        queryStr= string.join( map(str, self.queries),'\n')
        return self.name + ' facts\n' + factsStr +'\n'+self.name + ' conditionals\n'+ condsStr  + '\n'+self.name + ' queries\n'+queryStr + '\n'

    def append(self, func):
        """
        Include definitions from func into database
        """
        try:
            code = func.func_code
        except:
            raise TypeError, "function or method argument expected"
        names = code.co_names
        locally_defined = code.co_varnames
        globally_defined = func.func_globals.keys()
        defined = locally_defined+tuple(globally_defined)
        undefined = [name for name in names if name not in defined]
        newglobals = func.func_globals.copy()
        for name in undefined:
            newglobals[name] = symbol(name, self)
        exec code in newglobals

    def __lshift__(self, func):
        """
        A helper for decorator implementation
        """
        self.append(func)
        return LogicalFunction(self, func)		
            
    def solve(self, V = [{}]):
        """        
        The query queue is LIFO:
        Extend valuations in V satisfying the last query.
        """
        def solve1( v ):
            # get solutions from facts
            unify_facts = [unify(query, fact, v) for fact in self.facts]

            # look for solutions from conditionals
            unify_conditionals = []            
            for ( header , condition_list ) in self.conditionals:
                u = unify(query, header , v) # unify headers
                U = [ u ]
                
                if u != None:
                    # remember query queue
                    oldQueries = copy.deepcopy(self.queries)

                    # we want to start by the first conditional
                    D = copy.copy( condition_list )
                    D.reverse() 
                    
                    # phase 1: append the conditionals to query queue
                    for condition in D:
                        if type( condition ) == type('string'):
                            # process python code
                            # should return True or False
                            self.queries.append( condition )
                            #eval_python_string( condition , u)
                        else:
                            # append the conditional,
                            # with variables replaced according to u
                            # to the query queue
                            unified_condition = subst(u, condition )
                            self.queries.append( unified_condition )

                    # phase 2: solve the appended conditionals
                    for condition in D:
                        U =  self.solve( U )

                    # restore query queue    
                    self.queries = oldQueries

                    # grow the list of solutions
                    unify_conditionals = unify_conditionals + U
            return [ u for u in (unify_facts + unify_conditionals) if not u in [None, {}] ] 
        
        if self.queries:
            query = self.queries[-1]
            del self.queries[-1]
        else:
            return []

        if type( query ) == type( 'string' ):
            U = [ v for v in V if python_eval_string(query, v) ]                    
        else:
            U = []
            
            for v in V:
                U = U + solve1(v)
            
        return U
                    
def python_eval_string(s, v):
    for k in v:
        s=string.replace(s, str(k), str(v[k]))
    return eval( s, {} )

def subst(v, x):
    if v.has_key(x):
        return v[x]
    elif isinstance(x, Variable):
        return x
    elif isinstance(x, Struct):
        return Struct( x.database, x.head, [subst(v, xi) for xi in x.subs])

def unify(x,y,v={}):
    """
    Find one valuation extending v and unifying x with y
    """
    
    def extend(v, x, t):
        """
        Extend valuation v with v[x] = t
        """
        v1 = copy.copy(v)
        v1[x] = t
        return v1

    def occur_check(x, t):
        """
        Test if the variable x occurr in structure t
        """
        if x == t:
            return True
        elif isinstance(t, Struct):
            return t.head == x.head or occur_check(x, t.subs)
        return False

    def unify_var(x, t, v):
        """
        Test if v can be extended with v[x] = t;
        In that case return the extention
        Else return None
        """
        if x in v:
            return unify( v[ x ], t, v)
        elif occur_check(x, t):
            return None
        else:
            return extend(v, x, t)

    if v == None:
        return None
    elif x == y:
        return v
    elif isinstance(x, Variable):
        return unify_var(x, y, v)
    elif isinstance(y, Variable):
        return unify_var(y, x, v)
    elif isinstance(x, Struct) and isinstance(y, Struct) and (x.head == y.head):
        z = v
        n = len(x.subs)
        m = len(y.subs)
        if n == m:
            for i in range( n ):
                z = unify( x.subs[i], y.subs[i], z)
            return z
        else:
            return None
    else:
        return None

    
class LogicalFunction:
    """
    This class replaces a logical function once it has
    been consulted, to avoid erroneous use
    """
    def __init__(self, database, func):
        self.database=database
        self.logical_function=func
    def __call__(self):
        raise TypeError, "Logical functions are not really callable"

if __name__ == "__main__":

    db = Database('TEST')

    print "Defining a prolog program... ",

    def prolog_func():
        
        # prolog facts are prefixed with "+"
        + number(0) 
        + number(1)
        + number(2)
        + number(3)
        + number(4)

        # prolog conditionals have the pattern p << [q1, ..., qn]
        test(X, Y) << [number(X),  number(Y), 'X==2*Y' ]
        
        # prolog queries are prefixed with "~"
        ~ test(X, Y)
        
    # Update the database
    db << prolog_func
    print "done"

    print "Before solving"
    print db
    
    # Solve the queries
    x = db.solve()
    print 'Solutions'
    for v in x:
        for k in v: print k,"=", v[k],' ',
        print

    print "After solving"
    print db

The elegant recipe "Pythologic -- Prolog syntax in Python" settles a base for logic programming in python. However, it lacks resolution/query features: The user can define a prolog-like database e.g.

p(1) p(2) q(X,Y) :- p(X), p(Y)

but can't ask for the possible values of X and Y that verify

q(X,Y)

This recipe tries to solve that: The database can recieve a query (prefixed with ~) and has a .solve() method returning all the variable assignments satisfying the query. In the previous example, the returned assignments are

X=1 Y=1, X=1 Y=2, X=2 Y=1 and X=2 Y=2.

It turns out that it is easy to embed python code into conditionals. Look at the example in the code: the string 'X==2*Y' is evaluated as python code, with the variables X and Y replaced by appropriated values.

See Shai Berger's recipe in http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/303057 for the original "pythologic.py".

I've added little changes to the original "consult_and_transform" functions and respective decorators. First, since I'm in python 2.3, I'm not using decorators. Second, I liked so much the operator overloading that I'm using "<<" instead of "@logical"

3 comments

Francisco Coelho (author) 16 years, 11 months ago  # | flag

Yes, and pylog is a better "prolog-in-python"...

Shai Berger 16 years, 11 months ago  # | flag

Thanks and suggestions. Hi,

First of all, thank you for the compliment. Seeing this was a very nice and welcome surprise.

Second, there are a few comments I want to make, to help improve the recipe.

One is in the Python implementation: Look up Generators. The list of solutions to a Prolog-like query simply begs for lazy evaluation. Generators have been in Python since 2.2, I think, and 2.4 has "generator expressions", which are the generator parallels of list comprehensions.

Another is that the decorator in my recipe has a couple of advantages over the overloaded operator. One is documentational: with a decorator, the logical function declares itself up-front as special, whereas with your implementation this is left for comments and code after the function. More importantly, the decorator hides the reference to the original function, where your code does not (the relevant line can be fixed to "func = db << func" but that is a lot less pretty).

Also, I think putting the queries in the database for them to be solved is a little odd. I expect a database to be usable for answering several queries, one at a time, with no interactions between them, and this way I can't solve a new query without solving all the past queries. Or am I missing something? (my first thought was "he wants all queries to be defined in advance?!", but, of course, queries can be added later because more logical functions can be appended).

Created by Francisco Coelho on Fri, 24 Dec 2004 (PSF)
Python recipes (4591)
Francisco Coelho's recipes (1)

Required Modules

Other Information and Tasks