Scheme - Returning Control from a "loop" prematurely >>>Newbie Question<

Author

Returning Control from a "loop" prematurely >>>Newbie Question<

Patrick

2005-05-19, 4:02 pm

Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 73
Message-ID: <Ko1je.23109$HJ2.20837@fe11.lga>
Date: Thu, 19 May 2005 10:28:58 -0400
NNTP-Posting-Host: 67.82.57.121
X-Complaints-To: abuse@cv.net
X-Trace: fe11.lga 1116512938 67.82.57.121 (Thu, 19 May 2005 07:28:58 MST)
NNTP-Posting-Date: Thu, 19 May 2005 07:28:58 MST
Organization: Optimum Online
Xref: number1.nntp.dca.giganews.com comp.lang.scheme:58598

Hi.

Let's say I had a function g, which takes an integer
as an argument and will either return a positive integer
if it has some special property, otherwise it will
return 0. Most of the time, for arbitrary inputs,
g is going to return 0.

Now, suppose I want to set up a loop, and call g
with successive arguments (g 1), (g 2), (g 3), and
so on...

This loop is going to terminate when the loop counter
gets to some sentinel value or ,perhaps sooner , if that
that special property is found.

In C the code might look something like

int f (int n)
{
int result = 0;

f (int i = 0; i < n; ++i)
{
result = g(n);

if (result != 0)
i = n;
}

return result;
}

What g does specifically isn't that important. The
g I am working with is actually very complicated but
for the sake of having a concrete example, in this
case g will return the quotient of n divided by 11
only if 11 divides n evenly; g will return zero
otherwise.

In Scheme I have:

(define (g n)
(if (= (modulo n 11) 0)
(quotient n 11)
0))

(define (f n)
(define (f-iter i)
(if (> i n)
0
(if (not (= (g i) 0))
(f-iter (+ i 1))
(g i))))
(f-iter 1))

Obviously f isn't working how I want it to since this
function always seems to return 0.

I'm curious to see how people do this kind of thing
in Scheme since unlike C, it doesn't seem like you
can just let control "fall out of the loop", break,
or "force" a return from a function.

In a previous post of mine someone suggested that
I use the trace function to debug some code. Trace
sounds like a great tool but as far as I can tell it's
not available to me in PLT Scheme. My current language
setting is R5RS. Perhaps trace, on that implementation
goes by another name?

Thanks in advance.

Nils M Holm

2005-05-19, 4:02 pm

Patrick <mathg

XXXXII@hotmail.com> wrote:
> f (int i = 0; i < n; ++i)
> {
> result = g(n);
>
> if (result != 0)
> i = n;
> }

You can (roughly) rewrite this fragment as

for (i=0; i<n && g(i) != 0; i++) ;

(Assuming that you meant
- "for (int" instead or "f (int"
- "result = g(i)" instead of "result = g(n)"
)

This way you avoid the ugly premature exit and
get a version that should be easier to translate
to Scheme.

> I'm curious to see how people do this kind of thing
> in Scheme since unlike C, it doesn't seem like you
> can just let control "fall out of the loop", break,
> or "force" a return from a function.

Of course you can. Look up the R5RS procedure
"call-with-current-continuation" in your manual.

Nils

--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/

Adrian Kubala

2005-05-19, 4:02 pm

Patrick <mathg

XXXXII@hotmail.com> schrieb:
> I'm curious to see how people do this kind of thing
> in Scheme since unlike C, it doesn't seem like you
> can just let control "fall out of the loop", break,
> or "force" a return from a function.

Look up call-with-current-continuation (often abbreviated
call/cc). You can use continuations to do anything you can
do with labels/gotos/return/break/continue; the basic form
is:

(call/cc (lambda (return)
...
(return someval) ; when you need to escape
...))

David Van Horn

2005-05-19, 4:02 pm

Patrick wrote:
> Let's say I had a function g, which takes an integer
> as an argument and will either return a positive integer
> if it has some special property, otherwise it will
> return 0. Most of the time, for arbitrary inputs,
> g is going to return 0.
>
> Now, suppose I want to set up a loop, and call g
> with successive arguments (g 1), (g 2), (g 3), and
> so on...
>
> This loop is going to terminate when the loop counter
> gets to some sentinel value or ,perhaps sooner , if that
> that special property is found.
....
> What g does specifically isn't that important. The
> g I am working with is actually very complicated but
> for the sake of having a concrete example, in this
> case g will return the quotient of n divided by 11
> only if 11 divides n evenly; g will return zero
> otherwise.
>
> In Scheme I have:
>
> (define (g n)
> (if (= (modulo n 11) 0)
> (quotient n 11)
> 0))
>
> (define (f n)
> (define (f-iter i)
> (if (> i n)
> 0
> (if (not (= (g i) 0))
> (f-iter (+ i 1))
> (g i))))
> (f-iter 1))
>
> Obviously f isn't working how I want it to since this
> function always seems to return 0.

I think you have your conditional in f-iter reversed. When (= (g i) 0), then
i does not divide n evenly. So in that case, you want to recur. Also, you
call g twice on the same argument, so you're needlessly duplicating
computation (that is, if g is side-effect free), and since you said g is
complicated, this may be a significant waste.

Here is one way to write it. In g, I return false, rather than zero to
indicate that the number does not have the property in question. Likewise I
return false from f when a number having the property of g cannot be found.

;; g will return the quotient of n divided by 11
;; only if 11 divides n evenly; g will return _FALSE_
;; otherwise.

(define (g n)
(and (zero? (modulo n 11)) (quotient n 11)))

;; Call (g i) for 1 <= i <= n, and return (g i) whenever (g i) is not false.
;; Return _FALSE_ if no such value is found.

(define (f n)
(let loop ((i 1))
(and (<= i n)
(or (g i)
(loop (add1 i))))))

Alternatively, using SRFI 42:

(define (f n)
(first-ec #f (: i 1 n) (g i)))

HTH,
David

Jens Axel Søgaard

2005-05-19, 8:58 pm

Patrick wrote:
> I'm curious to see how people do this kind of thing
> in Scheme since unlike C, it doesn't seem like you
> can just let control "fall out of the loop", break,
> or "force" a return from a function.

See
<http://schemecookbook.org/view/Cook...PrematureReturn>.

--=20
Jens Axel S=F8gaard

Patrick

2005-05-20, 4:00 pm

Jens Axel Søgaard wrote:
> Patrick wrote:
>
>
>
> See
> <http://schemecookbook.org/view/Cook...PrematureReturn>.
>

Wow, that seems to answer my question _exactly_.

Thanks to all respondents.

Sponsored Links