Repository navigation
Expand file tree
/
Copy pathprims.lua
More file actions
3180 lines (3067 loc) · 129 KB
/
Copy pathprims.lua
File metadata and controls
3180 lines (3067 loc) · 129 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
-- prims.lua : build the runtime environment (function table F, apply/curry
-- machinery, KL primitives) and provide load/eval of KL forms.
local R = require("runtime")
local C = require("compiler")
local cons, is_cons, NIL = R.cons, R.is_cons, R.NIL
local Symbol, intern, is_symbol = R.Symbol, R.intern, R.is_symbol
local Excn, mkexcn = R.Excn, R.mkexcn
local rawset = rawset
local NEGZERO = -0.0
local Vmt = R.Vmt -- absvector metatable (pure-array layout; shared with runtime.lua)
-- counted non-tail calls (runtime.lua stack segments, #93), written inline
-- where a native calls back into Shen code (a shared trampoline would look
-- like recursion to the trace recorder)
local SD, SEGRUN, SEG_FRAMES = R.seg.SD, R.seg.run, R.seg.FRAMES
local pcall = R.seg.pcall -- restores the segment count on a caught error
local P = {}
local F = {} -- Shen/KL function table: name -> Lua function
local FA = setmetatable({}, {__mode="k"}) -- Lua function -> arity
local GLOBALS = {} -- KL global variable namespace: name -> value
P.F, P.FA, P.GLOBALS = F, FA, GLOBALS
-- Allocation-attribution instrumentation (Part 1, THROWAWAY). Module-scope so
-- both the compiled-KL allocation sites (ENV.BIND freeze-thunks, MKFUN lambda
-- closures) and the native prolog prims share one counter table. Flag-gated;
-- counters are integer increments into a pre-existing table (zero allocation,
-- never touch shen.*infs*). Revert before shipping any Part-2 lever.
local APROF = os.getenv("SHEN_ALLOC_PROFILE") ~= nil
local AP = { lzy_calls=0, lzyoc_calls=0, lzy_cont=0, lzyoc_cont=0,
deref_calls=0, deref_cons=0, occ_deref_calls=0, bind_calls=0,
newpv_total=0, newpv_poolmiss=0, mkbind=0, mkbind_slots=0, mkfun=0,
thaw_total=0 }
local AP_SLOTS = {} -- BIND-thunk slot-count histogram: nslots -> count created
local AP_THAW = {} -- per-thunk thaw count (strong keys, profiling only): thunk -> n
P.AP, P.AP_SLOTS, P.AP_THAW = AP, AP_SLOTS, AP_THAW
-- ---- errors / exceptions -------------------------------------------------
local function ERR(msg) error(mkexcn(msg), 0) end
-- Lua-error -> Shen-speak translation. Lua runtime errors that escape
-- compiled Shen code read like VM internals ("attempt to call field 'foo'
-- (a nil value)"). Translate the common shapes into Shen terms, preserving
-- the original text in parentheses so nothing is hidden. Applied by TOEXCN
-- (so trap-error handlers see the translated message) and by the REPL's
-- top-level error display (repl.lua). Handles both the LuaJIT/Lua-5.1
-- message order ("attempt to call field 'foo' (a nil value)") and the
-- Lua-5.4 order ("attempt to call a nil value (field 'foo')").
local ERR_OPS = {
{ "call", function(ty, name)
if ty == "nil" then
if name then return name .. " is undefined" end
return "attempt to call an undefined function"
end
return "attempt to call a " .. ty .. " value"
.. (name and (" ('" .. name .. "')") or "") .. " as a function"
end },
{ "index", function(ty, name)
if ty == "nil" and name then return name .. " is nil and cannot be indexed" end
return "attempt to index a " .. ty .. " value"
.. (name and (" ('" .. name .. "')") or "")
end },
{ "perform arithmetic on", function(ty, name)
return "arithmetic on a " .. ty .. " value"
.. (name and (" ('" .. name .. "')") or "") .. ": expected a number"
end },
{ "concatenate", function(ty, name)
return "string concatenation on a " .. ty .. " value"
.. (name and (" ('" .. name .. "')") or "") .. ": expected a string"
end },
{ "get length of", function(ty, name)
return "length of a " .. ty .. " value"
.. (name and (" ('" .. name .. "')") or "")
end },
}
local function translate_error(msg)
if type(msg) ~= "string" then return msg end
-- strip the "chunkname:line: " position prefix for matching only
local body = msg:match("^.-:%d+: (.*)") or msg
for _, e in ipairs(ERR_OPS) do
local op, fmt = e[1], e[2]
local prefix = "^attempt to " .. op .. " "
-- Lua 5.4 order: attempt to OP a TY value (KIND 'NAME')
local ty, name = body:match(prefix .. "a (%a+) value %(%a+ '([^']+)'%)")
if not ty then
-- Lua 5.1 / LuaJIT order: attempt to OP KIND 'NAME' (a TY value)
name, ty = body:match(prefix .. "%a+ '([^']+)' %(a (%a+) value%)")
end
if not ty then name = nil; ty = body:match(prefix .. "a (%a+) value") end
if ty then return fmt(ty, name) .. " (Lua: " .. msg .. ")" end
end
local t1, t2 = body:match("^attempt to compare (%a+) with (%a+)")
if t1 then
return "comparison between a " .. t1 .. " and a " .. t2
.. ": expected numbers (Lua: " .. msg .. ")"
end
local tt = body:match("^attempt to compare two (%a+) values")
if tt then
return "comparison between two " .. tt .. " values: expected numbers (Lua: " .. msg .. ")"
end
return msg
end
P.translate_error = translate_error
local function TOEXCN(e)
if getmetatable(e) == Excn then return e end
return mkexcn(translate_error(tostring(e)))
end
P.ERR = ERR
-- ---- apply / curry -------------------------------------------------------
local unpack = table.unpack or unpack
local function MKFUN(arity, fn) if APROF then AP.mkfun = AP.mkfun + 1 end; FA[fn] = arity; return fn end
-- Frozen-continuation thunks (from BIND / freeze) are represented as array
-- tables {fn, cap1, ..., capN} tagged with the Thunk metatable, NOT as Lua
-- closures. Reason: in LuaJIT every closed-over upvalue is a separate ~56-byte
-- GCupval box, so a freeze capturing 7 vars costs ~440 B as a closure but only
-- ~170 B as an 8-slot array table. Captures are never Lua nil (KL false/() are
-- non-nil values), so #t is a reliable length. thaw and APP's 0-arg path run a
-- thunk by calling t[1](t[2..#t]).
local Thunk = {}
local function runthunk(t)
if APROF then AP.thaw_total = AP.thaw_total + 1; AP_THAW[t] = (AP_THAW[t] or 0) + 1 end
return t[1](unpack(t, 2, #t))
end
P.Thunk = Thunk
local APP -- fwd
local MAX_PARTIAL1 = 12
local PARTIAL1 = {}
for ar = 2, MAX_PARTIAL1 do
local ps = {}
for i = 1, ar - 1 do ps[i] = "x" .. i end
local plist = table.concat(ps, ", ")
PARTIAL1[ar] = assert((loadstring or load)(
"return function(f, a) return function(" .. plist .. ") return f(a, " .. plist .. ") end end",
"=PARTIAL1"))()
end
local function PARTIAL(f, ar, have)
local need = ar - #have
local g
-- One argument at a time is what a curried chain does: a closure over it,
-- and no tables on the call. (A chain through a defun of arity n calls n-1
-- of these per use.)
if #have == 1 and ar <= MAX_PARTIAL1 then
return MKFUN(need, PARTIAL1[ar](f, have[1]))
end
g = function(...)
local extra = {...}
local all = {}
for i=1,#have do all[i] = have[i] end
local m = #have
for i=1,select("#", ...) do all[m+i] = extra[i] end
return f(unpack(all, 1, ar))
end
return MKFUN(need, g)
end
-- A compiled one-parameter lambda carries no FA entry (see the lambda case of
-- cexpr in compiler.lua): recording it was a new key in a weak table for every
-- closure created. An unrecorded function otherwise means "assume exact"
-- (primitives, a host's function), so APP tells the lambda apart here, on the
-- only path that needs to: applying it to other than one argument.
local getinfo = debug and debug.getinfo
-- The source names of chunks load_chunk loaded: compiled Shen, as opposed to a
-- host's own Lua, whatever it called its chunk. Recording this per chunk costs
-- nothing per closure, unlike marking each lambda as it is created.
local COMPILED_SOURCE = {}
local RAW_LAMBDA = setmetatable({}, {__mode="k"}) -- what getinfo said, per function
local function is_raw_lambda(f)
local r = RAW_LAMBDA[f]
if r ~= nil then return r end
r = false
if getinfo then
local i = getinfo(f, "uS")
r = i.nparams == 1 and not i.isvararg and i.what ~= "main"
and COMPILED_SOURCE[i.source] == true
end
RAW_LAMBDA[f] = r
return r
end
APP = function(f, ...)
-- Fast path: the operand is overwhelmingly a Lua function (a compiled Shen
-- function or a continuation/thunk). Check that first so the common case
-- avoids the `is_symbol` getmetatable probe entirely. APP is ~13% of the
-- typechecker's runtime, so this branch order matters.
if type(f) == "function" then
local n = select("#", ...)
local ar = FA[f]
if ar == nil then
if n == 1 or not is_raw_lambda(f) then -- primitive/unknown-arity fn: assume exact
return f(...)
end
ar = 1
end
if ar == n then
return f(...)
elseif n < ar then
return PARTIAL(f, ar, {...})
else
local args = {...}
local first = {}
for i=1,ar do first[i] = args[i] end
local r = f(unpack(first, 1, ar))
local rest = {}
for i=ar+1,n do rest[#rest+1] = args[i] end
return APP(r, unpack(rest, 1, #rest))
end
end
-- A frozen-continuation thunk applied with no args (KL `(thaw V)` sometimes
-- routes here): run it; if over-applied, apply the result to the rest.
if getmetatable(f) == Thunk then
if select("#", ...) == 0 then return runthunk(f) end
return APP(runthunk(f), ...)
end
-- Slow path: a symbol naming a function, or an error.
if is_symbol(f) then
local fn = F[f.name]
if fn == nil then ERR("not a function: " .. f.name) end
return APP(fn, ...)
end
ERR("attempt to apply a non-function")
end
P.APP, P.MKFUN, P.PARTIAL = APP, MKFUN, PARTIAL
-- What a compiled lambda of n parameters returns when called with fewer (see upart_guard
-- in compiler.lua): the arguments up to the first nil, partially applied. Called from the
-- lambda itself, not as a tail call, so level 2 is that lambda.
local getinfo_f = debug and debug.getinfo
local function UPART(n, ...)
local f = getinfo_f(2, "f").func
local have, k = { ... }, 0
while k < n - 1 and have[k + 1] ~= nil do k = k + 1 end
if FA[f] == nil and n > 1 then FA[f] = n end
if k == 0 then return f end
for i = k + 1, #have do have[i] = nil end
return PARTIAL(f, n, have)
end
P.UPART = UPART
-- ---- equality ------------------------------------------------------------
-- Lists are compared by walking the cdr spine in a loop and recursing only
-- into elements: the old car-and-cdr recursion was one Lua frame per cell,
-- which LuaJIT cannot trace (down-recursion aborts), so `=` on a list of N
-- cells ran interpreted. Deep `=` on list-shaped states is the hot path of
-- hash-map buckets and assoc lookups (issue #66).
local Cons = R.Cons
local function equal(a, b)
if a == b then return true end
if type(a) ~= "table" or type(b) ~= "table" then return false end
local mt = getmetatable(a)
if mt ~= getmetatable(b) then return false end
if mt == Cons then
repeat
local x, y = a[1], b[1]
if x ~= y and not equal(x, y) then return false end
a, b = a[2], b[2]
if a == b then return true end
until getmetatable(a) ~= Cons or getmetatable(b) ~= Cons
return equal(a, b)
end
-- vectors (pure-array layout: [1]=size, [i+2]=KL elt i)
if mt == Vmt then
local n = a[1]
if n ~= b[1] then return false end
for i=0,n-1 do
local x, y = a[i+2], b[i+2]
if x ~= y and not equal(x, y) then return false end
end
return true
end
return false
end
P.equal = equal
-- ---- primitive registration ---------------------------------------------
local function defprim(name, arity, fn)
F[name] = fn
FA[fn] = arity
C.ARITY[name] = arity
end
P.defprim = defprim
local function tonum(x)
if type(x) ~= "number" then ERR("not a number: " .. R.to_str(x)) end
return x
end
-- arithmetic
defprim("+", 2, function(a,b) return tonum(a) + tonum(b) end)
defprim("-", 2, function(a,b) return tonum(a) - tonum(b) end)
defprim("*", 2, function(a,b) return tonum(a) * tonum(b) end)
defprim("/", 2, function(a,b) b=tonum(b); if b==0 then ERR("division by zero") end; return tonum(a)/b end)
-- PUC Lua 5.3+ tier: Lua gained an integer subtype whose int64 arithmetic
-- WRAPS on overflow; LuaJIT (and 5.1) compute on IEEE doubles. The kernel
-- relies on double behaviour — e.g. shen.hashkey takes the product of all
-- byte values of a symbol name (astronomically large) and shen.mod reduces
-- it by repeated subtraction, which only terminates if the product stayed a
-- positive (possibly inexact) float rather than wrapping to a negative int64.
-- So on 5.3+ the value-producing arithmetic primitives compute in the float
-- domain, reproducing the LuaJIT number model exactly (comparisons need no
-- coercion: int/float compares are exact in 5.3+). Under LuaJIT
-- math.tointeger is nil and the definitions above stay installed unchanged.
if math.tointeger then
defprim("+", 2, function(a,b) return tonum(a) + 0.0 + tonum(b) end)
defprim("-", 2, function(a,b) return tonum(a) + 0.0 - tonum(b) end)
defprim("*", 2, function(a,b) return (tonum(a) + 0.0) * tonum(b) end)
defprim("/", 2, function(a,b) b=tonum(b); if b==0 then ERR("division by zero") end; return (tonum(a)+0.0)/b end)
end
defprim(">", 2, function(a,b) return tonum(a) > tonum(b) end)
defprim("<", 2, function(a,b) return tonum(a) < tonum(b) end)
defprim(">=",2, function(a,b) return tonum(a) >= tonum(b) end)
defprim("<=",2, function(a,b) return tonum(a) <= tonum(b) end)
defprim("=", 2, function(a,b) return equal(a,b) end)
-- lists
defprim("cons", 2, function(a,b) return cons(a,b) end)
defprim("hd", 1, function(x) if not is_cons(x) then ERR("hd of non-cons") end return x[1] end)
defprim("tl", 1, function(x) if not is_cons(x) then ERR("tl of non-cons") end return x[2] end)
defprim("cons?", 1, function(x) return is_cons(x) end)
-- predicates
defprim("number?", 1, function(x) return type(x)=="number" end)
defprim("string?", 1, function(x) return type(x)=="string" end)
defprim("symbol?", 1, function(x) return is_symbol(x) end)
defprim("boolean?",1, function(x) return type(x)=="boolean" end)
defprim("not", 1, function(x) if type(x)~="boolean" then ERR("not: not boolean") end return not x end)
-- what a test of a form that may not give a boolean compiles to (compiler.lua, bc)
local function boolean_check(x)
if x == true or x == false then return x end
ERR(R.to_str(x) .. " is not a boolean")
end
defprim("shen.bc", 1, boolean_check)
defprim("integer?",1, function(x) return type(x)=="number" and x==math.floor(x) and x~=math.huge and x~=-math.huge end)
-- symbols / strings
defprim("intern", 1, function(s)
if type(s)~="string" then ERR("intern: not a string") end
if s=="true" then return true elseif s=="false" then return false end
return intern(s)
end)
-- `str` on a number and the printer are two surfaces on ONE rendering rule, so
-- there is one implementation of it, in runtime.lua. Keeping a second copy here
-- is how they diverged before; do not reintroduce one. See R.num_to_str for the
-- rule (exact %d inside int64, shortest-round-trip expanded positionally
-- outside it, shortest_float for non-integral and non-finite values).
local numToStr = R.num_to_str
defprim("str", 1, function(x)
local t = type(x)
if t=="number" then return numToStr(x)
elseif t=="string" then return '"' .. x .. '"' -- quoted, as on shen-cl, shen-scheme, shen-go, shen-c
elseif t=="boolean" then return x and "true" or "false"
elseif is_symbol(x) then return x.name
elseif x==NIL then ERR("str: cannot convert ()")
else ERR("str: cannot convert") end
end)
defprim("cn", 2, function(a,b)
if type(a)~="string" or type(b)~="string" then ERR("cn: not strings") end
return a..b
end)
-- ---- strings are sequences of Unicode code points, held as UTF-8 ----------
-- (issue #80). A Shen string is a Lua string of UTF-8 bytes; the character
-- primitives (pos, tlstr, string->n, n->string, hdstr, explode, hash, the
-- reader) count CODE POINTS, not bytes. Pure-ASCII text stays on the old byte
-- fast path: every helper below first checks for a byte >= 0x80 and only then
-- walks the string as UTF-8. The checks are plain string.byte loops on
-- purpose: string.find with a pattern is not JIT-compiled by LuaJIT 2.1 and
-- aborts every trace that reaches it, which made an ASCII pos loop ~1000x
-- slower in testing. pos remembers the last string it scanned (first_high),
-- so a loop indexing one string scans it once.
--
-- INVALID UTF-8 is never an error and never loses data. Decoding is lenient:
-- any byte that does not begin a well-formed sequence -- a stray continuation
-- byte, a 0xC0/0xC1/0xF5..0xFF lead, a truncated sequence, an overlong form,
-- an encoded surrogate, anything above U+10FFFF -- is ONE character on its
-- own, consisting of that raw byte, whose code (string->n) is the byte value
-- 0x80..0xFF (the Latin-1 reading of that byte). pos/tlstr/explode keep the
-- raw byte, so (cn (hdstr S) (tlstr S)) == S always holds. The one thing that
-- does not round-trip is (n->string (string->n B)) for such a byte B: it
-- yields the UTF-8 encoding of U+0080..U+00FF, a different (valid) string.
-- The reader decodes source text the same way, so a stray Latin-1 byte in a
-- source string literal reads as the character of the same code.
--
-- n->string accepts integral 0..0x10FFFF except the surrogates
-- U+D800..U+DFFF and errors on anything else. Everything here is plain Lua
-- 5.1 string/arith code (no `utf8` library), so it runs identically on
-- LuaJIT 2.1 and PUC Lua 5.1..5.4.
local sbyte, ssub, schar = string.byte, string.sub, string.char
local mfloor = math.floor
-- first_high(s): byte index of the first byte >= 0x80 in s, or false if s is
-- pure ASCII. One-entry memo: strings are interned, so the hit test is a
-- pointer compare, and a loop calling pos on the same string scans it once.
local FH_S, FH_H = nil, false
local function first_high(s)
if s == FH_S then return FH_H end
local h = false
for i = 1, #s do
if sbyte(s, i) >= 0x80 then h = i; break end
end
FH_S, FH_H = s, h
return h
end
-- u8dec(s, i) -> code point, byte length of the character at byte index i
-- (i <= #s). Lenient: an ill-formed sequence decodes as its first byte alone.
local function u8dec(s, i)
local c = sbyte(s, i)
if c < 0x80 then return c, 1 end
if c < 0xC2 then return c, 1 end
if c < 0xE0 then
local c2 = sbyte(s, i + 1)
if c2 and c2 >= 0x80 and c2 < 0xC0 then return (c - 0xC0) * 64 + (c2 - 0x80), 2 end
return c, 1
end
if c < 0xF0 then
local c2, c3 = sbyte(s, i + 1, i + 2)
if c3 and c2 >= 0x80 and c2 < 0xC0 and c3 >= 0x80 and c3 < 0xC0 then
local cp = (c - 0xE0) * 4096 + (c2 - 0x80) * 64 + (c3 - 0x80)
if cp >= 0x800 and (cp < 0xD800 or cp > 0xDFFF) then return cp, 3 end
end
return c, 1
end
if c < 0xF5 then
local c2, c3, c4 = sbyte(s, i + 1, i + 3)
if c4 and c2 >= 0x80 and c2 < 0xC0 and c3 >= 0x80 and c3 < 0xC0
and c4 >= 0x80 and c4 < 0xC0 then
local cp = (c - 0xF0) * 262144 + (c2 - 0x80) * 4096 + (c3 - 0x80) * 64 + (c4 - 0x80)
if cp >= 0x10000 and cp <= 0x10FFFF then return cp, 4 end
end
end
return c, 1
end
-- u8enc(n) -> UTF-8 encoding of code point n, or nil if n is not an integral
-- Unicode scalar value (0..0x10FFFF minus the surrogates).
local function u8enc(n)
if type(n) ~= "number" or n ~= mfloor(n) or n < 0 then return nil end
if n < 0x80 then return schar(n) end
if n < 0x800 then return schar(0xC0 + mfloor(n / 64), 0x80 + n % 64) end
if n < 0x10000 then
if n >= 0xD800 and n <= 0xDFFF then return nil end
return schar(0xE0 + mfloor(n / 4096), 0x80 + mfloor(n / 64) % 64, 0x80 + n % 64)
end
if n <= 0x10FFFF then
return schar(0xF0 + mfloor(n / 262144), 0x80 + mfloor(n / 4096) % 64,
0x80 + mfloor(n / 64) % 64, 0x80 + n % 64)
end
return nil
end
-- u8len(s): number of characters (code points / lone invalid bytes).
local function u8len(s)
local h = first_high(s)
if not h then return #s end
local n, i, len = h - 1, h, #s
while i <= len do
local _, l = u8dec(s, i)
i = i + l; n = n + 1
end
return n
end
-- u8pos(s, n): the n-th (0-based) character of s as a string, or nil when n
-- is out of range. ASCII prefix -> one byte substring.
local function u8pos(s, n)
local len = #s
if n >= len then return nil end -- chars <= bytes
local h = first_high(s)
if not h or h > n + 1 then return ssub(s, n + 1, n + 1) end
local i, k = h, h - 1 -- k = index of char at byte i
while i <= len do
local _, l = u8dec(s, i)
if k == n then return ssub(s, i, i + l - 1) end
i = i + l; k = k + 1
end
return nil
end
-- u8tl(s): s without its first character (s non-empty).
local function u8tl(s)
local c = sbyte(s, 1)
if c < 0xC2 then return ssub(s, 2) end
local _, l = u8dec(s, 1)
return ssub(s, l + 1)
end
-- u8hd(s): the first character of s as a string (s non-empty).
local function u8hd(s)
local c = sbyte(s, 1)
if c < 0xC2 then return ssub(s, 1, 1) end
local _, l = u8dec(s, 1)
return ssub(s, 1, l)
end
-- u8explode(s): KL list of the characters of s.
local function u8explode(s)
local acc = NIL
local i = #s
while i >= 1 do -- ASCII fast path, back to front
local b = sbyte(s, i)
if b >= 0x80 then break end
acc = cons(schar(b), acc)
i = i - 1
end
if i == 0 then return acc end
acc = NIL
local chars, len = {}, #s
i = 1
while i <= len do
local _, l = u8dec(s, i)
chars[#chars + 1] = ssub(s, i, i + l - 1)
i = i + l
end
for j = #chars, 1, -1 do acc = cons(chars[j], acc) end
return acc
end
-- u8codes(s): KL list of the character codes of s (string->n of each char).
local function u8codes(s)
local acc = NIL
local i = #s
while i >= 1 do -- ASCII fast path, back to front
local b = sbyte(s, i)
if b >= 0x80 then break end
acc = cons(b, acc)
i = i - 1
end
if i == 0 then return acc end
acc = NIL
local cps, len = {}, #s
i = 1
while i <= len do
local cp, l = u8dec(s, i)
cps[#cps + 1] = cp
i = i + l
end
for j = #cps, 1, -1 do acc = cons(cps[j], acc) end
return acc
end
P.utf8 = { first_high = first_high, dec = u8dec, enc = u8enc, len = u8len,
pos = u8pos, tl = u8tl, hd = u8hd, explode = u8explode, codes = u8codes }
local function nstr_error(n)
local shown = type(n) == "number" and numToStr(n) or tostring(n)
ERR("n->string: " .. shown .. " is not a Unicode code point (0..1114111, excluding surrogates)")
end
defprim("pos", 2, function(s,n)
if type(s)~="string" then ERR("pos: not a string") end
if type(n)~="number" or n < 0 or n ~= mfloor(n) then ERR("pos: index out of range") end
local c = u8pos(s, n)
if c == nil then ERR("pos: index out of range") end
return c
end)
defprim("tlstr", 1, function(s)
if type(s)~="string" then ERR("tlstr: not a string") end
if #s == 0 then ERR("tlstr: empty string") end
return u8tl(s)
end)
defprim("string->n", 1, function(s)
if type(s) ~= "string" or #s == 0 then ERR("string->n: empty or non-string") end
local c = sbyte(s, 1)
if c < 0xC2 then return c end
return (u8dec(s, 1))
end)
defprim("n->string", 1, function(n)
if type(n) ~= "number" then ERR("n->string: not a number") end
local ch = u8enc(n)
if ch == nil then nstr_error(n) end
return ch
end)
defprim("string->symbol", 1, function(s) return intern(s) end)
-- empty?
defprim("empty?", 1, function(x) return x==NIL end)
-- globals (dual namespace)
-- Only a symbol names a global: keying on tostring() made (set "x" 1) and
-- (set x 1) the same variable, and (set 1 2) define one called "1".
defprim("set", 2, function(sym, v)
if not is_symbol(sym) then ERR(R.to_str(sym) .. " is not a symbol") end
GLOBALS[sym.name] = v; return v
end)
defprim("value", 1, function(sym)
if not is_symbol(sym) then ERR(R.to_str(sym) .. " is not a symbol") end
local key = sym.name
local v = GLOBALS[key]
if v == nil then ERR("variable " .. key .. " has no value") end
return v
end)
-- errors
defprim("simple-error", 1, function(msg) ERR(type(msg)=="string" and msg or R.to_str(msg)) end)
defprim("error-to-string", 1, function(e)
if getmetatable(e)==Excn then return e.msg end
return tostring(e)
end)
-- vectors (absvector: raw 0-indexed store of size n)
local FAILOBJ = intern("shen.fail!")
P.FAILOBJ = FAILOBJ
defprim("absvector", 1, function(n)
-- Validate first: a negative or fractional length would build a table whose
-- length word disagrees with its slots (and a non-number used to surface as
-- a raw Lua arithmetic error), and the printer dies on the result outside
-- any handler the program set up.
if type(n) ~= "number" or n < 0 or n % 1 ~= 0 then
ERR(R.to_str(n) .. " is not a valid vector length")
end
local v = { [1] = n }
for i=0,n-1 do v[i+2] = FAILOBJ end
return setmetatable(v, Vmt)
end)
defprim("absvector?", 1, function(x) return getmetatable(x)==Vmt end)
-- An out-of-range read is an error (every in-range slot holds a value: the
-- fail object until written), so kernel code that probes past the end under
-- trap-error -- the vector printer's shen.iter-vector, shen.dict? -- sees
-- the boundary instead of a Lua nil.
local function addr_oob(v, i)
ERR(R.to_str and (tostring(i) .. " is not a valid index") or "invalid index")
end
P.addr_oob = addr_oob
-- A negative index is out of range too: v[1] holds the length word. A write to
-- a slot that does not exist raises as well, rather than growing the table.
defprim("<-address", 2, function(v, i)
local w = v[i+2]
if w == nil or i < 0 then addr_oob(v, i) end
return w
end)
defprim("address->", 3, function(v, i, x)
if v[i+2] == nil or i < 0 then addr_oob(v, i) end
rawset(v, i+2, x); return v
end)
-- freeze/thaw : thunks are 0-arity functions (kernel: (defun thaw (V) (V)))
-- Hot path in the Prolog/typechecker CPS: a thawed value is always a 0-arity
-- Lua closure (produced by `freeze` / BIND), so call it directly and skip the
-- full APP dispatch (symbol check, arity lookup, vararg packing). APP remains
-- the fallback for the rare symbol case.
defprim("thaw", 1, function(x)
if getmetatable(x) == Thunk then return runthunk(x) end
if type(x) == "function" then return x() end
return APP(x)
end)
-- type : erased
defprim("type", 2, function(x, _ty) return x end)
-- eval-kl
local load_form -- fwd (defined below)
defprim("eval-kl", 1, function(form) return P.eval(form) end)
-- get-time : (get-time Sym), Sym in {run, real, unix}; anything else raises
local t0_real = os.time()
defprim("get-time", 1, function(sym)
local name = is_symbol(sym) and sym.name
if name == "run" then return os.clock()
elseif name == "unix" then return os.time()
elseif name == "real" then return os.time() - t0_real -- wall seconds since boot
else ERR("get-time: invalid option: " .. R.to_str(sym)) end
end)
-- ---- streams -------------------------------------------------------------
-- Stream objects carry a metatable so they are never confused with vectors
-- (absvector? requires getmetatable(x)==Vmt) or cons cells.
local Stream = {}
P.Stream = Stream
local function is_stream(x) return type(x)=="table" and getmetatable(x)==Stream end
P.is_stream = is_stream
local function mk_out_stream(writefn, closefn, name)
return setmetatable({ kind="out", write=writefn, close=closefn, name=name }, Stream)
end
local function mk_in_stream(readfn, closefn, name)
return setmetatable({ kind="in", readbyte=readfn, close=closefn, name=name, eof=false }, Stream)
end
P.mk_out_stream, P.mk_in_stream = mk_out_stream, mk_in_stream
-- 43.1 public character-stream interfaces. `pr` uses char-stream? to choose
-- between a fast (write-string) and a fallback (write-chars) path. write-chars
-- writes (string->n (pos S I)) per character with write-byte, which cannot
-- carry a code point above 0x7F (issue #80), so every output stream here is a
-- CHARACTER stream for pr: shen.write-string writes the string's UTF-8 bytes
-- as they are. write-byte stays a raw byte primitive.
defprim("char-stream?", 1, function(st) return is_stream(st) end)
defprim("write-string", 2, function(s, st)
if not is_stream(st) or st.kind~="out" then ERR("pr: not an output stream") end
if type(s) ~= "string" then ERR("pr: not a string") end
st.write(s)
return s
end)
-- write-byte (N STREAM) -> N : write a single byte to an output stream
defprim("write-byte", 2, function(n, st)
if not is_stream(st) or st.kind~="out" then ERR("write-byte: not an output stream") end
st.write(string.char(n))
return n
end)
-- raw next byte of an input stream, honouring one byte of pushback (used by
-- the UTF-8 decoder below when a sequence turns out to be ill-formed).
local function stream_byte(st)
local pb = st.pb
if pb then st.pb = nil; return pb end
if st.eof then return -1 end
local b = st.readbyte()
if b == nil then st.eof = true; return -1 end
return b
end
-- read-byte (STREAM) -> N | -1 at EOF
defprim("read-byte", 1, function(st)
if not is_stream(st) or st.kind~="in" then ERR("read-byte: not an input stream") end
return stream_byte(st)
end)
-- stream_char(st) -> code point of the next character of st, or -1 at EOF.
-- Lenient like u8dec: an ill-formed sequence yields its lead byte's value and
-- the offending byte is pushed back to start the next character.
local function stream_char(st)
local c = stream_byte(st)
if c < 0xC2 or c > 0xF4 then return c end -- ASCII, EOF, or lone byte
local need = c < 0xE0 and 1 or (c < 0xF0 and 2 or 3)
local cp = c < 0xE0 and c - 0xC0 or (c < 0xF0 and c - 0xE0 or c - 0xF0)
for _ = 1, need do
local b = stream_byte(st)
if b < 0x80 or b > 0xBF then
if b ~= -1 then st.pb = b end
return c
end
cp = cp * 64 + (b - 0x80)
end
if (need == 2 and (cp < 0x800 or (cp >= 0xD800 and cp <= 0xDFFF)))
or (need == 3 and (cp < 0x10000 or cp > 0x10FFFF)) then
return c -- overlong / surrogate / out of range: lead byte alone
end
return cp
end
-- shen.my-read-byte (reader.kl) feeds the reader behind `read` and `lineread`.
-- The reader consumes character codes (it rebuilds text with n->string), so
-- the native override (install_native_stdlib) reads one UTF-8 character with
-- stream_char and returns its code point; read-byte on the same stream still
-- sees raw bytes.
-- read-unit-string: one character as a string ("" at EOF).
defprim("read-unit-string", 1, function(st)
if not is_stream(st) or st.kind~="in" then ERR("read-unit-string: not an input stream") end
local cp = stream_char(st)
if cp == -1 then return "" end
return u8enc(cp) or schar(cp)
end)
-- Keep the pre-43 hook names available to older user code. The 43.1 kernel
-- itself uses only the public names above.
defprim("shen.char-stoutput?", 1, function(st) return is_stream(st) end)
defprim("shen.char-stinput?", 1, function(st) return is_stream(st) end)
defprim("shen.write-string", 2, function(s, st) return F["write-string"](s, st) end)
defprim("shen.read-unit-string", 1, function(st) return F["read-unit-string"](st) end)
-- A file name as `open` sees it: *home-directory*, which `cd` sets (sys.kl),
-- prepended as a plain string, as shen-scheme and shen-go do, so an absolute
-- name after a non-empty cd is joined too. Every native path that
-- reads a user file (read-file, read-file-as-*, the fasl `load`) resolves
-- through this too, so it opens the same file `open` would.
local function home_path(name)
local home = GLOBALS["*home-directory*"]
if type(home) ~= "string" or home == "" then
return name
end
return home .. name
end
P.home_path = home_path
-- open (NAME DIRECTION) -> stream ; DIRECTION is symbol `in` or `out`
defprim("open", 2, function(name, dir)
if type(name)~="string" then ERR("open: filename not a string") end
local d = is_symbol(dir) and dir.name or tostring(dir)
name = home_path(name)
if d == "in" then
local fh, e = io.open(name, "rb")
if not fh then ERR("open: cannot open "..name.." ("..tostring(e)..")") end
return mk_in_stream(function() local c = fh:read(1); return c and string.byte(c) or nil end,
function() fh:close() end, name)
elseif d == "out" then
local fh, e = io.open(name, "wb")
if not fh then ERR("open: cannot open "..name.." ("..tostring(e)..")") end
return mk_out_stream(function(s) fh:write(s) end, function() fh:close() end, name)
else
ERR("open: bad direction "..d)
end
end)
-- close (STREAM) -> ()
defprim("close", 1, function(st)
if not is_stream(st) then ERR("close: not a stream") end
-- Closing twice is harmless; using a closed stream raises a Shen error, not
-- Lua's "attempt to use a closed file". Replacing the functions keeps the
-- read and write paths free of a closed check.
if st.close then
st.close()
st.close = nil
if st.kind == "in" then
st.readbyte = function() ERR("read-byte: stream is closed") end
st.pb, st.eof = nil, false
else
st.write = function() ERR("write-byte: stream is closed") end
end
end
return NIL
end)
-- exit
defprim("exit", 1, function(n) io.stdout:flush(); os.exit(type(n)=="number" and n or 0) end)
-- Native reimplementation of the hottest Prolog dereference primitives.
-- These run ~6x/inference in the typechecker; as compiled KL each call pays
-- function-dispatch + per-step `<-address`/`shen.pvar?` indirection. The native
-- versions are tight Lua loops over the prolog binding vector (this is what the
-- shen-c and shen-rust ports do). shen.deref additionally does STRUCTURE SHARING
-- -- returning the original cons subtree unchanged when nothing dereffed -- which
-- the native C/Rust ports do NOT do, eliminating most of deref's cons allocation.
-- Installed after the kernel loads (overriding the compiled KL defuns in F).
-- A prolog variable is an absvector (pure-array layout, metatable Vmt): KL
-- index 0 (the `shen.pvar` tag) lives at slot [2], KL index 1 (the ticket) at
-- slot [3]. The binding for ticket t lives at prolog-vector KL-index t, i.e.
-- slot v[t+2], with shen.-null- meaning unbound.
function P.install_native_prolog()
local shen_pvar = intern("shen.pvar")
local shen_null = intern("shen.-null-")
local getmt = getmetatable
-- Allocation-attribution instrumentation (Part 1, THROWAWAY). Uses the
-- module-scope AP/APROF (shared with ENV.BIND/MKFUN). `prof` is a single
-- predictable-false branch when the flag is off.
local prof = APROF
local function is_pvar(x)
return getmt(x) == Vmt and x[2] == shen_pvar
end
local function lazyderef(x, v)
while getmt(x) == Vmt and x[2] == shen_pvar do
local w = v[x[3]+2]
if w == shen_null then return x end
x = w
end
return x
end
local function deref(x, v)
if prof then AP.deref_calls = AP.deref_calls + 1 end
if is_cons(x) then
local h0, t0 = x[1], x[2]
local h = deref(h0, v)
local t = deref(t0, v)
if h == h0 and t == t0 then return x end -- structure sharing: nothing changed
if prof then AP.deref_cons = AP.deref_cons + 1 end
return cons(h, t)
elseif getmt(x) == Vmt and x[2] == shen_pvar then
local w = v[x[3]+2]
if w == shen_null then return x end
return deref(w, v)
else
return x
end
end
-- Native unification core (extends the native deref family). These are the
-- hottest compiled-KL Prolog primitives; as KL each call pays F-table
-- dispatch + per-step `<-address`/`shen.pvar?` (which in KL wraps a
-- trap-error!) indirection. The native versions are tight Lua that call each
-- other directly (no F-table round-trip) -- this is what shen-c's overwrite.c
-- does. Semantics mirror klambda/prolog.kl EXACTLY (binding trail via the
-- prolog vector, occurs check, freeze/thaw CPS continuations). None of these
-- functions touch shen.*infs*, so the inference count is unchanged.
--
-- A continuation (KL `freeze`) is thawed after a successful bind; it may be a
-- BIND-thunk table (from compiled KL callers) or a plain Lua closure (built
-- by native lzy= below), so thaw handles both.
local function thaw(c)
if getmt(c) == Thunk then return runthunk(c) end
if type(c) == "function" then return c() end
return APP(c)
end
-- bindv: prolog-vector[ Var's ticket ] := Val (KL <-address Var 1 = Var[3])
local function bindv(var, val, vec) vec[var[3]+2] = val; return vec end
-- unwind: undo a binding on backtrack, returning the (false) result through.
local function unwind(var, vec, x) vec[var[3]+2] = shen_null; return x end
-- bind!: bind, run the continuation; if it fails (false) undo the binding.
local function bind_(var, val, vec, cont)
if prof then AP.bind_calls = AP.bind_calls + 1 end
bindv(var, val, vec)
local w = thaw(cont)
if w == false then return unwind(var, vec, w) end
return w
end
local function occurs(var, x)
if equal(var, x) then return true end
if is_cons(x) then
return occurs(var, x[1]) or occurs(var, x[2])
end
return false
end
-- lzy= : lazy unification (no occurs check). X and Y are already lazyderef'd
-- by the caller / by the recursive step. The tail continuation is a Lua
-- closure (KL `freeze`) that lazyderefs the tails when thawed.
local lzy
lzy = function(x, y, v, cont)
if prof then AP.lzy_calls = AP.lzy_calls + 1 end
if equal(x, y) then return thaw(cont) end
if is_pvar(x) then return bind_(x, y, v, cont) end
if is_pvar(y) then return bind_(y, x, v, cont) end
if is_cons(x) and is_cons(y) then
local xt, yt = x[2], y[2]
if prof then AP.lzy_cont = AP.lzy_cont + 1 end
return lzy(lazyderef(x[1], v), lazyderef(y[1], v), v,
function() return lzy(lazyderef(xt, v), lazyderef(yt, v), v, cont) end)
end
return false
end
-- lzy=! : lazy unification WITH occurs check (mirrors shen.lzy=!).
local lzyoc
lzyoc = function(x, y, v, cont)
if prof then AP.lzyoc_calls = AP.lzyoc_calls + 1 end
if equal(x, y) then return thaw(cont) end
if is_pvar(x) then
if prof then AP.occ_deref_calls = AP.occ_deref_calls + 1 end
if not occurs(x, deref(y, v)) then return bind_(x, y, v, cont) end
end
if is_pvar(y) then
if prof then AP.occ_deref_calls = AP.occ_deref_calls + 1 end
if not occurs(y, deref(x, v)) then return bind_(y, x, v, cont) end
end
if is_cons(x) and is_cons(y) then
local xt, yt = x[2], y[2]
if prof then AP.lzyoc_cont = AP.lzyoc_cont + 1 end
return lzyoc(lazyderef(x[1], v), lazyderef(y[1], v), v,
function() return lzyoc(lazyderef(xt, v), lazyderef(yt, v), v, cont) end)
end
return false
end
-- pvar pooling (playbook D). Tickets are allocated/reclaimed in strict LIFO
-- order: newpv bumps vec[3], gc-on-failure decrements it. A failed branch's
-- pvar (the one whose ticket gc reclaims) is not part of any result -- success
-- propagates x~=false so result pvars are never pooled -- so its 2-slot table
-- can be recycled instead of GC'd + reallocated by the next newpv. pstk
-- records, per ticket, the object created there so gc can reclaim it. A pooled
-- pvar only ever has its [3] (ticket) overwritten; [1]=2 and [2]=shen.pvar are
-- invariant, so reuse just rewrites the ticket. Scratch state is per-run, but
-- vectors are used sequentially (never nested in one inference), so a global
-- ticket-indexed stack is safe.
--
-- RESIDUAL RISK (validated empirically: 42 and 42 suites 134/134 + the typecheck
-- inference count is byte-identical with and without pooling, so no exercised
-- unification path is perturbed): recycling reuses the table OBJECT, not just
-- the ticket. This is unsafe only if a reclaimed-ticket pvar object is still
-- live after its branch fails. The one construct that could do that is
-- findall/shen.overbind, which snapshots derefed terms (shen.deref keeps
-- UNBOUND pvars by identity) into a collector across backtracking; if such a
-- snapshot retained a high-ticket unbound pvar that gc later reclaims, reuse
-- would mutate it. The kernel's own type rules don't trigger this (hence the
-- identical inference count), but heavy user-level findall over unbound logic
-- vars is the boundary to re-validate before reusing this pool elsewhere.
local pool = {} -- freelist of recyclable {2, shen.pvar, ticket} tables
local pstk = {} -- pstk[ticket] = pvar object allocated at that ticket
-- newpv: reuse a pooled pvar (or allocate), record it, clear its binding
-- slot, and bump the vector's ticket counter (KL index 1 = slot [3]).
local function newpv(vec)
if prof then AP.newpv_total = AP.newpv_total + 1 end
local n = vec[3]
-- Per-query capacity: shen.prolog-vector allocates ONE absvector of
-- (value shen.*prolog-memory*) slots per query, so the kernel's
-- shen.nextticket writes slot n and the query dies once n reaches the
-- vector size. This native path stores without going through address->,
-- so without this the vector would silently grow and a query that raises
-- on every other port would answer here.
local size = vec[1]
if type(size) == "number" and n >= size then
ERR("prolog vector index out of range: a single query may allocate at "
.. "most " .. (size - 2) .. " variables (shen.*prolog-memory*)")
end
local np = #pool
local pv = pool[np]
if pv ~= nil then pool[np] = nil; pv[3] = n
else
if prof then AP.newpv_poolmiss = AP.newpv_poolmiss + 1 end
pv = setmetatable({ [1] = 2, [2] = shen_pvar, [3] = n }, Vmt)
end
pstk[n] = pv
vec[n+2] = shen_null
vec[3] = n + 1
return pv
end
-- gc: on backtrack (x==false) reclaim the most recent ticket and recycle its
-- pvar object; else pass x through.
local function gc(vec, x)