12 Towards zebras

7.2

← prev up next →

12 Towards zebras

If we’ve been through the previous part, we can keep using the same file. Or we can use 7-amb.rkt as our starting point.

If we add a few more things to our language, we can use amb to figure out who owns the zebra.

12.1 What, if anything, is a zebra?

There exists multiple variations of the Zebra Puzzle. We will use the one we find on Wikipedia:

The Englishman lives in the red house.
There are five houses.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

12.2 Adding stuff to our language

There’s a few things that are necessary, or at least convenient, for solving the zebra puzzle.

12.2.1 More list/pair functions

Can add some primitives:

cons for constructing a list or pair
car for getting the first element of a list or pair
cdr for getting the tail of a list or the second element of a pair
null? for checking if something is the empty list

12.2.2 Quotes

In Racket, e.g. 'a is translated to (quote a) by the reader. If we want to support quotes in the language we’re making, we can match on (list 'quote exp) and continue with the quoted syntax, exp.

Quoting can be convenient for list-laterals, like '() and '(1 2 3). Also for for symbols, like 'foo.

12.2.3 Strings

Maybe we want strings, for values such as "red" and "zebra". (If we have added quotes to the language, we can choose to use values like 'red and 'zebra instead, and skip the strings.)

If we’re adding strings, we want to recognize string-literals in eval-exp, We can use string? for this, same way we use number? and boolean? for other literals.

We don’t really need to do any fancy string-operations in order to find the zebra. We can totally add some string-functions to our primitives, like string-append and, say, string-upcase, but we don’t have to.

12.2.4 equal?

If we add equal? to the primitives we can use it for checking if things (e.g. strings, symbols) are equal.

12.2.5 Recursive functions

The list is a recursive data structure. We might need recursive functions. Since our lists are Racket lists, our strings are Racket strings, and so on, we can probably get away with writing the recursive functions in Racket and just adding them as primitives. But it would be neat to add support for recursive functions to our language.

One thing we can do is to combine it with adding support for more rackety function definitions, the ones that go (define (function-name arguments ...) body ...). We can add a clause to the match in eval-sequence:

[(list (list 'define (list name params ...) body ...) rest ...) your code here]

Here we must extend the environment with the function definition. To make the possibly recursive function, we make a helper-function:

(define (make-named-function env name parameters body)
(λ (continue fail . arguments)
your code here))

This should behave mostly like make-function, only the function should add “itself” to the environment before adding the arguments to the environment. It can create a copy of “itself” by applying make-named-function again. (We’re really using Racket’s support for recursive functions to build our own support for it.)

12.3 Writing a zebra-program

One way to go about this:

12.3.1 Some lists

We make a list of colours, a list of nationalities, and so on. Each element in the each list is an amb-expression with the possible values. (We can optimize a bit: E.g. since the puzzle tells us that the norwegian lives in the first house, we don’t need an amb for the first element in the list of nationalities, and we don’t need to include norwegian as a possible value for the other elements.)

12.3.2 Some helper functions

We probably want some helper functions for stuff like:

Checking that a list contains no duplicate elements (we won’t allow e.g. two red houses)
Getting the index of an element in a list
Checking that one element in one list has the same index as another elemnt in another list (for things like “the Englishman lives in the red house”)
abs (or we can just include Racket’s abs in the primitives
Checking that one element has an index that is off by one from the index of another element in another list (for things like “the Norwegian lives next to the blue house”)

12.3.3 The requirements

With the lists and the helper functions we can specify the different requirements.

In order to make the program go faster, we should add the different requirements as soon as possible:

After defining a list, we immediately require that it has no duplicate elements.
After defining a list, we add all the requirements that we have the necessary lists for. Like, once we have defined a list of nationalities and a list of colours, we will add the requirements for “the Englishman lives in the red house” and “the green house is immediately to the right of the ivory house” before defining more lists.

12.3.4 Return a list with all the lists

Return a list with all the lists.

12.4 Running the zebra-program

We can run the program with evaluate to find one solution, and maybe run it with evaluate* to check that there is only one solution.

12.5 Done?

OMG.

← prev up next →

1	Meta-circular what?
2	Some Racket
3	Fixing the calculator
4	Lookup in the environment
5	Definitions
6	Functions
7	Continuation-passing style
8	Refactoring to CPS
9	Booleans
10	Ambiguousness
11	It’s puzzle time
12	Towards zebras

12.1	What, if anything, is a zebra?
12.2	Adding stuff to our language
12.3	Writing a zebra-program
12.4	Running the zebra-program
12.5	Done?