Semi-coherent rambling

I need to post more frequently, and if I wait for my thoughts to become coherent it may be quite some time.

I wanted to say something about abstraction, so I was thinking about some of the fundamental abstractions computer scientists use. What's really happening (for some sense of ‘real’) in the computer is some very complex electromagnetic field interactions. But no computer hacker I know sits down at the terminal and starts programming from Maxwell's equations. There are better ways to think about what a computer does.

Maybe the most basic abstraction is what I'll call primitive ontological abstraction. We'll take a fairly stable pattern of currents and we'll call that a ‘number’ or a ‘byte’ or some such thing. A circuit that can maintain the pattern we'll call a ‘register’, so we can talk about ‘register EAX’ holding ‘the value 27’ or somesuch thing. Here we abstracting away the idea of patterns of current flowing through the computer to simple objects. I call it primitive ontological abstraction because we're not dealing with ‘Big-O Object-Oriented’ ideas, but rather with the notion that there are ‘things’ in the computer like bits, bytes, characters, text strings, code chunks, etc. that are the basic ‘stuff’ we're going to compute with.

Without primitive ontological abstraction, our interaction with computer is going to be very limited. We could fiddle around with the electrical signals going in to the processor and maybe cause the computer to halt or generate a non-maskable interrupt, but it's hard to program the computer when you have no notion of ‘instructions’. But primitive ontological abstraction only lifts us up to the machine-code level where we are putting different byte values in sequential memory and then telling the computer to load the ‘program counter’ with a particular start address. At this point we need the next abstraction: naming.

---

Ok, my bus ride is over. We'll leave naming to the next post.

Which Schemes?

What's the point of a Scheme standard? I can think of a number of uses.

• A guideline for new Scheme implementations.
• A touchstone to distinguish a “real” implementation from a wanna-be.
• A reference point for academic papers so they don't need to devote an appendix to describing the semantics of their language.
• A “weighty tome” that adds gravitas to one's bookshelf.
• The reference for nitpicking language lawyers.
• A wishlist of features that would be nice to have.

But I think the most important thing for a Scheme standard to be is this:

• An agreement between language implementors and programmers that specifies the minimum functionality that an implementor is expected to provide and the maximum functionality that a programmer can assume is available from any system that claims to meet the standard.

Naturally, any implementation can provide more functionality than is prescribed, and no one expects any particular program to use all possible functionality.

Additional functionality is the way the language has evolved. The different implementations would add extra features for various reasons. Since these features were developed independently, there were often incompatible. Some of the differences were simply idiosyncratic, others, however, were caused by deliberate decisions about design. When a feature proved its utility, the programmers would put pressure on the implementations to add the feature. When a useful feature was incompatible between different implementations, an effort was made to reconcile the incompatibilities. In the early days, this could be accomplished by getting all the implementors in the same room and letting them argue. This isn't practical anymore.

The reason I put together my spreadsheet of Scheme implementations was not so that I could argue that any one is better than another. My purpose was altogether different. I wanted to get an idea of what subset of Scheme implementations are likely to affect or be affected by a new standard. Most of these Scheme implementations are at least R5RS compatible, and all of them extend the language in various ways. Some of these extensions are quite common across a large number of implementations.

If every Scheme implementation implemented an extension to the language in the same way with the same semantics, I can hardly there being much opposition to declaring this to be a standard feature. It would be a de-facto standard and it would require zero effort on the part of implementors if it became a de jure standard. On the other hand, if no Scheme implementation implemented a particular extension (say, for example, SRFI-49), there shouldn't be an enormous outcry if the feature were omitted from the standard. The issue becomes more complicated when a feature is available in only a subset of the implementations.

Let's take a particular example: SRFI-8 (special form receive for multiple values), is available in 21 implementations. The SRFI is trivially implemented with an R5RS syntax-rules macro. It seems to me that this would be a prime candidate for inclusion in an upcoming standard. It would require very little work on the part of implementors (unless, of course, they did not support multiple values at all or did not have syntax-rules), and the aesthetic issue (introducing a trivial special form) is fairly minor.

SRFI-36, on the other hand, is only available in three implementations. It defines a hierarchy of I/O exceptions. It would be non-trivial to add this to an implementation that had no exception hierarchies, or to one that had incompatible exceptions. It would be a poor candidate for inclusion.

