You may remember that the Z-machine only supports 16-bit integers, and that the puzzle input for the first day of 2024 used numbers sized around 75,000, which do not fit into 16 bits. We implemented long integer arithmetic on our own for Inform 6, which was greatly helped by having the 16-bit integers in the Z-machine, meaning we could comfortably store intermediate values without losing carry bits.

Imagine my shock when I read in the Dialog manual that

All numbers in Dialog are restricted to the range 0–16383 (inclusive).

Granted, this is still enough to implement long integer arithmetic, but! Dialog does also not have any bitwise operators, nor does it support emitting Z-machine opcodes directly. The manual goes on to explain that

developers that require more sophisticated number crunching will have to get creative.

You don’t say.

At the time I was learning the language I didn’t have the level of creativity in me to implement long integer arithmetic under those constraints. So I skipped past the first day, and went straight for the second day.

Dialog is different from many other programming languages, so we’ll have to start slow. In Dialog, the subroutine is not the fundamental unit of abstraction. Instead, the query is. The main difference is that whereas a subroutine typically

• Has a name,
• Takes arguments,
• Can perform side effects, and
• Returns a value.

queries instead

• Are identified by words,
• Can unify variables with values in both directions,
• Can perform side effects, and
• Always result in either failure or success.

The latter point is important, because it determines how execution flows in a Dialog program. Failure in Dialog does not mean something bad happened – it is a normal way to stop executing a query.

When a Dialog program starts up, it always starts by evaluating the query called (program entry point). The (program entry point) query must be defined by us, and we define a query by writing its name. The simplest way to define the entry point query would be to compile the following complete program:

(program entry point)

This is a query identified by the words program entry point. Because it has no query body, it always suceeds. We could make it always fail by giving it a body like

(program entry point)
  (1 = 2)

The sub-query (1 = 2) succeeds if one is equal to two, and fails otherwise. Since one is not equal to two, it will always fail, meaning our program, when defined like that, will always fail. Since failure is counted as a normal way to terminate execution, this failure will not be visible to the user – the program simply stops.

If we write plain text in the body of a query, that is taken to be a print statement query. A print statement query always suceeds. Thus the following program will print a customary message and then suceed.

(program entry point)
  Hello, world!

If we instead wanted it to fail, we could add a failing query to the end of the main query body. We used the failing query (1 = 2), before, but a convenient equivalent is (fail), a query that always fails.

(program entry point)
  Hello, world!
  (fail)

This would run the first sub-query, which prints a message, and when the second query fails, the main query would also fail. This highlights a key principle of how Dialog programs run: when a query is evaluated, it evaluates all sub-queries in sequence, and fails when any of them fail.

Now, perhaps, we can ask the user for a sequence of numbers.

(program entry point)
  Please enter a sequence of numbers:
  (line)
  (get input $Report)
  Aha, you are interested in $Report!

The program above defines the main query (program entry point) in terms of four sub-queries:

1. First a print statement to print a prompt.
2. Then comes a query called (line). This is built into the Dialog language and causes a newline to be printed.3³ Roughly speaking – Dialog applies some intelligence to things that are printed.
3. We have the query (get input $Report). This pauses execution and waits for the user to type stuff. If the user types space-separated numbers, Dialog will create a list of numbers and assign that list into the variable $Report.
4. Finally, we have another print statement, where we display the list back to the user.4⁴ Dialog applies some debug formatting to be able to print lists.

As long as the user types something at the prompt, none of these queries can fail. That means whenever the program runs, Dialog will evaluate all four sub-queries in turn. The results are predictable:

Please enter a sequence of numbers:
6 8 19
Aha, you are interested in [6 8 19]!

or

Please enter a sequence of numbers:
87 44 hammock
Aha, you are interested in [87 44 hammock]!

or

Please enter a sequence of numbers:

Aha, you are interested in []!

Dialog does not enforce that the user types numbers, but if the user types numbers, the program will get a list of numbers rather than a list of dictionary words, which is the string-like type in Dialog.

We’ll eventually want to do more complicated processing on the sequence we get from the user, but to take it step by step, let’s determine whether the first number the user typed is greater than three.

