How can I programmatically expand the "let" family of functions?

Hello! I am using Racket in a course at my university and I've found it quite enjoyable.

I am working on an assignment where the use of let and let* is limited so as to encourage good functional style. While I understand the motivation, this sent me down a rabbit hole of trying to find a way to write my code using let and let* and writing a program to automatically expand it to use lambda instead.

I posted my question on StackOverflow (linked below), but I'll include the contents here as well.

Any advice would be much appreciated (:


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

  • Sylwester's answer to Not able to use let in Racket discusses the expansion of let and letrec but does so by hand.
  • Alex Knauth's answer to When to use define and when to use let in racket includes a helpful discussion of the scopes of let, let*, and letrec.
  • Partial expansion of code in scheme is honestly pretty close to what I am looking for, but I will point out a few differences
    • I don't need to evaluate the code, simply expand what I consider to be "syntactic sugar" in this context

    • The question requires #lang scheme, but this question uses #lang racket

    • A comment refers the OP to Racket's Sandboxed Evaluation but I am not sure that is what I am looking for (advice is appreciated). It seems like this is used to provide some control over how code is evaluated, but what I am looking for is not control over evaluation. It is about expanding functions used for local bindings when they can be rewritten using lambda.

    • The answer links to expand and this seems to get me closer (maybe?) but I am struggling to find a way forward.

      > (syntax-e (expand '(let ([x 1] [y 2]) (+ x y))))
      '(#<syntax:/Applications/Racket v8.11.1/collects/racket/private/qq-and-or.rkt:193:51 let-values>
        #<syntax (((x) (quote 1)) ((y) (quote 2)))>
        #<syntax:/Applications/Racket v8.11.1/collects/racket/private/kw.rkt:1263:25 (#%app + x y)>)

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))
    [(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)))))]
     (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)
> (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)))

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

Edit #1: Edited to add more links; I was originally restricted as a new user.
Edit #2: Updated the quoted text from the StackOverflow question.

It depends on what exactly you’re trying to do; “expanding the let family of forms” isn’t specific enough. In what language (by that, I mean the limited one that you actually use, not the full Racket) are you trying to define let and friends as derived forms (“syntactic sugars”), for example?

Anyway, I think the ultimate answer is Redex, which is a very useful tool to do language experiment, but it is relatively complex. Another way to do so is to define a function like you will a macro, because macros are just compile-time functions! Again, it depends on which object language (the one in which the “expansion” happens) and which metalanguage (the one with which the “expansion” is done) you have in mind.

1 Like

Just as a quick example, let’s see how to do it in an object language with naturals numbers, the usual lambda-calculus constructs (variables, abstractions, and applications), and let forms:

#lang racket/base
(require redex/reduction-semantics)

(define-language Lambda-Let
  (e ::=
     natural                    ; natural numbers
     x                          ; variables
     (lambda (x ...) e)         ; abstractions
     (let ([x e] ...) e)        ; `let` forms
     (e e ...))                 ; applications
  (x ::= variable-not-otherwise-mentioned))

