Category: Software Engineering

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.

This isn’t a true hash table, it’s really just a pair list, but it behaves how most imperative programmers would expect a hash table to behave. Note: it is a naive implementation, so it has a linear access time.

(define (store data key value)
  (cond
	((null? data) (cons (list key value) '()))
	((equal? (caar data) key)
	 (cons (list key value) (cdr data)))
	(else
	  (cons (car data) (store (cdr data) key value)))))
(define (fetch data key)
  (cond
	((null? data) '())
	((equal? (caar data) key) (cadar data))
	(else
	  (fetch (cdr data) key))))
(set! x (store '() 'hello "World"))
(set! x (store x "The rain in spain" "falls mainly on the plain"))
(set! x (store x '(a b c) 42))
(fetch x '(a b c))
(fetch x "The rain in spain")

Here is a bit of code I’ve been tinkering with, it’s a simple CSV parser in Scheme that I am using to parse Stock data so that I can back test trading strategies.

(define (csv->list file_name)
  (with-input-from-file file_name
	(lambda ()
	  (let reading ((chars '()) (rows '()) (cols '()))
		(let ((char (read-char)))
		  (cond
			((eof-object? char) (reverse rows))
			((char=? char #\newline)
			 (reading '() (cons 
					(reverse 
					  (cons (list->string (reverse chars)) cols)) 
					rows) '()))
			((char=? char #\,)
			 (reading '() rows
			   (cons (list->string (reverse chars)) cols)))
			(else
			  (reading (cons char chars) rows cols))))))))
(csv->list "D:/Projects/StockMarket/NASDAQ_20101105.txt")

The above is why I love Scheme. Such a succinct language.

How to design functions in Scheme

The above small function follows the basic function design pattern, we begin with the target or most significant goal state: EOF. What do we do?

((eof-object? char) (reverse rows))

We return the reverse of the rows. This is because cons prepends new elements. Now we could call (append) instead of (cons) but (append) has to find the end of the list each time, adding unnecessary overhead.

Our next goal, or major target is the end of line, or #\newline character.

((char=? char #\newline)
  (reading '() (cons 
    (reverse 
	(cons (list->string (reverse chars)) cols)) 
     rows) '()))

If the current char equals a new line, we need to:

  1. Produce the column value (newline works like comma)
  2. Prepend the column value to the lists (cols)
  3. Prepend the (reverse cols) list onto (rows)
  4. Recurse into (reading) with the new (rows) and ‘() for both chars and cols

The next goal state, is encountering a comma, or the delimiter:

((char=? char #\,)
    (reading '() rows
      (cons (list->string (reverse chars)) cols)))

In this case we need to recurse into (reading) with ‘() for chars, as well as prepending the (reverse) of (chars) stringified to (cols).

So I’ve picked up a new book, Introduction to Algorithms, 3rd ed. and I’ve decided to try implementing some of them as a practice using Scheme, specifically I’m using a vanilla install of Chez Scheme.

(define merge-sort
  (lambda (l A L R sw)
	(cond
	  ((and (null? L) (null? l)) (append A R))
	  ((and (null? R) (null? l)) (append A L))
	  (else
		(cond 
		  ((null? l)
		   (cond
			 ((and (null? A) (or (= sw 1) (= sw 0)))
			  (merge-sort 
				l 
				A 
				(merge-sort L '() '() '() 0) 
				(merge-sort R '() '() '() 0) 
				-1))
			 (else
		   		(if (<= (car L) (car R))
			 		(merge-sort 
					  l 
					  (append A (list (car L))) 
					  (cdr L) 
					  R 
					  sw)
			 		(merge-sort 
					  l 
					  (append A (list (car R))) 
					  L 
					  (cdr R) 
					  sw)))))
		  (else
			(if (= sw 0)
			  (merge-sort 
				(cdr l) 
				A 
				(append L (list (car l))) 
				R 
				1)
			  (merge-sort 
				(cdr l) 
				A 
				L 
				(append R (list (car l))) 
				0))))))))

(merge-sort '(85 6 43 33 21 9 1 3 22 84 85) '() '() '() 0)

So I’ve picked up a new book, Introduction to Algorithms, 3rd ed. and I’ve decided to try implementing some of them as a practice using Scheme, specifically I’m using a vanilla install of Chez Scheme.

(define isort 
    (lambda (l1 l2)
        (cond
            ((null? l1) l2)
            ((null? l2) (isort
                (cdr l1)
                (cons (car l1) l2)))
            ((<= (car l1) (car l2)) 
                (isort
                    (cdr l1)
                    (cons
                        (car l1)
                        l2)))
            ((> (car l1) (car l2))
                (isort
                    (cdr l1)
                    (cons 
                        (car l2) (isort 
                            (cons 
                                (car l1) 
                                '()) 
                            (cdr l2))))))))
(isort '(85 12 59 45 72 51) '())

Now that’s all fine and good, but we need ‘More Power’ as Tim the Toolman Taylor would say. I think it’d be nice if we could pass the function a comparator, so that we could do ascending and descending sorts.

(define isortf 
    (lambda (l1 l2 c1 c2)
        (cond
            ((null? l1) l2)
            ((null? l2) (isort
                (cdr l1)
                (cons (car l1) l2) c1 c2))
            ((apply 
                c1 (list 
                    (car l1) 
                    (car l2))) 
                (isortf
                    (cdr l1)
                    (cons
                        (car l1)
                        l2) 
                    c1 
                    c2))
            ((apply 
                c2 (list 
                    (car l1) (car l2)))
                (isortf
                    (cdr l1)
                    (cons 
                        (car l2) (isortf 
                            (cons 
                                (car l1) 
                                '()) 
                            (cdr l2) 
                            c1
                            c2)) 
                    c1
                    c2)))))

(isort '(3 4 2 1) '())
(isortf '(3 4 2 1) '() >= <)

When you write in Scheme, it all makes perfect sense to you. It looks hand crafted, like a fine old carving. But part of you knows it's probably completely incomprehensible to anyone else.

Oh well. At least I think it's beautiful.