Foundations of Computing -- Fall 2000

Jon Jacky

In this program we will examine problem-solving in three contrasting programming languages.

Languages
Textbooks
Software
Laboratories
Seminars

Quizzes
Exercises

Recursion examples
Sorting examples

The Truth about Lists
    How computers work
    Scheme in Scheme

Scheme Retrospective
    What have we learned?
    Scheme and functional programming
    Finding the shortest path by breadth-first search

We never got to this, interesting anyway:

Graphics and Graphical User Interfaces

Last revised December 21, 2000. Use your browser's Reload or Refresh button to get the latest version.

Back to course page.

Languages

Programmers and other computer specialists typically work in several languages, not just one. The differences are not merely superficial. The languages have different purposes, and each expresses a different notion of computation.

Fall quarter we will study Scheme. Winter quarter we will add Awk and Java.

Scheme is a dialect of Lisp, one of the oldest and most influential programming languages. It was invented to support research in artificial intelligence and programming language design, but is also useful for general purpose programming (for example see this cool stuff and this esoteric stuff). Its simplicity and power make it an excellent vehicle for learning programming.

Here is a quick "Nutshell"-style tutorial that contrasts Scheme with other programming languages:

Here is another course page with a brief Scheme tutorial and other links. The sections on basics and recursion provide another view of material we covered. The section on eval and apply provides additional explanation on material from our last lecture.

Here is the complete text of a classic Scheme textbook for advanced students:

There is much more about Scheme here.

The other important Lisp dialect is Common Lisp, which is more complex than Scheme but is probably used more in industry. Here is information about an excellent Common Lisp textbook.

Awk is a scripting language, intended to help programmers write small but effective programs quickly. It is particularly well-suited for processing text patterns (in email messages, web pages, and other network traffic) and tabular data (from spreadsheets, databases, and other computer output). Other popular scripting languages are Perl, Python and Tcl, but Awk has a cleaner design and is easier to learn. It is excellent preparation for learning Perl which is similar but much hairier. Awk also has the same expression syntax (appearance and grammar rules) as C, C++, Java, and Javascript and is good preparation for learning any of these.

Java is ... oh, you've heard of it? What matters for our purposes is that it is representative of the most popular general-purpose languages. It has much in common with the older workhorses C and C++ but is simpler and more reliable.

Textbooks

One of the goals of this course is to teach you to select and use computer books effectively.

The Scheme book provides detailed explanations for beginners. The Awk book moves more quickly. The Java book is terse, almost telegraphic. After you have learned these, you will be prepared to use reference manuals and "Nutshell"-style books.

Required:

Simply Scheme: Introducing Computer Science, 2nd edition, Brian Harvey and Matthew Wright, ISBN 0262082810, MIT Press, 1999, 612 pages. About $60.

The Awk Programming Language, 1st edition, Alfred V. Aho, Brian W. Kernighan, Peter J. Weinberger, ISBN 020107981X, Addison-Wesley, 1988, 210 pages. About $41.

On to Java, 2nd edition, Patrick Henry Winston and Sundar Narasimhan, ISBN 0201385988, Addison-Wesley, 1998, 379 pages. About $25.

Also recommended:

The Little Schemer (earlier editions were called The Little LISPer), Daniel P. Friedman and Matthias Felleisen, MIT Press (very early editions were from Science Research Associates), in print since 1974. About 180 pages (but mostly whitespace). An introduction to Lisp/Scheme presented in an unusual question/answer format.

Software

The programming languages and tools for this course are installed on the computers at the ACC lab. During Fall term, we will be using Windows. During the rest of the year, we will also use Linux.

All of the programming languages and tools for this course are available for free, and most run on several kinds of computers. This makes it reasonable for students to install and use the software at home if they wish.

We will use the DrScheme environment for programming in Scheme. You can download DrScheme software and manuals for Windows, Linux, Macintosh and several other platforms here. You can download the example programs from Simply Scheme here. Here you can download the DrScheme teachpack for Simply Scheme, named simply-teachpack.scm. To do the examples in Simply Scheme, you must load this teachpack into DrScheme by selecting the Language menu, then selecting Add Teachpack and navigating to simply-teachpack.scm (in whatever folder you saved it).

Here is on online manual for using DrScheme that summarizes some of the material in the official manual:

Here are some online Scheme tutorials that take a different approach than our textbook:

You can download Awk for Windows here. Awk comes included with Linux (where it is called gawk). There is information about Awk for Macintosh here. You can download the example programs from The Awk Programming Language here.

Sun's Java site is here. The software we need must be in there somewhere. Watch this space for advice on what to download.

Laboratories

Laboratory work will develop technical skills.

Here are some notes on using the lab software.

Seminars

Readings and seminars will develop presentation skills, design sense, and critical judgment.

Here are the full references for the seminar readings, with URL's if availble.

Quizzes

Here are the weekly quizzes and solutions.

Exercises

Here are some exercise solutions we discussed in class.

Recursion Examples

Here are some recursion examples we discussed in class.

Sorting Examples

Here are some sorting examples from Brian Harvey, co-author of our textook Simply Scheme. Shows four surprising and beautiful applications of recursion.

The Truth About Lists

Handouts for the November 30 lecture.

I also handed out some diagrams showing how lists are implemented by conscells and pointers: Figs. 3.1, 3.2, 3.3, and 3.8 from pages 32, 33 and 38 of Paul Graham, ANSI COMMON LISP, Prentice Hall 1996.

Scheme Retrospective

Handouts from the December 5 lecture.

Here is the code for the example we discussed in class. This little example illustrates the power of functional programming and demonstrates almost every Scheme programming technique we discussed all quarter.

Graphics and Graphical User Interfaces

Here are some links on doing graphics and graphical user interfaces in DrScheme.

Graphics

To find the Help Desk entries, in DrScheme select Help > Help Desk, then in Find docs for: type the topic, such as make-posn, then select the entry, such as Position Operations.

To use draw.ss, you must set the language level to Advanced Student and load the draw.ss teachpack. See DrScheme notes.

Fractals

Graphical User Interface

Jon Jacky, jackyj@evergreen.edu