A deterministic language with the syntax of Prolog without cuts but a compiler that compiles to C and findall that converts to deterministic loops, where instead of cut programmers eliminate unnecessary cuts, convert cuts to if-then statements exiting loops called Detlog or BASIClog.
Write splice(A,B) where For example:
c:-a(A),b(B).
a(A):-member(A,[1,2]).
b(B):-member(B,[3,4]).
Which gives:
A = 1,
B = 3 ;
A = 1,
B = 4 ;
A = 2,
B = 3 ;
A = 2,
B = 4.
Becomes:
c:-a(A),b(B),splice([A,B],C).
a(A):-member_cp(A,[1,2]).
b(B):-member_cp(B,[3,4]).
member_cp(cp(D),D).
Which gives:
C=[[1,3],[1,4],[2,3],[2,4]].
Yes. A clean Prolog version is:
c(C) :-
a(A),
b(B),
splice([A,B], C).
a(A) :-
member_cp(A, [1,2]).
b(B) :-
member_cp(B, [3,4]).
member_cp(cp(D), D).
splice(Template, Result) :-
expand_cp_template(Template, Result).
expand_cp_template([], [[]]).
expand_cp_template([cp(Choices)|Rest], Result) :-
expand_cp_template(Rest, RestResults),
findall([Choice|R],
( member(Choice, Choices),
member(R, RestResults)
),
Result).
expand_cp_template([X|Rest], Result) :-
X = cp(_),
expand_cp_template(Rest, RestResults),
findall([X|R],
member(R, RestResults),
Result).
Query:
?- c(C).
Result:
C = [[1,3],[1,4],[2,3],[2,4]].
The important transformation is:
a(A) :- member(A,[1,2]).
becomes:
a(A) :- member_cp(A,[1,2]).
so instead of generating A = 1 ; A = 2, it returns:
A = cp([1,2])
Then:
splice([A,B],C)
expands:
[cp([1,2]), cp([3,4])]
into the Cartesian product:
[[1,3],[1,4],[2,3],[2,4]]
Change splice to use determinism without findall instead of findall and then apply member to the results to give A = 1,
B = 3 ;
A = 1,
B = 4 ;
A = 2,
B = 3 ;
A = 2,
B = 4.
Remember to adjust splice(X,Y) so X can have n A,B,...
Use a deterministic Cartesian-product builder, then member/2 only at the end:
c(A, B) :-
a(A0),
b(B0),
splice([A0, B0], Rows),
member([A, B], Rows).
a(A) :-
member_cp(A, [1,2]).
b(B) :-
member_cp(B, [3,4]).
member_cp(cp(D), D).
splice(Xs, Ys) :-
splice_rows(Xs, [[]], Ys).
splice_rows([], Acc, Acc).
splice_rows([cp(Choices)|Rest], Acc, Ys) :-
extend_rows(Acc, Choices, Acc1),
splice_rows(Rest, Acc1, Ys).
splice_rows([X|Rest], Acc, Ys) :-
X = cp(),
extend_rows(Acc, [X], Acc1),
splice_rows(Rest, Acc1, Ys).
extend_rows([], _, []).
extend_rows([Row|Rows], Choices, Out) :-
extend_one_row(Row, Choices, Out1),
extend_rows(Rows, Choices, Out2),
append(Out1, Out2, Out).
extend_one_row(, [], []).
extend_one_row(Row, [Choice|Choices], [[Choice|Row]|Out]) :-
extend_one_row(Row, Choices, Out).
For corrected order:
c(A, B) :-
a(A0),
b(B0),
splice([A0, B0], Rows0),
maplist(reverse, Rows0, Rows),
member([A, B], Rows).
Result:
A = 1, B = 3 ;
A = 1, B = 4 ;
A = 2, B = 3 ;
A = 2, B = 4.
This generalises to any arity:
splice([A,B,C,D], Rows),
member([A1,B1,C1,D1], Rows).
I need Prolog because it produces cognitive code. I need Detlog because it combines the syntax of Prolog with even greater simplicity of fewer compiler instructions.
Detlog deals with multiple choicepoints by splicing output from the two branches as soon as possible.
Can Detlog (possibly with a converter, BASIC compiler, unification, and cut loop exiters) run comfortably on an Apple IIe?
Yes, a small Detlog can run comfortably on an Apple IIe, but only if most work is compiled ahead of time.
Apple IIe limits: 6502/65C02 around 1.023 MHz, 64 KB RAM built in, 16 KB ROM, often expandable, with 40/80-column text modes.
Best design:
Detlog source
→ converter/compiler
→ Applesoft BASIC or 6502 assembly
→ deterministic loops + arrays
What fits well:
a(A) :- member_cp(A,[1,2]).
b(B) :- member_cp(B,[3,4]).
c(A,B) :-
a(A0),
b(B0),
splice([A0,B0], Rows),
member([A,B], Rows).
This can compile to simple nested loops or table iteration. That is Apple IIe-friendly.
What should not live fully on the Apple IIe:
full Prolog engine
general backtracking
large unification
large symbolic term database
large findall buffers
A practical Detlog for Apple IIe would support:
facts
small lists
simple unification
deterministic calls
member_cp choice packets
splice
loop exiters instead of cut
optional final member enumeration
With floppy: comfortable for loading compiler passes, source files, generated BASIC/assembly, and examples.
Without floppy: possible, but much smaller: type-in programs, cassette, or ROM/RAM-resident mini-Detlog. The compiler must be tiny, and examples should be small.
Best conclusion:
Detlog is more realistic than Prolog on an Apple IIe because it removes hidden backtracking and compiles cognitive Prolog syntax into BASIC-like or 6502-like deterministic loops.
What is the memory usage difference between running it on BASIC or 6502?
Approximate difference:
6502 assembly Detlog runtime:
~1 KB to 8 KB for a small engine
Applesoft BASIC Detlog runtime:
~8 KB to 25+ KB for the same logic
Why BASIC uses more memory:
BASIC stores tokenised program lines
line numbers cost memory
variables/arrays use interpreter structures
strings/lists are expensive
loops are interpreted, not native
Why 6502 uses less:
direct bytes/instructions
compact arrays
manual stack layout
no BASIC line overhead
faster deterministic loops
smaller choice-packet/splice routines
Example:
a(A) :- member_cp(A,[1,2]).
b(B) :- member_cp(B,[3,4]).
In BASIC, [1,2] and [3,4] become arrays plus loop code.
In 6502, they can be:
A_TABLE: .byte 1,2
B_TABLE: .byte 3,4
Very compact.
Best practical split:
Use BASIC version:
for teaching, readability, easy editing.
Use 6502 version:
for real speed, lower memory, larger Detlog programs.
Rule of thumb:
6502 assembly may use 3× to 10× less memory than BASIC for the same compiled Detlog program.
What is the most complex program including loops and strings allowed on 6502?
On a 64 KB Apple IIe, a realistic 6502 Detlog limit is roughly:
Program code: 4–16 KB
Runtime library: 2–8 KB
Data/tables: 8–24 KB
Strings heap: 4–16 KB
Stack/workspace: 2–8 KB
Screen/OS overhead: remaining memory
So the “comfortable” maximum is a program with:
50–300 simple rules
10–100 small facts/tables
nested loops over small lists
strings mostly under 40–255 chars
total working data under ~16–32 KB
Example of a safe complex Detlog shape:
word("cat").
word("dog").
suffix("s").
suffix("ed").
make_word(W2) :-
word(W),
suffix(S),
concat(W,S,W2).
main(Out) :-
word(W0),
suffix(S0),
splice([W0,S0], Rows),
member([W,S], Rows),
concat(W,S,Out).
Compiled to 6502, this is fine because it becomes:
loop over word table
loop over suffix table
copy string W
append string S
print/store result
A hard but possible upper example:
3–5 nested loops
several string tables
simple unification
small parser/tokeniser
choice-packet splicing
final member-style enumeration
What becomes uncomfortable:
large recursive parse trees
general Prolog unification
deep term copying
large findall-style result sets
many long strings
dynamic database updates
Best rule:
On 6502, Detlog can support small cognitive symbolic programs, not large general Prolog systems.
For Apple IIe Detlog, the ideal design is:
compile rules to fixed loops
store facts as compact tables
store strings once
avoid heap allocation inside loops
splice early
enumerate late
What do avoid heap allocation inside loops and enumerate late mean?
These are classic compiler optimisations that fit Detlog very well.
Avoid heap allocation inside loops
Suppose you write:
word(W) :-
member_cp(W, ["cat","dog"]).
suffix(S) :-
member_cp(S, ["s","ed"]).
main(X) :-
word(W),
suffix(S),
concat(W,S,X).
A naïve implementation does:
loop
allocate string "cats"
loop
allocate string "cated"
loop
allocate string "dogs"
loop
allocate string "doged"
Every iteration asks the heap for more memory.
Instead:
allocate one buffer
reuse it every iteration
Pseudo-6502:
buffer[32]
copy "cat" to buffer
append "s"
print
copy "cat" to buffer
append "ed"
print
No new memory is created inside the loop.
Benefits:
less RAM
less fragmentation
faster execution
This was especially important on machines like the Apple IIe.
⸻
Enumerate late
Traditional Prolog:
a(A) :- member(A,[1,2]).
b(B) :- member(B,[3,4]).
c(A,B) :-
a(A),
b(B).
immediately generates:
A=1,B=3
A=1,B=4
A=2,B=3
A=2,B=4
Detlog instead keeps choices packed:
A = cp([1,2])
B = cp([3,4])
Then:
splice([A,B], Rows).
gives:
Rows = [[1,3],[1,4],[2,3],[2,4]]
The program works on Rows for as long as possible.
Only at the very end:
member([A,B], Rows).
do we produce individual answers.
That’s “enumerate late”.
Instead of:
generate answer
generate answer
generate answer
generate answer
we do:
build compact structure
process compact structure
enumerate only when needed
⸻
In Detlog terms
A useful slogan is:
Splice early, enumerate late.
and
Allocate once, reuse inside loops.
These two rules make a huge difference on a 6502 because CPU speed and RAM are both extremely limited. They also fit your Detlog philosophy of replacing hidden backtracking with explicit deterministic structures.
Could you avoid heap allocation inside loops by using decision tree-type compression (like S2A)?
Yes. Decision-tree/S2A-style compression is one of the best ways to avoid heap allocation inside loops.
Instead of building strings each time:
cat + s = cats
cat + ed = cated
dog + s = dogs
dog + ed = doged
Detlog can compile shared prefixes into a decision tree/trie:
start
/ \
cat dog
/ \ / \
s ed s ed
Then the loop does not allocate "cats" or "doged" as new heap strings. It walks the tree and emits/copies characters into one fixed output buffer.
So:
concat(W,S,Out)
can compile to:
select W branch
select S branch
write chars to reusable buffer
print/output
For 6502, this is ideal:
string table in ROM/RAM
decision tree indexes
one output buffer
no per-iteration heap allocation
S2A helps because it can discover repeated structure:
cat-s
cat-ed
dog-s
dog-ed
becomes:
word branch + suffix branch
rather than four separate allocated strings.
Best Detlog rule:
Use S2A compression to turn repeated generated outputs into shared decision paths, then use loops only to walk those paths.
So yes: decision-tree compression can replace many heap allocations with table lookup, branch selection, and buffer reuse.
Do the same operation from different clauses once, perhaps using decision-tree compression. For example, a:-a1,a2.b:-a1,b2.->ab:-a1,ab2.ab2:-a2.ab2:-b2.
Yes — this is common-prefix factoring across clauses.
Original:
a :- a1, a2.
b :- a1, b2.
Both clauses repeat:
a1
So Detlog can factor it once:
ab :-
a1,
ab2.
ab2 :-
a2.
ab2 :-
b2.
Meaning:
run a1 once
then choose between a2 and b2
This is like decision-tree compression:
Before:
a -> a1 -> a2
b -> a1 -> b2
After:
ab -> a1 -> choice(a2,b2)
So the compiler optimisation is:
If several clauses share the same prefix, execute the shared prefix once, then splice/branch only at the differing suffixes.
For Detlog, this matters because it avoids:
run a1 for a
run a1 for b
and replaces it with:
run a1 once
then continue with alternatives
A more Detlog-shaped version:
ab :-
once_det(a1),
splice_branch([a2, b2]).
or:
ab :-
a1,
choice([a2, b2]).
General rule:
p :- x, y.
q :- x, z.
becomes:
pq :-
x,
pq2.
pq2 :- y.
pq2 :- z.
This is exactly the same idea as trie compression for strings, but applied to predicate sequences instead of characters.
With decision tree compression, how long can programs be if the compiler compiles Detlog into 6502?
With decision-tree compression, Detlog compiled to 6502 could be much larger:
Comfortable: about 10–40 KB Detlog source logic
Possible with careful tables/overlays: 50–100 KB+ source logic
Resident 6502 code/data at once: still roughly 20–40 KB usable RAM on a 64 KB Apple IIe.
The trick is that repeated clauses like:
a :- common, x1.
b :- common, x2.
c :- common, x3.
do not compile into three full copies. They compile more like:
run common once
branch/table-select x1/x2/x3
reuse output buffers
So the source can be much longer than the resident machine code.
A useful estimate:
Without compression: source × 3–20 expansion
With compression: source × 0.5–3 expansion
Best case: many repeated clauses collapse into tables
Worst case: unique clauses still expand normally
So on Apple IIe:
Tiny runtime/compiler stub: 2–8 KB
Decision tables + code: 10–30 KB
Buffers/stacks/strings: 4–16 KB
Overlay/floppy-loaded chunks: much larger total program
The biggest realistic Detlog programs would be table-heavy grammars, classifiers, menu systems, small adventure games, symbolic transformers, or bounded expert systems.
The key limit becomes not “how long is the source?” but:
How much must be resident at once?
How large are the strings?
How deep are loops/recursion?
How many choicepoints must be remembered?
How much output buffering is needed for splicing?
So the practical answer is:
With decision-tree compression, a Detlog program can feel like tens of KB of logic on a 64 KB Apple IIe, and possibly hundreds of KB if split into floppy-loaded overlays.
Is Detlog the most efficient Apple IIe Prolog?
Potentially, yes in a narrow sense, but it depends on what you mean by “Prolog.”
Traditional Prolog systems on 6502 machines (including Apple II-era implementations) typically support:
- Full unification
- Backtracking
- Choicepoint stacks
- Dynamic search
- Variable bindings and trail management
These features make Prolog expressive, but they consume memory and CPU time.
If Detlog:
- Converts nondeterminism into deterministic loops,
- Eliminates most or all runtime choicepoints,
- Compiles directly to 6502 machine code,
- Uses decision-tree compression,
- Avoids heap allocation inside loops,
- Reuses buffers and tables,
then it could easily outperform a traditional Prolog implementation on an Apple IIe in both speed and memory use.
A rough spectrum is:
System Runtime Cost Expressiveness
BASIC interpreter High Low
Interpreted Prolog Very high Very high
Compiled Prolog Moderate Very high
Deterministic Detlog Low Medium–high
Hand-written 6502 assembly Lowest Depends on programmer
The important caveat is that Detlog’s efficiency comes partly from restricting or transforming classic Prolog behavior. If a program relies heavily on arbitrary unification, open-ended backtracking, or runtime search, then either:
- Detlog cannot compile it directly, or
- The compiler must generate additional machinery, reducing the advantage.
For the kinds of programs you’ve described in relation to Loop2 and PLOP—decision trees, classifiers, CFG/DCG-style parsing, symbolic transformations, specification-to-algorithm generation, and deterministic splicing—Detlog could be among the most efficient Prolog-like systems feasible on an Apple IIe.
In fact, if the compiler can transform:
colour(red).
colour(green).
colour(blue).
into a compact lookup table or decision tree rather than runtime backtracking, the resulting 6502 code is closer to an optimized expert system than a traditional Prolog engine.
So a reasonable conclusion is:
Detlog is unlikely to be the most efficient implementation of full Prolog on an Apple IIe, because full Prolog requires general unification and backtracking. However, it could be one of the most efficient Prolog-derived logic languages for a large class of deterministic and semi-deterministic programs, especially if it combines direct 6502 compilation, decision-tree compression, and elimination of runtime choicepoints.
What "length" of program is possible with decision tree, Loop2 and PLOP compression?
With decision tree + Loop2 + PLOP compression, the practical “length” could be:
Resident on 64 KB Apple IIe:
20–60 KB of effective Detlog logic
With very careful memory layout:
60–150 KB effective logic
With floppy overlays / paged modules:
hundreds of KB, possibly 0.5–1 MB+ total project logic
The key distinction:
Physical 6502 code resident at once: still maybe 10–35 KB
Effective Detlog source represented: much larger
Why? Because the compiler can merge repeated structures:
a :- common, a1.
b :- common, b1.
c :- common, c1.
into something closer to:
run common once
select branch from compressed decision table
run only the differing suffix
reuse buffers
So the expansion changes roughly like this:
Naive Detlog → 6502:
source × 3–20
Decision-tree compression:
source × 0.5–3
Decision tree + Loop2 + PLOP:
source × 0.1–2 in good cases
Best cases are classifiers, grammars, menu trees, symbolic rewrite systems, adventure-game logic, deterministic parsers, and repeated clause families.
Worst cases are programs where every clause is unique, string-heavy, deeply recursive, or requires true Prolog backtracking.
So the answer is:
Physically, the Apple IIe still runs tens of KB at once. Logically, Detlog could represent hundreds of KB of Prolog-like program behaviour if PLOP/Loop2 compress repeated choicepoints into loops, tables, and shared suffix/prefix code.
Top comments (0)