Scheme - Something works on its own but not inside a lambda

Author

Something works on its own but not inside a lambda

Spiros Bousbouras

2007-11-19, 7:19 pm

Hi folks

I'm learning Scheme and I encountered a surprising behaviour.
I was writing a function which accepts as argument a positive
integer n and returns the nth term of the Fibonacci sequence.
(So numbering of terms is assumed to start from 1)

This was one effort:

(define fib-impr
(lambda (n)
(if (< n 3)
1
(begin
(define fib-aux
(lambda (previous-term current-term counter)
(if (< counter n)
(fib-aux current-term (+ previous-term current-term) (+
1 counter))
current-term)))
(fib-aux 1 2 3)))))

This seemed reasonable to me and Guile accepts the definition
but when I try

guile> (fib-impr 4)
standard input:448:9: In expression (define fib-aux (lambda # #)):
standard input:448:9: Bad define placement
ABORT: (misc-error)

I tried some experiments

guile> (define n 4)
guile> (if (< n 3)
1
(begin
(define fib-aux
(lambda (previous-term current-term counter)
(if (< counter n)
(fib-aux current-term (+ previous-term
current-term) (+ 1 counter))
current-term)))
(fib-aux 1 2 3)))
3

Works correctly. But if I put it inside a lambda as in

guile>
((lambda (n)
(if (< n 3)
1
(begin
(define fib-aux
(lambda (previous-term current-term counter)
(if (< counter n)
(fib-aux current-term (+ previous-term current-term) (+ 1
counter))
current-term)))
(fib-aux 1 2 3))))
4)
standard input:266:17: In expression (define fib-aux (lambda # #)):
standard input:266:17: Bad define placement
ABORT: (misc-error)

So why is it that the part
(if (< n 3)
......................
(fib-aux 1 2 3)))

works on its own but not inside a lambda ?

In the end I did

(define fib-impr
(lambda (n)
(define fib-aux
(lambda (previous-term current-term counter)
(if (< counter n)
(fib-aux current-term (+ previous-term current-term) (+ 1
counter))
current-term)))
(if (< n 3)
1
(fib-aux 1 2 3))))

This worked but it annoys me from an aesthetical point of
view that I define fib-aux although I may not need it.

Jussi Piitulainen

2007-11-19, 7:19 pm

Spiros Bousbouras writes:

> This was one effort:
>
> (define fib-impr
> (lambda (n)
> (if (< n 3)
> 1
> (begin
> (define fib-aux
> (lambda (previous-term current-term counter)
> (if (< counter n)
> (fib-aux current-term (+ previous-term current-term) (+
> 1 counter))
> current-term)))
> (fib-aux 1 2 3)))))
>
> This seemed reasonable to me and Guile accepts the definition

I don't think that's defined, according to R5RS. There are two kinds
of `begin' there: one containing definitions that can occur where a
definition can occur, and one containing expressions that can occur
where expressions can occur. Your problem is that a `begin' expression
does not contain a "body", unlike a `lambda' expression. A body begins
with definitions, followed by expressions.

You could say

(let ()
(define fib-aux (lambda (...) ...))
(fib-aux 1 2 3))

and that should work the way you expect. Or you could use letrec
directly:

(letrec ((fib-aux (lambda (...) ...)))
(fib-aux 1 2 3))

There is also a special construction often called "named let" that
fits here, since you are defining and immediately calling a single
procedure:

(let fib-aux ((previous-term 1)
(current-term 2)
(counter 3))
...)

The differences between `let' variants are subtle and important.

> This worked but it annoys me from an aesthetical point of
> view that I define fib-aux although I may not need it.

It doesn't annoy me. Happily, you can get what you want, as above.

Kjetil S. Matheussen

2007-11-19, 7:19 pm

On Mon, 19 Nov 2007, Spiros Bousbouras wrote:

> Hi folks
>
> I'm learning Scheme and I encountered a surprising behaviour.
> I was writing a function which accepts as argument a positive
> integer n and returns the nth term of the Fibonacci sequence.
> (So numbering of terms is assumed to start from 1)
>
> This was one effort:
>
> (define fib-impr
> (lambda (n)
> (if (< n 3)
> 1
> (begin
> (define fib-aux
> (lambda (previous-term current-term counter)
> (if (< counter n)
> (fib-aux current-term (+ previous-term current-term) (+
> 1 counter))
> current-term)))
> (fib-aux 1 2 3)))))
>
> This seemed reasonable to me and Guile accepts the definition
> but when I try
>
> guile> (fib-impr 4)
> standard input:448:9: In expression (define fib-aux (lambda # #)):
> standard input:448:9: Bad define placement
> ABORT: (misc-error)

Its just a stupid (IMO) restriction in scheme.

You can write it like this instead:

(define fib-impr
(lambda (n)
(if (< n 3)
1
(let ()
(define fib-aux
(lambda (previous-term current-term counter)
(if (< counter n)
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))
current-term)))
(fib-aux 1 2 3)))))

You can also write it like this:

(define (fib-impr n)
(if (< n 3)
1
(let fib-aux ((previous-term 1)
(current-term 2)
(counter 3))
(if (< counter n)
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))
current-term)))))

