Scheme Finger Exercises - CS451-HW1

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

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