Re: Scheme is too complicated

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> > 
> > Hmm.  I think your definition of slow and mine are different.  Could
> > you clarify what you mean when you say 'slow'?  How do you account for
> > the performance of Stalin?
> >
> 
> a while back I posted something like this:
> 
> hash->keys could be written in Scheme like this
> 
> (define entry->key cadr)
> 
> (define hash->keys
>   (lambda (mytab)
>     ;; maybe do some type-checking here
>     (let* ((vec (cdr mytab))
>            (vec-len (vector-length vec)))
>       (do ((keys '())
>            (i 0 (+ i 1))
>            (bucket (vector-ref vec 0) (vector-ref vec i)))
>           ((>= i vec-len) keys)
>         (do ((entry-list bucket (cdr entry-list)))
>             ((null? entry-list))
>           (let* ((entry (car entry-list))
>                  (key (entry->key entry)))
>             (set! keys (cons key keys))))))))
> 
> here's what I would call a functional version:
> 
> (define hash->keys
>   (lambda (mytab)
>     (let ((bucket->keys (lambda (bucket) (map entry->key bucket)))
>           (entry->key cadr))
>       (apply append (map bucket->keys (vector->list (cdr mytab)))))))
> 
> the functional guy is sleek and pretty, but those "vector->list" and
> "append" bits are performance killers. 
> 

How about:

(define (hash->keys mytab)
  (let ((real-tab (cdr mytab))
	(entry->key cadr)
	(end (vector-length real-tab)))
    (let loop-over-tab ((index 0)
			(accum ()))
      (if (= index end)
	  accum
	  (loop-over-tab (+ index 1)
			 (let loop-over-bucket ((l (vector-ref real-tab index))
						(accum accum))
			   (if (null? l)
			       accum
			       (loop-over-bucket (cdr l)
						 (cons (car l) accum)))))))))


This is a common style of programming once you have gotten past the
prototyping phase and want to write purely functional code that is
notheless tail-recursive, avoids gratuitous allocation, and does not
need to append (which requires copies). Such code is efficient and
optimizes very well. Actually, since all the named-let recursive calls
are tail calls, the named lets can be rewritten as do loops :


(define (hash->keys mytab)
  (let ((real-tab (cdr mytab))
	(entry->key cadr)
	(end (vector-length real-tab)))
    (do ((index 0 (+ 1 index))
	 (accum () (do ((l (vector-ref real-tab index) (cdr l))
			(accum accum (cons (car l) accum)))
		       ((null? l))
		     accum)))
	((= index end))
      accum)))

This is much like your original _non_-functional version, but actually
a bit shorter. Since it avoids side effects, it will also likely
compile to more efficient code (if it is getting compiled) or just
plain run faster since it doesn't have to set! variables if
interpreted.

An sufficiently smart compiler that had inside knowledge about
`reverse' `map' and `vector->list' might actually transform your
functional version into something close to the code above, but with a
big reverse around all of it (requiring one gratuitous copy), since
your purely functional version returns keys in the reverse of the
order of the other one. There do exist compilers that are smart enough
to do such transformations. In particular, I think Stalin knows how to
translate maps into iterations (someone correct me if I'm wrong).

If your point was just that the obvious and easy way to write Scheme
code that is inefficient unless you have a really smart compiler, I'll
grant your premise, but rewriting working simple-minded code to
functional but efficient code is not hard even by hand, and smart
compilers do exist.

 - Maciej