• R/O
  • HTTP
  • SSH
  • HTTPS

提交

标签
No Tags

Frequently used words (click to add to your profile)

javac++androidlinuxc#windowsobjective-cqtcocoa誰得pythonphprubygameguibathyscaphec翻訳計画中(planning stage)omegatframeworktwittertestdomvb.netdirectxbtronarduinopreviewerゲームエンジン

A categorical programming language


Commit MetaInfo

修订版c08887f024dd593812d696ff75f00c93ba919992 (tree)
时间2022-02-26 13:48:39
作者Corbin <cds@corb...>
CommiterCorbin

Log Message

Implement a not-yet-translated typechecker.

更改概述

差异

--- a/cammy-rpy/cammylib/arrows.py
+++ b/cammy-rpy/cammylib/arrows.py
@@ -113,9 +113,15 @@ class Xs(Element):
113113 class Arrow(object):
114114 _immutable_ = True
115115
116+ def boundVars(self):
117+ return self.domain.boundVars() | self.codomain.boundVars()
118+
116119 class Id(Arrow):
117120 _immutable_ = True
118121 def run(self, x): return x
122+ def types(self, cs):
123+ rv = cs.fresh()
124+ return rv, rv
119125
120126 class Comp(Arrow):
121127 _immutable_ = True
@@ -123,71 +129,138 @@ class Comp(Arrow):
123129 self.f = f
124130 self.g = g
125131 def run(self, x): return self.g.run(self.f.run(x))
132+ def types(self, cs):
133+ fdom, fcod = self.f.types(cs)
134+ gdom, gcod = self.g.types(cs)
135+ cs.unify(fcod, gdom)
136+ return fdom, gcod
126137
127138 class Ignore(Arrow):
128139 _immutable_ = True
129140 def run(self, x): return T()
141+ def types(self, cs): return cs.fresh(), cs.concrete("1")
130142
131143 class First(Arrow):
132144 _immutable_ = True
133145 def run(self, x): return x.first()
146+ def types(self, cs):
147+ left = cs.fresh()
148+ pair = cs.functor("pair", [left, cs.fresh()])
149+ return pair, left
134150
135151 class Second(Arrow):
136152 _immutable_ = True
137153 def run(self, x): return x.second()
154+ def types(self, cs):
155+ right = cs.fresh()
156+ pair = cs.functor("pair", [cs.fresh(), right])
157+ return pair, right
138158
139159 class Pair(Arrow):
140160 _immutable_ = True
141161 def __init__(self, f, g):
142162 self.f = f
143163 self.g = g
144- def run(self, x):
145- return P(self.f.run(x), self.g.run(x))
164+ def run(self, x): return P(self.f.run(x), self.g.run(x))
165+ def types(self, cs):
166+ fdom, fcod = self.f.types(cs)
167+ gdom, gcod = self.g.types(cs)
168+ cs.unify(fdom, gdom)
169+ return fdom, cs.functor("pair", [fcod, gcod])
146170
147171 class Left(Arrow):
148172 _immutable_ = True
149173 def run(self, x): return L(x)
174+ def types(self, cs):
175+ rv = cs.fresh()
176+ return rv, cs.functor("sum", [rv, cs.fresh()])
150177
151178 class Right(Arrow):
152179 _immutable_ = True
153180 def run(self, x): return R(x)
181+ def types(self, cs):
182+ rv = cs.fresh()
183+ return rv, cs.functor("sum", [cs.fresh(), rv])
154184
155185 class Case(Arrow):
156186 _immutable_ = True
157187 def __init__(self, f, g):
158188 self.f = f
159189 self.g = g
160- def run(self, x):
161- return x.tagged(self.f, self.g)
190+ def run(self, x): return x.tagged(self.f, self.g)
191+ def types(self, cs):
192+ fdom, fcod = self.f.types(cs)
193+ gdom, gcod = self.g.types(cs)
194+ cs.unify(fcod, gcod)
195+ return fdom, cs.functor("sum", [fdom, gdom])
162196
163197 class Curry(Arrow):
164198 _immutable_ = True
165- def __init__(self, f):
166- self._f = f
167-
168- def run(self, x):
169- return H(self._f, x)
199+ def __init__(self, f): self._f = f
200+ def run(self, x): return H(self._f, x)
201+ def types(self, cs):
202+ fdom, fcod = self._f.types(cs)
203+ x = cs.fresh()
204+ y = cs.fresh()
205+ cs.unify(fdom, cs.functor("pair", [x, y]))
206+ return x, cs.functor("hom", [y, fcod])
170207
171208 class Uncurry(Arrow):
172209 _immutable_ = True
173- def __init__(self, f):
174- self._f = f
175-
176- def run(self, x):
177- return self._f.run(x.first()).apply(x.second())
210+ def __init__(self, f): self._f = f
211+ def run(self, x): return self._f.run(x.first()).apply(x.second())
212+ def types(self, cs):
213+ fdom, fcod = self._f.types(cs)
214+ x = cs.fresh()
215+ y = cs.fresh()
216+ cs.unify(fcod, cs.functor("hom", [x, y]))
217+ return cs.functor("pair", [fdom, x]), y
178218
179219 class Either(Arrow):
180220 _immutable_ = True
181- def run(self, x):
182- return L(T()) if x.b() else R(T())
221+ def run(self, x): return L(T()) if x.b() else R(T())
222+ def types(self, cs):
223+ one = cs.concrete("1")
224+ return cs.concrete("2"), cs.functor("sum", [one, one])
225+
226+class TrueArr(Arrow):
227+ _immutable_ = True
228+ def run(self, x): return B(True)
229+ def types(self, cs): return cs.concrete("1"), cs.concrete("2")
230+
231+class FalseArr(Arrow):
232+ _immutable_ = True
233+ def run(self, x): return B(False)
234+ def types(self, cs): return cs.concrete("1"), cs.concrete("2")
235+
236+class NotArr(Arrow):
237+ _immutable_ = True
238+ def run(self, x): return B(not x.b())
239+ def types(self, cs): return cs.concrete("2"), cs.concrete("2")
240+
241+class Conj(Arrow):
242+ _immutable_ = True
243+ def run(self, x): return B(x.first().b() and x.second().b())
244+ def types(self, cs):
245+ two = cs.concrete("2")
246+ return cs.functor("pair", [two, two]), two
247+
248+class Disj(Arrow):
249+ _immutable_ = True
250+ def run(self, x): return B(x.first().b() or x.second().b())
251+ def types(self, cs):
252+ two = cs.concrete("2")
253+ return cs.functor("pair", [two, two]), two
183254
184255 class Zero(Arrow):
185256 _immutable_ = True
186257 def run(self, x): return N(rbigint.fromint(0))
258+ def types(self, cs): return cs.concrete("1"), cs.concrete("N")
187259
188260 class Succ(Arrow):
189261 _immutable_ = True
190262 def run(self, x): return N(x.n().int_add(1))
263+ def types(self, cs): return cs.concrete("N"), cs.concrete("N")
191264
192265 pr_driver = JitDriver(name="pr",
193266 greens=["pr"], reds=["n", "rv"],
@@ -208,13 +281,27 @@ class PrimRec(Arrow):
208281 rv = self._f.run(rv)
209282 return rv
210283
284+ def types(self, cs):
285+ xdom, xcod = self._x.types(cs)
286+ fdom, fcod = self._f.types(cs)
287+ cs.unify(xdom, cs.concrete("1"))
288+ cs.unify(xcod, fcod)
289+ cs.unify(fdom, fcod)
290+ return cs.concrete("N"), fcod
291+
211292 class Nil(Arrow):
212293 _immutable_ = True
213294 def run(self, x): return Xs([])
295+ def types(self, cs):
296+ return cs.concrete("1"), cs.functor("list", [cs.fresh()])
214297
215298 class Cons(Arrow):
216299 _immutable_ = True
217300 def run(self, x): return Xs([x.first()] + x.second().l())
301+ def types(self, cs):
302+ x = cs.fresh()
303+ xs = cs.functor("list", [x])
304+ return cs.functor("pair", [x, xs]), xs
218305
219306 fold_driver = JitDriver(name="fold",
220307 greens=["fold"], reds=["element"],
@@ -234,23 +321,35 @@ class Fold(Arrow):
234321 for e in x.l():
235322 rv = driveFold(self._c, P(e, rv))
236323 return rv
324+ def types(self, cs):
325+ ndom, ncod = self._n.types(cs)
326+ cdom, ccod = self._c.types(cs)
327+ cs.unify(ndom, cs.concrete("1"))
328+ x = cs.fresh()
329+ cs.unify(cdom, cs.functor("pair", [ccod, x]))
330+ cs.unify(ncod, ccod)
331+ return cs.functor("list", [x]), ccod
237332
238333 class FZero(Arrow):
239334 _immutable_ = True
240335 def run(self, x): return F(0.0)
336+ def types(self, cs): return cs.concrete("1"), cs.concrete("F")
241337
242338 class FOne(Arrow):
243339 _immutable_ = True
244340 def run(self, x): return F(1.0)
341+ def types(self, cs): return cs.concrete("1"), cs.concrete("F")
245342
246343 class FPi(Arrow):
247344 _immutable_ = True
248345 def run(self, x): return F(math.pi)
346+ def types(self, cs): return cs.concrete("1"), cs.concrete("F")
249347
250348 def sign(f): return math.copysign(1.0, f) > 0.0
251349 class FSign(Arrow):
252350 _immutable_ = True
253351 def run(self, x): return B(sign(x.f()))
352+ def types(self, cs): return cs.concrete("F"), cs.concrete("2")
254353
255354 class FFloor(Arrow):
256355 _immutable_ = True
@@ -259,10 +358,14 @@ class FFloor(Arrow):
259358 return L(F(float(math.floor(x.f()))))
260359 except (ValueError, OverflowError):
261360 return R(T())
361+ def types(self, cs):
362+ return (cs.concrete("F"),
363+ cs.functor("sum", [cs.concrete("F"), cs.concrete("1")]))
262364
263365 class FNegate(Arrow):
264366 _immutable_ = True
265367 def run(self, x): return F(-x.f())
368+ def types(self, cs): return cs.concrete("F"), cs.concrete("F")
266369
267370 INF = float("inf")
268371 class FRecip(Arrow):
@@ -274,6 +377,7 @@ class FRecip(Arrow):
274377 return F(math.copysign(INF, f))
275378 else:
276379 return F(1.0 / f)
380+ def types(self, cs): return cs.concrete("F"), cs.concrete("F")
277381
278382 class FLT(Arrow):
279383 _immutable_ = True
@@ -281,6 +385,9 @@ class FLT(Arrow):
281385 f1 = x.first().f()
282386 f2 = x.second().f()
283387 return B(True) if f1 == -0.0 and f2 == 0.0 else B(f1 < f2)
388+ def types(self, cs):
389+ f = cs.concrete("F")
390+ return cs.functor("pair", [f, f]), cs.concrete("2")
284391
285392 class FAdd(Arrow):
286393 _immutable_ = True
@@ -298,6 +405,9 @@ class FAdd(Arrow):
298405 if math.isnan(rv):
299406 rv = 0.0
300407 return F(rv)
408+ def types(self, cs):
409+ f = cs.concrete("F")
410+ return cs.functor("pair", [f, f]), f
301411
302412 MUL_SPECIALS = 0.0, -0.0, INF, -INF
303413 class FMul(Arrow):
@@ -316,24 +426,35 @@ class FMul(Arrow):
316426 if math.isnan(rv):
317427 rv = 0.0 * math.copysign(1.0, y) * math.copysign(1.0, z)
318428 return F(rv)
429+ def types(self, cs):
430+ f = cs.concrete("F")
431+ return cs.functor("pair", [f, f]), f
319432
320433 class FSqrt(Arrow):
321434 _immutable_ = True
322435 def run(self, x):
323436 f = x.f()
324437 return L(F(math.sqrt(f))) if sign(f) else R(T())
438+ def types(self, cs):
439+ f = cs.concrete("F")
440+ return f, cs.functor("sum", [f, cs.concrete("1")])
325441
326442 class FSin(Arrow):
327443 _immutable_ = True
328444 def run(self, x): return F(math.sin(x.f()))
445+ def types(self, cs): return cs.concrete("F"), cs.concrete("F")
329446
330447 class FCos(Arrow):
331448 _immutable_ = True
332449 def run(self, x): return F(math.cos(x.f()))
450+ def types(self, cs): return cs.concrete("F"), cs.concrete("F")
333451
334452 class FATan2(Arrow):
335453 _immutable_ = True
336454 def run(self, x): return F(math.atan2(x.first().f(), x.second().f()))
455+ def types(self, cs):
456+ f = cs.concrete("F")
457+ return cs.functor("pair", [f, f]), f
337458
338459
339460 class BuildProblem(Exception):
@@ -348,6 +469,11 @@ unaryFunctors = {
348469 "left": Left(),
349470 "right": Right(),
350471 "either": Either(),
472+ "t": TrueArr(),
473+ "f": FalseArr(),
474+ "not": NotArr(),
475+ "conj": Conj(),
476+ "disj": Disj(),
351477 "zero": Zero(),
352478 "succ": Succ(),
353479 "nil": Nil(),
--- /dev/null
+++ b/cammy-rpy/cammylib/types.py
@@ -0,0 +1,97 @@
1+from cammylib.sexp import Atom, Functor, Hole
2+
3+class UnificationFailed(Exception):
4+ def __init__(self, message):
5+ self.message = message
6+
7+class ConstraintStore(object):
8+ "A Kanren-style constraint store."
9+
10+ def __init__(self):
11+ self.i = 0
12+ self.constraints = []
13+
14+ def fresh(self):
15+ rv = self.i
16+ self.i += 1
17+ self.constraints.append(Hole(rv))
18+ return rv
19+
20+ def concrete(self, symbol):
21+ rv = self.i
22+ self.i += 1
23+ self.constraints.append(Atom(symbol))
24+ return rv
25+
26+ def functor(self, constructor, arguments):
27+ rv = self.i
28+ self.i += 1
29+ args = [Hole(arg) for arg in arguments]
30+ self.constraints.append(Functor(constructor, args))
31+ return rv
32+
33+ def walkArg(self, var):
34+ if isinstance(var, Atom):
35+ return var
36+ elif isinstance(var, Functor):
37+ return Functor(var.constructor,
38+ [self.walkArg(arg) for arg in var.arguments])
39+ elif isinstance(var, Hole):
40+ return self.walk(var.index)
41+ assert False, "impossible"
42+
43+ def walk(self, i):
44+ var = self.constraints[i]
45+ if isinstance(var, Hole) and var.index == i:
46+ return var
47+ else:
48+ return self.walkArg(var)
49+
50+ def unify(self, i, j):
51+ return self.unifyArg(self.walk(i), self.walk(j))
52+
53+ def unifyArg(self, vi, vj):
54+ print "unifying", vi.asStr(), vj.asStr()
55+ if isinstance(vi, Hole):
56+ self.constraints[vi.index] = vj
57+ elif isinstance(vj, Hole):
58+ self.constraints[vj.index] = vi
59+ elif isinstance(vi, Atom) and isinstance(vj, Atom):
60+ if vi.symbol != vj.symbol:
61+ raise UnificationFailed(
62+ "Can't unify constant types: %s vs. %s" %
63+ (vi.symbol, vj.symbol))
64+ elif isinstance(vi, Functor) and isinstance(vj, Functor):
65+ if vi.constructor != vj.constructor:
66+ raise UnificationFailed(
67+ "Can't unify compound types: %s vs. %s" %
68+ (vi.constructor, vj.constructor))
69+ if len(vi.arguments) != len(vj.arguments):
70+ raise UnificationFailed("Compound types have different arity?")
71+ for i, argi in enumerate(vi.arguments):
72+ self.unifyArg(argi, vj.arguments[i])
73+ else:
74+ raise UnificationFailed("Quite different types: %s. vs %s" %
75+ (vi.asStr(), vj.asStr()))
76+
77+def formatType(sexp):
78+ if isinstance(sexp, Hole):
79+ return "_%d" % sexp.index
80+ elif isinstance(sexp, Atom):
81+ return sexp.symbol
82+ elif isinstance(sexp, Functor):
83+ if sexp.constructor == "hom":
84+ return "[%s, %s]" % (formatType(sexp.arguments[0]),
85+ formatType(sexp.arguments[1]))
86+ elif sexp.constructor == "pair":
87+ return "(%s x %s)" % (formatType(sexp.arguments[0]),
88+ formatType(sexp.arguments[1]))
89+ elif sexp.constructor == "sum":
90+ return "(%s + %s)" % (formatType(sexp.arguments[0]),
91+ formatType(sexp.arguments[1]))
92+ elif sexp.constructor == "list":
93+ return "[%s]" % formatType(sexp.arguments[0])
94+ else:
95+ assert False, "whoops"
96+ else:
97+ assert False, "not whoops"
--- a/cammy-rpy/repl.py
+++ b/cammy-rpy/repl.py
@@ -1,13 +1,22 @@
11 # Inspired by https://www.pypy.org/posts/2018/11/guest-post-implementing-calculator-repl-6271483514675006846.html
22
3+import os
4+import sys
5+
36 from rpython.rlib.rfile import create_stdio
47
58 from cammylib.arrows import buildArrow, BuildProblem
69 from cammylib.hive import Hive, MissingAtom
710 from cammylib.parser import parse
11+from cammylib.types import ConstraintStore, formatType, UnificationFailed
812
913 LINE_BUFFER_LENGTH = 1024
1014
15+def command(code, line):
16+ if code == "e":
17+ # Edit a file
18+ os.system("$EDITOR")
19+
1120 def repl(hive, stdin, stdout):
1221 while True:
1322 stdout.write("> ")
@@ -15,6 +24,10 @@ def repl(hive, stdin, stdout):
1524 if not line:
1625 # Empty read means EOF.
1726 break
27+ if line.startswith(":"):
28+ if len(line) < 2:
29+ print "Not a full command"
30+ command(line[1], line[3:])
1831 sexp, trail = parse(line)
1932 print "Got:", line
2033 print "S-expression:", sexp.asStr()
@@ -27,8 +40,13 @@ def repl(hive, stdin, stdout):
2740 try:
2841 arrow = buildArrow(sexp)
2942 print "Arrow:", arrow
43+ cs = ConstraintStore()
44+ domain, codomain = arrow.types(cs)
45+ print "Type:", formatType(cs.walk(domain)), "->", formatType(cs.walk(codomain))
3046 except BuildProblem as bp:
3147 print "Couldn't build arrow:", bp.message
48+ except UnificationFailed as uf:
49+ print "Couldn't check type:", uf.message
3250 return 0
3351
3452 def main(argv):
@@ -40,3 +58,6 @@ def main(argv):
4058 def target(driver, *args):
4159 driver.exe_name = "cammy-repl"
4260 return main, None
61+
62+if __name__ == "__main__":
63+ main(sys.argv)
--- a/hive/fractal-membership.cammy
+++ b/hive/fractal-membership.cammy
@@ -4,3 +4,8 @@
44 (list/filter (f/ltpair v2/norm (fun/const f/2)))
55 (comp list/len
66 (f/divpair nat/to-f (fun/const (comp @1 nat/to-f))))))
7+
8+Measure the degree to which a fractal diverges. Given a maximum number of
9+steps, we iterate the IFS for a fractal in the complex plane until its
10+absolute value exceeds 2, and return a value in [0,1] indicating how many
11+steps were taken before divergence.
--- a/hive/graph-fun.cammy
+++ b/hive/graph-fun.cammy
@@ -1 +1,5 @@
11 (comp @0 (v3/triple id id (fun/const f-one)))
2+
3+Graph a real function on the plane. When interpreted as a red/green/blue
4+triple, the codomain varies from blue to white as the value of the function
5+varies from zero to one.
--- a/hive/h2rgb.cammy
+++ b/hive/h2rgb.cammy
@@ -12,3 +12,5 @@
1212 (fun/const f/3))
1313 f/abs)
1414 (fun/const f-one))))
15+
16+Convert a hue to its red, green, and blue components.
--- a/hive/hv2rgb.cammy
+++ b/hive/hv2rgb.cammy
@@ -1,3 +1,5 @@
11 (comp
22 (pair (comp fst h2rgb) (v3/broadcast snd))
33 (v3/map2 f-mul))
4+
5+Convert a hue/value pair to a red/green/blue triple.
--- a/hive/iter-fractal.cammy
+++ b/hive/iter-fractal.cammy
@@ -3,3 +3,6 @@
33 (fun/const (comp @1 nonempty/unfold))
44 (pair (comp (fun/const f-zero) fun/dup) @0))
55 snd)
6+
7+Iterate an [IFS](https://en.wikipedia.org/wiki/Iterated_function_system) for a
8+given number of steps.
--- a/todo.txt
+++ b/todo.txt
@@ -13,6 +13,12 @@
1313 * cammy-draw ...: take an expression and canvas params, make a PNG
1414 * cammy-frame $HIVE: take an expression on stdin, return framed expression
1515 on stdout
16+* REPL improvements
17+ * allow mid-functor newlines
18+ * jellification
19+ * : commands
20+ * help, describe commands
21+ * edit an atom's trail
1622 * Other entrypoints
1723 * Split and cleanup movelist
1824 * cammy-typecheck: take an expression on stdin, print its type