Advent of Code in Polar

What is Polar

The oso policy language, Polar, is designed to be good for writing authorization policies. Many of the choices made optimize for that use case. Things like its logic-based nature, pattern-matching specializers and how easy it is to interoperate with the host language's objects are all meant to make it easy to write policies over your existing data to make authorization decisions. But Polar isn't just for authorization, it's actually a fully general purpose language, a close relative of Prolog, and should be powerful enough for any computing task.

It's a good exercise to try and write programs in Polar that are more complicated than your average authorization rule set. Previously we even implemented an entire game in Polar. Using Polar in new and different ways teaches us a lot about the language and its rough edges.

Why advent of code

Advent of code is a fun series of programming puzzles that are published every day from December 1st to December 25th. I've been a big fan of advent of code for a while and it has been a tool I've used to get better at programming. It's especially useful to me to try out a new language I'm learning. I did advent of code in Rust a few years ago when I was just getting started, and it really helped accelerate how fast I got the hang of things having to solve a bunch of different kinds of problems. I thought that this year I could do the same thing for Polar, and use advent of code to really see what it could do.

I have to admit I haven't finished all the problems yet but I've learned a ton about Polar, both good and bad in the process. I've clarified to myself a bunch of patterns that show up when writing Polar programs, found some rough edges in the language that we can clean up, and come up with some features that could help Polar in the future.

Common Programming Patterns With Polar

Loops and Recursion

Many times when solving a problem you need to iterate over a data structure. In the cases where this came up in advent of code it was usually a list. Polar has three ways to deal with lists: in, forall, and recursion.

in is an operator that binds a variable to every member of a list. It can be used for membership checks, and can be combined with another expression to make a filter: x in [1,2,3] and x >= 2.

forall is an operator that succeeds if everything within it succeeds. forall is usually combined with in to check if a condition is true for every element in a list: forall(x in [1,2,3], x < 10).

If however you need to process a list element by element and combine the values in some way, you need to use list destructuring and recursion. We can do that with rules that match on a list with a rest variable. The [first, *rest] specializer matches a list and binds the first element to first and the rest of the list to rest.

Lets say you have a list of numbers and you want to sum them. There are two ways you can write this in Polar. This first way recursively goes down the list until it hits the base case (the empty list []) and then builds back up the answer.

sum([], 0);
sum([first, *rest], ans) if
   sum(rest, rest_ans) and
   ans = rest_ans + first;

The other way to write it is like this:

sum([], ans, ans);
sum([first, *rest], prev_ans, ans) if
   this_ans = first + prev_ans and
   sum(rest, this_ans, ans);
sum(lst, ans) if sum(lst, 0, ans);

The differences here are subtle but important. In the first example you recurse down to the base case and then build up the result. In the second example you pass the intermediate result down to the next level and then bind the result var once you hit the base case.

The first one seems like it's a little simpler (it's less lines of code after all) but the second one should actually be preferred. It's an iterative recursive algorithm and can be thought of as a loop. The recursive call is the last thing in the rule which makes this a tail call and we can optimize this kind of recursion so that the stack doesn't grow. We are planning to implement this kind of optimization and have an issue that you can vote on if it's import to your use cases.

Blowing the stack was something that happened a lot in my work on these problems. Tail call optimizations are something we need to add and when we do the second example will work even on very large arrays.

Another thing this pattern shows is how you can set up a recursive rule with two definitions: one that's the base case, and one that's the recursive case. Being able to lay these out with specializers I think makes it easy to see what's happening. When you have to add intermediate values to your recursive rules you can simply wrap the whole thing in a helper that sets up the default values and calls it directly for a list.

Function Calls

Polar rules don't work the same as functions in other languages. There is no return value; they simply specify relationships between variables and the rule succeeds or it doesn't. Sometimes (lots of times) you want to calculate something with a rule and get an answer out. In these cases you can use a function call pattern.

add(a, b, answer) if answer = a + b;

You can simply pass another variable to a rule that will get bound to the result. This is something you get very comfortable with after writing Polar for a while, but can be confusing the first time you see logic programming.

Helper functions

