SourceForge.net 2007 Community Choice Award

It's time to vote for your 2007 Community Choice Award at SourceForge. If you like SchemeScript, go to the project page and click on the "Nominate this project" link! (You must have a sourceforge account to do so...)

Tuple space implementation - Implementing the client API

In a previous post, I designed the client API for an implementation of tuple spaces in Gambit Scheme/Termite. In this post, we will see how to implement the API.

Low-level API

As described in the previous post, the client API is composed of three macros:

(tspace-put! (tag expr-1 expr-2 ... expr-n))
(tspace-read (tag pat-1 pat-2 ... pat-n)
  expr-1 ... expr-n)
(tspace-get! (tag pat-1 pat-2 ... pat-n)
  expr-1 ... expr-n)

The approach taken here is to expand calls to these macros to calls to a lower-level API that sends requests/messages to the tuple space server (which could be on a different node or even a different machine on the network) using the basic Termite procedures. This low-level API is not meant to be called directly by a client application. It's a private API.

This low-level API is composed of three procedures, one for each of the macros:

(tspace:put! tag fields)
(tspace:read tag template)
(tspace:get! tag template)

We will see what a template can be below.

Implementing this low-level API is straightforward. If we assume that the server process is registered globally under tuple-space (with the register procedure), the last two procedures can be implemented like this:

