The language for this homework is:
#lang pl 10 |
In this homework you will implement a solution for the “N-Queens” problem. You will do this in Schlac which means that you need to implement a lot 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, 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 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 Racket quote as a back-door for getting Racket 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 Racket 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 Racket. For example, it is easy to try some code in Racket that uses (and E1 E2 E3), 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 E1 E2) E3) which is almost certainly meaningless.
The obvious approach to make your way towards a working solution is to comment out the whole code, then uncomment bits one by one as you implement the missing parts, making sure that the given tests pass, and possibly adding more tests if needed.
Note that in some cases you might be tempted to rely on our implementation. For example, relying on the fact that the encoding of a number n is the “raise a function to the nth power” function works only for this encoding. The same goes for dropping if because we implement booleans as selector functions anyway. Doing such things is not a good idea, since it breaks an abstraction barrier (and in the case of this language, it’s one that cannot be enforced).
Note: you should still define the time you spent, but you must do that within the language, and Schlac is not really good at dealing with big numbers (they are function compositions, so things do get slow). So, for this homework, define hours-spent as the (Church-encoded) number of hours you’ve spent. There is an important point to note here — if you define this as an expression, for example
(define hours-spent (+ 3 3)) |
(test (->nat hours-spent) => '6) |