Arc Forumnew | comments | leaders | submit | herdrick's commentslogin
1 point by herdrick 3777 days ago | link | parent | on: Arc 3.1 (works on latest MzScheme)

Why is it faster? I would think that banning list mutation would only slow down a program that had originally used it.

-----

5 points by rntz 3777 days ago | link

I presume arc3.1 is only faster if you use plt4, which is attributable to plt4 being faster than mzscheme 372 thanks to improvements to the language implementation. The speed boost obviously doesn't come from making conses immutable, since Arc still has mutable conses.

If you're asking why immutable conses could speed up a programming language in general, well, a compiler can make more powerful optimizations if it's allowed to assume that lists won't mutate mid-flight. Obviously a specific program that used mutability of conses would need to be rewritten, and might end up faster or slower; but code that doesn't take advantage of the mutability of conses (of which there is a lot, Scheme having the functional heritage it does) can be speeded up.

Of course, given that Arc's mutable conses are accomplished by using pointer hacking to mutate plt4's supposedly immutable conses, one would hope the plt4 compiler doesn't take real advantage of the immutability of their conses, otherwise it might make assumptions that Arc will break, leading to difficult-to-detect bugs.

-----

1 point by herdrick 3775 days ago | link

Arc's mutable conses are accomplished by using pointer hacking to mutate plt4's supposedly immutable conses,

Really?

-----

5 points by rntz 3775 days ago | link

  ; Eli's code to modify mzscheme-4's immutable pairs.

  ;; to avoid a malloc on every call, reuse a single pointer, but make
  ;; it thread-local to avoid races
  (define ptr (make-thread-cell #f))
  (define (get-ptr)
    (or (thread-cell-ref ptr)
        (let ([p (malloc _scheme 1)]) (thread-cell-set! ptr p) p)))

  ;; set a pointer to the cons cell, then dereference it as a pointer,
  ;; and bang the new value in the given offset
  (define (set-ca/dr! offset who p x)
    (if (pair? p)
      (let ([p* (get-ptr)])
        (ptr-set! p* _scheme p)
        (ptr-set! (ptr-ref p* _pointer 0) _scheme offset x))
      (raise-type-error who "pair" p)))

  (define (n-set-car! p x) (set-ca/dr! 1 'set-car! p x))
  (define (n-set-cdr! p x) (set-ca/dr! 2 'set-cdr! p x))
Really. (This is an excerpt from arc3.1's ac.scm.)

-----

4 points by herdrick 3869 days ago | link | parent | on: Request for Bugs

Nope. All you can do is use mcons ('mutable cons'), mcar, mcdr, etc. But apparently there are only a few functions that work with these things. It's like using lists in a language that doesn't support lists well. Useless.

  > (require scheme/mpair)
  > (require (lib "1.ss" "srfi"))
  > (lset-difference eq? (list 1 2) (list 2 3))
  (1)
  > (lset-difference eq? (mlist 1 2) (mlist 2 3))
  {1 2}
This really burns me.

-----

3 points by CatDancer 3867 days ago | link

Hmmmmmm... I had thought that r6rs compatibility mode wasn't very useful, if it just made car a synonym for mcar etc. But it does more, for example unlike in regular plt-4 where in (lambda args ...) args is an immutable list, in r6rs mode:

  #!r6rs
  (import (rnrs) (rnrs mutable-pairs (6)))
  (define x ((lambda a a) 'a 'b 'c))
  (set-car! (cdr x) 'd)
  (write x)
  (newline)

  $ plt-4.1.5/bin/mzscheme -t a.scm
  (a d c)
This looks like it could solve a lot of problems with a port to plt-4, since otherwise we'd need to be rewriting the Arc compiler to change the expansion of (fn args ...) etc.

-----

2 points by CatDancer 3865 days ago | link

Played around with it a bit more, r6rs appears problematic as apparently ++ is not a legal symbol in r6rs (!)

I took a look at PLT's implementation of lambda for r6rs/r5rs (it's in collects/r5rs/main.ss), and they just simply convert to a mutable list if the lambda has a rest parameter:

  (define-syntax (r5rs:lambda stx)
    ;; Convert rest-arg list to mlist, and use r5rs:body:
    (syntax-case stx ()
      [(_ (id ...) . body)
       (syntax/loc stx (#%plain-lambda (id ...) (r5rs:body . body)))]
      [(_ (id ... . rest) . body)
       (syntax/loc stx
         (#%plain-lambda (id ... . rest)
                         (let ([rest (list->mlist rest)])
                           (r5rs:body . body))))]))
(the list->mlist is the part I'm looking at)

So having for example (fn args ...) compile to an (arc-lambda args ...) which does the same thing might be simpler than trying to get Arc to compile and run in the whole complicated r6rs environment.

-----

4 points by pg 3869 days ago | link

Incidentally, does the (or some) Scheme standard allow an implementation to make cons cells immutable? I.e. is supporting set-car! optional?

-----

5 points by CatDancer 3868 days ago | link

Strongly deprecated:

http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale...

I participated a bit in the discussion while r6rs was being created, but it quickly became apparent to me that the goals that the editors were striving for weren't things that I personally cared about.

So, anyway, due to the "compromise", can we get mutable pairs if we run MzScheme in r6rs compatibility mode?

a.scm:

  #!r6rs
  (import (rnrs) (rnrs mutable-pairs (6)))

  (define x (cons 'a 'b))
  (set-car! x 'c)
  (write x)
  (newline)

  $ ./mzscheme a.scm
  (c . b)
So yes, though it turns out that in r6rs compatibility mode cons is really just mcons, so we don't actually gain anything.

-----

1 point by herdrick 3868 days ago | link

Interesting. Have you tried r6rs compat mode?

It looks like SRFI 1, at least, isn't working with r6rs: http://list.cs.brown.edu/pipermail/plt-dev/2009-March/000283...

-----

2 points by CatDancer 3868 days ago | link

Have you tried r6rs compat mode?

Not any more than I've shared here.

-----