My favourite Scheme feature: named `let`
Recently, on Stack Overflow, there was a discussion on what named let was all about, so I thought I'd write a post on the topic.
What's a named let?
So, let's consider a function for merging two sorted lists of numbers (since I felt that factorial or fibonacci were way overused as examples of self-recursive functions):
(define (merge lhs rhs) (cond ((null? lhs) rhs) ((null? rhs) lhs) ((< (car rhs) (car lhs)) (cons (car rhs) (merge lhs (cdr rhs)))) (else (cons (car lhs) (merge (cdr lhs) rhs)))))
This is fine and good, but some people look at this and say, OMG, this isn't tail-recursive, so if given long lists, it'll blow the stack! Okay, fine. Let's write a tail-recursive version:
(define (merge lhs rhs) (define (loop result lhs rhs) (cond ((null? lhs) (append-reverse! result rhs)) ((null? rhs) (append-reverse! result lhs)) ((< (car rhs) (car lhs)) (loop (cons (car rhs) result) lhs (cdr rhs))) (else (loop (cons (car lhs) result) (cdr lhs) rhs)))) (loop '() lhs rhs))
This is also fine, but now you had to write an inner function. And of course, whenever you're creating a function for the express purpose of immediately calling it, guess what the answer is? :-)
(define (merge lhs rhs) (let loop ((result '()) (lhs lhs) (rhs rhs)) (cond ((null? lhs) (append-reverse! result rhs)) ((null? rhs) (append-reverse! result lhs)) ((< (car rhs) (car lhs)) (loop (cons (car rhs) result) lhs (cdr rhs))) (else (loop (cons (car lhs) result) (cdr lhs) rhs)))))
That is what a named let is.
How do you define named let?
Many Scheme implementations implement let as a macro that creates a lambda and calls it, rather than as a built-in.
An unnamed let is easy to implement:
(define-syntax let (syntax-rules () ((let ((id value) ...) body ...) ((lambda (id ...) body ...) value ...))))
A named let is similarly easy; the lambda is simply wrapped in a rec:
(define-syntax let (syntax-rules () ((let tag ((id value) ...) body ...) ((rec tag (lambda (id ...) body ...)) value ...))))
All the rec does here is to give the lambda a name that can be used within the lambda for self-recursive calls.
But what is rec?
rec is a macro that wraps up a letrec (or an internal definition) in a pretty way. You can implement it in terms of either letrec:
(define-syntax rec (syntax-rules () ((rec name value) (letrec ((name value)) name))))
or an internal definition:
(define-syntax rec (syntax-rules () ((rec name value) (let () (define name value) name))))
In fact, in Scheme implementations where letrec is implemented as a macro on top of internal definitions (or the other way around), the two may well expand to identical code.
rec also provides syntactic sugar for defining a recursive function, much like define does:
(define-syntax rec (syntax-rules () ((rec (name . args) body ...) (rec name (lambda args body ...)))))
Putting it all together
(define-syntax rec (syntax-rules () ((rec (name . args) body ...) (rec name (lambda args body ...))) ((rec name value) (letrec ((name value)) name)))) (define-syntax let (syntax-rules () ((let ((id value) ...) body ...) ((lambda (id ...) body ...) value ...)) ((let tag ((id value) ...) body ...) ((rec (tag id ...) body ...) value ...))))