April 7, 2007

PLT-Scheme and the stupidity syndrome…

Posted in Programming, Scheme at 7:22 pm by pmatos

PLT Scheme is huge as compared to the R5RS Scheme standard, on which PLT Scheme builds upon. No matter how much I spend my free time having fun with Scheme, I always get in the end with an “Aha” moment and then I feel deeply stupid.

Check this… I’ve been developing a graph library and I had it ready to upload to Planet, however, I wanted to tweak it some more. To build a sparse graph I had a very simple structure based on lists. The make-sparse-graph should receive two optional arguments, procedures, and return the structure for an empty graph. My version 30 minutes ago was like this:

  ; Constructor
  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define (make-sparse-graph . fns)
    (define (make node=? node?)
      (cons (cons node=? node?) '()))
    (cond [(= (length fns) 0)
           (make eq? (lambda (x) #t))]
          [(and (= (length fns) 1)
                (procedure? (car fns)))
           (make (car fns) (lambda (x) #t))]
          [(and (= (length fns) 2)
                (procedure? (car fns))
                (procedure? (cadr fns)))
           (make (car fns) (cadr fns))]
           (error "make-sparse-graph: Should receive 0 to 2 optional procedures.")]))

I was not really satisfied with it. Through a discussion on PLT-Scheme mailing list, I got to case-lambda, which seemed very nice so I improved it a little to:

  ;; Constructor
  ;; make-fixed-sparse-graph : node=? node? -> empty sparse-graph
  (define (make-fixed-sparse-graph node=? node?)
    (cons (cons node=? node?) '()))

  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define make-sparse-graph
      [() (make-fixed-sparse-graph eq? (lambda (x) #t))]
      [(node=?) (make-fixed-sparse-graph node=? (lambda (x) #t))]
      [(node=? node?) (make-fixed-sparse-graph node=? node?)]))

But… hey, again, by searching through the docs on contracts I found yet again a another pearl opt-lambda and here’s the current version:

  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define make-sparse-graph
    (opt-lambda ((node=? eq?) (node? (lambda (x) #t)))
      (cons (cons node=? node?) '())))

Well, after this… by looking to my first first and to my last one… damn, I feel stupid! Yes, sometimes I have a love-hate relationship with PLT-Scheme… I wonder if I kept searching I would end up with a 10 character function definition. :-)



  1. Phil said,

    When I have to write functions that take optional parameters, I write something like this, which is uglier than what you came up with, but purely R5RS:

    ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
    (define (make-sparse-graph . args)
    (let ((node=? (if (pair? args) (car args) eq?))
    (node? (if (and (pair? args) (pair? (cdr args))) (cadr args) (lambda (x) #t))))
    (cons (cons node=? node?) ‘())))

  2. The original version is also purely RnRS but much better than Phil’s
    version, because it actually checks arity. If the procedure is
    accidentally called with more than two arguments, it reports an
    error. In contrast, Phil’s version ignores the extra arguments.

    Of course, the CASE-LAMBDA and OPT-LAMBDA versions preserve this arity
    checking even in the face of a variable number of arguments, which is
    what makes them paricularly nice.

    (Dybvig and Hieb’s original paper on CASE-LAMBDA shows why this is a
    big performance win as well. The short version is that with the
    (lambda args …) notation, the compiler is forced to allocate a list
    object on the heap and has to bypass the traditional call-return
    mechanisms. Using CASE-LAMBDA restores the call stack to its normal
    role. See “A New Approach to Procedures with Variable Arity”, Lisp
    And Symbolic Computation, vol 3, number 3.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: