CS 451  ---  Fall 2002  ---  Assignment One


		       SCHEME FINGER EXERCISES


 1. Write LOOKUP-CODE which takes a target symbol, an sexpr to be
    searched, and a dummy inner expression, and returns a hunk of code
    (ie an s-expression) with CAR's and CDR's that would fetch the
    given target symbol out of the given sexpr, with the dummy inner
    expression used as the source of the sexpr.  If the target symbol
    is not found in the sexpr to be searched, LOOKUP-CODE returns #f.
    If the target appears more than once, the first (as printed) is
    the one to find.

    Examples

	(lookup-code 'd '(a (b c (d e) f g) h) 'xxx)
	  ;; -> (car (car (cdr (cdr (car (cdr xxx))))))

	(lookup-code 'j '(a (b c (d e) f g) h) 'xxx)
	  ;; -> #f

	(lookup-code 'b '(a b c) '(map z g))
	  ;; -> (car (cdr (map z g)))

	(lookup-code 'b 'a '(map a b))
	  ;; -> #f

	(lookup-code 'b 'b '(map z g))
	  ;; -> (map z g)

	(lookup-code 'b 'b 'q)
	  ;; -> q



 2. Write REPEAT-TO-FIXEDPOINT which takes a function and an initial
    value and applies the function repeatedly to its own output until
    the value settles down (ie stops changing) and returns that value.

	(repeat-to-fixedpoint (lambda (x)
				(if (> x 1) (- x 1) x))
			      952.3)
	  ;; -> 0.3

	(repeat-to-fixedpoint (lambda (x)
				(/ (+ x (/ 10 x)) 2))
			      1.0)
	  ;; -> 3.16227766016838

	(repeat-to-fixedpoint (lambda (x)
				(cond ((pair? x) (car x))
				      ((number? x) 'num)
				      ((symbol? x) 'sym)
				      (else 'atom)))
			      '((((1) 2) 3) 4))
	  ;; -> sym

	(repeat-to-fixedpoint (lambda (x) x) 'blorg)
	  ;; -> blorg

	(repeat-to-fixedpoint (lambda (x) (if (pair? x) (car x) x))
			      '(((((a b) c) d) e f g) h))
	  ;; -> a


 3. Write CYCLES which takes a directed graph, whose vertices are
    symbols, represented as a list of edges, and returns a list of all
    vertices that are in some cycle.

	(cycles '((a b) (b c) (c d) (d e) (e c) (e f)))
	  ;; -> (c d e)

	(cycles '((a b) (b c) (c c) (c d) (d e) (e e) (e f)))
	  ;; -> (e c)

	(cycles '((a b) (b c) (c d) (d e) (e f)))
	  ;; -> ()


 4. Write ASSOCIATOR which takes an association list and returns a
    function which, when passed a value, looks that value up in the
    association list and returns the associated value, or if the value
    is not found returns #f.

	(let ((a (associator '((one two) (two four) (three eight)))))
	  (list (a 'two) (a 'zero) (a 1) (a 'three) (a a)))
	  ;; -> (four #f #f eight #f)



 5. Find something interesting in the R5RS manual, some unexpected
    generalization or useful special form or other aspect of the
    language of which you were previously unaware, and describe it and
    why you found it interesting.  This will be graded on how
    interesting we find your answer.  Eg, the fact that (+) returns 0
    while (*) returns 1 would be reasonably lame, because I used to
    describe it in the first week of 257.  The fact that
    (string-append) returns "", because strings under the append
    operation form a semi-group whose identity element is the empty
    string, would be a little better.


----------------------------------------------------------------

Due: before class Wed 4-Sep-2002.

Please comment reasonably.  Points for readability and conciseness.

Hand your code in by running the script
 ~bap/bin/hw-handin your-cs451-f2002-hw1.scm
on a CS machine.  It will generate a time stamp which you should save.

Please follow the above; do not email your assignment as an attachment
to one of the instructors' personal email addresses.