diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch25/spread-implement | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch25/spread-implement')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch25/spread-implement | 1835 |
1 files changed, 1835 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch25/spread-implement b/js/games/nluqo.github.io/~bh/ssch25/spread-implement new file mode 100644 index 0000000..dfc7d41 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch25/spread-implement @@ -0,0 +1,1835 @@ +<P> + +<P><A NAME="accountant"></A><CENTER><IMG SRC="../ss-pics/accountant.jpg" ALT="figure: accountant"></CENTER><P><CENTER>They did spreadsheets by hand in the old +days. +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 25: Implementing the Spreadsheet Program</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 25</H2> +<H1>Implementing the Spreadsheet Program</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../simply.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/ssch25.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../ssch24/spread.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="database.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT +Press web page for <CITE>Simply Scheme</CITE></A> +</TABLE></TABLE> + +<HR> + +<P>This is a big program and you can't keep it all in your head at once. In +this chapter, we'll discuss different parts of the program separately. For +example, while we're talking about the screen display procedures, we'll just +take the rest of the program for granted. We'll assume that we can ask for +the value in a cell, and some other part of the program will ensure that we +can find it out. + +<P>Our division of the program includes these parts: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The command processor, which reads user commands and oversees their +execution. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The specific commands: cell selection commands, <CODE>load</CODE>, and <CODE>put</CODE>. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The formula translator, which turns a formula into an <EM>expression</EM> +by translating relative cell positions to specific cells. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The dependency manager, which keeps track of which cells' expressions +depend on which other cells. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The expression evaluator. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The screen printer. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The cell management procedures, which store and retrieve cell +information for the rest of the program. + +</TABLE> +<P> + +<P>The diagram below shows the interconnections among these seven +parts of the program by showing what information they have to provide for +each other. + +<P><CENTER><IMG SRC="../ss-pics/dataflow.jpg" ALT="figure: dataflow"></CENTER> + +<P>(The arrows that <EM>aren't</EM> in the diagram convey as much +information as the ones that are. For example, since there is no arrow from +the evaluator to the printer, we know that when the spreadsheet program +redisplays the screen, the values printed are found directly in the data +structure; no new computation of formulas is needed.) + +<P><H2>Cells, Cell Names, and Cell IDs</H2> + +<P>The spreadsheet program does its work by manipulating cells. In this +section we introduce three abstract data types having to do with cells. +Before we jump into the spreadsheet procedures themselves, we must introduce +these three types, which are used throughout the program. + +<P>Each cell is a data structure that contains various pieces of information, +including its value and other things that we'll talk about later. Just as +these cells are arranged in a two-dimensional pattern on the screen, they +are kept within the program in a two-dimensional data structure: a vector +of vectors. + +<P>The elements of a vector are selected by number, using <CODE>vector-ref</CODE>. +Therefore, if we're looking for a particular cell, such as <CODE>c5</CODE>, what +the program really wants to know is that this cell is in column 3, row +5.<A NAME="text1" HREF="spread-implement#ft1">[1]</A> If the program refers to cells by +name, then there will be several occasions for it to split the word <CODE>c5</CODE> +into its pieces <CODE>c</CODE> and <CODE>5</CODE>, and to convert the letter <CODE>c</CODE> into +the number 3. These operations are fairly slow. To avoid carrying them out +repeatedly, the spreadsheet program identifies cells internally using a form +that's invisible to the person using the program, called a "cell ID." + +<P><A NAME="g1"></A> +<A NAME="g2"></A> +Therefore, there are three different <A NAME="g3"></A><A NAME="g4"></A>abstract data types in the +program that have to do with cells: cell names, such as <CODE>c5</CODE>; cell IDs; +and cells themselves. We've chosen to represent cell IDs as three-element +lists like this one: + +<P><PRE>(id 3 5) +</PRE> + + +<P>but you won't see much evidence of that fact within the program +because we've implemented selectors and constructors for all of these three +types. The representation includes the word <CODE>id</CODE> because one facility +that the program needs is the ability to determine whether some datum is or +is not a cell ID. The predicate <CODE>cell-id?</CODE> looks for a list whose first +element is <CODE>id</CODE>. + +<P>The selectors for cell IDs are <CODE>id-row</CODE> and <CODE>id-col</CODE>; both take a +cell ID as argument and return a number. The constructor, <CODE>make-id</CODE>, +takes a column number (not a letter) and a row number as arguments. + +<P>When the program recognizes a cell name typed by the user, it calls <CODE>cell-name->id</CODE> to translate the name to an ID, and only the ID is stored for +later use. + +<P>(These application-specific ADTs are similar to the database of known values +in the pattern matcher, as opposed to more general-purpose ADTs like +trees and sentences.) + +<P><H2>The Command Processor</H2> + +<P>Here's the core of the command processor: + +<P><PRE>(define (<A NAME="g5"></A>command-loop) + (print-screen) + (let ((command-or-formula (read))) + (if (equal? command-or-formula 'exit) + "Bye!" + (begin (process-command command-or-formula) + (command-loop))))) +</PRE> + +<P>This short program runs until the user types <CODE>exit</CODE>, because +it invokes itself as its last step. During each invocation, it prints the +current spreadsheet display, uses <CODE>read</CODE> to read a command, and +carries out whatever actions that command requires. Those actions probably +change something in the spreadsheet data, so the next cycle has to redisplay +the modified data before accepting another command. + +<P><CODE>Print-screen</CODE> is a large chunk of the program and will be discussed +in its own section. + +<P>How does <CODE>process-command</CODE> work? It looks for the command name (a word +such as <CODE>put</CODE>) in its list of known commands. The commands are kept in an +association list, like this: + +<P><PRE>((p …) (n …) (b …) (f …) (select …) (put …) (load …)) +</PRE> + +<P>Each of these sublists contains two elements: the name and the +procedure that carries out the command. We'll see shortly how these +procedures are invoked. + +<P>Looking for the command name is a little tricky because in the spreadsheet +language a command can be invoked either by typing its name inside +parentheses with arguments, as in Scheme, or by typing the name alone, +without parentheses, which Scheme wouldn't interpret as a request to invoke +a procedure. For example, the argument to <CODE>process-command</CODE> might be a +list, such as <CODE>(f 3)</CODE>, or just a word, such as <CODE>f</CODE>. A third case is +that the argument might not be one of these commands at all, but instead +might be a formula, just like one that could be used to determine the value +in a cell. <CODE>Process-command</CODE> must recognize these three cases: + +<P><PRE>(define (<A NAME="g6"></A>process-command command-or-formula) + (cond ((and (list? command-or-formula) + (command? (car command-or-formula))) + (execute-command command-or-formula)) + ((command? command-or-formula) + (execute-command (list command-or-formula 1))) + (else (exhibit (ss-eval (pin-down command-or-formula + (selection-cell-id))))))) +</PRE> + +<P>The <CODE>command?</CODE> predicate tells whether its argument is one of +the command names in the list. As you can see, if a command name is used +without parentheses, <CODE>process-command</CODE> pretends that it was given an +argument of <CODE>1</CODE>. + +<P><CODE>Execute-command</CODE> looks up the command name in the list of commands, +then applies the associated procedure to the arguments, if any: + +<P> +<PRE>(define (<A NAME="g7"></A>execute-command command) + (apply (get-command (car command)) + (cdr command))) +</PRE> + +<P>The <CODE>else</CODE> clause in <CODE>process-command</CODE>, which handles the case +of a formula typed instead of a command, invokes several procedures +that you haven't seen yet. We'll explain them when we get to the section of +the program that manipulates formulas. The only one that's used just for +command processing is <CODE>exhibit</CODE>: + +<P><PRE>(define (<A NAME="g8"></A>exhibit val) + (show val) + (show "Type RETURN to redraw screen") + (read-line) + (read-line)) +</PRE> + +<P>This prints a value on the screen, gives the user a chance to read +it, and then, when the user is ready, returns to processing commands. (This +will entail redrawing the spreadsheet display; that's why we have to wait for +the user to hit return.) The reason that we invoke <CODE>read-line</CODE> twice is +that the call to <CODE>read</CODE> from <CODE>command-loop</CODE> reads the spreadsheet +formula you typed but doesn't advance to the next line. Therefore, the +first <CODE>read-line</CODE> invocation gobbles that empty line; the second call to +<CODE>read-line</CODE> reads the (probably empty) line that the user typed in +response to the prompting message.<A NAME="text2" HREF="spread-implement#ft2">[2]</A> + +<P><H2>Cell Selection Commands</H2> + +<P>Several commands have to do with selecting a cell. We'll show just one +typical procedure, the one that carries out the <CODE>p</CODE> (previous row) +command: + +<P><PRE>(define (<A NAME="g9"></A>prev-row delta) + (let ((row (id-row (selection-cell-id)))) + (if (< (- row delta) 1) + (error "Already at top.") + (set-selected-row! (- row delta))))) + +(define (<A NAME="g10"></A>set-selected-row! new-row) + (select-id! (make-id (id-column (selection-cell-id)) new-row))) + +(define (<A NAME="g11"></A>select-id! id) + (set-selection-cell-id! id) + (adjust-screen-boundaries)) +</PRE> + +<CODE>Prev-row</CODE> must ensure that the selected cell is within the +legal boundaries. Since <CODE>prev-row</CODE> only moves upward, it has to check +only that we don't go beyond row 1. (<CODE>Next-row</CODE> will instead check that +we don't go beyond row 30 in the other direction.) + +<P><CODE>Adjust-screen-boundaries</CODE> checks for the situation in which the newly +selected cell, although within the bounds of the spreadsheet, is not within +the portion currently visible on the screen. In that case the visible +portion is shifted to include the selected cell. (The procedure is +straightforward and uninteresting, so we're not showing it here. You can +see it in the complete listing of the spreadsheet program at the end of this +chapter.) + +<P><CODE>Selection-cell-id</CODE> is a procedure that returns the cell ID of the +cell that's currently selected. Similarly, <CODE>set-selection-cell-id!</CODE> sets the +current selection. There are comparable procedures <CODE>screen-corner-cell-id</CODE> and <CODE>set-screen-corner-cell-id!</CODE> to keep track of +which cell should be in the upper left corner of the screen display. There +is a vector named <CODE>*special-cells*</CODE> that holds these two cell IDs; you +can see the details in the complete program listing. + +<P> +<H2>The <CODE><B>Load</B></CODE> Command</H2> + +<P>Loading commands from files is easy. The <CODE>command-loop</CODE> procedure, +which carries out commands from the keyboard, repeatedly reads a command +with <CODE>read</CODE> and invokes <CODE>process-command</CODE> to carry it out. To load +commands from a file, we want to do exactly the same thing, except that we +read from a file instead of from the keyboard: + +<P><PRE>(define (spreadsheet-load filename) + (let ((port (open-input-file filename))) + (sl-helper port) + (close-input-port port))) + +(define (sl-helper port) + (let ((command (read port))) + (if (eof-object? command) + 'done + (begin (show command) + (process-command command) + (sl-helper port))))) +</PRE> + +<P><H2>The <CODE><B>Put</B></CODE> Command</H2> + +<P>The <CODE>put</CODE> command takes two arguments, a formula and a place to put it. +The second of these can specify either a single cell or an entire row or +column. (If there is no second argument, then a single cell, namely the +selected cell, is implied.) <CODE>Put</CODE> invokes <CODE>put-formula-in-cell</CODE> +either once or several times, as needed. If only a single cell is involved, +then <CODE>put</CODE> calls <CODE>put-formula-in-cell</CODE> directly. If a row or column +is specified, then <CODE>put</CODE> uses the auxiliary procedure <CODE>put-all-cells-in-row</CODE> or <CODE>put-all-cells-in-col</CODE> as an intermediary. + +<P><PRE>(define (<A NAME="g12"></A>put formula . where) + (cond ((null? where) + (put-formula-in-cell formula (selection-cell-id))) + ((cell-name? (car where)) + (put-formula-in-cell formula (cell-name->id (car where)))) + ((number? (car where)) + (put-all-cells-in-row formula (car where))) + ((letter? (car where)) + (put-all-cells-in-col formula (letter->number (car where)))) + (else (error "Put it where?")))) +</PRE> + +<P>The only tricky part of this is the first line. <CODE>Put</CODE> can be +invoked with either one or two arguments. Therefore, the dot notation is +used to allow a variable number of arguments; the parameter <CODE>where</CODE> will +have as its value not the second argument itself, but a list that either +contains the second argument or is empty. Thus, if there is a second +argument, <CODE>put</CODE> refers to it as <CODE>(car where)</CODE>. + +<P><PRE>(define (<A NAME="g13"></A>put-all-cells-in-row formula row) + (put-all-helper formula (lambda (col) (make-id col row)) 1 26)) + +(define (<A NAME="g14"></A>put-all-cells-in-col formula col) + (put-all-helper formula (lambda (row) (make-id col row)) 1 30)) + +(define (<A NAME="g15"></A>put-all-helper formula id-maker this max) + (if (> this max) + 'done + (begin (try-putting formula (id-maker this)) + (put-all-helper formula id-maker (+ 1 this) max)))) + +(define (<A NAME="g16"></A>try-putting formula id) + (if (or (null? (cell-value id)) (null? formula)) + (put-formula-in-cell formula id) + 'do-nothing)) +</PRE> + +<P><CODE>Put-all-cells-in-row</CODE> and <CODE>put-all-cells-in-col</CODE> invoke +<CODE>put-all-helper</CODE>, which repeatedly puts the formula into a +cell.<A NAME="text3" HREF="spread-implement#ft3">[3]</A> <CODE>Put-all-helper</CODE> is a typical sequential recursion: Do +something for this element, and recur for the remaining elements. The +difference is that "this element" means a cell ID that combines one +constant index with one index that varies with each recursive call. How are +those two indices combined? What differs between filling a row and filling +a column is the <EM>function</EM> used to compute each cell ID. + +<P>The substitution model explains how the <CODE>lambda</CODE> expressions used as +arguments to <CODE>put-all-helper</CODE> implement this idea. Suppose we are +putting a formula into every cell in row 4. Then <CODE>put-all-cells-in-row</CODE> +will be invoked with the value <CODE>4</CODE> substituted for the parameter <CODE>row</CODE>. After this substitution, the body is + +<P><PRE>(put-all-helper formula (lambda (col) (make-id col 4)) 1 26) +</PRE> + +<P>The <CODE>lambda</CODE> expression creates a procedure that takes a +column number as argument and returns a cell ID for the cell in row 4 and +that column. This is just what <CODE>put-all-helper</CODE> needs. It invokes the +procedure with the varying column number as its argument to get the proper +cell ID. + +<P><CODE>Put-all-helper</CODE> doesn't directly invoke <CODE>put-formula-in-cell</CODE>. The +reason is that if a particular cell already has a value, then the new +formula isn't used for that particular cell, unless the formula is empty. +That is, you can erase an entire row or column at once, but a non-empty +formula affects only cells that were empty before this command. <CODE>Try-putting</CODE> decides whether or not to put the formula into each possible +cell. (In <CODE>try-putting</CODE>, the third argument to <CODE>if</CODE> could be +anything; we're interested only in what happens if the condition is true.) + +<P>All that's left is, finally, to put the formula into a cell: + +<P><PRE>(define (<A NAME="g17"></A>put-formula-in-cell formula id) + (put-expr (pin-down formula id) id)) +</PRE> + +<P>The two new procedures seen here, <CODE>pin-down</CODE> and <CODE>put-expr</CODE>, are both large sections of the program and are described in the +next two sections of this chapter. + +<P><H2>The Formula Translator</H2> + +<P>Suppose the user has said + +<P><PRE>(put (* (cell b) (cell c)) d) +</PRE> + +<P>The <CODE>put</CODE> procedure puts this formula into each cell of column +<CODE>d</CODE> by repeatedly calling <CODE>put-formula-in-cell</CODE>; as an example, +let's concentrate on cell <CODE>d4</CODE>. + +<P>The purpose of the formula is that later we're going to use it to compute a +value for <CODE>d4</CODE>. For that purpose, we will need to multiply two +particular numbers together: the ones in cells <CODE>b4</CODE> and <CODE>c4</CODE>. +Although the same formula applies to cell <CODE>d5</CODE>, the particular numbers +multiplied together will be found in different places. So instead of +storing the same general formula in every <CODE>d</CODE> cell, what we'd really +like to store in <CODE>d4</CODE> is something that refers specifically to <CODE>b4</CODE> and <CODE>c4</CODE>. + +<P>We'll use the term "expression" for a formula whose cell references have +been replaced by specific cell IDs. We started with the idea that we wanted +to put a formula into a cell; we've refined that idea so that we now want to +put an expression into the cell. This goal has two parts: We must +translate the formula (as given to us by the user in the <CODE>put</CODE> command) +to an expression, and we must store that expression in the cell data +structure. These two subtasks are handled by <CODE>pin-down</CODE>, discussed in +this section, and by <CODE>put-expr</CODE>, discussed in the next section. <CODE>Pin-down</CODE> is entirely functional; the only modification to the spreadsheet +program's state in this process is carried out by <CODE>put-expr</CODE>. + +<P>We'll refer to the process of translating a formula to an expression as +"pinning down" the formula; the procedure <CODE>pin-down</CODE> carries out this +process. It's called "pinning down" because we start with a <EM>general</EM> formula and end up with a <EM>specific</EM> expression. <CODE>Pin-down</CODE> takes two arguments: The first is, of course, a formula; the +second is the ID of the cell that will be used as the reference point for +relative cell positions. In the context of the <CODE>put</CODE> command, the +reference point is the cell into which we'll put the expression. But <CODE>pin-down</CODE> doesn't think about putting anything anywhere; its job is to +translate a formula (containing relative cell locations) into an expression +(containing only absolute cell IDs).<A NAME="text4" HREF="spread-implement#ft4">[4]</A> <CODE>Pin-down</CODE> needs a reference point +as a way to understand the notation <CODE><3</CODE>, which means "three +cells before the reference point." + +<P>Let's go back to the specific example. <CODE>Put-formula-in-cell</CODE> will invoke + +<P><PRE>(pin-down '(* (cell b) (cell c)) 'd4) +</PRE> + +<P>and <CODE>pin-down</CODE> will return the expression + +<P><PRE>(* (id 2 4) (id 3 4)) +</PRE> + +<P>The overall structure of this problem is tree recursive. That's because a +formula can be arbitrarily complicated, with sublists of sublists, just like +a Scheme expression: + +<P><PRE>(put (+ (* (cell b) (cell c)) (- (cell 2< 3>) 6)) f) +</PRE> + +<P>Here's <CODE>pin-down</CODE>: + +<P><PRE>(define (<A NAME="g18"></A>pin-down formula id) + (cond ((cell-name? formula) (cell-name->id formula)) + ((word? formula) formula) + ((null? formula) '()) + ((equal? (car formula) 'cell) + (pin-down-cell (cdr formula) id)) + (else (bound-check + (map (lambda (subformula) (pin-down subformula id)) + formula))))) +</PRE> + + +<P>The base cases of the tree recursion are specific cell names, such +as <CODE>c3</CODE>; other words, such as numbers and procedure names, which are +unaffected by <CODE>pin-down</CODE>; null formulas, which indicate that the user is +erasing the contents of a cell; and sublists that start with the word <CODE>cell</CODE>. The first three of these are trivial; the fourth, which we will +describe shortly, is the important case. If a formula is not one of these +four base cases, then it's a compound expression. In that case, we have to +pin down all of the subexpressions individually. (We basically <CODE>map</CODE> +<CODE>pin-down</CODE> over the formula. That's what makes this process tree +recursive.) + +<P>One complication is that the pinned-down formula might refer to nonexistent +cells. For example, saying + +<P><PRE>(put (+ (cell 2< 3<) 1) d) +</PRE> + +<P>refers to cells in column <CODE>b</CODE> (two to the left of <CODE>d</CODE>) +three rows above the current row. That works for a cell such as <CODE>d7</CODE>, +referring to cell <CODE>b4</CODE>, but not for <CODE>d2</CODE>, which has no row that's +three above it. (There is no row <CODE>-1</CODE>.) So our program must refrain +from pinning down this formula for cells <CODE>d1</CODE>, <CODE>d2</CODE>, and <CODE>d3</CODE>. +<CODE>Pin-down</CODE> will instead return the word <CODE>out-of-bounds</CODE> to signal +this situation. + +<P>The case of a nonexistent cell is discovered by <CODE>pin-down-cell</CODE> at the +base of a tree recursion. The <CODE>out-of-bounds</CODE> signal must be returned +not only by the base case but by the initial invocation of <CODE>pin-down</CODE>. +That's why <CODE>bound-check</CODE> is used to ensure that if any part of a formula +is out of bounds, the entire formula will also be considered out of bounds: + +<P><PRE>(define (<A NAME="g19"></A>bound-check form) + (if (member 'out-of-bounds form) + 'out-of-bounds + form)) +</PRE> + +<P>When a formula contains a <CODE>(cell …)</CODE> sublist, the procedure <CODE>pin-down-cell</CODE> is invoked to translate that notation into a cell ID. + +<P>The arguments to <CODE>pin-down-cell</CODE> are a list of the "arguments" of the +<CODE>cell</CODE> sublist and the reference point's cell ID. (The word +"arguments" is in quotation marks because the word <CODE>cell</CODE> doesn't +represent a Scheme procedure, even though the parenthesized notation looks +like an invocation. In a way, the special treatment of <CODE>cell</CODE> by <CODE>pin-down</CODE> is analogous to the treatment of special forms, such as <CODE>cond</CODE>, +by the Scheme evaluator.) + +<P>There can be one or two of these "arguments" to <CODE>cell</CODE>. A single +argument is either a number, indicating a row, or a letter, indicating a +column. Two arguments specify both a column and a row, in that order: + +<P><PRE>(define (<A NAME="g20"></A>pin-down-cell args reference-id) + (cond ((null? args) + (error "Bad cell specification: (cell)")) + ((null? (cdr args)) + (cond ((number? (car args)) ; they chose a row + (make-id (id-column reference-id) (car args))) + ((letter? (car args)) ; they chose a column + (make-id (letter->number (car args)) + (id-row reference-id))) + (else (error "Bad cell specification:" + (cons 'cell args))))) + (else + (let ((col (pin-down-col (car args) (id-column reference-id))) + (row (pin-down-row (cadr args) (id-row reference-id)))) + (if (and (>= col 1) (<= col 26) (>= row 1) (<= row 30)) + (make-id col row) + 'out-of-bounds))))) +</PRE> + +<P>In the two-argument case, the job of <CODE>pin-down-col</CODE> and <CODE>pin-down-row</CODE> is to understand notations like <CODE><3</CODE> for relative +rows and columns: + +<P><PRE>(define (pin-down-col new old) + (cond ((equal? new '*) old) + ((equal? (first new) '>) (+ old (bf new))) + ((equal? (first new) '<) (- old (bf new))) + ((letter? new) (letter->number new)) + (else (error "What column?")))) + +(define (pin-down-row new old) + (cond ((number? new) new) + ((equal? new '*) old) + ((equal? (first new) '>) (+ old (bf new))) + ((equal? (first new) '<) (- old (bf new))) + (else (error "What row?")))) +</PRE> + +<P><H2>The Dependency Manager</H2> + +<P>The remaining part of the <CODE>put</CODE> command is <CODE>put-expr</CODE>, which actually +stores the translated expression in the cell data structure. You might +imagine that putting an expression into a cell would require nothing more +than invoking a mutator, like this: + +<P><PRE>(define (put-expr expr cell) ;; wrong + (set-cell-expr! cell expr)) +</PRE> + +<P>The trouble is that adding an expression to a cell might have many +consequences beyond the mutation itself. For example, suppose we say + +<P><PRE>(put (+ a3 b2) c4) +</PRE> + +<P>If cells <CODE>a3</CODE> and <CODE>b2</CODE> already have values, we can't just +put the formula into <CODE>c4</CODE>; we must also compute its value and put that +value into <CODE>c4</CODE>. + +<P>Also, once <CODE>c4</CODE> has a value, that could trigger the computation of +some other cell's value. If we've previously said + +<P><PRE>(put (+ a3 c4) b5) +</PRE> + +<P>then we're now able to compute a value for <CODE>b5</CODE> because both +of the cells that it depends on have values. + +<P>All this implies that what's inside a cell is more than just an expression, or +even an expression and a value. Each cell needs to know which other cells it +depends on for its value, and also which other cells depend on it. + +<P><A NAME="g21"></A> +<A NAME="g22"></A> +Our program represents each cell as a four-element vector. Each cell +includes a value, an expression, a list of <EM>parents</EM> (the cells that it +depends on), and a list of <EM>children</EM> (the cells that depend on it). +The latter two lists contain cell IDs. So our example cell <CODE>c4</CODE> might +look like this: + +<P><PRE>#(12 + (+ (id 1 3) (id 2 2)) + ((id 1 3) (id 2 2)) + ((id 2 5))) +</PRE> + +<P>In a simpler case, suppose we put a value into a cell that nothing +depends on, by saying, for example, + +<P><PRE>(put 6 a1) +</PRE> + +<P>Then cell <CODE>a1</CODE> would contain + +<P><PRE>#(6 6 () ()) +</PRE> + +<P>(Remember that a value is just a very simple formula.) + +<P>There are selectors <CODE>cell-value</CODE> and so on that take a cell ID as +argument, and mutators <CODE>set-cell-value!</CODE> and so on that take a cell ID +and a new value as arguments. There's also the constructor <CODE>make-cell</CODE>, +but it's called only at the beginning of the program, when the 780 cells in +the spreadsheet are created at once. + +<P>When a cell is given a new expression, several things change: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The new expression becomes the cell's expression, of course. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The cells mentioned in the expression become the parents of this cell. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">This cell becomes a child of the cells mentioned in the expression. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">If all the parents have values, the value of this cell is computed. + +</TABLE><P> +Some of these changes are simple, but others are complicated. For example, +it's not enough to tell the cell's new parents that the cell is now their child +(the third task). First we have to tell the cell's <EM>old</EM> parents that this cell <EM>isn't</EM> their child any more. That +has to be done before we forget the cell's old parents. + +<P>Here is an example. (In the following tables, we represent the data structures +as if cells were represented by their names, even though really their IDs +are used. We've done this to make the example more readable.) Suppose that +we have five cells set up like this: + +<P><TABLE><TR><TH>cell <TH>expression <TH>value +<TH>parents <TH>children +<TR><TD> <TR><TD><CODE>a1</CODE><TD><CODE>20</CODE> +<TD><CODE>20</CODE><TD><CODE>()</CODE><TD><CODE>(a2)</CODE> +<TR><TD><CODE>b1</CODE><TD><CODE>5</CODE><TD><CODE>5</CODE><TD><CODE>()</CODE> +<TD><CODE>(a2 b2)</CODE> +<TR><TD><CODE>c1</CODE><TD><CODE>8</CODE><TD><CODE>8</CODE><TD><CODE>()</CODE> +<TD><CODE>()</CODE> +<TR><TD><CODE>a2</CODE><TD><CODE>(+ a1 b1)</CODE><TD><CODE>25</CODE> +<TD><CODE>(a1 b1)</CODE><TD><CODE>(b2)</CODE> +<TR><TD><CODE>b2</CODE><TD><CODE>(+ a2 b1)</CODE><TD><CODE>30</CODE> +<TD><CODE>(a2 b1)</CODE><TD><CODE>()</CODE> +</TABLE> + + +<P>If we now enter the spreadsheet command + +<P><PRE>(put (+ b1 c1) a2) +</PRE> + +<P>the program must first remove <CODE>a2</CODE> from the children of its +old parents (changes are shown in boldface): + +<P><TABLE><TR><TH>cell <TH>expression <TH>value +<TH>parents <TH>children +<TR><TD> <TR><TD><CODE>a1</CODE><TD><CODE>20</CODE> +<TD><CODE>20</CODE><TD><CODE>()</CODE><TD><CODE><STRONG><BIG>()</BIG></STRONG></CODE> +<TR><TD><CODE>b1</CODE><TD><CODE>5</CODE><TD><CODE>5</CODE><TD><CODE>()</CODE> +<TD><CODE><STRONG><BIG>(b2)</BIG></STRONG></CODE> +<TR><TD><CODE>c1</CODE><TD><CODE>8</CODE><TD><CODE>8</CODE><TD><CODE>()</CODE> +<TD><CODE>()</CODE> +<TR><TD><CODE>a2</CODE><TD><CODE>(+ a1 b1)</CODE><TD><CODE>25</CODE> +<TD><CODE>(a1 b1)</CODE><TD><CODE>(b2)</CODE> +<TR><TD><CODE>b2</CODE><TD><CODE>(+ a2 b1)</CODE><TD><CODE>30</CODE> +<TD><CODE>(a2 b1)</CODE><TD><CODE>()</CODE> +</TABLE> + + +<P>Then the program can change the expression and compute a new list of +parents: + +<P> +<TABLE><TR><TH>cell <TH>expression <TH>value +<TH>parents <TH>children +<TR><TD> <TR><TD><CODE>a1</CODE><TD><CODE>20</CODE> +<TD><CODE>20</CODE><TD><CODE>()</CODE><TD><CODE>()</CODE> +<TR><TD><CODE>b1</CODE><TD><CODE>5</CODE><TD><CODE>5</CODE><TD><CODE>()</CODE> +<TD><CODE>(b2)</CODE> +<TR><TD><CODE>c1</CODE><TD><CODE>8</CODE><TD><CODE>8</CODE><TD><CODE>()</CODE> +<TD><CODE>()</CODE> +<TR><TD><CODE>a2</CODE><TD><CODE><STRONG><BIG>(+ b1 c1)</BIG></STRONG></CODE> +<TD><CODE>25</CODE><TD><CODE><STRONG><BIG>(b1 c1)</BIG></STRONG></CODE> +<TD><CODE>(b2)</CODE> +<TR><TD><CODE>b2</CODE><TD><CODE>(+ a2 b1)</CODE><TD><CODE>30</CODE> +<TD><CODE>(a2 b1)</CODE><TD><CODE>()</CODE> +</TABLE> + + +<P>Next it can tell the new parents to add <CODE>a2</CODE> as a +child, and can compute <CODE>a2</CODE>'s new value: + +<P><TABLE><TR><TH>cell <TH>expression <TH>value +<TH>parents <TH>children +<TR><TD> <TR><TD><CODE>a1</CODE><TD><CODE>20</CODE> +<TD><CODE>20</CODE><TD><CODE>()</CODE><TD><CODE>()</CODE> +<TR><TD><CODE>b1</CODE><TD><CODE>5</CODE><TD><CODE>5</CODE><TD><CODE>()</CODE> +<TD><CODE><STRONG><BIG>(a2 b2)</BIG></STRONG></CODE> +<TR><TD><CODE>c1</CODE><TD><CODE>8</CODE><TD><CODE>8</CODE><TD><CODE>()</CODE> +<TD><CODE><STRONG><BIG>(a2)</BIG></STRONG></CODE> +<TR><TD><CODE>a2</CODE><TD><CODE>(+ b1 c1)</CODE> +<TD><CODE><STRONG><BIG>13</BIG></STRONG></CODE><TD><CODE>(b1 c1)</CODE> +<TD><CODE>(b2)</CODE> +<TR><TD><CODE>b2</CODE><TD><CODE>(+ a2 b1)</CODE><TD><CODE>30</CODE> +<TD><CODE>(a2 b1)</CODE><TD><CODE>()</CODE> +</TABLE> + + +<P>Changing <CODE>a2</CODE>'s value affects the values of all of its +children, and also its grandchildren and so on (except that in this example +there are no grandchildren): + +<P><TABLE><TR><TH>cell <TH>expression <TH>value +<TH>parents <TH>children +<TR><TD> <TR><TD><CODE>a1</CODE><TD><CODE>20</CODE> +<TD><CODE>20</CODE><TD><CODE>()</CODE><TD><CODE>()</CODE> +<TR><TD><CODE>b1</CODE><TD><CODE>5</CODE><TD><CODE>5</CODE><TD><CODE>()</CODE> +<TD><CODE>(a2 b2)</CODE> +<TR><TD><CODE>c1</CODE><TD><CODE>8</CODE><TD><CODE>8</CODE><TD><CODE>()</CODE> +<TD><CODE>(a2)</CODE> +<TR><TD><CODE>a2</CODE><TD><CODE>(+ b1 c1)</CODE> +<TD><CODE>13</CODE><TD><CODE>(b1 c1)</CODE> +<TD><CODE>(b2)</CODE> +<TR><TD><CODE>b2</CODE><TD><CODE>(+ a2 b1)</CODE> +<TD><CODE><STRONG><BIG>18</BIG></STRONG></CODE><TD><CODE>(a2 b1)</CODE><TD><CODE>()</CODE> +</TABLE> + + +<P>Now that we've considered an example, here is the main procedure that +oversees all these tasks: + +<P><PRE>(define (<A NAME="g23"></A>put-expr expr-or-out-of-bounds id) + (let ((expr (if (equal? expr-or-out-of-bounds 'out-of-bounds) + '() + expr-or-out-of-bounds))) + (for-each (lambda (old-parent) + (set-cell-children! + old-parent + (remove id (cell-children old-parent)))) + (cell-parents id)) + (set-cell-expr! id expr) + (set-cell-parents! id (remdup (extract-ids expr))) + (for-each (lambda (new-parent) + (set-cell-children! + new-parent + (cons id (cell-children new-parent)))) + (cell-parents id)) + (figure id))) +</PRE> + +Remember that <CODE>put-expr</CODE>'s first argument is the return value +from <CODE>pin-down</CODE>, so it might be the word <CODE>out-of-bounds</CODE> instead of +an expression. In this case, we store an empty list as the expression, +indicating that there is no active expression for this cell. + +<P>Within the body of the <CODE>let</CODE> there are five Scheme expressions, each of +which carries out one of the tasks we've listed. The first expression tells +the cell's former parents that the cell is no longer their child. The second +expression stores the expression in the cell. + +<P>The third Scheme expression invokes <CODE>extract-ids</CODE> to find all the cell +ids used in <CODE>expr</CODE>, removes any duplicates, and establishes those +identified cells as the argument cell's parents. (You wrote <CODE>remdup</CODE> in +Exercise <A HREF="../ssch14/recur-patterns.html#remdup">14.3</A>.) For example, if the <CODE>expr</CODE> is + +<P><PRE>(+ (id 4 2) (* (id 1 3) (id 1 3))) +</PRE> + +<P>then <CODE>extract-ids</CODE> will return the list + +<P><PRE>((id 4 2) (id 1 3) (id 1 3)) +</PRE> + +<P>and <CODE>remdup</CODE> of that will be + +<P><PRE>((id 4 2) (id 1 3)) +</PRE> + +<P>The fourth expression in the <CODE>let</CODE> tells each of the new parents to +consider the argument cell as its child. The fifth expression may or may +not compute a new value for this cell. (As we'll see in a moment, that +process is a little complicated.) + +<P>Two of these steps require closer examination. Here is the procedure used +in the third step: + +<P><PRE>(define (<A NAME="g24"></A>extract-ids expr) + (cond ((id? expr) (list expr)) + ((word? expr) '()) + ((null? expr) '()) + (else (append (extract-ids (car expr)) + (extract-ids (cdr expr)))))) +</PRE> + +<P>This is a tree recursion. The first three <CODE>cond</CODE> clauses are +base cases; cell IDs are included in the returned list, while other words +are ignored. For compound expressions, we use the trick of making recursive +calls on the <CODE>car</CODE> and <CODE>cdr</CODE> of the list. We combine the results +with <CODE>append</CODE> because <CODE>extract-ids</CODE> must return a flat list of +cell IDs, not a cheap tree. + +<P>The fifth step in <CODE>put-expr</CODE> is complicated because, as we saw in the +example, changing the value of one cell may require us to recompute the +value of other cells: + +<P><PRE>(define (<A NAME="g25"></A>figure id) + (cond ((null? (cell-expr id)) (setvalue id '())) + ((all-evaluated? (cell-parents id)) + (setvalue id (ss-eval (cell-expr id)))) + (else (setvalue id '())))) + +(define (<A NAME="g26"></A>all-evaluated? ids) + (cond ((null? ids) #t) + ((not (number? (cell-value (car ids)))) #f) + (else (all-evaluated? (cdr ids))))) + +(define (<A NAME="g27"></A>setvalue id value) + (let ((old (cell-value id))) + (set-cell-value! id value) + (if (not (equal? old value)) + (for-each figure (cell-children id)) + 'do-nothing))) +</PRE> + +<P><CODE>Figure</CODE> is invoked for the cell whose expression we've just +changed. If there is no expression (that is, if we've changed it to an empty +expression or to an out-of-bounds one), then <CODE>figure</CODE> will remove any old +value that might be left over from a previous expression. If there is an +expression, then <CODE>figure</CODE> will compute and save a new value, but only if +all of this cell's parents have numeric values. If any parent doesn't have +a value, or if its value is a non-numeric label, then <CODE>figure</CODE> has to +remove the value from this cell. + +<P><CODE>Setvalue</CODE> actually puts the new value in the cell. It first looks up +the old value. If the new and old values are different, then all of the +children of this cell must be re-<CODE>figure</CODE>d. This, too, is a tree +recursion because there might be several children, and each of them might +have several children. + +<P>We haven't yet explained how <CODE>ss-eval</CODE> actually computes the value from +the expression. That's the subject of the next major part of the program. + +<P><H2>The Expression Evaluator</H2> + +<P><CODE>Figure</CODE> invokes <CODE>ss-eval</CODE> to convert a cell's expression into its +value. Also, we've seen earlier that <CODE>process-command</CODE> uses <CODE>ss-eval</CODE> to evaluate an expression that the user types in response to a +spreadsheet prompt. (That is, <CODE>ss-eval</CODE> is invoked if what the user +types isn't one of the special commands recognized by <CODE>process-command</CODE> +itself.) + +<P>The <CODE>ss</CODE> in <CODE>ss-eval</CODE> stands for "spreadsheet"; it distinguishes +this procedure from <A NAME="g28"></A><CODE>eval</CODE>, a primitive procedure that evaluates +Scheme expressions. As it turns out, <CODE>ss-eval</CODE>'s algorithm is +similar in many ways to that of Scheme's <CODE>eval</CODE>, although <CODE>ss-eval</CODE> +is much simpler in other ways. The experience you already have with +Scheme's expression evaluation will help you understand the spreadsheet's. + +<P>Scheme's evaluator takes an expression and computes the corresponding value. +The expressions look quite different from the values, but there are +well-defined rules (the ones we studied in Chapter 3) to translate +expressions to values. In the spreadsheet language, as in Scheme, an +expression can be one of three things: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">a constant expression (a number or quoted word), whose value is itself. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">a variable (a cell ID, in the case of the spreadsheet language). +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">a procedure invocation enclosed in parentheses. + +</TABLE><P> +The spreadsheet language is simpler than Scheme for three main reasons. + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">There are no special forms such as <CODE>if</CODE> or <CODE>define</CODE>.<A NAME="text5" HREF="spread-implement#ft5">[5]</A> +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The only variables, the cell IDs, are global; in Scheme, much of the +complexity of evaluation has to do with variables that are local to +procedures (i.e., formal parameters). +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">The only procedures are primitives, so there is no need to evaluate +procedure bodies. + +</TABLE><P> +The structure of <CODE>ss-eval</CODE> is a <CODE>cond</CODE> whose clauses handle the +three types of expressions. Constants and variables are easy; +invocations require recursively evaluating the arguments before the +procedure can be invoked. + +<P><PRE>(define (<A NAME="g29"></A>ss-eval expr) + (cond ((number? expr) expr) + ((quoted? expr) (quoted-value expr)) + ((id? expr) (cell-value expr)) + ((invocation? expr) + (apply (get-function (car expr)) + (map ss-eval (cdr expr)))) + (else (error "Invalid expression:" expr)))) +</PRE> + +<P>The value of a number is itself; the value of a quoted word is the word +without the quotation mark. (Actually, by the time <CODE>ss-eval</CODE> sees a +quoted word, Scheme has translated the <CODE>'abc</CODE> notation into <CODE>(quote abc)</CODE> and that's what we deal with here. Also, double-quoted strings +look different to the program from single-quoted words.) + +<P><PRE>(define (<A NAME="g30"></A>quoted? expr) + (or (string? expr) + (and (list? expr) (equal? (car expr) 'quote)))) + +(define (<A NAME="g31"></A>quoted-value expr) + (if (string? expr) + expr + (cadr expr))) +</PRE> + +<P>The third clause checks for a cell ID; the value of such an +expression is the value stored in the corresponding cell. + +<P>If an expression is none of those things, it had better be a function +invocation, that is, a list. In that case, <CODE>ss-eval</CODE> has to do three +things: It looks up the function name in a table (as we did earlier for +spreadsheet commands); it recursively evaluates all the argument +subexpressions; and then it can invoke <CODE>apply</CODE> to apply the procedure to +the argument values. + +<P><CODE>Get-function</CODE> looks up a function name in the name-to-function +association list and returns the corresponding Scheme procedure. Thus, only +the functions included in the list can be used in spreadsheet formulas. + +<P>The entire expression evaluator, including <CODE>ss-eval</CODE> and its helper +procedures, is functional. Like the formula translator, it doesn't change +the state of the spreadsheet. + +<P><H2>The Screen Printer</H2> + +<P>The procedures that print the spreadsheet on the screen are straightforward +but full of details. Much of the work here goes into those details. + +<P>As we mentioned earlier, a better spreadsheet program wouldn't redraw the +entire screen for each command but would change only the parts of the +screen that were affected by the previous command. However, Scheme does not +include a standard way to control the positioning of text on the screen, so +we're stuck with this approach. + +<P><PRE>(define (<A NAME="g32"></A>print-screen) + (newline) + (newline) + (newline) + (show-column-labels (id-column (screen-corner-cell-id))) + (show-rows 20 + (id-column (screen-corner-cell-id)) + (id-row (screen-corner-cell-id))) + (display-cell-name (selection-cell-id)) + (show (cell-value (selection-cell-id))) + (display-expression (cell-expr (selection-cell-id))) + (newline) + (display "?? ")) +</PRE> + +<P><CODE>Screen-corner-cell-id</CODE> returns the ID of the cell that +should be shown in the top left corner of the display; <CODE>selection-cell-id</CODE> returns the ID of the selected cell. + +<P><CODE>Show-column-labels</CODE> prints the first row of the display, the one with +the column letters. <CODE>Show-rows</CODE> is a sequential recursion that prints +the actual rows of the spreadsheet, starting with the row number of the <CODE>screen-corner</CODE> cell and continuing for 20 rows. (There are 30 rows in the +entire spreadsheet, but they don't all fit on the screen at once.) The rest +of the procedure displays the value and expression of the selected cell at +the bottom of the screen and prompts for the next command. + +<P>Why isn't <CODE>display-expression</CODE> just <CODE>display</CODE>? +Remember that the spreadsheet stores expressions in a form like + +<P><PRE>(+ (id 2 5) (id 6 3)) +</PRE> + +<P>but the user wants to see + +<P><PRE>(+ b5 f3) +</PRE> + +<P><CODE>Display-expression</CODE> is yet another tree recursion over +expressions. Just as <CODE>pin-down</CODE> translates cell names into cell IDs, +<CODE>display-expression</CODE> translates IDs back into names. (But <CODE>display-expression</CODE> prints as it goes along, instead of reconstructing and +returning a list.) The definition of <CODE>display-expression</CODE>, along with +the remaining details of printing, can be seen in the full program listing +at the end of this chapter. + +<P>Just to give the flavor of those details, here is the part that displays +the rectangular array of cell values. <CODE>Show-rows</CODE> is a sequential +recursion in which each invocation prints an entire row. It does so by +invoking <CODE>show-row</CODE>, another sequential recursion, in which each +invocation prints a single cell value. + +<P><PRE>(define (show-rows to-go col row) + (cond ((= to-go 0) 'done) + (else + (display (align row 2 0)) + (display " ") + (show-row 6 col row) + (newline) + (show-rows (- to-go 1) col (+ row 1))))) + +(define (show-row to-go col row) + (cond ((= to-go 0) 'done) + (else + (display (if (selected-indices? col row) ">" " ")) + (display-value (cell-value-from-indices col row)) + (display (if (selected-indices? col row) "<" " ")) + (show-row (- to-go 1) (+ 1 col) row)))) + +(define (selected-indices? col row) + (and (= col (id-column (selection-cell-id))) + (= row (id-row (selection-cell-id))))) +</PRE> + +<P>Why didn't we write <CODE>show-row</CODE> in the following way? + +<P><PRE>(define (show-row to-go col row) ;; alternate version + (cond ((= to-go 0) 'done) + (else + (let ((id (make-id col row))) + (display (if (equal? id (selection-cell-id)) ">" " ")) + (display-value (cell-value id)) + (display (if (equal? id (selection-cell-id)) "<" " ")) + (show-row (- to-go 1) (+ 1 col) row))))) +</PRE> + +<P>That would have worked fine and would have been a little clearer. +In fact, we did write <CODE>show-row</CODE> this way originally. But it's a little +time-consuming to construct an ID, and <CODE>show-row</CODE> is called 120 times +whenever <CODE>print-screen</CODE> is used. Since printing the screen was +annoyingly slow, we sped things up as much as we could, even at the cost of +this kludge. + +<P><H2>The Cell Manager</H2> + +<P>The program keeps information about the current status of the spreadsheet +cells in a vector called <CODE>*the-spreadsheet-array*</CODE>. It contains all of +the 780 cells that make up the spreadsheet (30 rows of 26 columns). It's +not a vector of length 780; rather, it's a vector of length 30, each of whose +elements is itself a vector of length 26. In other words, each element of +the spreadsheet array is a vector representing one row of the spreadsheet. +(Each element of <EM>those</EM> vectors is one cell, which, as you recall, is +represented as a vector of length four. So the spreadsheet array is a +vector of vectors of vectors!) + +<P>The selectors for the parts of a cell take the cell's ID as argument and +return one of the four elements of the cell vector. Each must therefore be +implemented as two steps: We must find the cell vector, given its ID; and +we must then select an element from the cell vector. The first step is +handled by the selector <CODE>cell-structure</CODE> that takes a cell ID as +argument: + +<P><PRE>(define (<A NAME="g33"></A>cell-structure id) + (global-array-lookup (id-column id) + (id-row id))) + +(define (<A NAME="g34"></A>global-array-lookup col row) + (if (and (<= row 30) (<= col 26)) + (vector-ref (vector-ref *the-spreadsheet-array* (- row 1)) + (- col 1)) + (error "Out of bounds"))) +</PRE> + +<P><CODE>Global-array-lookup</CODE> makes sure the desired cell exists. +It also compensates for the fact that Scheme vectors begin with element +number zero, while our spreadsheet begins with row and column number one. +Two invocations of <CODE>vector-ref</CODE> are needed, one to select an entire row +and the next to select a cell within that row. + +<P>Selectors and mutators for the parts of a cell are written using +<CODE>cell-structure</CODE>: + +<P><PRE>(define (<A NAME="g35"></A>cell-value id) + (vector-ref (cell-structure id) 0)) + +(define (<A NAME="g36"></A>set-cell-value! id val) + (vector-set! (cell-structure id) 0 val)) + +(define (<A NAME="g37"></A>cell-expr id) + (vector-ref (cell-structure id) 1)) + +(define (<A NAME="g38"></A>set-cell-expr! id val) + (vector-set! (cell-structure id) 1 val)) + +(define (<A NAME="g39"></A>cell-parents id) + (vector-ref (cell-structure id) 2)) + +(define (<A NAME="g40"></A>set-cell-parents! id val) + (vector-set! (cell-structure id) 2 val)) + +(define (<A NAME="g41"></A>cell-children id) + (vector-ref (cell-structure id) 3)) + +(define (<A NAME="g42"></A>set-cell-children! id val) + (vector-set! (cell-structure id) 3 val)) +</PRE> + +<P>The constructor is + +<P><PRE>(define (make-cell) + (vector '() '() '() '())) +</PRE> + +<P>The spreadsheet program begins by invoking <CODE>init-array</CODE> to set up this +large array. (Also, it sets the initial values of the selected cell and the +screen corner.) + +<P><PRE>(define (<A NAME="g43"></A>spreadsheet) + (init-array) + (set-selection-cell-id! (make-id 1 1)) + (set-screen-corner-cell-id! (make-id 1 1)) + (command-loop)) + +(define *the-spreadsheet-array* (make-vector 30)) + +(define (<A NAME="g44"></A>init-array) + (fill-array-with-rows 29)) + +(define (<A NAME="g45"></A>fill-array-with-rows n) + (if (< n 0) + 'done + (begin (vector-set! *the-spreadsheet-array* n (make-vector 26)) + (fill-row-with-cells + (vector-ref *the-spreadsheet-array* n) 25) + (fill-array-with-rows (- n 1))))) + +(define (<A NAME="g46"></A>fill-row-with-cells vec n) + (if (< n 0) + 'done + (begin (vector-set! vec n (make-cell)) + (fill-row-with-cells vec (- n 1))))) +</PRE> + +<P> +<P>That's the end of the project, apart from some straightforward procedures +such as <CODE>letter->number</CODE> that you can look up in the complete listing +if you're interested. + +<P><H2>Complete Program Listing</H2> + +<P><P><P><PRE> +(define (spreadsheet) + (init-array) + (set-selection-cell-id! (make-id 1 1)) + (set-screen-corner-cell-id! (make-id 1 1)) + (command-loop)) + +(define (command-loop) + (print-screen) + (let ((command-or-formula (read))) + (if (equal? command-or-formula 'exit) + "Bye!" + (begin (process-command command-or-formula) + (command-loop))))) + +(define (process-command command-or-formula) + (cond ((and (list? command-or-formula) + (command? (car command-or-formula))) + (execute-command command-or-formula)) + ((command? command-or-formula) + (execute-command (list command-or-formula 1))) + (else (exhibit (ss-eval (pin-down command-or-formula + (selection-cell-id))))))) + +(define (execute-command command) + (apply (get-command (car command)) + (cdr command))) + +(define (exhibit val) + (show val) + (show "Type RETURN to redraw screen") + (read-line) + (read-line)) + + +;;; Commands + +;; Cell selection commands: F, B, N, P, and SELECT + +(define (prev-row delta) + (let ((row (id-row (selection-cell-id)))) + (if (< (- row delta) 1) + (error "Already at top.") + (set-selected-row! (- row delta))))) + +(define (next-row delta) + (let ((row (id-row (selection-cell-id)))) + (if (> (+ row delta) 30) + (error "Already at bottom.") + (set-selected-row! (+ row delta))))) + +(define (prev-col delta) + (let ((col (id-column (selection-cell-id)))) + (if (< (- col delta) 1) + (error "Already at left.") + (set-selected-column! (- col delta))))) + +(define (next-col delta) + (let ((col (id-column (selection-cell-id)))) + (if (> (+ col delta) 26) + (error "Already at right.") + (set-selected-column! (+ col delta))))) + +(define (set-selected-row! new-row) + (select-id! (make-id (id-column (selection-cell-id)) new-row))) + +(define (set-selected-column! new-column) + (select-id! (make-id new-column (id-row (selection-cell-id))))) + +(define (select-id! id) + (set-selection-cell-id! id) + (adjust-screen-boundaries)) + +(define (select cell-name) + (select-id! (cell-name->id cell-name))) + +(define (adjust-screen-boundaries) + (let ((row (id-row (selection-cell-id))) + (col (id-column (selection-cell-id)))) + (if (< row (id-row (screen-corner-cell-id))) + (set-corner-row! row) + 'do-nothing) + (if (>= row (+ (id-row (screen-corner-cell-id)) 20)) + (set-corner-row! (- row 19)) + 'do-nothing) + (if (< col (id-column (screen-corner-cell-id))) + (set-corner-column! col) + 'do-nothing) + (if (>= col (+ (id-column (screen-corner-cell-id)) 6)) + (set-corner-column! (- col 5)) + 'do-nothing))) + +(define (set-corner-row! new-row) + (set-screen-corner-cell-id! + (make-id (id-column (screen-corner-cell-id)) new-row))) + +(define (set-corner-column! new-column) + (set-screen-corner-cell-id! + (make-id new-column (id-row (screen-corner-cell-id))))) + + +;; LOAD + +(define (spreadsheet-load filename) + (let ((port (open-input-file filename))) + (sl-helper port) + (close-input-port port))) + +(define (sl-helper port) + (let ((command (read port))) + (if (eof-object? command) + 'done + (begin (show command) + (process-command command) + (sl-helper port))))) + + +;; PUT + +(define (put formula . where) + (cond ((null? where) + (put-formula-in-cell formula (selection-cell-id))) + ((cell-name? (car where)) + (put-formula-in-cell formula (cell-name->id (car where)))) + ((number? (car where)) + (put-all-cells-in-row formula (car where))) + ((letter? (car where)) + (put-all-cells-in-col formula (letter->number (car where)))) + (else (error "Put it where?")))) + +(define (put-all-cells-in-row formula row) + (put-all-helper formula (lambda (col) (make-id col row)) 1 26)) + +(define (put-all-cells-in-col formula col) + (put-all-helper formula (lambda (row) (make-id col row)) 1 30)) + +(define (put-all-helper formula id-maker this max) + (if (> this max) + 'done + (begin (try-putting formula (id-maker this)) + (put-all-helper formula id-maker (+ 1 this) max)))) + +(define (try-putting formula id) + (if (or (null? (cell-value id)) (null? formula)) + (put-formula-in-cell formula id) + 'do-nothing)) + +(define (put-formula-in-cell formula id) + (put-expr (pin-down formula id) id)) + + +;;; The Association List of Commands + +(define (command? name) + (assoc name *the-commands*)) + +(define (get-command name) + (let ((result (assoc name *the-commands*))) + (if (not result) + #f + (cadr result)))) + +(define *the-commands* + (list (list 'p prev-row) + (list 'n next-row) + (list 'b prev-col) + (list 'f next-col) + (list 'select select) + (list 'put put) + (list 'load spreadsheet-load))) + + +;;; Pinning Down Formulas Into Expressions + +(define (pin-down formula id) + (cond ((cell-name? formula) (cell-name->id formula)) + ((word? formula) formula) + ((null? formula) '()) + ((equal? (car formula) 'cell) + (pin-down-cell (cdr formula) id)) + (else (bound-check + (map (lambda (subformula) (pin-down subformula id)) + formula))))) + +(define (bound-check form) + (if (member 'out-of-bounds form) + 'out-of-bounds + form)) + +(define (pin-down-cell args reference-id) + (cond ((null? args) + (error "Bad cell specification: (cell)")) + ((null? (cdr args)) + (cond ((number? (car args)) ; they chose a row + (make-id (id-column reference-id) (car args))) + ((letter? (car args)) ; they chose a column + (make-id (letter->number (car args)) + (id-row reference-id))) + (else (error "Bad cell specification:" + (cons 'cell args))))) + (else + (let ((col (pin-down-col (car args) (id-column reference-id))) + (row (pin-down-row (cadr args) (id-row reference-id)))) + (if (and (>= col 1) (<= col 26) (>= row 1) (<= row 30)) + (make-id col row) + 'out-of-bounds))))) + +(define (pin-down-col new old) + (cond ((equal? new '*) old) + ((equal? (first new) '>) (+ old (bf new))) + ((equal? (first new) '<) (- old (bf new))) + ((letter? new) (letter->number new)) + (else (error "What column?")))) + +(define (pin-down-row new old) + (cond ((number? new) new) + ((equal? new '*) old) + ((equal? (first new) '>) (+ old (bf new))) + ((equal? (first new) '<) (- old (bf new))) + (else (error "What row?")))) + + +;;; Dependency Management + +(define (put-expr expr-or-out-of-bounds id) + (let ((expr (if (equal? expr-or-out-of-bounds 'out-of-bounds) + '() + expr-or-out-of-bounds))) + (for-each (lambda (old-parent) + (set-cell-children! + old-parent + (remove id (cell-children old-parent)))) + (cell-parents id)) + (set-cell-expr! id expr) + (set-cell-parents! id (remdup (extract-ids expr))) + (for-each (lambda (new-parent) + (set-cell-children! + new-parent + (cons id (cell-children new-parent)))) + (cell-parents id)) + (figure id))) + +(define (extract-ids expr) + (cond ((id? expr) (list expr)) + ((word? expr) '()) + ((null? expr) '()) + (else (append (extract-ids (car expr)) + (extract-ids (cdr expr)))))) + +(define (figure id) + (cond ((null? (cell-expr id)) (setvalue id '())) + ((all-evaluated? (cell-parents id)) + (setvalue id (ss-eval (cell-expr id)))) + (else (setvalue id '())))) + +(define (all-evaluated? ids) + (cond ((null? ids) #t) + ((not (number? (cell-value (car ids)))) #f) + (else (all-evaluated? (cdr ids))))) + +(define (setvalue id value) + (let ((old (cell-value id))) + (set-cell-value! id value) + (if (not (equal? old value)) + (for-each figure (cell-children id)) + 'do-nothing))) + + +;;; Evaluating Expressions + +(define (ss-eval expr) + (cond ((number? expr) expr) + ((quoted? expr) (quoted-value expr)) + ((id? expr) (cell-value expr)) + ((invocation? expr) + (apply (get-function (car expr)) + (map ss-eval (cdr expr)))) + (else (error "Invalid expression:" expr)))) + +(define (quoted? expr) + (or (string? expr) + (and (list? expr) (equal? (car expr) 'quote)))) + +(define (quoted-value expr) + (if (string? expr) + expr + (cadr expr))) + +(define (invocation? expr) + (list? expr)) + +(define (get-function name) + (let ((result (assoc name *the-functions*))) + (if (not result) + (error "No such function: " name) + (cadr result)))) + +(define *the-functions* + (list (list '* *) + (list '+ +) + (list '- -) + (list '/ /) + (list 'abs abs) + (list 'acos acos) + (list 'asin asin) + (list 'atan atan) + (list 'ceiling ceiling) + (list 'cos cos) + (list 'count count) + (list 'exp exp) + (list 'expt expt) + (list 'floor floor) + (list 'gcd gcd) + (list 'lcm lcm) + (list 'log log) + (list 'max max) + (list 'min min) + (list 'modulo modulo) + (list 'quotient quotient) + (list 'remainder remainder) + (list 'round round) + (list 'sin sin) + (list 'sqrt sqrt) + (list 'tan tan) + (list 'truncate truncate))) + +;;; Printing the Screen + +(define (print-screen) + (newline) + (newline) + (newline) + (show-column-labels (id-column (screen-corner-cell-id))) + (show-rows 20 + (id-column (screen-corner-cell-id)) + (id-row (screen-corner-cell-id))) + (display-cell-name (selection-cell-id)) + (display ": ") + (show (cell-value (selection-cell-id))) + (display-expression (cell-expr (selection-cell-id))) + (newline) + (display "?? ")) + +(define (display-cell-name id) + (display (number->letter (id-column id))) + (display (id-row id))) + +(define (show-column-labels col-number) + (display " ") + (show-label 6 col-number) + (newline)) + +(define (show-label to-go this-col-number) + (cond ((= to-go 0) '()) + (else + (display " -----") + (display (number->letter this-col-number)) + (display "----") + (show-label (- to-go 1) (+ 1 this-col-number))))) + +(define (show-rows to-go col row) + (cond ((= to-go 0) 'done) + (else + (display (align row 2 0)) + (display " ") + (show-row 6 col row) + (newline) + (show-rows (- to-go 1) col (+ row 1))))) + +(define (show-row to-go col row) + (cond ((= to-go 0) 'done) + (else + (display (if (selected-indices? col row) ">" " ")) + (display-value (cell-value-from-indices col row)) + (display (if (selected-indices? col row) "<" " ")) + (show-row (- to-go 1) (+ 1 col) row)))) + +(define (selected-indices? col row) + (and (= col (id-column (selection-cell-id))) + (= row (id-row (selection-cell-id))))) + +(define (display-value val) + (display (align (if (null? val) "" val) 10 2))) + +(define (display-expression expr) + (cond ((null? expr) (display '())) + ((quoted? expr) (display (quoted-value expr))) + ((word? expr) (display expr)) + ((id? expr) + (display-cell-name expr)) + (else (display-invocation expr)))) + +(define (display-invocation expr) + (display "(") + (display-expression (car expr)) + (for-each (lambda (subexpr) + (display " ") + (display-expression subexpr)) + (cdr expr)) + (display ")")) + + +;;; Abstract Data Types + +;; Special cells: the selected cell and the screen corner + +(define *special-cells* (make-vector 2)) + +(define (selection-cell-id) + (vector-ref *special-cells* 0)) + +(define (set-selection-cell-id! new-id) + (vector-set! *special-cells* 0 new-id)) + +(define (screen-corner-cell-id) + (vector-ref *special-cells* 1)) + +(define (set-screen-corner-cell-id! new-id) + (vector-set! *special-cells* 1 new-id)) + + +;; Cell names + +(define (cell-name? expr) + (and (word? expr) + (letter? (first expr)) + (number? (bf expr)))) + +(define (cell-name-column cell-name) + (letter->number (first cell-name))) + +(define (cell-name-row cell-name) + (bf cell-name)) + +(define (cell-name->id cell-name) + (make-id (cell-name-column cell-name) + (cell-name-row cell-name))) + +;; Cell IDs + +(define (make-id col row) + (list 'id col row)) + +(define (id-column id) + (cadr id)) + +(define (id-row id) + (caddr id)) + +(define (id? x) + (and (list? x) + (not (null? x)) + (equal? 'id (car x)))) + +;; Cells + +(define (make-cell) + (vector '() '() '() '())) + +(define (cell-value id) + (vector-ref (cell-structure id) 0)) + +(define (cell-value-from-indices col row) + (vector-ref (cell-structure-from-indices col row) 0)) + +(define (cell-expr id) + (vector-ref (cell-structure id) 1)) + +(define (cell-parents id) + (vector-ref (cell-structure id) 2)) + +(define (cell-children id) + (vector-ref (cell-structure id) 3)) + +(define (set-cell-value! id val) + (vector-set! (cell-structure id) 0 val)) + +(define (set-cell-expr! id val) + (vector-set! (cell-structure id) 1 val)) + +(define (set-cell-parents! id val) + (vector-set! (cell-structure id) 2 val)) + +(define (set-cell-children! id val) + (vector-set! (cell-structure id) 3 val)) + +(define (cell-structure id) + (global-array-lookup (id-column id) + (id-row id))) + +(define (cell-structure-from-indices col row) + (global-array-lookup col row)) + +(define *the-spreadsheet-array* (make-vector 30)) + +(define (global-array-lookup col row) + (if (and (<= row 30) (<= col 26)) + (vector-ref (vector-ref *the-spreadsheet-array* (- row 1)) + (- col 1)) + (error "Out of bounds"))) + +(define (init-array) + (fill-array-with-rows 29)) + +(define (fill-array-with-rows n) + (if (< n 0) + 'done + (begin (vector-set! *the-spreadsheet-array* n (make-vector 26)) + (fill-row-with-cells + (vector-ref *the-spreadsheet-array* n) 25) + (fill-array-with-rows (- n 1))))) + +(define (fill-row-with-cells vec n) + (if (< n 0) + 'done + (begin (vector-set! vec n (make-cell)) + (fill-row-with-cells vec (- n 1))))) + +;;; Utility Functions + +(define alphabet + '#(a b c d e f g h i j k l m n o p q r s t u v w x y z)) + +(define (letter? something) + (and (word? something) + (= 1 (count something)) + (vector-member something alphabet))) + +(define (number->letter num) + (vector-ref alphabet (- num 1))) + +(define (letter->number letter) + (+ (vector-member letter alphabet) 1)) + +(define (vector-member thing vector) + (vector-member-helper thing vector 0)) + +(define (vector-member-helper thing vector index) + (cond ((= index (vector-length vector)) #f) + ((equal? thing (vector-ref vector index)) index) + (else (vector-member-helper thing vector (+ 1 index))))) + +(define (remdup lst) + (cond ((null? lst) '()) + ((member (car lst) (cdr lst)) + (remdup (cdr lst))) + (else (cons (car lst) (remdup (cdr lst)))))) + +(define (remove bad-item lst) + (filter (lambda (item) (not (equal? item bad-item))) + lst)) +</PRE><P> + + + +<P><H2>Exercises</H2> + +<P><B>25.1</B> The "magic numbers" 26 and 30 (and some numbers derived from +them) appear many times in the text of this program. It's easy to imagine +wanting more rows or columns. + +<P>Create global variables <CODE>total-cols</CODE> and <CODE>total-rows</CODE> with values 26 +and 30 respectively. Then modify the spreadsheet program to refer to these +variables rather than to the numbers 26 and 30 directly. When you're done, +redefine <CODE>total-rows</CODE> to be 40 and see if it works. + + +<P> +<B>25.2</B> Suggest a way to notate columns beyond <CODE>z</CODE>. What procedures would have +to change to accommodate this? + + +<P> +<B>25.3</B> Modify the program so that the spreadsheet array is kept as a single vector +of 780 elements, instead of a vector of 30 vectors of 26 vectors. What +procedures do you have to change to make this work? (It shouldn't be very +many.) + + +<P> +<B>25.4</B> The procedures <CODE>get-function</CODE> and <CODE>get-command</CODE> are almost identical +in structure; both look for an argument in an association list. They +differ, however, in their handling of the situation in which the argument is +not present in the list. Why? + + +<P> +<B>25.5</B> The reason we had to include the word <CODE>id</CODE> in each cell ID was so we +would be able to distinguish a list representing a cell ID from a list of +some other kind in an expression. Another way to distinguish cell IDs would +be to represent them as vectors, since vectors do not otherwise appear +within expressions. Change the implementation of cell IDs from +three-element lists to two-element vectors: + +<P><PRE>> (make-id 4 2) +#(4 2) +</PRE> + +<P>Make sure the rest of the program still works. + + +<P> +<B>25.6</B> The <CODE>put</CODE> command can be used to label a cell by using a quoted word +as the "formula." How does that work? For example, how is such a formula +translated into an expression? How is that expression evaluated? What if +the labeled cell has children? + + +<P> +<B>25.7</B> Add commands to move the "window" of cells displayed on the screen +without changing the selected cell. (There are a lot of possible user +interfaces for this feature; pick anything reasonable.) + + +<P> +<B>25.8</B> Modify the <CODE>put</CODE> command so that after doing its work it prints + +<P><PRE>14 cells modified +</PRE> + +<P>(but, of course, using the actual number of cells modified +instead of 14). This number may not be the entire length of a row or column +because <CODE>put</CODE> doesn't change an existing formula in a cell when you ask +it to set an entire row or column. + + +<P> +<B>25.9</B> Modify the program so that each column remembers the number of digits that +should be displayed after the decimal point (currently always 2). Add a +command to set this value for a specified column. And, of course, modify +<CODE>print-screen</CODE> to use this information. + + +<P> +<B>25.10</B> Add an <CODE>undo</CODE> command, which causes the effect of the previous command +to be nullified. That is, if the previous command was a cell selection +command, <CODE>undo</CODE> will return to the previously selected cell. If the +previous command was a <CODE>put</CODE>, <CODE>undo</CODE> will re-<CODE>put</CODE> the previous +expressions in every affected cell. You don't need to undo <CODE>load</CODE> or +<CODE>exit</CODE> commands. To do this, you'll need to modify the way the other +commands work. + + +<P> +<B>25.11</B> Add an <CODE>accumulate</CODE> procedure that can be used as a function in +formulas. Instead of specifying a sequence of cells explicitly, in a +formula like + +<P><PRE>(put (+ c2 c3 c4 c5 c6 c7) c10) +</PRE> + +<P>we want to be able to say + +<P><PRE>(put (accumulate + c2 c7) c10) +</PRE> + +<P>In general, the two cell names should be taken as corners of a +rectangle, all of whose cells should be included, so these two commands +are equivalent: + +<P><PRE>(put (accumulate * a3 c5) d7) +(put (* a3 b3 c3 a4 b4 c4 a5 b5 c5) d7) +</PRE> + +<P>Modify <CODE>pin-down</CODE> to convert the <CODE>accumulate</CODE> form into +the corresponding spelled-out form. + + +<P> +<B>25.12</B> Add variable-width columns to the spreadsheet. There should be a command to +set the print width of a column. This may mean that the spreadsheet can +display more or fewer than six columns. + + +<P> + +<HR> +<A NAME="ft1" HREF="spread-implement#text1">[1]</A> The vector elements are numbered from zero, but we number rows and +columns from one, subtracting one in the selector that actually extracts +information from the array of cells.<P> +<A NAME="ft2" HREF="spread-implement#text2">[2]</A> Not every version of Scheme has +this behavior. If you find that you have to hit <CODE>return</CODE> twice after exhibiting +the value of a formula, take out one of the <CODE>read-line</CODE> invocations.<P> +<A NAME="ft3" HREF="spread-implement#text3">[3]</A> We originally wrote two separate helper procedures for the two +cases, like this: + +<P><PRE>(define (put-all-cells-in-row formula row) + (row-helper formula 1 26 row)) + +(define (row-helper formula this-col max-col row) + (if (> this-col max-col) + 'done + (begin (try-putting formula <B>(make-id this-col row)</B>) + (row-helper formula (+ this-col 1) max-col row)))) + +(define (put-all-cells-in-col formula col) + (column-helper formula 1 30 col)) + +(define (column-helper formula this-row max-row col) + (if (> this-row max-row) + 'done + (begin (try-putting formula <B>(make-id col this-row)</B>) + (column-helper formula (+ this-row 1) max-row col)))) +</PRE> + +<P>but the procedures were so similar that we decided to generalize the +pattern.<P> +<A NAME="ft4" HREF="spread-implement#text4">[4]</A> In fact, <CODE>process-command</CODE> +also invokes <CODE>pin-down</CODE> when the user types a formula in place of a +command. In that situation, the result doesn't go into a cell but is +immediately evaluated and printed.<P> +<A NAME="ft5" HREF="spread-implement#text5">[5]</A> You can +think of the <CODE>cell</CODE> notation in generalized formulas as a kind of +special form, but <CODE>pin-down</CODE> has turned those into specific cell IDs +before the formula is eligible for evaluation as an expression.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch24/spread.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="database.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |