Search code examples
syntaxbindingschemelisplet

Unusual Scheme `let` binding, what is `f`?


In "The Scheme Programming Language 4th Edition" section 3.3 Continuations the following example is given:

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))

I can confirm it works in chezscheme as written:

> (product '(1 2 3 4 5))
120

What is 'f' in the above let? Why is the given ls being assigned to itself? It doesn't seem to match what I understand about (let ...) as described in 4.4 local binding:

syntax: (let ((var expr) ...) body1 body2 ...)

If 'f' is being defined here I would expect it inside parenthesis/square brackets:

(let ([f some-value]) ...)

Solution

  • This is 'named let', and it's a syntactic convenience.

    (let f ([x y] ...)
      ...
      (f ...)
      ...)
    

    is more-or-less equivalent to

    (letrec ([f (λ (x ...)
                  ...
                  (f ...)
                  ...)])
      (f y ...))
    

    or, in suitable contexts, to a local define followed by a call:

    (define (outer ...)
      (let inner ([x y] ...)
        ...
        (inner ...)
        ...))
    

    is more-or-less equivalent to

    (define (outer ...)
      (define (inner x ...)
        ...
        (inner ...)
        ...)
      (inner y ...))
    

    The nice thing about named let is that it puts the definition and the initial call of the local function in the same place.

    Cavemen like me who use CL sometimes use macros like binding, below, to implement this (note this is not production code: all its error messages are obscure jokes):

    (defmacro binding (name/bindings &body bindings/decls/forms)
      ;; let / named let
      (typecase name/bindings
        (list
         `(let ,name/bindings ,@bindings/decls/forms))
        (symbol
         (unless (not (null bindings/decls/forms))
           (error "a syntax"))
         (destructuring-bind (bindings . decls/forms) bindings/decls/forms
           (unless (listp bindings)
             (error "another syntax"))
           (unless (listp decls/forms)
             (error "yet another syntax"))
           (multiple-value-bind (args inits)
               (loop for binding in bindings
                     do (unless (and (listp binding)
                                     (= (length binding) 2)
                                     (symbolp (first binding)))
                          (error "a more subtle syntax"))
                     collect (first binding) into args
                     collect (second binding) into inits
                     finally (return (values args inits)))
             `(labels ((,name/bindings ,args
                         ,@decls/forms))
                (,name/bindings ,@inits)))))
        (t
         (error "yet a different syntax"))))