We’ll make a new query for this. In Dialog, queries are identified with words, but they can have variable names interspersed between any of the words. This means we could create a query called (does $List have a large first number?) where the variable $List representing the parameter comes early on in the definition. Here’s the full definition of such a query.

(does $List have a large first number?)
  ($List = [$First | $Rest])
  ($First > 3)

In order for this query to succeed, both of its subqueries must succeed. In other words, it must be able to

1. decompose $List into a $First element and the $Rest of the list; and
2. the $First element must be a number greater than three.

If either of those two sub-queries fail, then the entire (does $List have a large first number?) query will fail.

When we insert a call to the large-number query in our main program, it will either allow the main program to continue to execute (if the large-number query succeeds), or halt execution of the main program (if the large-number query fails). Thus, we can use it to conditionally print a message:

(program entry point)
  Please enter a sequence of numbers:
  (line)
  (get input $Report)
  Aha, you are interested in $Report!
  (line)
  (does $Report have a large first number?)
  The first number is indeed large!

What actually happens when Dialog encounters a call to a query is that it matches the name of the query word-for-word with all other queries we have defined. If any of the words in the query are variables (i.e. start with a dollar sign) and are currently unassigned, Dialog is allowed to assign them a value to make the query match. This process is called unification. In this case, the $Report variable is bound to a list, but the $List variable inside the query is unassigned, so Dialog assigns the value of $Report into $List to make the query match its definition. Then execution of the sub-query takes place.

We defined the query using a verbose name to illustrate how Dialog tries to match the name and assigns values to variables to make it match exactly, but we can use shorter query names. I’m a programmer, so I’d prefer to define our query as

(first-large? $List)
  ($List = [$First | $Rest])
  ($First > 3)

using the much shorter, Ruby-inspired name first-large?. We can also decompose the argument list in the query declaration directly, instead of with a subquery. It’s the same thing.

(first-large? [$First | $Rest])
  ($First > 3)

This will produce the expected effect.

Please enter a sequence of numbers:
5 8 3
Aha, you are interested in [5 8 3]!
The first number is indeed large!

and

Please enter a sequence of numbers:
1 8 2
Aha, you are interested in [1 8 2]!

It’s a little annoying that it doesn’t print anything when the first number is small. We’ll see if we can fix that.

So far, we have only seen queries that succeed if all of their subqueries succeed. We can get the effect of conditional execution by defining the same query multiple times. Here, we have split out the printing of the message into a large-feedback query.

(program entry point)
  Please enter a sequence of numbers:
  (line)
  (get input $Report)
  Aha, you are interested in $Report!
  (line)
  (large-feedback $Report)

(large-feedback $List)
  (first-large? $List)
  The first number is indeed large!

(large-feedback $List)
  Sorry, the first number seems small.

(first-large? [$First | $Rest])
  ($First > 3)

You’ll note that there are now two queries with the same declaration. When there are multiple queries that match, Dialog sets up a choice point before executing the first matching query. If that query fails, Dialog will roll back any changes it made during its execution, and execute the next matching query instead. In our program above, that means it will try the first large-feedback query, which fails if the first number is small, and then go on to try the second large-feedback query. The effect is printing different messages whether the first number is large or small.

If we don’t want to split up this definition, there’s a control flow primitive in Dialog called (or) which sets up such a choice point inside a query. To use that, we’d write the large-feedback query with one query body:

(large-feedback $List)
  (first-large? $List)
  The first number is indeed large!
  (or)
  Sorry, the first number seems small.

Although (or) looks like a query, it’s the syntax for a control flow primitive in Dialog. When a query is defined with (or), Dialog first executes the queries above the (or) as normal, but if any of them fail, it restores to the start of execution of that query, and runs the queries below the (or) instead.

In the above case, this has the desired effect: if the first number is large, it will get to the relevant print statement, and then the large-feedback query is considered successful. In contrast, if the first-large? query fails, the (or) construct will move execution over to its other side, and print the consolitory message.

The (or) construct is inconvenient in that it considers everything above it as one branch, and everything below it as another branch. We can limit its scope with curly braces, as here:

(program entry point)
  Please enter a sequence of numbers:
  (line)
  (get input $Report)
  Aha, you are interested in $Report!
  (line)
  {
    (first-large? $Report)
    The first number is indeed large!
  (or)
    Sorry, the first number seems small.
  }

