Unique types and STM?

I had an idea at work.

A given programming language is mostly useful only for masturbation if it cannot support things such as file handles, sockets, pipes, graphics, etc… but these wreck hell on purely functional languages. Monads conceptually work by passing a data structure representing the world between the functions which must alter it, it is happenstance that it is never the same twice. Unique types are a sort of middle ground, a type of data which can only be used once afterwards from which an alternate is derived. Both monads and unique types are syntactically noisier than allowing direct mutation, although Kernel’s clean support for multiple value returns would greatly simplify the handling of uniques. Scheme and Ocaml “solve” it by presuming to be “mostly” functional languages and allow mutation of variables (via refs in Ocaml, set! in Scheme). This is the simplest method but breaks referential transparency a whole lot.

So here’s the question. Why don’t we make those things unique types, and automagically handle their updating in the background managed by something along the lines of STM or the such as is already done for mutable data (ala Clojure)?

Someone steal this idea and implement it or point me to something which already does something similar, or point out some flaws, or whatever. I think it’s a neat idea and would like to know if it’s redundant or for some reason unworkable.

SMOS

A quick hack, does what I needed it to do. Namely, manage access to ancestor’s methods a little more like YASOS. Maybe someone’ll find it useful.

Perma link for updates and such: http://prael.wordpress.com/smos/

smos.scm

;;;; smos.scm
;;;; Still Macroless Object System.
;;;; This code is still in the public domain.
;;;; No warrany. In fact, I guarantee that even looking at this code will break your shit, leaving you destitute and homeless.

;;;; 0.0.2
;;;; Broke out vector stuff, in case obj's structure changes later.
;;;; Somewhat YASOS-ify ancestor handling. Ancestors are now stored in a vector.
;;;; (make-method! self some-method (lambda (self) (operate-as self a-number-in-ancestors-vector some-other-method)))

;;;; 0.0.1
;;;; Initial copy of MOS.

;;;; Object Construction:
;;;;       0           1          2             3              4             5         6
;;;; #(object-tag get-method make-method! unmake-method! get-all-methods ancestors operate-as)

;;;; Original header: ----------------------------------------------------
;;; "object.scm" Macroless Object System
;;; Author: Wade Humeniuk <humeniuw@cadvision.com>
;;;
;;; This code is in the public domain.

;;;Date:  February 15, 1994

;; Object Construction:
;;       0           1          2             3              4
;; #(object-tag get-method make-method! unmake-method! get-all-methods)
;;;; ---------------------------------------------------------------------

