TSPL3: Wrong "or" definition?
Elena
I'm going through TSPL3 and, when talking about syntax definitions, we
are showed an incorrect definition of "or". I can't understand why
such definition does not work.
Here it is:
(define-syntax or ; incorrect!
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (or e2 ...))))))
I think this should work: the empty call returns #f, otherwise it
returns the first true value it finds. I've even fed such definition
to MzScheme and it seems to work.
What am I missing? Thanks.
Source: http://www.scheme.com/tspl3/further.html#./further:h1
Pascal J. Bourguignon
Check the correct version given just before.
The difference is in the processing of a single argument.
The wrong definition cannot deal with (or x),
therefore it cannot deal with (or #f ... #f x).
(_ e1 e2 ...) matches a form with at least two arguments.
--
__Pascal Bourguignon__
Nils M Holm
> Elena <egar...@gmail.com> writes:
>
> > Hi,
> >
> > I'm going through TSPL3 and, when talking about syntax definitions, we
> > are showed an incorrect definition of "or". I can't understand why
> > such definition does not work.
> >
> > Here it is:
> >
> > (define-syntax or ; incorrect!
> > (syntax-rules ()
> > ((_) #f)
> > ((_ e1 e2 ...)
> > (let ((t e1))
> > (if t t (or e2 ...))))))
> >
> > I think this should work: the empty call returns #f, otherwise it
> > returns the first true value it finds. I've even fed such definition
> > to MzScheme and it seems to work.
> >
> > What am I missing? Thanks.
> >
> > Source: http://www.scheme.com/tspl3/further.html#./further:h1
>
> Check the correct version given just before.
>
> The difference is in the processing of a single argument.
In fact, the second clause deals with single-argument OR just fine.
But try this with the working definition of OR and then with
the above one:
((lambda (x) (x x)) (lambda (x) (or #f (x x))))
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Jussi Piitulainen
It seem like this definition of (or (odd? (- x 1))) might
put (odd? (- x 1)) in a non-tail position, which is not good
in a definition of (odd? x).
Elena
> But try this with the working definition of OR and then with
> the above one:
>
> ((lambda (x) (x x)) (lambda (x) (or #f (x x))))
Both hang the interpreter. So does predefined "or".
Jussi Piitulainen
That's a herring. This is not about infinite loops. This is
about large finite loops.
Try these:
(define (broken-non-negative? x)
(or (zero? x) (broken-non-negative? (- x 1))))
(define (even-more-broken-non-negative? x)
(broken-or (zero? x) (even-more-broken-non-negative? (- x 1))))
(broken-non-negative? 1000000000)
(even-more-broken-non-negative? 1000000000)
I counted, slowly, to about 20 before the first call finished.
I counted, slowly, to about 30 before the second call finished.
The results were different.
Nils M Holm
> On Apr 15, 11:08 am, Nils M Holm <news2...@t3x.org> wrote:
> > But try this with the working definition of OR and then with
> > the above one:
> >
> > ((lambda (x) (x x)) (lambda (x) (or #f (x x))))
>
> Both hang the interpreter.
Yes, but in different ways. Wait for a while. Or expand both
versions and try to figure out the difference.
Mr.Cat
> Both hang the interpreter. So does predefined "or".
The `correct' or just hangs, but `broken' one slowly consumes
process's memory. You may see that in `top' or any othe kind of
process manager.
Follow Nils M Holm's advice - expand `(lambda (x) (x x)) (lambda (x)
(or #f (x x))))' for both `or's and notice, that for `broken' `or'
each iteration leaves an unevaluated `thunk'.
Mr.Cat
> Yes, but in different ways. Wait for a while. Or expand both
> versions and try to figure out the difference.
So, the `correct' `or' works better for inherently broken use cases?
Or are there any real-world examples where the `broken' `or' would be
inapplicable.
Elena
(define-syntax or ;; correct
(syntax-rules ()
((_) #f)
((_ e) e)
((_ e1 e2 e3 ...)
(let ((t e1))
(if t t (or e2 e3 ...))))))
(define-syntax or ;; incorrect!
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (or e2 ...))))))
are different. The last line should expand in the same way, except for
the last evaluation where the incorrect definition has one more
expansion (parens not checked):
(_ e1) ;; last element match
(let ((t e1))
(if t t (or))))))
Thanks
Derick Eddington
> Thank you all for your replies. Anyway, I can't still understand why:
>
> (define-syntax or ;; correct
> (syntax-rules ()
> ((_) #f)
> ((_ e) e)
> ((_ e1 e2 e3 ...)
> (let ((t e1))
> (if t t (or e2 e3 ...))))))
>
> (define-syntax or ;; incorrect!
> (syntax-rules ()
> ((_) #f)
> ((_ e1 e2 ...)
> (let ((t e1))
> (if t t (or e2 ...))))))
The reason the second definition is incorrect is one of the most
important things to learn about Scheme. As the R6RS specification of
`or' says: "The last <test> expression is in tail context if the `or'
expression itself is". I explain more below.
> are different. The last line should expand in the same way, except for
> the last evaluation where the incorrect definition has one more
> expansion (parens not checked):
>
> (_ e1) ;; last element match
> (let ((t e1))
> (if t t (or))))))
`e1' is not in tail-position. So, if the `e1' expression is a
procedure call, it is not a tail-call, and so it is not tail-
recursive, and so it does not use constant space. The procedure call
stack has to grow a new frame to evaluate the procedure call because
the call needs to return to the `let' binding continuation. Tail-
calls do not grow the stack because they don't need to. More
abstractly, say for some hypothetical non-stack-based machine, you can
think of it as: additional information must be remembered to know
where non-tail-calls must return to, but remembering additional
information is not required for tail-calls.
A real-world-type example of how the tail-call correctness of `or'
matters is:
> (define l (make-list #e1e7 123))
> (letrec-syntax
((or ;; correct
(syntax-rules ()
((_) #f)
((_ e) e)
((_ e1 e2 e3 ...)
(let ((t e1))
(if t t (or e2 e3 ...)))))))
(letrec
((list-of-numbers?
(lambda (x)
(or (null? x)
(and (pair? x)
(number? (car x))
(list-of-numbers? (cdr x)))))))
(time
(list-of-numbers? l))))
running stats for (list-of-numbers? l):
no collections
237 ms elapsed cpu time, including 0 ms collecting
255 ms elapsed real time, including 0 ms collecting
0 bytes allocated
#t
> (letrec-syntax
((or ;; incorrect
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (or e2 ...)))))))
(letrec
((list-of-numbers?
(lambda (x)
(or (null? x)
(and (pair? x)
(number? (car x))
(list-of-numbers? (cdr x)))))))
(time
(list-of-numbers? l))))
running stats for (list-of-numbers? l):
no collections
2565 ms elapsed cpu time, including 0 ms collecting
2631 ms elapsed real time, including 0 ms collecting
150699776 bytes allocated
#t
>
The reason for the memory allocation and longer time of the second
example is because the stack is growing for every call to `list-of-
numbers?' because the procedure calls itself recursively but it's
getting called in that `let' and so it's not tail-recursive. The more
recursions (in this example, the longer the list), the more stack
frames are needed.
Proper tail-recursion is not only important for computations which
return, but also for allowing designs where a program's main control
flow is based on infinitely tail-calling procedures. If the stack
continued to grow, all memory would be consumed. Proper tail-
recursion allows straightforward implementations of concepts which are
recursively defined, because you don't have to worry about running out
of memory no matter the amount of recursion.
Tail-calling has been called "goto" which passes arguments. That's
usually how it's implemented -- the current stack frame is overwritten
and reused for a tail-call, and this works because the old return
address of that frame is the same as needed for the new call. E.g.,
in `((lambda (f x) (f x)) - 1)' the call to `f' is a tail-call, which
means the value returned by `f' is the return value of the whole
expression, so the value can just be returned directly to the
continuation of the whole expression without growing a new unneeded
stack frame.
I recommend searching the R[56]RS for all these "tail" terms.
--
: Derick
----------------------------------------------------------------
Derick Eddington
wrote:
> Proper tail-
> recursion allows straightforward implementations of concepts which are
> recursively defined, because you don't have to worry about running out
> of memory no matter the amount of recursion.
P.S. That is an over-generalization. Many concepts which are
recursively defined cannot be implemented to take advantage of tail-
recursion. E.g., this does grow the stack:
(define (thing? x)
(or (number? x)
(and (pair? x)
(thing? (car x))
(thing? (cdr x)))))
--
: Derick
----------------------------------------------------------------
Shiro Kawai
call (the language specification requires it), and Scheme programmers
are used to count on such a property.
It's not a textbook exercise. Once I got a bug report to the
application I wrote at work, that the application crashed if it
ran very long time. It turned out one of my macro was incorrect
in terms of which expression must be evaluated in tail context.
The code that used the macro naturally used tail recursion to
loop, but it gradually consumed memory until the process ran
out of memory.
That said, a question came to my mind. I think the Scheme spec
doesn't prohibit a smart compiler from optimizing the code:
(let ((t <expr>)) (if t t #f))
into
<expr>
right? It doesn't REQUIRED to do so, thus the portable 'or'
can't count on this optimization, but when you write an 'or'
macro to a specific implementation that you know does this
optimization, the OP's macro is correct, isn't it?
--shiro
Nils M Holm
> Or are there any real-world examples where the `broken' `or' would be
> inapplicable.
Yes, there are. See Jussi Piitulainen's posting elsewhere in this thread
or the example in TSPL3.
Nils M Holm
> Mr.Cat <abakh...@gmail.com> wrote:
> > Or are there any real-world examples where the `broken' `or' would be
> > inapplicable.
>
> Yes, there are. See Jussi Piitulainen's posting elsewhere in this thread
> or the example in TSPL3.
Of course you may consider the broken-non-negative? and even?/odd?
examples as broken use cases, too, so here is a more real-world one
(note that is based on the same principles as the other examples,
though):
(define-syntax wrong-or
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (wrong-or e2 ...))))))
(define (iota l h)
(letrec
((j (lambda (x r)
(if (= x l)
(cons l r)
(j (- x 1) (cons x r))))))
(j h '())))
(define (memv? x a)
(if (null? a)
#f
(or (eqv? x (car a))
(memv? x (cdr a)))))
(define (wrong-memv? x a)
(if (null? a)
#f
(wrong-or (eqv? x (car a))
(wrong-memv? x (cdr a)))))
At least on my system,
(memv? x (iota 0 x))
works fine, while
(wrong-memv? x (iota 0 x))
takes ages for sufficiently large values of x.
Abdulaziz Ghuloum
On Apr 16, 6:44 am, Shiro Kawai <shiro.ka...@gmail.com> wrote:
> That said, a question came to my mind. I think the Scheme spec
> doesn't prohibit a smart compiler from optimizing the code:
>
> (let ((t <expr>)) (if t t #f))
>
> into
>
> <expr>
>
> right?
This transformation is correct provided that <expr> returns
a single value. If the semantics of returning an incorrect
number of values require raising an exception, the
transformation above may mask it. E.g.,
Before transformation:
(let-values ([(x y) (let ([t (values 1 2)]) (if t t #f))])
(+ x y)) ;=> error
After transformation:
(let-values ([(x y) (values 1 2)])
(+ x y)) ;=> 3
> It doesn't REQUIRED to do so, thus the portable 'or'
> can't count on this optimization, but when you write an 'or'
> macro to a specific implementation that you know does this
> optimization, the OP's macro is correct, isn't it?
That's an example of two bugs canceling one another. :-)
Aziz,,,
Shiro Kawai
> [Sorry if this appears twice]
> On Apr 16, 6:44 am, Shiro Kawai <shiro.ka...@gmail.com> wrote:
>
> > That said, a question came to my mind. I think the Scheme spec
> > doesn't prohibit a smart compiler from optimizing the code:
>
> > (let ((t <expr>)) (if t t #f))
>
> > into
>
> > <expr>
>
> > right?
>
> This transformation is correct provided that <expr> returns
> a single value. If the semantics of returning an incorrect
> number of values require raising an exception, the
> transformation above may mask it. E.g.,
Ah, right! Thanks for the explanation.
So the above transformation is only allowed if the compiler
can see outer context, but not possible locally.
--shiro
Elena
I did know about TCO, but I didn't realize it would interact with
macro writing too.
To understand such issue better, I've expanded both macros by hand (I
couldn't understand DrScheme Macro Stepper's output) in a really dumb
call. Does that show your point?
;;;; Really dumb recursive function.
(define (g)
(or (f) (g)))
;;;; Well-behaved "or" expansion.
(define (g)
(let ((t (f)))
(if t
t
(g)))) ;; tail call
;;;; Broken "or" expansion.
(define (g)
(let ((t (f)))
(if t
t
(let ((t (g))) ;; non tail call
(if t
t
#f)))))
Michele Simionato
> To understand such issue better, I've expanded both macros by hand (I
> couldn't understand DrScheme Macro Stepper's output) in a really dumb
> call.
BTW, for people not using DrScheme, I should perhaps notice that my
sweet-macros
library provide some facility to expand macros. The facility is
intended to be
minimal (it expands only one level) and should work portably for all
R6RS
implementations.
For instance, I just tried this script and it works with mzscheme:
#!r6rs
(import (rnrs) (sweet-macros))
(def-syntax or_
(syntax-rules ()
((or_) #f)
((or_ e1 e2 ...) (let ((t e1)) (if t t (or_ e2 ...))))))
(display (syntax-expand (or_ (f) (g)))) ;=> {let {{t {f}}} {if t t
{or_ {g}}}}
(display (syntax-expand (or_ (g)))); => {let {{t {g}}} {if t t {or_}}}
You can find a description of the library starting from episode #9
of my Adventures: http://www.artima.com/weblogs/viewpost.jsp?thread=251474
M. Simionato
Mr.Cat
> This transformation is correct provided that <expr> returns
> a single value. If the semantics of returning an incorrect
> number of values require raising an exception, the
> transformation above may mask it. E.g.,
Good point, but scheme does not require raising an exception for
incorrect number of values, iirc.
Abdulaziz Ghuloum
> That said, a question came to my mind. I think the Scheme spec
> doesn't prohibit a smart compiler from optimizing the code:
>
> (let ((t <expr>)) (if t t #f))
>
> into
>
> <expr>
>
> right?
This transformation is correct provided that <expr> returns
a single value. If the semantics of returning an incorrect
number of values require raising an exception, the
transformation above may mask it. E.g.,
Before transformation:
(let-values ([(x y) (let ([t (values 1 2)]) (if t t #f))])
(+ x y)) ;=> error
After transformation:
(let-values ([(x y) (values 1 2)])
(+ x y)) ;=> 3
> It doesn't REQUIRED to do so, thus the portable 'or'
> can't count on this optimization, but when you write an 'or'
> macro to a specific implementation that you know does this
> optimization, the OP's macro is correct, isn't it?
That's an example of two bugs canceling one another. :-)
Aziz,,,
Derick Eddington
> I did know about TCO, but I didn't realize it would interact with
> macro writing too.
The source-code produced after all macro expansion is finished is what
is analyzed for TCO. Macros just transform source-code, so it's up to
you to determine what the resulting source-code is/does.
> To understand such issue better, I've expanded both macros by hand (I
> couldn't understand DrScheme Macro Stepper's output) in a really dumb
> call. Does that show your point?
>
> ;;;; Really dumb recursive function.
> (define (g)
> (or (f) (g)))
>
> ;;;; Well-behaved "or" expansion.
> (define (g)
> (let ((t (f)))
> (if t
> t
> (g)))) ;; tail call
>
> ;;;; Broken "or" expansion.
> (define (g)
> (let ((t (f)))
> (if t
> t
> (let ((t (g))) ;; non tail call
> (if t
> t
> #f)))))
Yeah, that's the issue.
DrScheme's "Check Syntax" is useful for showing tail-positions. Do
"Check Syntax" on an open file and then hover the mouse pointer over
the beginning parenthesis of expressions, and if an expression is in
tail-position, arrows will be drawn to and from its corresponding
other tail-expressions. If you right-click, you can make the arrows
stay.
--
: Derick
----------------------------------------------------------------
Abdulaziz Ghuloum
I said "if the semantics ...", and that applies to:
1. R6RS implementations since the R6RS does require it.
2. A good number of R5RS implementations that also detect and
report such errors even though the R5RS does not require it.
Aziz,,,
Mr.Cat
> 1. R6RS implementations since the R6RS does require it.
Iirc this requirement only applies to call-with-values.
Abdulaziz Ghuloum
That's incorrect.
Aziz,,,
Mr.Cat
wrote:
> That's incorrect.
What I see in r6rs is:
> ... continuations implicitly accepting a single value, such as the continuations of <operator> and <operand>s of procedure calls or the <test> expressions in conditionals, take exactly one value. The effect of passing an inappropriate number of values to such a continuation is undefined...
Since `(let ((x expr)) body)' is essentially `((lambda (x) body)
(expr))', `expr' is in operand position. So, though its continuation
takes one value, the effect of passing more that one is undefined.
Is that incorrect?
Abdulaziz Ghuloum
> What I see in r6rs is:
>
>> ... continuations implicitly accepting a single value, such
>> as the continuations of <operator> and <operand>s of procedure
>> calls or the <test> expressions in conditionals, take exactly
>> one value. The effect of passing an inappropriate number of
>> values to such a continuation is undefined...
>
> Since `(let ((x expr)) body)' is essentially `((lambda (x) body)
> (expr))', `expr' is in operand position. So, though its continuation
> takes one value, the effect of passing more that one is undefined.
>
> Is that incorrect?
That's correct, and I stand corrected. Though, the meaning of
"undefined behavior" does not seem to be defined or explained
in the document.
Aziz,,,
Derick Eddington
description of the practical advantages of tail-call optimization,
including advantages not mentioned in this thread.
http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html