~ubuntu-branches/ubuntu/karmic/pypy/karmic

<div id="menubar"><a class="menu" href="http://codespeak.net/pypy/dist/pypy/doc/news.html">news</a> <a class="menu" href="../getting-started.html">getting-started</a> <a class="menu" href="../index.html">documentation</a> <a class="menu" href="https://codespeak.net/viewvc/pypy/dist/">svn</a> <a class="menu" href="https://codespeak.net/issue/pypy-dev/">issues</a><a class="menu" href="../contact.html">contact</a> <a class="menu" href="http://pypy.org/">EU/project</a> </div></div>

<h1 class="title">Some ideas about implementation of Logic Programming</h1>

<h1><a id="the-problem" name="the-problem">The problem</a></h1>

<h2><a id="basics" name="basics">Basics</a></h2>

<p>Logic and contraint programming as envisionned in PyPy draws heavily

on the Computation Space concept present in the Oz language.</p>

<p>Computation spaces provide an infrastructure and API that allows

seamless integration of concurrent constraint and logic programming in

the language.</p>

<p>Currently, there is an implementation of computation spaces that is

sufficient enough for constraint solving. It uses :</p>

<p>ask()

clone()

commit()</p>

<p>in straightforward ways. This space is merely a constraint store for

finite domain constraint variables. It does not really support

execution of arbitrary computations 'inside' the space ; only

constraint propagation, i.e. a fixed interrpeter-level algorithm, is

