if I feed this many numbers (by e.g. piping seq 1 100000 && echo "" to my Z-machine interpreter) it runs through all of the input and then prints the termination message.
Now if I try to expand this into a recursive call instead, like so:
it only runs for 328 iterations, and then just stops. At first I thought the 329th $Number for some reason unified with the empty input, but that doesn’t seem to be the case either, because the terminating message is never printed. So it’s more like the (get-input $) query fails after so many iterations.
I thought that maybe it’s because the bracketed (or) clause creates a bunch of choice points it needs to keep track of and eventually it runs out of some resource. Accordingly, I tried inserting (just) at the top of the query to discard any previous choice points – that should make the query tail recursive, if I think about this right. Just to be sure, I’ve inserted (just) all over the place, and nothing seems to have an effect.
It also stops on the same iteration count both when compiling to z5 and z8.
What am I misunderstanding about the Dialog execution model? Is *(repeat forever) the only way to achieve iteration beyond just few steps?
I don’t know the exact answer to why it stops after that particular number of recursions, but the manual does say this:
Tail-call optimization is backend-dependent. This means that infinite loops must be implemented using (repeat forever). If they are implemented using recursion, some memory might leak with every iteration, and the program will eventually crash.
Aha! That was quick. A more complex program fails after a fewer number of iterations, so the exact number of iterations is probably a matter of resource exhaustion. When reading the manual I had appartenly skipped over the chapter named “memory footprint” because I didn’t expect my tiny toys to have memory problems…
Aha, so it’s the main heap, not the aux heap. In that case, it sounds like the problem is that all the $Number variables are sticking around between iterations.
Now I’m curious. Isn’t that weird? How would I confirm? Is there anything I can do in my code to prevent that from happening, or is this something that needs to go into the compiler?
Variables are first class things in Dialog, they exist in memory similar to how a list cell exists in memory, and continue to exist even after a query has returned.
This is different to languages like C, C++, Rust where a variable is usually part of the stack frame, and once a function returns that variable no longer exists.
There isn’t anything you can do about it, except use an algorithm that minimizes creation of variables.
I don’t believe this can be true – then almost no game would work. Surely tens of (temporary) variables are used in the execution of a single turn in any reasonably sized games. It would be unreasonable that a new space of memory is allocated for each, in order for them to stick around after the query has returned.
Either, it seems to me, you’re talking about global variables (which aren’t used in the crashing example) or you’re referring to variables belonging to queries that have not yet returned, which would be the case when tail calls aren’t optimised.
The latter seems like the most reasonable interpretation of your comment, but then Draconis suggests that would present itself as an exhaustion of the aux heap, not the main heap. So I remain confused!
Dialog does something very clever: once everything returns to the main loop (i.e. the player is entering their next command), all the variables and list cells created while handling the last input can simply be deleted. It is a stack which gets reset (emptied) on each loop.
That only complication with that: when you store variables or lists in a global variable. Normal variables can just be dereferenced (store their value instead). List cells need to be copied to the long-term heap.
This stack-clearing happens every time a query succeeds or fails, which is why (repeat forever) is so useful: it gives you an infinite supply of choice points to jump back to and clear the stack. It looks like the stack-clearing doesn’t necessarily happen on a tail call, is the key thing.
Which might be a bug—after all, the point of a tail call is that you can’t get back to the parent function afterward, so there’s no reason to keep the variables around. But the manual does say that you shouldn’t rely on tail-call optimization for infinite loops anyway.
For an interpreter, I’m guessing it wouldn’t be too hard to support tail-call optimisation. Clearing the allocations on the heap (stack) is already done as a part of popping the choice point stack, so that same logic could be reused for tail calls.
Yeah, I suspect the reason it’s currently not done is because variables could be passed to the child function in the tail call, and resetting the stack is an all-or-nothing proposition. But Dialog’s optimizer should be good enough to detect when no variables from the parent function are involved in the tail call, and reset the stack when that happens.
After a bit more thought, though, I’m not sure if this is an optimization worth making. Generally the reason for tail recursion is to break a problem down into smaller pieces, which means variables have to survive between calls. The main reason to do tail recursion without passing any variables is to create an infinite loop—but this will break in the debugger, which doesn’t do tail call optimization. So I’m not sure this optimization will see much use.
That’s basically what I’m wondering. If you’re not keeping any variables between tail calls, it seems like (repeat forever) will pretty much always be better.
The main place it doesn’t work is when you want to get input, process it, then make one of a dozen different tail calls depending on that input, maybe for something like a state machine. But in that case, you can stash the input on the long-term heap, then make the tail call after backtracking to free memory—the standard library actually uses this trick during disambiguation.
(The long-term heap turns out to be a very useful device for when you need to break the rules of Dialog’s control-flow model!)