What about something like SRFI-23? Here's where things get tricky. There are only seventeen implementations that support SRFI-23, but included in those seventeen are PLT Scheme, MIT Scheme, Gambit, Gauche, Chicken, SCM, SISC, and Scheme48. It's not universal, but it is very widespread. Or what about SRFI-48? It is available in Larceny, Scheme48, partly in Kawa, STKlos, PLT Scheme, Iron Scheme, and S7. If you use MIT Scheme, Gambit, Gauche, Chicken, SCM or SISC, you're out of luck.

The tiers that I had published previously were not there because of my preferences. They were there as a rough guide to determine how much support is needed or given for a particular feature set. Your new special form may be the niftiest hack since McCarthy's amb, but if you can't get buy-in from PLT, MIT, Gauche, Guile, Gambit, Chicken, Scheme48, and SCM, it just cannot be called a standard. Alternatively, if the “Top Ten” buy into your ideas (whatever the “Top Ten” might be), then it will probably be one of the less supported implementations that will have to admit that they do not adhere to the standard.

So which Schemes are the leaders of the pack?

Temerity

I added a column to my Scheme Implementation spreadsheet. That is ‘Arbitrary Metric A’ As the name suggests, it is arbitrary. However, it is also a metric. My opinion about the merits of any particular scheme implementation was not a factor.

Metric A sucks. It cannot be independently verified, it's relevancy cannot be determined, the bias is unknown. It has exactly one virtue: it has a value. I'd like to come up with something better, but until I do, here it is.

If you have an objective metric, give me the values, (or better yet, tell us how to derive them!!!) and I'll add a column for that.

---

Not only did I have the temerity to measure Scheme implementations on a hidden scale (it could have been a Ouija board), I had the temerity to rank the implementations. Furthemore, I divided them into four broad tiers.

Tier 1 is the powerhouse implementations. Of course PLT scheme is the most popular scheme. I was surprised to find that Gauche is tremendously popular. I've heard of it, but never used it. I was also surprised, but pleased to see MIT Scheme is still popular enough to stand out from the crowd.

Tier 2 is the usual suspects. These implementations are well known and have a solid following. The surprise here is that EdScheme is in this tier but Chez Scheme is not and that Scsh is here but Scheme 48 is not.

Tier 3 is the genus omne.

Tier 4 is the obscure implementations.

Stupid software

I'm getting old and I can't work these newfangled “web” applications. Let me try again.

http://spreadsheets.google.com/pub?key=twRSWnj1h-j_F3IHRXxwrmg&output=html

Please email me if you have problems.

A list of Scheme implementations

I've made a list of Scheme Implementations at this incredibly ugly URL: http://spreadsheets.google.com/ccc?key=0Aozj6rF-PmISdHdSU1duajFoLWpfRjNJSFJYeHdybWc.

This list is not meant to be exhaustive, but I'd like it to include all the Scheme implementations that are likely to affect, or to be affected by, the next Scheme standard.

For the moment, I just want to make a list of active implementations. I don't want to compare features, or list conformance. I'll add these later if they seem relevant.

Please send me email if I have omitted things, got things wrong, or included abandoned implementations. Thank you for your time.

A harder puzzle

The previous puzzle was inspired by this one:

(define (f l)
  (if (null? l) 
      #f
      (let ((r (fold-left kernel k0 l)))
        (f (if (car r) (cadr r) (caddr r))))))

(define (kernel l e)
  (list (not (car l))
        (if (car l) (cons e (cadr l)) (cadr l))
        (cons e (cons e (cons e (caddr l))))))

(define k0 (list #f '() '(#t #t #t)))

Q1 (easy): Show that for any non-negative integer n, (f (make-list n)) can return no value other than #f.

Q2 (very hard): Show that for any non-negative integer n, (f (make-list n)) returns #f.

A small puzzle

I got this from Marshall Spight today.

(define (f a b)
  (if (zero? b)
      a
      (f (logxor a b)
         (* (logand a b) 2))))

Q: F is better known as ______ ?

You may need these auxiliary functions.

(define (logand a b)
  (cond ((zero? a) 0)
        ((zero? b) 0)
        (else
         (+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (or (even? a)
                    (even? b))
                0
                1)))))

(define (logxor a b)
  (cond ((zero? a) b)
        ((zero? b) a)
        (else 
         (+ (* (logxor (floor (/ a 2)) (floor (/ b 2))) 2)
            (if (even? a)
                (if (even? b) 0 1)
                (if (even? b) 1 0))))))

And please don't just post a spoiler. If you just want ‘first credit’, email me directly.

What's amusing to me is that it isn't obvious if F even terminates.