ledit uscheme

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

14. Higher-order functions. Do Exercise 14 on page 209 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 defined is in the initial basis, 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 210. 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 212 of Ramsey. You cannot represent these sets using lists. If any part of your code to construct or to interrogate a set 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. When set-ops-from is given an equality predicate, it returns a list of six values. Each value in this list is an operation that either constructs or interrogates a set made with the given equality predicate. Each operation is like the ones you wrote in part (c), except now they are coded using the third approach to polymorphism.

  Your set-ops-from might look like this

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

  Although you may write set-ops-from however you like—for example by copying the code above and replacing each ... with your own code—it must return a list whose contents are in the order shown above. If a submission’s set-ops-from returns anything else, we cannot grade its functional correctness.

(check-assert (procedure? set-ops-from))
(check-expect (length (set-ops-from =)) 6)

(val atom-set-ops (set-ops-from =))
(val nullset      (car atom-set-ops))
(val member?      (cadr atom-set-ops))
(val add-element  (caddr atom-set-ops))
(val union        (car (cdddr atom-set-ops)))
(val inter        (cadr (cdddr atom-set-ops)))
(val diff         (caddr (cdddr atom-set-ops)))

A. Good functional style. The Impcore-with-locals function

    (define f-imperative (y) (locals x)
      (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 107, 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.

    (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)))