Practical Scheme Programming

Question

It's been a few months since I've touched Scheme and decided to implement a command line income partitioner using Scheme.

My initial implementation used plain recursion over the continuation, but I figured a continuation would be more appropriate to this type of program. I would appreciate it if anyone (more skilled with Scheme than I) could take a look at this and suggest improvements. I'm that the multiple (display... lines is an ideal opportunity to use a macro as well (I just haven't gotten to macros yet).

(define (ab-income)
  (call/cc
   (lambda (cc)
     (let
         ((out (display "Income: "))
          (income (string->number (read-line))))
       (cond
         ((<= income 600)
          (display (format "Please enter an amount greater than $600.00~n~n"))
          (cc (ab-income)))
         (else
          (let
              ((bills    (* (/ 30 100) income))
               (taxes    (* (/ 20 100) income))
               (savings  (* (/ 10 100) income))
               (checking (* (/ 40 100) income)))
            (display (format "~nDeduct for bills:---------------------- $~a~n" (real->decimal-string bills 2)))
            (display (format "Deduct for taxes:---------------------- $~a~n" (real->decimal-string taxes 2)))
            (display (format "Deduct for savings:-------------------- $~a~n" (real->decimal-string savings 2)))
            (display (format "Remainder for checking:---------------- $~a~n" (real->decimal-string checking 2))))))))))

Invoking (ab-income) asks for input and if anything below 600 is provided it (from my understanding) returns (ab-income) at the current-continuation. My first implementation (as I said earlier) used plain-jane recursion. It wasn't bad at all either but I figured every return call to (ab-income) if the value was below 600 kept expanding the function.

(please correct me if that apprehension is incorrect!)

Answer 1

First of all, you don't need a continuation. According to the standard, Scheme will always perform tail call optimization. A tail call is a function call which is in the final position in a function; after that call is run, nothing else will happen. In that situation, we don't need to preserve the activation record we're currently in; as soon as the function we call returns, we'll just pop it. Consequently, a tail call reuses the current activation record. As an example, consider this:

(define (some-function x y)
  (preprocess x)
  (combine (modified x) y))
(some-function alpha beta)

When we call some-function, we allocate space for its activation record on the stack: local variables, parameters, etc. We then call (preprocess x). Since we need to return to some-function and keep processing, we have to preserve some-function's activation record, and so we push a new activation record on for preprocess. Once that returns, we pop preprocess's stack frame and keep going. Next, we need to evaluate modified; the same thing has to happen, and when modified returns, its result is passed to combine. One would think we'd need to create a new activation record, run combine, and then return this to some-function—but some-function doesn't need to do anything with that result but return it! Thus, we overwrite the current activation record, but leave the return address alone; when combine returns, then, it will return its value to exactly what was waiting for it. Here, (combine (modified x) y) is a tail call, and evaluating it doesn't require an extra activation record.

This is how you can implement loops in Scheme, for instance:

(define (my-while cond body)
  (when (cond)
    (body)
    (my-while cond body)))

(let ((i 0))
  (my-while (lambda () (< i 10))
            (lambda () (display i) (newline) (set! i (+ i 1)))))

Without tail call optimization, this would be inefficient, and would potentially overflow with a long-running loop building up lots of calls to my-while. However, thanks to tail call optimization, the recursive call to my-while cond body is a jump, and allocates no memory, making this as efficient as iteration.

Secondly, you don't need any macros here. While you can abstract out the display block, you can do this with a plain function. Macros allow you, on some level, to change the syntax of the language—add your own sort of define, implement some type-case construct which doesn't evaluate all its branches, etc. Of course, it's all still s-expressions, but the semantics are no longer simply "evaluate the arguments and call the function". Here, however, function-call semantics are all you need.

With that said, I think this is how I'd implement your code:

(require (lib "string.ss"))

(define (print-report width . nvs)
  (if (null? nvs)
    (void)
    (let ((name  (car  nvs))
          (value (cadr nvs)))
      (display (format "~a:~a $~a~n"
                       name
                       (make-string (- width (string-length name) 2) #\-)
                       (real->decimal-string value 2)))
      (apply print-report width (cddr nvs)))))

(define (ab-income)
  (display "Income: ")
  (let ((income (string->number (read-line))))
    (if (or (not income) (<= income 600)) 
      (begin (display "Please enter an amount greater than $600.00\n\n")
             (ab-income))
      (begin (newline)
             (print-report 40 "Deduct for bills"       (* 3/10 income)
                              "Deduct for taxes"       (* 2/10 income)
                              "Deduct for savings"     (* 1/10 income)
                              "Remainder for checking" (* 4/10 income))))))

First, at least in my version of mzscheme, I needed a (require (lib "string.ss")) line to import real->decimal-string. Next, I abstracted out the display block you were talking about. What we see is that each line wants to print the money in the same format at the 40th column, printing a tag name and a row of dashes in front of it. Consequently, I wrote print-report. The first argument is the initial width; in this case, 40. The remaining arguments are field-value pairs. The length of each field (plus two for the colon and the space) are subtracted from the width, and we generate a string consisting of that many dashes. We use format to lay the fields out in the right order, and display to print the string. The function recurses over all the pairs (using tail recursion, so we won't blow the stack).

In the main function, I moved the (display "Income: ") to before the let; you ignore its result, so why assign it to a variable? I then augmented the if condition to test if input is false, which happens when string->number can't parse the input. Finally, I removed your local variables, since all you do is print them, and used Scheme's fraction syntax instead of division. (And of course, I use print-report instead of displays and formats.)

I think that's all; if you have any other questions about what I did, feel free to ask.