Monthly Archives: January 2013

Attempting to Count Change, Iteratively

I have discovered what I believe is a nice optimization for the tree-recursive change-counting procedure, cc, mentioned in a previous post. (In the first edition, it’s Exercise 1.9.)

Unfortunately I’m still struggling with the real problem: how to implement this problem to evolve an iterative process, as requested by the book. My attempts to recast the computation using only variables passed as procedure arguments are failing. These attempts always need more “registers” than I have available, and I start thinking in terms of some kind of “storage” where I can stash the intermediate problems that I can’t work on yet.

Of course, these “registers” are arguments to the function, and this “storage” is also known as the stack. And growing the stack is what we’re trying to avoid.

Scannning ahead in the text, Exercise 1.10 asks the reader to

Draw the tree illustrating the process generated by the (cc) procedure … making change for 11 cents.

Here’s what appeared in my notebook – Note that the procedure calls surrounded by boxes are the ones that return a value of 1. In this case, the return value of (cc 11 3) is 4, shown by the 4 boxed procedure calls:

../img/cc-larger-tree-scaled.jpg

While drawing out this tree, I noticed that once the procedure tries to make change for an amount using only pennies, it makes (* 2 amount) unnecessary procedure calls. It’s easy to see that they just bang down the list from amount to 0 and finally return 1. My idea was to reformulate the procedure so that we perform this check first, like so:

(define (cc-faster amount kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1) ; Are we making change with pennies? If so, there's only one way to do it!
        ((= amount 0) 1)
        ((or (< amount 0)
             (= kinds-of-coins 0)) 
         0)
        (else (+
               (cc-faster amount (- kinds-of-coins 1))
               (cc-faster (- amount (first-denomination kinds-of-coins)) 
                   kinds-of-coins)))))

Calling this procedure results in the following tree of procedure calls:

../img/cc-smaller-tree-scaled.jpg

Note that instead of 55 procedure calls, we now make only 15! And the discrepancy only grows wider as we count larger amounts of change, prompting me to make the following measurements using MIT Scheme – the with-timing-output macro is described at the bottom:

(with-timing-output (cc 700 5))
; Run time:     75.81
; GC time:      .34
; Actual time:  76.641
;Value: 207530

(with-timing-output (cc-faster 700 5))
; Run time:     .56
; GC time:      .02
; Actual time:  .608
;Value: 207530

This reduces running time from over a minute to less than a second, which is kind of exciting! It’s still not an iterative process, though.

Just for completeness, here’s how long the same procedure takes using m-cc, the memoizing version of cc described previously. Obviously looking stuff up in memory is faster than computing it over and over again:

(with-timing-output (m-cc 700 5))
; Run time:     0.
; GC time:      0.
; Actual time:  0.
;Value: 207530

And here’s the definition of the with-timing-output macro. It’s just sugar on top of the with-timings measurement procedure built into MIT Scheme:

(define-syntax with-timing-output
  (syntax-rules ()
    ((with-timing-output body)
     (with-timings 
         (lambda () body) 
       (lambda (run-time gc-time real-time)
         (display "Run time:\t")
         (write (internal-time/ticks->seconds run-time))
         (newline)
         (display "GC time:\t")
         (write (internal-time/ticks->seconds gc-time)) 
         (newline)
         (display "Actual time:\t")
         (write (internal-time/ticks->seconds real-time))
         (newline))))))

Next step: ITERATION!

