CSC 372, Spring 2023 Assignment 7 Due: Friday, April 21 at 23:59:59

Overview

This assignment asks you to apply Racket to a variety of problems. Some, such as num-symbols and doubled? are straightforward list processing procedures. In unary.rkt you'll be writing a group of related procedures to manipulate unary numbers represented as lists. minmax.rkt is a standalone program that's run from the command-line.

This assignment has one "big problem": pinfo.rkt. It asks you to write Racket code that analyzes Racket code. We'll see that's relatively easy because Racket, like all Lisps, is homoiconic, but pinfo.rkt does pose some challenges. In terms of difficulty, pinfo.rkt should be worth a few more points than are assigned, but I didn't want to bet too much of your grade on it.

Racket facilitates both functional programming and imperative programming, and you're free to mix them as you see fit. However, with one exception, higher-order procedures are not allowed on this assignment. (I'll open up those to you on assignment 8.)

This is the first Racket assignment I've ever written, so all problems are brand new, and all sorts of issues might turn up with them and/or the Tester machinery. It's likely to be a Bug Bounty Bonanza, with an overflowing FAQ page.

I'm not entirely happy with this collection of problems but sometimes you just need to call something done, get it out the door, and move on to what's next, so here's what I've settled on for assignment 7.

Along with this write-up, the material presented on Racket slides 1-154 should provide all you need to complete this assignment. If you find yourself Googling up exotic things we haven't talked about, you're perhaps overlooking something that's been provided; I never intend assignments to be a scavenger hunt.

