detecting a recursive call?

[Kees-Jochem Wehrmeijer]

Hi,

I'm wondering whether it's possible for a function to detect whether it's being called by itself, possibly indirectly. I want to use this to prevent endless loops and generate different results in these situations. For example, imagine I have the following functions:

(define (foo loc)

  (list

   (cons loc 'a)

   (cons (+ loc 1) 'b)

   (cons (+ loc 2) 'c)))

(define (combine a b)

  (lambda (loc)

    (append (a loc) (b (+ loc 3)))))

So I can do:

> ((combine foo foo) 0)

=> '((0 . a) (1 . b) (2 . c) (3 . a) (4 . b) (5 . c))

Now, let's say I have these recursive definitions:

(define (recur1 loc)

  ((combine foo recur2) loc))

(define (recur2 loc)

  (recur1 loc))

Defined in this way, a call to (recur1 0) loops endlessly. I would like it too return something like

> (recur1 0)

=> '(0 . a) (1 . b) (2 . c) (loop 0))

So I was thinking if I could make it work if I could do something like:

(define (recur1 loc)

  (if (in-recursive-call?)

      (list (cons 'loop 0))

      ((combine foo recur2) loc)))

Is that something that's possible? Is there a better way to do what I want?

Thanks,

Kees

[Sam Tobin-Hochstadt]

This is possible -- the central trick is to maintain information about
the call stack separately, perhaps by using continuation marks.

We (mostly Phil Nguyen) recently built a tool that does this. If you
take your program, install the "termination" package, and then add:

(require termination)
(begin/termination (recur1 0))

you get this error message:

possible-non-termination: Recursive call to `#<procedure:recur1>` has
no obvious descent on any argument
- Preceding call:
* 1st arg: 3
- Subsequent call:
* 1st arg: 6

We have a paper, here: https://arxiv.org/abs/1808.02101 which goes
into detail about how it works. The source code is here:
https://github.com/philnguyen/termination

Sam

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/292977cf-7800-453f-9d4b-b6a1ee525287%40googlegroups.com.

[Gustavo Massaccesi]

If you don't want to use the package or you want other criteria for stooping, I think the correct way to do this are continuation marks, but an easier but more inefficient way is using a parameter (so it is thread safe).

;-----

#lang racket
(define recursion-level (make-parameter 0))

(define (f x)
  (sleep (* .1 (random)))
  (cond
    [(<= (recursion-level) 5)
     (parameterize ([recursion-level (add1 (recursion-level))])
       (displayln (list (recursion-level) x))
       (f (* x 2)))]
    [else
     (displayln (list "too many recursions" x))]))

(thread (lambda () (f 10)))
(f 1)

; -----

Gustavo

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2Bb0odK1qfox9Ah2umLqKxUhas_GTJUv95Avm536g9ybGg%40mail.gmail.com.

[Hendrik Boom]

On Fri, Aug 09, 2019 at 01:03:17PM -0400, Sam Tobin-Hochstadt wrote:
> This is possible -- the central trick is to maintain information about
> the call stack separately, perhaps by using continuation marks.

Or set a global variable on entry, and reset it on exit.
If on entry the global variable is set (before you set it, of course),
you've called yourself, directly of indirectly.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2Bb0odK1qfox9Ah2umLqKxUhas_GTJUv95Avm536g9ybGg%40mail.gmail.com.

[Sam Tobin-Hochstadt]

That has a couple potential problems, including breaking tail calls, but is also potentially faster. This is all discussed in the paper I linked. 

Sam

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20190809182512.cffth5bwreff5urs%40topoi.pooq.com.

[Kees-Jochem Wehrmeijer]

Thanks everyone! I'm gonna have a closer look at those. What I ended up doing was something like this:

(struct Wrapper (exp arg) #:mutable)

(define-syntax-rule (define-wrapper name exp)

  ((define name (Wrapper (delay exp) #f)))

(define (Wrapper->fn w)

  (lambda (arg)

    (if (Wrapper->arg w)

        (list 'loop (Wrapper->arg w))

        (let ()

           (set-Wrapper-arg! w arg)

           (define result (force (Wrapper-exp w)))

           (set-Wrapper-arg! w #f)

           result))))

So basically, when the function gets called the first time its argument will be #f. In my particular case this won't be the case for any other calls, so only in that case it will force the expression.

Kees

> > To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.

> > To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/292977cf-7800-453f-9d4b-b6a1ee525287%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2Bb0odK1qfox9Ah2umLqKxUhas_GTJUv95Avm536g9ybGg%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.