isthisblog

Hello Prolog 01: Data Structures, Operation, and Control

June 27, 2018

[DRAFT DISCLAIMER]

Instead of publishing the article when it's done, I figured if I just write and don't post this anywhere (like twitter, hn, etc), I can keep writing and get feedback, then when the post is "done", I'll spread the word. Once the [DRAFT] subtitle (and this block of text) is gone, it's considered "published". So feel free to leave feedback either at my email (isthisnagee+blog@gmail.com, also linked below) or by opening an github issue on this post's github issue

[END DRAFT DISCLAIMER]

In Prolog, the "type name" is an integral part of all the occurences of an object's description. In Rust for example, I would first describe a type, then I would instantiate an object of that type.

struct Rectangle {
height: u32,
width: u32,
}
let rectangle = Rectangle{ height: 10, width: 10 };

In prolog, this is a single step!

rectangle(10, 10)

We describe rectangle as rectangle/2. That is, "rectangle" is rectangle that takes two arguments. rectangle is what is known as a Functor. It takes components (arguments) and maps them to compound objects.

The List

Lists are very interesting, and this is where prolog started to blow my mind a bit. We'll define a list like this:

  1. The empty list
  2. An object combined with a list.

Here's an example

const someList = []
const someObject = 1
const aList = [someObject, ...someList]
// [1]
const anotherList = [2, 3]
const aBiggerList = [someObject, ...anotherList]
// [1, 2, 3]

The book used "cons", "cdr", and "car" and their combination and variances. While I understand their historical significance and all that (see here for an explanantion into what they mean) the only word I'll borrow is "cons", short for "construct", and it's what we use to "consturct" a list

In Prolog, we can describe a list of three objects as follows:

cons(a, cons(b, cons(c, emptylist))).

Here, cons/2, a/0, b/0, c/0, and emptylist/0 are all functors! Functors that take 0 arguments are a neat little trick for constants.

While this is cool and all, these are only descriptions of objects. The example above was a description of a list of the first three letters of the alphabet ([a, b, c]).

But for these lists to be practical, we need to be able to more easily combine, extract, and manipulate. This is where operations like Procedures come into play!

Operations!

A Term, which starts with an uppercase letter, is a definition of a type. If types describe the shapes of objects, then Terms describe the shapes of types. So Variable2 describes the set of all objects, whereas [a, b, c] describes a set who's members are all objects of length three with first element is a, the second is b, and the third is c. This list only has one member, the list [a, b, c]. It might be a bit weird to think about, but bear with me.

Consider these examples:

all records titled "Hello" of an unknown artist

song(Artist, 'Hello')

all records by Adele

song(adele, Record)

The name of all songs by Adele in the album titled "25

song(adele, record(Name, '25'))

all non empty lists

[ Head | Tail ]

Procedures

Ok so this is where we get to the cool part and I think this is where prolog shines!

Let's write a procedure. I'll start off by writing some (pretty bad) documentation for it:

The procedure first_element will take in a list and output the first element in the list (the Head) and the rest of the list (the Tail).

Here's an implementation in JavaScript

const first_element = (list) => {
  const [Head, ...Tail] = list
  return {
    Head,
    Tail
  }
}

// usage:
const { Head, Tail } = first_element([1, 2, 3]);

Here it is in prolog:

first_element([Head | Tail], Head, Tail).

Pretty cool! The JavaScript solution is only as short as it is because of some newer syntax (the spread operator, and property shorthand), otherwise we'd be using a lot of built ins. The prolog procedure says the following:

Accept any object from the set of objects matching [Head | Tail] and then put Head in the second argument and Tail as the third argument.

This is how we would get head and tail out in prolog

?- first_element([1, 2, 3], First, Rest).
% First = 1
% Rest = [2, 3]

What's really fun about this is that this is also valid:

?- first_element(A, 1, [2, 3]).
% A = [1, 2, 3]

What!!!! This might be why naming is such a hard problem. Clearly this procedure is not just first_element. It can combine elements in a list, it can get the first element, and it can get the tail. This is also valid

?- first_element([H | [2, 3, 4]], 1, T).
% H = 1
% T = [2, 3, 4]

Complex.