alpha_rename.rkt

#lang racket

#|
let app = 5;;
let app = 2;;
let z = 3;;
let z = 2;;
let app = 3 in app + z;;
app * z
|#

(define example
  '(let ([app 5])
     (let ([app 2])
       (let ([z 3])
         (let ([z 2])
           (let ([app 3])
             (+ app z))
           (* app z))))))

;; Rename different bindings to different names
(define (α-rename e)

  ;; Keep track of identifiers that are seen at a binding position at least once
  (define seen-binders (mutable-set))

  ;; Map each binder to a unique name.
  ;; If it's the first time, keep the same name to minimize ugliness
  (define (gen-binding! x)
    (cond [(set-member? seen-binders x) (gensym x)]
          [else
           (set-add! seen-binders x)
           x]))

  ;; Rename binders in expression
  (define (go e m)
    (match e
      [`(let ([,x ,e_x]) ,es ...)
       (define x* (gen-binding! x))
       (define e_x* (go e_x m))
       (define es*
         ;; Recursively rename body with extended "environment" `m`
         (let ([m* (hash-set m x x*)])
           (for/list ([e es])
             (go e m*))))
       `(let ([,x* ,e_x*]) ,@es*)]
      [(or '+ '- '* '/ (? number?)) e]
      [(? symbol? x)
       (hash-ref m x)]
      [(list es ...)
       (for/list ([e es])
         (go e m))]))

  (go e (hash)))

(α-rename example)
;; ==>
;; (let ((app 5))
;;   (let ((app340641 2))
;;     (let ((z 3))
;;       (let ((z340642 2))
;;         (let ((app340643 3)) (+ app340643 z340642))
;;         (* app340641 z340642)))))