Sunday, May 16, 2010

The Light Bulb Is Not Yet On

I have reset on going through Essentials of Programming Languages, and struggling my way through learning Scheme. I wrote a working answer (at least as tested) for a problem in the second chapter, but I feel like I happened upon it through test-driven development. I suppose in some ways that's a good thing, but I can say that it is not a terribly comfortable feeling to write some code but not really grok what it's doing. Anyway, here is the paraphrased problem, and my solution (test cases included):

Exercise 2.2.9, #3. (car&cdr2 s slst errvalue) generates a procedure composition that, when evaluated, produces the code for a procedure that takes a list with the same structure as slst and returns the value in the same position as the leftmost occurrence of s in slst. If s does not occur in slst, then errvalue is returned.

(define (contains? s los)
(if (null? los)
#f
(if (symbol? (car los))
(if (eq? s (car los))
#t
(contains? s (cdr los)))
(if (contains? s (car los))
#t
(contains? s (cdr los))))))

(define (car&cdr2 s slst errvalue)
(if (contains? s slst)
(car&cdr2-help s slst 'car)
errvalue))

(define (car&cdr2-help s slst lst)
(if (symbol? (car slst))
(if (eq? s (car slst))
lst
(list 'compose lst (car&cdr2-help s (cdr slst) 'cdr)))
(if (contains? s (car slst))
(list 'compose 'car (car&cdr2-help s (car slst) 'cdr))
(list 'compose lst (car&cdr2-help s (cdr slst) 'cdr)))))


Here are the tests (schemeunit):
(define-test-suite 2.2.9
(test-case "3."
(check equal?
(car&cdr2 'a '() 'fail)
'fail)
(check equal?
(car&cdr2 'a '(a) 'fail)
'car)
(check equal?
(car&cdr2 'a '(b) 'fail)
'fail)
(check equal?
(car&cdr2 'a '(a b) 'fail)
'car)
(check equal?
(car&cdr2 'b '(a b) 'fail)
'(compose car cdr))
(check equal?
(car&cdr2 'c '(a b c) 'fail)
'(compose car (compose cdr cdr)))
(check equal?
(car&cdr2 'd '(a (b c) d) 'fail)
'(compose car (compose cdr cdr)))
(check equal?
(car&cdr2 'dog '(cat lion (fish dog) pig) 'fail)
'(compose car (compose cdr (compose car (compose cdr cdr)))))
(check equal?
(car&cdr2 'c '((a b) c) 'fail)
'(compose car cdr))))

Any Schemers care to give me pointers? I sure could use the help.

2 comments:

  1. First off let me admit that I don't know EOPL the way I do, say, SICP or even HtDP. Thus, there may be aspects of what they're trying to do that aren't as clear to me as they would be. Still, I think I do see some things you've missed.

    I will add that you do seem to have missed at least some of the purpose of the exercise, which is to return an actual function, or at least the code for a function.I do find it a little unusual that they've requested you to return the code for a function rather than the new function itself, but it isn't all that out of the ordinary. Generating code like this is a typical Lisp-ish solution for several kinds of problems, though as I said, it would be more common to return a lambda for a simple function-generator like this. Still, even if they want code, you'd probably want to modify it to return a whole function, not just the body, something like so:

    (define (car&cdr2 s slst errvalue)
    (if (contains? s slst)
    (list 'lambda '(x) (car&cdr2-help s slst 'car))
    errvalue))

    This should make it fairly easy to use (eval) to get the actual function.

    I also think that the authors were being deliberately obscure with the name of the function, because this is something which could have an actual, general use for working with certain data structures. A better name for it might be make-accessor-by-pattern, because that's what it does - it takes some pattern and a part of that pattern, and returns a function to extract the same member in other structures of the same type. Imagine, for example, a data structure whose form was

    ((first-name last-name) (street-address unit city state country postal-code) (position-1 position-2...)))

    You could manually write a series of accessors for this structure, to help abstract it away, but what if the structure had dozens of fields? Well, this function automates that: by passing it the pattern list above, and the name of a field such as, say, last-name, you could automatically generate a getter for that field. Better still, this could generate ones for groups of fields, b matching, say, '(street-address unit city state country postal-code) as a whole.

    At least, that is my impression of what it might be used for. I have no idea if that was the authors' intent or not.

    I don't know if this helps or not; I'll look at the code in more depth tonight.

    ReplyDelete
  2. I take back part of what I'd said earlier; assuming that your (compose) function is something like this:

    (define (compose f g)
    (lambda (x)
    (f (g x))))

    then the return from that will already be a procedure, so you wouldn't need the extra (lambda) part in (car&cdr2-help). You would produce and call the actual running function something like this:

    (define get-second (eval (car&cdr2 'a '(b a) 'fail)))

    (get-second '(a b))

    Also, I 'simplified' your code (though perhaps at the expense of readability) by nesting (contains?) into (car&cdr2) and using a named let for (car&cdr2-help):

    (define (car&cdr2 s slst errvalue)
    (define (contains? s los)
    (if (null? los)
    #f
    (if (symbol? (car los))
    (if (eq? s (car los))
    #t
    (contains? s (cdr los)))
    (if (contains? s (car los))
    #t
    (contains? s (cdr los))))))

    (if (contains? s slst)
    (let iterate-list ((slst slst)
    (lst 'car))
    (if (symbol? (car slst))
    (if (eq? s (car slst))
    lst
    (list 'compose lst (iterate-list (cdr slst) 'cdr)))
    (if (contains? s (car slst))
    (list 'compose 'car (iterate-list (car slst) 'cdr))
    (list 'compose lst (iterate-list (cdr slst) 'cdr)))));)
    errvalue))

    I don't know if you've run across either of these idioms before, so I figured I show them to you.

    BTW, Blogger doesn't seem to support bbcode, and the HTML equivalent tags are disabled. How do you format code here?

    ReplyDelete