(first-large? [$First | $Rest])
  ($First > 3)

This kind of conditional execution is so common that Dialog has syntactic sugar for it to make it look more like other programming languages. We could instead have written e.g.

(program entry point)
  Please enter a sequence of numbers:
  (line)
  (get input $Report)
  Aha, you are interested in $Report!
  (line)
  (if) ($Report = [$First | $]) ($First > 3) (then)
    The first number is indeed large!
  (else)
    Sorry, the first number seems small.
  (endif)

This is desugared to almost the same thing.5⁵ The difference is that further failures in the (then) branch won’t toss execution over to the (else) branch. In these notes, I will try to stick to the more primitive constructs rather than syntax sugar, to communicate more clearly that what happens under the hood are queries executing until one fails, then Dialog backtracks and tries the other alternative.

Now that we have that in place, let’s construct a more complicated query on the report. Instead of seeing whether the first number is large, let’s see if the entire sequence is increasing. Our query that checks if a sequence is increasing will do so by running another query that checks if the rest of the sequence is increasing, given the first number.

(sequence-increasing? [$First | $Rest])
  (sequence-increasing-from? $Rest $First)

(sequence-increasing-from? [$First | $Rest] $Previous)
  ($First > $Previous)
  (sequence-increasing-from? $Rest $First)

If we plop this down in our main query instead of the first-large? query, we’ll find that it judges all sequences as not increasing. The reason is that given the input, say, [4, 6, 9], it will eventually try to run the query

(sequence-increasing-from? [] 9)

and this does not match any queries we have defined, so it fails.6⁶ The functional programmers in the crowd will recognise this as recursion with a missing base case. And when it fails, the failure falls through to the top level. We can easily fix this by defining that query to always be a success:

(sequence-increasing? [$First | $Rest])
  (sequence-increasing-from? $Rest $First)

(sequence-increasing-from? [] $)
(sequence-increasing-from? [$First | $Rest] $Previous)
  ($First > $Previous)
  (sequence-increasing-from? $Rest $First)

The empty dollar sign is a wildcard variable, indicating we want the query to succeed for all values of that variable. With this addition, the program works. It does judge the empty input as “not increasing” but that’s probably fine.

To solve the second day’s Advent of Code problem, we will also want to check if a sequence is decreasing. We could copy-paste the above queries and update the operator used, but we could also think of it as an opportunity for abstraction. First, we modify the queries to take a parameter that indicates the criterion on which the sequence should be evaluated.

(sequence-satisfies? $Condition [$First | $Rest])
  (sequence-satisfies-from? $Condition $Rest $First)

(sequence-satisfies-from? $Condition [] $)
(sequence-satisfies-from? $Condition [$First | $Rest] $Previous)
  (compare-by $Condition $First $Previous)
  (sequence-satisfies-from? $Condition $Rest $First)

What we have done here is add another variable which indicates by which condition the sequence should be evaluated. We have also changed the explicit comparison ($First > $Previous) to a compare-by query that takes a condition and two values and compares by that condition.

When we call this query, we need to pass it a value indicating by which condition we want to compare. We could pass it a plain number (and decide on a convention that e.g. 0 means increasing, 1 means decreasing, etc.) but it’s more readable if we use a symbol.7⁷ Actually, they are not called symbols in Dialog, but objects. That seems very confusing to me. They have no properties and no methods! They are plain symbols. I’m sure the compiler translates them to a number, too. These are words prefixed by hash signs. Thus, the call to the new query would look like:

