164 views

Skip to first unread message

Dec 15, 2003, 3:38:47 PM12/15/03

to

Hello,

I'm just starting to understand macros, but I think I could use some

help with this:

I'd like to develop a construct that allows for a very convenient

means of iteration, that is used heavily in Matlab and GNU Octave. It's

called a 'range'.

A range works like this in GNU Octave:

octave> [1:5]

ans =

1 2 3 4 5

octave> [1:2:10]

ans =

1 3 5 7 9

So, basically, it defines a starting point, an optional increment

size, and an endpoint. The endpoint is not included if the increment

won't fall on it exactly. The default increment size is "1".

This is really useful for "mapping", or iterating:

octave> gamma([1:5])

ans =

1 1 2 6 24

See how the function automagically was mapped over the range?

I would like to do something like that in Scheme, where if I would

write:

(fact [1:5] )

or

(fact ([1:2:20]) )

or, more abstractly:

(proc ([start:step:stop]) )

It would convert into a loop:

(do ((i start (+ i step ) ) )

((>= i stop) )

(proc i) )

I guess the following syntax would be more easily transformed?

(iter proc ([start:step:stop]) )

Any insight would be greatly appreciated.

~Tomer

A little lisper

Dec 15, 2003, 3:43:56 PM12/15/03

to

tal...@noshpam.lbl.government wrote:

> (fact [1:5] )

> or

> (fact ([1:2:20]) )

>

> or, more abstractly:

>

> (proc ([start:step:stop]) )

>

> It would convert into a loop:

>

> (do ((i start (+ i step ) ) )

> ((>= i stop) )

>

> (proc i) )

>

> I guess the following syntax would be more easily transformed?

>

> (iter proc ([start:step:stop]) )

(define-syntax iter

(syntax-rules ()

((iter proc start step stop)

(do ((i start (+ i step )))

((>= i stop))

(proc i)))))

(iter display 1 2 10)

--

Jens Axel Søgaard

Dec 15, 2003, 5:05:48 PM12/15/03

to

On Dec 15, 2003 at 9:43pm, Jens Axel Søgaard wrote:

First off, thanks for the answer!

usenet >tal...@noshpam.lbl.government wrote:

usenet >

usenet >> (fact [1:5] )

usenet >> or

usenet >> (fact ([1:2:20]) )

^^^^^^^^^^

So I guess there's no generic way to do this expansion for all

existing procedures? Each one would have to be overloaded to recognize

a 'range' type?

usenet >>

usenet >> or, more abstractly:

usenet >> I guess the following syntax would be more easily transformed?

usenet >>

usenet >> (iter proc ([start:step:stop]) )

usenet >

usenet >(define-syntax iter

usenet > (syntax-rules ()

usenet > ((iter proc start step stop)

usenet > (do ((i start (+ i step )))

usenet > ((>= i stop))

usenet > (proc i)))))

usenet >

usenet >(iter display 1 2 10)

I guess I set myself up for this answer. I could just write this as a

procedure, I guess...

usenet >

usenet >

So here's the essence of my question: Is there a way, via macrology,

to modify an expression so that it re-arranges the expression that it

is within? Or can the macro only operate with the current expression,

and sub-expressions?

TIA,

~Tomer

Dec 15, 2003, 5:28:41 PM12/15/03

to

> usenet >tal...@noshpam.lbl.government wrote:

> usenet >

> usenet >> (fact [1:5] )

> usenet >> or

> usenet >> (fact ([1:2:20]) )

> ^^^^^^^^^^

> So I guess there's no generic way to do this expansion for all

> existing procedures? Each one would have to be overloaded to recognize

> a 'range' type?

> usenet >

> usenet >> (fact [1:5] )

> usenet >> or

> usenet >> (fact ([1:2:20]) )

> ^^^^^^^^^^

> So I guess there's no generic way to do this expansion for all

> existing procedures? Each one would have to be overloaded to recognize

> a 'range' type?

If I'm understanding you correctly, you're describing an operation exactly

like the standard Scheme "map" operation, combined with a range-creation

function. E.g. the above could be expressed as:

(map fact (range 1 5)) => (1 2 6 24 120)

(Note that 'map' differs from the 'iter' that Jens gave, in that it requires

the range to be fully built in advance as a list, rather than

built-as-you-go.)

If you want a map operation to be forced automatically whenever the argument