I would write it like this though:

(define (fib-impr n)
(define (fib-aux previous-term current-term counter)
(if (= counter n)
current-term
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))))
(if (< n 3)
1
(fib-aux 1 2 3)))

Or perhaps like this:

(define (fib-impr n)
(let fib-aux ((previous-term 1)
(current-term 2)
(counter 3))
(cond ((< n 3) 1)
((= counter n) current-term)
(else
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))))))

Spiros Bousbouras

2007-11-20, 8:17 am

On Nov 19, 4:29 pm, "Kjetil S. Matheussen" <k.s.matheus...@notam02.no>
wrote:
> On Mon, 19 Nov 2007, Spiros Bousbouras wrote:
>
>
>
>
>
>
> Its just a stupid (IMO) restriction in scheme.

Thanks , I was wondering what was the point of the restriction.

> You can write it like this instead:
>
> (define fib-impr
> (lambda (n)
> (if (< n 3)
> 1
> (let ()
> (define fib-aux
> (lambda (previous-term current-term counter)
> (if (< counter n)
> (fib-aux current-term
> (+ previous-term current-term)
> (+ 1 counter))
> current-term)))
> (fib-aux 1 2 3)))))
>
> You can also write it like this:
>
> (define (fib-impr n)
> (if (< n 3)
> 1
> (let fib-aux ((previous-term 1)
> (current-term 2)
> (counter 3))
> (if (< counter n)
> (fib-aux current-term
> (+ previous-term current-term)
> (+ 1 counter))
> current-term)))))
>
> I would write it like this though:
>
> (define (fib-impr n)
> (define (fib-aux previous-term current-term counter)
> (if (= counter n)
> current-term
> (fib-aux current-term
> (+ previous-term current-term)
> (+ 1 counter))))
> (if (< n 3)
> 1
> (fib-aux 1 2 3)))
>
> Or perhaps like this:
>
> (define (fib-impr n)
> (let fib-aux ((previous-term 1)
> (current-term 2)
> (counter 3))
> (cond ((< n 3) 1)
> ((= counter n) current-term)
> (else
> (fib-aux current-term
> (+ previous-term current-term)
> (+ 1 counter))))))

Should any of the above methods be preferred for reasons
of speed or whatever ?

Kjetil S. Matheussen

2007-11-20, 7:18 pm

On Tue, 20 Nov 2007, Spiros Bousbouras wrote:

> On Nov 19, 4:29 pm, "Kjetil S. Matheussen" <k.s.matheus...@notam02.no>
> wrote:
>
> Thanks , I was wondering what was the point of the restriction.
>

Well, the official reason for the restriction is not to
make scheme stupid. :-) But some scheme implementations,
dependent on the implementation, needs to do some extra source
transformations without this restrictions, plus that its not
always obvious how the programs should behave either without
the restriction. But from a users point of view, its
a rediculous restriction.

>
> Should any of the above methods be preferred for reasons
> of speed or whatever ?
>

The first one is probably faster in most implementations, if thats
extremely important. Many might find the second one faster to read,
because all the if-s are gathered into one cond.

William D Clinger

2007-11-20, 7:18 pm

Concerning

(define (fib-impr1 n)
(define (fib-aux previous-term current-term counter)
(if (= counter n)
current-term
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))))
(if (< n 3)
1
(fib-aux 1 2 3)))

(define (fib-impr2 n)
(let fib-aux ((previous-term 1)
(current-term 2)
(counter 3))
(cond ((< n 3) 1)
((= counter n) current-term)
(else
(fib-aux current-term
(+ previous-term current-term)
(+ 1 counter))))))

Spiros Bousbouras asked:
> Should any of the above methods be preferred for reasons
> of speed or whatever ?

Kjetil S. Matheussen replied:
> The first one is probably faster in most implementations, if thats
> extremely important. Many might find the second one faster to read,
> because all the if-s are gathered into one cond.

The first one's faster because it pulls the (< n 3) test
out of the main loop. How much faster depends on the
implementation, of course. I was curious.

Timings in seconds on a four-year-old Linux machine:

(fib-impr1 40) (fib-impr2 40) ratio

MzScheme v370 [3m] .000000249 .000000269 .93
Larceny v0.95 .000000318 .000000361 .88
Ikarus v0.0.1 .000000325 .000000378 .86
Gambit 4.0b22 .000000394 .000000410 .96
Bigloo 3.0a .000000631 .000000891 .71
MIT Scheme .000001120 .000001130 .99
Chicken 2.6 .000001723 .000001716 1.00
Petite Chez 7.3 .000015906 .000026497 .60
Scheme 48 1.3 .000044320 .000057190 .77
Kawa 1.9.1 .000053434 .000061697 .87

Will

Sponsored Links