Category: Scheme & LISP

If you haven’t had the chance, you really should pick up a copy of Common Lisp: A gentle introduction to symbolic computation by David Touretzky, in there you will find a series of “templates” for recursion. Consider these like tools in you toolbox.

The following is a presentation of these “recursion templates” in Scheme code with generous examples. Not as clumsy or imprecise as a for loop, they are elegant weapons, from a more civilized era.

Double-Test Tail Recursion

This template is a simple search recursion across a list.

(define (has-odd? lst)
	(cond
		((null? lst) #f)
		((odd? (car lst)) #t)
		(else
			(has-odd? (cdr lst)))))

As you see, we have a Double-Test at the beginning of the cond, the first tests null, and the second tests for the needle that we are searching for in the haystack that we’ve been passed.

In Touretzsky’s version, the first clause returned nil, I’ve elected to return #f which I think is more correct, as an empty list obviously does not have any odds in it. I prefer a uniformity in return types, even though in this example ‘() is certainly not true, therefore it is functionally equivalent.

Search a list for a value

(define (in-list? needle haystack)
    (cond
      ((null? haystack) #f)
      ((equal? (car haystack) needle)
        #t)
      (else
          (in-list? needle (cdr haystack)))))
(in-list? "Hello" '("Hello" "World")) ; #t
(in-list? "Hello" '("Goobye" "World")) ; #f

Single Test Augmenting Recursion, or Incrementing Recursion

This is a way to recursively accumulate or increment some value, such as counting.

(define (count-items lst)
    (cond
        ((null? lst) 0)
        (else
            (+ 1 (count-items (cdr lst))))))

List Consing Recursion

Here we build a list of values as we go along, notice that we are decrementing, so the numbers are in reverse order.

(define (count-down n)
	(cond
	  ((zero? n)
	   '())
	  (else
		(cons n (count-down (- n 1))))))

An alternative to this would be:

(define (count-up n)
  (let loop ((i 1))
    (cond
      ((> i n) '())
      (else
        (cons i (loop (+ i 1)))))))

Simultaneous Multivariate Recursion

Here we define a function that accepts an ordinal, like 1st, 2nd, 3rd (without the ordinal suffix), and
return that element.

In Touretzky’s book, he reimplements nth, which starts at zero, our function however does not accept 0.

(define (snatch i lst)
  (cond
    ((<= i 1)
      (car lst))
    (else
      (snatch (- i 1) (cdr lst)))))

Conditional Consing

Here we have two paths, one (number?) which conses the car of lst with the result of a recursive call to nums, or, which simply returns whatever would be returned via the continuation. Notice how the numbers come out in order!

(define (nums lst)
  (cond
	((null? lst) '())
	((number? (car lst))
	 (cons 
	   (car lst)
	   (nums (cdr lst))))
	(else
	  (nums (cdr lst)))))

Multiple Recursion

Here we combine the results from two independent recursions, each call has the possibility of generating 2 more recursions and on and on.

(define (fib n)
  (cond
	((equal? n 0) 1)
	((equal? n 1) 1)
	(else
	  (+ (fib (- n 1))
		 (fib (- n 2))))))

Car/Cdr Recursion

(define (find-number lst)
  (cond
	((number? lst) lst)
	((atom? lst) #f)
	(else
	  (or (find-number (car lst))
		  (find-number (cdr lst))))))

Page is a work in progress

In another post, I discussed how to build Chez Scheme from source for Debian 9 Stretch, here is how to setup SLIB.

git clone https://github.com/taktoa/slib.git
cp -fr slib /usr/share
cd /usr/local/lib
ln -sf /usr/share/slib .
chmod 777 /usr/share/slib
touch /usr/bin/chez
chmod 777 /usr/bin/chez
vim /usr/bin/chez

Edit the file /usr/bin/chez to be:

#! /usr/bin/scheme
(load "/usr/share/slib/chez.init")

There are a few gotchas when building Chez Scheme from source. The first is that you’ll need to install libncurses5-dev and libx11-dev

$ apt install build-essential libncurses5-dev libx11-dev

The next thing to consider is that you cannot build on a server or Virtual Machine with less than 4 Gigabytes of memory. This is because the nanopass compiler is a memory hog (see this issue) and there seems to be no fix.

Welcome to Scheme/LISP – Where there is always some bullshit hurdle to getting shit done.

Here are the steps you can take to deploy Chez Scheme on a remote server, such as a VPS that doesn’t have enough memory.

  1. Download and install: https://www.virtualbox.org/wiki/Downloads
  2. Download an iso of your version of linux, make sure to match perfectly with what is running on the server. For me it’s Debian 9 x64.
  3. Install a minimal linux system, then run: apt install build-essential libncurses5-dev libx11-dev rsync
  4. Clone the ChezScheme repo, then in that dir run ./configure && make
  5. rsync, or scp, ChezScheme to your server with: rsync -av ChezScheme/ user@server.com:/path/ChezScheme
  6. Once the sync is don, ssh to your server, into your ChezScheme dir, and run: make install

That should be about it!

Chez Scheme has to be the easiest, most consistent Windows friendly Scheme interpreter I’ve used. Of course, I’ve only otherwise tried MIT Scheme (and CLisp – which is epic crap).

If you want to start learning Scheme (or Lisp – I suggest Scheme), then Chez is the way to go. I’m still not very good with Scheme, and my code is not very idiomatic, mainly due to the absolute poverty of learning resources for Scheme and LISP in general.

A good resource for learning scheme is Schemers, which I find pretty helpful. Probably the most effective and useful text on Scheme or LISP I’ve ever read is The Little Schemer, it doesn’t seem like it will help at first, but about halfway through the book you’ll wonder why other language texts aren’t similar. Another great book for understanding LISPs in general is Common LISP: A gentle introduction to symbolic computation.

One central feature to these books is that they won’t teach you “how to get shit done” in Scheme or LISP. There’s a basic disconnect between LISP in theory and LISP in practice. You can pick up Practical Common LISP, which is misnamed in the extreme. You can also read it online for free.

Let me ask you, when is the last time you wrong a database of your own MP3s? I didn’t think so. How often do you write HTML compilers? Didn’t think so.

Here are the things I do often:

  1. Write a csv parser that injects 100k+ items into a MySQL Database because the columns are janky/custom.
  2. Write a script to iterate over 100k rows and modify the title/name/x-field because the client screwed up the original csv import and now the application API calls to XYZ are rejected because of bad characters.
  3. Write a new cron script that does x, y and sometimes z even 10 hours
  4. Read data from XYZ datasource (DB, CSV, Flatfile) and perform some repetitive transformation.
  5. Generate thousands of lines of boiler plate code for Framework X in language Y because a customer insists on deploying an app with that Language/Framework
  6. Produce destructable XML/JSON templates for some inconsistent hair brained SOAP API, or JSON API

Yeah. Not too many MP3 databases. I’ve been programming for over 15 years. Never wrote one yet.