Polar doesn't have a lot of builtin functions for operating on values. Lots of the power of Polar is that you can easily use host language objects and methods. For some problems if I needed something like a math function that wasn't defined in Polar I could easily set up a helper class with that method from Python and use it in Polar.

class Lib:
   @staticmethod
   def cos(f):
       return Math.cos(f);

oso.register_constant(Lib, "Lib")
cos(f, ans) if ans = Lib.cos(f);

Inline Queries

Polar has syntax for specifying an inline query, which is run when a Polar file is loaded and will throw an error if it doesn't succeed. I used these extensively for unit tests when doing advent of code problems.

add(a, b, ans) if ans = a + b;

?=add(1,2,3);
?=not add(1,2,4);

If / Else

A Polar rule either succeeds, or it fails. If it fails, it backtracks and doesn't evaluate any more terms in the current branch. But sometimes you want to check if some condition is true, and do one thing if it is and another if it isn't. In most languages this would be an if / else branch. In polar you can do an equivalent thing with or and cut. The or sets up a choice point and the cut eliminates the untaken branch.

(
   check_something() and
       then_block() and cut
) or (else_block());

Case / Match statements

Sometimes you have a value and you want to do different things depending on what the value is. In other languages this could be a switch statement, a match statement or even a big chain of if / else if/ else blocks. In Polar the best way to do these are with individual rules and specializers. This came up a lot in advent of code (as you'll see soon) and results in some really nice looking code.

Places where Polar was a great fit

Day 4 was one of my favorites to write in Polar. It's a great fit for the language. I had a list of inputs and a list of rules the inputs had to satisfy to be valid. This is very similar to a policy so I could write out the rules in Polar and evaluate them.

https://gist.github.com/saolsen/114e4a8fca950cf143ff1924f13629a3

Day 8 was my favorite of them all. I had to implement a little virtual machine. This included many of the patterns I spoke about above: using helpers from Python (in this case list indexing), the if/  else block pattern, and having rules for the individual operations:

op("acc", arg, acc, i, next_acc, next_i) if next_i = i+1 and next_acc = acc+arg;
op("jmp", arg, acc, i, acc, next_i) if next_i = i+arg;
op("nop", _, acc, i, acc, next_i) if next_i = i+1;

The best part of day 8 was on part two where I had to take the program (the input) and find a version where a single instruction was swapped to a different one that made the program terminate. Without the swap the program will enter into an infinite loop. In Polar I can simply evaluate the program as usual but when I hit one of the swappable instructions, evaluate it swapped and not swapped. If I detect that that the program is looping, the query fails (and backtracks) and this way I can search the whole state of possible programs.

https://gist.github.com/saolsen/df640e94933ead78da501da175249194

Places where Polar was a bad fit

There were also some rough edges I hit.

Counting successes

A Polar rule either succeeds or fails. In a lot of cases I wanted to count the number of successes of a rule. For instance in a list of items, how many of them pass a rule? We have forall to see if all of them succeed, but no way to see how many succeed right now. You have to recurse over the list yourself and count as you go. There are some Prolog predicates that exist for this kind of thing ( bagof / setof / findall ) that we might consider adding to Polar.

List operations

There are many things you might want to do with lists that aren't built in. The only real built-in tool that you have is destructuring, which lets you pull items off the head and place items onto the head of lists. These operations are based on Lisp-style cons cells, where those are the only efficient operations. All other operations, like appending lists together, getting the nth element, or counting the length, etc have to be done with recursive rules, which adds to the complexity of the algorithm.  Polar represents lists internally as Rust vectors, not cons cells, so we could add builtins for other operations like getting the length, or appending to the end, or pulling out slices. There were many different days where any or all of these would have been useful, but I had to implement them as helpers in Python.

Large searches

Our defaults for stack size limit and timeouts for running a query are set small because authorization decisions are done inline when using oso and they need to stay fast or they'll slow down your app. For other problems like searching a large state space for some solution, it would be nice to raise those limits at runtime. Right now they're constants, but we might make them configurable in the future so Polar can handle other workloads like advent of code problems.

Phew

All in all it was a great exercise in using Polar. Experiments like this are a great help to keep us pushing Polar to be a great language to use for authorization and more! We have created some issues to track these potential features that you can vote or comment on if you'd like to see them as well.