Paren-off macro

0 views
Skip to first unread message

zhaoway

unread,
Mar 6, 2003, 12:07:31 PM3/6/03
to
I find I need a paren-off macro. Like this,

(define-syntax paren-off
(syntax-rules ()
((_ (a ...))
a ...)))

The above code is wrong. But hopefully you get the idea. Can I do this
in a simple way, either as functions or as macros. For example, I
often need a function append-list-member, which really should be this
simple,

(define (append-list-member lis)
(append (paren-off lis)))

Please give me some ideas! Thank you!

Joe Marshall

unread,
Mar 6, 2003, 1:07:40 PM3/6/03
to
z...@netspeed-tech.com (zhaoway) writes:

> I find I need a paren-off macro....

There is no such thing (nor could there be). What are you trying to
accomplish?

> (define-syntax paren-off
> (syntax-rules ()
> ((_ (a ...))
> a ...)))
>
> The above code is wrong. But hopefully you get the idea.

Um, no, I don't.

> Can I do this
> in a simple way, either as functions or as macros. For example, I
> often need a function append-list-member, which really should be this
> simple,
>
> (define (append-list-member lis)
> (append (paren-off lis)))

Is this attempting to `flatten' one level of a list? Try this:

> (foldr append '() '((this is) (a) (test list)))
(this is a test list)

Lauri Alanko

unread,
Mar 6, 2003, 1:18:14 PM3/6/03
to
Joe Marshall <j...@ccs.neu.edu> quoth:

> > (define (append-list-member lis)
> > (append (paren-off lis)))
>
> Is this attempting to `flatten' one level of a list? Try this:
>
> > (foldr append '() '((this is) (a) (test list)))
> (this is a test list)

Uh? Is this somehow preferable to the usual (apply append list-of-lists)?


Lauri Alanko
l...@iki.fi

Joe Marshall

unread,
Mar 6, 2003, 2:56:33 PM3/6/03
to
Lauri Alanko <l...@iki.fi> writes:

Probably not. I do a lot of common lisp hacking and apply is not
guaranteed to work on extremely large argument lists, so I tend to use
foldr or reduce when I want to reduce a list of objects.

Jeffrey Mark Siskind

unread,
Mar 6, 2003, 6:15:29 PM3/6/03
to
Joe Marshall <j...@ccs.neu.edu> wrote in message news:<of4otg...@ccs.neu.edu>...

There are other reasons why you want to use fold rather than apply.
apply
only works when the procedure you are applying takes a variable number
of
arguments. And it assumes that it is defined to do a fold on those
arguments.
Apply doesn't specify the associativity of the fold.Or the identity of
the
fold. So if you are teaching the concept of folding an arbitrary
binary procedure (with specified associativity and identity) then you
want to teach
fold, not apply. And if you want your code to take an arbitrary binary
procedure as a higher-order argument then you want to use fold, not
apply.

There are situations where you want/need to use apply. But simulating
fold
is not one of them.

Jeffrey M. Vinocur

unread,
Mar 8, 2003, 1:00:52 AM3/8/03
to
In article <a520654a.03030...@posting.google.com>,
Jeffrey Mark Siskind <qo...@purdue.edu> wrote:

>> Lauri Alanko <l...@iki.fi> writes:
>>
>> > > > (foldr append '() '((this is) (a) (test list)))
>> >
>> > Uh? Is this somehow preferable to the usual (apply append list-of-lists)?

[ rewrapping...might want to check your line lenths ]

>There are other reasons why you want to use fold rather than
>apply. apply only works when the procedure you are applying
>takes a variable number of arguments. And it assumes that it is
>defined to do a fold on those arguments. Apply doesn't specify
>the associativity of the fold.Or the identity of the fold.

