Deprecated: Function set_magic_quotes_runtime() is deprecated in /home/raedan/public_html/textpattern/lib/txplib_db.php on line 14
State of Flow: Dabbling in Scheme::journal

Dabbling in Scheme

Channing Walton - Tuesday August 15, 2006

This weekend I started learning Scheme … comments and suggestions are welcome.

I have been programming in Java for a decade and decided that I should learn something completely different. So, I decided to learn Scheme after watching a few of the Abelson and Sussman lectures (which I thoroughly recommend).

So, to start tinkering I needed a problem and since I’ve been talking to Lance recently about the Relational Model of Data I decided to implement some of those ideas in Scheme.

Using the Schemeway plugin for Eclipse, this is what I came up with to build a very simple model of relations, and to perform three operations: SELECT, PROJECT and JOIN.

I am not going to try to give this to you in bits, the code below is whole thing, and I’ll talk it through below:

(Apologies for the formatting but I’ll sort it out soon.)

;;
;; Set up the basics
;;

(define (field name value) (cons name value))
(define (tuple . fields) fields)
(define (relation . tuples) tuples)

(define (field-name field) (car field))

(define (field-value field) (cdr field))

(define (tail list) (cdr list))

;;
;; Helpers
;;

(define (find-field name tuple) (find (lambda(field) (string=? name (field-name field))) tuple))

(define (field-value-in-tuple fieldname tuple) (field-value (find-field fieldname tuple)))

(define (field-value=? name value) (lambda (tuple) (= value (field-value-in-tuple name tuple))))

(define (field-name-in? f field-names) (any (lambda(name) (string=? name (field-name f))) field-names))

(define (project-tuple t field-names) (filter (lambda(field) (field-name-in? field field-names)) t))

;;
;; The Operations
;;

(define (select predicate relation) (filter predicate relation))

(define (project relation fields) (map-in-order (lambda(t) (project-tuple t fields)) relation))

