Return from a lambda

Questions & Answers
1

Hi,

i have some functions def that allow returning early from function defined.
But i have a few difficulties to pass from the version 'define to the version 'lambda.

'def is defined this way (code shortened):

(module def racket/base


	(provide def return return-rec)

	(require srfi/31 ;; for 'rec in def*
		
		 racket/stxparam
		 (for-syntax racket/base))

                (define-syntax def

                      (lambda (stx)
    
                               (syntax-case stx ()
	  
                                      ((_ (<name> <arg> ...) <body> <body>* ...)
	 
         
	 #'(define (<name> <arg> ...)

	     (call/cc

	      (lambda (ret-rec-id) ;(#,ret-rec-id)
		;; In the body we adjust the 'return-rec' keyword so that calls
		;; to 'return-rec' are replaced with calls to the escape
		;; continuation.

		(syntax-parameterize
		 ([return-rec (syntax-rules ()
				[(return-rec vals (... ...))
				 (ret-rec-id vals (... ...))])])
		 
		 (apply (rec <name> (lambda (<arg> ...)
				      
				      (call/cc

				       (lambda (ret-id) ;(#,ret-id)
					 ;; In the body we adjust the 'return' keyword so that calls
					 ;; to 'return' are replaced with calls to the escape
					 ;; continuation.
					 (syntax-parameterize
					  ([return (syntax-rules ()
						     [(return vals (... ...))
						      (ret-id vals (... ...))])])
					  <body> <body>* ...)))))
			
			(list <arg> ...)))))))
))) ; check the number of parenthesis !

which works well allowing to 'return from the current call and 'return-rec from all recursive calls if any.

But i have problem to define a 'lambda+ that would do the same (code shortened but should works):

(define-syntax lambda+
	  (lambda (stx)
  	    (syntax-case stx ()
	      ((_ (<arg> ...) <body> <body>* ...)

	       #'(lambda (<arg> ...)
		       (apply (rec <name>
				   (lambda (<arg> ...)				    
					    (call/cc
					     (lambda (ret-id) ;(#,ret-id)
					       ;; In the body we adjust the 'return' keyword so that calls
					       ;; to 'return' are replaced with calls to the escape
					       ;; continuation.
					       (syntax-parameterize
						([return (syntax-rules ()
							   [(return vals (... ...))
							    (ret-id vals (... ...))])])
						;;(display "def+.rkt : def+ : <body> =") (display <body>) (newline)
						<body>
						<body>*
						...)))))			      
			      (list <arg> ...))))

	 )))

return-rec is not critical to my code, as it can be done by return in a program, and Python has just return and no way to return directly from all the nested calls but as it works in def i think there could be a solution for lambda+ ?

for now i can execute this:

(define x 3)
((rec
    bar
    (lambda+
     ()
     (when (x < 5) (set!x (+ x 1)) (display "super!") (newline) (bar))
     (display "returning")
     (newline)
     (return 17)
     'not_good))))


super!
super!
returning
returning
returning
17

only at REPL at some point i got a solution with other code and return-rec with an expected output:

super!
super!
returning
17

but was at REPL and definitions have less restrictions than in module.

Regards,

2

In the expansion of def macro, <name> is shadowed in the <body> <body>* ... forms by the binding introduced by rec. Thus, (lexically) recursive of <name> call the inner procedure, inside the capture of ret-rec-id.

In your lambda+ macro, there is no name for that inner procedure: you bind it to <name>, but that is not a pattern variable, so it is just an arbitrary name that, by hygiene, is not in scope in the body forms. Without a name for that inner procedure, even if you added an outer continuation analogous to return-rec-id, any recursive call would go through the outer procedure, so a new return-rec continuation would be established alongside each new return continuation.

More fundamentally:

this concept seems conceptually flawed. The implementation for def in fact returns from only recursive calls made lexically inside the body. I would suggest thinking further about what programming patterns you are trying to make easier to express. Also, you should probably weigh this feature against the performance cost of adding two continuation operations to every procedure call.

I know you are sometimes interested in portability to other Schemes, but, in Racket, call-with-continuation-prompt and abort-current-continuation might be more direct ways to express early return than call/cc.

Finally, tangentially, when your macros generate code in the form (apply <expression> (list <arg> ...)), they could more efficiently simply generate (<expression> <arg> ...): there's no need for apply.

3

I did not understand completely the macro def, it comes from the Guile mailing list years ago, i just adapted it to have a return-rec by nesting the original in another level of call/cc. It works well.

Using it i find little usage of return-rec because anyway if you do return it will return at the level of recursion above and will encounter surely another return as the procedure is recursively defined.

I will try to take in account all what you said and try to reply. Since yesterday i'm considering dropping support for return-rec in lambda+.

About performance ,yes i know, for this reason i have undocumented other 'def versions. Upgrading the project of Guile and Kawa or create other is a concern but require a lot of time, the Racket version is far ahaead but for this reason i try to keep in R5RS...R7RS compatibility.

4

Taking this in account i'm not far from a solution,it well returns from nested recursive calls but it does not return the value! no problem with the single return.

Here my simple current code:

(define-syntax lambda+
	  (lambda (stx)
  	    (syntax-case stx ()
	      ((_ (<arg> ...) <body> <body>* ...)

	       #'(call/cc
		    (lambda (ret-rec-id) ;(#,ret-rec-id)
		     
		      (syntax-parameterize
		       ([return-rec (syntax-rules ()
				      [(_ vals (... ...))
				       (ret-rec-id vals (... ...))])])
		       (lambda (<arg> ...)			    
			 (call/cc
			  (lambda (ret-id) ;(#,ret-id)
			    ;; In the body we adjust the 'return' keyword so that calls
			    ;; to 'return' are replaced with calls to the escape
			    ;; continuation.
			    (syntax-parameterize
			     ([return (syntax-rules ()
					[(_ vals (... ...))
					 (ret-id vals (... ...))])])
			     <body>
			     <body>*
			     ...))))))))
))) ; check parenthesis !

this run well on simple return:

(define x 3)
(define foo (rec bar (lambda+ ()
                    (when (< x 5)
                      (set! x (+ x 1))
                      (display "super!")(newline)
                      (bar))
                    (display "returning") (newline)
                    (return 17)
                    'not_good)))
(foo)
super!
super!
returning
returning
returning
17

but trying return-rec :

(define x 3)
(define foo (rec bar (lambda+ ()
                    (when (< x 5)
                      (set! x (+ x 1))
                      (display "super!")(newline)
                      (bar))
                    (display "returning") (newline)
                    (return-rec 17)
                    'not_good)))

(foo)
super!
super!
returning

i did not get the return value 17 :open_mouth:

any idea?

5

Your implementation of return-rec uses a continuation where the lambda+ expression was evaluated, not where the resulting function is called.

Here is your sample code with cleaned-up indentation and in a form that actually runs:

#lang racket

(require (only-in srfi/31 rec)
         racket/stxparam)

(define-for-syntax (out-of-context stx)
  (raise-syntax-error #f "used out of context" stx))

(define-syntax-parameter return out-of-context)

(define-syntax-parameter return-rec out-of-context)

(define-syntax (lambda+ stx)
  (syntax-case stx ()
    [(_ (<arg> ...) <body> <body>* ...)
     #'(call/cc
        (lambda (ret-rec-id)
          (syntax-parameterize
              ([return-rec (syntax-rules ()
                             [(_ vals (... ...))
                              (ret-rec-id vals (... ...))])])
            (lambda (<arg> ...)			    
              (call/cc
               (lambda (ret-id)
                 (syntax-parameterize
                     ([return (syntax-rules ()
                                [(_ vals (... ...))
                                 (ret-id vals (... ...))])])
                   <body> <body>* ...)))))))]))

(This makes it much easier to read and comment upon your code. In particular, avoid posting commented-out code like ;(#,ret-id), especially as syntax highlighting in email and Discourse is not smart enough to handle it.)

At the REPL, you then get:

> (define x 3)
> (define foo
    (rec bar
      (lambda+ ()
               (when (< x 5)
                 (set! x (+ x 1))
                 (displayln "super!")
                 (bar))
               (displayln "returning")
               (return-rec 17)
               'not_good)))
> foo
#<procedure>
> (foo)
super!
super!
returning
> foo
17

If you put this inside a module, you would instead get an error like:

define-values: assignment disallowed;
 cannot re-define a constant
  constant: foo
  in module:'anonymous-module

(In fact, it only works this well because Racket implicitly inserts continuation prompts.)

It seems like your use of (define foo (rec bar 🕳️)) may have been an attempt to respond to my comment that:

but bar is still outside from the perspective of the introduced return-rec continuation. This is easier to see if you write out an without your lambda+ macro. The macro stepper can help with this, but I've done it by hand to further simplify the presentation:

(define x 3)
(define foo
  (rec bar
    ;; [A]
    (let/cc return-rec
      (λ () ;; [B]
        (let/cc return
          (when (< x 5)
            (set! x (+ x 1))
            (displayln "super!")
            (bar))
          (displayln "returning")
          (return-rec 17)
          'not_good)))))

The immediate problem is that you need to introduce a lambda expression at [A] around the rest of the forms, so that the return-rec continuation returns to a call site, not the place where the lambda+ expression is used. You would then need to adjust the inside of return-rec to immediately call the inner procedure. This would the equivalent to what your def version does.

But the fundamental problem would still remain: foo and bar would both refer to the outer procedure to be added at [A], but, for return-rec to be useful, you need to be able to call the inner lambda at [B] so that nested calls capture a new return continuation but not a new return-rec continuation. This is fine for your def macro: since it knows the name of the defined procedure, it shadows that name in the body with a binding for the inner procedure. But a lambda-like form creates an anonymous function: there is no name to shadow.

You could change your lambda+ macro to be a recursive binding form like rec or named let, which would give you a name. You could also change your implementation to use prompts instead of call/cc, which would also change the semantics of returning to be based on dynamic extent, rather than lexical nesting.

But what I really recommend is that you think about the question, Why does the language feature return-rec appear necessary? If you can describe a type of program that you are trying to make easier to express, people may be able to offer suggestions about how to implement such a feature and give it clear semantics. But the general notion of return-rec returning “from all recursive calls if any” seems to me conceptually flawed. It seems analogous to the way the Scheme standards don't speak about “tail recursion”, but about the proper treatment of all tail calls, whether they are self-recursive, mutually recursive, or not recursive at all. I think it would be hard to come up with a generally useful and composable definition of “from all recursive calls if any”. It seems especially hard to come up with a semantics that will be more clear than adding an explicit let/ec where needed. And the performance cost of adding two continuation captures to every call to a procedure defined with def or lambda+ seems exorbitant.

6

Just for fun, here's a demonstration of how continuation prompts can express recursive early returns:

#lang racket
(module+ test
  (require rackunit))
(define-values [call-with-return-point return]
  (let ([tag (make-continuation-prompt-tag 'return)])
    (define (call-with-return-point thunk)
      (call-with-continuation-prompt
       thunk
       tag
       (λ (rec? vals)
         (cond
           [(and rec? (continuation-prompt-available? tag))
            (abort-current-continuation tag rec? vals)]
           [else
            (apply values vals)]))))
    (define (return #:rec? [rec? #f] . vals)
      (unless (continuation-prompt-available? tag)
        (error 'return "no return point available"))
      (abort-current-continuation tag rec? vals))
    (values call-with-return-point return)))
(module+ test
  (define (wrap-demo thunk)
    (call-with-return-point
     (λ ()
       (+ 1 (call-with-return-point thunk)))))
  (check-equal? (wrap-demo (λ ()
                             (return 2)
                             (error "won't get here")))
                3)
  (check-equal? (wrap-demo (λ ()
                             (return "recursive return" #:rec? #t)
                             (error "won't get here")))
                "recursive return"))

But again, I think what's most needed is careful thinking through of the design and motivation of return-rec. If you conclude it really is a feature you want, the choice of implementation technique should follow from the design of the language construct, not the other way around.

7

It's a very interesting discussion.It's early in my timezone and i could be offline for days as my daughter has an important medical rendez-vous this morning.

a short answer:
i misunderstand the use of rec. The code you and me provided works.
I just did not see it modified foo !!! perheaps a property of the code and rec used. I have to think of that. And that not the way i want it, this side effect is bad and not possible in module, yes i had this error. No i just wanted the value returned.
Sorry if the text is not clear , i have no time for now.

i not really understand this :


foo
#<procedure:...-Racket/lambda+.rkt:37:21>


#<eof>
> (foo)


(foo)
super!
super!
returning


#<eof>
> foo


foo
17

foo changed from procedure to number 17 !!!

about return-rec philosophy , i just wanted a return as in Python ,after i think of a more global return-rec.

Find return-rec not really usefull , i use it one time only ,and i find it could be easy to code in another way but when i wrote the code return-rec was in my mind so i use it, here is the sole example for now:

i understand the problem is a combination of rec and lambda+ , this has to be studied with a quiet mind

Damien

8

i think i now understand the problem

but seems hard to code

i just do not know how to solve the [A] point with a lambda,i understand the problem is to continue with the call site not where lambda+ was defined, but i'm not sure it could done with an anonymous function without encapsulating in soemthing else, but not from the inner of it

9

ok i will stop here, this is far from my competence

it is a minor feature , a lot of language have return, only scheme+ got a return-rec ,it works with def, def+ but will not works with lambda+ unless a good samaritain write it for me ah ah ah

here is my last unsucessfull atempt:

(define (<name> <arg> ...)

	     (call/cc

	      (lambda (ret-rec-id) ;(#,ret-rec-id)
		;; In the body we adjust the 'return-rec' keyword so that calls
		;; to 'return-rec' are replaced with calls to the escape
		;; continuation.

		(syntax-parameterize
		 ([return-rec (syntax-rules ()
				[(return-rec vals (... ...))
				 (ret-rec-id vals (... ...))])])
		 
		 (apply (rec <name> (lambda (<arg> ...)
				      
				      (call/cc

				       (lambda (ret-id) ;(#,ret-id)
					 ;; In the body we adjust the 'return' keyword so that calls
					 ;; to 'return' are replaced with calls to the escape
					 ;; continuation.
					 (syntax-parameterize
					  ([return (syntax-rules ()
						     [(return vals (... ...))
						      (ret-id vals (... ...))])])
					  <body> <body>* ...)))))
			
			(list <arg> ...))))))

(define x 3)
(define foo (lambda+ ()
                    (when (< x 5)
                      (set! x (+ x 1))
                      (display "super!")(newline)
                      (foo))
                    (display "returning") (newline)
                    (return-rec 17)
                    'not_good))
(foo)

that still does not works with return-rec

Welcome to DrRacket, version 8.18.0.13-2025-08-26-0bb5c26e85 [cs].
Language: racket, with debugging; memory limit: 8192 MB.
super!
super!
returning
returning
returning
17

the return-rec still act as a return

my official version 2 days ago already take that in account:

i add 2 different error message:

and it is well specified of the doc that lambda+ is limited to using only return :

10

What is strange is that if i create a version that allows just return and no more return-rec, so that there is only 1 call/cc and not 2 it slower :
i wrote a defun that allow just return instead of def or def+ that allows return and return-rec, see the benchmarks on fibonacci:

Welcome to DrRacket, version 8.17 [cs].
Language: reader SRFI-105, with debugging; memory limit: 14000 MB.
SRFI 105 Curly Infix v12.3 for Scheme+
care of quote flag set to:#t
strict SRFI-105 flag set to:#f
use only syntax transformers flag set to:#f
SRFI-105 Curly Infix parser for Racket Scheme and R6RS by Damien MATTEI
(based on code from David A. Wheeler and Alan Manuel K. Gloria.)
Scheme+ v15.7 by Damien Mattei
> (def+ (fib+ n)
  (if {n < 2}
      n
      {(fib+ (n - 1)) + (fib+ (n - 2))}))


(def+ (fib+ n) (if (< n 2) n (+ (fib+ (- n 1)) (fib+ (- n 2)))))


#<eof>
> (time (fib+ 43))


(time (fib+ 43))
cpu time: 77452 real time: 76932 gc time: 5070
433494437


#<eof>
> (define (fib n)
  (if {n < 2}
      n
      {(fib (n - 1)) + (fib (n - 2))}))


(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))


#<eof>
> (time (fib 43))


(time (fib 43))
cpu time: 40814 real time: 40570 gc time: 2144
433494437


#<eof>
> (defun (fib-fun n)
  (if {n < 2}
      n
      {(fib-fun (n - 1)) + (fib-fun (n - 2))}))


(defun (fib-fun n) (if (< n 2) n (+ (fib-fun (- n 1)) (fib-fun (- n 2)))))


#<eof>
> (time (fib-fun 43))


(time (fib-fun 43))
cpu time: 95027 real time: 94339 gc time: 5270
433494437


#<eof>
> (time (fib+ 43))


(time (fib+ 43))
cpu time: 77428 real time: 76894 gc time: 3928
433494437


#<eof>
> (time (fib 43))


(time (fib 43))
cpu time: 40879 real time: 40654 gc time: 2135
433494437


#<eof>
> (time (fib-fun 43))


(time (fib-fun 43))
cpu time: 94473 real time: 93838 gc time: 5363
433494437


#<eof>
> (def+ (fib+rr n)
  (if {n < 2}
      (return-rec n)
      {(fib+rr (n - 1)) + (fib+rr (n - 2))}))


(def+
 (fib+rr n)
 (if (< n 2) (return-rec n) (+ (fib+rr (- n 1)) (fib+rr (- n 2)))))


#<eof>
> (time (fib+rr 43))


(time (fib+rr 43))
cpu time: 0 real time: 0 gc time: 0
1


#<eof>
> (defun (fib-fun-ret n)
  (if {n < 2}
      (return n)
      (return {(fib-fun (n - 1)) + (fib-fun (n - 2))})))


(defun
 (fib-fun-ret n)
 (if (< n 2) (return n) (return (+ (fib-fun (- n 1)) (fib-fun (- n 2))))))


#<eof>
> (time (fib-fun-ret 43))


(time (fib-fun-ret 43))
cpu time: 94780 real time: 94042 gc time: 5357
433494437


#<eof>
>

summary:

with define 40 seconds
with def+ 76 seconds
with defun 96 seconds !!!

if i release a version that allows only return it will be the slower of all.

Note that return-rec could be dangerous with double recursion (fibonacci example) because it will exit the function not only the calls ,see the false result of fib+rr, the programmer should take care of that.

here is the code of defun, largely base on lambda+:

(module defun racket/base


	(provide defun #;def+ return return-rec)

	(require srfi/31 ;; for 'rec in defun*
		
		 Scheme+/nfx
		 Scheme+/return
		 racket/stxparam
		 (for-syntax racket/base))
	  

(define-syntax defun

  (lambda (stx)
    
      (syntax-case stx ()

	;; multiple definitions without values assigned
	;; (defun (x y z))
	;; TODO: remove? redundant with (declare x y z)
	((_ (var1 ...)) #`(begin (define var1 '()) ...))


	((_ (<name> <arg> ...) <body> <body>* ...)
	 
         
	 #'(define (<name> <arg> ...)
		 
	     (apply (rec <name> (lambda (<arg> ...)
				  
				  (call/cc

				   (lambda (ret-id) ;(#,ret-id)
				     ;; In the body we adjust the 'return' keyword so that calls
				     ;; to 'return' are replaced with calls to the escape
				     ;; continuation.
				     (syntax-parameterize
				      ([return (syntax-rules ()
						 [(return vals (... ...))
						  (ret-id vals (... ...))])])
				      <body>
				      <body>*
				      ...)))))
		    
		    (list <arg> ...))))

	

	;; variadic arguments in list
	;; (defun (foo a . L) (when #t (return (cons a L))))
	;; (foo 1 2 3)
	;; '(1 2 3)
	((_ (<name> <arg> . L) <body> <body>* ...)
	 
         
	 #'(define (<name> <arg> . L)

	     
	     (apply (rec <name> (lambda (<arg> . L)
				  
				  (call/cc

				   (lambda (ret-id) ;(#,ret-id)
				     ;; In the body we adjust the 'return' keyword so that calls
				     ;; to 'return' are replaced with calls to the escape
				     ;; continuation.
				     (syntax-parameterize
				      ([return (syntax-rules ()
						 [(return vals (... ...))
						  (ret-id vals (... ...))])])
				      <body>
				      <body>*
				      ...)))))
		    
		    (cons <arg> L))))


	

	;; single definition without a value assigned
	;; (defun x)
	((_ var) #`(define var '()))

	;; (defun s  3 ² + 2 * 3 * 5 + 5 ²)
	;; 64
	((_ var expr expr-optional ...) #`(define var ($nfx$-rec expr expr-optional ...))) ; expr expr-optional ...))

	((_) #`(error "Bad defun form"))
	
	

	)))



)
11

That is because your fib+rr doesn't implement the Fibonacci sequence: it short circus early and always returns 1.

(It would help a lot if you could minimize examples, remove dead or commented-out code, and clean up indentation before posting. For example, the definitions of your fib functions are duplicated twice.)