is a range, you wouldn't be able to do that in Scheme without *major*

hackery (e.g. in PLT Scheme, by redefining the #%app application operator

and testing for range arguments when applying functions).

> So here's the essence of my question: Is there a way, via macrology,

> to modify an expression so that it re-arranges the expression that it

> is within? Or can the macro only operate with the current expression,

> and sub-expressions?

The latter. (Although I'm always leery of making blanket statements about

what macros can't do, here.)

Anton

Dec 15, 2003, 5:29:01 PM12/15/03

to

tal...@noshpam.lbl.government wrote:

> On Dec 15, 2003 at 9:43pm, Jens Axel Søgaard wrote:

> On Dec 15, 2003 at 9:43pm, Jens Axel Søgaard wrote:

> First off, thanks for the answer!

> usenet >tal...@noshpam.lbl.government wrote:

> usenet >

> usenet >> (fact [1:5] )

> usenet >> or

> usenet >> (fact ([1:2:20]) )

> ^^^^^^^^^^

> So I guess there's no generic way to do this expansion for all

> existing procedures? Each one would have to be overloaded to recognize

> a 'range' type?

In a macro call the name of the macro is always first.

> usenet >>

> usenet >> or, more abstractly:

> usenet >> I guess the following syntax would be more easily transformed?

> usenet >>

> usenet >> (iter proc ([start:step:stop]) )

> usenet >

> usenet >(define-syntax iter

> usenet > (syntax-rules ()

> usenet > ((iter proc start step stop)

> usenet > (do ((i start (+ i step )))

> usenet > ((>= i stop))

> usenet > (proc i)))))

> usenet >

> usenet >(iter display 1 2 10)

>

> I guess I set myself up for this answer. I could just write this as a

> procedure, I guess...

Yes.

> So here's the essence of my question: Is there a way, via macrology,

> to modify an expression so that it re-arranges the expression that it

> is within?

No.

> Or can the macro only operate with the current expression,

> and sub-expressions?

Yes.

--

Jens Axel Søgaard

Dec 15, 2003, 5:41:00 PM12/15/03

to

usenet >> (iter proc ([start:step:stop]) )

usenet >

usenet >(define-syntax iter

usenet > (syntax-rules ()

usenet > ((iter proc start step stop)

usenet > (do ((i start (+ i step )))

usenet > ((>= i stop))

usenet > (proc i)))))

usenet >

usenet >(iter display 1 2 10)usenet >

usenet >(define-syntax iter

usenet > (syntax-rules ()

usenet > ((iter proc start step stop)

usenet > (do ((i start (+ i step )))

usenet > ((>= i stop))

usenet > (proc i)))))

usenet >

usenet >

usenet >

Okay, so I whipped up this utility. You put in either start:stop, or

start:step:stop. Note that if you put in a start which is greater than

the stop, and that the step is negative, then it should "increment

down". I tried to make it mirror the GNU Octave 'range' behavior:

(define (range-iter proc arg1 arg2 . arg3)

(cond ((and (null? arg3)

(> arg1 arg2) )

(error "range-iter: start must be lesser than stop.") )

((and (not (null? arg3))

(= arg2 0 ) )

(error "range-iter: step-size cannot be zero." ) )

((and (not (null? arg3))

(or (and (> arg2 0)

(> arg1 (car arg3 ) ) )

(and (< arg2 0)

(< arg1 (car arg3 ) ) ) ) )

(error "range-iter: step not in agreement with start and stop.") )

(else

(let ((start arg1)

(stop (if (null? arg3) arg2 (car arg3) ) )

(step (if (null? arg3) 1 arg2 ) ) )

(do ((i start (+ i step)))

((> i stop ))

(proc i ) ) ) ) ) )

guile> (range-iter (lambda (x)

(display (expt 2 x) )

(newline) )

1 2 10 )

2

8

32

128

512

---

~Tomer

Dec 15, 2003, 5:52:06 PM12/15/03

to

tal...@noshpam.lbl.government wrote:

> Okay, so I whipped up this utility. You put in either start:stop, or

> start:step:stop. Note that if you put in a start which is greater than

> the stop, and that the step is negative, then it should "increment

> down". I tried to make it mirror the GNU Octave 'range' behavior:

>

> (define (range-iter proc arg1 arg2 . arg3)

> Okay, so I whipped up this utility. You put in either start:stop, or

> start:step:stop. Note that if you put in a start which is greater than

> the stop, and that the step is negative, then it should "increment

> down". I tried to make it mirror the GNU Octave 'range' behavior:

>

> (define (range-iter proc arg1 arg2 . arg3)

I haven't figured out whether you are doing this as a learning

exercise, or whether you are after the functionality. If the

latter is the case, then take a look at Sebastian Egner's

SRFI:

<http://srfi.schemers.org/srfi-42/srfi-42.html>

And perhaps the Scheme 48's macros for loops:

<http://s48.org/0.57/manual/s48manual_49.html>

--

Jens Axel Søgaard

Dec 15, 2003, 9:32:05 PM12/15/03

to

Jens Axel Søgaard <use...@jasoegaard.dk> writes:

> I haven't figured out whether you are doing this as a learning

> exercise, or whether you are after the functionality. If the

> latter is the case, then take a look at Sebastian Egner's

> SRFI:

>

> <http://srfi.schemers.org/srfi-42/srfi-42.html>

>

> And perhaps the Scheme 48's macros for loops:

>

> <http://s48.org/0.57/manual/s48manual_49.html>

Also:

http://www.cs.cornell.edu/eli/Swindle/misc-doc.html#collect

(With features that are missing from the others.)

--

((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:

http://www.barzilay.org/ Maze is Life!

Dec 16, 2003, 3:27:17 PM12/16/03

to

On Dec 15, 2003 at 11:52pm, Jens Axel Søgaard wrote:

usenet >Date: Mon, 15 Dec 2003 23:52:06 +0100

usenet >From: Jens Axel Søgaard <use...@jasoegaard.dk>

usenet >Newsgroups: comp.lang.scheme

usenet >Subject: Re: Matlab/GNU Octave 'Ranges' Macro

usenet >

usenet >tal...@noshpam.lbl.government wrote:

usenet >> Okay, so I whipped up this utility. You put in either start:stop, or

usenet >> start:step:stop. Note that if you put in a start which is greater than

usenet >> the stop, and that the step is negative, then it should "increment

usenet >> down". I tried to make it mirror the GNU Octave 'range' behavior:

usenet >>

usenet >> (define (range-iter proc arg1 arg2 . arg3)

usenet >

usenet >I haven't figured out whether you are doing this as a learning

usenet >exercise, or whether you are after the functionality. If the

usenet >latter is the case, then take a look at Sebastian Egner's

usenet >SRFI:

It started as follows:

* I wish I could do this, as in GNU Octave, in Scheme!

Ex.:

octave> gamma([1:.3:5.27832])

* Oh, maybe I could do this with macros!

* Ummm... wait; I want to have a function's argument modify the

encasing function as well? Is that possible?

* Oh, I guess I can do this with a function, even though it wouldn't

be as succinct and elegant as it is with the GNU Octave range notation...

usenet >

usenet > <http://srfi.schemers.org/srfi-42/srfi-42.html>

usenet >

usenet >And perhaps the Scheme 48's macros for loops:

usenet >

usenet > <http://s48.org/0.57/manual/s48manual_49.html>

usenet >

usenet >

Thanks for the leads; I just hate re-inventing the wheel. Eli, thank

you as well.

~Tomer

Dec 17, 2003, 12:39:30 PM12/17/03

to

tal...@noshpam.lbl.government wrote:

> * I wish I could do this, as in GNU Octave, in Scheme!

> * I wish I could do this, as in GNU Octave, in Scheme!

> octave> gamma([1:.3:5.27832])

In Scheme:

(map gamma (range 1 .3 5.27832))

Is there really much difference whether you write one or the other?

> * Ummm... wait; I want to have a function's argument modify the

> encasing function as well? Is that possible?

According to the other answers, no (without manipulating the part

of your scheme system that reads the instructions).

Actually, in Mathematica, which is more lispy that Octave, but

more number-crunching oriented that scheme, there is an attribute

"listable" that applies to all of Mathematica's functions, and

which you can set on to produce the effect you are after:

f[{a,b,c}]

f[{a,b,c}]

Attributes[f] = {Listable}

{Listable}

f[{a,b,c}]

{f[a],f[b],f[c]}

But in plain scheme, there is nothing like attributes to functions, and it

one would like add something like that, one would need to manipulate the

scheme system itself.

Dec 17, 2003, 2:13:03 PM12/17/03

to

On Dec 17, 2003 at 5:39pm, Sampo Smolander wrote:

sampo. >tal...@noshpam.lbl.government wrote:

sampo. >> * I wish I could do this, as in GNU Octave, in Scheme!

sampo. >> octave> gamma([1:.3:5.27832])

sampo. >

sampo. >In Scheme:

sampo. >(map gamma (range 1 .3 5.27832))

sampo. >

sampo. >Is there really much difference whether you write one or the other?

You're right. It's pretty close. And that is exactly why I thought it

would be a relatively-easy learning-macros exercise! :-)

sampo. >

sampo. >> * Ummm... wait; I want to have a function's argument modify the

sampo. >> encasing function as well? Is that possible?

sampo. >

sampo. >According to the other answers, no (without manipulating the part

sampo. >of your scheme system that reads the instructions).

What answers? I got a "no", with no justification, explanation, or

references. I was hoping for a more solid answer ( especially to my

recent abstract question on macrology... :-(

sampo. >Actually, in Mathematica, which is more lispy that Octave, but

sampo. >more number-crunching oriented that scheme, there is an attribute

sampo. >"listable" that applies to all of Mathematica's functions, and

sampo. >which you can set on to produce the effect you are after:

Yes! This is the effect that I'm after. :-) Perhaps I'd use

Mathematica, but it's not free ( beer or freedom ).

~Tomer

Dec 17, 2003, 6:39:52 PM12/17/03

to

Sampo Smolander wrote:

> But in plain scheme, there is nothing like attributes to functions, and it

> one would like add something like that, one would need to manipulate the

> scheme system itself.

> But in plain scheme, there is nothing like attributes to functions, and it

> one would like add something like that, one would need to manipulate the

> scheme system itself.

PLT has a structures-as-procedures feature that can be used to give functions

attributes.

http://download.plt-scheme.org/doc/205/html/mzscheme/mzscheme-Z-H-4.html#node_sec_4.6

-d

Dec 17, 2003, 11:46:37 PM12/17/03

to

In this article we show how to implement the 'range' macro in R5RS Scheme.

It seems the macro can do everything that Matlab's macro can do -- and

then some.

It seems the macro can do everything that Matlab's macro can do -- and

then some.

tal...@noshpam.lbl.government wrote in message news:<Pine.LNX.4.44.031215...@thar.lbl.gov>...

> A range works like this in GNU Octave:

>

> octave> [1:5]

> ans =

> 1 2 3 4 5

> octave> [1:2:10]

> ans =

> 1 3 5 7 9

>

> So, basically, it defines a starting point, an optional increment

> size, and an endpoint. The endpoint is not included if the increment

> won't fall on it exactly. The default increment size is "1".

>

> This is really useful for "mapping", or iterating:

>

> octave> gamma([1:5])

> ans =

> 1 1 2 6 24

What an excellent illustration for shift/reset! Please see the Scheme

Bibliography (and in particular, papers by Danvy and Filinski). We

will be using a version of delimited continuation operators called

bshift/breset, whose R5RS implementation is given in Appendix A. The

margins of this message are not big enough for the extensive

discussion of bshift/breset.

(define (no-more) (list no-more))

(define-syntax range

(syntax-rules ()

((range r from step to)

(bshift r f

(do ((i from (+ i step))) ((> i to) no-more)

(f i))))

((range r from to) (range r from 1 to))))

This is all the code. Let us see how it works. Let us first define the

function fact, the guinea-pig of computer science.

(define (fact n) (if (<= n 0) 1 (* n (fact (- n 1)))))

As we see, it is a regular function that has no idea about ranges. And

yet, we can do:

(display "test 1") (newline)

(breset r (begin (display (fact (range r 1 5))) (newline)))

; prints:

1

2

6

24

120

The breset r form delimits the extent of the range iterator.

or

(display "test 2") (newline)

(breset r (begin (display (fact (range r 1 2 14))) (newline)))

; which prints:

1

6

120

5040

362880

39916800

6227020800

We can easily have two ranges:

(display "test 3: two ranges") (newline)

(breset r1 (breset r2

(begin (display (+ (range r1 1 2) (range r2 100 10 120)))

(newline))))

; which prints

101

111

121

102

112

122

But we can do much more. The ability to limit the extent of the

iteration lets us, for example, collect the result of the iteration into

a list. Or do some other advanced operation. For example:

(display "test 4: collect") (newline)

(display

(breset r1

(breset r2 (bshift r1 f (let* ((n (range r2 1 5)) (nprev (f #f)))

(* n (if (eq? no-more nprev) 1 nprev))

)))))

(newline)

which prints 120 -- the value of 5!. Indeed, we have

computed (* 1 2 3 4 5). To be more precise, we computed

(* 1 (* 2 (* 3 (* 4 (* 5 1))))). As we generated the numbers within the

range, we plugged them into a computation. Finally, we can use a range

within a range:

(display "test 5: range-collect") (newline)

(breset r3

(begin

(display

(breset r1

(breset r2 (bshift r1 f (let* ((n (range r2 (range r3 1 5) 5))

(nprev (f #f)))

(* n (if (eq? no-more nprev) 1 nprev))

)))))

(newline)))

that prints

120 ; which is (* 1 2 3 4 5)

120 ; which is (* 2 3 4 5)

60 ; which is (* 3 4 5)

20 ; which is (* 4 5)

5 ; which is (* 5)

As we can see, the ability to explicitly delimit the range of our

iteration is quite handy. The Scheme code that does all the printing

and computation doesn't even suspect that it is participating in any

iteration. The code tested on SCM 5d6, Petite Chez Scheme, and Scheme48.

Appendix A.

; statically-scoped shift/reset

(define-syntax breset

(syntax-rules ()

((_ ?rc ?e) (*breset (lambda (?rc) ?e)))))

(define-syntax bshift

(syntax-rules ()

((_ ?rc ?s ?e) (*bshift ?rc (lambda (?s) ?e)))))

(define (*breset body)

(call-with-current-continuation

(lambda (rcf)

(let* ((rc (list rcf))

(v (body rc)))

((car rc) v)))))

(define (*bshift rc f)

(call-with-current-continuation

(lambda (k)

(let ((v

(f

(lambda (v) ; s

(let* ((old-rc (car rc))

(sv

(call-with-current-continuation

(lambda (k*)

(set-car! rc k*)

(k v))))

)

(set-car! rc old-rc)

sv)))))

((car rc) v)))))

Dec 18, 2003, 1:37:08 AM12/18/03

to

Sampo Smolander <sampo.smolan...@helsinki.fi> schrieb:

> Actually, in Mathematica, which is more lispy that Octave, but

> more number-crunching oriented that scheme, there is an attribute

> "listable" that applies to all of Mathematica's functions, and

> which you can set on to produce the effect you are after:

>

> f[{a,b,c}]

>

> f[{a,b,c}]

>

> Attributes[f] = {Listable}

>

> {Listable}

>

> f[{a,b,c}]

>

> {f[a],f[b],f[c]}

> Actually, in Mathematica, which is more lispy that Octave, but

> more number-crunching oriented that scheme, there is an attribute

> "listable" that applies to all of Mathematica's functions, and

> which you can set on to produce the effect you are after:

>

> f[{a,b,c}]

>

> f[{a,b,c}]

>

> Attributes[f] = {Listable}

>

> {Listable}

>

> f[{a,b,c}]

>

> {f[a],f[b],f[c]}

I haven't been paying attention to this thread, so I may have missed the

point, but why not use a HoF?

(define (make-listable f)

(lambda (x)

(if (list? x)

(map f x)

(f x))))

(define (f x) (+ 2 x))

(set! f (make-listable f))

(f (list 1 2 3))

==> (3 4 5)

Dec 18, 2003, 7:32:51 PM12/18/03

to

Adrian Kubala <adr...@sixfingeredman.net> wrote:

> I haven't been paying attention to this thread, so I may have

> missed the point, but why not use a HoF?

> (define (make-listable f)

> (lambda (x)

> (if (list? x)

> (map f x)

> (f x))))

Yes, that is quite easy and quite possible.> I haven't been paying attention to this thread, so I may have

> missed the point, but why not use a HoF?

> (define (make-listable f)

> (lambda (x)

> (if (list? x)

> (map f x)

> (f x))))

After making the appropriate functions listable, one

could go on computing like (log (range 1 10)).

Maybe the original poster might think that this is too clumsy,

since before you can start to use the normal math functions

(sin, con, and the like) as listable, you'd have to explicitly

make them listable. But then again, that shouln'd be much work

(in a init file or something), since there aren't so many

math functions in scheme anyway :-)

That's the way I'd choose if I wanted this kind on behavior.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu