I'm working on spawk, a scheme-awk hybrid. And for the last couple days I've been writing <a href="http://librep.sf.net">rep</a> code to use in sawfish.

Woo scheme. I'm taking apart these python programs I have and am now writing them in scheme.

So, for a while I've been meaning to make myself a passport for Fort Emad (Actually, I really wanted to make a passport for my role as former Overlord of Minnesota, Protector of the Dakotas, and Subjugator of Wisconsin, but I couldn't think of enough symbols). So anyway, I've been thinking of doing this for a while now, and just today I got a little inspiration from http://passports.slawek.com/ Of course, I still have to figure out where to get the supplies (and perhaps access to a quality color copier).

I've had this recurring theme in my life where I try to get my brother into some technical topic or other. Typically I'm trying to get him into programming of some sort. I never know how much of it is me being a pestering brute and how much is him actually enjoying and understanding the lesson.

So my latest push was accepted rather warmly. I mentioned that graph algorithms are usually big list manipulations, and the sort of thing that has all sorts of rich algorithm analysis behind it. Lots of good science code out there.

So he sent me this way to determine if a sequence of the degrees of unique vertices is graphical. That is, can we say that in a reasonable universe, all of these vertices are connected in a single structure.

(1 2 2 1) is a valid graph, since it is just four nodes strung together in a line. (7 2 2 1) is invalid, since there's simply not enough nodes for any one of them to have 7 connections.

I'm not sure he followed my explanations, or really spent much time reading my long mails on the subject. I encouraged him to trace the various functions to see how they work. The trace function is simply fantastic for learning how a system is behaving without going into the debugger. It's much like the strace and ltrace tools, but it's easier to be selective.

I'm not a great schemer, so likely this is done in a stupid or redundant way. I do think it's done in a portable way, and is straightforwardly implemented so that a new schemer can understand it.

So here's the code, all commented and supafly. The latest version lives at http://zork.net/~nick/scheme/degree_seq.scm

; Functions for analyzing degree sequences in an undirected graph


