Features Download
From: Eli Barzilay <eli-oSK4jVRJLyZg9hUCZPvPmw <at> public.gmane.org>
Subject: Size matters
Newsgroups: gmane.comp.lang.racket.user
Date: Saturday 8th June 2013 19:49:52 UTC (over 3 years ago)
(Possible irrelevant rambling, but I generally am very aware of my
code formatting, and this looked like a good point to highlight.  It's
still probably picking on something that not many people care about as
much as I do...)

The style guide has a section labeled "size matters" -- it also has
another section on names, encouraging using readable names.  Both of
these are perfectly reasonable goals, but they can pull you in
different directions, and I ran into an example that demonstrates it
in a very nice way.  There is also Yaron's quote about favoring
readers, which is IMO more important than both of these -- since they
are just sub-points aiming towards that goal.

I have recently experimented more with taking code compactness more
seriously.  I still keep my own code under 80 characters, which I know
many people don't like, but on the other hand, I always try to fill
the lines as much as possible while maintaining readability.  The idea
is that the principle of favoring readers means that it should be easy
to read code -- and lines that are too long, or suffer from rightward
drift, or names that are too long are all things that delay reading.
I can also see the recent tendency to use `define' where possible as
something that goes to this end too: prefer using the same kind of
binding construct to make it easier to read code.

So to get to my point, there's the decision of what name to use for
your identifiers some people (*ahem*) stick to an always-readable
names, to the point of not using names like `i', `n', and `x'.  I'm on
the complete other side of this -- I strongly prefer these names
because they make code shorted and therefore easier to read.  The same
goes for the style guide's recommendation to name intermediate values
instead of nesting function calls -- it's obviously a line that the
author should decide on (exaggerated examples on both sides are easy,
and contribute nothing), and I tend to go further with nested calls
than defining intermediates.  (This same point applies to naming
functions vs using lambda expressions.)

My point here is that using longer names and binding intermediates can
explain the code better, but it's easy to carry this over to hurting
overall readability.  The example that made me post this is below (no
need to look up who wrote the original code, it's irrelevant since it
*is* following many of the style's guidelines).  The first chunk is
the original code, the second is my rewrite.  There are some obvious
things like using `match' to make the code more concise and more
readable, but note that the `cond' expression in the loop is very hard
to read in the first version -- the descriptive names are long enough
that the overall structure of the loop is not obvious.

In my revision, the much shorter names are less readable, but on the
flip side they allow laying out the code in a way that makes it much
more obvious, and since I started this by just doing mechanical
transformations, it was surprising to see that what the shrunk code is
doing becomes very clear.  This clarity has the obvious advantages,
which is why it's so important to "favor readers".

As a sidenote -- there are two named intermediates in this code that I
didn't get rid of: on one hand losing them won't save space (and
therefore I consider removing them as something that would only
obfuscate things), and on the other hand the result would be nesting
the verbose computation into a place where it is not relevant.  (And
yes, there'd be an advantage for having an infix syntax here, IMO...)

(In any case, sorry for the noise.  I'll avoid further replies...)


(define (fill-sack (items items) (volume-left 0.25) (weight-left 25) (sack
null) (sack-value 0))
  (if (null? items)
      (values (list sack) sack-value)
      (let* ((item (first items))
             (item-wgt (item-weight item))
             (max-q-wgt (floor (/ weight-left item-wgt)))
             (item-vol (item-volume item))
             (max-q-vol (floor (/ volume-left item-vol))))
            ((best-sacks (list sack))
             (best-sack-value sack-value))
          ((qty (in-range 0 (add1 (min max-q-vol max-q-wgt)))))
          (let-values (((inner-best-sacks inner-best-sack-value)
                        (fill-sack (cdr items)
                                   (- volume-left (* qty item-vol))
                                   (- weight-left (* qty item-wgt))
                                   (cons (cons qty item) sack)
                                   (+ sack-value (* qty (item-value
              [(> inner-best-sack-value best-sack-value)
               (values inner-best-sacks inner-best-sack-value)]
              [(= inner-best-sack-value best-sack-value)
               (values (append best-sacks inner-best-sacks)
              [else (values best-sacks best-sack-value)]))))))


(define (fill-sack items volume-left weight-left sack sack-value)
  (match items
    ['() (values (list sack) sack-value)]
    [(cons (and (item _ _ item-val weight volume) item) items)
     (define max-q-wgt (floor (/ weight-left weight)))
     (define max-q-vol (floor (/ volume-left volume)))
     (for/fold ([best (list sack)] [best-val sack-value])
               ([n (exact-round (add1 (min max-q-vol max-q-wgt)))])
       (define-values [best* best-val*]
         (fill-sack items
                    (- volume-left (* n volume))
                    (- weight-left (* n weight))
                    (cons (cons n item) sack)
                    (+ sack-value (* n item-val))))
       (cond [(> best-val* best-val) (values best* best-val*)]
             [(= best-val* best-val) (values (append best best*)
             [else                   (values best best-val)]))]))


          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze
is Life!
  Racket Users list:
CD: 3ms