Indeed. But these are properties which often are obvious from
the function in question; I don't think anyone would argue that
(append '()) should return something other than the empty list,
or that the associativity of n-ary append doesn't follow
immediately from the specification for binary append.


>So if you are teaching the concept of folding an arbitrary
>binary procedure (with specified associativity and identity)
>then you want to teach fold, not apply.

There's no arguing that folding is an important concept to teach.
But that doesn't make a good reason to use it instead of apply,
in general.


>And if you want your code to take an arbitrary binary procedure
>as a higher-order argument then you want to use fold, not apply.

True. But not relevant to the case in question.


>There are situations where you want/need to use apply. But
>simulating fold is not one of them.

There is *no* convincing reason to use fold here.

And there *is* a convincing reason to use apply: I can trust the
designer of append to have worked out the optimal associtivity,
whereas to use fold I have to stop and make sure I choose the
correct one.

Another reason: In the absence of any indication for the
contrary, I would definitely prefer giving append all of the
arguments at once instead of one by one. Suppose the compiler
can optimize some aspect of memory allocation by knowing the
final size of the list in advance -- you'd eliminate that
optimization for what benefit?

--
Jeffrey M. Vinocur * jm...@cornell.edu
http://www.people.cornell.edu/pages/jmv16/

Joe Marshall

unread,
Mar 10, 2003, 9:58:04 AM3/10/03
to
jm...@cornell.edu (Jeffrey M. Vinocur) writes:

> There is *no* convincing reason to use fold here.
>
> And there *is* a convincing reason to use apply: I can trust the

> designer of append to have worked out the optimal associativity,


> whereas to use fold I have to stop and make sure I choose the
> correct one.

I disagree completely. With FOLDR, you are operating on the top level
list using list operations. With APPLY, you are operating on the top
level list using argument spreading and the n-ary function mechanism.
There is no reason to assume that this latter is `optimal'.

> Another reason: In the absence of any indication for the
> contrary, I would definitely prefer giving append all of the
> arguments at once instead of one by one. Suppose the compiler
> can optimize some aspect of memory allocation by knowing the
> final size of the list in advance -- you'd eliminate that
> optimization for what benefit?

Why do you think that the compiler could not have knowledge of how to
efficiently compile FOLDR?

I have to agree with Jeffrey Mark Siskind. FOLDR is a higher order
procedure for reducing lists, and that is exactly what the original
poster is attempting to do.

Lauri Alanko

unread,
Mar 10, 2003, 1:48:14 PM3/10/03
to
Joe Marshall <j...@ccs.neu.edu> quoth:

> I have to agree with Jeffrey Mark Siskind. FOLDR is a higher order
> procedure for reducing lists, and that is exactly what the original
> poster is attempting to do.

Maybe we could quit bickering and just state that the Right Thing is to
use SRFI-1 and (concatenate '((this) (bloody) (list of things))) ?


Lauri Alanko
l...@iki.fi

Jeffrey M. Vinocur

unread,
Mar 10, 2003, 5:33:54 PM3/10/03
to
In article <vfyrs1...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu> wrote:
>jm...@cornell.edu (Jeffrey M. Vinocur) writes:
>
>> And there *is* a convincing reason to use apply: I can trust the
>> designer of append to have worked out the optimal associativity,
>> whereas to use fold I have to stop and make sure I choose the
>> correct one.
>
>I disagree completely. With FOLDR, you are operating on the top level
>list using list operations. With APPLY, you are operating on the top
>level list using argument spreading and the n-ary function mechanism.
>There is no reason to assume that this latter is `optimal'.

But there is...assuming the designer is not out of his mind. We
know (append '(1) '(2)) ==> (1 2) and which to predict what
(append '(1) '(2) '(3)) will return. Now, you've got six
possibilities, and I can't see how you can possibly make a case
for any but (1 2 3).

And of course, the specification indicates that this is the case.


>> Another reason: In the absence of any indication for the
>> contrary, I would definitely prefer giving append all of the
>> arguments at once instead of one by one.
>

>Why do you think that the compiler could not have knowledge of how to
>efficiently compile FOLDR?

When the input function can have arbitrary behavior? Now, it's
Scheme, so we probably don't have to be concerned about separate
compilation. So it's *possible* the compiler could do some
optimization on this particular call to foldr, although I would
be very impressed.

But it doesn't matter! Since append is provided by the
implementation, we can expect that it will be written optimally
for the general case. So if, in general, the best way to
implement n-ary append is with a call to foldr, then the library
append should have done it that way.

(Yes, it's possible that the library is implemented naievly and
doesn't make use of something that would improve perfomance. But
unless you're *sure* that this is the case, and are additionally
*sure* that the slowdown is significantly impairing your program,
there's no reason to rewrite a library function, and in fact I'd
consider it inappropriate to do so.)


>I have to agree with Jeffrey Mark Siskind. FOLDR is a higher order
>procedure for reducing lists, and that is exactly what the original
>poster is attempting to do.

I just don't get this. You have a tool designed for appending
lists together, and you won't use it.

Do you refuse to use map and filter because they can be written
with foldr as well?

Jeffrey Mark Siskind

unread,
Mar 10, 2003, 6:20:58 PM3/10/03
to
> > I have to agree with Jeffrey Mark Siskind. FOLDR is a higher order
> > procedure for reducing lists, and that is exactly what the original
> > poster is attempting to do.
>
> Maybe we could quit bickering and just state that the Right Thing is to
> use SRFI-1 and (concatenate '((this) (bloody) (list of things))) ?

No. You miss my point. The concatenate procedure in SRFI-1 might be
appropriate in this limited situation. But it is not the Right Thing in
a broader sense. The notion of fold or reduction pervades mathematics.And it
pervades clean thinking about programming. Today you might want to fold append
over a list. Tomorrow you might need to change that to folding union over a
list. Using fold exposes the underlying notion and makes such a change possible.
apply and concatenate do not.

Notions like mapping, folding, set comprehensions, bounded quantification, and
nondeterminism allow one to write code that transparently reflects the underlying
mathematical concepts and fosters clean thinking.

Joe Marshall

unread,
Mar 11, 2003, 10:24:36 AM3/11/03
to

I don't have a problem with APPEND, I have a problem with using
APPLY. APPLY isn't designed to append lists together.

> >> And there *is* a convincing reason to use apply: I can trust the
> >> designer of append to have worked out the optimal associativity,
> >> whereas to use fold I have to stop and make sure I choose the
> >> correct one.
>

> >There is no reason to assume that this latter is `optimal'.
>
> But there is...assuming the designer is not out of his mind. We
> know (append '(1) '(2)) ==> (1 2) and which to predict what
> (append '(1) '(2) '(3)) will return. Now, you've got six
> possibilities, and I can't see how you can possibly make a case
> for any but (1 2 3).
>
> And of course, the specification indicates that this is the case.

I wasn't questioning the result, I was questioning the assertion of
`optimal'. We have two alternatives:

(FOLDR APPEND '() LIST-OF-LISTS)
vs.
(APPLY APPEND LIST-OF-LISTS)

In the APPLY case, the LIST-OF-LISTS is `spread' on the stack as
N-arguments to APPEND. APPEND, being an N-ARY function, then conses a
`rest' argument that is virtually identical in structure to the
list-of-lists we just spread.

FOLDR calls the given function on exactly 2 arguments each time. One
can't generalize, but it doesn't seem unreasonable that operating on a
fixed number of arguments might be more `optimal' than operating on an
arbitrary number.

> >Why do you think that the compiler could not have knowledge of how to
> >efficiently compile FOLDR?
>
> When the input function can have arbitrary behavior? Now, it's
> Scheme, so we probably don't have to be concerned about separate
> compilation. So it's *possible* the compiler could do some
> optimization on this particular call to foldr, although I would
> be very impressed.

MIT-Scheme defines FOLD-RIGHT as follows:

(define (fold-right procedure initial-value list)
(let fold ((list list))
(cond ((pair? list) (procedure (car list) (fold (cdr list))))
((null? list) initial-value)
(else (error:wrong-type-argument list "list")))))

There's no reason why fold-right could not be inlined during
compilation (if one promises not to redefine it). The relevant call
ends up being (append (car list) (fold (cdr list))). I can't see
how a call to apply could be compiled any more efficiently.

Jeffrey M. Vinocur

unread,
Mar 14, 2003, 4:34:56 PM3/14/03
to
In article <heaark...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu> wrote:
>
>I don't have a problem with APPEND, I have a problem with using
>APPLY. APPLY isn't designed to append lists together.

Oh, I see your problem.

I don't think of APPLY in the same way you do, I think. In my
mind, the distinction between passing n separate arguments and a
list of n elements is just syntax. If every function call had to
be done with APPLY and a list of arguments, we wouldn't be having
this discussion. I mean, do you have a problem with using
(apply + l) to sum a list of numbers, because APPLY isn't
designed for arithmetic?

Hmm. Suppose that instead of needing APPLY, we had primitive
syntax, so (+ . l) would sum a list of numbers. Would you have a
problem with (define (concat ll) (append . ll)), then? I
certainly wouldn't, and I don't consider using APPLY to be
substantially different.

>FOLDR calls the given function on exactly 2 arguments each time. One
>can't generalize, but it doesn't seem unreasonable that operating on a
>fixed number of arguments might be more `optimal' than operating on an
>arbitrary number.

True. But the library-designers-are-right-until-proven-wrong
argument still holds; if the FOLDR solution is optimal, then we
should expect the library append to be written as

(define (append . ll)
(define (binary-append l1 l2)
...)
(foldr binary-append '() ll))


>There's no reason why fold-right could not be inlined during
>compilation (if one promises not to redefine it).

That's not the optimization I'm worried about at all.


>The relevant call ends up being (append (car list) (fold (cdr
>list))). I can't see how a call to apply could be compiled any
>more efficiently.

It's a bit of a reach in this case (although I can contrive some
things if I try hard enough), but consider the equivalent case of
concatenating a bunch of immutable, array-representation,
strings. (At least, I think it's equivalent; let me know if you
disagree.)

But (foldr binary-concat "" stringlist) has O(n^2) runtime, and
(apply nary-concat stringlist) has O(n) runtime if written
correctly.

be...@sonic.net

unread,
Mar 14, 2003, 8:28:14 PM3/14/03
to
"Jeffrey M. Vinocur" wrote:
>
> In article <heaark...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu> wrote:
> >
> >I don't have a problem with APPEND, I have a problem with using
> >APPLY. APPLY isn't designed to append lists together.
>
> Oh, I see your problem.
>
> I don't think of APPLY in the same way you do, I think. In my
> mind, the distinction between passing n separate arguments and a
> list of n elements is just syntax. If every function call had to
> be done with APPLY and a list of arguments, we wouldn't be having
> this discussion. I mean, do you have a problem with using
> (apply + l) to sum a list of numbers, because APPLY isn't
> designed for arithmetic?


It's not quite the same. Lists of arguments use up cons cells,
which have to be garbage-collected. Direct calls to routines
that have a fixed number of arguments do not.

well ... whether they do or not depends on the compiler, to
be pedantic. But in most systems a function call does not
require cons cells to be allocated and, later, reaped, whereas
in most systems a call to apply will use cons cells.

OTOH, if the compiler can *prove* that the list you're passing
isn't used as an actual list anywhere, it can take your call
to apply and compile it as though it had been a direct call
with explicit arguments.

Bear

Abdulaziz Ghuloum

unread,
Mar 14, 2003, 11:51:52 PM3/14/03
to
Jeffrey M. Vinocur wrote:
> In article <heaark...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu> wrote:
>
>>I don't have a problem with APPEND, I have a problem with using
>>APPLY. APPLY isn't designed to append lists together.
>
>
> Oh, I see your problem.
>
> I don't think of APPLY in the same way you do, I think. In my
> mind, the distinction between passing n separate arguments and a
> list of n elements is just syntax. If every function call had to
> be done with APPLY and a list of arguments, we wouldn't be having
> this discussion. I mean, do you have a problem with using
> (apply + l) to sum a list of numbers, because APPLY isn't
> designed for arithmetic?
>
> Hmm. Suppose that instead of needing APPLY, we had primitive
> syntax, so (+ . l) would sum a list of numbers. Would you have a
> problem with (define (concat ll) (append . ll)), then? I
> certainly wouldn't, and I don't consider using APPLY to be
> substantially different.
> [...]

But it *is* different. apply (as stated like ten times so far in this
thread) takes a list and spreads it on the stack (and parameter
registers if any). (lambda args ...) creates a new list (see R5RS
section 4.1.4). So, if you have a function binary-plus and would like
to define a procedure arb-plus, you have many options:

(define arb-plus
(lambda args
(let loop ((ls args) (sum 0))
(if (null? ls)
sum
(loop (cdr args) (binary-plus (car args) sum))))))

which uses a constant stack and heap space. Or

(define arb-plus
(lambda args
(foldl binary-plus 0 args)))

which uses constant stack and (length args) heap. Or

(define arb-plus
(lambda args
(foldr binary-plus 0 args)))

which uses (length args) stack and constact heap. But you certainly
would not define it as:

(define arb-plus
(lambda args
(if (null? args)
0
(binary-plus (car args) (apply arb-plus (cdr args))))))

which although does not use more than (length n) stack and heap at the
same time, it does O(N^2) copies from the stack to the heap and back.
So, the distinction between a normal function call and using apply, and
the distinction between (lambda (a0 ...) ...) and (lambda args ...) is
more than syntactic as you mentioned at the beginning of your post.

Aziz,,,

Joe Marshall

unread,
Mar 18, 2003, 11:02:49 AM3/18/03
to
jm...@cornell.edu (Jeffrey M. Vinocur) writes:

> In article <heaark...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu> wrote:
> >
> >I don't have a problem with APPEND, I have a problem with using
> >APPLY. APPLY isn't designed to append lists together.
>
> Oh, I see your problem.
>
> I don't think of APPLY in the same way you do, I think. In my
> mind, the distinction between passing n separate arguments and a
> list of n elements is just syntax. If every function call had to
> be done with APPLY and a list of arguments, we wouldn't be having
> this discussion. I mean, do you have a problem with using
> (apply + l) to sum a list of numbers, because APPLY isn't
> designed for arithmetic?
>
> Hmm. Suppose that instead of needing APPLY, we had primitive
> syntax, so (+ . l) would sum a list of numbers. Would you have a
> problem with (define (concat ll) (append . ll)), then? I
> certainly wouldn't, and I don't consider using APPLY to be
> substantially different.

Yes, I wouldn't write either of these in this way.

Here is an example of where I think APPLY is the correct thing to use:

(define (clr-marshaled com-function)
(lambda (object method . args)
(marshal-from-com
(apply com-function
(clr-object->com-object object)
method
(map marshal-to-com args)))))

(This is part of a .NET wrapper I'm writing for MzScheme where the .NET
objects are represented by COM objects.) The salient point is that
I'm abstracting away the arity of the com-function by using rest
arguments and apply.

> But (foldr binary-concat "" stringlist) has O(n^2) runtime, and
> (apply nary-concat stringlist) has O(n) runtime if written
> correctly.

True. If I were worried about this I wouldn't use APPLY *or* FOLDR,
though. I'd roll my own.

Eli Barzilay

unread,
Mar 18, 2003, 12:19:09 PM3/18/03
to
Joe Marshall <j...@ccs.neu.edu> writes:

> Here is an example of where I think APPLY is the correct thing to use:
>
> (define (clr-marshaled com-function)
> (lambda (object method . args)
> (marshal-from-com
> (apply com-function
> (clr-object->com-object object)
> method
> (map marshal-to-com args)))))

One approach which is used by the PLT object system (I think it was
the syntax for creating objects or sending messages) will do an apply
for an identifier after the dot. In Swindle I did it for all function
application (basically because I enjoyed playing with the syntax
system, where you can do all kinds of weird games...).

--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://www.barzilay.org/ Maze is Life!

Reply all
Reply to author
Forward
0 new messages