ledit uscheme

    /comp/105/bin/uscheme -q < myfilename > /dev/null

14. Higher-order functions. Do Exercise 14 on page 201 of Ramsey, parts (b) to (f), part (h), and part (j). You must not use recursion—solutions using recursion will receive No Credit. This restriction applies only to code you write. For example, gcd, which is in the initial basis, or insert, which is given, may use recursion.

For this problem only, you may define one helper function at top level.

15. Higher-order functions. Do Exercise 15 on page 202. You must not use recursion—solutions using recursion will receive No Credit. As above, this restriction applies only to code you write.

For this problem, you get full credit if your implementations return correct results. You get EXTRA CREDIT¹ if you can duplicate the behavior of exists? and all? exactly. To earn the extra credit, it must be impossible for an adversary to write a μScheme program that produces different output with your version than with a standard version. However, the adversary is not permitted to change the names in the initial basis.

19. Functions as values. Do Exercise 19 on page 204 of Ramsey. You cannot represent these sets using lists. If any part of your code uses cons, car, cdr, or null?, you are doing the problem wrong.

Do all four parts:

• Parts (a) and (b) require no special instructions.

• In part (c), your add-element function must take two parameters: the element to be added as the first parameter and the set as the second parameter.

  Also in part (c), compare values for equality using the equal? function.

• In part (d), when you code the third approach to polymorphism, write a function set-ops-from which places your set functions in a record. Use the syntactic sugar described in the book in Section 2.16.6 on page 183.

  In particular, your submission must include this record definition:

  (record set-ops (empty member? add-element union inter diff))

  Code your solution to part (d) as a function set-ops-from, which will accept one argument (an equality predicate) and will return a record created by calling make-set-ops. Your function might look like this:

  (define set-ops-from (eq?)
    (let ([empty   ...]
          [member? ...]
          [add     ...]
          [union   ...]
          [inter   ...]
          [diff    ...])
      (make-set-ops empty member? add union inter diff)))

  Fill in each ... with your code.

To help you get part (d) right, we recommend that you use these unit tests:

