Repository navigation
Expand file tree
/
Copy pathprolog_compile.lua
More file actions
1407 lines (1318 loc) · 52.9 KB
/
Copy pathprolog_compile.lua
File metadata and controls
1407 lines (1318 loc) · 52.9 KB
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
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
-- prolog_compile.lua — retargets the kernel's Prolog clause compiler onto the
-- soa32 substrate (prolog_engine.lua).
--
-- STRATEGY: we do NOT re-implement shen.compile-head/compile-body. The legacy
-- `shen.compile-prolog` (klambda/prolog.kl:27) runs unchanged and produces a
-- KL `(define Name P1..Pk B L K C -> Body)` form whose Body is built from a
-- small CLOSED vocabulary (let/if/=/cons?/hd/tl/freeze/thaw/do + the engine
-- prims lazyderef/deref/pvar?/bind!/newpv/gc/unlocked?/cut/unlock/incinfs +
-- goal calls + the builtins when/is/is!/bind/var?/return/fork/findall/call).
-- We TRANSLATE that form into direct-coded Lua against the substrate ABI:
--
-- NativePred[name] = function(a1..ak, n, cont) -> result-or-false
--
-- so clause order, +m/-m modes, stpart var allocation, and the cut-counter
-- structure are inherited from the battle-tested kernel compiler instead of
-- re-derived. Continuations are DEFUNCTIONALIZED: every (freeze E) in a
-- goal-continuation position becomes a statically-lifted chunk-local Lua
-- function + an integer handle (E.newcontN) capturing free vars in the int32
-- capture buffer; let-bound freezes / GoTo lambda chains that are only
-- invoked locally are CLOSURE-CONVERTED to static functions called with their
-- free vars as extra arguments — zero allocation.
--
-- DUAL REGISTRATION: the F["shen.compile-prolog"] wrapper returns the legacy
-- define form unchanged (so the legacy curried-CPS predicate is registered
-- exactly as before) and ADDITIONALLY translates it natively. Native code is
-- only entered through native query paths (the prolog? routing below, and
-- the Phase-3 typecheck driver); anything the translator cannot handle just
-- leaves NativePred[name] unset and the legacy path serves it.
--
-- prolog? ROUTING: F["shen.call-prolog"] (the macro helper) is wrapped: when
-- every predicate named in the query body is native-compiled (and the body
-- avoids call/findall, which can dispatch closures we cannot), the query is
-- compiled AT MACRO TIME into a synthetic native predicate and the expansion
-- becomes a direct call to the native runner. Otherwise the original
-- expansion (legacy CPS) is returned. SHEN_PROLOG_NATIVE=off disables the
-- routing (translation still happens; it is inert).
local R = require("runtime")
local C = require("compiler")
-- 5.2+ compatibility shims (this module only runs under LuaJIT today — it is
-- loaded via prolog_engine.lua, which is FFI-gated — but keep it loadable).
local unpack = table.unpack or unpack
local loadstring = loadstring or load
-- A value in return position: `THAWN(x)` (a counted, non-tail thaw) as the
-- whole expression becomes `THAW(x)`, a proper tail call that neither grows
-- the stack nor counts toward a segment (prolog_engine.lua, #85).
local function tail_return(val)
if val:sub(1, 6) ~= "THAWN(" then return val end
local depth, i, n = 0, 6, #val
while i <= n do
local c = val:sub(i, i)
if c == '"' then
i = i + 1
while i <= n and val:sub(i, i) ~= '"' do
if val:sub(i, i) == "\\" then i = i + 1 end
i = i + 1
end
elseif c == "(" then depth = depth + 1
elseif c == ")" then
depth = depth - 1
if depth == 0 then
if i == n then return "THAW(" .. val:sub(7) end
return val
end
end
i = i + 1
end
return val
end
local M = {}
local E, P, F -- bound in install()
local NP -- E.NativePred
-- ---------------------------------------------------------------------------
-- KL list helpers
-- ---------------------------------------------------------------------------
local Cons, Symbol, NIL = R.Cons, R.Symbol, R.NIL
local getmt = getmetatable
local function is_cons(x) return getmt(x) == Cons end
local function is_sym(x) return getmt(x) == Symbol end
local function sname(x) return x.name end
local function lst2tbl(l)
local t, n = {}, 0
while is_cons(l) do n = n + 1; t[n] = l[1]; l = l[2] end
return t, n
end
local function is_klvar(x)
return is_sym(x) and x.name:match("^%u") ~= nil
end
local SYM = setmetatable({}, { __index = function(t, k)
local s = R.intern(k); rawset(t, k, s); return s
end })
-- ---------------------------------------------------------------------------
-- free-variable computation (first-occurrence order)
-- ---------------------------------------------------------------------------
local function fv_walk(e, bound, out, seen)
if is_klvar(e) then
local n = e.name
if not bound[n] and not seen[n] then
seen[n] = true; out[#out + 1] = n
end
elseif is_cons(e) then
local h = e[1]
if h == SYM["let"] and is_cons(e[2]) and is_cons(e[2][2]) then
-- single- or multi-binding let: (let V1 E1 [V2 E2 ...] Body)
local v, ex = e[2][1], e[2][2][1]
local rest = e[2][2][2]
local body
if rest[2] == NIL then
body = rest[1]
else
body = R.cons(SYM["let"], rest)
end
fv_walk(ex, bound, out, seen)
local saved = bound[v.name]
bound[v.name] = true
fv_walk(body, bound, out, seen)
bound[v.name] = saved
elseif h == SYM["lambda"] and is_cons(e[2]) and is_cons(e[2][2]) then
local v, body = e[2][1], e[2][2][1]
local saved = bound[v.name]
bound[v.name] = true
fv_walk(body, bound, out, seen)
bound[v.name] = saved
else
while is_cons(e) do
fv_walk(e[1], bound, out, seen)
e = e[2]
end
end
end
end
local function freevars(e)
local out = {}
fv_walk(e, {}, out, {})
return out
end
-- ---------------------------------------------------------------------------
-- the translator
-- ---------------------------------------------------------------------------
-- ctx = {
-- buf : chunk-level lines (lifted static fns / conts)
-- nlift : lifted-fn counter
-- nlocal : local counter
-- fail : error escape (translation refused)
-- }
-- env maps KL var name -> { lua = <local name>, kind = "term"|"count"|"cont"
-- |"result", or kind = "static" with .fn/.params/.fvs }
--
-- Emission is ANF-ish: compile_* appends statements to `out` and returns a
-- Lua expression string for the value.
local BUILTIN_GOALS = {
["when"] = true, ["is"] = true, ["is!"] = true, ["bind"] = true,
["var?"] = true, ["return"] = true, ["fork"] = true, ["findall"] = true,
["call"] = true,
}
-- A call to another predicate by name. Records the callee (the driver
-- closure in typecheck_native.lua follows these) and resolves through MISS so
-- a name with no native predicate raises E.native_miss rather than calling
-- nil.
local function np_ref(ctx, nm)
ctx.callees[nm] = true
local q = string.format("%q", nm)
return "(NP[" .. q .. "] or MISS(" .. q .. "))"
end
local function refuse(ctx, why)
ctx.failed = why
error(ctx.fail, 0)
end
-- ctx.fnloc counts the locals (params included) declared so far in the Lua
-- function being emitted, across all branches: an upper bound on what Lua
-- checks against its 200-locals-per-function cap.
local function newlocal(ctx, pfx)
ctx.nlocal = ctx.nlocal + 1
ctx.fnloc = ctx.fnloc + 1
return (pfx or "v") .. ctx.nlocal
end
-- On the split retry (see translate_core), past this many locals a let chain
-- continues in a lifted static. The margin covers locals a single let can
-- add after the check (if-chains, fork, guard imports).
local LET_SPLIT_LOCALS = 120
-- The wide retry (see translate_core) is for predicates that still pass a
-- Lua limit after splitting: a 40+ premise consume helper hands ~2N
-- captures to one constructor call (250 registers), its lifted functions
-- outgrow the chunk's locals, and one function can reference more than 60
-- of them as upvalues. In wide mode:
-- * a static with more than WIDE_CAPS parameters takes its free vars as
-- one table T (read as T[i]), and splitting never refuses;
-- * a continuation with more than WIDE_CAPS captures reads CAPREF(base, i)
-- at each use instead of copying every capture into a local;
-- * a handle with more than WIDE_NEWCONT captures is built by
-- NEWCONTT(fn, {...}): same capbuf layout, no wide argument list;
-- * lifted functions are fields of one chunk table LT;
-- * a cons chain longer than WIDE_CONS is built by CONSL({...}, tail).
local WIDE_SPLIT_LOCALS = 60
local WIDE_CAPS = 24
local WIDE_NEWCONT = 48
local WIDE_CONS = 16
local function indent(d) return string.rep(" ", d) end
-- A let extends env with a child table that __index-chains to its parent.
-- LuaJIT gives up on __index chains of 100 tables ("loop in gettable"), and
-- a wide sequent rule's consume helper nests that many lets. Every
-- ENV_FLATTEN levels the chain is collapsed into one table (inner bindings
-- win) whose __index is the chain's root lookup (nil, or a lift_static /
-- lift_cont penv function), so lookups see exactly the same bindings.
-- Parents are never written after a child is created, so the copy is safe.
local ENV_FLATTEN = 32
local function extend_env(env)
local mt = getmetatable(env)
local depth = (mt and mt.depth or 0) + 1
if depth < ENV_FLATTEN then
return setmetatable({}, { __index = env, depth = depth })
end
local flat, t, root = {}, env, nil
while t do
for k, v in pairs(t) do
if flat[k] == nil then flat[k] = v end
end
local tmt = getmetatable(t)
local idx = tmt and tmt.__index
if type(idx) == "table" then
t = idx
else
root = idx; t = nil
end
end
return setmetatable({}, { __index = setmetatable(flat, { __index = root, depth = 1 }), depth = 2 })
end
local compile_value -- fwd: control/result position
local compile_term -- fwd: term-construction position
local static_fvs -- fwd: free vars of a static about to be lifted
-- atom constant: interned at translate time, inlined as a number literal
local function atomconst(x)
return tostring(E.atom(x))
end
-- lift an embedded Shen expression (a when-test / is-RHS / computed goal arg)
-- into a KL defun called with materialized term arguments. Returns the Lua
-- call expression.
local guard_n = 0
-- A guard argument that names one engine term: (shen.deref X B) or a bare
-- term variable X (the driver may already have dereferenced X, as the 43.1
-- deref-hoisted by-hypothesis-h does). Returns its Lua local, else nil.
local function guard_term_ref(x, env)
if is_cons(x) and x[1] == SYM["shen.deref"] and is_cons(x[2]) then
x = x[2][1]
end
if is_klvar(x) then
local b = env[x.name]
if b and b.kind == "term" then return b.lua end
end
return nil
end
local function lift_guard(ctx, e, env, out, d)
-- (= T1 T2) over two engine terms: compare in the arena (E.eqterm) instead
-- of materializing both sides to Shen lists and calling `=`. This is the
-- by-hypothesis check, run once per hypothesis per goal; materializing it
-- was ~75% of a typecheck-heavy run.
if is_cons(e) and e[1] == SYM["="] and is_cons(e[2]) and is_cons(e[2][2])
and e[2][2][2] == NIL then
local a = guard_term_ref(e[2][1], env)
local b = a and guard_term_ref(e[2][2][1], env)
if b then return "EQTERM(" .. a .. ", " .. b .. ")" end
end
-- replace (shen.deref X B) / (shen.lazyderef X B) with fresh params
local params, args = {}, {}
local seen = {} -- engine var -> param (dedupe repeated references)
local function mkparam(luaname)
if seen[luaname] then return seen[luaname] end
local i = #params + 1
params[i] = R.intern("GP" .. i)
args[i] = luaname
seen[luaname] = params[i]
return params[i]
end
local function strip(x)
if is_cons(x) then
local h = x[1]
if (h == SYM["shen.deref"] or h == SYM["shen.lazyderef"])
and is_cons(x[2]) and is_klvar(x[2][1]) then
local vn = x[2][1].name
local b = env[vn]
if not b or b.kind ~= "term" then refuse(ctx, "guard derefs non-term " .. vn) end
return mkparam(b.lua)
end
return R.cons(strip(x[1]), strip(x[2]))
end
if is_klvar(x) then
-- bare engine-value variables (the t-star drivers pass raw terms to
-- helpers like subst) are materialized like deref'd ones; full deref
-- and materialize agree on everything a Shen helper can observe
local b = env[x.name]
if b then
if b.kind ~= "term" then refuse(ctx, "non-term var in guard: " .. x.name) end
return mkparam(b.lua)
end
end
return x
end
local stripped = strip(e)
guard_n = guard_n + 1
local gname = "shen.lua-guard-" .. guard_n
-- (defun gname (GP1..GPk) stripped)
local plist = NIL
for i = #params, 1, -1 do plist = R.cons(params[i], plist) end
P.eval(R.cons(SYM["defun"], R.cons(R.intern(gname),
R.cons(plist, R.cons(stripped, NIL)))))
local call = 'F[' .. string.format("%q", gname) .. ']('
for i = 1, #args do
call = call .. (i > 1 and ", " or "") .. "MAT(" .. args[i] .. ")"
end
return call .. ")"
end
-- A GOAL in term position — the argument of call/1, of findall/3, or any
-- predicate argument that is later handed to one of them.
--
-- The kernel spells a goal as a PARTIAL APPLICATION: prolog.shen's
-- shen.function-calls leaves an argument of the form (F A1..Ak) as a Shen
-- application, so evaluating it yields a closure still wanting the four
-- Bindings/Lock/Key/Continuation arguments, and (define call Call B L K C ->
-- (Call B L K C)) simply supplies them. The native engine instead spells a
-- goal as a STRUCTURE and dispatches on its head (E.g_call).
--
-- Guard-lifting (F A1..Ak) therefore produced a legacy CPS closure interned
-- as an opaque atom, and E.g_call rejected it with "goal is not a structure".
-- Build the structure the native engine expects instead.
--
-- Returns the Lua expression, or nil when `e` is not a goal (any other
-- embedded Shen computation still guard-lifts).
local function compile_goal_term(ctx, e, env, out, d)
local h = e[1]
if not is_sym(h) then return nil end
local r = M.registry[sname(h)]
if not r then return nil end
-- A prolog predicate's Shen arity is (term arity + 4). Only an application
-- that supplies exactly the term arguments — leaving B L K C outstanding —
-- denotes a goal; anything else is not what call/1 can complete.
local parts = lst2tbl(r.form)
local arrow
for i = 3, #parts do
if parts[i] == SYM["->"] then arrow = i; break end
end
if not arrow then return nil end
local nterms = (arrow - 3) - 4
local a, an = lst2tbl(e[2])
if an ~= nterms then return nil end
local acc = "0" -- NIL
for i = an, 1, -1 do
acc = "CONS(" .. compile_term(ctx, a[i], env, out, d) .. ", " .. acc .. ")"
end
return "CONS(" .. atomconst(h) .. ", " .. acc .. ")"
end
-- compile a term-construction expression
compile_term = function(ctx, e, env, out, d)
if is_cons(e) then
local h = e[1]
if h == SYM["cons"] and is_cons(e[2]) and is_cons(e[2][2]) then
if ctx.wide then
-- every pending CONS argument holds a register
local elems, t = {}, e
while is_cons(t) and t[1] == SYM["cons"] and is_cons(t[2]) and is_cons(t[2][2]) do
elems[#elems + 1] = t[2][1]
t = t[2][2][1]
end
if #elems > WIDE_CONS then
local parts = {}
for i, x in ipairs(elems) do parts[i] = compile_term(ctx, x, env, out, d) end
return "CONSL({" .. table.concat(parts, ", ") .. "}, "
.. compile_term(ctx, t, env, out, d) .. ")"
end
end
local a = compile_term(ctx, e[2][1], env, out, d)
local b = compile_term(ctx, e[2][2][1], env, out, d)
return "CONS(" .. a .. ", " .. b .. ")"
elseif h == SYM["shen.lazyderef"] and is_cons(e[2]) then
local a = compile_term(ctx, e[2][1], env, out, d)
return "LZD(" .. a .. ")"
elseif (h == SYM["hd"] or h == SYM["tl"]) and is_cons(e[2]) then
local a = compile_term(ctx, e[2][1], env, out, d)
return (h == SYM["hd"] and "CAR(" or "CDR(") .. a .. ")"
elseif h == SYM["shen.newpv"] then
return "NEWVAR()"
elseif h == SYM["shen.deref"] and is_cons(e[2]) then
-- a full deref in term position: identity in the native engine
return compile_term(ctx, e[2][1], env, out, d)
else
-- a goal (a partially applied prolog predicate) -> native goal structure
local g = compile_goal_term(ctx, e, env, out, d)
if g then return g end
-- embedded Shen computation producing a value -> guard-lift + import
local call = lift_guard(ctx, e, env, out, d)
local r = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. r .. " = IMP(" .. call .. ")"
return r
end
elseif is_klvar(e) then
local b = env[e.name]
if not b then refuse(ctx, "unbound var in term: " .. e.name) end
if b.kind ~= "term" then refuse(ctx, "non-term var in term position: " .. e.name) end
return b.lua
else
-- literal atom: symbol / number / string / boolean / ()
return atomconst(e)
end
end
-- compile a continuation argument: C-var (handle), let-bound freeze (already
-- a static), or an inline (freeze E) -> lifted cont + newcontN
local function compile_cont(ctx, e, env, out, d)
if is_klvar(e) then
local b = env[e.name]
if not b then refuse(ctx, "unbound cont var " .. e.name) end
if b.kind == "cont" or b.kind == "result" then return b.lua end
if b.kind == "static" then
-- a let-bound freeze passed onward as a continuation: wrap as handle
if #b.params > 0 then refuse(ctx, "parameterized GoTo used as cont") end
return ctx:mkhandle(b, out, d)
end
refuse(ctx, "bad cont var kind: " .. e.name)
elseif is_cons(e) and e[1] == SYM["freeze"] and is_cons(e[2]) then
local body = e[2][1]
return ctx:lift_cont(body, env, out, d)
else
refuse(ctx, "unsupported cont expression")
end
end
-- compile in control/value position
compile_value = function(ctx, e, env, out, d)
if e == true then return "true" end
if e == false then return "false" end
if is_klvar(e) then
local b = env[e.name]
if not b then refuse(ctx, "unbound var: " .. e.name) end
if b.kind == "static" then refuse(ctx, "static escapes as value") end
return b.lua
end
if not is_cons(e) then
if e == NIL then return atomconst(e) end
if type(e) == "number" then return tostring(e) end -- counter arithmetic
refuse(ctx, "literal in value position: " .. tostring(e))
end
local h = e[1]
local args = e[2]
-- (let V Expr Body) — including the kernel's multi-binding form
-- (let V1 E1 V2 E2 ... Body), which the Shen macro pipeline would desugar
if h == SYM["let"] and is_cons(args) and is_cons(args[2]) then
if ctx.split and ctx.fnloc >= (ctx.wide and WIDE_SPLIT_LOCALS or LET_SPLIT_LOCALS) then
-- a static this wide would split again on its first let (a wide
-- static takes them as one table)
local fvs, implicit = static_fvs({}, e, env)
if ctx.wide or #fvs < LET_SPLIT_LOCALS then
local st = ctx:lift_static(nil, {}, e, env, fvs, implicit)
return ctx:callstatic(st, {}, env, out, d)
end
end
local v, ex = args[1], args[2][1]
local rest = args[2][2]
local body
if rest[2] == NIL then
body = rest[1]
else
-- more bindings follow: re-wrap as a nested let
body = R.cons(SYM["let"], rest)
end
local nenv = extend_env(env)
if is_cons(ex) and (ex[1] == SYM["freeze"] or ex[1] == SYM["lambda"]) then
-- closure-convert: a let-bound freeze/lambda-chain becomes a static
-- chunk-level function with its free vars as trailing parameters
local params, inner = {}, ex
while is_cons(inner) and inner[1] == SYM["lambda"] do
params[#params + 1] = inner[2][1]
inner = inner[2][2][1]
end
if is_cons(inner) and inner[1] == SYM["freeze"] then
-- (freeze E) possibly under lambdas (shen.goto emits one or the other)
inner = inner[2][1]
end
local st = ctx:lift_static(v.name, params, inner, env)
nenv[v.name] = st
else
-- term-producing initializers compile in term mode; everything else
-- (goal calls, if-chains) is a result
local kind, ex_lua = "result", nil
if is_cons(ex) then
local eh = ex[1]
if eh == SYM["shen.lazyderef"] or eh == SYM["hd"] or eh == SYM["tl"]
or eh == SYM["shen.newpv"] or eh == SYM["cons"]
or eh == SYM["shen.deref"] then
kind = "term"
ex_lua = compile_term(ctx, ex, nenv, out, d)
end
elseif is_klvar(ex) then
local b = env[ex.name]
kind = b and b.kind or "result"
end
if not ex_lua then
ex_lua = compile_value(ctx, ex, nenv, out, d)
end
local lv = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. lv .. " = " .. ex_lua
nenv[v.name] = { lua = lv, kind = kind }
end
return compile_value(ctx, body, nenv, out, d)
end
-- (if T A B)
if h == SYM["if"] and is_cons(args) and is_cons(args[2]) then
local t, a, b = args[1], args[2][1], args[2][2][1]
local tl = compile_value(ctx, t, env, out, d)
local r = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. r
out[#out + 1] = indent(d) .. "if " .. tl .. " then"
local abuf = {}
local av = compile_value(ctx, a, env, abuf, d + 1)
for _, l in ipairs(abuf) do out[#out + 1] = l end
out[#out + 1] = indent(d + 1) .. r .. " = " .. av
out[#out + 1] = indent(d) .. "else"
local bbuf = {}
local bv = compile_value(ctx, b, env, bbuf, d + 1)
for _, l in ipairs(bbuf) do out[#out + 1] = l end
out[#out + 1] = indent(d + 1) .. r .. " = " .. bv
out[#out + 1] = indent(d) .. "end"
return r
end
-- (= A B)
if h == SYM["="] and is_cons(args) and is_cons(args[2]) then
local a, b = args[1], args[2][1]
-- a side is an engine term when it is a term variable, or a
-- (shen.lazyderef X B) of one (compiled to LZD): upstream ec16a9f's
-- by-hypothesis tests (= (shen.lazyderef Hyp B) ()) before descending
local function termkind(x)
if is_klvar(x) then return env[x.name] and env[x.name].kind end
if is_cons(x) and x[1] == SYM["shen.lazyderef"]
and is_cons(x[2]) and is_klvar(x[2][1]) then
local v = env[x[2][1].name]
return v and v.kind == "term" and "term" or nil
end
return nil
end
local akind, bkind = termkind(a), termkind(b)
if akind == "term" or bkind == "term" then
local al = compile_term(ctx, a, env, out, d)
local bl = compile_term(ctx, b, env, out, d)
return "(" .. al .. " == " .. bl .. ")"
else
local al = compile_value(ctx, a, env, out, d)
local bl = compile_value(ctx, b, env, out, d)
return "(" .. al .. " == " .. bl .. ")"
end
end
-- term tests / accessors in control positions
if h == SYM["cons?"] and is_cons(args) then
return "(" .. compile_term(ctx, args[1], env, out, d) .. " >= CONS_BASE)"
end
if h == SYM["shen.pvar?"] and is_cons(args) then
local a = compile_term(ctx, args[1], env, out, d)
return "(" .. a .. " >= VAR_BASE and " .. a .. " < CONS_BASE)"
end
if h == SYM["shen.unlocked?"] then return "LOCKOPEN()" end
-- (do (shen.incinfs) E)
if h == SYM["do"] and is_cons(args) and is_cons(args[2]) then
if is_cons(args[1]) and args[1][1] == SYM["shen.incinfs"] then
out[#out + 1] = indent(d) .. "INCINFS()"
else
compile_value(ctx, args[1], env, out, d)
end
return compile_value(ctx, args[2][1], env, out, d)
end
if h == SYM["shen.incinfs"] then
out[#out + 1] = indent(d) .. "INCINFS()"
return "true"
end
-- (thaw X)
if h == SYM["thaw"] and is_cons(args) then
local x = args[1]
if is_klvar(x) then
local b = env[x.name]
if b and b.kind == "static" then
if #b.params > 0 then refuse(ctx, "thaw of parameterized static") end
return ctx:callstatic(b, {}, env, out, d)
end
end
-- THAWN counts the frame toward the engine's stack segments (#85);
-- tail_return turns it back into a plain THAW in return position
return "THAWN(" .. compile_value(ctx, x, env, out, d) .. ")"
end
-- (shen.gc B E): LIFO-pop the var allocated by the paired shen.newpv when
-- E fails (stpart structure guarantees pairing)
if h == SYM["shen.gc"] and is_cons(args) and is_cons(args[2]) then
local el = compile_value(ctx, args[2][1], env, out, d)
local r = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. r .. " = " .. el
out[#out + 1] = indent(d) .. "if " .. r .. " == false then POPVAR() end"
return r
end
-- (shen.bind! X Y B Cont)
if h == SYM["shen.bind!"] and is_cons(args) then
local a = lst2tbl(args)
local x = compile_term(ctx, a[1], env, out, d)
local y = compile_term(ctx, a[2], env, out, d)
local k = compile_cont(ctx, a[4], env, out, d)
return "BIND1(" .. x .. ", " .. y .. ", " .. k .. ")"
end
-- (shen.cut B L K C)
if h == SYM["shen.cut"] and is_cons(args) then
local a = lst2tbl(args)
local n = compile_value(ctx, a[3], env, out, d)
local k = compile_cont(ctx, a[4], env, out, d)
return "CUT(" .. n .. ", " .. k .. ")"
end
-- (shen.unlock L K)
if h == SYM["shen.unlock"] and is_cons(args) then
local a = lst2tbl(args)
local n = compile_value(ctx, a[2], env, out, d)
return "UNLOCK(" .. n .. ")"
end
-- (+ K 1) — the hascut? counter bump
if h == SYM["+"] and is_cons(args) and is_cons(args[2]) then
local al = compile_value(ctx, args[1], env, out, d)
local bl = compile_value(ctx, args[2][1], env, out, d)
return "(" .. al .. " + " .. bl .. ")"
end
-- static invocation: (GoTo a1..ak)
if is_klvar(h) then
local b = env[h.name]
if b and b.kind == "static" then
local a, an = lst2tbl(args)
local call_args = {}
for i = 1, an do
call_args[i] = compile_term(ctx, a[i], env, out, d)
end
return ctx:callstatic(b, call_args, env, out, d)
end
refuse(ctx, "application of variable " .. h.name)
end
-- curried static application: ((F a) b) ... — the t-star drivers apply
-- multi-param GoTo lambdas one argument at a time
if is_cons(h) then
local arglists = { args }
local cur = h
while is_cons(cur) and is_cons(cur[1]) do
arglists[#arglists + 1] = cur[2]
cur = cur[1]
end
if is_cons(cur) and is_klvar(cur[1]) then
local b = env[cur[1].name]
if b and b.kind == "static" then
arglists[#arglists + 1] = cur[2]
local call_args = {}
for i = #arglists, 1, -1 do
local at = lst2tbl(arglists[i])
for j = 1, #at do
call_args[#call_args + 1] = compile_term(ctx, at[j], env, out, d)
end
end
if #call_args == #b.params then
return ctx:callstatic(b, call_args, env, out, d)
end
refuse(ctx, "curried static arity mismatch: " .. cur[1].name)
end
end
refuse(ctx, "application of non-static expression")
end
-- goal calls + builtins: (name args... B L K C)
if is_sym(h) then
local a, an = lst2tbl(args)
local nm = sname(h)
if BUILTIN_GOALS[nm] then
if nm == "when" then
-- (when Test B L K C): Test is an embedded Shen expression
local t = a[1]
local tl
if t == true then tl = "true"
elseif t == false then tl = "false"
elseif is_cons(t) and t[1] == SYM["shen.maxinfexceeded?"] then
tl = "MAXINF()" -- hot path: runs once per system-S call
elseif is_cons(t) then tl = lift_guard(ctx, t, env, out, d)
else refuse(ctx, "when test shape") end
local k = compile_cont(ctx, a[an], env, out, d)
local r = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. r .. " = false"
out[#out + 1] = indent(d) .. "if " .. tl .. " then " .. r .. " = THAWN(" .. k .. ") end"
return r
elseif nm == "is" or nm == "is!" or nm == "bind" then
local x = compile_term(ctx, a[1], env, out, d)
local y = compile_term(ctx, a[2], env, out, d)
local k = compile_cont(ctx, a[an], env, out, d)
local op = (nm == "is") and "UNIFY" or (nm == "is!") and "UNIFYOC" or "BIND1"
return op .. "(" .. x .. ", " .. y .. ", " .. k .. ")"
elseif nm == "var?" then
-- (var? X B L K C): E.g_var takes the uniform goal ABI
-- (term, count, cont), so the Key must be passed through — emitting
-- GVAR(x, k) put the continuation in the count parameter and left
-- cont nil, crashing thawH on every SUCCEEDING varhood test.
local x = compile_term(ctx, a[1], env, out, d)
local nk = compile_value(ctx, a[an - 1], env, out, d)
local k = compile_cont(ctx, a[an], env, out, d)
return "GVAR(" .. x .. ", " .. nk .. ", " .. k .. ")"
elseif nm == "return" then
local x = compile_term(ctx, a[1], env, out, d)
return "MAT(" .. x .. ")"
elseif nm == "fork" then
-- (fork (cons goal1 (cons goal2 ...)) B L K C): unroll statically.
-- each goali is a call form (name args...) without the BLKC suffix
local nk = compile_value(ctx, a[an - 1], env, out, d)
local k = compile_cont(ctx, a[an], env, out, d)
local kv = newlocal(ctx, "fk")
out[#out + 1] = indent(d) .. "local " .. kv .. " = " .. k
local r = newlocal(ctx)
out[#out + 1] = indent(d) .. "local " .. r .. " = false"
local lst = a[1]
local first = true
while is_cons(lst) and lst[1] == SYM["cons"] and is_cons(lst[2]) do
local g = lst[2][1]
lst = lst[2][2][1]
if not (is_cons(g) and is_sym(g[1])) then refuse(ctx, "fork goal shape") end
local guard = first and "" or ("if " .. r .. " == false then ")
local gb = {}
local gargs, gn = lst2tbl(g[2])
local parts = {}
for i = 1, gn do parts[i] = compile_term(ctx, gargs[i], env, gb, d + 1) end
for _, l in ipairs(gb) do out[#out + 1] = l end
local gname = sname(g[1])
if BUILTIN_GOALS[gname] then refuse(ctx, "builtin inside fork") end
out[#out + 1] = indent(d) .. guard .. r .. " = " ..
np_ref(ctx, gname) .. "(" ..
table.concat(parts, ", ") .. (gn > 0 and ", " or "") ..
nk .. ", " .. kv .. ")" .. (first and "" or " end")
first = false
end
return r
elseif nm == "findall" or nm == "call" then
local nk = compile_value(ctx, a[an - 1], env, out, d)
local k = compile_cont(ctx, a[an], env, out, d)
if nm == "call" then
local g = compile_term(ctx, a[1], env, out, d)
return "GCALL(" .. g .. ", " .. nk .. ", " .. k .. ")"
else
local t = compile_term(ctx, a[1], env, out, d)
local g = compile_term(ctx, a[2], env, out, d)
local rr = compile_term(ctx, a[3], env, out, d)
return "GFINDALL(" .. t .. ", " .. g .. ", " .. rr .. ", " ..
nk .. ", " .. k .. ")"
end
end
end
-- plain goal call: last 4 args are B L K C -> (terms..., n, cont)
if an < 4 then refuse(ctx, "goal call with <4 args: " .. nm) end
local parts = {}
for i = 1, an - 4 do
parts[#parts + 1] = compile_term(ctx, a[i], env, out, d)
end
local n = compile_value(ctx, a[an - 1], env, out, d)
local k = compile_cont(ctx, a[an], env, out, d)
parts[#parts + 1] = n
parts[#parts + 1] = k
return np_ref(ctx, nm) .. "(" .. table.concat(parts, ", ") .. ")"
end
refuse(ctx, "unsupported form")
end
-- ---------------------------------------------------------------------------
-- lifting machinery (methods on ctx)
-- ---------------------------------------------------------------------------
local CtxMT = {}
CtxMT.__index = CtxMT
-- Handle constructor for k captures. NEWCONT0..16 and the varargs NEWCONTV
-- share one layout (k contiguous capbuf slots at contBase[h]). Generated
-- fixed-width constructors past 16 win in isolation but measured ~25% slower
-- on einsteins-riddle, whose wide continuations take NEWCONTV.
local function newcont_ctor(k)
if k <= 16 then return "NEWCONT" .. k end
return "NEWCONTV"
end
-- the handle construction for continuation function `fname` over the Lua
-- expressions `caps`
local function newcont_call(ctx, fname, caps)
if ctx.wide and #caps > WIDE_NEWCONT then
return "NEWCONTT(" .. fname .. ", {" .. table.concat(caps, ", ") .. "})"
end
local parts = { fname }
for _, c in ipairs(caps) do parts[#parts + 1] = c end
return newcont_ctor(#caps) .. "(" .. table.concat(parts, ", ") .. ")"
end
local function liftname(ctx, pfx)
ctx.nlift = ctx.nlift + 1
local fname = pfx .. ctx.nlift
ctx.liftnames[#ctx.liftnames + 1] = fname
if ctx.wide then return "LT." .. fname end
return fname
end
-- closure-convert a let-bound freeze / lambda chain into a chunk-level fn.
-- A static referencing another static is fine (both are chunk-level fns):
-- the inner static's free vars are folded into THIS static's free vars so
-- they are in scope at the inner call sites.
static_fvs = function(params, body, env)
local bound = {}
for _, p in ipairs(params) do bound[p.name] = true end
local fvs, fvseen, implicit = {}, {}, {}
local function addfv(vn)
if bound[vn] or fvseen[vn] then return end
fvseen[vn] = true
local outer = env[vn]
if not outer then return end
if outer.kind == "static" then
for _, f in ipairs(outer.fvs) do addfv(f) end
elseif outer.kind == "vec" or outer.kind == "lock" then
-- engine-implicit, dropped at use sites
implicit[vn] = outer
else
fvs[#fvs + 1] = vn
end
end
for _, vn in ipairs(freevars(body)) do addfv(vn) end
return fvs, implicit
end
function CtxMT.lift_static(ctx, name, params, body, env, fvs, implicit)
if not fvs then fvs, implicit = static_fvs(params, body, env) end
local fname = liftname(ctx, "LF")
local st = { kind = "static", fn = fname, params = params, fvs = fvs,
body = body, env = env }
-- emit the lifted definition; statics resolve through to chunk scope.
-- The vec/lock params keep their kinds so a misuse refuses exactly as it
-- would have in the enclosing env.
local penv = setmetatable({}, { __index = function(_, k)
local b = env[k]
if b and b.kind == "static" then return b end
return nil
end })
for vn, b in pairs(implicit) do penv[vn] = b end
local sig = {}
for i, p in ipairs(params) do
sig[#sig + 1] = "p" .. i
penv[p.name] = { lua = "p" .. i, kind = "term" }
end
if ctx.wide and #params + #fvs > WIDE_CAPS then
st.wide = true
sig[#sig + 1] = "T"
for i, vn in ipairs(fvs) do
penv[vn] = { lua = "T[" .. i .. "]", kind = env[vn].kind }
end
else
for i, vn in ipairs(fvs) do
sig[#sig + 1] = "fv" .. i
penv[vn] = { lua = "fv" .. i, kind = env[vn].kind }
end
end
local fbuf = {}
local saved_loc = ctx.fnloc
ctx.fnloc = #sig
local fval = compile_value(ctx, body, penv, fbuf, 1)
ctx.fnloc = saved_loc
local def = { fname .. " = function(" .. table.concat(sig, ", ") .. ")" }
for _, l in ipairs(fbuf) do def[#def + 1] = l end
def[#def + 1] = " return " .. tail_return(fval)
def[#def + 1] = "end"
ctx.buf[#ctx.buf + 1] = table.concat(def, "\n")
return st
end
-- direct invocation of a static (thaw GoTo / (GoTo a b))
function CtxMT.callstatic(ctx, st, call_args, env, out, d)
local parts, fvp = {}, {}
for _, a in ipairs(call_args) do parts[#parts + 1] = a end
for _, vn in ipairs(st.fvs) do
local b = env[vn]
if not b then refuse(ctx, "static fv out of scope: " .. vn) end
fvp[#fvp + 1] = b.lua
end
if st.wide then
parts[#parts + 1] = "{" .. table.concat(fvp, ", ") .. "}"
else
for _, l in ipairs(fvp) do parts[#parts + 1] = l end
end
return st.fn .. "(" .. table.concat(parts, ", ") .. ")"
end
-- (freeze E) in continuation position -> lifted cont fn + newcontN handle.
-- All captures must be numbers (term/count/cont/result-kind locals).
function CtxMT.lift_cont(ctx, body, env, out, d)
local fname = liftname(ctx, "LK")
local fvs = {}
for _, vn in ipairs(freevars(body)) do
if env[vn] then fvs[#fvs + 1] = vn end
end
-- statics referenced from the cont body are chunk-level fns whose OWN free
-- vars must also be captured
local capture, statics, seen, implicit = {}, {}, {}, {}
local function addcap(vn)
if seen[vn] then return end
seen[vn] = true
local b = env[vn]
if b.kind == "static" then
statics[vn] = b
for _, f in ipairs(b.fvs) do addcap(f) end
elseif b.kind == "vec" or b.kind == "lock" then
-- the prolog vector / lock vector are engine-implicit: dropped at
-- every use site, so never captured
implicit[vn] = b
else
capture[#capture + 1] = vn
end
end
for _, vn in ipairs(fvs) do addcap(vn) end
local penv = setmetatable({}, { __index = function(_, k)
-- statics resolve through to chunk scope
local b = env[k]
if b and b.kind == "static" then return b end
return nil
end })
for vn, b in pairs(implicit) do penv[vn] = b end
local fbuf = {}
local decls = {}
local wide = ctx.wide and #capture > WIDE_CAPS
for i, vn in ipairs(capture) do
if wide then
penv[vn] = { lua = "CAPREF(base, " .. (i - 1) .. ")", kind = env[vn].kind }
else
local lv = "c" .. i
decls[#decls + 1] = "local " .. lv .. " = CAPREF(base, " .. (i - 1) .. ")"
penv[vn] = { lua = lv, kind = env[vn].kind }
end
end
local saved_loc = ctx.fnloc
ctx.fnloc = (wide and 0 or #capture) + 2
local fval = compile_value(ctx, body, penv, fbuf, 1)
ctx.fnloc = saved_loc
local def = { fname .. " = function(base, h)" }
for _, l in ipairs(decls) do def[#def + 1] = " " .. l end
for _, l in ipairs(fbuf) do def[#def + 1] = l end
def[#def + 1] = " return " .. tail_return(fval)
def[#def + 1] = "end"
ctx.buf[#ctx.buf + 1] = table.concat(def, "\n")
local caps = {}
for _, vn in ipairs(capture) do caps[#caps + 1] = env[vn].lua end
return newcont_call(ctx, fname, caps)
end
-- a zero-param static used as a continuation value: wrap into a handle
function CtxMT.mkhandle(ctx, st, out, d)
-- captures = the static's free vars (numbers). A consume helper for a
-- sequent premise closes over two locals per premise variable plus the
-- assumption and the engine temps (2*N+5), so six premises already need
-- 17. The width must not be capped: refusing leaves NativePred[name]
-- unset while the already-translated caller still calls it.
local fname = liftname(ctx, "LH")
local decls, caps = {}, {}
local args = {}
for i, vn in ipairs(st.fvs) do
if st.wide then
args[#args + 1] = "CAPREF(base, " .. (i - 1) .. ")"