1. An enigma [10]

Complete the comment so it describes in a sentence or two what does the following function does and what kind of argument it should be called with to avoid getting a run time error.

(define (enigma x)
  ;; the enigma function ...
  (or (null? x)
      (null? (rest x))
      (and (not (equal? (car x) (car (cdr x))))
           (enigma (rest x)))))

Hint: it you can't see what enigma does by inspection, load it into a Scheme interpreter and experiment with it. If it is obvious from the code what it does, it's still wise to load it into Scheme and verify your theory.

2. A conundrum [10]

Complete the comment so it describes in a sentence or two what does the following function does and what kind of argument it should be called with to avoid getting a run time error.

(define (conundrum x y)
  ;; The amazing function conundrum ...
  (cond ((null? y) -1)
        ((equal? x (first y)) 0)
        (else (let ((z (conundrum x (rest y))))
                   (if (< z 0) z (+ 1 z))))))

Recall that the let is used to create an environment with new local variables and to initially bind them to particular values. Let evaluates the expressions for the initial values outside the environment and then creates the new local variables and makes the initial assignments. A typical example is creating a local variable TEMP used to swap the values of two other variables, A and B:

(let ((temp #f)) 
   (set! temp a)
   (set! a b)
   (set! b temp))

Note that we might simplify this as follows:

(let ((temp a)) 
   (set! a b)
   (set! b temp))

3. lambda expressions [20]

Write lambda expressions that evaluate to the following:

• 3.1 (5 pts) A function that takes no arguments and always returns 0
• 3.2 (5 pts) A function that takes two strings and returns the one that should occur first in a alphabetic ordering. (Hint: the builtin function string<? will be helpful.)
• 3.3 (10 pts) A function that takes a single argument, F, that is a predicate function and returns a new function that is F's converse. Whenever the predicate F is true for some argument, its converse will be false and whenever F is false, its converse will be true. (Hints: the answer is simple and will have the form (define q3.3 (lambda (F) ...)). You will need a lambda inside a lambda. Since you don't know how many arguments F will take (and might in fact take a variable number) you will have to use apply and the syntax for defining a lambda expression that takes any number of arguments -- e.g., ((lambda X (apply + (map square X))) 1 2 3 4) returns 30.

(lambda (n) (+ n 1))

> ((lambda (n) (+ n 1)) 100)
101

Welcome to MzScheme v4.2.5 [3m], Copyright (c) 2004-2010 PLT Scheme Inc.
> (require "test.ss")
> (load "hw7.ss")
> (test "tests2.in" "tests2.out")
#t  

4. unique-atoms (30)

Write a function unique-atoms that takes an arbitrary s-expression and returns a list of the unique atoms in it. The order of the atoms in the list is not important.

> (load "hw6.ss")
> (unique-atoms '(a (b) b ((c)) (a (b))))
(a c b)
> (unique-atoms '(a . a))
(a)
> (unique-atoms '())
()

Hint: Start by writing a function atoms that takes an s-expression and returns a list of all of the atoms in it. Then write a function unique-members that takes a list and returns a list of the unique top-level elements of the list. Once you have these two, you are almost done.

5. Simple Perl (30)

The instructors need help rewriting their gradesheet generation program in Perl. (It was originally written as a 8-character APL program, and no one alive can figure out how it works;-) ) The requirements are simple:

It should read the file from the filehandle STDIN. so, no opening of files necessary--you can just start reading.

Each line consists of a series of fields, separated by tabs ("\t").

The file starts off with a single header line, in which each field is the label for that corresponding column. After splitting the line up into fields at the tabs, scan the list of fields for certain patterns:

1. A header field called "Name" indicates the "student name" column.
2. A header field called "Email" indicates the "email address" column.
3. Any header field that contains the substring "Problem": e.g., "Problem #1" or "Extra Credit Problem", indicates a column containing a grade for that problem. For each of these grade colums, the very next column holds a comment for that grade.

There might be other columns, which you should ignore. Also, the columns are in no particular order (except that each "Problem" column has the corresponding comment column immediately after it).

The rest of the file consists of student grades, one student's record per line. Each record contains that student's name, email address, numerical grade for each problem, and a comment for each problem, in the order specified by the headers. As with the headers, any other fields can be safely ignored.

For each student record, you should do the following:

1. Break the line up into fields at tabs.
2. Print out "Name: ", followed by the student's name, then a newline.
3. Print out "Email: ", followed by the student's email address, then a newline.
4. For each column position that corresponds to a problem grade:
   • Print out: "Grade for ", then the label for that problem (saved from the header), then the actual numerical grade.
   • Then, print out an optional comment according to the following rules:
     • If the associated comment is non-blank, print that.
     • Else if the grade is 0, print "Not done."
     • Otherwise, don't print anything.
5. Print out "Final Grade: ", then the sum of the numerical grades.
6. End each student's record with a double newline

Name: Park, John
Email: park@umbc.edu
Grade for Problem #1: 17  Really bad.
Grade for E.C. Problem: 5
Final Grade: 22

Name: Doe, Jane
Email: doe2@umbc.edu
Grade for Problem #1: 100  Well done!
Grade for E.C. Problem: 0  Why didn't you do this?
Final Grade: 100

Name: Smith, Bob
Email: smith9999@gmail.com
Grade for Problem #1: 0  Not done.
Grade for E.C. Problem: 0  Not done.
Final Grade: 0

A few additional remarks and hints:
The input file is guaranteed to be properly formatted, i.e. you don't have to do any error checking, like making sure every line has the correct number of fields, that the grade field is numerical, etc. You also don't have to check for quoted strings, like we did in the in-class example. The whole program should be about 20-25 lines. Keep it simple, and don't try to abuse Perl's many shortcuts. To help you get started, here's a link to the code I wrote during lecture last week to parse quoted strings in tab-separated files similar to the ones for this homework: hw7_perl_example.pl. Also, the short sample file from above is available here: hw7_perl_input.txt

You should name your Perl script "hw7_perl.pl", and submit that file.

Extra Credit: Tricky Lisp (10)

Write a function called 'reverse-tree that will invert an entire list, recursively reversing any sublists. Some examples:

;; A simple list:
(reverse-tree '(A B C))
'(C B A)

;; A nested list:
(reverse-tree '(A (X Y Z) B C))
'(C B (Z Y X) A)

;; And the most complex example:
(reverse-tree '(A B (P Q R (X Y Z) (1 2 3) ()) D E (((F) G) H)))
'((H (G (F))) E D (() (3 2 1) (Z Y X) R Q P) B A)

Note that you cannot just define 'reverse-tree to be another name for 'reverse: that function only operates on the top level list, and not on sublists. However, 'reverse would be a useful helper function to call from inside your function.

Sound simple enough? Here's the catch: I'm adding a few extra restrictions to make it more interesting. First, you can only define the one function -- 'reverse-tree; furthermore, you cannot use the 'lambda special form inside. Second, you can only use the following small set of functions:

• reverse
• map
• if
• cond
• list?
• null?

To submit the extra credit problem, just add the function definition for 'reverse-tree to the end of the file "hw7.ss" you are already submitting.

Testing your code

We will provide a file hw7test.ss that you can use to test your code. Put this file in the same directory as your hw7.ss file on gl and then call the following:

mzscheme -f hw7test.ss

What to hand in

Start with the stub file hw7stub.ss. Rename this to hw7.ss and edit it to include your answers to problems 1-3 and the code for problem 4. Submit the file hw7.ss to the submit directory on gl. (If you are doing the extra credit, that function should also be put into this file).

For problem #5, separately submit hw7_perl.pl. Note that that file is due 48 later than the rest of the assignment.