Functional data structures with "iterative syntax"
Jens Axel Søgaard
; This file provides two macros, with allows the use of
; functional data structures in a "iterative syntax".
; As example, the following functional stack is used.
; The idea came from reading this post of Bradd W. Szonye:
; <http://groups.google.com/groups?selm=slrnbqauch.ks0.bradd%2Bnews%40szonye.com&output=gplain>
; who thought the traditional let-values idiom was somewhat clumsy.
; Example:
; (define S (make-stack))
; (with-implicit-set! S (push)
; (with-implicit-second-value-set! S (pop)
; (push 1 S)
; (push 2 S)
; (pop S)
; (push 3 S)
; (pop S)))
;;; STACK
; The following functional data structure is used as example.
(define (make-stack) '())
(define (push x S) (cons x S))
(define (pop S) (values (car S) (cdr S)))
;;; (with-implicit-set! var (f ...) body ...)
; All calls to functions occuring in f ... will set
; var to their return value.
(define-syntax with-implicit-set!
(syntax-rules ()
[(with-implicit-set! v () body ...)
(begin body ...)]
[(with-implicit-set! v (f g ...) body ...)
(let-syntax ([f (syntax-rules ()
[(f . x) (let ([y (f . x)])
(set! v y)
y)])])
(with-implicit-set! v (g ...)
body ...))]))
; Example
(define (display/nl x) (display x) (newline))
(define last 0)
(with-implicit-set! last (+ - *)
(display/nl (* 3 4))
(display/nl last)
(display/nl (+ 1 2))
(display/nl last))
(newline)
;; Output
; 12
; 12
; 3
; 3
;;; (with-implicit-second-value-set! v (f ...) body ...)
; The functions in f ... all return two multiple values.
; The result of a call (f args ...) in body, will set
; the variable v with the second value, and return the first.
(define-syntax with-implicit-second-value-set!
(syntax-rules ()
[(with-implicit-second-value-set! v () body ...)
(begin body ...)]
[(with-implicit-second-value-set! v (f g ...) body ...)
(let-syntax ([f (syntax-rules ()
[(f . x) (let-values ([(y new-v) (f . x)])
(set! v new-v)
y)])])
(with-implicit-second-value-set! v (g ...) body ...))]))
; Example
(define (display/nl x) (display x) (newline))
(define S (make-stack))
(with-implicit-set! S (push)
(with-implicit-second-value-set! S (pop)
(display/nl (push 1 S))
(display/nl (push 2 S))
(display/nl (pop S))
(display/nl (push 3 S))
(display/nl (pop S))))
(display/nl S)
;; Output
; (1)
; (2 1)
; 2
; (3 1)
; 3
; (1)
Abdulaziz Ghuloum
> (define-syntax with-implicit-set!
> (syntax-rules ()
> [(with-implicit-set! v () body ...)
> (begin body ...)]
> [(with-implicit-set! v (f g ...) body ...)
> (let-syntax ([f (syntax-rules ()
> [(f . x) (let ([y (f . x)])
> (set! v y)
> y)])])
> (with-implicit-set! v (g ...)
> body ...))]))
> ;;; (with-implicit-second-value-set! v (f ...) body ...)
> ; The functions in f ... all return two multiple values.
> ; The result of a call (f args ...) in body, will set
> ; the variable v with the second value, and return the first.
> (define-syntax with-implicit-second-value-set!
> (syntax-rules ()
> [(with-implicit-second-value-set! v () body ...)
> (begin body ...)]
> [(with-implicit-second-value-set! v (f g ...) body ...)
> (let-syntax ([f (syntax-rules ()
> [(f . x) (let-values ([(y new-v) (f . x)])
> (set! v new-v)
> y)])])
> (with-implicit-second-value-set! v (g ...) body ...))]))
I would avoid the nested let-syntaxes and do the whole thing in one
sweep. I'm sure this is not new to Jens so I'm wondering if there is a
particular reason why it was not written like:
(define-syntax with-implicit-set!
(syntax-rules ()
[(with-implicit-set! v (f ...) b b* ...)
(let-syntax
([f (syntax-rules ()
[(f . x)
(let ([y (f . x)])
(set! v y)
y)])]
...)
b b* ...)]))
(define-syntax with-implicit-second-value-set!
(syntax-rules ()
[(with-implicit-second-value-set! v (f ...) b b* ...)
(let-syntax
([f (syntax-rules ()
[(f . x)
(let-values ([(y new-v) (f . x)])
(set! v new-v)
y)])]
...)
b b* ...)]))
Aziz,,,
Jens Axel Søgaard
No reason at all, apart from the fact I didn't think of it.
--
Jens Axel Søgaard
Bradd W. Szonye
> Functional data structures with "imperative syntax" ...
> The idea came from reading this post of Bradd W. Szonye:
> who thought the traditional let-values idiom was somewhat clumsy.
Not sure what you mean by "traditional let-values idiom." If you mean by
that, "returning multiple values as a pair or vector, then using
car/cdr/vector-ref to split out the components," then yes, that's very
cumbersome. The LET-VALUES macro simplifies things greatly, although
it's still somewhat cumbersome when you need to cascade several uses. I
suppose that's what LET*-VALUES is for.
> Example:
>
> (define S (make-stack))
> (with-implicit-set! S (push)
> (with-implicit-second-value-set! S (pop)
> (push 1 S)
> (push 2 S)
> (pop S)
> (push 3 S)
> (pop S)))
I must admit that this is clever, although I don't know whether it's
what I'm really looking for. This is a lot like an implicit LET*-VALUES
that lets you re-use the same binding. Hm, that might be just the right
thing for something like a splay tree, where you really do want to
mutate the value.
I suspect that a self-mutating object is probably the right way to do a
splay tree (and similar data-structures, like some heaps). If you want
to use it in a functional way, then a monad is probably the right way to
do that. I wonder if your syntax is an ad-hoc monad? I don't know enough
about them to tell.
--
Bradd W. Szonye
http://www.szonye.com/bradd
Andre
> I suspect that a self-mutating object is probably the right way to do a
> splay tree (and similar data-structures, like some heaps). If you want
> to use it in a functional way, then a monad is probably the right way to
> do that. I wonder if your syntax is an ad-hoc monad? I don't know enough
> about them to tell.
A state monad can be used to hide and automate the stack passing.
This solution is purely funtional (no set!'s) but can easily be made
to use imperative update of the state by modifying the
definitions in the monad below. To give a flavor of how to use
it, a couple fo examples:
(run
(do (push 1)
(push 2)
(pop)
(push 3)
(pop))
(make-stack))
-------------> (values 3 '(1))
(run
(do (push 1)
(push 2)
(x <- (pop))
(y <- (pop))
(push y)
(push x))
(make-stack))
-------------> (values 'void '(2 1))
The definitions are:
;=======================================================
; Type state-transformer a = state -> state a
; return : a -> state-transformer a
(define (return a) (lambda (state) (values a state)))
(define-syntax do
(syntax-rules (<-)
((do result) result)
((do (a <- m) exp)
(lambda (state) (let-values (((a state) (m state)))
(exp state))))
((do m exp)
(lambda (state) (let-values (((dummy state) (m state)))
(exp state))))
((do exp1 exp2 ...)
(do exp1 (do exp2 ...)))))
; run : (state-transformer a) state -> (values a state)
(define (run m initial-state) (m initial-state))
;=================================================================
(define (make-stack) '())
(define (push x)
(lambda (s) (values 'void (cons x s))))
(define (pop)
(lambda (s) (values (car s) (cdr s))))
;==========================================================
regards
A.v.T
Jens Axel Søgaard
> "Bradd W. Szonye" <bradd...@szonye.com> wrote in message news:<slrnbqigr9.9...@szonye.com>...
> A state monad can be used to hide and automate the stack passing.
> This solution is purely funtional (no set!'s) but can easily be made
> to use imperative update of the state by modifying the
> definitions in the monad below. To give a flavor of how to use
> it, a couple fo examples:
>
> (run
> (do (push 1)
> (push 2)
> (pop)
> (push 3)
> (pop))
> (make-stack))
>
> -------------> (values 3 '(1))
...
> ; Type state-transformer a = state -> state a
>
> ; return : a -> state-transformer a
>
> (define (return a) (lambda (state) (values a state)))
>
> (define-syntax do
> (syntax-rules (<-)
> ((do result) result)
> ((do (a <- m) exp)
> (lambda (state) (let-values (((a state) (m state)))
> (exp state))))
> ((do m exp)
> (lambda (state) (let-values (((dummy state) (m state)))
> (exp state))))
> ((do exp1 exp2 ...)
> (do exp1 (do exp2 ...)))))
>
> ; run : (state-transformer a) state -> (values a state)
>
> (define (run m initial-state) (m initial-state))
>
>
> ;=================================================================
>
> (define (make-stack) '())
>
> (define (push x)
> (lambda (s) (values 'void (cons x s))))
>
> (define (pop)
> (lambda (s) (values (car s) (cdr s))))
>
> ;=================================================================
I find this solution elegant. But it seems to me that problems arise,
if I try use "normal" functions in the do. E.g.:
(run
(do (push 1)
(x <- pop)
(display x)
(push 3)
(pop))
(make-stack))
But this could probably be repaired if one extended the macro to
handle this syntax:
(with-functional (push pop)
(run
(do (push 1)
(x <- pop)
(display x)
(push 3)
(pop))
(make-stack))
Nevertheless, I still like the solution.
--
Jens Axel Søgaard
Andre
>
> > I find this solution elegant. But it seems to me that problems arise,
> if I try use "normal" functions in the do. E.g.:
>
> (run
> (do (push 1)
> (x <- pop)
> (display x)
> (push 3)
> (pop))
> (make-stack))
>
This is what (return ...) is for (although it is perhaps confusingly named):
(run
(do (push 1)
(push 2)
(x <- (pop))
(y <- (pop))
(return (display x))
(return (newline))
(push y)
(push x))
(make-stack))
---------> displays: 2\n
returns: (values 'void '(2 1))
Regards
A.v.T.
Jens Axel Søgaard
> This is what (return ...) is for (although it is perhaps confusingly named):
Ah!
I better start reading about monads real soon now (read: summer holiday).
--
Jens Axel Søgaard
Bradd W. Szonye
splay tree ADTs):
Jens Axel Søgaard <use...@jasoegaard.dk> wrote:
> I better start reading about monads real soon now (read: summer holiday).
Yes, same here. Thanks to Andre for a very elegant way to deal with part
of the issues I raised.
Note that the multiple-value returns still exist, albeit under the hood.
I still think they're a good idea, because they give implementations the
latitude for efficient "hookups" between multiple-valued returns and
multiple-argument functions. I do wish there were some good, general way
to express that. It seems to me that requiring explicit packing and
unpacking (i.e., making the programmer do it, as some posters suggested)
is the wrong way to go.
Let me state the problem more generally: Some functions need to return
more than one value. In Scheme, you can do that with VALUES, by
explicitly packing values into pairs/tuples, or in other ways. Depending
on the Scheme implementation, some of these methods are more efficient
than others (both in terms of run-time efficiency and programmer
efficiency). Andre's monad deals with some of the programmer efficiency
issues, in a very elegant way. But I'm still a bit concerned about
runtime efficiency. In particular, I would expect list-consing to be
inferior to most implementations of call-with-values, speedwise and
GC-wise.
I don't know whether VALUES is the right solution either, but I'm pretty
sure that list-consing isn't, and tuple construction isn't much better
(because Scheme doesn't really do tuples other than pairs -- Scheme
vectors are slightly inferior to generic tuples IMO).
David Rush
wrote:
> (because Scheme doesn't really do tuples other than pairs -- Scheme
> vectors are slightly inferior to generic tuples IMO).
Just how are scheme vectors different from and worse than generic tuples
in say, SML? Is it the lack of a pattern-matching syntax?
david rush
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Shriram Krishnamurthi
> On Thu, 06 Nov 2003 21:02:34 GMT, Bradd W. Szonye
> <bradd...@szonye.com> wrote:
>
> > (because Scheme doesn't really do tuples other than pairs -- Scheme
> > vectors are slightly inferior to generic tuples IMO).
>
> Just how are scheme vectors different from and worse than generic tuples
> in say, SML? Is it the lack of a pattern-matching syntax?
If you pass a tuple of arguments to a procedure expecting a tuple, the
compiler will often refrain from creating a tuple data structure and
pass the arguments in registers instead. This is what enables SML to
have the flexibility of using tuples to represent argument "lists"
without losing performance.
There are numerous reasons why this is optimization is possible in SML
and difficult in Scheme, most of which should be known to readers
here. Barring the optimization, simple accessors (in the form of,
say, pattern matching) are the main difference I see.
Shriram
Michael Sperber
Shriram> If you pass a tuple of arguments to a procedure expecting a tuple, the
Shriram> compiler will often refrain from creating a tuple data structure and
Shriram> pass the arguments in registers instead. This is what enables SML to
Shriram> have the flexibility of using tuples to represent argument "lists"
Shriram> without losing performance.
Shriram> There are numerous reasons why this is optimization is possible in SML
Shriram> and difficult in Scheme, most of which should be known to readers
Shriram> here. Barring the optimization, simple accessors (in the form of,
Shriram> say, pattern matching) are the main difference I see.
It isn't exactly "easy" in ML, either. Moreover, since ML doesn't
really have a default strategy for (conceptual) multi-argument
functions (tuples or currying), there's more currying/uncurrying going
on which further complicates things.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Jeffrey Mark Siskind
> compiler will often refrain from creating a tuple data structure and
> pass the arguments in registers instead. This is what enables SML to
> have the flexibility of using tuples to represent argument "lists"
> without losing performance.
>
> There are numerous reasons why this is optimization is possible in SML
> and difficult in Scheme, most of which should be known to readers
> here. Barring the optimization, simple accessors (in the form of,
> say, pattern matching) are the main difference I see.
Stalin will (in the appropriate circumstances) pass both argument pairs and
return pairs in registers.
qobi@tlamachilistli>cat tuples.sc
(define (swap pair) (cons (cdr pair) (car pair)))
(car (swap (swap (cons 1 2))))
qobi@tlamachilistli>stalin -On -dI -c tuples.sc
The essence of tuples.c is:
struct structure_type534 f6(struct structure_type534 a654)
{struct structure_type534 r6;
int t0;
int t1;
struct structure_type534 t2;
struct structure_type534 t3;
t2 = a654;
t0 = t2.s1;
t3 = a654;
t1 = t3.s0;
r6.s0 = t0;
r6.s1 = t1;
return r6;}
int f0(void)
{struct structure_type534 t4;
struct structure_type534 t5;
struct structure_type534 t6;
int t7;
int t8;
int t26;
t26 = 20;
t7 = 1;
t8 = 2;
t6.s0 = t7;
t6.s1 = t8;
t5 = f6(t6);
t4 = f6(t5);
return t4.s0;}
qobi@tlamachilistli>gcc3 -S -O2 -freg-struct-return -fomit-frame-pointer tuples.c
The essence of tuples.s is (on x86):
f6:
pushl %esi
pushl %ebx
movl 16(%esp), %edx
movl %edx, %ecx
movl 12(%esp), %eax
movl %ecx, %ebx
movl %eax, %esi
movl %ebx, %eax
popl %ebx
movl %esi, %edx
popl %esi
ret
f0:
subl $20, %esp
movl $2, %edx
pushl %edx
movl $1, %eax
pushl %eax
call f6
addl $8, %esp
pushl %edx
pushl %eax
call f6
addl $28, %esp
ret
Note that this involves some pushing and popping on the stack because of the
lack of registers in the x86 ISA. But a good C compiler on a good architecture
could pass both the arugment tuples and the return tuples in registers from
the Stalin-generated code.
Bradd W. Szonye
>> (because Scheme doesn't really do tuples other than pairs -- Scheme
>> vectors are slightly inferior to generic tuples IMO).
David Rush <ku...@gofree.indigo.ie> wrote:
> Just how are scheme vectors different from and worse than generic
> tuples in say, SML? Is it the lack of a pattern-matching syntax?
No, I was thinking of something else entirely. A vector is like an
n-tuple, and a pair is like a 2-tuple, but they're two completely
different types in Scheme. In other words, they're both expressions of
the same general concept, but there's no unified version of the concept.
Also, there's no convenient way to "explode" a tuple/pair/vector in
Scheme. Something like
(let-tuple (((a b c) (vector 1 2 3))
((d e) (pair 4 5))
((f g h i) (values 6 7 8 9)))
...)
would be handy for dealing with all of the many ways of returning
multiple values in Scheme. Or perhaps a generalized APPLY that can deal
with arbitrary tuples instead of lists. Ideally, it'd have some way to
optimize the common composition case where one function accepts a tuple
and another one returns a tuple.
I guess I too am looking for a way to manipulate argument lists; LET is
just a special case of that, since LET is just syntactic sugar for a
common kind of closure.