Before the lab

Background

• This lab completes our discussion git, and starts our first programming language, namely Racket.

• For learning racket, we will mainly follow Functional Introduction to computer science

• You may also find the BSL reference helpful.

Viewing project history

1. At any point you can view the history of your changes using

    $ git log
   

   Use this command to verify that all the changes you expected to be pushed to the server really were.

   If you also want to see complete diffs at each step, use

    $ git log -p
   

   Often the overview of the changes is useful to get a feel for each step

    $ git log --stat --summary
   

2. In most projects, you have to share commit messages to (at least) the same people who view your source code. Share your "best commit" message with one or more of your neighbours.

3. Find something positive to say about the other commit messages you are reading.

4. Find a constructive improvement with one of the other messages. Don't be mean, people have varying levels of experience with this.

Racket

Racket Expressions.

• Form groups of 2 or 3.

• Work through Exercise 0: for each of the following lines of code, someone from the group should guess what is wrong before trying it in the Interactions window of DrRacket.

    (* (5) 3)
    (+ (* 2 4)
    (5 * 14)
    (* + 3 5 2)
    (/ 25 0)
  

• Work through Exercise 1. In general where the text asks you to predict the value of an expression, you can also enter into the definitions window something like

    (check-expect (* 6 9) 42)
  

  When you run (e.g. F5), then you will find out if your prediction is correct.

• Work through Exercise 2. You can test your answers by applying the following functions to appropriate arguments. Notice that the value of y does not matter.

#lang htdp/bsl
(define y 18)
(define (t1 x)
  (or (= x 0) (< 0 (/ y x))))
(define (t2 x)
  (or (< 0 (/ y x)) (= x 0)))
(define (t3 x)
  (and (= x 0) (< 0 (/ y x))))
(define (t4 x)
  (or (< 0 (/ y x)) (not (= x 0))))

Racket functions

• Do this part on your own.

• Do Exercise 4

  Here are some tests to help you check your function

(check-expect (middle-of-three 1 2 3) 2)
(check-expect (middle-of-three 2 1 3) 2)
(check-expect (middle-of-three 1 3 2) 2)

• Do these tests suffice? Why or why not?

The DrRacket stepper

• copy arith.rkt, save it as ~/cs2613/labs/L02/arith.rkt and commit it.

• run your arith.rkt in DrRacket; observe that the test fails

• run your arith.rkt in the DrRacket Stepper. Notice that after about 7 steps, we have reduced the test case to multiplication by zero which looks wrong. That means that the problem is with the recursive (reduction) step.

• Fix the a > 0 case of my-* to match the following formula a * b = (a - 1) * b + b, while still using my-+

• DrRacket should report "The test passed!" when you have it working. Commit this version of your code. Remember that git commit message quality counts in this course, so work on making commit messages.

Test Coverage

Unit testing is an important part of programming, and has inspired something called test driven development.

• This activity continues arith.rkt from the first half of the lab.

• Under

  Language -> Choose Language -> Show Details -> Dynamic Properties
  

  enable

  ⊙ Syntactic test suite coverage
  

• comment out the given test

• run your code in DrRacket again

• most likely you will have some code highlighted with orange text and black foreground. This means that code is not covered by your test suite. Uncomment the given test, and if needed add tests to cover each piece of uncovered code.

• When you have complete test coverage, commit your code.

  In this course, for all racket assignments you will lose marks if you don't have complete test coverage.

• Push your repo to coursegit.

• If you have extra time, run the tests on the command line with raco test arith.rkt

Before Next Lab

Before the lab

Q&A

• Questions about Assignment 1?

Setup

• make a directory labs/L03 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Semantics

As you read in FICS unit 3, we can understand evaluation ("running") of Racket programs as a sequence of "reductions" or "substitutions". These rules are similar to the reduction steps in the DrRacket stepper.

The stepper uses the following rules for and and or (notice that these rules enforce short circuit evaluation)

(and true exp2 ...) => (and exp2 ...)
(and false exp2 ...) => false
(or true exp2 ...) => true
(or false exp2 ...) => (or exp2 ...)
(and) => true
(or) => false

Following Exercise 7, write a new set of rules that requires at least two arguments for and and or. The rules are for human consumption; you can write them as comments in DrRacket. You can write "exp1 exp2 ..." to mean at least 2 expressions.

Discuss your answers with a your group, and try a couple evaluation small examples by hand using your rules.

Simulating Natural Numbers I

Write the times function from Exercise 11 in FICS. You can (and should) use the following code from the linked discussion

#lang htdp/bsl
(define-struct Z ())
(define-struct S (pred))
(define (pred nat)
  (cond
    [(Z? nat) (error "can't apply pred to Z")]
    [(S? nat) (S-pred nat)]))

(define (plus nat1 nat2)
  (cond
    [(Z? nat1) nat2]
    [(S? nat1) (make-S (plus (S-pred nat1) nat2))]))

Here is the template for structural recursion on (simulated) natural numbers. See the linked text (or the plus function just above) for how to add a second "carried-along" parameter.

(define (my-nat-fn nat)
  (cond
    [(Z? nat) ...]
    [(S? nat) ... (my-nat-fn (S-pred nat)) ...]))

Here are some tests to get you started. As always, try to have as complete test coverage as possible. Depending on how you choose the language in DrRacket, the line (define-struct S (pred)) may show partial coverage; you can ignore this for this lab.

;; 0 * 0 = 0
(check-expect (times (make-Z) (make-Z)) (make-Z))
;; 0 * 1 = 0
(check-expect (times (make-Z) (make-S (make-Z))) (make-Z))
;; 2 * 1 = 2
(check-expect (times (make-S (make-S (make-Z)))
                       (make-S (make-Z)))
              (make-S (make-S (make-Z))))

You may find it helpful to refer back to your solution from L02.

Simulating Natural Numbers II

Write the compare function from Exercise 11 in FICS. Your function compare should use the struct definitions Z and S, and pass the following tests

;; 0 = 0
(check-expect (compare (make-Z) (make-Z)) 'equal)
;; 0 < 1
(check-expect (compare (make-Z) (make-S (make-Z))) 'less)
;; 1 > 0
(check-expect (compare (make-S (make-Z)) (make-Z)) 'greater)
;; 2 > 1
(check-expect (compare (make-S (make-S (make-Z)))
                       (make-S (make-Z))) 'greater)

Before Next Lab

Before the lab

Questions from last time

• The programming languages we will study this term are all dynamically typed. This means that not only the value but also the type of variables can change at runtime. Why does this make testing even more important?

• What kind of software problems is testing not well suited to find?

• Why might mutable state (e.g. instance variables in Java) make writing unit tests harder?

Setup

• make a directory labs/L04 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Structural recursion, on numbers

Use structural (note that structural here is only indirectly related to Racket structs) recursion on natural numbers (not the simulated ones from above, but regular Racket numbers like 1, 42, and 1337) to define a function (sum-factors n max-factor) that sums all factors of n (including 1) no larger than max-factor

Recall the template for structural recursion on natural numbers:

(define (my-nat-fn n)
  (cond
    [(zero? n) ...]
    [(positive? n) ... (my-nat-fn (sub1 n)) ...]))

Try to use only one recursive call to sum-factors like in the template. Keep in mind that the n in the template might be a different parameter of your function. You can use the builtin function remainder to test for divisibility.

The following tests should pass

;; 1+2+3 = 6
(check-expect (sum-factors 6 5) 6)
;; 1+2+4+7+14 = 28
(check-expect (sum-factors 28 27) 28)

Substitute in a list

Complete FICS Exercise 13.

Note the template for structural recursion.

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...]))

Here is a test case based on the linked test

(check-expect
 (substitute 3 "three" (list "four" 3 4 "three" 3))
 (list "four" "three" 4 "three" "three"))

Uniquifying lists

Complete FICS Exercise 15. Although probably not intended by the original question, use the built-in BSL function member? to simplify your solution. Otherwise use only the constructs specified in Exercise 14, and structural recursion. Here is one test case derived from the linked text.

(check-expect
 (unique-right
  (list 1 4 2 1 5 4))
 (list 2 1 5 4))

Add an element to all lists

Recall the template for structural recursion on lists

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...])

Use this template to write a function cons-all that adds a given element to the front of each given sublist. This is related to FICS Exercises 23-25 (but you only need to write cons-all, not do those exercises).

The following test case illustrates the use of cons-all. You will need to use the language #lang htdp/bsl+ or "Beginning Student with List Abbreviations" or replace the use of ' in the following.

(check-expect (cons-all 3 '((2 4) () (5)))
              '((3 2 4) (3) (3 5)))

Before Next Lab