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

JShoes1415 · March 20, 2024, 2:31am

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 (:

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

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.

usao · March 20, 2024, 6:02am

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.

usao · March 20, 2024, 6:43am

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

JShoes1415 · March 20, 2024, 1:26pm

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!

JShoes1415 · March 20, 2024, 1:33pm

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.

EmEf · March 20, 2024, 1:37pm

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

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

If you want something like this equivalence for let*, try this:

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

;; is equivalent to 

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

and

(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).

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

JShoes1415 · March 20, 2024, 2:19pm

@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.

soegaard · March 20, 2024, 2:54pm

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.

EmEf · March 20, 2024, 3:04pm

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

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 https://felleisen.org/matthias/BTLS-sample.pdf

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

Easy:

(define-syntax (my-let stx)
(syntax-case stx ()
[(_ ([x rhs] …) body …) #’((lambda (x …) body …) rhs …)]))

JShoes1415 · March 20, 2024, 3:13pm

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;
print(x);

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

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

EmEf · March 20, 2024, 3:43pm

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

soegaard · March 20, 2024, 6:29pm

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

Topic		Replies	Views
How can I redefine defintions in typed racket top level (repl) Questions & Answers question , typed-racket	3	372	July 16, 2022
Provide an example using "eval-syntax" & "syntax" in typed/racket General	7	190	January 26, 2023
Resources for continuations / delimited continuations / racket continuation functionality from a beginner perspective? Questions & Answers	3	362	February 7, 2023
"Getting It" (or, Making It "Click") Questions & Answers question	6	398	May 28, 2022
Create New data types Questions & Answers	6	217	May 9, 2023

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

Context

The Question

What I've tried

Coding it myself (not a complete solution)

Related Topics