Re: Detecting Infinite Looping

Subject: Re: Detecting Infinite Looping
From: Henry Thompson <ht@xxxxxxxxxxxxxxx>
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
     (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
    (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!


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
     (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  

 DSSSList info and archive:

Current Thread
  • Detecting Infinite Looping
    • W. Eliot Kimber - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id XAA26840Wed, 28 Jan 1998 23:49:20 -0500 (EST)
      • Richard Light - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id EAA04376Thu, 29 Jan 1998 04:14:50 -0500 (EST)
      • Henry Thompson - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id EAA04681Thu, 29 Jan 1998 04:40:15 -0500 (EST) <=
      • <Possible follow-ups>
      • Pawson, David - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id DAA29108Thu, 29 Jan 1998 03:02:52 -0500 (EST)
      • Gavin Nicol - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id FAA05174Thu, 29 Jan 1998 05:37:26 -0500 (EST)
      • W. Eliot Kimber - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id KAA06902Thu, 29 Jan 1998 10:35:42 -0500 (EST)
        • hanche+dsssl-l - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id NAA07915Thu, 29 Jan 1998 13:13:21 -0500 (EST)