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/ss/instructor.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ss/instructor.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ss/instructor.html | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ss/instructor.html b/js/games/nluqo.github.io/~bh/ss/instructor.html new file mode 100644 index 0000000..6bb2a0f --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ss/instructor.html @@ -0,0 +1,202 @@ +<HTML> +<HEAD> +<TITLE>Simply Scheme: To the Instructor</TITLE> +</HEAD> +<BODY> +<CITE>Simply Scheme</CITE> 2/e Copyright (C) 1999 MIT +<H1>To the Instructor</H1> + +<TABLE><TR><TD> +<P><IMG SRC="../simply.jpg" ALT="cover photo"> +<TD valign="center"> +<CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR><A HREF="http://www.cnmat.berkeley.edu/~matt">Matthew +Wright</A><BR>University of California, Berkeley</CITE> +<BR><BR><A HREF="http://www-mitpress.mit.edu/book-home.tcl?isbn=0262082810">MIT +Press web page for Simply Scheme</A> +</TABLE> + +<P><A HREF="../simply-toc.html">(back to Table of Contents)</A> + +<HR> + +<P>The language that we use in this book isn't exactly standard Scheme. We've +provided several extensions that may seem unusual to an experienced Scheme +programmer. This may make the book feel weird at first, but there's a +pedagogic reason for each extension. + +<P>Along with our slightly strange version of Scheme, our book has a slightly +unusual order of topics. Several ideas that are introduced very early in +the typical Scheme-based text are delayed in ours, most notably recursion. +Quite a few people have looked at our table of contents, noted some +particular big idea of computer science, and remarked, "I can't believe +you wait so long before getting to <EM>such and such</EM>!" + +<P>In this preface for instructors, we describe and explain the unusual +elements of our approach. Other teaching issues, including the timing and +ordering of topics, are discussed in the Instructor's Manual. + +<P><H2>Lists and Sentences</H2> + +<P>The chapter named "Lists" in this book is Chapter 17, about halfway +through the book. But really we use lists much earlier than that, almost +from the beginning. + +<P>Teachers of Lisp have always had trouble deciding when and how to introduce +lists. The advantage of an early introduction is that students can then +write interesting symbolic programs instead of boring numeric ones. The +disadvantage is that students must struggle with the complexity of the +implementation, such as the asymmetry between the two ends of a list, while +still also struggling with the idea of composition of functions and Lisp's +prefix notation. + +<P>We prefer to have it both ways. We want to spare beginning students the +risk of accidentally constructing ill-formed lists such as + +<P><PRE>((((() . D) . C) . B) . A) +</PRE> + +<P>but we also want to write natural-language programs from the +beginning of the book. Our solution is to borrow from Logo the idea of a +<EM>sentence</EM> abstract data type.<SUP>*</SUP> Sentences are +guaranteed to be flat, proper lists, and they appear to be symmetrical to +the user of the abstraction. (That is, it's as easy to ask for the last +word of a sentence as to ask for the first word.) The <CODE>sentence</CODE> +constructor accepts either a word or a sentence in any argument position. + +<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Speaking of abstraction, even +though that's the name of Part V, we do make an occasion in each of the +earlier parts to talk about abstraction as examples come up.</SMALL></BLOCKQUOTE></SMALL><P>We defer <EM>structured</EM> lists until we have higher-order functions and +recursion, the tools we need to be able to use the structure +effectively.<SUP>*</SUP> A +structured list can be understood as a tree, and Lisp programmers generally +use that understanding implicitly. We create an explicit abstract data type +for trees and use it for a thorough exploration of tree structure, without +reference to the implementation of trees. We then explicitly connect the +usual informal tree recursion on structured lists to our more formal version. + +<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Even then, we take lists as a primitive data type. We +don't teach about pairs or improper lists, except as a potential pitfall.</SMALL></BLOCKQUOTE></SMALL><P><H2>Sentences and Words</H2> + +<P>We haven't said what a <EM>word</EM> is. Scheme includes separate data types +for characters, symbols, strings, and numbers. We want to be able to +dissect words into letters, just as we can dissect sentences into words, so +that we can write programs like <CODE>plural</CODE> and <CODE>pig-latin</CODE>. Orthodox +Scheme style would use strings for such purposes, but we want a sentence to +look <CODE>(like this)</CODE> and not <CODE>("like" "this")</CODE>. We've arranged that +in most contexts symbols, strings, and numbers can be used interchangeably; +our readers never see Scheme characters at all.<SUP>*</SUP> +Although a word made of letters is represented internally as a symbol, while +a word made of digits is represented as a number, above the abstraction line +they're both words. (A word that standard Scheme won't accept as a symbol +nor as a number is represented as a string.) + +<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Scheme's primitive +I/O facility gives you the choice of expressions or characters. Instead of +using <CODE>read-char</CODE>, we invent <CODE>read-line</CODE>, which reads a line as a +sentence, and <CODE>read-string</CODE>, which returns the line as one long word.</SMALL></BLOCKQUOTE></SMALL><P>There is an efficiency cost to treating both words and sentences as abstract +aggregates, since it's slow to disassemble a sentence from right to left and +slow to disassemble a word in either direction. Many simple procedures that +seem linear actually behave quadratically. Luckily, words aren't usually +very long, and the applications we undertake in the early chapters don't use +large amounts of data in any form. We write our large projects as +efficiently as we can without making the programs unreadable, but we +generally don't make a fuss about it. Near the end of the book we discuss +explicitly the efficient use of data structures. + +<P><H2>Overloading in the Text Abstraction</H2> + +<P>Even though computers represent numbers internally in many different ways +(fixed point, bignum, floating point, exact rational, complex), when people +visit mathland, they expect to meet numbers there, and they expect that all +the numbers will understand how to add, subtract, multiply, and divide with +each other. (The exception is dividing by zero, but that's because of the +inherent rules of mathematics, not because of the separation of numbers into +categories by representation format.) + +<P>We feel the same way about visiting textland. We expect to meet English +text there. It takes the form of words and sentences. The operations that +text understands include <CODE>first</CODE>, <CODE>last</CODE>, <CODE>butfirst</CODE>, and <CODE> +butlast</CODE> to divide the text into its component parts. You can't divide an +empty word or sentence into parts, but it's just as natural to divide a word +into letters as to divide a sentence into words. (The ideas of mathland and +textland, as well as the details of the word and sentence procedures, come +from Logo.) + +<P>Some people who are accustomed to Scheme's view of data types consider <CODE> +first</CODE> to be badly "overloaded"; they feel that a procedure that selects an +element from a list shouldn't also extract a letter from a symbol. Some of +them would prefer that we use <CODE>car</CODE> for lists, use <CODE>substring</CODE> for +strings, and not disassemble symbols at all. Others want us to define <CODE> +word-first</CODE> and <CODE>sentence-first</CODE>. + +<P>To us, <CODE>word-first</CODE> and <CODE>sentence-first</CODE> sound no less awkward than +<CODE>fixnum-+</CODE> and <CODE>bignum-+</CODE>. Everyone agrees that it's reasonable to +overload the name <CODE>+</CODE> because the purposes are so similar. Our students +find it just as reasonable that <CODE>first</CODE> works for words as well as for +sentences; they don't get confused by this. + +<P>As for the inviolability of symbols--the wall between names and data--we +are following an older Lisp tradition, in which it was commonplace to <CODE> +explode</CODE> symbols and to construct new names within a program. Practically +speaking, all that prevents us from representing words as strings is that +Scheme requires quotation marks around them. But in any case, the +abstraction we're presenting is that the data we're dissecting are neither +strings nor symbols, but words. + +<P><H2>Higher-Order Procedures, Lambda, and Recursion</H2> + +<P>Scheme relies on procedure invocation as virtually its only control +mechanism. In order to write interesting programs, a Scheme user must +understand at least one of two hard ideas: recursion or procedure as object +(in order to use higher-order procedures). We believe that higher-order +procedures are easier to learn, especially because we begin in Chapter +8 by applying them only to named procedures. Using a named procedure +as an argument to another procedure is the way to use procedures as objects +that's least upsetting to a beginner. After the reader is comfortable with +higher-order procedures, we introduce <CODE>lambda</CODE>; after that we introduce +recursion. We do the tic-tac-toe example with higher-order procedures and +<CODE>lambda</CODE>, but not recursion. + +<P>When we get to recursion, we begin with an example of embedded recursion. +Many books begin with the simplest possible recursive procedure, which turns +out to be a simple sequential recursion, or even a tail recursion. We feel +that starting with such examples allows students to invent the "go back" +model of recursion as looping. + +<P><H2>Mutators and Environments</H2> + +<P>One of the most unusual characteristics of this book is that there is no +assignment to variables in it. The reason we avoid <CODE>set!</CODE> is that the +environment model of evaluation is very hard for most students. We use a +pure substitution model throughout most of the book. (With the background +they get from this book, students should be ready for the environment model +when they see a rigorous presentation, as they will, for example, in Chapter +3 of <EM>SICP.</EM>) + +<P>As the last topic in the book, we do introduce a form of mutation, namely +<CODE>vector-set!</CODE>. Mutation of vectors is less problematic than mutation of +lists, because lists naturally share storage. You really have to go out of +your way to get two pointers to the same vector.<SUP>*</SUP> Mutation of data +structures is less problematic than assignment to variables because it +separates the issue of mutation from the issues of binding and scope. Using +vectors raises no new questions about the evaluation process, so we present +mutation without reference to any formal model of evaluation. We +acknowledge that we're on thin ice here, but it seems to work for our +students. + +<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>We don't talk about +<CODE>eq?</CODE> at all. We're careful to write our programs in such a way that +the issue of identity doesn't arise for the reader.</SMALL></BLOCKQUOTE></SMALL><P>In effect, our model of mutation is the "shoebox" model that you'd find in +a mainstream programming language text. Before we get to mutation, we use +input/output programming to introduce the ideas of effect and sequence; +assigning a value to a vector element introduces the important idea of +state. We use the sequential model to write two more or less practical +programs, a spreadsheet and a database system. A more traditional approach +to assignment in Scheme would be to build an object-oriented language +extension, but the use of local state variables would definitely force us to +pay attention to environments. + +<P><A HREF="../simply-toc.html">(back to Table of Contents)</A> + +</HTML> |