Iterating through two lists in order simultaneously non-recursively

Authoring Dialog
1

Let’s say I have two lists and I want to iterate through each of their elements up to the end of the shorter list, like this Python (the actual actions performed within the loop are not important here):

for i in range(min(len(list1), len(list2)):
    print(str(list1[i]) + str(list2[i]))

This is, of course, possible in Dialog with with recursion and partial lists:

(print [] $)
(print $ [])
(print [$Head1 | $Tail1] [$Head1 | $Tail1])
    $Head1(no space)$Head2(line)
    (print $Tail1 $Tail2)

But this is also not great in terms of heap usage, at least for the particular “real” logic I have in my project. I have had issues with running out of heap space and I would very much like for that not to be a concern. Does the language support doing the same thing in backtracking? Something like this, of course, behaves like nested for loops rather than a single one:

(exhaust) {
    *($Element1 is one of $List1)
    *($Element2 is one of $List2)
    $Element1(no space)$Element2(line)    
}

I haven’t been able to work out a solution to this, but maybe there’s something I missed in the documentation.

2

I don’t know of a way without using recursion. You could kind of hack around it with global variables:

(now) (global list $Start)
(stoppable) {
    *(repeat forever)
    (global list $List)
    (if) (empty $List) (then) (stop) (endif)
    ($List = [$Head | $Tail])
    do something with $Head
    (now) (global list $Tail)
    (fail)
}

(Showing only one list here, but this is easily extended to any number.)

But in general, Dialog expects you’ll handle this with recursion. I’d recommend other tricks to save heap space first, since this global variable hackery will be quite slow. The values of global variables are stored on a heap (a real heap, unlike the standard Dialog “heap”) that gets shuffled around as needed to coalesce empty blocks of memory, so storing to it multiple times per iteration gets messy.

3

In principle, your original example is tail-recursive.

In practice, Dialog should be a lot better at detecting and loopifying tail recursion than it currently is. Your original code is the correct pattern, and a modern optimizing compiler should take one look at it and produce iterative loop code.

2 Likes
4

What other tricks would you have in mind? The documentation (Language Chapter 9, section Memory Footprint; I apparently am not allowed to post links) only seems to note switching to global variables (from object variables), backtracking, and tail recursion. And if the tail recursion isn’t being properly detected (which certainly seems to be the case given the heap usage I am seeing) I’m not sure what else to do here without having actual control over freeing heap allocations (which does not appear to be a language feature).

5

What version of the Dialog compiler are you using? 0m/03 had some issues with per-object variables and heap space usage (see this thread: Heap space exhausted - solution and why ), so if your program uses a lot of those, and you’re using a version of Dialog earlier than 1a/01, the first thing to try is updating the compiler. You might also take a look at this thread: Heap space exhausted: What do you do now? , where @Draconis has laid out a number of optimizations not mentioned in the documentation.

6

So! Warning, this will be a bit of a long post.

Dialog’s “heap” isn’t actually a heap, in the data-structure sense. It doesn’t let you allocate and deallocate arbitrary blocks; it’s just a big chunk of memory that keeps a pointer to its current endpoint (the “top” pointer). Whenever something needs to get stored on the heap (a list, an unrecognized dictionary word, even just a local variable), it’s stored at the current top, then the top is increased past it. (Much more like a stack than a heap, really.)

So how do heap blocks get deallocated? Well, they mostly just…don’t. Whenever a choice point or stop point is created, the top pointer is saved as part of it; whenever Dialog backtracks to that choice point or stop point, the top pointer is reset to that value (so everything beyond that value is lost to the void). This is the only way the heap can shrink, ever. (This is how it’s unlike a stack; you can’t pop individual things off it.)

Separate from this, Dialog has two proper stacks, which live in the aux heap. The aux stack is used to store intermediate values that need to survive backtracking, for things like (collect $); it grows up from the bottom of the aux heap. The trail stack is basically just a call stack, and it grows down from the top of the aux heap. (If they ever meet in the middle, the game crashes.)

Dialog is actually quite good at recognizing and optimizing tail recursion! But…its tail recursion optimization is entirely focused on the aux stack and trail stack. If you try to recurse too deeply without tail recursion, you’ll exhaust the aux heap, because it needs to make a new call record for each query. Tail recursion avoids this by reusing the same call record, but…that doesn’t help with exhausting the main heap. If you make any lists, unbound variables, and so on, those will accumulate on the heap over and over until you backtrack.

So, how do we fix this? In the short term, the only way to get heap memory back is to backtrack, so you’re going to need to backtrack. If there’s some expensive computation where you need the side effects (printing, setting flags, etc) but not the actual result (the local variables it binds), you can backtrack after doing it and free all that heap memory:

{
    (really expensive computation $X $Y $Z) (fail)
    (or)
    %% succeed
}

(Fun fact: this is exactly equivalent to (exhaust) (really expensive computation $X $Y $Z). You can use that syntactic sugar if you prefer.)

You can also store the result of your expensive computation in a global and then (stop). The standard library uses tricks like this to make sure that there’s always backtracking before running the whole parser machinery, since that uses a whole lot of heap space.

In the long term…well, ideally, when Dialog detected tail recursion, it would somehow optimize the main heap usage as well as the aux heap usage. The problem is, I have no idea how to do that! Consider this block of code from the standard library, which reverses a list:

(reverse $Input $Output)
	(reverse-sub $Input $Output [])

(reverse-sub [] $Output $Output)
(reverse-sub [$Head | $Tail] $Output $SoFar)
	(reverse-sub $Tail $Output [$Head | $SoFar])

This seems like it should clearly be tail-recursive, right? But [$Head | $SoFar] means creating a cons cell on the heap, and the current architecture offers no way to clear the rest of the variables off the heap while preserving this one.

It’s a thorny problem! Someone messaged yesterday saying they’d built an Å-machine interpreter in Go that could handle this sort of tail recursion optimization, but I don’t know how that works; we’ll have to wait and see when it’s released. If other people have ideas, though, please let me know; heap usage is one of Dialog’s biggest weaknesses right now, and I would love to improve it.

2 Likes