2010/04/26

Enhanced queue

util.queue module (ref:util.queue) has been completely rewritten for 0.9.1.

The main motivation is to support thread-safe queue (mtqueue). Last couple of years I had quite a few projects that needed to fully utilize multiple cores, and for almost every one of them I ended up writing some kind of thread-safe queue. It is a simple but robust way as a synchronization primitive. Naturally the feature is a strong candidate for Gauche to provide natively.

Writing a thread-safe queue is seemingly a simple task. Yet it took some time for me to come up an API I feel right.

Just protecting access to a queue by a mutex makes the queue thread-safe, but it doesn't make the queue usable for synchronization; we want a consumer thread to block when it finds the queue is empty, and to resume automatically as soon as some data is available in the queue.

Providing a simple-minded thread-safety, that just protects access by a mutex, isn't a good strategy. It doesn't help much to build synchronization operations, since the latter needs a condition variable to cooperate with the mutex of the queue. Such a strategy is a dead-end of abstraction; it does abstract something, but does not useful to build more abstractions on top of it.

So, we use a condition variable and let a consumer thread block on an empty queue. Is that enough? Not really.

If a producer thread fails for some reason, the consumer thread would wait indefinitely. It is usually unacceptable in the production code; the consumer thread must detect abnormality and try to recover, report to supervisor, or shut itself down gracefully. There's also a situation that a consumer thread fails; in such case a producer thread would just keep pushing the data into the queue until it exhausts memory, which is also undesirable.

I explored some options. In one option, a queue had low and high water marks, and a callback was called when the length goes below the low mark or above the high mark, and it adjusted the pace of either a consumer or a producer threads. It worked for the project, but I felt it too complicated for general use.

Finally I ended up on a simple concept of timeouts, plus optional upper-bound of the queue length. The API is parallel to other timeout-able thread operations so that it's easy to remember, and I think it is general enough so that more sophisticated stuff can be built on top of it.

Here's an outline of synchronizing mtqueue operations. See the manual in svn trunk if you are curious to know the details.

• make-mtqueue :key max-length
  Returns a thread-safe queue, with optional upper bound of the queue length.
