Code Examples

This page (which you can read on the web at http://www.cs.iastate.edu/~leavens/ComS342-EOPL2e/docs/code-examples.html) gives access to code examples in the course library and in the lecture notes directory.

You can use the table of contents (on the web) to jump directly to the kind of example you are looking for.

If you click on a Scheme file name and your browser tries to download a plugin (e.g., for a Lotus Screen Cam Movie), then you need to change your browser's rules for associating file suffixes with viewers. One way to do this on Windows (95/98) is to go into the Windows Explorer, and click on "View" then "Folder Options", then click on the "File Types" tab, and then enter a new file type for .scm files.

Contents

1. Scheme Background
• Data Types
• Expressions
• Procedures
• Syntactic Abstraction
2. EOPL 2e Chapter 1
• Inductive Specifications and Grammars (1.1)
• Deriving Recursive Programs from Grammars (1.2)
• Tail Recursion (1.2.3)
• Static and Binding of Variables (1.3)
3. EOPL 2e Chapter 2
• Specifying Data via Interfaces (2.1)
• Abstractin for Inductive Datatypes (2.2)
• Data Abstraction (2.3)
• Transformation of Procedural to Abstract Syntax Tree Representations (2.3.2-2.3.3)
4. EOPL 2e Chapter 3
5. EOPL 2e Chapter 4
6. EOPL 2e Chapter 5
7. EOPL 2e Chapter 6

Scheme Background

Data Types

•   Construct and lists and improper lists
•   Use of quote, cons, and list primitives (and when to use each)
•   Extract parts of lists and improper lists

$PUB/lib/whos-on-first.scm
$PUB/lib/lambda*.scm, for example $PUB/lib/lambda-1-exp.scm

• Dot notation

$PUB/lib/dot-notation.scm

•  How to read and write our type notation ($PUB/docs/type-notation.html)

Expressions

• Make decisions using if expressions
• Make declarations using define

• Differences between expressions, statements, and declarations.

Procedures

•  Use of map

$PUB/lib/matrix-ops.scm
$PUB/lib/sym-exp.scm (parse-s-list)
$PUB/lib/remove-sym-exp-with-map.scm (remove-s-list)
 
• Uses of curried procedures

$PUB/lib/grav-force.scm
$PUB/lib/test-homework.scm (cs342:test-maker, cs324:eval-print-maker, cs342:regression-test-maker-maker, ...)
$PUB/lib/type-check-unify.scm (tc:list-unify-maker)
$PUB/lib/type-check-infer.scm (tc:check-application-maker, tc:infer-elements-type-lub-maker, ...)
$PUB/lib/vector-generator.scm (see $PUB/lib/vector-generator.tst and vector-map.scm for how it's used)

•  Write variable arity procedures

  $PUB/lib/sum.scm
  $PUB/lib/product.scm
  $PUB/lib/atomic-tree.scm (tree)
  $PUB/lib/set-ops.scm (set-of, set-union*)

Syntactic Abstraction

•  How to desugar expressions in Scheme (let, and, or, cond, case)

 $PUB/lib/lambda-if-let-exp-examples.scm (sugar, which does the opposite of the "let" desugaring)
 
• Be able to use let, letrec, and, or, cond, case in Scheme programs.  There are lots of examples of this.  You can grep for the appropriate keyword to find examples in the library files.  The following are some simple examples.

•  examples of "and" and "or"
       $PUB/homework/set-ops.scm (set-member?, set-subset?, set-equal?)
       $PUB/lib/all.scm
       $PUB/lib/some.scm
       $PUB/lib/type-check-unify.scm (tc:occurs-check?, ...)

• examples of "let", "let*", "letrec", and "cond", e.g.,
      $PUB/lib/whos-on-first.scm
      $PUB/lib/type-check-infer.scm

EOPL Chapter 1

Inductive Specifications and Grammars (1.1)

•  BNF notation

  $PUB/lib/lambda*.scm, for example $PUB/lib/lambda-1-exp.scm
  The document defining our type notation
  $PUB/lib/type-check-output-type-expr.scm

Deriving Recursive Programs from Grammars (1.2)

•  How grammar relates to the outline of a recursive procedure (1.2.1)
•  Write recursive programs over flat lists (1.2.2)

  $PUB/lib/sum.scm (sum-of-list)
  $PUB/lib/product.scm (product-of-list)
  $PUB/lib/type-check-utils.scm (tc:last-item, tc:some, tc:member?, tc:filter, tc:find-duplicates, ...)
  $PUB/lib/set-ops.scm
  $PUB/lib/type-predicates.scm (list-of)
• Write recursive programs over symbol-expression and lists of symbol-expressions (s-lists, pp. 19-22)

  $PUB/lib/subst.scm
  $PUB/lib/num-of.scm
  $PUB/lib/remove-sym-exp.scm
  try these using $PUB/lib/sym-exp-cooked.scm also, instead of $PUB/lib/sym-exp.scm
• Write recursive programs over grammars

  $PUB/lib/lambda*-examples.scm, for example $PUB/lib/lambda-1+quote-examples.scm
  $PUB/lib/type-check-output-type-expr.scm
  $PUB/lib/type-check-type-expr.scm
  $PUB/lib/type-check-type-translate.scm (tc:type-vars, tc:output-type-vars, tc:nest-args, tc:type-unnest-args, tc:substq-all-output)

Tail Recursion (1.2.3)

Understand the difference between full recursion and tail recursion.

Examples of full recursion are found in the section above on deriving recursive programs from grammars.  Compare the code for the fully recursive $PUB/lib/product.scm with the tail recursive code in $PUB/lib/product-tail-recursive.scm.  Note the pending computations surrounding the recursive calls in the fully-recursive version.
 

Write tail-recursive procedures:

• Using letrec

Scope and Binding of Variables (1.3)

• free and bound names and variable references in an expression

 $PUB/lib/lambda-1-exp-examples.scm (free-vars, free?, bound-vars, bound?)
 $PUB/lib/combinator-tools.scm (occurs-free-in?)
• combinators

 $PUB/lib/combinators.scm
 $PUB/lib/y.scm
see also $PUB/lib/combinator-tools.scm

EOPL Chapter 2

Specifying Data via Interfaces (2.1)

Abstraction for Inductive Data Types (2.2)

• Use of define-datatype to declare variant record types
• Abstract syntax that corresponds to a concrete syntax.
• Use of cases in recursive programming, especially over some abstract syntax.

Data Abstraction (2.3)

•  Representation types and defrep

  $PUB/lib/stack.scm
  $PUB/lib/seq-as-proc.scm
  $PUB/lib/seq-as-ast.scm

Transformation of Procedural to Abstract Syntax Tree Representations (2.3.2-2.3.3)

  $PUB/lib/seq-as-proc.scm transformed to $PUB/lib/seq-as-ast.scm
  $PUB/lib/environment-as-proc.scm transformed to $PUB/lib/environment-as-ast.scm
  $PUB/lib/phone-book-as-proc.scm transformed to $PUB/lib/phone-book-as-ast.scm and optimized to a ribcage representation in $PUB/lib/phone-book-as-ribcage.scm
  $PUB/lib/road-map-as-proc.scm transformed to $PUB/lib/road-map-as-ast.scm