Assignment #7: Lazy Programming in Schlac: N-Queens

Work and submission is with the same pairs.

You will need to have an updated course plugin, and that requires an updated PLT Scheme version.

The assignment is significantly watered down, so it should not require more than a few hours, or even less.

In this assignment you will implement a solution for the N-Queens problem. You will do this in Schlac which means that you need to implement many of the “runtime-support” for your code, but it also means that you enjoy the benefits of laziness. The main implication of this is the fact that you write a function that computes all possible solutions, but returns only the first one — and because the language is lazy, then no additional solutions are actually computed.

To make your job easier, you get a template file with holes to fill the rest of the code in. The code uses #lang CSU660/schlac which is the same language that we've used in class (Lecture #16); and you'll see also a (use-church) line at the top, which imports all functions that were defined in that lecture. The template file has ??? in all holes that you need to fill — in some cases it is just an expression in the definition, and in some cases the whole definition needs to be written. For your convenience, the file contains a complete set of function headers (contracts and purpose statements) as well as tests — so the only thing you need to do is add the missing code pieces.

Note that the tests use the conversion functions that are not officially a part of Schlac, as well as using a Scheme quote as a back-door for getting Scheme values into the tests.

Remember that this is Schlac: it is a lazy language, it is curried, and define cannot generate recursive definitions. Also, many of the “library” function names resemble their Scheme counterparts — but be careful: since all values in Schlac are single-argument functions, you will never get any error from Schlac code. If you have errors in your code, they will usually manifest themselves as errors only when you try to convert values back to Scheme. For example, it is easy to try some code in Scheme that uses (and E₁ E₂ E₃), and assume that it will work the same in Schlac — but this is wrong, since and is a two-argument function, and automatic currying means that if you use this expression in Schlac then it's as if you entered ((and E₁ E₂) E₃) which is almost certainly meaningless.

A natural way to work your way towards a solution is to comment all code out, then uncomment functions one by one as you implement the missing parts and make sure the given tests pass.