schemeracketlet

How to programmatically expand the let* family of functions in racket

Context

This question is tangentially related to a homework assignment, but I am not looking to have someone do my work for me.

I have an assignment where we are discouraged from overuse of let, let*, and similar functions to encourage us to "think functionally".

I also understand that expressions using let can be expanded to only use lambda in the following manner.

#lang racket

; using let
(let ([x 1] [y 2]) (+ x y))

; with lambda
((lambda (x y) (+ x y)) 1 2)

Looking at this caused me to ask the following question.

The Question

Is there some way to accomplish this expansion programmatically? The only part that should be modified are those using let, let*, and so on.

> (expand-let '(let ([x 1] [y 2]) (+ x y)))
'((lambda (x y) (+ x y)) 1 2)

It would be cool if this could apply to all "local binding" Racket functions: let, let*, letrec, let-values, let*-values, letrec-values, and so on.

As pointed out in the comments, this doesn't really serve any practical purpose for my assignment, but I am still looking into it as a personal project as I am new to Racket. Any advice is appreciated.

What I've tried

Coding it myself (not a complete solution)

I attempted my own solution as a beginner and got stuck. Any advice is appreciated.

(define (expand-let atomized-expr)
  (expand-let-helper (syntax->datum (expand atomized-expr)) (lambda (result) result)))
(define (expand-let-helper parse-tree return)
  (define (expand-let-bindings bindings)
    (map (lambda (binding) (list (caar binding) (expand-let (cadr binding)))) bindings))
  (cond
    [(null? parse-tree) (return '())]
    [(not (pair? parse-tree)) (return parse-tree)]
    [(eq? (car parse-tree) '#%app)
     (expand-let-helper (cdr parse-tree) (lambda (result) (return result)))]
    [(eq? (car parse-tree) '#%top) (return (cdr parse-tree))]
    [(eq? (car parse-tree) 'let-values)
     (let* ([bindings (cadr parse-tree)]
            [body (cddr parse-tree)]
            [expanded-bindings (expand-let-bindings bindings)]
            [vars (map car expanded-bindings)]
            [vals (map cadr expanded-bindings)])
       (expand-let-helper body
                          (lambda (result)
                            (return `((lambda (,@vars) ,@result) ,@vals)))))]
    [else
     (expand-let-helper (cdr parse-tree)
                        (lambda (cdr-result)
                          (expand-let-helper (car parse-tree)
                                             (lambda (car-result)
                                               (return (cons car-result cdr-result))))))]))

See results here:

; successful case
> ((lambda (x y) (let ((a (+ x y)) (b (- x y))) (* a b))) 1 2)
-3
> (expand-let '((lambda (x y) (let ((a (+ x y)) (b (- x y))) (* a b))) 1 2))
'((lambda (x y) ((lambda (a b) (* a b)) (+ x y) (- x y))) '1 '2)
> (eval (expand-let '((lambda (x y) (let ((a (+ x y)) (b (- x y))) (* a b))) 1 2)))
-3

; failing cases (pointed out in comments)
> (expand-let '(let ([n (random -10 10)]) (cond [(positive? n) 1] [(negative? n) -1] [else 0])))
'((lambda (n) (if (positive? n) '1 (if (negative? n) '-1 '0)))
  (random '-10 '10))
Solution

  • The short answer is that not even Racket's syntax expander could do this properly without significant effort. When the transformer encounters (let ...), it needs to determine if let is a macro or a variable bound by an enclosing expression.

    > ((lambda (let) (+ let 1)) 1)
2

    So the transformer needs to track the local environment and know details about the #lang in use and any modules required at the top level.

    Assuming a particular instance of (let ([id value-expr] ...) body ...) is determined to be a macro, the transformer must transform it into a lambda expression and application and also recursively transform sub-expressions, but only the value expressions and body expressions. It would be an error to treat [id value-expr] as a procedure application, for example. In other words, the transformer must understand the semantics of the macros it encounters.

    That goes for custom macros, too. Suppose you encounter the following code.

    (define-syntax my-macro some-transformer-procedure)
(my-macro (let ((a 1)) (b 2)))

    You can at least know that (my-macro (let ((a 1)) (b 2))) is a macro invocation. The let-expression looks like a normal let, but you don't know what the macro will transform it into, and thus cannot expand it properly, without understanding the macro's semantics. And the semantics are encapsulated in some-transformer-procedure, which is a black box, and the macro's documentation, which is not machine-readable.

    If you devised a method to specify the semantics of every macro and could ensure that all custom macros provided a complete and correct spec readable by the transformer, then you might have a chance. The fact that macros can define other macros ad infinitum greatly increases the complexity of this hypothetical system.

    Somewhat ironically, these challenges highlight one of the benefits of Racket's macro system. The compiler needs to analyze expressions in a manner similar to what you're attempting. To make its work easier, it uses macros to distill complex constructs down to a handful of core expressions like lambda and if that it can subsequently manipulate according to a set of rules that are guaranteed to preserve correctness. The simpler the expressions are, the simpler and more widely-applicable the rules can be, allowing for powerful optimizations.

    Here's one example using ChezScheme:

    > (print-gensym #f)
> (expand/optimize
   '(lambda (x)
      (let* ([f1 (lambda (lt) (lambda (a b) (lt a b)))]
             [f2 (lambda () (f1 <))])
        ((f2) (+ 1 2) x))))
(lambda (x) (#2%< 3 x))

    As you can see, it was able to simplify the expression quite a bit. (#2%< is a particular implementation of the < procedure that the compiler decided was appropriate.)