• dequeue/wait! mtqueue :optional (timeout #f) (timeout-val #f)
  Pop an item from mtqueue, or block if the queue is empty, with optional timeout. The semantics of timeout and timeout-val are the same as thread-join! etc. (ref:thread-join!).
• enqueue/wait! mtqueue obj :optional (timeout #f) (timeout-val #f)
  Push obj into the queue, or block if the queue has maximum number of elements, with optional timeout.

Note that there are also dequeue! and enqueue! that do not block. They work on both mtqueue and normal (non-thread-safe, but cheap) queue. dequeue! throws an error by default if the queue is empty, though you can suppress it by providing a fallback value.

Tags: 0.9.1, util.queue

2010/04/26

Better REPL?

Gosh's default REPL provides bare minimum features. I almost always run gosh inside Emacs and usually it's fine, but sometimes I do feel it can be better.

So I'm experimenting ideas here: http://gauche.svn.sourceforge.net/viewvc/gauche/Gauche-scripts/trunk/xrepl/

Here are some stuff I have. I'll use it for a while to see if it's worth to be included into gosh or not. Other ideas and feedbacks are welcome.

Prettyprinting the result

It has rudimental pretty printer (which is a bit dumb; it may take exponential time for large S-expr that I need to fix). Ideally pretty printer should be a part of Gauche, integrated with built-in format etc.

gosh> (call-with-input-string
          (values-ref (http-get "blog.practical-scheme.net" "/gauche") 2)
        (cut ssax:xml->sxml <> '()))
(*TOP*
 (html
  (head
   (title "Gauche Devlog")
   (base (|@| (href "http://blog.practical-scheme.net/gauche")))
   (link
    (|@| (type "application/rss+xml") (title "RSS") (rel "alternate")
     (href "http://blog.practical-scheme.net/gauche?c=rss")))
   (link (|@| (type "text/css") (rel "stylesheet") (href "blog.css")))
   (link (|@| (type "text/css") (rel "stylesheet") (href "gauche-devlog.css"))))
  (body
...

History

Accessing recent evaluation results. This feature has been sitting long in my wishlist, but I couldn't make up my mind of what symbols I would use; CL uses *, **, ***, ... but in Scheme * would conflict with the built-in function. I finally decided to adapt Clojure's convention; *1 refers to the last evaluated result, *2 for the second last, etc.

gosh> *1
(*TOP*
 (html
  (head
   (title "Gauche Devlog")
...
gosh> (length (cadr *1))
3

The procedure *history prints the list of history.

*1, *2, ... only keeps the first value of the result(s). In case if we have more than one values, *1+, *2+, ... keeps the list of values.

If the last evaluation ends as an error, the condition object is bound to *e.

gosh> (car 3)
*** ERROR: pair required, but got 3
Stack Trace:
_______________________________________
  0  (with-error-handler (lambda (e) (let ((e e)) (%guard-rec e e (else ...
        [unknown location]
gosh> *e
#<error "pair required, but got 3">

Shell-like commands

You can type shell commands by leading it with a comma:

gosh> ,cd ~/src/Gauche
/home/shiro/src/Gauche
gosh> ,ls
AUTHORS       README          configure.ac       ltmain.sh
COPYING       VERSION         configure.ac.orig  m4/
ChangeLog     acinclude.m4    doc/               missing*
DIST*         aclocal.m4      examples/          mkinstalldirs*
DIST_EXCLUDE  config.guess*   ext/               rpmfiles-common.txt
Gauche.spec   config.log      framework.sh*      rpmfiles-encoding.txt
HACKING       config.rpath*   gc/                rpmfiles-gdbm.txt
INSTALL.in    config.status*  gc.diff            src/
Makefile      config.sub*     install-sh*        test/
Makefile.in   config.threads  lib/               test.record
NEWS          configure*      libsrc/            winnt/
gosh> ,make -j
for d in gc src lib ext doc; do (cd $d; make all); done
make[1]: Entering directory `/home/shiro/src/Gauche/gc'
...

Sometimes I'm too lazy to switch from *scheme* buffer to *shell* buffer (or, more like that I forget to switch and am annoyed by getting 'unbound variable: ls').

It would be nicer if I can easily grab the shell output into Scheme variable, and feed the content of Scheme variable into shell commands.

Smarter (or verbose) error handling

I'm not sure I'll keep this one, but giving a try.

"." isn't in *load-path* by default, for the obvious security reasons. But sometimes I forget to type "./foo.scm" and being annoyed, for I know foo.scm in the current dir is safe. So, here's a little help...

gosh> (load "t.scm")
*** REPL: Cannot load file "t.scm" in *load-path* ("../lib" "../libsrc" "../src" "/usr/share/gauche/site/lib" "/usr/share/gauche/0.9.1_pre1/lib" "/usr/share/gauche/0.9/lib" "/home/shiro/src/Gauche-scripts/xrepl/")
But you have the file under the current directory.
Do you want to add "." in *load-path*? (y/n): 

This is actually implemented in more general "error filter" framework. When REPL gets an error, a series of registered tests are run, and if there's a match, an associated action is invoked.

This kind of thing may be too annoying (in fact, I don't even like CL implementations entering the debugger on error by default.) But I'll see.

Tag: repl

2010/04/26

ERR5RS Records and beyond

Release 0.9.1 will include support for ERR5RS Records (srfi:99). It also supersedes the existing srfi-9 records (srfi:9).

The srfi-9 record implementation as of Gauche 0.9 is just a thin wrapper of Gauche's class facility. That is, a record type that has slot x, y, z is actually an ordinary Gauche class with slot x, y, z. It has no advantage to, and less features than Gauche's object system, except that it is portable.

In 0.9.1 I make records a bit more special. A record type is still a class, but using MOP, it is customized to take advantage of inflexibility of records---we can make it more efficient. So in some places records can be better choice than classes.

First of all, I don't make record types obey the class redefinition protocol. If you define a record type and bound to a variable which previously bound to another record type, then the variable is just overwritten; the old type and the new type don't have any relation; and instances of the old type remains as they are, instead of being upgraded to the new type.

This allows us to allocate a record instance as a flat array, instead of a header pointing to a value array. We can also pre-calculate offsets of slots for accessors and modifiers. I'm also planning to enable some aggressive inlining so that record accessors and modifiers are inline expanded to be as fast as vector access. (The inlining part has not implemented yet. But it is a fun MOP twiddling to adapt the record semantics into Gauche's class system).

Secondly, I extended ERR5RS and added a "pseudo record type", which treats other type of aggregates such as lists or vectors as if they are records. For Common Lisp users, it is like (:type list) or (:type vector) option of defstruct. Here's an example:

gosh> (use gauche.record)
#<undef>
gosh> (define-record-type (point (pseudo-rtd <vector>))
        #t #t (x) (y) (z))
point-z-set!
gosh> (make-point 2 3 4)
#(2 3 4)
gosh> (point-x (make-point 2 3 4))
2
gosh> (let1 p (make-point 2 3 4) (point-z-set! p 9) p)
#(2 3 9)

The point record type inherits a pseudo record type returned from 'pseudo-rtd, which in this case a record type that uses a vector as a storage. The constructor make-point returns a vector. Accessors and modifiers takes a vector.

Besides the efficiency (vector access is very fast in Gauche), I see another advantage of this; it is less binding. Suppose your library defines concrete point record type, and ask users to send the data in points through API. If the user module have different representation of points, it have to convert every points back and forth to call your library. If your library exposes points with pseudo type, on the other hand, the user can simply use vectors; which can be interpreted in may other ways.

Currently I'm only testing with vector-backed records, but the plan is also enable uniform-vector backed ones---then it will be more attractive since uniform vectors can be directly passed into GL layer (via Gauche-gl).

Finally, a small addition to the srfi; I made the record accessor work with generalized set!, if the slot is mutable.

gosh> (define-record-type pare #t #t (kar) (kdr))
pare-kdr-set!
gosh> (define p (make-pare 1 2))
p
gosh> (set! (pare-kar p) 100)
#<undef>
gosh> (pare-kar p)
100

Another idea I'm pondering is to define a default printer to records, so that it prints out its slot values something like CL's struct.

Tags: 0.9.1, gauche.record, srfi-9, srfi-99

2010/04/25

About this blog

As the release cycle of Gauche slowing down (partly because of wider adoption of Gauche in production environments), I find it getting more difficult to cram explanations of all the new features into release notes, especially it can be months to write release notes after the feature is actually implemented.

A blog seems a good way to fill the gap; I can describe things in detail as I'm working on it, and it will eventually be a good collection of documents. I may also pick up Lisp/Scheme topics in general, or write "how to write it in Gauche" type of articles.

As you might expect, this blog is a customized WiLiKi Wikiengine running on Gauche. I'll include this blog utility in the next WiLiKi release.

Tag: Misc