Pascal's triangle in mit-scheme

Question

As suggested by the name of source file (ex1.12.scm), I just started learning mit-scheme by reading SICP. In Exercise 1.12, I'm asked to "compute elements of Pascal's triangle by means of a recursive process." For fun and extra practice, I wrote a program to print the whole triangle. (It took me several minutes to print a Pascal's triangle, and several hours to beautify it :/)

(define (pascal x)
  (define (pascal-iter m n max-len)
    (cond ((and (> m 0) (> n 0))
             (pascal-iter m (- n 1) max-len)       
             (beauti-print (pascal-item m n) max-len))
          ((= n 0) (pascal-iter (- m 1) (- m 1) max-len)
                   (display "\n")
                   (print-space (* (- x m) max-len)))
          ((= m 0) "Done")))
  (define (pascal-item m n)
    (cond ((= n 1) 1)
          ((= n m) 1)
          (else (+ (pascal-item (- m 1) (- n 1))
                   (pascal-item (- m 1) n)))))
  (define (beauti-print item max-len)
    (print-space (floor (- max-len
                       (/ (num-of-digit item) 2))))
    (display item)
    (print-space (ceiling (- max-len
                         (/ (num-of-digit item) 2)))))
  (define (num-of-digit n)
    (+ (floor (/ (log n) (log 10))) 1) )
  ;; (print-space 1)   -> " "
  ;; (print-space 1.5) -> "  "
  (define (print-space n)
    (cond ((> n 0) (display " ")
                (print-space (- n 1)))
          (else (display ""))))
  (pascal-iter x x (num-of-digit (pascal-item x (/ x 2)))))

(pascal 12)

Here is the output:

;Loading "ex1.12.scm"...

                                   1   
                                1     1   
                             1     2     1   
                          1     3     3     1   
                       1     4     6     4     1   
                    1     5     10    10    5     1   
                 1     6     15    20    15    6     1   
              1     7     21    35    35    21    7     1   
           1     8     28    56    70    56    28    8     1   
        1     9     36    84   126   126    84    36    9     1   
     1     10    45   120   210   252   210   120    45    10    1   
  1     11    55   165   330   462   462   330   165    55    11    1   
;... done

One of its drawbacks is obvious: recursion is very expensive. In fact, (pascal 15) would produce ;Aborting!: maximum recursion depth exceeded on my machine.

However, please don't put too much emphasis on performance-related issues when answering this question, because I think for me, for this moment, the form of good programming habits takes higher priority than the optimization of algorithm. As a result, please focus on readability, code style and so on.

Answer 1

Keep your concerns separated

One design principle that is vital to engineering good software is that of "separation of concerns". In other words, each function should be concerned with doing one, and only one, thing.

If you step back and take a look at the pascal function, you will see it's trying to do two things at once:

1. Compute Pascal's triangle
2. Pretty-print the triangle

You can separate these concerns.

Let's start with the pascal function. It should only compute the values in the triangle. It should return a list of "rows", where a row is represented a list of numbers.

So we can use pascal to compute a list of lists of numbers. Now we want to pretty-print this list. We could do this all in one function (and there's nothing really wrong with that). But if we're careful, we can make things more generic (and thus reusable). We can compose pretty-printing the triangle into the following:

• Formatting each row. This involves taking a list of numbers and returning a string representation for that row.
• Centering the rows. Basically, padding each string with spaces.
• Printing the rows. Taking the strings and print them each on separate lines.

We can define functions format-row, center-lines, and print-lines to handle these tasks. Now we can define a function pretty-print-pascal that combines these functions:

(define pretty-print-pascal (x)
  (print-lines (center-lines (map format-row (pascal x)))))

Answer 2

The sub-definition of pascal-item is what is being asked for in the 1.12 exercise. However it's entirely unsuited for calculating the entire triangle of X rows. Without a proper data structure (list of lists, vector, hash table...) poor pascal-item has to do all the work (and absent memiozation must to it many more times than is really necessary)

Not having the data structure also forces you to mix the printing logic with the step by step calculation of the triangle, which while clever makes it a bit hard to follow, and difficult to use either separately down the line.

My advice is to keep moving along in the book, at which point most of this will be more clear.