Anonymous lambdas directly referring to themselves

Question

Does Scheme or do any dialects of scheme have a kind of "self" operator so that anonymous lambdas can recur on themselves without doing something like a Y-combinator or being named in a letrec etc.

Something like:

(lambda (n)
   (cond
     ((= n 0) 1)
     (else (* n (self (- n 1)))))))

Answer 1

There is a tradition of writing “anaphoric” macros that define special names in the lexical scope of their bodies. Using syntax-case, you can write such a macro on top of letrec and lambda. Note that the definition below is as hygienic as possible considering the specification (in particular, invisible uses of alambda will not shadow self).

;; Define a version of lambda that binds the
;; anaphoric variable “self” to the function
;; being defined.
;;
;; Note the use of datum->syntax to specify the
;; scope of the anaphoric identifier. 
(define-syntax alambda
  (lambda (stx)
    (syntax-case stx ()
      [(alambda lambda-list . body)
       (with-syntax ([name (datum->syntax #'alambda 'self)])
         #'(letrec ([name (lambda lambda-list . body)])
             name))])))

;; We can define let in terms of alambda as usual.
(define-syntax let/alambda
  (syntax-rules ()
    [(_ ((var val) ...) . body)
     ((alambda (var ...) . body) val ...)]))

;; The let/alambda macro does not shadow the outer
;; alambda's anaphoric variable, which is lexical
;; with regard to the alambda form.
((alambda (n)
   (if (zero? n)
       1
       (let/alambda ([n-1 (- n 1)])
         (* (self n-1) n))))
 10)
;=> 3628800

Most people avoid anaphoric operators since they make the structure of the code less recognizable. In addition, refactoring can introduce problems rather easily. (Consider what happens when you wrap the let/alambda form in the factorial function above in another alambda form. It's easy to overlook uses of self, especially if you're not reminded of it being relevant by having to type it explicitly.) It is therefore generally preferable to use explicit names. A “labeled” version of lambda that allows this can be defined using a simple syntax-rules macro:

;; Define a version of lambda that allows the
;; user to specifiy a name for the function
;; being defined.
(define-syntax llambda
  (syntax-rules ()
    [(_ name lambda-list . body)
     (letrec ([name (lambda lambda-list . body)])
       name)]))

;; The factorial function can be expressed
;; using llambda.
((llambda fac (n)
   (if (zero? n)
       1
       (* (fac (- n 1)) n)))
 10)
;=> 3628800

Answer 2

I have found a way using continuations to have anonymous lambdas call themselves and then using Racket macros to disguise the syntax so the anonymous lambda appears to have a "self" operator. I don't know if this solution is possible in other versions of Scheme since it depends on the Call-with-composable-continuation function of racket and the Macro to hide the syntax uses syntax parameters.

The basic idea is this, illustrated with the factorial function.

( (lambda (n)
     (call-with-values 
       (lambda () (call-with-composable-continuation  
                        (lambda (k) (values k n))))
     (lambda (k n)
        (cond 
          [(= 0 n) 1]
          [else (* n (k k (- n 1)))])))) 5)  

The continuation k is the call to the anonymous factorial function, which takes two arguments, the first being the continuation itself. So that when in the body we execute (k k N) that is equivalent to the anonymous function calling itself (in the same way that a recursive named lambda would do).

We then disguise the underlying form with a macro. Rackets syntax-parameters allow the transformation of (self ARGS ...) to (k k ARGS ... )

so we can have:

 ((lambda-with-self (n)
    (cond 
      [(= 0 n) 0]
      [(= 1 n) 1]
      [else (* n (self (- n 1)))])) 5)

The complete Racket program to do this is:

#lang racket
(require racket/stxparam) ;required for syntax-parameters
(  define-syntax-parameter self (λ (stx) (raise-syntax-error #f "not in  `lambda-with-self'" stx)))

(define-syntax-rule
(lambda-with-self (ARG ... ) BODY ...) 
 (lambda (ARG ...)
   (call-with-values 
    (lambda ()(call/comp (lambda (k) (values k ARG ...))))
    (lambda (k ARG ...)
      (syntax-parameterize ([self (syntax-rules ( )[(self ARG ...) (k k ARG ...)])])
    BODY ...)))))
;Example using factorial function
((lambda-with-self (n)
      (cond 
        [(= 0 n) 0]
        [(= 1 n) 1]
        [else (* n (self (- n 1)))])) 5)

This also answers my previous question about the differences between the different kinds of continuations. Different kinds of continuations in Racket

This only works because unlike call-with-current-continuation, call-with-composable-continuation doesn't abort back to a continuation prompt but invokes the continuation at the place it was invoked.

Answer 3

No. The trouble with the "current lambda" approach is that Scheme has many hidden lambdas. For example:

• All the let forms (including let*, letrec, and named let)
• do (which expands to a named let)
• delay, lazy, receive, etc.

To require the programmer to know what the innermost lambda is would break encapsulation, in that you'd have to know where all the hidden lambdas are, and macro writers can no longer use lambdas as a way to create a new scope.

All-round lose, if you ask me.