; list-satisfies? is a list analyzer function.  It accepts a predicate
; function and a list.  If any element of the list should fail the
; predicate, then list-satisfies? fails as a whole.  Put another way, it
; succeeds *only* when all elements of the list satisfy the predicate.
(define list-satisfies?
  (lambda (predicate l)
    (cond ((null? l) #t)
          ((predicate (car l)) (list-satisfies? predicate (cdr l)))
          (else #f))))

; decrement-n-elements accepts an integer n and a list of numbers.  It
; subtracts 1 from the first n elements of the list.  No data validation
; is done, so all atoms must be numbers.  In the event that there aren't
; enough elements in the list to decrement n elements, the function will
; simply return a list with all elements decremented.
(define decrement-n-elements
  (lambda (n l)
    (cond ((null? l) '())
          ((zero? n) l)
          (else (cons (- (car l) 1)
                      (decrement-n-elements (- n 1) (cdr l)))))))

; valid-degree-sequence? is a predicate that analyzes a list of integers
; representing the degree of connectedness of unique nodes in an
; undirected graph.  It returns true if the sequence is all zeroes or
; reduces to same, and false if it contains a negative degree or reduces
; to a sequence with a negative degree.
(define valid-degree-sequence?
  (lambda (sequence)
    (cond ((list-satisfies? zero? sequence) #t)
          ((list-satisfies? (lambda (x) (not (negative? x))) sequence)
           (valid-degree-sequence? (reduce-sequence sequence)))
          (else #f))))

; reduce-sequence does the actual work of reducing the degree sequence.
; If the sequence d1,d2...dn has enough elements such that n >= d1, then
; it will decrement the first d1 elements of d2...dn.  If there are not
; enough elements for this to be performed, the list reduces to the bogus
; sequence (-1), which will fail any valid-degree-sequence? test.
(define reduce-sequence
  (lambda (sequence)
    (cond ((> (length (cdr sequence)) (car (sort sequence >)))
           (decrement-n-elements (car (sort sequence >))
                                 (cdr (sort sequence >))))
          (else '(-1)))))

If I were to run a hacker book club, I would screen out anyone who codes, especially for a living. I'd also not be too keen on anyone who was big on numbers, since the goal would be to catch Liberal Arts types and high school kids and so forth. I always imagine advertising this in the classifieds or something.

Here's the reading list I'd use:

Hackers Start out with Hackers. It's a great read, and every hacker I know who read it as a child envied the people described in it. It's an inspiring story, and really gets across the notion of hacking, as opposed to mere development, or even work.

It covers the old guard of MIT, and lists many names that come up in anyone's study of LISP. It puts LISP into a historical context, which is useful.

Modern editions even end up with RMS, which can lead into...

Free as in Freedom

It's the natural sequel to Hackers, and it covers a lot more of the philosophical angles. It helps put Free Software into historical perspective as well, and provides a context for EMACS the way Hackers does for LISP.

It's possible to skip this book, and cover Free Software in other ways, or to merely put this book on the list of subsequent reading the members might want to do on their own time.

Once the history and ethical questions are out of the way, move on to some more technical topics.

The Pattern on the Stone

Hillis makes a great explanation of the core principles of computer hardware and logical design. It's perhaps a GEB-lite, and references Hofstadter in one of the chapters. It's quite possibly the best introduction of the actual technology of computation for the lay reader.

It's a super-slim book, and can be covered in its entirety in a single session.

He talks about everything in terms of functional decomposition, which lets us lead into an application of functional decomposition: LISP itself.

The Little Schemer

This book above all others is why I love scheme. It's like a catechism for lisp programmers, or a dialogue between master and novice. It's Socratean intellectual midwifery -- 200 pages of leading questions and answers forcing you to work out the process of computation in your head or on paper.

It's quite possibly the best way to learn computer programming, and it requires absolutely no computers whatsoever to do so. It doesn't even mention particular operating environments, or teach you how to run the expressions on any sort of machine. It instead teaches you how to think about computation in a way that hack C and Perl programmers never get.

It's designed for people who are perhaps a touch innumerate, or can't get their multiplication tables down, or panic at long division. It assumes only basic arithmetic or algebraic skills, and even then only for a chapter. The whole book is structured around the manipulation of lists of names of food items (though many will note that the book is decidedly not vegetarian, lumping "turkey" in with "peanut butter and jelly", it never advises the reader to eat any meat).

This book would be covered less like a book club reading group, and more like a recitation session or laboratory. It'd be good to have a blackboard at this point, to illustrate and discuss each step of the question-answer cycle. I bet you I could teach even my dad to understand Y. It's all just linguistics.

It's an obsession.

Over the weekend I read Paul Graham's treaties on the social order of adolescent nerds. I started bouncing through his site some more, and reading the history of T and the magic of macros and so on and so forth. It must have struck a scheme funnybone or something, because I picked up my copy of SICP and started reading.

Now I'm in the middle of chapter two (there are only five chapters), and I've already read through chapter ten of TLS a long time ago. I grok Y, but never really got around to building any real apps in scheme.

I realized that I had MIT-Scheme already installed on zork, and started fiddling in edwin. It's almost enough to make me start using EMACS.

So now I have a project in mind: integrate libguile into nwall. This way people can write scheme scripts to add features to nwall.

I also want to start a reading club for fledgeling hackers, but that's another story, and I have to BART off to an evening class now.

So, as part of the Capoeira club, I got a CD of songs. The only problem being that the CD-R I received is the worst quality CD ever, I can't even get it to play real time. So, I figured this was a job for CD Paranoia. I started late last night, and it's still on the first skippy track.

The other day, I went down to eat my lunch in the dining hall, and one of the patrons had a guitar and was playing an acoustic rendition of the theme to The Fresh Prince of Bel Air. I tried to sit far away, because I had no idea what he'd do next, but it turned out it was his last song.