keep plaiyng

Recently, I joined a group of fringe languages fanatics (especially scheme and lisp, but smalltalk is welcome to, as well as haskell and so).

The first meeting was 2 weeks ago, and we talked about many things (well, I mostly listened, but...). Jos Koot explained us some usages of plt-redex, and made a lightning introduction to lambda-calculus. Jao said that in the next session, he would be explaining us a bit of Factor (a concatenative programming language (forth derivative)) , and probably, there will be some lightning talks.

After the presentations and the main talk, we decided it'd be good to make reading groups to examine cool books related to lisp/scheme/whatever.

Some proposed SICP, some others LiSP , but in the end, we chose to start with PLAI.

I started it last week, and red about 30 pages without many problems. Everything seemed sane. Then, when I decided to try it, I faced some problems, that other scheme newbies might have too. So let's try to fix them :) .

plt-scheme and DrScheme.

First things first. To try the codes there, you should install the complete plt-scheme (mzscheme alone won't work). That wasn't a problem for me because I'd already installed to try fluxus, but as there wasn't a proper package for vectorlinux, I decided to start packaging it (at the end, rbistolfi packaged it, as his comp is more powerfull than mine, and it's a looong compilation).

We decided to compile it with --enable-shared to make fluxus 'compatible' with it.

When I tried to use the sample codes in the book..... FAIL. define-type nor type-case existed in my plt-scheme. What I needed to do was install plai libraries through a simple require.

(require (planet plai/plai:1:3))

Reading the book

While reading the book, at first all made sense until I found this:

<wae> ::= <num>
       | {+ <wae> <wae>}
       | {- <wae> <wae>}
       | {with {<id> <wae>} <wae>}
       | <id>


(define-type WAE
[num (n number?)]
[add (lhs WAE?) (rhs WAE?)]
[sub (lhs WAE?) (rhs WAE?)]
[with (name symbol?) (named-expr WAE?) (body WAE?)]
[id (name symbol?)])

How come in the BNF with had only 2 arguments (the first one containing 2 elements), and when the author defines 'with' in scheme, it has 3?

The key to this is reading carefully the first chapters, when the author says that it's our job to modify the parse function to adequate the code to be properly evaluated. In fact, I was understanding the whole thing wrong, thinking that define-type was what should constrain my syntax, but it turned to be the other way around.

When I execute :

{calc {parse '{with {x 4} {+ x x} }}}

What I'm doing is calling parse first, so I have the full power to massage the 'parse' input and output it in a way calc can use. calc is the function that uses type-case, so it's the function that must obey the constraints defined at define-type.

Btw. I'm not passing all the tests for the 3rd chapter but only the first 4. Anyway, I think I just understood a new concept and the whole flux of what must go where.

Now the (unfinished) code. for the WAE parser (3rd Chapter)

(define-type WAE
[num (n number?)]
[add (lhs WAE?) (rhs WAE?)]
[sub (lhs WAE?) (rhs WAE?)]
[with (name symbol?) (named-expr WAE?) (body WAE?)]
[id (name symbol?)])

(define (parse sexp)
(cond
 [(number? sexp) (num sexp)]
 [(symbol? sexp) (id sexp)]
 [(list? sexp)
  (case (first sexp)
     [(+) (add (parse (second sexp))
                (parse (third sexp)))]
     [(-) (sub (parse (second sexp))
               (parse (third sexp)))]
    [(with) (with (first (second sexp))
                  (parse (second (second sexp)))
                  (parse (third sexp)))])]))

(define (subst expr sub-id val)
(type-case WAE expr
         [num (n) expr]
         [add (l r) (add (subst l sub-id val)
                         (subst r sub-id val))]
         [sub (l r) (sub (subst l sub-id val)
                         (subst r sub-id val))]
         [with (bound-id named-expr bound-body)
               (if (symbol=? bound-id sub-id)
                   expr
                   (with bound-id
                         named-expr
                         (subst bound-body sub-id val)))]
         [id (v) (if (symbol=? v sub-id) val expr)]))

(define (calc expr)
(type-case WAE expr
 [num (n) n]
 [add (l r) (+ (calc l) (calc r))]
 [sub (l r) (- (calc l) (calc r))]
 [with (bound-id named-expr bound-body)
        (calc (subst bound-body
                      bound-id
                      (num (calc named-expr))))]
 [id (v) (error 'calc "free identifier")]))

cya! And Thanks to all flibers!