(check-expect (procedure? set-ops-from)   #t)
(check-expect (set-ops? (set-ops-from =)) #t)

And to write your own unit tests for the functions in part (d), you may use these definitions:

(val atom-set-ops (set-ops-from =))
(val nullset      (set-ops-empty atom-set-ops))
(val member?      (set-ops-member? atom-set-ops))
(val add-element  (set-ops-add-element atom-set-ops)) 
(val union        (set-ops-union atom-set-ops))
(val inter        (set-ops-inter atom-set-ops))
(val diff         (set-ops-diff atom-set-ops))

A. Good functional style. The Impcore function

    (define f-imperative (y) (locals x) ; x is a local variable
      (begin 
        (set x e)
        (while (p? x y) 
           (set x (g x y)))
        (h x y)))

is in a typical imperative style, with assignment and looping. Write an equivalent μScheme function f-functional that doesn’t use the imperative features begin (sequencing), while (goto), and set (assignment).

• Assume that p?, g, and h are free variables which refer to externally defined functions.
• Assume that e is an arbitrary expression.
• Use as many helper functions as you like, as long as they are defined using let or letrec and not at top level.

Hint #1: If you have trouble getting started, rewrite while to use if and goto. Now, what is like a goto?

Hint #2: (set x e) binds the value of e to the name x. What other ways do you know of binding the value of an expression to a name?

Don’t be confused about the purpose of this exercise. The exercise is a thought experiment. We don’t want you to write and run code for some particular choice of g, h, p?, e, x, and y. Instead, we want you write a function that works the same as f-imperative given any choice of g, h, p?, e, x, and y. So for example, if f-imperative would loop forever on some inputs, your f-functional must also loop forever on exactly the same inputs.

Once you get your mind twisted in the right way, this exercise should be easy. The point of the exercise is not only to show that you can program without imperative features, but also to help you develop a technique for eliminating such features.

    A --> B --> C
    |           ^
    |           |
    +-----------+

G1. Edge-list representations. A single graph may have many different representations as an edge list. For example, the graph pictured above can be represented by either of the following edge lists:

'((A B) (B C) (A C))
'((A B) (A C) (B C))

Define a function =edge-list? which takes as arguments two edge lists and returns a Boolean indicating whether they represent the same graph. To test your function, choose three different graphs, and use check-expect to demonstrate that your function works on each one.

Hint: You have already written this function, but you know it by another name.

G2. Successors-map representations. A single graph may have many different representations as a successors map. For example, the graph pictured above can be represented by any of the following successors maps:

'((A (B C)) (B (C)) (C ()))
'((A (C B)) (B (C)) (C ()))
'((B (C)) (A (C B)) (C ()))

Define a function =successors-map? which takes as arguments two successors maps and returns a Boolean indicating whether they represent the same graph. To test your function, choose two different graphs, and use check-expect to demonstrate that your function works on each one.

Hint: There are at least two good ways to approach this problem. You can code it directly, or you can generalize the book function =alist? using the third approach to polymorphism. If you use the polymorphic approach, you will find yourself able to reuse more code.

G3. Converting representations.

1. Write function successors-map-of-edge-list, which accepts a graph in edge-list representation and returns a representation of the same graph in successors-map representation.

2. Write function edge-list-of-successors-map, which accepts a graph in successors-map representation and returns a representation of the same graph in edge-list representation. You must assume that in the argument graph, every node has at least one incoming edge or one outgoing edge. Otherwise the graph cannot be represented using an edge list.

Write unit tests for each function. In your unit tests, you may find it convenient to use =edge-list? and =successors-map?.

Hint: By 105 standards, the solution to this problem requires a lot of code. Your new best friend is let*.

M. Reasoning about higher-order functions. Using the calculational techniques from Section 2.4.5, which starts on page 101, prove that

    (o ((curry map) f) ((curry map) g)) == ((curry map) (o f g))

To prove two functions equal, prove that when applied to equal arguments, they return equal results.

Take the following laws as given:

   ((o f g) x) == (f (g x))        ; apply-compose law
   (((curry f) x) y) == (f x y)    ; apply-curried law

Using these laws should keep your proof relatively simple.

O. Ordered lists. I said in class that in most cases, a function that consumes lists uses the obvious inductive structure on lists: a list either empty or is made with cons. Here is a problem that requires a more refined inductive structure.

Define a function ordered-by? that takes one argument—a comparison function that represents a transitive relation—and returns a predicate that tells if a list is totally ordered by that relation. Assuming the comparison function is called precedes?, here is an inductive definition of a list that is ordered by precedes?:

• The empty list is ordered by precedes?.

• A singleton list is ordered by precedes?.

• A list of the form (cons x (cons y zs)) is ordered by precedes? if the following properties hold:

  • x is related to y, which is to say (precedes? x y).

  • List (cons y zs) is totally ordered by precedes?.

Here are some examples. Note the parentheses surrounding the calls to ordered-by?.

-> ((ordered-by? <) '(1 2 3))
#t
-> ((ordered-by? <=) '(1 2 3))
#t
-> ((ordered-by? <) '(3 2 1)) 
#f
-> ((ordered-by? >=) '(3 2 1))
#t
-> ((ordered-by? >=) '(3 3 3))
#t
-> ((ordered-by? =) '(3 3 3)) 
#t

Hints:

• The structure of your function should be informed by the structure of the inductive definition of what it means for a list to be ordered by a relation.

• You will need letrec.

• We recommend that your submission include the following unit tests, which help ensure that your function has the correct name and takes the expected number of parameters.

  (check-expect (procedure? ordered-by?) #t)
  (check-expect (procedure? (ordered-by? <)) #t)
  (check-error (ordered-by? < '(1 2 3)))

    (define sum-upto (n)
      (letrec ([sigma (lambda (m n) ;;; UGLY CODE
                         (if (> m n) 0 (+ m (sigma (+ m 1) n))))])
         (sigma 1 n)))

    (define sum-upto (n)
      (letrec ([sum-from (lambda (m) ;;; BETTER CODE
                         (if (> m n) 0 (+ m (sum-from (+ m 1)))))])
         (sum-from 1)))