(define (cartesian-product r1 r2) (define (accumulate-join t2 accumulator) (fold-right (lambda (t1 accumulator2) (cons (append t1 t2) accumulator2)) accumulator r1)) (fold-right accumulate-join '() r2))

Thats it! This is sufficient to define relations, select project and join. Pretty neat for such little code but of course there are a few things missing (such as not enforcing uniqueness of tuples in a relation), but its a toy problem.

The first three lines define a field which has a name and value, tuple as a list of fields, and relation as a list of tuples.

field-name and field-value add semantics to the model. They are not necessary but I think it helps to build semantic richness for comprehension. They wrap the built-in car and cdr functions which return the first and second elements of a pair.

Implementing SELECT

The first thing I implemented is the relational operation, select. All this actually does is wrap the function filter which filters a list using a predicate. The list in this case is a relation, which is a list of tuples.

To try this out, I set up some sample data and selected something from it:

(define t1 (tuple (field "name" "Channing") (field "age" 38)))
(define t2 (tuple (field "name" "Lance") (field "age" 37)))
(define r (relation t1 t2))

(select (field-value=? "age" 37) r )

You can see the implementation of field-value=? is pretty straightforward. It returns a function that given a tuple, returns the value of a field in that tuple. It makes use of another function field-value-in-tuple to do the work of finding the value of a named field in a tuple.

Pretty easy so far.

Implementing PROJECT

The relational operation PROJECT, returns a new relation containing tuples with a subset of the original fields. It is similar in concept to the SQL select column1, column2, ... from TABLE. So my implementation of PROJECT takes a relation and the field names of interest.

To implement PROJECT, I made use of the map function from SRFI 1’s list library. The list given to map is the relation. The predicate given to map is a lambda which projects a tuple, ie selects a set of fields from the tuple.

Still pretty easy.

Implementing CARTESIAN-PRODUCT or JOIN

To keep things easy for me (this is only the third day of Scheme for me after all) I decided that my JOIN operation will simply be the cartesian product, which is fine.

Once again, I made use of a function from SRFI 1’s list library: fold-right which is a list iterator.

Because the cartesian product will result in a new relation whose size is the product of the two relations given to the function, I need to accumulate the results as I go. My function defines a new function accumulate-join which does the work. I’ll leave it as an exercise for the reader to figure out how it works. When you’ve done so, please explain it to me ;)

Testing

Because I am into TDD, I was looking for a SchemeUnit are something similar and found Sebastian Egner’s Lightweight testing library, SRFI-78. This is what my tests look like:

(include "/Users/channing/Java/workspace3.2/relations/test/check.scm") (include "/Users/channing/Java/workspace3.2/relations/src/relation.scm")

(check-reset!);
(check-set-mode! 'report-failed)

(check (car (field "foo" 2)) => "foo")
(check (cdr (field "foo" 2)) => 2)

(check (field-name (field "foo" 2)) => "foo")

(check (field-value (field "foo" 2)) => 2)

(check (first '(1 2 3)) => 1)

(check (tail '(1 2 3)) => '(2 3))

(check (field-value-in-tuple "foo" (tuple (field "foo" 1) (field "bar" 2))) => 1)

(check (find-field "foo" (tuple (field "foo" 1) (field "bar" 2))) => (field "foo" 1))

(check (=field-name (field "foo" 1) (field "foo" 2)) => #t)

(check (field-name-in? (field "bar" 1) '("foo" "bar")) => #t)

(check (field-name-in? (field "xyz" 1) '("foo" "bar")) => #f)

(check (project-tuple (tuple (field "foo" 1) (field "bar" 2)) '("foo")) => (tuple (field "foo" 1)))

(check (project (relation (tuple (field "foo" 1) (field "bar" 2)) (tuple (field "foo" 3) (field "bar" 4))) '("foo")) => (relation (tuple (field "foo" 1)) (tuple (field "foo" 3))))

(check (cartesian-product (relation (tuple (field "foo" 1) (field "bar" 2)) (tuple (field "foo" 11) (field "bar" 21)) ) (relation (tuple (field "bloop" 3) (field "bling" 4)) (tuple (field "bloop" 31) (field "bling" 41)))) => (relation (tuple (field "foo" 1) (field "bar" 2) (field "bloop" 3) (field "bling" 4)) (tuple (field "foo" 11) (field "bar" 21) (field "bloop" 3) (field "bling" 4)) (tuple (field "foo" 1) (field "bar" 2) (field "bloop" 31) (field "bling" 41)) (tuple (field "foo" 11) (field "bar" 21) (field "bloop" 31) (field "bling" 41)) ))

(check-report)

Printing

During development is was useful to print fields, relations and tuples. Here is the code to do that:

(include "/Users/channing/Java/workspace3.2/relations/src/relation.scm")

(define (say text) (newline) (display text))

(define (display-strings . more-items) (for-each (lambda (s) (display s)) more-items))

(define (display-tuple tuple) (display "|") (for-each (lambda(field) (display-strings " " (field-value field) " |")) tuple) )

(define (display-heading relation) (display "|") (for-each (lambda(field) (display-strings " " (field-name field) " |")) (first relation)))

(define (display-table-of-values relation) (for-each (lambda(tuple) (display-tuple tuple) (newline)) relation) )

(define (display-relation relation) (newline) (display-heading relation) (newline) (display-table-of-values relation))

I think its pretty self explanatory. Here are some examples of its output.

Given:

(include "/Users/channing/Java/workspace3.2/relations/src/printing.scm")

;;
;; Define some tuples with fields and a relation
;;

(define t1 (tuple (field "name" "Channing") (field "age" 38)))
(define t2 (tuple (field "name" "Lance") (field "age" 37)))
(define r (relation t1 t2))

(say "A relation r")
(display-relation r)

(say "select tuples from r where age=37")
(display-relation (select (field-value=? "age" 37) r ))

(say "select the name field from r using a projection")
(display-relation (project r '("name")))

(define t3 (tuple (field "extra" "stuff") (field "more" 100)))
(define r2 (relation t3))

(say "A relation r2")
(display-relation r2 )

(say "join r and r2")
(display-relation (cartesian-product r r2))

(say "select tuples from joining r and r2 where age is 38")
(display-relation (select (field-value=? "age" 38 ) (cartesian-product r r2)))

the result:

A relation r
name age
Channing 38
Lance 37

select tuples from r where age=37
name age
Lance 37

select the name field from r using a projection
name
Channing
Lance

A relation r2
extra more
stuff 100

join r and r2
name age extra more
Channing 38 stuff 100
Lance 37 stuff 100

select tuples from joining r and r2 where age is 38
name age extra more
Channing 38 stuff 100

Conclusions

The main thing that struck me is that for the first time since switching from electronics and physics, I felt like I was engineering a solution. There is an elegance and robustness to Scheme that isn’t there with Java, Ruby or any other language I have used to date.

OK, I have only been looking at Scheme for a few months, and experimenting a few days, but there have been a number of extremely clever people I’ve met over the years that have said “if only we could use Lisp this would be so much simpler”. I’ll report back later about my progress with Scheme.