2011/07/10

Quasiquoting

As of 0.9.1 Gauche doesn't handle quasiquote patterns something like this:

gosh> ``(,,@(list 1 2))
`(,,@(list 1 2))

It may be arguable a bug, or an unspecified behavior in R5RS. The outer-level quasiquote should expand unquote-splicing, and that should produce (unquote 1 2); however, quasiquote syntax in R5RS does not allow such pattern, so the resulting form wouldn't be a valid quasiquotation. It doesn't explain the above result, but if it's an error in R5RS term, anything can happen. (In fact, the result wasn't intended at all; it was just an outcome of failing recognition of the pattern.)

Still, it is allowed to have (unquote 1 2) as a pure datum, it may be more reasonable that ``(,,@(list 1 2)) expands into `((unquote 1 2)).

R6RS solved this ambiguity by allowing unquote to have multiple arguments. Since it is upper compatible to R5RS, I decided to implement R6RS behavior in Gauche. Now you get this:

gosh> ``(,,@(list 1 2))
`((unquote 1 2))

And this:

gosh> `((unquote 1 2))
(1 2)

★ ★ ★

While thinking about this, I found a difference between Scheme and CL about quasiquoting that I was not aware before.

In Scheme, `a, ,a, ,@a are merely a reader-level abbreviation of (quasiquote a), (unquote a) and (unquote-splicing a), respectively. The real semantics of quasiquoting is defined in terms of the latter S-expressions.

In CL, quasiquoting (bakcquotes) are defined in reader level. That is, comma-datum doesn't need to be an abbreviation of something like (unquote datum) or (comma datum). It doesn't need to have list equivalents at all. The comma and comma-atmark can be directly parsed by the reader, and transformed to whatever piece of code that produces the desired result.

It is not obvious in a simple case, but see the followings:

In Allegro:

cl-user> `'`(,,(cons 1 (cons 2 nil)))
'(excl::bq-list (1 2))

In CLisp:

[6]> `'`(,,(cons 1 (cons 2 nil)))
'(LIST (1 2))

This means the inner backquote form are interpreted rather liberally.

On the other hand, I believe in Scheme this is the only possible result (modulo printing `a or (quasiquote a) etc.)

gosh> `'`(,,(cons 1 (cons 2 '())))
'`(,(1 2))

A practical outcome of this difference is that, in CL, you cannot write an S-expression with a comma without corresponding backquote.

In Scheme, you can write a macro that implicitly inserts quasiquote:

gosh> (define-syntax implicit-qq
        (syntax-rules ()
          [(_ x) (quasiquote x)]))
#<undef>
gosh> (implicit-qq ,(+ 1 2))
3

IIUC, you can't do this in standard CL, since the expression (implicit-qq ,(+ 1 2)) raises error at the reader, before the form gets passed to the macro expander.

Tags: quasiquote, r5rs, r6rs, CommonLisp

2011/07/09

Not like the old-school Lisp atoms

Ah it's been long since the last entry. It's not that Gauche development is staggered; the thing is, I run several development threads concurrently, using local topic branches, and it is hard to pick a topic that can make a complete entry with conclusion.

Nah, too much excuses. From now on, I dump here whatever thoughts and experiments I did, slow but constantly, even without a nice conclusion.

Ok, so let me pick up where I left... the last entry was March 16. The next thing I did was to commit the support of atoms.

No, not that traditional Lisp atoms which mean something that's not a cons. Having atomp was once important to explain how Lisp worked, but these days, with so many different datatypes, I don't think having a term for non-cons objects is important. That usage should become a history.

These days, more important atomic property is that something be atomic with regard to concurrent execution. To confess, I steal the term from Clojure. Though Gauche doesn't abstract concurrent threads nor isolate mutable operations so much as Clojure does, I do find some recurring patterns I use while writing concurrent code in Gauche, and this is one of them.

An atom here is a wrapper to bundle one or more objects that needs to be updated atomically. It is available in gauche.threads module. The following creates an atom with two vectors.

  (use gauche.threads)
  (define a (atom (vector 1) (vector 2)))

  a => #<<atom> 0x17467e0>

To access those vectors safely, you pass a procedure to atomic.

  (atomic a (lambda (v0 v1) ...do whatever with v0 and v1...))

No other thread can access/modify the atom a until atomic returns.

Gauche's builtin hashtable is not thread-safe. I was always wondering whether I should provide a separate thread-safe hashtable type, or provide a generic support to allow exclusive access to any objects, like Java's synchronized mechanism. The former would explode the number of primitive datatypes (how about thread-safe treemap? thread-safe sparse hash? &c.) The latter is cleaner, but difficult to implement efficiently (especially, think about allow synchronized on any pair!)

