What are the differences between 'let' or 'letrec' and 'define' for creating local bindings?

Question

I don't understand what the differences are between (sorry for the contrived example):

(define average
  (lambda (elems)

   (define length
     (lambda (xs)
      (if (null? xs)
          0
          (+ 1 (length (cdr xs))))))

   (define sum
     (lambda (xs)
      (if (null? xs)
          0
          (+ (car xs) (sum (cdr xs))))))

   (define total (sum elems))

   (define count (length elems))

   (/ total count)))

and

(define average
  (lambda (elems)
   (letrec ((length
              (lambda (xs)
               (if (null? xs)
                   0
                   (+ 1 (length (cdr xs))))))

            (sum
              (lambda (xs)
               (if (null? xs)
                   0
                   (+ (car xs) (sum (cdr xs))))))

            (total (sum elems))

            (count (length elems)))

     (/ total count))))

As far as I can tell, they both create a new scope, and in that scope create 4 local variables that refer to each other and to themselves, and evaluate and return a body.

Am I missing something here, or is letrec synonymous with scoped defines?

I know this may be implementation dependent; I'm trying to get an understanding of the fundamentals of Lisps.

Crankshaft

Answer 1

You are correct that there are parallels between the define and letrec versions of your code. However, the devil is in the details. In R5RS, internal define has letrec semantics. In R6RS, internal define has letrec* semantics.

What's the difference? Your code has actually just highlighted this difference. As Zhehao's answer mentions, your definition of total and count inside the same letrec as the length and sum is incorrect: length and sum are not guaranteed to be bound by the time you're evaluating the values of (length elems) and (sum elems), since the binding of those variables is not guaranteed to be left-to-right.

letrec* is similar to letrec, but with a left-to-right guarantee. So if you changed your letrec to letrec*, it'd be okay.

Now, back to my initial comment: because R5RS's internal define uses letrec semantics, even your define version of the code would be incorrect under an R5RS implementation, but it would be okay under an R6RS implementation, which has letrec* semantics.

Nonparticipation

Strictly speaking, length and sum are guaranteed to be bound (to locations); what isn't guaranteed is that they have yet been assigned their initializing values. And even if they have been assigned them, the Scheme reports R5RS--R7RS say it's nonetheless an "error" to be referencing those values in the way you do in the initializing clauses for total and count. (However, I don't think that implementations are required to detect and complain about this error.) Some more on differences btw letrec/letrec*: https://mcmap.net/q/1925586/-letrec-and-reentrant-continuations/272427 – Nurse

Answer 2

Both let/letrec and define will create locally scoped definitions. However, let/letrec is more convenient when you aren't inside and implicit begin statement. For instance, the following code uses a let macro.

(define (test) (let ((x 1)) x))

The same code using locally scoped defines would be

(define test (lambda () (define x 1) x))

This is sort of a contrived example, but generally using let macros to do local bindings is considered more functional.

Also, your example code does not use letrec correctly. You do not need the defines inside the letrec declarations (in fact they really shouldn't be there).

Rennold

Great answer! As mentioned in my answer, under R5RS, even the define version of the OP's code is incorrect, not just the letrec version. – Nonparticipation

Good point about define inside letrec ... must have been tired when I wrote that. +1 – Crankshaft