triggered on commit() calls. [note: don't look at the current code ...]</p>

</div>

<h2><a id="choice-points" name="choice-points">Choice points</a></h2>

<p>For logic programming we need more. Basically a 'logic program' is a

standard Python program augmented with the 'choice' operator. The

program's entry point must be a zero arity procedure. Any program

whose execution path contains a 'choice' is a logic, or relational (in

Oz parlance) program.</p>

<p>For instance:</p>

def foo():

choice:

return bar()

or:

from math import sqrt

return sqrt(4)

def bar():

choice: return 0 or: return 1

def entry_point():

a = foo()

if a < 2:

fail()

return a

</pre>

<p>What should happen when we encounter a choice ? One of the choice

points ought to be chosen 'non-deterministically'. That means that the

decision to choose does not belong to the program istelf (it is not an

'if clause' depending on the internal state of the program) but to

some external entity having interest in the program outcomes depending

on the various choices that can be made in a choice-littered program.</p>

<p>Such an entity is typically a 'solver' exploring the space of the

program outcomes. The solver can use a variety of search strategies,

for instance depth-first, breadth-first, discrepancy search,

best-search, A* ... It can provide just one solution or some or all of

them.</p>

<p>Thus the program and the methods to extract information from it are

truly independant, contrarily to Prolog programs which are hard-wired

for depth-first exploration (and do not support concurrency, at least

not easily).</p>

</div>

<h2><a id="choice-continued" name="choice-continued">Choice, continued</a></h2>

<p>The above program contains just one choice point. If given to a depth

first search solver, it will produce three spaces : the two first

spaces will be failed and thus discarded, the third will be a solution

space and ready to be later merged. We leave the semantics of space

merging for another day.</p>

<p>Pardon the silly ascii art:</p>

entry_point -> foo : choice

/ \

/ 2 (solution)

bar : choice

/ \

0 1

(failure)(failure)

</pre>

</div>

100

101

<h2><a id="search-and-spaces" name="search-and-spaces">Search and spaces</a></h2>

102

<p>To allow this de-coupling between program execution and search

103

strategy, the computation space comes handily. Basically, choices are

104

made, and program branches are taken, in speculative computations

105

which are embedded, or encapsulated in the so-called computation

106

space, and thus do not affect the whole program, nor each other, until

107

some outcome (failure, values, updated speculative world) is

108

considered and eventually merged back into the parent world (which

109

could be the 'top-level' space, aka normal Python world, or another

110

speculative space).</p>

111

<p>For this we need another method of spaces :</p>

112

<p>choose()</p>

113

<p>The choice operator can be written straightforwardly in terms of

114

choose:</p>

115

116

def foo():

117

choice = choose(3)

118

if choice == 1:

119

return 1

120

elif choice == 2:

121

from math import sqrt

122

return sqrt(4)

123

else: # choice == 3

124

return 3

125

</pre>

126

<p>Choose is more general than choice since the number of branches can be

127

determined at runtime. Conversely, choice is a special case of choose

128

where the number of branches is statically determined. It is thus

129

possible to provide syntactic sugar for it.</p>

130

<p>It is important to see the relationship between ask(), choose() and

131

commit(). Ask and commit are used by the search engine running in the

132

top-level space, in its own thread, as follows :</p>

133

<p>ask() wait for the space to be 'stable', which means that the program

134

running inside is blocked on a choose() call. It returns precisely the

135

value provided by choose, thus notifying the search engine about the

136

number of available choice points. The search engine can then,

137

depending on its strategy, commit() the space to one of its branches,

138

thus unblocking the choose() call and giving a return value which

139

represent the branch to be taken. The program encapsulated in the

140

space can thus run until :</p>

141

142

<li>it encounters another choice point,</li>

143

<li>it fails (by way of explicitly calling the fail() operator, or

144

raising an uncatched exception up to its entry point),</li>

145

<li>properly terminating, thus being a candidate 'satisfying' solution

146

to the problem it stands for.</li>

147

</ul>

148

<p>Commit and choose allow a disciplined communication between the world

149

of the search engine (the normal Python world) and the speculative

150

computation embedded in the space. Of course the search and the

151

embedded computation run in different threads. We need at least one

152

thread for the search engine and one per space for this scheme to

153

work.</p>

154

</div>

155

156

<h2><a id="cloning" name="cloning">Cloning</a></h2>

157

<p>The problematic thing for us is what happens before we commit to a

158

specific choice point. Since the are many of them, the solver

159

typically needs to take a snapshot of the current computation space so

160

as to be able to later try the other choice points (possibly all of

161

them if it has been asked to enumerate all solutions of a relational

162

or constraint program).</p>

163

<p>Taking a snapshot, aka cloning, is easy when the space is merely a

164

constraint store. It is more involved when it comes to snapshotting a

165

whole tree of threads. It is akin to saving and making copies of the

166

current continuation (up to some thread frame).</p>

167

</div>

168

</div>

169

170

<h1><a id="solutions-or-ideas-in-the-direction-of" name="solutions-or-ideas-in-the-direction-of">Solutions, or ideas in the direction of</a></h1>

171

172

<h2><a id="copying-collector" name="copying-collector">Copying collector</a></h2>

173

<p>In Mozart computation space cloning is implemented by leveraging the

174

copying garbage collector. There is basically a switch on the GC entry

175

point which tells whether it is asked to really do GC or just clone a

176

space.</p>

177

</div>

178

179

<h2><a id="thread-cloning" name="thread-cloning">Thread cloning</a></h2>

180

<p>It is expected that PyPy coroutines/greenlets/microthreads be at some

181

point picklable. One could implement clone() using the thread pickling

182

machinery.</p>

183

<p>Such is the abstract interface of computation spaces (the

184

inherit-from-threads part is a bit speculative):</p>

185

186

class MicroThread ...

187

"provided by PyPy, stackless team"

188

189

class CompSpace(Microthread):

190

191

"""solver API"""

192

193

def ask(self):

194

"""

195

blocks until the space is stable, which means that

196

the embedded computation has reached a fixpoint

197

returns int in [0,1,n]

198

0 : space is failed (further calls to the

199

space raise an exception)

200

1 : space is entailed (solution found)

201

n : space is distributable (n choice points)

202

"""

203

204

def commit(self, choice):

205

"""tells the space which choice point to pick"""

206

207

def clone(self):

208

"""returns a cloned computation space"""

209

210

def merge(self):

211

"""

212

extract solution values from an entailed space

213

furher calls to space methods will raise

214

an exception

215

"""

216

217

"""distributor API"""

218

219

def choose(self):

220

"""

221

blocks until commit is called

222

returns the choice value that

223

was given to the commit call

224

"""

225

226

def fail(self):

227

"""

228

mark the space as failed

229

"""

230

231

"""

232

constraint stuff : a space acts as/contains a constraint

233

store which holds : logic variables, constraint variables

234

(logic vars augmented with finite domains), constraints

235

"""

236

237

def var(self, domain, name=None):

238

"""

239

creates a possibly named contraint variable inside

240

the space, returns the variable object

241

"""

242

243

def tell(self, constraint):

244

"""register a constraint"""

245

</pre>

246

<p>Programs runing in a computation spaces should not be allowed to alter

247

the top-level space (i.e interaction with the global program state and

248

outside world).</p>

249

</div>

250

</div>

251

</div>

252

</div></body></html>

b'\\ No newline at end of file'

Older »