Now atoms can be used to provide mutable objects exclusive access. Just say (atom (make-hashtable 'eq?)), and then wrap any access to the table by atomic. I expect that most cases of trivial use of <mutex> can be replaced by atoms.

Not only wrapping mutable objects, but atom itself can be a mutable objects with synchronization. You can replace its wrapped value by atomic-update!.

  (define b (atom 0))

  (atomic-update! b (cut + 1 <>))

This makes an atom b works as a counter with mutex. If the atom wraps N values, the update procedure should be N-in N-out procedure. To extract the value, a convenient procedure atom-ref can be used.

  (atom-ref b)

You may notice that if you retrieve a mutable object wrapped by atom by atom-ref, you can modify it outside of protection. Atoms are not intended to prohibit you from doing dangerous things; they just make it easier to do things safely rather than error-prone ways.

Finally but importantly, those atom primitive consistently takes optional timeout and timeout-val arguments.

  (atomic a (^(x y) ... #t) 10.0 'timeout)

This returns #t if we can access the atom successfully, but if we cannot obtain a lock for 10.0 seconds, it gives up and returns timeout. I find it indispensable to write a robust code. The semantics of timeout and timeout-val is the same as other thread primitives.

Tags: atom, gauche.threads, Concurrency

2011/03/16

Benchmarking utilities

I just expanded the features of gauche.time module (ref:gauche.time). Now it has convenience procedures to run benchmarks and compare results.

gosh> (time-these/report
       '(cpu 5.0)
       `((native-map! . ,(cut map  (cut + 1 <>) input))
         (scheme-map! . ,(cut maps!(cut + 1 <>) input))
         (native-map  . ,(cut mapa (cut + 1 <>) input))
         (scheme-map  . ,(cut maps (cut + 1 <>) input))))
Benchmark: ran native-map!, scheme-map!, native-map, scheme-map, each for at least 5.0 cpu seconds.
  native-map!: 5.267 real, 5.250 cpu (5.230 user + 0.020 sys)@86.86/s n=456
  scheme-map!: 5.268 real, 5.260 cpu (5.260 user + 0.000 sys)@85.55/s n=450
   native-map: 5.348 real, 5.330 cpu (5.330 user + 0.000 sys)@63.41/s n=338
   scheme-map: 5.338 real, 5.340 cpu (5.330 user + 0.010 sys)@62.92/s n=336

              Rate native-map! scheme-map! native-map scheme-map
  native-map! 87/s          --       1.015      1.370      1.380
  scheme-map! 86/s       0.985          --      1.349      1.360
   native-map 63/s       0.730       0.741         --      1.008
   scheme-map 63/s       0.724       0.735      0.992         --
#<undef>

If you know Perl, the output would look familiar. Yes, I blatantly stole the idea of Perl's Benchmark.pm. It still lacks the features such as cache control and flexible output formatting seen in Perl, but I'm happy to have this in the standard Gauche toolbox.

The rest of a little story I ended up having this.

When I add libraries to Gauche, I tend to make them as a set of relatively simple, solid, and mutually orthogonal components, rather than specialized, complex chunk of code each of which is designed for a particular application.

I guess that's rooted from the Unix culture and/or functional programming, and not very uncommon tendency. It is natural to expect it to be easy to assemble a new tool with those simple, orthogonal components when I face a new problem. Probably as the side effect of the tendency, I tend to be overly skeptical to a tool that is specialized to handle a single specific problem.

When I began thinking of enhancing gauche.time (I had been running benchmarks for optimization for some time then, and was getting bored with the tedious process), I started off with functional components that could be combined to achieve common task of benchmarking.

It took not long to realize that I couldn't decide a good interface in the intermediate layer, though. If I kept it simple, I feared there would be cases that it was not enough and the whole suite should be scrapped. If I made it general enough, the interface looked too complicated for typical usage.

I stepped back and thought what I wanted to do at the beginning. Basically almost always the task consists of running several pieces of code, measure their speed, and compare. Perl has a module specifically designed for that, and it looked to do just what I want. And it seemed that it's straightforward to copy its main features.

It could be constructed with orthogonal compoents; e.g. creating the layout of comparison matrix could be a separete component. But I don't understand the problem enough to design a clean interface to make it independent. So I hard-coded that.

I may rewrite them in future, once I have a solid idea on how to design generic text table formatting API. In the meantime, it is more useful to shortcut and have some working code, than wait for clean, neat, and composable components. Specialized tools aren't necessarily bad, if the problem is well defined and common enough.

Here are several procedures added for benchmarking. See the git repo for the details.

• time-this : benchmark single code in thunk. returns <time-result> object.
• time-result+, time-result- : operations on <time-result>.
• time-these : benchmark several code to compare and returns list of results.
• report-time-result : format the result of time-these.
• time-these/report : combination of above two.

Tags: gauche.time, Perl, benchmarking

2011/02/03

Bitten by floating point numbers again

When I read about PHP hanging while parsing 2.2250738585072011e-308, I did what most language implementers must have done---typed in the number to the Gauche prompt. Gauche wasn't vulnerable to this number. Good.

It is reported that PHP problem was that Intel's 80bit extended floating point calculation was used where IEEE double precision calculation should have been used. Like PHP, Gauche refers to Clinger's paper (PS), but ours is rather naive implementation of Clinger's AlgorithmR and using exact integer arithmetic, thus we have nothing to do with extended precision calculation.

So when I heard about Java hangs reading 2.2250738585072012e-308 shortly after, I didn't bother checking. Ah the same problem again.

Well, it wasn't.

Jens Thiele reported that Gauche had the same issue as Java.

gosh> 2.2250738585072012e-308
;; => hangs

Let's see what is happening. For simplicity we only consider positive numbers, but the discussion applies to negative numbers as well by reverting comparisons (e.g. less than -> greater than).

The floating point number reader must map the input real number to the closest IEEE double precision number ("IEEE double" from now on). In most cases, each IEEE double covers the region of real numbers between 1/2 LSB greater than and 1/2 LSB less than the exact real number it represents, as shown below.

If the input falls on the exact center of two IEEE doubles, we use round-to-even rule.

There are exceptions on the number 2^m. The adjacent IEEE double below 2^m is closer than the one above, since we switch exponent below this boundary, so the numbers below it have greater precision. Those IEEE doubles on the boundary covers between 1/2 LSB greater than, but only 1/4 LSB less than, the exact number it represents. Clinger's paper, and thus Gauche, correctly account this boundary case.

However, there is one exception among these exceptions: The minimum normalized number, 2^(-1022). In this case, the adjacent IEEE double below is just as far apart as the one above, since we don't have more precision anymore.

Our implementation of AlgorithmR missed this condition, which created a gap in the coverage.

The number 2.2250738585072012e-308 falls into this gap. When the algorithm refines approximation, it thinks the input number is too small to round to 2^(-1022), so it decreases the estimate. Then it finds the input is too large to round down, so it increases the estimate. Repeat ad infinitum.

This anormality only occurs here, since no denormalized numbers satisfy our boundary condition check for the 2^m cases.

The fix is just one line.

--- src/number.c        (revision 7350)
+++ src/number.c        (working copy)
@@ -3543,6 +3543,7 @@
         case -1: /* d2 < y */
             if (Scm_NumCmp(m, SCM_2_52) == 0
                 && sign_d < 0
+                && k > -1074
                 && Scm_NumCmp(Scm_Ash(d2, 1), y) > 0) {
                 goto prevfloat;
             } else {

Tag: Flonums

2011/01/07

Queue of zero length

Does it make sense to have a queue whose maximum length is zero? I thought it didn't, so when I wrote <mtqueue> (ref:util.queue) I defined the range of mtqueue-max-length be one or more. (Zero means the queue has unlimited length, which is a bit kludgy in retrospect). A queue with zero max length would be always empty and full. It seemed that it'd be no use.

Now it occurs me that actually it may be useful as a synchronization device.

The multi-thread queue <mtqueue> can be used to synchronize consumer threads and producer threads. A consumer thread blocks on dequeue/wait! when there's no data in the queue, and unblocks when some data is put in the queue. A producer thread blocks on enqueue/wait! when the queue is full, and unblocks when the data in the queue is consumed and there is some room in it. So, an <mtqueue> with max-length == 1 can be used as a synchronizing variable, like MVar in Haskell.

If we had an <mtqueue> with max-length == 0, how would it work? A possible behavior would be as follows: A consumer thread would block on dequeue/wait! unless there's a producer thread waiting on enqueue/wait!. A producer thread would block on enqueue/wait! unless there's a consumer thread waiting on dequeue/wait!.

That is, it allows passing data from the producer to the consumer directly, without putting the data into a buffer.

It can be useful, since once a piece of data is put in the queue, it is left untouched until a consumer consumes it. When there's something happens in consumer threads, such that all of them are taking extremely long computation, the queued data will be held in the queue indefinitely. If you want to guarantee that a piece of data is either processed timely or otherwise timeout, you need to put a separate logic to watch the queue.

With a zero-length queue, the producer can set timeout, so it is easy to implement the behavior to timeout when consumers are busy.

This is a kind of special interpretation of the behavior of <mtqueue>. With a simple definition---enqueue/wait! blocks when the queue is full, and dequeue/wait! blocks when the queue is empty---a straightforward interpretation is that both enqueue and dequeue always block and do nothing useful. So it is arguable that we should provide a different data structure for this non-buffering synchronization.

Besides, the current implementation interpretes zero max-length as "unlimited length". It would be an incomaptibile change if we support zero-length queue.

I'm still undecided, but for now, I feel non-buffering synchronization is a natural extension for the behavior of <mtqueue> with zero max-length, and will be better to have it than to have different synchronization primitives. Since <mtqueue> was just introduced in 0.9.1, it may be not too late to change it.

However, I might be overlooking something. I'm open for discussion. Also I'm curious if other implementations/languages have this non-buffering synchronization primitives.

(Added on 2011/01/08 01:17:47 UTC): Rui pointed me Java's SynchronousQueue. This is probably the same as I expect in zero-length mtqueue. In Java it appears its tradition to separate classes if implementations differ, but in Gauche I think it's more natural to implement it as an extention of existing <mtqueue>.

Tags: util.queue, mtqueue, threads