Scheme Finger Exercises - CS451-HW1

Write Scheme functions to do each of the following. They should not use any side effects, should be properly commented and indented, etc. Your filename should have the extension .scm, for our convenience as well as your own. (10 points each.)

In the ``examples'' below, return values are shown in comments following sample invocations.

  1. Define bi-skip, which takes two lists, the first list consisting of non-negative integers. It returns elements of the second list with gaps removed from the sequence of length corresponding to sequential elements of the first list. For behaviour after the second list (the list of numbers) is exhausted, see below. It is an error for the second list to be exhausted before the first (ie you don't have to worry about that case.)

    Examples:

    (bi-skip '(0 2 3 1) '(a b c d e f g h i j k l m n o p))
      ; (a d h j k l m n o p)
    (bi-skip '() '(a b c d e f g h i j k l m n o p))
      ; (a b c d e f g h i j k l m n o p)
    (bi-skip '(3) '(a b c d e f g h i j k l m n o p))
      ; (d e f g h i j k l m n o p)
    (bi-skip '(1 1 1 1 1 1 1 1) '(a b c d e f g h i j k l m n o p))
      ; (b d f h j l n p)
    
  2. Define a higher-order function curry-skip with the following property:
    ((curry-skip 0) 'foo)               ; foo
    (((curry-skip 1) 'foo) 'bar)        ; bar
    ((((curry-skip 2) 'foo) 'bar) 'baz) ; baz
    
  3. Define tr?, which tests if all calls to (ie direct invocations of as a function, using the original name ie without rebinding) a particular variable in a hunk of scheme code are in tail-recursive position. It takes two arguments, the first a symbol and the second an s-expr representing a hunk of scheme code. The scheme code will be very stereotyped: it can contain only function calls, numeric constants, variables, and the special forms if, let, and quote. Note in particular the absence of lambda from this list.

    Examples:

    (tr? 'foo 0)                                ; #T (vacuously)
    (tr? 'foo '(+ 1 3))                         ; #T
    (tr? 'foo '(foo 2))                         ; #T
    (tr? 'foo '(bar 1 (foo 3)))                 ; #F
    (tr? 'bar '(bar 1 (foo 3)))                 ; #T
    (tr? 'foo '(if (bar) (foo) (baz)))          ; #T
    (tr? 'baz '(if (bar) (foo) (baz)))          ; #T
    (tr? 'bar '(if (bar) (foo) (baz)))          ; #F
    (tr? 'foo '(foo (let ((foo bar)) (+ 1 (foo x))))) ; #T
    (tr? 'foo '(+ 1 (if x (foo) (bar))))        ; #F
    
    (If you need to refresh your memory of the concept of tail recusion, look under tail recursion in the index to the Scheme manual by Dybvig, available online in the reference materials portion of the CS451 web pages. A web search also leads to a nice explanation, a page from the R5RS manual. In general, I will expect everyone in the class to be professional: to program with a language manual by their side, to look things up on their own initiative, to skim relevant reference materials as a matter of habit.)
Due fifteen minutes before class: 3:45pm, Wed Aug 29.

We will take off as many points for a 23-hour-late assignment as for a 24-second late one, so please don't skip class to work on it.

Turn in your code by running

 ~bap/bin/handin your-file.scm
on a regular UNM CS machine. (You should use whatever filename is appropriate in place of your-file.scm. You can put multiple files on the command line, or even directories. Directories will have their entire contents handed in, so please be careful with them, and in particular be sure to clean out any cruft.)
Barak Pearlmutter <bap@cs.unm.edu>