N-Queens, LEDs, Scheme

Home | Archive

N-Queens, LED's, Scheme

2005-07-29T13:14:00

N-Queens, LED's, Scheme

It's that time of the year when I am teaching Lisp; I just know enough of it to do some simple puzzle-solving stuff. I had chanced upon two great books, Structure and Interpretation of Computer Programs and How To Design Programs long time back. I wish to read both books completely, but I think I never will :-( It's a pity that students are made to learn such horrible languages like C/C++/Java (note that I am talking from a pedagogic perspective). As a teacher, I can say with some authority that beginning students waste too much of time trying to master the syntactic intricacies of these languages; time which should be spent trying to understand the essence of problem solving. A language like Scheme (a dialect of Lisp) is almost syntax-free (I don't think this is the correct term to use...), and has such great expressive power that you can think of teaching the basics of a Prolog like backtracking engine to talented beginners (read SICP if you don't believe me). One objection raised against the `Lispish' languages is that they are far too abstract and removed from `real world' applications; this is not the case. Take the case of Guile, the GNU scheme interpreter implemented as a library. You can evaluate scheme expressions within a C program using Guile; you can also define primitive Scheme functions in C. I had no idea of how simple it was until I tried it out yesterday. Here is a sample program:

#include <guile/gh.h>

void real_main(int argc, char *argv[])
{
	gh_eval_str("(define (sqr x) (* x x))");
	gh_eval_str("(display (sqr 10))");
	gh_eval_str("(newline)");
}

main(int argc, char *argv[])
{
	gh_enter(argc, argv, real_main);
}

Compile the program:

cc b.c -lguile

Run it, and it prints 100. Scheme expressions are evaluated by passing them as simple C strings to `gh_eval_str'. Because of some problems involving the garbage collector, all invocations of gh_eval_ should take place in a function which has been called via `gh_enter'. Here is a program which demonstrates how you can define a scheme function in C.

#include <guile/gh.h>

SCM add(SCM a, SCM b)
{
	int p, q;
	p = gh_scm2int(a);
	q = gh_scm2int(b);
	return gh_int2scm(p+q);
}

void real_main(int argc, char *argv[])
{

	gh_new_procedure2_0("add", add);
	gh_eval_str("(display (add 34 20))(display 121)");
	scm_shell(argc, argv);
}

main(int argc, char *argv[])
{
	gh_enter(argc, argv, real_main);

}

The C function is defined as returning an object of type `SCM' and accepting two SCM objects; `SCM' is (I believe) some kind of C representation for Scheme data types. Within the body of the function, the Scheme representations are converted to proper C integers, summed up and converted back to Scheme-style representation. The `gh_new_procedure' function informs the Scheme interpreter of the existence of a function whose Scheme name is given as the first argument(ie, "add"). The scm_shell function invokes an interactive Scheme shell within which we can test out our `add'. It's now trivial to define an `enable-io' function which invokes `iopl' to get I/O privileges and two other functions out-port and in-port which does port I/O using inb/outb calls. You can now write a parallel port LED blinker in Scheme! You can go one step further. A few of my students are working on visualizing the N-Queen's problem using a chess board in which each square contains one LED; all the LED's are interfaced to the parallel port using some simple electronics. As a queen is placed on a cell, the corresponding LED lights up. As the algorithm backtracks, you can see some of the LED's going off and new LED's getting lighted. Should be fun to watch!