On Scheme

Thoughts on Scheme and teaching Scheme

Archive for March 9th, 2006

Incomplete Function Calls 2: Implementation Notes

Posted by Peter on March 9, 2006

As promised I will give a brief description of how the ic-call macro was written. (short answer: by hitting keys on a keyboard).
When I first thought of the problem I initially rejected it as being impossible in Scheme. However, because I am coming to love Scheme more and more, I went back to the problem, after all who wants to admit that their favorite language may be imperfect? First I wrote cases dealing with a fixed function and parameters and wrote various statements that would generate a new function. After a few of these I was able to figure out a pattern. Once I had the necessary pattern I wrote normal functions, not macros, which took the appropriate lists (i.e. simulated parameters) and transformed them into the desired patterns. Functions are much easier to try out an idea for a macro with, because they are much easier to debug, and you can see their output directly, not just its effects. The next step was then to put these functions into a macro with a letrec statement. After a few more tests I added the genyms to avoid variable capture, and the macro was basically done. The macro, with a bug fix since last time, as well as comments is as follows:

(define-syntax ic-call
    (lambda (x)
      (letrec (
               (caddadr
                (lambda (x)
                  (car (cdr (cdr (car (cdr x)))))))
               (cadadr
                (lambda (x)
                  (car (cdr (car (cdr x))))))
               (caadr
                (lambda (x)
                  (car (car (cdr x)))))
               ;we do the majority of the work here
               ;we are buiding a statement in the form (((symbol expr)* ) (lambda (params) (function params-and-lets)
               (gen-let-and-lambda
                (lambda (params existing)
                  (cond ((null? params) existing)   ;if there are no more paremeters we are done
                         ; the case where the parameter is X:
                         ; we need to add a new symbol to the params and to the arguments
                         ; passed to the function
                        ((eq? (car params) 'X)
                           (let ((t-sym (gensym)))
                             (gen-let-and-lambda (cdr params)
                                                 (cons (car existing)
                                                       (list (list (caadr existing)
                                                                   (append (cadadr existing) (list t-sym))
                                                                   (append (caddadr existing) (list t-sym))))))))
                         ; case where the parameter is not X
                         ; we add a new item to the values let defines, and append that symbol
                         ; to the arguments passed to the function.
                        (else (let ((t-sym (gensym))) 
                                (gen-let-and-lambda (cdr params) 
                                                    (cons (append (car existing) (list (list t-sym (car params))))
                                                          (list (list (caadr existing)
                                                                      (cadadr existing)
                                                                      (append (caddadr existing) (list t-sym))))))))
                        )))
               ; this function is basically a wrapper arround gen-let-and-lambda that
               ; provides the correct starting parameters, as well as prepending a let onto the results
               (p-c-transformer
                (lambda (statement)
                  ; we are assigning the function itself to a gensym
                  ; in case the "function" is actually an expression returning a function
                  (let ((f-syms (gensym)))
                    (cons 'let
                          (gen-let-and-lambda (cdr statement) `(((,f-syms ,(car statement))) (lambda () (,f-syms))))))))
               )
        ; the results of all our hard work
       (datum->syntax-object (syntax k) (p-c-transformer (cdr (syntax-object->datum x)))))))

Note that if we could use destructuring-bind from common lisp this macro would be much shorter. (see following)

(define-syntax ic-call
    (lambda (x)
      (letrec (
               (gen-let-and-lambda
                (lambda (params existing)
                  (cond ((null? params) existing)
                        ((eq? (car params) 'X)
                           (let ((t-sym (gensym)))
                             (destructuring-bind
                              (lets (l p body)) existing
                              (gen-let-and-lambda (cdr params) 
                                                  `(,lets (,l ,(append p (list t-sym)) ,(append body (list t-sym))))))))
                        (else (let ((t-sym (gensym)))
                                (destructuring-bind
                                 (lets (l p body)) existing
                                 (gen-let-and-lambda
                                  (cdr params) 
                                  `(,(append lets (list (list t-sym (car params)))) 
                                     (,l ,p ,(append body (list t-sym))))))))
                        )))
               (p-c-transformer
                (lambda (statement)
                  (let ((f-syms (gensym)))
                    (cons 'let
                          (gen-let-and-lambda (cdr statement) `(((,f-syms ,(car statement))) (lambda () (,f-syms))))))))
               )

My own homebrew solution for destructuring-bind in scheme and my difficulty getting it to work in another macro will be covered next time, so stay tuned.

Posted in Exploring Scheme | Leave a Comment »

 
Follow

Get every new post delivered to your Inbox.