How to pass a string as a function name in scheme ? [Dynamic construction of functions names in Scheme]

Question

The problem is the following and it found in http://www.cs.indiana.edu/classes/b551-leak/scheme_practice.html .

Problem definition: Write a function cxr that is a generalization of the car/cdr operators provided in Scheme. cxr should take a string of "a"s and "d"s representing the sequence of car and cdr operations to be performed and return a function capable of performing that sequence.

Thus (cxr "ad") is equivalent to the function cadr.

    ((cxr "ad") '(i ii iii iv v vi vii))  ==> ii
    (define sixth (cxr "addddd"))
    (sixth '(i ii iii iv v vi vii))         ==> vi

My attempt: I converted cxr "ad" into a string "cadr" using string-append. [This is easy] .. Now how can I link between "cadr" with cadr ... I tried the string->symbol, but the output is quoted and whence the function is not executed. -- so is there any way of unquoting ?!

The real question: how to solve this problem ?

---

UPDATE: Thanks all for these answers. They are all correct and I have solved it this way actually before I even post the question. I was mainly looking for a way to actually call caddddr when the input is (cxr adddd) ... Everbody did the same functionality as caddddr but did not actually call cadddr.

That is, how to make functions wit the same naming type as cadr caddr etc.

---

UPDATE: (I think I found the solution and it is as follows - but as it is told below it does not work for longer d's):

(define cxr 
(lambda (ad l)
   ( (eval (string->symbol (string-append "c" ad "r")))   l)
)
)

Answer 1

As Mimisbrunnr points out, the idea here is not to string-append and then eval. For one thing, this won't work for longer sequences of a's and d's.

Instead, you want to write a function that consumes a string and returns a function by analyzing the string character-by-character.

In HtDP parlance, this could be done as structural recursion on a list of "a"s and "d"s, after converting the string to a list.

To make this easier, you can use "string->list". This exists in Racket, and I have a vague sense that it's a part of r5rs as well.

Answer 2

You ask: "Now how can I link between "cadr" with cadr.

First we can link the characters #\a to car and #\d to cdr:

(define (x->cxr x)
  (if (eqv? x #\a) car cdr))

Example:

> ((x->cxr #\a) '(foo bar)) 
'foo

Then use the fact that cadr is the composition of car and cdr (as in cadr is (compose car cdr).

(define (cxr s)
  (apply compose
         (map x->cxr 
              (string->list s))))

Answer 3

Here's a possible implementation, a mini-interpreter for a list of operations to be applied on a given input:

(define (cxr ops)
  (lambda (input)
    (generate-cxr (reverse (string->list ops)) input)))

(define (generate-cxr ops-list acc)
  (if (null? ops-list)
      acc
      (generate-cxr (cdr ops-list) (operate (car ops-list) acc))))

(define (operate op input)
  (cond ((eqv? op #\a) (car input))
        ((eqv? op #\d) (cdr input))
        (else (error "unknown operation" op))))

I divided the problem in three parts:

1. cxr returns a function that, when called, will process its input against the sequence of operations received as a parameter. Notice that the list of operations gets processed in the inverse order in which they were declared
2. generate-cxr processes each operation in turn, until no more operations are left to perform, accumulating the result
3. operate decides which operation to apply and actually performs it, returning the result

The above procedures return a correct answer but it is very inefficient, because the syntactic analysis of operations is interleaved with their execution. It's possible to separate the syntactic analysis from execution, producing a faster solution. See section 4.1.7 in SICP.

Answer 4

EDIT: In response to your update, I think you want to do something like this:

(eval `(define ,<procedure-to-return-symbol> ,<value>) <environment>)

e.g. in mit-scheme:

(eval `(define ,(string->symbol "abc") ,(* 2 2)) user-initial-environment)

Where user-initial-environment is the environment under which symbols are interned when typed into the REPL. This example will return the symbol abc associated with the value 4. Using this method you would be able to use your procedure to create the name and associate it with the value returned by my solution below. You can read more about eval and mit-scheme environments here. </edit>

EDIT2: An explicit solution:

(define (cxr x)
  (define (helper xlist arg)
    (cond ((null? xlist) arg)
          ((eq? (car xlist) #\a) (car (helper (cdr xlist) arg)))
          ((eq? (car xlist) #\d) (cdr (helper (cdr xlist) arg)))
          (else (error "INVALID ARGS FOR CXR"))))
  (eval `(define ,(string->symbol (string-append "c" x "r"))
           ,(lambda (arg) (helper (string->list x) arg))) user-initial-environment))

In this way you can create named procedures for any depth of "ad" strings.</edit>

Your initial solution is at best usable where there are compositions of car and cdr already defined. The problem is looking for a procedure that returns a procedure which takes the car/cdr of a list to an arbitrary depth. This is my solution:

(define (cxr x)
  (define (helper xlist arg)
    (cond ((null? xlist) arg)
          ((eq? (car xlist) #\a) (car (helper (cdr xlist) arg)))
          ((eq? (car xlist) #\d) (cdr (helper (cdr xlist) arg)))
          (else (error "INVALID ARGS FOR CXR"))))
  (lambda (arg) (helper (string->list x) arg)))

helper runs down the list of a's and d's calling the either car or cdr on the result of the next call to helper -- it builds the body for the lambda. When the list is empty, helper returns arg which is the parameter for the lambda expression. Since the lambda form does not have an argument passed to it in the definition, cxr will return a procedure.