• R/O
  • HTTP
  • SSH
  • HTTPS

提交

标签
No Tags

Frequently used words (click to add to your profile)

javac++androidlinuxc#windowsobjective-ccocoa誰得qtpythonphprubygameguibathyscaphec計画中(planning stage)翻訳omegatframeworktwitterdomtestvb.netdirectxゲームエンジンbtronarduinopreviewer

A categorical programming language


Commit MetaInfo

修订版c712d3d6d6f37ee20b18f5ec0a874a6f5bf9097f (tree)
时间2023-03-25 14:30:25
作者Corbin <cds@corb...>
CommiterCorbin

Log Message

Use general recursion to implement folds.

This required extending the queue of curried arrows to a more general
pending-arrow queue which can emit several types of subroutines. Along
the way, I fixed some disassembler bugs, factored some text handling,
and tightened up the data model a bit.

更改概述

差异

--- a/sampler/cammylib/arrows.py
+++ b/sampler/cammylib/arrows.py
@@ -3,7 +3,7 @@ import math
33 from rpython.rlib.objectmodel import specialize
44 # from rpython.rlib.rbigint import rbigint
55
6-from cammylib.elements import F, N, thePoint, theTrue, theFalse, endOfList
6+from cammylib.elements import F, N, thePoint, theTrue, theFalse
77
88
99 def arrowEq(arr1, arr2): return arr1 is arr2 or arr1.eq(arr2)
@@ -276,7 +276,7 @@ class PrimRec(Arrow):
276276
277277 class Nil(Arrow):
278278 _immutable_ = True
279- def compileCAM(self, compiler): compiler.quote(endOfList)
279+ def compileCAM(self, compiler): compiler.quote(thePoint)
280280 def types(self, cs):
281281 return cs.concrete("1"), cs.functor("list", [cs.fresh()])
282282
@@ -297,40 +297,7 @@ class Fold(Arrow):
297297 def eq(self, other):
298298 return isinstance(other, Fold) and arrowEq(self._n, other._n) and arrowEq(self._c, other._c)
299299
300- def compileCAM(self, compiler):
301- # Folds in CAM/ZINC are always foldl, but Cammy is always foldr.
302- # So, we reverse the input list before folding.
303- # Conveniently, this can be done with foldl!
304- # self.compileBody(Ignore(), Cons(), compiler)
305- self.compileBody(self._n, self._c, compiler)
306-
307- def compileBody(self, nil, cons, compiler):
308- # Stash the entire list onto the side stack.
309- compiler.startList()
310- compiler.quote(thePoint)
311- nil.compileCAM(compiler)
312- # At the top of the loop, the accumulator is in the register and the
313- # rest of the list is in the side stack.
314- loop = compiler.here()
315- compiler.push()
316- compiler.iter()
317- compiler.push()
318- # This test is backwards, so we swap before jumping.
319- compiler.isEndOfList()
320- compiler.sumSwap()
321- compiler.gotoRight()
322- isNil = compiler.jumpForward()
323- compiler.pop()
324- compiler.cons()
325- compiler.pairSwap()
326- cons.compileCAM(compiler)
327- compiler.goto()
328- compiler.jumpBackwardTo(loop)
329- compiler.jumpHere(isNil)
330- # There are two points on top of the accumulator. Pop the point from
331- # the isNil check, and then pop endOfList.
332- compiler.pop()
333- compiler.pop()
300+ def compileCAM(self, compiler): compiler.fold(self._n, self._c)
334301
335302 def types(self, cs):
336303 ndom, ncod = self._n.types(cs)
@@ -341,6 +308,40 @@ class Fold(Arrow):
341308 cs.unify(ncod, ccod)
342309 return cs.functor("list", [x]), ccod
343310
311+class TNil(Arrow):
312+ _immutable_ = True
313+ def compileCAM(self, compiler): compiler.quote(thePoint)
314+ def types(self, cs):
315+ return cs.concrete("1"), cs.functor("tree", [cs.fresh()])
316+
317+class TCons(Arrow):
318+ _immutable_ = True
319+ def compileCAM(self, compiler): pass
320+ def types(self, cs):
321+ x = cs.fresh()
322+ xs = cs.functor("tree", [x])
323+ return cs.functor("pair", [x, cs.functor("pair", [xs, xs])]), xs
324+
325+class TFold(Arrow):
326+ _immutable_ = True
327+ def __init__(self, n, c):
328+ self._n = n
329+ self._c = c
330+
331+ def eq(self, other):
332+ return isinstance(other, TFold) and arrowEq(self._n, other._n) and arrowEq(self._c, other._c)
333+
334+ def compileCAM(self, compiler): compiler.tfold(self._n, self._c)
335+
336+ def types(self, cs):
337+ ndom, ncod = self._n.types(cs)
338+ cdom, ccod = self._c.types(cs)
339+ cs.unify(ndom, cs.concrete("1"))
340+ x = cs.fresh()
341+ cs.unify(cdom, cs.functor("pair", [x, cs.functor("pair", [ccod, ccod])]))
342+ cs.unify(ncod, ccod)
343+ return cs.functor("tree", [x]), ccod
344+
344345 def makeConstant(x, ty):
345346 class Constant(Arrow):
346347 _immutable_ = True
@@ -455,6 +456,8 @@ def buildCompound(name, args):
455456 return PrimRec(args[0], args[1])
456457 elif name == "fold" and len(args) == 2:
457458 return Fold(args[0], args[1])
459+ elif name == "tfold" and len(args) == 2:
460+ return TFold(args[0], args[1])
458461 else:
459462 raise BuildProblem("Invalid compound functor: " + name)
460463
@@ -470,10 +473,3 @@ class Given(Arrow):
470473 def compileCAM(self, compiler):
471474 raise BuildProblem("given arrows (holes) cannot be compiled")
472475 def types(self, cs): return cs.givens(self.index)
473-
474-
475-def indexOfArrow(alist, arr1):
476- "Look up an arrow in an association list. Return -1 if not present."
477- for i, (arr2, _) in enumerate(alist):
478- if arrowEq(arr1, arr2): return i
479- return -1
--- a/sampler/cammylib/cam.py
+++ b/sampler/cammylib/cam.py
@@ -3,20 +3,25 @@ import math
33 from rpython.rlib.jit import JitDriver, isconstant, we_are_jitted
44 from rpython.rlib.rvmprof import get_unique_id, register_code, register_code_object_class, vmprof_execute_code
55
6-from cammylib.arrows import indexOfArrow
7-from cammylib.elements import F, L, N, P, R, T, eltsEq, endOfList, theBool, thePoint, theTrue, theFalse
6+from cammylib.arrows import arrowEq
7+from cammylib.elements import F, L, N, P, R, T, Tr, eltsEq, theBool, thePoint, theTrue, theFalse
8+from cammylib.text import ljust
89
910 # A basic CAM, as in the original paper:
1011 # https://doi.org/10.1016/0167-6423(87)90020-7
1112
1213 # The original core opcodes.
13-(QUOTE, CUR, PUSH, POP, SWAP, CONS, APP, RET, GOTO, HALT,
14+(QUOTE, CUR, PUSH, POP, SWAP, CONS, APP, RET, GOTO, CALL, HALT,
1415 # Jets of core opcodes.
1516 SNOC,
1617 # Custom opcodes for our structures.
17-GOTORIGHT, STARTLIST, ITER,
18+GOTORIGHT,
1819 # Custom opcodes for our data.
19-ASSOC) = range(15)
20+ASSOC) = range(14)
21+ops = [
22+ "QUOTE", "CUR", "PUSH", "POP", "SWAP", "CONS", "APP", "RET", "GOTO",
23+ "CALL", "HALT", "SNOC", "GOTORIGHT", "ASSOC",
24+]
2025
2126 # To facilitate profiling, the term operations are factored out into a table.
2227
@@ -103,6 +108,7 @@ termOps = [
103108 # Core term ops.
104109 TermOp("fst", lambda term: term.first()),
105110 TermOp("snd", lambda term: term.second()),
111+ TermOp("trd", lambda term: term.third()),
106112 TermOp("branch", lambda term: L(thePoint) if term.b() else R(thePoint)),
107113 TermOp("dup", lambda term: P(term, term)),
108114 TermOp("pairSwap", lambda term: P(term.second(), term.first())),
@@ -119,9 +125,8 @@ termOps = [
119125 TermOp("nDouble", lambda term: N(term.n() << 1)),
120126 TermOp("nAdd", lambda term: N(term.first().n() + term.second().n())),
121127 TermOp("nMul", lambda term: N(term.first().n() * term.second().n())),
122- TermOp("uncons", lambda term: R(thePoint) if term is endOfList else L(term)),
123- TermOp("isEndOfList",
124- lambda term: L(thePoint) if term is endOfList else R(thePoint)),
128+ TermOp("uncons", lambda term: R(thePoint) if term is thePoint else L(term)),
129+ TermOp("isNil", lambda term: L(term) if term is thePoint else R(thePoint)),
125130 # Custom floating-point term ops.
126131 TermOp("sign", lambda term: theBool(sign(term.f()))),
127132 TermOp("floor", lambda term: floor(term.f())),
@@ -141,17 +146,16 @@ termOps = [
141146 print "CAM: Created %d term ops" % len(termOps)
142147
143148
144-ops = [
145- "QUOTE", "CUR", "PUSH", "POP", "SWAP", "CONS", "APP", "RET", "GOTO",
146- "HALT", "SNOC", "GOTORIGHT", "STARTLIST", "ITER", "ASSOC",
147-]
148149 def hasParam(op):
149- return op in (QUOTE, CUR, GOTO, GOTORIGHT)
150+ return op in (QUOTE, CUR, GOTO, CALL, GOTORIGHT)
150151 def decode(op):
151152 if isTermOp(op):
152153 return termOps[unmaskTermOp(op)].name
153154 else:
154155 return ops[op]
156+LABEL_WIDTH = 5
157+PC_WIDTH = 4
158+def getLabel(labels, l): return "l%d:" % labels[l] if l in labels else ""
155159 def disassemble(insts, consts):
156160 lines = []
157161 labels = {}
@@ -163,21 +167,21 @@ def disassemble(insts, consts):
163167 if op == QUOTE:
164168 const = insts[i]
165169 i += 1
166- s = "%s %d (%s)" % (decode(op), const,
167- consts[const].asStr())
168- elif op in (CUR, GOTO, GOTORIGHT):
170+ s = "%s %d (%s)" % (decode(op), const, consts[const].asStr())
171+ elif op in (CUR, GOTO, CALL, GOTORIGHT):
169172 label = insts[i]
170173 i += 1
171- labels[label] = "l%d:" % l
172- l += 1
173- s = "%s %d %s" % (decode(op), label, labels[label])
174+ if label not in labels:
175+ labels[label] = l
176+ l += 1
177+ s = "%s %d (%d)" % (decode(op), label, labels[label])
174178 else:
175179 s = decode(op).upper()
176- if isTermOp(op):
177- s += " (term op)"
180+ if isTermOp(op): s += " (term op)"
178181 lines.append((pc, s))
179- labeled = [(labels.get(lpc, " "), lpc, ls) for (lpc, ls) in lines]
180- return "".join(["%s %d: %s\n" % line for line in labeled])
182+ labeled = [(ljust(getLabel(labels, lpc), LABEL_WIDTH), ljust("%d:" % lpc, PC_WIDTH), ls)
183+ for (lpc, ls) in lines]
184+ return "".join(["%s %s %s\n" % line for line in labeled])
181185
182186
183187 class CAM(object):
@@ -216,9 +220,6 @@ def runTermOp(op, term):
216220 def runCAM(cam, term):
217221 pc = 0
218222 stack = thePoint
219- # My way of avoiding recursion when folding: Values are pushed to a
220- # secondary stack.
221- sideStack = []
222223
223224 while pc < len(cam.code):
224225 CAMDriver.jit_merge_point(pc=pc, cam=cam,
@@ -271,6 +272,11 @@ def runCAM(cam, term):
271272 pc = code[pc]
272273 CAMDriver.can_enter_jit(pc=pc, cam=cam,
273274 term=term, stack=stack)
275+ elif op == CALL:
276+ stack = P(N(pc + 1), stack)
277+ pc = code[pc]
278+ CAMDriver.can_enter_jit(pc=pc, cam=cam,
279+ term=term, stack=stack)
274280 elif op == HALT:
275281 return term
276282 elif op == GOTORIGHT:
@@ -279,13 +285,6 @@ def runCAM(cam, term):
279285 pc = pc + 1 if isLeft else address
280286 CAMDriver.can_enter_jit(pc=pc, cam=cam,
281287 term=term, stack=stack)
282- elif op == STARTLIST:
283- sideStack.append(endOfList)
284- while term is not endOfList:
285- sideStack.append(term.first())
286- term = term.second()
287- elif op == ITER:
288- term = sideStack.pop()
289288 elif op == ASSOC:
290289 pair = stack.first()
291290 term = P(pair.first(), term)
@@ -301,6 +300,98 @@ def runCAM(cam, term):
301300 return term
302301
303302
303+class PendingArrow(object): pass
304+
305+class PendingCurry(PendingArrow):
306+ _immutable_ = True
307+ def __init__(self, cur): self._cur = cur
308+ def eq(self, other):
309+ return isinstance(other, PendingCurry) and arrowEq(self._cur, other._cur)
310+ def makeSubroutine(self, jump, compiler):
311+ compiler.jumpHere(jump)
312+ self._cur.compileCAM(compiler)
313+ compiler.ret()
314+
315+class PendingFold(PendingArrow):
316+ _immutable_ = True
317+ def __init__(self, nil, cons):
318+ self._nil = nil
319+ self._cons = cons
320+ def eq(self, other):
321+ return isinstance(other, PendingFold) and arrowEq(self._nil, other._nil) and arrowEq(self._cons, other._cons)
322+ def makeSubroutine(self, jump, compiler):
323+ compiler.jumpHere(jump)
324+ here = compiler.here()
325+ # Are we at the end of the list?
326+ compiler.push()
327+ compiler.isNil()
328+ compiler.gotoRight()
329+ isCons = compiler.jumpForward()
330+ # We are at the end of the list.
331+ compiler.pop()
332+ self._nil.compileCAM(compiler)
333+ compiler.ret()
334+ # We have a cons.
335+ compiler.jumpHere(isCons)
336+ compiler.pop()
337+ compiler.push()
338+ compiler.snd()
339+ compiler.call()
340+ # Recurse.
341+ compiler.jumpBackwardTo(here)
342+ # Reduce.
343+ compiler.swap()
344+ compiler.fst()
345+ compiler.snoc()
346+ self._cons.compileCAM(compiler)
347+ compiler.ret()
348+
349+class PendingTFold(PendingArrow):
350+ _immutable_ = True
351+ def __init__(self, tnil, tcons):
352+ self._tnil = tnil
353+ self._tcons = tcons
354+ def eq(self, other):
355+ return isinstance(other, PendingTFold) and arrowEq(self._tnil, other._tnil) and arrowEq(self._tcons, other._tcons)
356+ def makeSubroutine(self, jump, compiler):
357+ compiler.jumpHere(jump)
358+ here = compiler.here()
359+ # Are we at a leaf?
360+ compiler.push()
361+ compiler.isNil()
362+ compiler.gotoRight()
363+ isBranch = compiler.jumpForward()
364+ # We are at a leaf.
365+ compiler.pop()
366+ self._tnil.compileCAM(compiler)
367+ compiler.ret()
368+ # We have a branch.
369+ compiler.jumpHere(isBranch)
370+ compiler.pop()
371+ compiler.push()
372+ compiler.push()
373+ # Recurse.
374+ compiler.snd()
375+ compiler.call()
376+ compiler.jumpBackwardTo(here)
377+ compiler.swap()
378+ compiler.trd()
379+ compiler.call()
380+ compiler.jumpBackwardTo(here)
381+ compiler.cons()
382+ compiler.swap()
383+ compiler.fst()
384+ # Reduce.
385+ compiler.snoc()
386+ self._tcons.compileCAM(compiler)
387+ compiler.ret()
388+
389+def pendingIndex(alist, arr1):
390+ "Look up an arrow in an association list. Return -1 if not present."
391+ for i, (arr2, _) in enumerate(alist):
392+ if arr1.eq(arr2): return i
393+ return -1
394+
304395 class Compiler(object):
305396 """
306397 Compile an arrow to CAM bytecode.
@@ -321,7 +412,7 @@ class Compiler(object):
321412 # a list for the indices instead of sparse storage.
322413 self.jumpLabels = []
323414 # Queue of curried arrows to compile.
324- self.curryQueue = []
415+ self.pendingArrows = []
325416 # List of arrows which have already been compiled into subroutines.
326417 self.compiledArrows = []
327418
@@ -386,18 +477,22 @@ class Compiler(object):
386477 def jumpHere(self, jump):
387478 self.insts[jump] = self.barrier = len(self.insts)
388479
389- def curry(self, arrow):
390- self.insts.append(CUR)
391- self.lastOp = CUR
480+ def postpone(self, inst, pendingArrow):
481+ self.insts.append(inst)
482+ self.lastOp = inst
392483 jump = self.jumpForward()
393- self.curryQueue.append((jump, arrow))
484+ self.pendingArrows.append((jump, pendingArrow))
485+
486+ def curry(self, arrow): self.postpone(CUR, PendingCurry(arrow))
487+ def fold(self, nil, cons): self.postpone(CALL, PendingFold(nil, cons))
488+ def tfold(self, tnil, tcons): self.postpone(CALL, PendingTFold(tnil, tcons))
394489
395490 def compileArrow(self, topArrow):
396491 topArrow.compileCAM(self)
397492 self.halt()
398- while self.curryQueue:
399- jump, arrow = self.curryQueue.pop()
400- index = indexOfArrow(self.compiledArrows, arrow)
493+ while self.pendingArrows:
494+ jump, pending = self.pendingArrows.pop()
495+ index = pendingIndex(self.compiledArrows, pending)
401496 if index >= 0:
402497 # Use that arrow instead of this one.
403498 _, there = self.compiledArrows[index]
@@ -405,11 +500,9 @@ class Compiler(object):
405500 else:
406501 here = len(self.insts)
407502 # Save the address of the subroutine for later.
408- self.compiledArrows.append((arrow, here))
503+ self.compiledArrows.append((pending, here))
409504 # Patch the original jump, then compile the arrow once.
410- self.jumpHere(jump)
411- arrow.compileCAM(self)
412- self.ret()
505+ pending.makeSubroutine(jump, self)
413506
414507 def makeMachine(self):
415508 rv = CAM(self.insts[:], self.constants[:])
@@ -433,10 +526,9 @@ class Compiler(object):
433526 def app(self): self.emit(APP)
434527 def ret(self): self.emit(RET)
435528 def goto(self): self.emit(GOTO)
529+ def call(self): self.emit(CALL)
436530 def halt(self): self.emit(HALT)
437531 def gotoRight(self): self.emit(GOTORIGHT)
438- def startList(self): self.emit(STARTLIST)
439- def iter(self): self.emit(ITER)
440532 def assoc(self): self.emit(ASSOC)
441533
442534 for i, op in enumerate(termOps):
--- a/sampler/cammylib/elements.py
+++ b/sampler/cammylib/elements.py
@@ -26,6 +26,9 @@ class Element(object):
2626 def second(self):
2727 raise TypeFail("not a pair")
2828
29+ def third(self):
30+ raise TypeFail("not a triple")
31+
2932 def tagged(self, f, g):
3033 raise TypeFail("not tag")
3134
@@ -39,7 +42,6 @@ class T(Element):
3942 _immutable_ = True
4043 def asStr(self): return "*"
4144 thePoint = T()
42-endOfList = T()
4345
4446 class B(Element):
4547 _immutable_ = True
@@ -84,6 +86,20 @@ class P(Element):
8486
8587 def asStr(self): return "(%s, %s)" % (self._x.asStr(), self._y.asStr())
8688
89+class Tr(Element):
90+ _immutable_ = True
91+
92+ def __init__(self, x, y, z):
93+ self._x = x
94+ self._y = y
95+ self._z = z
96+
97+ def first(self): return self._x
98+ def second(self): return self._y
99+ def third(self): return self._z
100+
101+ def asStr(self): return "(%s, %s, %s)" % (self._x.asStr(), self._y.asStr(), self._z.asStr())
102+
87103 class L(Element):
88104 _immutable_ = True
89105
--- /dev/null
+++ b/sampler/cammylib/text.py
@@ -0,0 +1,7 @@
1+def ljust(s, w):
2+ l = len(s)
3+ return s if l >= w else " " * (w - l) + s
4+
5+def rjust(s, w):
6+ l = len(s)
7+ return s if l >= w else s + " " * (w - l)
--- a/sampler/main.py
+++ b/sampler/main.py
@@ -2,16 +2,13 @@ import os
22 import sys
33
44 from cammylib.hax import patch_ctypes_for_ffi
5+from cammylib.text import rjust
56
67 # Side-effecting imports for actions.
78 import animate, disassemble, draw, repl
89 # And now we can import and use the actions.
910 from actions import actions
1011
11-def rjust(s, w):
12- l = len(s)
13- return s if l >= w else s + " " * (w - l)
14-
1512 def help(exe, problem):
1613 # XXX stderr?
1714 print "%s: %s" % (exe, problem)