{
  (sequence-satisfies? #increasing $Report)
  Yup, increasing.
(or)
  Sorry, not increasing.
}

In order for this to work, we also have to define the compare-by query, so we’ll do that.

(compare-by #increasing $A $B)
  ($A > $B)

With this, we get the expected result.

To support checking if a sequence is decreasing, we only have to implement that compare-by operation.

(compare-by #decreasing $A $B)
  ($A < $B)

We can also add the compare-by operation to determine whether a sequence only consists of small steps.

(compare-by #small-stepped $A $B)
  ($A < $B)
  (compare-by #small-stepped $B $A)

(compare-by #small-stepped $A $B)
  ($A minus $B into $Difference)
  ($Difference < 4)

This looks weird because Dialog isn’t very strong at maths. Dialog doesn’t have negative numbers, so we have to make sure we are subtracting in the right order. If $A is smaller than $B, we swap them before performing the computation.

The Advent of Code puzzle asks us to determine which reports are safe, where safety is determined by the sequence being small-stepped and being either increasing or decreasing. We have what we need to determine that for a single sequence now.

(program entry point)
  Please enter a sequence of numbers: (line)
  (get input $Report)
  {
    (report-safe? $Report)
    The report is safe.
  (or)
    Sorry, that report is unsafe.
  }

(report-safe? $Report)
  (sequence-satisfies? #small-stepped $Report)
  (sequence-monotonic? $Report)

(sequence-monotonic? $Report)
  (sequence-satisfies? #increasing $Report)

(sequence-monotonic? $Report)
  (sequence-satisfies? #decreasing $Report)

We have a separate query for determining whether the report is increasing or decreasing because we want Dialog to try both. But we can apply a trick to simplify the code. We know that Dialog creates a choice point if we have a block with an (or) query, so we can use that to try both directions.

(report-safe? $Report)
  (sequence-satisfies? #small-stepped $Report)
  { ($Direction = #increasing) (or) ($Direction = #decreasing) }
  (sequence-satisfies? $Direction $Report)

When Dialog runs this query, it will first assign #increasing to $Direction, because it has not yet seen anything that contradicts this choice. It will then go through the sequence-satisfies? #increasing query. If that query fails, Dialog takes that to mean that there is evidence that contradicts $Direction being #increasing. So Dialog rolls back to the choice point created by the (or) construct, and runs the rest of the query again except with $Direction set to #decreasing. If that also fails, then the entire report-safe? query fails. But if it succeeds, the report-safe? query also succeeds.

This way of writing it would be unnecessarily verbose if we had many directions. There is a query built in to Dialog called ($ is one of $). That query succeeds if the first argument is a member of the list in the second argument. If the first argument is an unbound variable, then Dialog will do its thing where it assigns a value to the first argument to make the query succeed. In practice, that means Dialog assigns one of the values of the list to the variable.

We might imagine we could use this query as such:

(report-safe? $Report)
  (sequence-satisfies? #small-stepped $Report)
  ($Direction is one of [#increasing #decreasing])
  (sequence-satisfies? $Direction $Report)

but this would not work as we want it to. The problem is that Dialog does not insert a choice point before the is one of query, so it will never be able to backtrack to try multiple assignments for the $Direction variable. There is a special little syntax we can use to get Dialog to insert a choice point before that query. See if you spot it!

(report-safe? $Report)
  (sequence-satisfies? #small-stepped $Report)
  *($Direction is one of [#increasing #decreasing])
  (sequence-satisfies? $Direction $Report)

The asterisk turns the query into a multi-query, which means Dialog creates a choice point before running the query, and then if any of the subsequent queries fail, it backtracks and tries a new way to unify the query. If the subsequent queries succeed, the overall query evaluation succeeds and the choice point is discarded.

At this point, we can use tail recursion to evaluate multiple reports.

(program entry point)
  (read-and-evaluate-reports)

(read-and-evaluate-reports)
  (get input $Report)
  (if) ~($Report = []) (then)
    (evaluate-safety $Report)
    (read-and-evaluate-reports)
  (endif)

(evaluate-safety $Report)
  (report-safe? $Report)
  The report $Report is safe. (line)
  (or)
  Sorry, the report $Report is unsafe. (line)

If we run this with the test input in the second day’s problem, it answers correctly.

The report [7 6 4 2 1] is safe.
Sorry, the report [1 2 7 8 9] is unsafe.
Sorry, the report [9 7 6 2 1] is unsafe.
Sorry, the report [1 3 2 4 5] is unsafe.
Sorry, the report [8 6 4 4 1] is unsafe.
The report [1 3 6 7 9] is safe.

However, if we run this on the full input, it just … stops after a while, as if the read-and-evaluate-reports query fails – and this shouldn’t be possible given how it’s written!

Hidden in the last chapter of the Dialog manual, under the section Some notes on performance, subsection Memory footprint, we find the remark

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.

The problem seems to be that we run out of memory!8⁸ We can install an error handler in our Dialog code that receives runtime error codes. This confirms the memory problem. As the manual alludes to, there is a special query built into the language which always succeeds, and it’s called (repeat forever). The way we normally use it is as a multi-query, meaning it will be re-tried over and over as long as any of the subsequent queries fail. Here it is in context.

(read-and-evaluate-reports)
  *(repeat forever)
  (get input $Report)
  {
    ($Report = [])
  (or)
    (evaluate-safety $Report)
    (fail)
  }

We need the explicit failure call at the end, because Dialog will only backtrack to the choice point established by the multi-query if the subsequent queries fail. When the input is empty, we don’t fail the query, because then we do want to break out of the query successfully.

However, having turned the iteration into an actual loop, we can not explicitly accumulate a count of safe reports, which would have been my initial plan. What we’ll do instead is use a global variable to keep track of that.

(global variable (safe-reports 0))
(read-and-evaluate-reports $Count)
  *(repeat forever)
  (get input $Report)
  {
    ($Report = [])
    (safe-reports $Count)
  (or)
    (report-safe? $Report)
    (safe-reports $Previous)
    ($Previous plus 1 into $Next)
    (now) (safe-reports $Next)
    (fail)
  }

A global variable is like a query definition except that it is allowed to change when the program runs. At the program start, we have a query defined as (safe-reports 0). When the program queries for e.g. (safe-reports $Previous), and the $Previous variable is unassigned, it will assign 0 to $Previous in order to unify the queries – typical Dialog evaluation. This is how we can read global variables.

Because we have declared that query as a global variable, we are also allowed to run something like (now) (safe-reports 5). This will re-define the query to (safe-reports 5), rather than (safe-reports 0). The (now) directive is what allows us to replace query definitions during program run-time. We use this in the (read-and-evaluate-reports) query to increment the count of safe reports seen.

Running this on the full test input, it actually gives us the correct answer!9⁹ Just like with Prolog, I’m always a little surprised when a Dialog program Just Works™.

The twist for the second half of the second day’s problem is that we should consider reports safe also if we can produce a safe report by excluding one of the numbers in the report. This would have taken too much time for me to implement in Inform 6, but it is a natural fit for Dialog!

I can imagine two ways of doing it. We could modify the sequence-satisfies? query to try skipping over one item at each step, and returning successfully if any of those attempts are successful. If we want to keep our sequence-satisfies? unchanged, we could instead first generate all equivalent sequences (i.e. sequences missing one item), and then test all of those for safety.

I selected the latter approach. This is a query that generates all equivalent reports, i.e. it takes a report and gives back all reports that result from excluding one number from it.

(report-equivalent [$First | $Rest] $Result)
  *(report-equivalent $Rest $More)
  ($Result = [$First | $More])
  (or)
  ($Result = $Rest)

I wrote this. It was actually easy to write. I just typed out the things I felt should be there. But I cannot for the life of me explain how it works.10¹⁰ This happens when I write Prolog code too. My intuition for it is that we get all equivalent reports constructed from the rest of the numbers in this report and tack on the first number to them. Then when we have exhausted those, we also return the equivalent report we get from excluding the first number.

We can test this by creating a temporary entry point query that overrides the real one.

(program entry point)
  (get input $Report)
  *(report-equivalent $Report $Equivalent)
  We got an equivalent $Equivalent (line)
  (fail)

The multi-query continues to extract equivalents as long as the main query fails, which is always does thanks to the (fail) call. When given the input 1 2 3 4 this will print

We got an equivalent [1 2 3]
We got an equivalent [1 2 4]
We got an equivalent [1 3 4]
We got an equivalent [2 3 4]

That’s exactly what we want! We’ll add a new query

(report-with-equivalents-safe? $Report)
  (report-safe? $Report)
  (or)
  *(report-equivalent $Report $Equivalent)
  (report-safe? $Equivalent)

which, if the report is not safe on its own, tests the safety of all equivalent reports. We call this in the main query instead of directly calling report-safe?. When fed the full input, it again returns the correct answer!