(define (tspace:read tag template)
  (!? (resolve 'tuple-space) `(read ,tag ,template)))

(define (tspace:get! tag template)
  (!? (resolve 'tuple-space) `(get ,tag ,template)))

Note the use of the !? procedure calls. They are used instead of the ! procedure because we want to send a message to the server and block until we get a response. !? means "send and wait for a response".

The call to resolve simply tries to get the process object bound to the globally defined name given. (We won't handle exceptions and errors right now.)

The first procedure looks a little more complicated, but not that much:

(define (tspace:put! tag fields)
  (! (resolve 'tuple-space) (list (self) (make-tag) `(put ,tag ,fields))))

In this procedure, we explicitly pass (self) and a tag, a unique identifier. This is only to make the put message have the same structure as the read and get! messages. The !? procedure sends them automatically for us.

Implementing tspace-put!

Implementing the tspace-put! macro is trivial. In fact, we implement it as a macro simply to be more consistent with the syntax of the tspace-read and tspace-get! macros. Here is the code:

(define-macro (tspace-put! object)
  (match object
    ((tag . fields)
      (where (list? fields))
     `(tspace:put! ,tag (list ,@fields)))
    (else
     (error "invalid object in tspace-put! - " object))))

(I won't use R5RS syntax-rules macros here. They don't mix well with the rest of the Gambit system.) The match expression ensures that object is a list of at least one element.

"Don't care" variables

In calls to the tspace-get! and tspace-read macros, the patterns can be variable names (symbols) or constants. A special symbol, (_, the underscore) can also be used to indicate that the corresponding field can hold any value, and that we are not interested in that value. That's what we call a "don't care" variable.

From the perspective of the low-level API, all the pattern variables are "don't care" variables. In other words, it does not make sense to send the variable names to the server, as they are only used to name some of the values in the matched tuple. This means the tspace-read and tspace-get! macros will first have to replace all the variable patterns with "don't care" variables.

Implementing get! and read

Both macros differ only in the name of the low-level API procedure that must ultimately be called. We will thus abstract a little bit and defer the hard part of both macros to an auxiliary procedure (not a macro):

(define-macro (tspace-read pattern . body)
  (tspace-retrieve pattern body 'tspace:read))

(define-macro (tspace-get! pattern . body)
  (tspace-retrieve pattern body 'tspace:get!))

(In addition to saving us from some copy-paste, relying on an auxiliary procedure has another advantage: the procedure can be easily tested since it's not a macro.)

Here is the definition of the tspace-retrieve procedure:

(define (tspace-retrieve pattern body-list retriever-name)
  (match pattern
    ((tag . fields)
     (where (list? fields))
     (let ((variables (filter pair?
                              (map (lambda (object index)
                                     (if (and (symbol? object) (not (eq? '_ object)))
                                         (cons object index)
                                         #f))
                                   fields
                                   (iota (length fields)))))
           (fields    (map (lambda (object)
                             (if (symbol? object)
                                 '(quote _)
                                 object))
                           fields))
           (tuple-var (gensym)))
       `(let ((,tuple-var (,retriever-name ,tag (list ,@fields))))
          (let ,(map (lambda (var/index)
                      `(,(car var/index) (list-ref ,tuple-var ,(cdr var/index))))
                    variables)
            ,@body-list))))
    (else
     (error "invalid tspace pattern: " pattern))))

The first let extracts the variables from the patterns together with the corresponding index in the template, builds the template that will be send to the server, and creates a new symbol to ensure some hygiene. The body of the let builds the resulting code.

Here is an example of using this procedure. Calling

(tspace-retrieve '('tag x _ 1) '((+ x 1)) 'tspace:read)

yields

(let ((#:g0 (tspace:read 'tag (list '_ '_ 1))))
  (let ((x (list-ref #:g0 0)))
    (+ x 1)))

Note that this makes the assumption that the value returned by tspace:read is a list (the list of the tuple fields). That's an implementation choice. We could have used vectors instead. But as long as this representation does not leak outside of the low-level API and the generated code, that's ok.

That's it for today. Next time, we'll see how to implement the server. This will involve a lot of interesting design decisions.

SISC debugging with SchemeScript

On the SISC users list, Daniel Sadilek explains his solution to debugging SISC code with SchemeScript:

I found a workaround:

(define-syntax debug
 (syntax-rules ()
   ((_ var ...)
    (begin
      (print "Debugging. Available lexical bindings: " '(var) ...)
      (let ((child-env (make-child-environment (interaction-environment))))
        (putprop 'var child-env var) ...
        (with-environment child-env (lambda () (repl)))
        (print "Debugging ended."))))))

This special syntactic form can be used like this:

(define (f x)
 (let ((sq (* x x)))
   (debug x sq)
   (+ sq sq)))

Btw, I use the SchemeScript IDE and really like the editing style that is made possible with the above debug-form. You can put (debug some-vars) inside a procedure and execute it (or some other procedure that calls it). Then, with access to the local variables, you can write your code inside the procedure -- right in place -- and evaluate by pressing Ctrl+Enter. If finished, you exit the debug REPL.

Gambit-C has (IMO) a much better debugger than any other free Scheme implementation. But the editing/debugging style described above is exactly what I had in mind when developing SchemeScript and what makes it comparable to Emacs in terms of integration with the Scheme system.

Yahoo Pipe for Gambit/Termite

I have created a Yahoo Pipe for Gambit/Termite related articles. (The resulting feed is displayed at the right of this page.)

What? Another packaging system for Scheme?

Manuel Serrano has just release Bigloo 3.0a. Its most important new feature is a new packaging system, ScmPkg. Yes, you read correctly: a new packaging system!

It is not related in any way to the Scheme Now! effort, even if it shares its initial goal and philosophy: an implementation-neutral package distribution system. (Even if, in fact, Manuel was one of the early Snow designers.) Were we really in need of another one?

Instead of uniting the Scheme community, these two competing efforts will help balkanize it more. That's my feeling. Who will take time to write packages for both Snow and ScmPkg? And R6RS, and Egg, and Planet, and ...

But you know what? I DON'T MIND! Me, as a Scheme developer, I (usually) don't want to port my code to a dozen implementations. Even two implementations. I use Gambit, that's all. Or Kawa. It depends on the project, the target platform. But once I have chosen an implementation, I stick to it. Porting a library to different implementations has a cost. A huge cost that I'm not willing to pay.

So we should stop worrying about compatibility. We should go write useful applications in our Scheme dialect of our choice. Create success stories in Scheme. (Where are they, btw, the Scheme success stories? I know of Erlang success stories, Common Lisp success stories. But Scheme ones? Do you know one?)

In the long run, it's not the core language that will make a difference. It's its use in the implementation of a truly unique and innovative platform or framework for developing amazing applications. Ruby would not be as successfull as it is without Rails. Erlang has Mnesia and Yaws. Even Java would not be so popular if it weren't for the J2EE specifiation and tools like Eclipse.

In my case, I bet on Gambit-C, JazzScheme, and Termite. This trio has the potential to have a strong influence on the Scheme community. It has unique and compelling features for the development of innovative products.

And Snow? I see it as a repository of Gambit packages/libraries. Nothing more.

Parallel map with Termite

In Parallel Map Beer Song in Erlang, Bill Clementson gives an implementation of pmap (a parallel map) in Erlang.

Here is an implementatin of pmap in Termite Scheme, as given by Marc Feeley on the Gambit mailing list:

(define (pmap f lst)
   (let ((parent (self)))
     (map (lambda (pid)
            (recv ((,pid reply) reply)))
          (map (lambda (x)
                 (spawn (lambda () (! parent (list (self) (f x))))))
               lst))))