---

Backstory

A few years ago at Colby, my roommates and I decided to set up a Secret Santa game amongst ourselves just a few days before the winter break. It was infeasible to get everyone in the same location to generate draws together, yet we wanted to avoid one person drawing on everyone's behalf. So, I wrote a small script to perform the task for us. Having recently learned JavaScript, I hastily wrote a function that looked something like the following.

function assignRecipient(giver) {
  
  // Ensure no self-matches 
  // Ensure no duplicate recipients
  const possibleRecipients = names
    .filter(name => name != giver)
    .filter(name => !Object.values(pairs).includes(name))
  
  if (giver !== names[names.length - 2] || 
      Object.values(pairs).indexOf(names[names.length - 1] !== -1))
  {
    pairs[giver] = possibleRecipients[Math.floor(Math.random() 
                    * possibleRecipients.length)]
  }
  else
  {
    // Final input still is not a recipient
    // Forcibly assign penultimate input -> ultimate input
    pairs[giver] = this.names[this.names.length - 1]
  }
}

But a problem gnawed away at me. Did the implemented logic capture the necessary constraints?

---

Answer Set Programming

My first question struck at a fundamental difference between imperative programming and declarative programming. Vladimir Lifschitz [1] effectively described this difference.

The difference between traditional "imperative” programming and declarative programming is similar to the difference between imperative and declarative sentences in natural language. An imperative sentence is a command that can be obeyed or disobeyed: “Go to school.” A declarative sentence, on the other hand, is a statement that can be true or false: “I am at school.” A program in an imperative language is formed from commands: "multiply \(n\) by \(2\)" … A program in a declarative language, on the other hand, consists of conditions on the values of variables that characterize solutions to the problem. Assignments are out of place in a declarative program.

It seemed that a declarative programming approach could provide better assurance of having implemented the correct set of constraints.

Answer set programming (ASP) follows the declarative model as a type of logic programming. Answer set solvers find stable models and thus realize ASP. I decided to rewrite the program as an application using Clingo, a widely used solver in the field of AI.

Declarative programs are often much shorter than imperative programs. Case in point: I transformed the old, imperative script into a short, declarative Clingo program, which finds every possible answer set for an instance.

% Initialize persons
person(X) :- init(X).		

% Create pairs
pair(X, Y) :- person(X), person(Y), X != Y.	

% Filter pairs
1{match(X, Y) : pair(X, Y)}1 :- person(X).
1{match(X, Y) : pair(X, Y)}1 :- person(Y).		

#show match/2.

I wrapped this program using the Python bindings provided by Potassco. After concatenating an input instance in the form init(alice).init(bob).init(carol), the wrapper loads the ASP program into a Control object and grounds its variables.

control = Control()
control.add("base", [], asp_program)
control.ground([("base", [])])

Clingo then finds a single answer set (or "model"), which is further processed as required by the rest of the application.

control.configuration.solve.models = 1
with control.solve(yield_=True) as handle:
  for model in handle:
    # Do something with the model

---

Frontend

Here is an example of the application in action. With an AWS layer lying between the NodeJS frontend and the answer set solver, the request and response go through a lot of formatting. For the input alice, bob, carol, dave, eve, we may get the following output where a sample text file could read "Hi alice. You need to send a present to bob. Merry Christmas!"

There is an additional issue of trust, which is tricky to solve in a scenario with a frontend web interface. Should other participants trust the designated generator not to peek at any of the other text files? The generator can also look in the browser's developer tools to see the unformatted response. My initial thoughts on resolving this issue have to do with implementing an automated mailserver or a messaging bot (e.g. WhatsApp, Telegram, or SMS with the Twilio API), which would require a lot of information exchange between all the group members and would likely be overkill. As a basic measure, the contents of the text file are padded with a lot of initial whitespace so that the link preview that appears at the bottom of a browser upon a hover does not reveal any assignment.

---

Cloud Architecture

I set up the backend processor on Amazon Web Services (AWS), particularly leveraging S3, Lambda, and SQS. Interactions between these services required some configuration in IAM and Cognito to set up the necessary roles, policies, and permissions. The architecture of the backend is as follows.

1. The NodeJS server puts a request object into the input S3 bucket.
2. The bucket action triggers the Lambda handler, which is a Python function that runs the Clingo program.
3. The handler sends the ASP result to an SQS response queue.
4. The NodeJS server polls the queue until finding the desired message.

The handler is configured using Docker by specifying an image that is pushed to Elastic Container Registry (ECR). The Lambda is generated from deployments of this image.

---

What I Learned

Basic AWS cloud architecture: I learned how to set up a Lambda and deploy images from ECR, how to communicate between different services such as S3, SQS, and Lambda, and how to configure roles, policies, and permissions to avoid security issues.

Answer set programming: I already had some experience with Clingo, but this was my first time using the Python bindings.

Containers: This was my first time building a Docker container from the ground up and deploying an image.

Node/ExpressJS: I had used both of these quite a bit in the past, but that was approximately four years ago. I had fun re-familiarizing myself with these technologies.

Deployment: This was my first web application which I have deployed to be publicly usable. Setting up hosting on Heroku was not a bad experience, though correctly configuring AWS environment variables took much longer to figure out than it should have.

---

References

1. Lifschitz, V. 2019. Answer Set Programming. Springer.