(define object:tag 'object)

(define (obj:tag obj)
  (vector-ref obj 0))
(define (obj:get-methods obj)
  (vector-ref obj 1))
(define (obj:make-method! obj)
  (vector-ref obj 2))
(define (obj:unmake-method! obj)
  (vector-ref obj 3))
(define (obj:get-all-methods obj)
  (vector-ref obj 4))
(define (obj:ancestors obj)
  (vector-ref obj 5))
(define (obj:operate-as obj)
  (vector-ref obj 6))

(define (object? obj)
  (and (vector? obj)
       (eq? object:tag (obj:tag obj))))

;;; This might be better done using COMLIST:DELETE-IF.
(define (object:removeq obj alist)
  (if (null? alist)
      alist
      (if (eq? (caar alist) obj)
          (cdr alist)
          (cons (car alist) (object:removeq obj (cdr alist))))))

(define (operate-as obj ancestor-number method)
  (if (object? obj)
      ((obj:operate-as obj) ancestor-number method)
      (error "Cannot access ancestors of non-object: " obj)))

(define (get-all-methods obj)
  (if (object? obj)
      (obj:get-all-methods obj)
      (error "Cannot get methods on non-object: " obj)))

(define (make-method! obj generic-method method)
  (if (object? obj)
      (if (procedure? method)
          (begin
            ((obj:make-method! obj) generic-method method)
            method)
          (error "Method must be a procedure: " method))
      (error "Cannot make method on non-object: " obj)))

(define (get-method obj generic-method)
  (if (object? obj)
      ((obj:get-methods obj) generic-method)
      (error "Cannot get method on non-object: " obj)))

(define (unmake-method! obj generic-method)
  (if (object? obj)
      ((obj:unmake-method! obj) generic-method)
      (error "Cannot unmake method on non-object: " obj)))

(define (make-predicate! obj generic-predicate)
  (if (object? obj)
      ((obj:make-method! obj) generic-predicate (lambda (self) #t))
      (error "Cannot make predicate on non-object: " obj)))

(define (make-generic-method . exception-procedure)
  (define generic-method
    (lambda (obj . operands)
      (if (object? obj)
          (let ((object-method ((obj:get-methods obj) generic-method)))
            (if object-method
                (apply object-method (cons obj operands))
                (error "Method not supported: " obj)))
          (apply exception-procedure (cons obj operands)))))

  (if (not (null? exception-procedure))
      (if (procedure? (car exception-procedure))
          (set! exception-procedure (car exception-procedure))
          (error "Exception Handler Not Procedure:"))
      (set! exception-procedure
            (lambda (obj . params)
              (error "Operation not supported: " obj))))
  generic-method)

(define (make-generic-predicate)
  (define generic-predicate
    (lambda (obj)
      (if (object? obj)
          (if ((obj:get-methods obj) generic-predicate)
              #t
              #f)
          #f)))
  generic-predicate)

(define (make-object . ancestor-list)
  (define method-list (list))
  (define ancestors (list->vector (cons 'i-wish-self-could-go-here-but-i-dont-have-macros ancestor-list)))
  (define num-ancestors (length ancestor-list)) ; I can't seem to (vector-length ancestors) here.
  (define (operate-as obj-num method)
    (method (vector-ref ancestors obj-num)))
  (define (make-method! generic-method method)
    (set! method-list (cons (cons generic-method method) method-list))
    method)
  (define (unmake-method! generic-method)
    (set! method-list (object:removeq generic-method method-list))
    #t)
  (define (methods) method-list)
  (define (get-method generic-method)
    (let ((method-def (assq generic-method method-list)))
      (if method-def
          (cdr method-def)
          (let loop ((current-ancestor 1))
            (if (> current-ancestor num-ancestors)
                #f
                (let ((method-def ((obj:get-methods (vector-ref ancestors current-ancestor)) generic-method)))
                  (if method-def
                      method-def
                      (loop (+ 1 current-ancestor)))))))))
  (vector object:tag get-method make-method! unmake-method! methods ancestors operate-as))

;; Samples:

;; SMOS/MOS:
;;
;; > (define name (make-generic-method))
;; > (define job (make-generic-method))
;; > (define (person n)
;;     (define self (make-object))
;;     (make-method! self name (lambda (self) n))
;;     self)
;; > (map name (list (person 'bob) (person 'ashley) (person 'george)))
;; (bob ashley george)
;; > (define (worker n j)
;;     (define self (make-object (person n)))
;;     (make-method! self job (lambda (self) j))
;;     self)
;; > (map name (list (worker 'bob 'mechanic) (worker 'ashley 'pilot) (worker 'george 'loanshark)))
;; (bob ashley george)
;; > (map job (list (worker 'bob 'mechanic) (worker 'ashley 'pilot) (worker 'george 'loanshark)))
;; (mechanic pilot loanshark)
;; >

;; SMOS operate-as:
;;
;; > (define name (make-generic-method))
;; > (define is (make-generic-method))
;; > (define job (make-generic-method))
;; > (define really (make-generic-method))
;; >  (define (person n)
;;     (define self (make-object))
;;     (make-method! self name (lambda (self) n))
;;     (make-method! self is (lambda (self) 'person))
;;     self)
;; >  (define (employee n j)
;;     (define self (make-object (person n)))
;;     (make-method! self job (lambda (self) j))
;;     (make-method! self is (lambda (self) 'slave))
;;     (make-method! self really (lambda (self) (operate-as self 1 is)))
;;     self)
;; > (name (employee 'bob 'mechanic))
;; bob
;; > (is (employee 'bob 'mechanic))
;; slave
;; > (really (employee 'bob 'mechanic))
;; person

(define name (make-generic-method))
(define is (make-generic-method))
(define job (make-generic-method))
(define really (make-generic-method))
(define (person n)
  (define self (make-object))
  (make-method! self name (lambda (self) n))
  (make-method! self is (lambda (self) 'person))
  self)
(define (employee n j)
  (define self (make-object (person n)))
  (make-method! self job (lambda (self) j))
  (make-method! self is (lambda (self) 'slave))
  (make-method! self really (lambda (self) (operate-as self 1 is)))
  self)
(name (employee 'bob 'mechanic))
(is (employee 'bob 'mechanic))
(really (employee 'bob 'mechanic))

ParrotVM

Makes my pants uncomfortable. Register based, tail call optimizing, supports call/cc(!), has the beginnings of JIT compilation… the GC isn’t exactly bleeding edge but at least isn’t one of the stop-the-world sorts (something about 3 color marks and a background thread doing incremental sweeping IIRC), and like the layout algorithms in xmonad it is easy to replace with something better when one comes around. Oh yeah, and threading. Decent looking FFI. The promise of calling libs from other languages in the future (like the way OCaml can talk to any Perl module from CPAN). And it reached 1.0 with a stable API recently. And interestingly there seems to be talks about working along side the LLVM folk…

There’s just a lot of cool shit going on here. Whereas Java/.Net are trying to bolt in the infrastructure to support dynamic languages, Parrot’s designed from the ground up to do this.

Perhaps GC wouldn’t matter much if something like newLISP with its funky one reference only “GC” were ported to it… on that note I should try to compile newLISP to LLVM bytecode.

And Java’s planning (apparently) on supporting TCO and if it already did, so would Clojure (the recur thing just drives me loopy, pun intended), and I probably never would have noticed Parrot.

For that matter, Clojure on Parrot would rock my balls too. And there’s word of Parrot eventually maybe understanding JVM/.Net bytecode… shouldn’t be much of a tweak from there…

You know? A few months ago I found myself wishing I had been born in the 60’s or 70’s, so I could have been around when all of the cool Lisp stuff was happening. I think I’ve changed my mind… this is a fucking awesome time to be here.

And as long as my ParrotVM post has turned into an obscure Lisp post, I should mention Arc. Arc is a Lisp. There, I mentioned it. Now let’s never speak of that again.

Who wants a non-toy R5RS Scheme on the Parrot VM?

So do I, go write me one. Here’s how (I hope):

pre-scheme is essentially a lispy-syntax C, complete with memory allocations, freeing, goto, minimal TCO, no GC… basically disgusting from a (this, anyway) lisper’s POV, and a far cry from the shear sexiness of R5.

The interesting thing about it though (other than making C a saner language) is that Scheme48’s VM is implemented via Scheme48’s pre-scheme->C translator, which as it happens, in true Lisp fashion, is itself implemented in Scheme. And I’d imagine implementing the minimalistic pre-scheme to be a far sight easier than implementing all of R5. You can look at the Scheme48 distribution’s makefile to see how to go about getting pre-scheme loaded to play with.

It may be a weird way to go about it, running a stack based VM atop a register based one (let alone one wanting malloc/free), but I’d think it to be the quickest route towards non-toy R5 on Parrot, and if nothing else a sufficient stop-gap until “native” implementations approach practical usability. Plus you already have most of your test suite for free.

Of course I havn’t looked into this in any depth, particularly what the Parrot implementation of pre-scheme would need to do other than parse the syntax. And I don’t really have the time to. So I thought I’d toss the idea out there and see if anyone else picks it up. What the hell, it’s worth a shot right?

A different take on closure-based object orientation

Provides OO-like access to already existing data abstractions, and its implementation is a pretty neat use of syntax-rules macros. It seems like it could be a pretty useful bit of code in a lot of cases when you wish to write in an OO-style but are using libraries not designed as such. You can find it here.

Text editing, efficiency, and design.

The Craft of Text Editing — by Craig A. Finseth.

It’s a book on how to design[1] an Emacs clone. Comparisons to vi are made where appropriate.

It’s interesting in that despite being written in 1991 most of what it covers regarding editor specific functionality and concerns is still valid. It’s essentially built around a model-view-controller pattern, long before the patterns book was published. There still hasn’t been much improvement on gap buffers or linked lists and such for modeling the data. User interface design is obviously important, if you expect to have any users. I like timeless shit like that.

A few parts such as chapter seven cover implementation and performance details which aren’t of particular concern today, but I think are still worth the read simply because it’s an interesting look into the sorts of tradeoffs one faces when performance matters (chapter seven itself even says as much, pointing out that for screen management you could just use the prevalent curses library). Thankfully we don’t generally use monochrome text-only terminals over a connection who’s speed is measured in baud anymore, but while people typing faster than the networked terminal could respond on slower connections is no longer a real concern, over time people have gotten lazy and despite multi gigahertz machines with megabit/sec connections we still deal with lag. The lag’s just in other areas now, but it’s still there, especially on the web. Especially when someone’s on dialup, or a cell phone, neither of which are exactly uncommon just as 300 baud connections wern’t uncommon in 1991. I’m thinking specifically of XML’s rampant misuse for non-trivially-sized datasets here as one example where something like JSON or SQLite or Google’s newly released Protocol Buffers would be far more appropriate. Using scripting languages to implement entire applications (as in RoR, Django, etc…) would rank pretty high as well, but at least in those cases it’s the server’s CPU cycles they’re chewing away and not your own computer’s. Unless of course it’s also an AJAX site. Sigh[2].

Writing a new editor, of any sort, from scratch today would simply be retarded. You aren’t going to do anything new, editors have been done to death. It would accomplish nothing but a pointless reinvention of the wheel when all you needed to do was pick a well designed customizable editor, and learn to use it. Emacs, vi, LyX[3], Eclipse, TextMate, there’s shit loads of good editors already. But the fact that the book covers writing a text editor for obsolete equipment seems incidental to me. It’s more about properly designing software, using a text editor as a specific case example. In that regard it will remain valid for many years to come, especially in a world where test-driven development and “agile” development run rampant and naive programmers think “if it works, it’s done”. Not to say that TDD/Agile are bad ideas, I think TDD is awesome. But when they’re mis-used by the lazy, they’re fucking horrible.

—

[1] Design, not program. The book won’t teach you how to code in general, let alone anything usable, save for an appendix covering the minimum of C necessary to, with effort, understand the code examples. It was written for programmers, ergo it contains mostly concepts, not code.

[2] I know there’s going to be some ass chewing over this. Oh well.

[3] Especially handy when writing papers, articles, and such like. While the web has only recently begun to understand the value of separating content from presentation, it’s been around for document editing for eons. If you’re trying to do both at the same time, you’re wasting time. The trick is these two choice quotes from Bram Moolenaar:

“I want to get the work done, I don’t have time to look through the documentation to find some new command”. If you think like this, you will get stuck in the stone age of computing. Some people use Notepad for everything, and then wonder why other people get their work done in half the time…

Don’t overdo it. If you always try to find the perfect command for every little thing you do, your mind will have no time left to think about the work you were actually doing. Just pick out those actions that take more time than necessary, and train the commands until you don’t need to think about it when using them. Then you can concentrate on the text.

R5RS syntax-rules macros in Gambit Scheme

Stumbled upon Alexey Radul’s list of Scheme Implementation Choices, and noticed that Gambit was listed as no-syntax-rules:

The syntax-rules macro system is off by default in several Schemes. I tried as best I could to find out how to turn it on, but was not uniformly successful.
[...]
RScheme and Gambit produce an error

Well I remember it being a bit tricky to figure out how to do this in Gambit myself not too long ago, so I thought I’d share the method here and hopefully make it easier for others to find.

> (load "~~/syntax-case")
"/usr/home/Martin/.snow-site/v1.1.2/host/gambit/v4.2.0/syntax-case.scm"
> (define-syntax foo (syntax-rules () ((_) 1)))
> (foo)
1
>

or

$ gsi -e '(load "~~/syntax-case")' -
> (define-syntax foo (syntax-rules () ((_) 1)))
> (foo)
1
>

I’m not fond of the ‘magic’ file path to get to it, but it comes with Gambit and it does work. If I recall correctly, it’s a port of psyntax.

Scheme, Forth, and C

I came across an article entitled Forth Versus C, and I couldn’t help but notice how much of it applies directly to Scheme (and mostly Common Lisp) as well, with only a few changes in terminology. Naturally not the parts involving its dual stack nature and such, but that’s far from the majority (and you could bring up a similar topic anyway, just compare the C stack to call/cc instead).

This bit especially caught my attention, especially in light of another recent post:

Q. But how can a non-programmer even read a program, let alone tell whether it is right?
A. Forth syntax can be learnt in an hour or two. If the top level of the program cannot be read and understood by someone who understands the problem domain, it is wrong and you should change it.

I would also say this would apply to *any* Domain Specific Language. Lisps (and apparently Forth) make constructing DSL’s trivially easy, any many of the pros and cons of such are discussed (in relation to C).

Back on topic though, I think this article neatly describes many of the fundamental differences between Lisp and C just as well as Fortran and C. I highly recommend giving it a read.

A new Lisp forum

briancarper.net writes:

Ten days ago I complained that there were no good Lisp equivalents of ruby-forum or perlmonks. It looks like someone went and made one. What good timing.

You can find it here.

And yes, it has a Scheme subforum along with the expected Common Lisp. And Elisp, Clojure, and Arc subforums, as well as a catch-all Other.

A bit odd that it’s a PHP forum for a Lisp community… who knows, maybe it’s running on Roadsend (which is built upon Bigloo Scheme)?

Regardless, it’s about damn time!

How I feel about Scheme’s performance.

I came across this post written earlier today, How fast is Scheme? Well…. which states:

I don’t know much about Scheme [...] but it seems that the Scheme compilers produce quite sluggish code, at least looking through the grainy, distorted lens that is the Computer Language Benchmarks Game.

That seems to make enough sense to me. For one-off heavily numerical tests, Scheme pretty much sucks. Especially considering that to compile the code it often has to go through C.

He goes on to say:

SBCL comes out very much on top; in general the Gambit programs take two or three times as long to do their job (although I haven’t looked at memory usage). But as far as Scheme compilers go, Gambit seems to be improving things.

With the right declarations, SBCL has been known to outperform straight C as well. Its compiler is really quite something. And (IIRC) it doesn’t have the “handicap” of using C as an intermediate language.

Personally however, I tend to consider C generating Scheme compilers more practical for issues of portability and/or easier FFI than performance. Chicken’s a good example of braindead-easy FFI. And I feel where Gambit really shines is when you need many, many threads. It’ll handle hundreds of thousands of threads in a breeze. Termite is a good example of exploiting its threading capabilities. RScheme does real-time GC. SCSH has replaced every use I’ve had for shell/perl/etc scripts. There’s a decent chance that any random Linux box already has Guile installed. SISC and Kawa leverage Java’s JIT machiery and provide trivially easy Java FFI. Bigloo can compile to Java bytecode as well. MzScheme runs its own JIT compiler by default where it can, and is prefered to its C output. And there’s a JIT option for all the C-generating Scheme’s as well, compile with LLVM instead of GCC. I think it’d be especially interesting to compare MzScheme’s JIT to MzScheme’s C + LLVM. And if you’re going the Scheme->C route for performance reasons, I’d think Stalin to be the obvious Scheme to use, whether with GCC or LLVM depending on its expected run time (assuming there’s even noticeable startup overhead with LLVM, it’s embedded VM is really quite minimal). Many of them have really nice OO systems built in as well

But none of these tests run long enough to let any of the JIT options really shine. Basically, I say throw any of the JIT options into the mix, and make the tests long enough to really let them do their magic.

I very strongly suspect the same holds for Java, having run a Freenet node for quite some time it gets noticeably snappier once the JVM has had a chance to see it run for a while, especially for recent versions of Java. I’d also argue that’s exactly (other than its relatively primitive GC) what makes Java so incredibly horrid for client-side stuff such as applets, you’re loading a JIT compiler and GC you’ll hardly get a chance to even use before you’ve closed the window. But its JIT has been making leaps and bounds lately, as mentioned on Good Math, Bad Math:

About a year later, testing a new JIT for Java, the Java time was down to 0.7 seconds to run the code, plus about 1 second for the JVM to start up. (The startup times for C, C++, and Ocaml weren’t really measurable – they were smaller than the margin of error for the measurements.)

This is from the previous measurement of 1 minute and 20 seconds for Java. As I said before, SISC, Kawa, and Bigloo will happily use the Java VM. Straight C scored 0.8 seconds. OCaml kicked all their asses even before compilation, but that’s not the point here. If you really need every last bit of performance you can get though, OCaml seems to be worth looking into.

So yeah, I’m *very* interested in what the performance possibilities for Scheme really are, if nothing else out of shear curiosity. Maybe I’ll wind up running a few benchmarks of my own at some point, reiterating the tests, say, a hundred or a thousand times each… but in the end, even if this does increase their performance relative to SBCL… you don’t need to use an obscure implementation or do JIT tricks with SBCL in the first place. A lot of people havn’t heard of Stalin or LLVM. A lot of people don’t want to load one language (Java) to run another (Scheme). Although again, I’d question whether MzScheme’s performance is really so bad in the long run.

And I’d question whether it was really worth it in the first place. Fluxus and Impromtu are two obvious examples which come to mind, both heavy graphics/audio livecoding systems, which solve many problems the same way you would in, say, Python. Offload much of the heavy work onto libraries. There’s a PDF floating on the net somewhere about MzScheme controlling an array of telescopes, and of course there’s the US Navy’s Metcast project. SchemDoc, Scheme Elucidator, the LAML they’re both based on that you can just feed any XML DTD into and get a Scheme representation of that XML language in. SCWM and Orion window managers. MetaModeler for dealing with many/large databases. For web stuff there’s TeX2page, SISCweb, BRL, WiLiKi, the Hop framework, HtmlPrag, SXML, it goes on. There’s a lot of uses which don’t demand every last bit of performance from the Scheme implementation, and I’m just not really doing anything that does.

And if I were writing something and came across an annoying bottleneck? I’d likely take the NetBSD approach. Instead of trying to tweak things to run faster (LLVM, Java, implementation-specific declarations, etc…), I’d see if I couldn’t find a fundamentally more efficient algorithm first. Which reminds me, I still want those books.

[update] On the Reddit thread where apparently most of the views for this article are coming from (who’d have thought so many people would be interested in some Scheme noob’s opinions of language performance? Well over 500 hits already, scant hours later), there’s a link to a fascinating email thread discussing the floating point speed of Gambit-C. I have Brad Lucier’s paper printing to read later as I type this. There’s also a reply in the thread by Brad himself, my favorite part of which is the end summary, which is generally similar to the “NetBSD approach” mentioned above. Is there some sort of established term for this idea?

Anyway, I’ll certainly be rethinking my opinions of Gambit-C as “that threading/Termite implementation”.

[update 2] It’s morning, getting close to 1500 views for this post now… searching for r5rs performance on Google this is the 3rd result! I still don’t see why this is drawing so much attention, but as long as it is, have you seen Scheme Now!?

Scheme Now!, also known as Snow, is a repository of Scheme packages that are portable to several popular implementations of Scheme.

Snow is a general framework for developing and distributing portable Scheme packages. Snow comes with a set of core packages that provide portable APIs for practical programming features such as networking, cryptography, data compression, file system access, etc. Snow packages can export procedures, macros and records.

[update 3] 1844 views as I write this on July 1st. Also now the first result on google for the aforementioned search. Wow. o_O