Edwin `dired-do-shell-command’ on files

Evaluate this code in your Edwin REPL and you’re one step closer to being able to use Edwin as your primary file manager. I’ve reimplemented the Emacs `dired-do-shell-command’ function as an Edwin command (note that it puts these definitions in the `edwin dired’ environment’):

(ge '(edwin dired))

(define (string-join xs)
  (list->string (concatenate
    (map (lambda (s) (string->list s)) xs))))

(define (shell-command-prompt prompt)
  (prompt-for-string prompt #f
                            'DEFAULT-TYPE 'INSERTED-DEFAULT
                            'HISTORY 'SHELL-COMMAND))

(define (pathname->string pathname)
  (uri->string (pathname->uri pathname)))

(define-command dired-do-shell-command
  "Run a shell command on the file or directory at the current point."
  (lambda ()
    (list (shell-command-prompt "Shell command on file: ")
    (command-argument)))
  (lambda (command pathname)
    ((ref-command shell-command)
     (string-join
      (list command " "
            (pathname->string (dired-current-pathname)) " &")) #f)))

(define-key 'dired #\! 'dired-do-shell-command)

Reading Email from Edwin/Imail

After much consternation, poring over of manuals, and scouring of the Interwebs for a decent, working `stunnel.conf’, I am finally able to read my mail from Edwin. And yes, it is amazing.

I think it’s probably time for me to make some documentation contributions to MIT Scheme and stunnel both.

Call it one more stumbling block overcome on the road to “Full Edwin”.

For the record, here are a few things to note when setting up Edwin’s IMail program:

– Read the manual! It’s available in a lovely linked PDF at
http://gnu.org/s/mit-scheme.

– Don’t fiddle with the value of `imail-default-imap-server’. Instead, configure your `stunnel.conf’ as shown below.

– Even after reading the manual, you need to play around in IMail to learn how best to do things. (I’m still working on this, as I literally just got it set up this morning.)

Finally, here’s my working stunnel.conf:

# GLOBAL OPTIONS

debug = 7
output = /home/rml/stunnel.log

# SERVICE-LEVEL OPTIONS

[IMAP (Gmail) Incoming]
client = yes
accept = 127.0.0.1:143
connect = imap.gmail.com:993

[SMTP (Gmail) Outgoing]
client = yes
accept = 127.0.0.1:587
connect = smtp.gmail.com:465

Onward, aspiring Scheme wizards!

(Now to figure out how to send!)

Edwin Support for External Schemes

I’m pleased to announce an alpha release of support for using Edwin to interact with external Schemes. This is similar to the way Emacs can interact with REPLs from languages other than Emacs Lisp.

The code is available at http://github.com/rmloveland/edwin-external-scheme. The repository contains two Edwin modes, “External Scheme mode” and “External Scheme REPL mode”.

Usage

“External Scheme REPL mode” allows you to interact with an external Scheme REPL’s process from Edwin in the same way you would interact with a shell using `#\M-x shell’. Load the file `external-scheme-repl.scm’ and enter the command `#\M-x external-scheme-repl’. You’ll be asked to enter the name of the external Scheme you’d like to run, and away you go.

External Scheme mode inherits from Edwin’s Scheme mode for all of its formatting and editing commands, but provides its own commands for sending expressions to a running external Scheme REPL, if one exists.

Load the file `external-scheme-mode.scm’ and enter the command `#\M-x external-scheme-mode’ in a buffer containing Scheme code that you want to send to the external Scheme. Right now you can run only one external Scheme REPL, so be sure that the code you’re sending is going to be understood by that Scheme. It’s a simple matter of programming to extend this to multiple external Scheme buffers if you care to.

Caveats

Right now you may run only one external Scheme REPL at a time. Any Scheme buffers in External Scheme mode will send their eval’d code to that REPL.

Finally, note that files containing Scheme code are automatically opened by Edwin in its own Scheme mode, no matter what Scheme they’re written in, so you’ll need to do `#\M-x external-scheme-mode’.

Motivation

Finally, why bother? Isn’t MIT Scheme good enough? The answer is yes: it’s great. However, I often write scripts using Scheme Shell due to its tight integration with UNIX and excellent process notation. I could already write these programs in Emacs, but Edwin is my preferred editor.

Trading Space for Time

Working through SICP for the first time. Found a used first edition (hardcover, no less) on eBay. Some misguided person had marked each of the covers up with a giant X in black marker.

The first edition differs from the second in a few ways. For example, at the end of the tree-recursive change-counting problem on pages 39-40 of the second edition, the authors say “it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge”. They also note that memoization can be used to reduce the number of redundant computations that occur.

In other words, we can trade space for time.

In the first edition, Exercise 1.9 asks you to design a procedure that evolves an iterative process for solving the change-counting problem. I’m working on a solution to that problem; in the meantime, I implemented a procedure that I call memoizing-apply which does the following:

  1. See if an answer has already been computed and stored in a table *mr* (short for `memoized-results’).
  2. If the answer hasn’t already been computed, compute it. Then stick the answer in the table *mr*.

This process is known as memoization or tabulation, and *mr* serves as a lookup table.

We define a table *mr*, and a procedure memoized? that checks if the procedure has already been called with the current arguments. This assumes that the procedure always returns the same answer when you give it the same arguments.

(define *mr* '())

(define (memoized? args)
  (let ((result (assoc args *mr*)))
    (if result
        (cdr result)
        #f)))

Memoizing-apply does what we described above: it checks if the answer has already been computed (is already in the lookup table), and if so it just returns the answer. If not, it computes the answer and sticks it in the table.

(define (memoizing-apply f xs)
  (or (memoized? xs)
      (let ((result (apply f xs)))
      (begin (push! (cons xs result) *mr*)
             result))))

Note that push! is not a standard Scheme procedure; here’s the definition:

(define-syntax push!
  (syntax-rules ()
    ((push! item seq)
     (set! seq (cons item seq)))))

Let’s try it out. (Note that you can get the definitions for the procedures cc and first-denomination from a freely available copy of the book available at the SICP website.)

Here’s my modified version of cc, the change-counting procedure. I call it m-cc, and it uses the memoizing-apply procedure above to avoid doing redundant work:

(define (m-cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+
               (memoizing-apply m-cc (list amount (- kinds-of-coins 1)))
               (memoizing-apply m-cc (list (- amount (first-denomination kinds-of-coins))
                               kinds-of-coins))))))

The above code is different from the original in that it uses memoizing-apply to make the recursive call to itself. In my testing this is much faster than the equivalent cc version.

The memoization technique works very nicely, but it’s only appropriate in situations where memory is freely available. On most computers, most of the time, it’s probably the best way to go, since the tree-recursive implementation is readable and easy to understand. The exercise that asks you to solve the problem using an iterative process will likely be more complicated, but I’m not sure yet.