## Re: Detecting Infinite Looping

 Subject: Re: Detecting Infinite Looping From: Henry Thompson Date: 29 Jan 1998 09:40:24 +0000
```node-list-contains? plus a slight change in perspective will do the
trick for you (although if my memory serves, n-l-c? isn't defined in
JADE -- a definition is offered at the end of this message).

There are two idioms for building up a list recursively from an
inductive definition:

The simple version, isomorphic to the inductive definition of the
desired result (substitute appropriately for P, F, NEXT, BASE

(define f1
(lambda (x)
(if P
BASE
(cons F (f1 NEXT)))))

The substitutions
P: (null? x)
BASE: '()
F: (car x)
NEXT: (cdr x)
would copy the top level of a list

Note this formulation is not trivially tail-recursive.

The alternative, tail-recursive, formulation, is as follows:

(define f1
(lambda (x)
(f1a x BASE)))

(define f1a
(lambda (x result)
(if P
result
(f1a NEXT (append result (list F))))))

This computes exactly the same result, but has the advantages that it's
tail recursive AND you have the result available to you as you go.
It may be less efficient (because of the append), but if you don't
care about order you can say (cons (F x) result) instead, or reverse
the result in one go at the end.

So the following would give a useful result on a circular list (not
possible in DSSSL, I know):

P: (or (null? x)(member (car x) result))
BASE: '()
F: (car x)
NEXT: (cdr x)

This is in fact a misleading definition, because it bails at the first
duplicate list ELEMENT, which is not what I said, but the paradigm
should be clear by now, I hope!

ht

PS.  You can see the tail recursion more clearly by using a named 'let'

(define f1
(lambda (arg)
(let loop ((x arg)
(result BASE))
(if P
result
(loop NEXT (append result (list F)))))))

--
Henry S. Thompson, Human Communication Research Centre, University of Edinburgh
2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
Fax: (44) 131 650-4587, e-mail: ht@xxxxxxxxxxxxxxx
URL: http://www.cogsci.ed.ac.uk/~ht/

DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist

```