Looking ahead, there will be one more Racket assignment, due at 23:59:59 on May 3, the last day of classes. I hope to publish it no later than April 24. If I'm not flubbing any calculations, you'll find 84 points worth of problems on this assignment. If things go as planned, Assignment 8 will have 70 points worth of problems, producing the total of exactly 580 assignment points cited as an ideal in the syllabus. (If things don't go as planned, Assignment 8 might end up with less than 70 points, and in turn that would make assignment points worth slightly more than 0.1% of the final grade each. And, as I write this, I see a mistake in the syllabus in the middle of page 11: it has an example of such a change in weighting, but uses 600 points instead of 580 as the ideal.)

ASSIGNMENT-WIDE RESTRICTIONS

There are two assignment-wide restrictions:

  1. You may not use any higher-order procedures.

    However, there is one exception: You'll see in the write-up for pinfo.rkt that you'll need to use sort, which requires a comparison predicate.

  2. You may not require (i.e., import) any modules.

The Usual Stuff

Odds and Ends

A Tester workaround

The Tester currently gets tripped up on some test case expressions with quoted lists, like this one: 
(num-symbols '(a b c))
As a work-around, troublesome test case expressions use the quote special form instead: 
(num-symbols (quote (a b c)))

A show macro

As a simple debugging aid I've written a show macro that prints both a given expression and its value. Here's an example of usage: 
% cat a7/show-demo.rkt
#lang racket

(include "a7/show.rkt")

(define-values (x y z) (values 3 4 5))

(show (+ x (* y z)))
(show (string-split "some words to split"))
(show x y z)
Execution: 
% cp a7/show-demo.rkt .; racket show-demo.rkt
(+ x (* y z)): 23
(string-split some words to split): '("some" "words" "to" "split")
x: 3
y: 4
z: 5
The important thing to "get" about show is that instead of having to add code (underlined) to "label" the output with something like, 
(printf "(length x): ~a\n" (length x))
you can write just 
(show (length x))
It is simply impossible to write something like show in Java! You can get pretty close to show with macros in C++ and, to a lesser degree, in C. You can get the same effect in Python with IceCream (and maybe other packages, too), but the implementation of IceCream has dozens, maybe hundreds of lines of core code, versus a half-dozen lines for a7/show.rkt.

Short names for procedures when testing by hand

Just like in Haskell and Python, you can give a procedure with a long name a shorter synonym for testing. For example, if at the end of your num-symbols.rkt you add 

(define ns num-symbols)
you can then test it with (ns '(a 1 b)).

The rk/i script

If you're developing with Dr. Racket, there's a dead-simple edit-run cycle: edit your code in one pane of the window and hit control-R (or cmd-R) to run it and see the output below. However, for working with Racket from the command line I wanted something like ghci's :r or swipl's make., so I could edit with Emacs or Vim in another window and reload. I haven't found anything in XREPL (which is what you get when you run racket on the command-line) that provides a similar capability, so I wrote a simple Bash script, rk/i. (The name is inspired by python3 -i FILE, which loads FILE and then starts the REPL.)

An example of using rk/i follows. Here's a source file: 

% cat hello.rkt
#lang racket

(define (hello)
    (displayln "Hello!")
    (displayln "This is v1"))
Let's load it up with rk/i and call hello: 
% rk/i hello.rkt
Welcome to Racket v8.5 [cs].
"hello.rkt"> (hello)
Hello!
This is v1
"hello.rkt">
Now, in another window I'll edit hello.rkt and change that v1 to v2. Then, still in rk/i in this "window", I'll call a procedure named r to reload the current file. Then I'll call hello again, to hopefully see the new version number. 
"hello.rkt"> (r)
  [re-loading /home/whm/372/a7/hello.rkt]
"hello.rkt"> (hello)
Hello!
This is v2
"hello.rkt">
Control-D exits rk/i.

Unfortunately, if an error is encountered on the initial load, (r) doesn't work: 

% rk/i hello.rkt
Welcome to Racket v8.5 [cs].
hello.rkt:3:0: read-syntax: expected a `)` to close `(`
...
> (r)
r: undefined;
>
In this case I'll need to exit rk/i with control-D, fix the error, and try rk/i again.

Run-time errors in XREPL

Dr. Racket shows great detail when an error is encountered but sadly, XREPL does not. Here's a version of sum-nums with a bug—line 6 has (L car) instead of (car L): 

% cat -n sum-nums.rkt
     1  #lang racket
     2
     3  (define (sum-nums L)
     4      (cond
     5          [(empty? L) 0]
     6          [(number? (L car)) (+ (car L) (sum-nums (cdr L)))]
     7          [else (sum-nums (cdr L))]))
Here's what we see when we run it: 
> (sum-nums '(3 1 5))
application: not a procedure;
 expected a procedure that can be applied to arguments
  given: '(3 1 5)
 [,bt for context]
XREPL has a ,bt command but it doesn't show us a line number: 
"sum-nums.rkt"> ,bt
application: not a procedure;
 expected a procedure that can be applied to arguments
  given: '(3 1 5)
  context...:
   body of "/home/whm/372/a7/sum-nums.rkt"
   /home/whm/372/a7/sum-nums.rkt:3:0: sum-nums
   /usr/local/racket/share/pkgs/xrepl-lib/xrepl/xrepl.rkt:1573:0
   /usr/local/racket/collects/racket/repl.rkt:11:26
One thing we can do is to (1) add the failing call to sum-nums.rkt and (2) run it with rk/et ("et" for error-trace): 
% cat sum-nums.rkt
#lang racket

(define (sum-nums L)
    (cond
        [(empty? L) 0]
        [(number? (L car)) (+ (car L) (sum-nums (cdr L)))]
        [else (sum-nums (cdr L))]))

(sum-nums '(3 1 5)) ; ADDED

% rk/et sum-nums.rkt
application: not a procedure;
 expected a procedure that can be applied to arguments
  given: '(3 1 5)
  errortrace...:
   /home/whm/372/a7/sum-nums.rkt:6:18: (L car)
   /home/whm/372/a7/sum-nums.rkt:6:9: (number? (L car))
   /home/whm/372/a7/sum-nums.rkt:4:4: (cond ((empty? L) 0) ((number? ...
  context...:
   /home/whm/372/a7/sum-nums.rkt:3:0: sum-nums
   body of "/home/whm/372/a7/sum-nums.rkt"
Following errortrace...: above, we see the offending call, (L car), at line 6, column 18.

Yes, I thought the 21st century would be a little better than this.

Without further ado...
The Problems of Assignment 7!

Problem 1. (6 points) ruler.rkt

Write a Racket procedure ruler that takes an integer argument between 1 and 99, inclusive and prints a two-line "ruler", like this: 

> (ruler 60)
         1         2         3         4         5         6
123456789012345678901234567890123456789012345678901234567890

> (ruler 18)
         1
123456789012345678

> (ruler 63/3)
         1         2
123456789012345678901

Note: For readability the examples above and below are shown with a blank line added after the output from each call.

If ruler is called with an integer that is out of range or that does not satisfy the integer? predicate, a line with just a question mark is printed: 

> (ruler 100)
?

> (ruler 'ten)
?

> (ruler 64/3)
?

Note: You'll find that (integer? 34.0) returns #t, but as a simplification we won't test with something like (ruler 34.0).

RESTRICTION: To make this problem a little more interesting, the characters ", ', and # (quotation mark, apostrophe, and number sign) MAY NOT APPEAR IN ruler.rkt! (Yes, that's why the error message is so short.)

Problem 2. (14 points) unary.rkt

Note: I'm making this problem the first list-processing problem on this assignment in hopes the restrictions (see below!) will help you focus on some basic elements of Racket, perhaps as the warmup.hs problems on the Haskell assignments maybe helped you get some practice with basics in Haskell.

A unary number represents a number N with a series of N identical marks. The number 3 might be represented as |||, a 7 is |||||||, and a 1 is |.

For this problem you are to write a collection of simple Racket procedures that operate on unary numbers that are represented as lists of 1s. For example, 4 is '(1 1 1 1). It's arguable whether zero can truly be represented as a unary number, but we will represent zero with an empty list, '().

Here are examples using three of the procedures: 

> (decimal->unary 5)
'(1 1 1 1 1)

> (unary-add '(1 1 1) '(1 1 1 1))
'(1 1 1 1 1 1 1)

> (unary->decimal '(1 1 1 1))
4

RESTRICTIONS! The following restrictions apply:

Here are the procedures you are to implement:

Procedure Description Notes
(decimal->unary n) Convert a decimal number n to its unary representation. Assume n is non-negative.
(unary-zero) Return the unary representation of zero, i.e., an empty list. Provided
(unary-one) Return the unary representation of the number 1, i.e. the list '(1). Provided
(unary-zero? n) Return #t if n is the unary representation of the decimal number 0 Provided
(unary-one? n) Return #t if n is the unary representation of the decimal number 1. Provided
(unary? n) Return #t if n is a unary number, i.e., either the empty list or a list consisting only of 1s.
(unary->decimal n) Convert a unary number n to its decimal representation.
(unary-add a b) Return the sum of the unary numbers a and b.
(unary-sub a b) If a >= b then return a - b, otherwise return the symbol 'negative.
(unary-lt a b) Return #t if a < b, else return #f.
(unary-mul a b) Use repeated unary addition to compute a * b.

NOTE: All procedures except unary? assume that argument(s) that represent unary numbers are valid unary numbers.

Start your work on this problem by copying a7/unary-starter.rkt to unary.rkt in your assignment 7 directory. You'll see that rather than starting with #lang racket, a module declaration is used. Be sure your procedure definitions are enclosed in that module declaration, following the definitions of the provided procedures.

Here are examples of each procedure in operation: 

> (decimal->unary 5)
'(1 1 1 1 1)

> (decimal->unary 15)
'(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

> (unary-zero)
'()

> (unary-one)
'(1)

> (unary-zero? (unary-zero))
#t

> (unary-zero? (unary-one))
#f

> (unary? '(1 1 1))
#t

> (unary? '(1 x 1))
#f

> (unary? 'x)
#f

> (unary->decimal (unary-zero))
0

> (unary->decimal (unary-one))
1

> (unary->decimal '(1 1 1))
3

> (unary->decimal (decimal->unary 15))
15

> (unary-add '(1 1) '(1 1 1))
'(1 1 1 1 1)

> (unary-add '(1 1) (unary-one))
'(1 1 1)

> (unary-add (decimal->unary 15) (decimal->unary 9))
'(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

> (unary-sub '(1 1 1 1) '(1))
'(1 1 1)

> (unary-sub '(1 1 1 1) '(1 1 1 1 1 1 1))
'negative

> (unary-sub (unary-one) (unary-one))
'()

> (unary-sub (unary-zero) (unary-one))
'negative

> (unary-lt (unary-zero) (unary-one))
#t

> (unary-lt '(1 1 1 1) '(1))
#f

> (unary-lt '(1 1) '(1 1))
#f

> (unary-lt '(1 1) '(1 1 1))
#t

> (unary-mul '(1 1 1) (unary-one))
'(1 1 1)

> (unary-mul '(1 1 1) '(1 1 1 1))
'(1 1 1 1 1 1 1 1 1 1 1 1)

> (unary->decimal (unary-mul '(1 1 1) '(1 1 1 1)))
12

> (unary-mul (decimal->unary 20) (unary-zero))
'()

A restriction checker for unary.rkt

I doubt that I'll get an automated restriction checker in place for this problem but a7/check-unary is a script to help you manually look for violations. It reads unary.rkt, does some simple textual manipulations facilitated by Racket's simple syntax, and discards things that are known to be ok, leaving a list of things to manually double-check. Here's what I see when I run it on my solution: 

% a7/check-unary
helper
%
It looks like I've got a procedure named helper, and you might have some helper procedures, too. That's fine, of course.

Note: a7/check-unary will report variable names like lst, value, etc. You can avoid that by only using one-character variable names, as I happened to, without really thinking about it.

A note about testing

Whenever a7/tester tests this problem, it copies a7/test-unary.rkt and a7/test-unary2.rkt to your directory. Don't have any files of your own creation with those names—they will get clobbered!

Acknowledgement

This problem and write-up are closely based on a Racket problem that Dr. Collberg has used and that I enjoyed solving myself when first learning Racket. I appreciate him letting me use it!

Problem 3. (3 points) num-symbols.rkt

Write a Racket procedure num-symbols that takes one argument, a list, and returns the number of symbols in the list. Examples: 

> (num-symbols '(a b c))
3

> (num-symbols '(1 2 a 3 b "four" c))
3

> (num-symbols '(1 2 a 3 b "four" c d))
4

> (num-symbols (string->list "abcd"))
0

> (num-symbols '(x))
1

Problem 4. (2 points) doubler.rkt

Write a Racket procedure doubler that takes a list and returns a list with each element duplicated, just like doubler.hs on assignment 4, but with no pesky restrictions. Examples: 

> (doubler '(a b c))
'(a a b b c c)

> (doubler (range 5))
'(0 0 1 1 2 2 3 3 4 4)

> (doubler (string->list "testing"))
'(#\t #\t #\e #\e #\s #\s #\t #\t #\i #\i #\n #\n #\g #\g)

> (doubler empty)
'()

Problem 5. (3 points) eq-pairs.rkt

Write a Racket procedure eq-pairs? that takes a list and returns #t iff the list consists of pairs of values that are equal to each other. If not, eq-pairs? returns #f. Examples: 

> (eq-pairs? '(0 0 1 1 2 2 3 3 4 4))
#t

> (eq-pairs? (list 1 2/2 3 (+ 1 2) (length (range 5)) 5))
#t

> (eq-pairs? '(a a b d))
#f
An empty list produces #t. Any list of odd length produces #f. 
> (eq-pairs? empty)
#t

> (eq-pairs? '(1 1 1))
#f
Easy challenge: Handle odd-lengths without an explicit check, like (odd? (length ...)).

Problem 6. (3 points) longer-syms.rkt

Write a Racket procedure longer-syms that takes two lists of symbols and produces a list with the longer of the two symbols in each corresponding position. Example: 

> (longer-syms '(some symbols right here) '(are these or those longer?))
'(some symbols right those)
longer-syms stops when either list runs out. 
> (longer-syms '(a b c d e) '(xx))
'(xx)

> (longer-syms '(a b c d e) '())
'()

If both symbols at a given position are the same length, the symbol :samelen: is produced for that position. 

> (longer-syms '(a bb ccc dddd eeee) '(aaaaa bbbb ccc dd e))
'(aaaaa bbbb :samelen: dddd eeee)

> (longer-syms '(a b c d e) '(a bb c dd e f ff))
'(:samelen: bb :samelen: dd :samelen:)

Problem 7. (4 points) 2nd.rkt

Write a Racket procedure 2nd that returns the second largest value in a list of numbers. If the list has less than two numbers, return 'none. 

> (2nd '(3 1 5 7))
5

> (2nd '(1/2 1/4 1/3 1/5))
1/3

> (2nd '(1/2 1/4 1/3 1/5 1/3))
1/3

> (2nd empty)
'none

> (2nd '(10))
'none

RESTRICTION:You may not do a sort—your solution should be O(n), based on the length of the input list.

Problem 8. (4 points) larger.rkt

Write a variadic Racket procedure (larger lower-bound value1 ... valueN) that returns a list of the values that are larger than lower-bound. All arguments are numbers. Examples: 

> (larger 4 3 1 5 7 9 2)
'(5 7 9)

> (larger 40 34 37 25 43 40 4 46 19 13 10 16 28 22 31 49 7 1)
'(43 46 49)

> (larger 20 5 15 -5 0 25 55/2 10 25/2 5/2 35/2 45/2 20 -5/2 15/2)
'(25 55/2 45/2)

> (larger 3 1 2)
'()

> (larger 3)
'()
If larger is called with no arguments, an error should be produced: 
> (larger)
larger: arity mismatch;
 the expected number of arguments does not match the given number
  expected: at least 1
  given: 0
However, you shouldn't need to write any code to detect that condition. (My code does not contain the text "arity mismatch", for example.)

Problem 9. (8 points) fsort.rkt

This problem is a Racket reprise of fsort.pl from assignment 6—you're to write a flip sort in Racket. Examples: 

> (fsort 3 1 5)
'(stack: (3 1 5) flips: (2))

> (fsort 5 4 3 2 1)
'(stack: (5 4 3 2 1) flips: (5))

> (fsort 5 1 3 1 4 2)
'(stack: (5 1 3 1 4 2) flips: (6 2 5 2 4 3))

> (fsort 3 1 3 1 2)
'(stack: (3 1 3 1 2) flips: (5 3 4 2 3))

> (fsort 1 2 3)
'(stack: (1 2 3) flips: ())
Note that fsort returns a list with four elements:
  1. The symbol stack:
  2. A list with the pancakes to sort
  3. The symbol flips:
  4. A list of the flips

Just like in the Prolog version, you don't need to match my flips; you simply need to produce a list of flips that produces a sorted stack. Two requirements for the flips carry over from the Prolog version:

You may assume that stacks always have at least one pancake and that pancake sizes are always greater than zero.

Implementation notes