16

In an answer which explains how to convert a number to a list the number->list procedure is defined as follows:

(define (number->list n)
  (let loop ((n n)
             (acc '()))
    (if (< n 10)
        (cons n acc)
        (loop (quotient n 10)
              (cons (remainder n 10) acc)))))

Here a "named let" is used. I don't understand how this named let works.

I see that a loop is defined where the variable n is equal to n, and the variable acc equal to the empty list. Then if n is smaller than 10 the n is consed to the acc. Otherwise, "the loop" is applied with n equal to n/10 and acc equal to the cons of the remainder of n/10 and the previous accumulated stuff, and then calls itself.

I don't understand why loop is called loop (what is looping?), how it can automatically execute and call itself, and how it will actually add each number multiplied by its appropriate multiplier to form a number in base 10.

I hope someone can shine his or her light on the procedure and the above questions so I can better understand it. Thanks.

2 Answers 2

21

The basic idea behind a named let is that it allows you to create an internal function, that can call itself, and invoke it automatically. So your code is equivalent to:

(define (number->list n)
  (define (loop n acc)
    (if (< n 10)
        (cons n acc)
        (loop (quotient n 10)
              (cons (remainder n 10) acc))))
  (loop n '()))

Hopefully, that is easier for you to read and understand.

You might, then, ask why people tend to use a named let rather than defining an internal function and invoking it. It's the same rationale people have for using (unnamed) let: it turns a two-step process (define a function and invoke it) into one single, convenient form.


It's called a loop because the function calls itself in tail position. This is known as tail recursion. With tail recursion, the recursive call returns directly to your caller, so there's no need to keep the current call frame around. You can do tail recursion as many times as you like without causing a stack overflow. In that way, it works exactly like a loop.


If you'd like more information about named let and how it works, I wrote a blog post about it. (You don't need to read it to understand this answer, though. It's just there if you're curious.)

1
  • 1
    Thanks again. Great blog post. Aug 14, 2015 at 22:09
9

A normal let usage can be considered an anonymous procedure call:

(let ((a 10) (b 20))
  (+ a b))

;; is the same as 
((lambda (a b)
   (+ a b))
 10
 20)

A named let just binds that procedure to a name in the scope of the procedure so that it is equal to a single procedure letrec:

(let my-chosen-name ((n 10) (acc '()))
  (if (zero? n)
      acc
      (my-chosen-name (- n 1) (cons n acc)))) ; ==> (1 2 3 4 5 6 7 8 9 10)

;; Is the same as:
((letrec ((my-chosen-name 
          (lambda (n acc)
            (if (zero? n)
                acc
                (my-chosen-name (- n 1) (cons n acc))))))
  my-chosen-name)
 10
 '()) ; ==> (1 2 3 4 5 6 7 8 9 10)

Notice that the body of the letrec just evaluates to the named procedure so that the name isn't in the environment of the first call. Thus you could do this:

(let ((loop 10))
  (let loop ((n loop))
    (if (zero? n)
        '()
        (cons n (loop (- n 1))))) ; ==> (10 9 8 7 6 5 4 3 2 1)

the procedure loop is only in the environment of the body of the inner let and does not shadow the variable loop of the outer let.

In your example, the name loop is just a name. In Scheme every loop is ultimately done with recursion, but usually the name is used when it's tail recursion and thus an iterative process.

9
  • 1
    I find that an explanation of named let in terms of letrec to be too unwieldly. I usually prefer to make reference to rec (from SRFI 31), which is a nicer syntactic sugar around letrec. The translation from unnamed to named let, in terms of simply adding a rec, is simple and easy to reason about. Aug 9, 2015 at 22:46
  • Also, with rec, you don't need to explain the acrobatics around "notice that the body of the letrec just evaluates to the named procedure so that the name isn't in the environment of the first call". rec is easy to reason about. Just use that. :-) Aug 9, 2015 at 22:49
  • @ChrisJester-Young Any of letrec, rec and named let can be used to implement the other two. letrec is the most powerful. I would rather just use lambda but then you'd have to show the warts of Scheme.
    – Sylwester
    Aug 9, 2015 at 22:56
  • Scheme has warts?!! :-O I actually just explained the code in terms of an internally defined function. That is lambda without actually saying the word lambda. :-) Aug 9, 2015 at 22:57
  • Anyway, yes, letrec is the most powerful of the three (since you can use it to create mutually recursive functions), but it's often overkill (syntactically speaking). In the same way, case-lambda is (syntactically) overkill when you have only one "case", and can just use lambda. (Don't laugh. In Guile, all lambdas are represented as case-lambdas behind the scenes.) Aug 9, 2015 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.