How to do your Racket

...

expository and programming problems

• this directive describes how to answer both expository problems and programming problems. For detailed instructions on how to format your homework as a single (.rkt) file and submit it, see the Racket HW Checklist.

...

• Some homework problems will be conventional expository questions that require a short written answer.
• All of the assigned expository problems should be answered in the same Racket Racket (.rkt rkt) file as your Racket programming Racket programming exercises. Of course   To do this, you must  "comment out" each expository answer either by:

1. 1. Beginning each line in the answer to an expository question with the comment escape character ; (semicolon) ; or
   2. Enclosing the entire expository answer in a Racket comment box created using Racket block comment brackets #| and |# (sometimes called bookends). 

• Note that you can You should create your entire homework file solution including solutions answers to expository problems withinn a single Racket file using the DrRacket editor.  Of course, you must "comment out" all of your expository answers so that they are ignored when your file is executed as Racket code.

Hand evaluation problems

• Most expository problems will be hand-evaluation problems where you are asked to manually evaluate a particular Racket program Racket program invocation. You must format your hand evaluation exactly like our examples (except you will need to insert a comment escape character if the evaluation is embedded in a Racket file with characters so you expository answers are ignored when the file is processed as executable Racket code.

  • Example 1: Hand evaluationHand evaluation

    Code Block
    Code Block
    Given (define poly (lambda (x y) (+ (expt 2 x) y))) (poly 3 5) =>Given (define ((lambdaf (x y) (+ (expt 2 x) y)) (f 3 5) => (+ (expt 2 3) 5)) => (+ 8 5) => 13

    
    

  • Example 2: Hand evaluation

    Code Block

    Given (define (fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) (fact 4) => (if (zero? 4) 1 (* 4 (fact (- 4 1)))) => (if false 1 (* 4 (fact (- 4 1)))) => (* 4 (fact (- 4 1))) => (* 4 (fact 3)) => (* 4 (if (zero? 3) 1 (* 3 (fact (- 3 1))))) => (* 4 (if false 1 (* 3 (fact (- 3 1))))) => (* 4 (* 3 (fact (- 3 1)))) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (if (zero? 2) 1 (* 2 (fact (- 2 1)))))) => (* 4 (* 3 (if false 1 (* 2 (fact (- 2 1)))))) => (* 4 (* 3 (* 2 (fact (- 2 1))))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (if (zero? 1) 1 (* 1 (fact (- 1 1))))))) => (* 4 (* 3 (* 2 (if false 1 (* 1 (fact (- 1 1))))))) => (* 4 (* 3 (* 2 (* 1 (fact (- 1 1)))))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 (if (zero? 0) 1 (* 0 (fact (- 0 1)))))))) => (* 4 (* 3 (* 2 (* 1 (if true 1 (* 0 (fact (- 0 1)))))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24 > 24

    
    

Warning: supporting functions as values introduces an extra wrinkle in the reduction process which we will discuss in Lecture 7 and beyond.   The wrinkle is conceptually simple but notationally tedious.

Programming problems

• Most of your homework problems will be programming problems.
• Half (50%) of your grade on programming problems depends on good style and following the recipe (program grading is described in detail on the homework grading page). In particular, these points will be based on
  • 30% for following the design recipe carefully and documenting your program as you are taught in this course (see below), and
  • 20% for good programming style as taught in the course.
• The other half of your grade will be based on demonstrated correctness:
  • 30% for passing all of our tests; and
  • 20% for constructing a comprehensive set of unit tests for each function in your program.

• All assigned programming problems should be done in the same .rkt rkt file.

• At the top of your programming solution file, please put a header with the assignment number, your name, and your e-mail address like this:

  Code Block
  ;; COMP 311 HW #01 ;; Christopher Warrington <chrisw@rice.edu>

  
  

• Strictly follow the formatting and documentation directives given below under the heading Requirements.  The easiest way to follow these requirements is to imitate the Sample Program solution below.

...

You must include a data definition and corresponding template for each form of data processed used in your homework submissions unless instructed otherwise. You only need to include a data definition and corresponding template once for an assignment, not once for every problem that uses that data defintiondefinition.

Data Definitions and Templates:

...

• Example 3. Data definition of shape:

  Code Block

  ;; A shape is either ;; * a triangle (make-triangle b h), ;; where b and h are positive-reals ;; * a square (make-square s), ;; where s is a positive-real. (define-struct triangle (base height)) (define-struct square (side)) ;; ;; Examples: ;; (make-triangle 1 2) ;; (make-triangle 2 5) ;; (make-square 4) ;; (make-square 2.5) ;; ;; Template for ANY function that processes a shape #| ;; shape<shape-functionfunction> : shape -> ... (define (shape<shape-functionfunction> ... shape ...) (cond [(triangle? shape) ... (triangle-base shape) ... ... (triangle-height shape) ...] [(square? shape) ... (square-side shape) ...])) |#

  
  

• Example 4. Data definition of list-of-numbers:

  Code Block

  ;; A list-of-numbers is either ;; empty, or ;; (cons n lon) ;; where n is a number, and lon is a list-of-numbers ;; ;; Examples: ;; empty ;; (cons 1 empty) ;; (cons 1 (cons 4 empty)) ;; ;; Template for list-of-numbers #| ;; lon<lon-ff> : list-of-numbers -> ... (define (lon<lon-ff> ... a-lon ...) (cond [(empty? a-lon) ...] [(cons? a-lon) ... (first a-lon) ... ... (lon<lon-ff> ... (rest a-lon) ...) ... ])) |#

  
  

• Once your have written a data definition, you can use it in the rest of the assignment.
• The template for writing a function that processes a particular kind of data (data type) is based only on the corresponding data definition, not on the particular functions that you happen define on that type. Hence, there is only one template per data type. This same template is used as the starting point for writing all functions that process that data type.
• If the type is a structure, the template should include the field extraction operations. If the type is a union, the template needs to have an appropriate cond statement (see example 3). If the type is recursive, the template includes the expected recursive calls on the recursive data components (see example 4).

...

;; COMP 311 HW #Sample
;; Corky Cartwright <cork@rice.edu>

;; A list-of-numbers is either:
;;   empty, or
;;   (cons n alon) where n is a number and alon is a list-of-numbers
;;
;; Examples:
;;   empty
;;   (cons 10 (cons -1 (cons 5 empty))) = '(10 -1 5)
;;   (cons 1 (cons 2 (cons 3 empty)))   = '(1 2 3)
;;   (cons 3 (cons 2 (cons 1 empty)))   = '(3 2 1)

#| Template: (enclosed in block comment brackets)
   (define (lon<lon-ff> ... a-lon ...)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (lon<lon-ff> ... (rest a-lon) ...) ... ]))
|#

;; Main function: sort

;; ContractSignature and purposePurpose:
;; sort: list-of-numbers -> list-of-numbers
;; Purpose: (sort alon) returns the a list with same elements (including duplicates) as alon but in ascending order.

;; Examples:
;; (sort empty) = empty
;; (sort '(0)) = '(0)
;; (sort '(1 2 3)) = '(1 2 3)
;; (sort '(3 2 1)) = '(1 2 3)
;; (sort '(10 -1 10 -20 5)) = (-20 -1 5 10 10)

#| Template Instantiation for the sort function:
   (define (sort a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (sort (rest a-lon)) ... ]))
|#
;; Code:

   (define (sort a-lon)
     (cond
       [(empty? a-lon) empty]
       [(cons? a-lon) (insert (first a-lon) (sort (rest a-lon)))]))

;; Tests
(check-expect (sort empty) empty)
(check-expect (sort '(0)) '(0))
(check-expect (sort '(1 2 3)) '(1 2 3))
(check-expect (sort '(3 2 1)) '(1 2 3))
(check-expect (sort '(10 -1 10 -20 5)) '(-20 -1 5 10 10))

;; Auxiliary function

;; ContractSignature and purposePurpose
;; insert: number list-of-numbers -> list-of-numbers
;; Purpose: (insert n alon), where alon is in increasingascending order, returns a list containing n and the elts of alon in ascending order

;; Examples:

;;  (insert 17 empty) = '(17)
;;  (insert 17 '(17)) = '(17 17)
;;  (insert 4 '(1 2 3)) = '(1 2 3 4)
;;  (insert 0 '(1 2 3)) = '(0 1 2 3)
;;  (insert 2 '(1 1 3 4)) = '(1 1 2 3 4)

#| Template instantiation
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (insert n (rest a-lon)) ... ]))
|#

;; Code
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) (cons n empty)]
       [(cons? a-lon)
        (if (<= n (first a-lon)) (cons n a-lon)
            (cons (first a-lon) (insert n (rest a-lon))))]))
;; Tests

(check-expect (insert 17 empty) '(17))
(check-expect (insert 17 '(17)) '(17 17))
(check-expect (insert 4 '(1 2 3)) '(1 2 3 4))
(check-expect (insert 0 '(1 2 3)) '(0 1 2 3))
(check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4))

...

;; Auxiliary function

;; ContractSignature and purpose
;; insert: number list-of-numbers -> list-of-numbers
;; Purpose: (insert n alon), where alon is in increasing order, returns a list containing n and the elts of alon in ascending order

;; Examples and Tests:

(check-expect (insert 17 empty) '(17))
(check-expect (insert 17 '(17)) '(17 17))
(check-expect (insert 4 '(1 2 3)) '(1 2 3 4))
(check-expect (insert 0 '(1 2 3)) '(0 1 2 3))
(check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4))

#| Template instantiation
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (insert n (rest a-lon)) ... ]))
|#

;; Code
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) (cons n empty)]
       [(cons? a-lon)
        (if (<= n (first a-lon)) (cons n a-lon)
            (cons (first a-lon) (insert n (rest a-lon))))]))

Updated Sample Program

A function named sort is included in the core library for most (all?) of the Racket dialects supported by DrRacket.  The following revision (with no changes to the code other than the name of the sort function) should run in all of the HTDP student languages except Beginner which Beginner which excludes abbreviated list notation using the quote character ' , which appears in tests.

;; COMP 311 HW #Sample
;; Corky Cartwright <cork@rice.edu>
 
;; A list-of-numbers is either:
;;   empty, or
;;   (cons n alon) where n is a number and alon is a list-of-numbers
;;
;; Examples (some written as binding of variable names to values)
;;   empty
;;   (cons 10 (cons -1 (cons 5 empty))) = '(10 -1 5)
(define l0    (cons 0 empty))                    ;;  '(0)
(define l123  (cons 1 (cons 2 (cons 3 empty))))  ;;  '(1 2 3)
(define l321  (list 3 2 1))                      ;;  '(3 2 1)
 
#| Template for the data type list-of-numbers (enclosed in block comment brackets):
   (define (lon-f ... a-lon ...)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (lon-f ... (rest a-lon) ...) ... ]))
|#
 
;; Main function: _sort_  (the name sort is already defined in the library)
 
;; Contract and purpose:
;; _sort_: list-of-numbers -> list-of-numbers
;; Purpose: (_sort_ alon) returns the a list with same elements (including duplicates) as alon but in ascending order.
 
;; Examples (written as executable tests)
;; Named values which make the executable tests more concise

;; Executable tests (most using named values define as list-of-numbers examples)
(check-expect (_sort_ empty) empty)
(check-expect (_sort_ l0) l0)
(check-expect (_sort_ l123) l123)
(check-expect (_sort_ l321) l123)
(check-expect (_sort_ '(10 -1 10 -20 5)) '(-20 -1 5 10 10))

;; TestsNote: the preceding ests are already set up as executable examples
 
#| Template Instantiation for _sort_ function:
   (define (_sort_ a-lonlont)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (_sort_ (rest a-lon)) ... ]))
|#
;; Code (using not yet defined auxiliary function insert)
 
   (define (_sort_ a-lon)
     (cond
       [(empty? a-lon) empty]
       [(cons? a-lon) (insert (first a-lon) (_sort_ (rest a-lon)))]))

;; Auxiliary function
 
;; Contract and purpose
;; insert: number list-of-numbers -> list-of-numbers
;; Purpose: (insert n alon), where alon is in increasing order, returns a list containing n and the elts of alon in ascending order
 
;; Examples:
 
(check-expect (insert 17 empty)  '(17))
(check-expect (insert 17 '(17))  '(17 17))
(check-expect (insert 4 l123) '(1 2 3 4))
(check-expect (insert 0 l123) '(0 1 2 3))
(check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4))
 
#| Template instantiation
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (insert n (rest a-lon)) ... ]))
|#
 
;; Code
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) (cons n empty)]
       [(cons? a-lon)
        (if (<= n (first a-lon)) (cons n a-lon)
            (cons (first a-lon) (insert n (rest a-lon))))]))
  
;; Tests already set up as executable examples

...