Open jcreedcmu opened 3 months ago
It seems possible (but not certain) that %fquery
might help, see https://delphin.poswolsky.com/publications specifically "Factoring Report"
Chapter 8 of these notes might be relevant to understanding what's going on in twelf's compile.fun
.
Unfortunately, %compile
and %fquery
don't seem to do TCO out of the box:
%use equality/integers.
x : integer -> type.
program : integer -> integer -> integer -> type.
/ : program 0 ACC ACC.
/ : program N ACC OUT <- program (N - 1) (ACC + 1) OUT.
%worlds () (program _ _ _).
%mode (program +N +ACC -M).
%compile program.
%fquery (program 100000 0 X).
on twelf-wasm runs out of memory. However, inspecting the output, we see the functional program pretty-printed:
fun program 0 ACC = <ACC, <>>
| program N ACC = let
val <OUT, <>> = program (~1 + N) (1 + ACC)
in
<OUT, <>>
end
This program is not actually tail-recursive, due to the tupling around the output value OUT
. Possibly a small tweak to the implementation of %compile
might allow real tail-call optimization?
The code responsible for pretty-printing these compiled programs is here in tomegaprint.fun.
tomega.sig has the definition of Prg
, the syntax type for compiled functional programs.
The goal of this issue is to allow a twelf logic program, via FFI, to call
WaitNextEvent
, dispatch onevent->what
, and then call itself again in a loop, until some user choice terminates the loop.It would be nice if we could simply write the loop in a (logic-programming) tail-recursive style, like
However, I'm concerned that
%query
might still keep around enough data to reconstruct a proof term to justify its substitution, which would mean an continual leaking of memory as the predicatetail-rec
iterates.