(define-metafunction Lambda-Let
  let->lambda : e -> e
  [(let->lambda (lambda (x ...) e_body))
   (lambda (x ...) (let->lambda e_body))]
  [(let->lambda (let ([x e] ...) e_body))
   (let->lambda ((lambda (x ...) e_body) e ...))]
  [(let->lambda (e ...))
   ((let->lambda e) ...)]
  [(let->lambda e)

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

The metafunction (i.e., function on terms) is automagically defined according to the object language, which is why Redex is so useful.

Edit: Make it recursive.

1 Like

First of all, thank you so much for your answer.

Honestly, I don't think I really know what I am trying to do because Racket is so new to me. I just noticed how let, let*, and letrec (the functions in the let family of forms that I have actually used so far) can be rewritten with lambdas instead, and I was wondering if I could do that expansion programmatically. I am probably not understanding your question here so let me know if I missed anything.

I will have to look into this. Thank you!

Just hopping back in to say your example looks amazing and works like magic. I will go through the documentation to try to understand this a little better.

On Mar 19, 2024, at 10:41 PM, Joshua Shew via Racket Discourse wrote that he has "an assignment where we are discouraged from overuse of let, let*, and similar functions to `think functionally’. “

  1. I frankly don’t understand what it means to consider let or let* as “not functional.” Every functional language — Haskell, OCaml, Erlang, … — has such language constructs. This phrase “think functionally” is either out of context or the person who posed the exercise is plainly unfamiliar with functional programming (languages).

  2. Your “expansion” of let is wrong. It should be

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

;; is equivalent to 

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

I am playing with indentation here to show how the function parameters of lambda are once again lined up with their initial (and only) values.

  1. If you want something like this equivalence for let*, try this:
(let* ([x 1]) (+ x 2))

;; is equivalent to 

(let ([x 1]) (+ x 2))


(let*  ([x 1] [y (+ x 1]) (* x y))

;; is equivalent to 

(let ([x 1]) (let* ([y (+ x 1)]) (* x y))

That is, let* is best understood as a recursive notational definition (syntactic sugar).

  1. Are you asking about define-syntax or other ways to program these things inside of Racket?

@EmEf Thank you for your response!

(1) I understand that let is not "less functional" than lambda. My understanding that this requirement was in place to get us out of the imperative style of thinking.

var x = 1;
var y = x + 1;
<more code>
(let* ([x 1] [y (+ x 1)]) <more code>)

At this point, I am pursuing this as a learning exercise, not for reasons related to the assignment.

(2) Thank you for pointing that out! The member of StackOveflow also pointed out that mistake for me and I corrected it in my question. I forgot to do that here but I'll edit the original post to do that now.

(3) Thank you for pointing that out. Is there a similar way of understanding letrec?

(4) Any way to do this inside Racket is good. I don't have a lot of constraints on the solution.

Suppose that Racket didn't have let and let* then you can define them using macros.
Simple macros can be written using rewrite rules.
More advanced macros allow arbitrary transformations.
Luckily, for a simple implementation of let and let* we only need simple macros.

#lang racket

(define-syntax-rule (mylet ([id expr] ...) body ...)
  ((λ (id ...) body ...) expr ...))

(define-syntax mylet*
  (syntax-rules ()
    [(mylet* ()                         body ...)   ((λ() body ...))]
    [(mylet* ([id expr])                body ...)   (mylet ([id expr]) body ...)]
    [(mylet* ([id0 expr0] [id expr]...) body ...)   (mylet ([id0 expr0])
                                                           (mylet* ([id expr] ...) body ...))]))
(mylet  ([x 1] [y 2])        (+ x y))    
(mylet* ([x 1] [y (+ x 10)]) (+ x y))

(syntax->datum (expand #'(mylet  ([x 1] [y 2]) (+ x y))))
(syntax->datum (expand #'(mylet* ([x 1] [y (+ x 10)]) (+ x y))))

Try running the snippet in DrRacket.

What the simple macros above doesn't handle is error reporting.
If the user writes (mylet ([x 1] [x 2]) (+ x 3)) then proper error reporting phrases the error in terms of mylet and not the constructs, that mylet expands to. But that's a topic for another day.

1 Like
  1. Hmph.
int y = x + 1;
.. more code ..

is functional code unless more code contains assignments to x or y. Even C++ distinguishes initialization of variables from assignment. (And the meaning of those two is quite different, which is why people spend oodles of time explaining = in C++ — if they teach it properly — meta-if this is possible.)

  1. Yes.
(letrec ([f (lambda (x) (f x))]) (f 1))

;; is equivalent to

[(Y (lambda (f) (lambda (x) (f x)))) 1]

(using [ … ] only to distinguish the outer application from the inner one).

Y is a funny function. It’s called “fix pointed operator”.

If mutual recursion is needed, the abbreviation is more complicated. See

But really don’t use letrec, use `define.

  1. Easy:
(define-syntax (my-let stx)
(syntax-case stx ()
[(_ ([x rhs] …) body …) #’((lambda (x …) body …) rhs …)]))
1 Like

Got it. So to expand on your comment and making sure I understand it, the following is not strictly functional...

int x = 1;
int y = 2;
x = x + y;

...and my instructor probably wanted to avoid the following constructions.

> (let* ([x 1] [y 2] [x (+ x y)]) x)

Yes, x = x + y imperatively updates x and thus invalidates what the community has come to agree on as “functional.”

No, (let* ([x 1] [x (+ x 1)]) …) is functional. The two x on the left-hand side of let are distinct identifiers.

This is roughly like this in Java:

int my_method() { 
  int x = 1; 
  if (1 == x) { 
     int x = 2; // <— declares a new x
     return x; 
  return x; 
1 Like

Btw - in exercises where let is disallowed, just use a helper function to get around the restriction.

; solve  a x² + bx + c = 0

(define (solve a b c)
  (solve-helper a b c 
                (- (* b b) (* 4 a c))))  ; d=b²-4ac

(define (solve-helper a b c d)  
    [(< d 0) '()]
    [(= d 0) (list (/ b (* -2 a)))]
    [(> d 0) (list (/ (- (- b) (sqrt d)) (* 2 a))
                   (/ (+ (- b) (sqrt d)) (* 2 a)))]))

(solve 1 0 -9)
1 Like