Hi, a small problem. Let's use binary trees. Leaves are themselves
and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
Ex: tree(+,tree(*,x,2),tree(-,y,1))
which represents (+ (* x 2) (- y 1)) in Lisp for example.
Problem : program copytree(t) which returns a copy of the tree t,
functionally of course, but with an iterative (tail recursive)
process, using a stack.
I solve this with a two-phase algorithm :
1. first build *iteratively* the postfix walking of the tree into a list :
(+ x 2 * y 1 - +)
For that I push the left son onto the stack and dive into the right son.
2. then walk *iteratively* this list to rebuild a new tree.
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
Thanks,
JG
From: Pascal J. Bourguignon
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <87k54ayzqg.fsf@galatea.local>
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> Hi, a small problem. Let's use binary trees. Leaves are themselves
> and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
>
> Ex: tree(+,tree(*,x,2),tree(-,y,1))
> which represents (+ (* x 2) (- y 1)) in Lisp for example.
>
> Problem : program copytree(t) which returns a copy of the tree t,
> functionally of course, but with an iterative (tail recursive)
> process, using a stack.
>
> I solve this with a two-phase algorithm :
>
> 1. first build *iteratively* the postfix walking of the tree into a list :
> (+ x 2 * y 1 - +)
> For that I push the left son onto the stack and dive into the right son.
Notice that that the length of that list is the number of leaves in the tree.
> 2. then walk *iteratively* this list to rebuild a new tree.
>
> Is there a more simple one-phase way (iterative and functional,
> first order please, no CPS) to get this algorithm ?
No, THIS algorithm is two-phase. You cannot change it, it's the
essence if THIS algorithm, to be two-phase.
Now, we may try to invent a different, one-phase algorithm. Is it
what you want? Then do it! The hint is to use a stack (notice that
its biggest length will be the depth of the tree, which is usually on
the order of log(number of leaves).
--
__Pascal Bourguignon__
Pascal, I don't understand your reply. I want to find a one-phase algorithm
to solve this problem of copying in a functional iterative way a binary tree.
I have already a two-phase algorithm.
I'm just asking : does anyone know a one-phase algorithm ?
I'm not a student, I'm trying to get my program done in the best way...
Somebody else (Kaz Kylheku) tells me to be destructive. No, I don't want
for many reasons. And I don't think that using libraries will keep me
from finding cute algorithms...
JG
In article <··············@galatea.local>,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> Jean Guillaume Pyraksos <······@hotmail.com> writes:
>
> > Hi, a small problem. Let's use binary trees. Leaves are themselves
> > and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
> >
> > Ex: tree(+,tree(*,x,2),tree(-,y,1))
> > which represents (+ (* x 2) (- y 1)) in Lisp for example.
> >
> > Problem : program copytree(t) which returns a copy of the tree t,
> > functionally of course, but with an iterative (tail recursive)
> > process, using a stack.
> >
> > I solve this with a two-phase algorithm :
> >
> > 1. first build *iteratively* the postfix walking of the tree into a list :
> > (+ x 2 * y 1 - +)
> > For that I push the left son onto the stack and dive into the right son.
>
> Notice that that the length of that list is the number of leaves in the tree.
>
> > 2. then walk *iteratively* this list to rebuild a new tree.
> >
> > Is there a more simple one-phase way (iterative and functional,
> > first order please, no CPS) to get this algorithm ?
>
> No, THIS algorithm is two-phase. You cannot change it, it's the
> essence if THIS algorithm, to be two-phase.
>
> Now, we may try to invent a different, one-phase algorithm. Is it
> what you want? Then do it! The hint is to use a stack (notice that
> its biggest length will be the depth of the tree, which is usually on
> the order of log(number of leaves).
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> Pascal, I don't understand your reply. I want to find a one-phase algorithm
> to solve this problem of copying in a functional iterative way a binary tree.
> I have already a two-phase algorithm.
> I'm just asking : does anyone know a one-phase algorithm ?
> I'm not a student, I'm trying to get my program done in the best way...
Well, I would think that the best way would be to use a recursive
algorithm.
Tree walkers belong to a class of functions that are fundamentally
recursive. The class of recursive functions is larger than the class of
iterative functions, so you can't really have a purely iterative
solution to this problem. At best you can not use the built-in
recursion and instead implement it yourself by maintaining a stack or
queue of pending operations that you will need to execute.
Since a tree walker is fundamentally a recursive function, you can't
have a proper tail-recursive version. Simply because the algorithm
requires doing things via multiple recursion along different branches of
the tree walk. Again, you could probably disguise it, but any such
solution will be a lot more convoluted than a straight-forward recursive
solution.
Why are you interested in an iterative solution?
--
Thomas A. Russ, USC/Information Sciences Institute
From: Pascal J. Bourguignon
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <874ovdyxyl.fsf@galatea.local>
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> Pascal, I don't understand your reply. I want to find a one-phase algorithm
> to solve this problem of copying in a functional iterative way a binary tree.
> I have already a two-phase algorithm.
> I'm just asking : does anyone know a one-phase algorithm ?
> I'm not a student, I'm trying to get my program done in the best way...
>
> Somebody else (Kaz Kylheku) tells me to be destructive. No, I don't want
> for many reasons. And I don't think that using libraries will keep me
> from finding cute algorithms...
Kaz is right: you gave too many constraint for your problem to have a solution.
iterative & no assignment & no continuation ==> impossible.
So which one feature do you want to leave out?
--
__Pascal Bourguignon__
None, I do *want* a tail-recursive, purely functional, first order solution.
I'll try myself, or prove me that this is impossible.
I have already such a tail-recursive, purely functional, first order solution
in O(n) but two-phase, in 2n iterative steps.
I'm looking for a one-phase solution. I don't see on the theoretical side why
I couldn't find one.
Thanks,
JG
In article <··············@galatea.local>,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> > Somebody else (Kaz Kylheku) tells me to be destructive. No, I don't want
> > for many reasons. And I don't think that using libraries will keep me
> > from finding cute algorithms...
>
> Kaz is right: you gave too many constraint for your problem to have a solution.
>
> iterative & no assignment & no continuation ==> impossible.
>
> So which one feature do you want to leave out?
On 23 maio, 12:01, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> None, I do *want* a tail-recursive, purely functional, first order solution.
> I'll try myself, or prove me that this is impossible.
> I have already such a tail-recursive, purely functional, first order solution
> in O(n) but two-phase, in 2n iterative steps.
> I'm looking for a one-phase solution. I don't see on the theoretical side why
> I couldn't find one.
But are you sure that the first phase of your algorithm is iterative
and purely functional? You said you push the left son into a stack,
and this is not exactly functional (you need to use "pop", which is
destructive). You can do the exact same thing to create your algorithm.
It is iterative and functional, I pass the stack as an argument.
push and pop are *not* destructive. See the last reply from pjb...
Thanks Pascal, I'll get an eye on your lap-level solution :-)
JG
In article
<····································@c36g2000yqn.googlegroups.com>,
gugamilare <··········@gmail.com> wrote:
> On 23 maio, 12:01, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> > None, I do *want* a tail-recursive, purely functional, first order solution.
> > I'll try myself, or prove me that this is impossible.
> > I have already such a tail-recursive, purely functional, first order solution
> > in O(n) but two-phase, in 2n iterative steps.
> > I'm looking for a one-phase solution. I don't see on the theoretical side why
> > I couldn't find one.
>
> But are you sure that the first phase of your algorithm is iterative
> and purely functional? You said you push the left son into a stack,
> and this is not exactly functional (you need to use "pop", which is
> destructive). You can do the exact same thing to create your algorithm.
From: Kaz Kylheku
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <20090605051520.82@gmail.com>
On 2009-05-24, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> It is iterative and functional, I pass the stack as an argument.
> push and pop are *not* destructive. See the last reply from pjb...
There is no such thing as ``iterative and functional''. Iteration is procedural.
With regard to tail recursion, you can look at it in two ways. Either it is
optimized function calls, in which case it's not iteration but optimized
recusion. It may be functional, but it's not iterative. Or tail recursion is
a syntactic sugar for iteration. Then it's understood that the calls are
really goto, and the call arguments are not bound to fresh parameters, but
clobber the existing variables. Now you have iteration, but it's not
functional.
I actually thought that all modern versions of Lisp considered
tail recursion as de facto optimized (bounded stack space).
If not, it is a considerable regression, see Python...
"Functional iteration" makes high sense IMHO.
Iteration is *not* a procedural-only concept.
JG
In article <·················@gmail.com>,
Kaz Kylheku <········@gmail.com> wrote:
> On 2009-05-24, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> > It is iterative and functional, I pass the stack as an argument.
> > push and pop are *not* destructive. See the last reply from pjb...
>
> There is no such thing as ``iterative and functional''. Iteration is procedural.
>
> With regard to tail recursion, you can look at it in two ways. Either it is
> optimized function calls, in which case it's not iteration but optimized
> recusion. It may be functional, but it's not iterative. Or tail recursion is
> a syntactic sugar for iteration. Then it's understood that the calls are
> really goto, and the call arguments are not bound to fresh parameters, but
> clobber the existing variables. Now you have iteration, but it's not
> functional.
From: Pascal J. Bourguignon
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <87iqjquw3k.fsf@galatea.local>
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> I actually thought that all modern versions of Lisp considered
> tail recursion as de facto optimized (bounded stack space).
> If not, it is a considerable regression, see Python...
> "Functional iteration" makes high sense IMHO.
> Iteration is *not* a procedural-only concept.
You must distinguish a recursive procedure from a recursive process,
and an iterative procedure from an iterative process.
A recursive procedure may behave recursively or iteratively depending
on the kind of recursive calls it makes (terminal or non-terminal).
When you have a recursive procedure with only terminal recursive calls,
then you get an iterative process.
When you have a recursive procedure with non terminal recursive calls,
then you get a recursive process.
When you have an iterative procedure with an iterative process, then
unless it's an infinite loop, there's no other way than to change some
state, it cannot be purely functional, inside that procedure.
And of course, you cannot have an iterative procedure with a recursive
process stricto-sensu ; you could manage the stack yourself, but as in
the preceding case, you must also change the state (use a mutable
stack or at least a mutable reference to a functional stack).
+----------------------------------------------------------------------+
| process: | iterative | recursive |
+-----------------+-----------------------+----------------------------+
| procedure: | | |
| iterative | loop with state | loop with stack and state |
| ----------------+----------||-----------+----------------------------+
| recursive | function with only | function with non-tail |
| | tail recursive calls | recursive calls |
+-----------------+-----------------------+----------------------------+
And since there's a trivial transformation between the two cells in
the iterative process column, some languages mandate, and most CL
implementations do implement Tail Call Optimization (which is also
useful for non recursive tail calls).
Notice that conceptually, there's no assignment in the case of a
recursive procedure with iterative process, because the substitution
rule may still be used to compute the result. Assignment here is only
an detail at the level of the generated code that's useful because we
have computer with finite memory.
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
----------> http://www.netmeister.org/news/learn2quote.html <-----------
---> http://homepage.ntlworld.com/g.mccaughan/g/remarks/uquote.html <---
__Pascal Bourguignon__ http://www.informatimago.com/
On May 24, 3:41 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Jean Guillaume Pyraksos <······@hotmail.com> writes:
>
> > I actually thought that all modern versions of Lisp considered
> > tail recursion as de facto optimized (bounded stack space).
> > If not, it is a considerable regression, see Python...
> > "Functional iteration" makes high sense IMHO.
> > Iteration is *not* a procedural-only concept.
>
> You must distinguish a recursive procedure from a recursive process,
> and an iterative procedure from an iterative process.
>
> A recursive procedure may behave recursively or iteratively depending
> on the kind of recursive calls it makes (terminal or non-terminal).
>
> When you have a recursive procedure with only terminal recursive calls,
> then you get an iterative process.
>
> When you have a recursive procedure with non terminal recursive calls,
> then you get a recursive process.
>
> When you have an iterative procedure with an iterative process, then
> unless it's an infinite loop, there's no other way than to change some
> state, it cannot be purely functional, inside that procedure.
>
> And of course, you cannot have an iterative procedure with a recursive
> process stricto-sensu ; you could manage the stack yourself, but as in
> the preceding case, you must also change the state (use a mutable
> stack or at least a mutable reference to a functional stack).
>
> +----------------------------------------------------------------------+
> | process: | iterative | recursive |
> +-----------------+-----------------------+----------------------------+
> | procedure: | | |
> | iterative | loop with state | loop with stack and state |
> | ----------------+----------||-----------+----------------------------+
> | recursive | function with only | function with non-tail |
> | | tail recursive calls | recursive calls |
> +-----------------+-----------------------+----------------------------+
>
> And since there's a trivial transformation between the two cells in
> the iterative process column, some languages mandate, and most CL
> implementations do implement Tail Call Optimization (which is also
> useful for non recursive tail calls).
>
> Notice that conceptually, there's no assignment in the case of a
> recursive procedure with iterative process, because the substitution
> rule may still be used to compute the result. Assignment here is only
> an detail at the level of the generated code that's useful because we
> have computer with finite memory.
>
There's no disagreeing that taxonomies like process and procedure are
helpful for people to learn idioms, but these are not precise. There
will always be corner cases that aren't clear. E.g. continuation-
passing style. Note all the calls to copy below are tail calls...
The "stack" is a chain of closures.
(defstruct (binop (:constructor new-binop (op lhs rhs))) op lhs rhs)
(defun copy (tree &optional (cont #'identity))
(if (binop-p tree)
(copy (binop-lhs tree)
(lambda (lhs)
(copy (binop-rhs tree)
(lambda (rhs)
(funcall cont
(new-binop (binop-op tree) lhs rhs))))))
(funcall cont tree)))
(defun test ()
(copy (new-binop :plus
(new-binop :times
'a
(new-binop :minus
3
'b))
'c)))
Yes, this CPS solution is standard and clean, but the problem now is to
transform closure into a first-order (still functional) stack...
I think that my two-phase solution is optimal, as the cost of walking
the tree is O(n) and the cost of building it is O(n) too. I would be
happy if I could interleave the two in a unique stack...
JG
In article
<····································@r34g2000vba.googlegroups.com>,
Gene <············@gmail.com> wrote:
> There's no disagreeing that taxonomies like process and procedure are
> helpful for people to learn idioms, but these are not precise. There
> will always be corner cases that aren't clear. E.g. continuation-
> passing style. Note all the calls to copy below are tail calls...
> The "stack" is a chain of closures.
>
> (defstruct (binop (:constructor new-binop (op lhs rhs))) op lhs rhs)
>
> (defun copy (tree &optional (cont #'identity))
> (if (binop-p tree)
> (copy (binop-lhs tree)
> (lambda (lhs)
> (copy (binop-rhs tree)
> (lambda (rhs)
> (funcall cont
> (new-binop (binop-op tree) lhs rhs))))))
> (funcall cont tree)))
>
> (defun test ()
> (copy (new-binop :plus
> (new-binop :times
> 'a
> (new-binop :minus
> 3
> 'b))
> 'c)))
From: Pascal J. Bourguignon
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <87y6sk5ncr.fsf@galatea.local>
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> Yes, this CPS solution is standard and clean, but the problem now is to
> transform closure into a first-order (still functional) stack...
> I think that my two-phase solution is optimal, as the cost of walking
> the tree is O(n) and the cost of building it is O(n) too. I would be
> happy if I could interleave the two in a unique stack...
You keep adding constraints! This is not a good way to get your
answer expeditively...
You've noted that my solution uses two stacks, but it's trivial to
transform it to use only one stack.
--
__Pascal Bourguignon__
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> Yes, this CPS solution is standard and clean, but the problem now is to
> transform closure into a first-order (still functional) stack...
> I think that my two-phase solution is optimal, as the cost of walking
> the tree is O(n) and the cost of building it is O(n) too. I would be
> happy if I could interleave the two in a unique stack...
But your solution uses O(n) temporary storage, while mines use only
O(depth(tree)). On the other hand mines being purely functional rely
either on a good compiler or a garbage collector.
;;; A copy-tree function that is functional (no setf),
;;; terminal-recursive, without continuations, and without functional
;;; parameters (1st order) and using only one stack:
;; First, two silly macros and functions avoiding recursion and need
;; for a stack:
(defmacro stack-push* (&rest elements-and-stack)
"(macroexpand '(stack-push* 1 2 3 4 stack))
--> (STACK-PUSH 1 (STACK-PUSH 2 (STACK-PUSH 3 (STACK-PUSH 4 STACK))))"
(if (endp (rest elements-and-stack))
(first elements-and-stack)
`(stack-push* ,@(butlast elements-and-stack 2)
(stack-push ,(first (last (butlast elements-and-stack)))
,(first (last elements-and-stack))))))
(defun substitute-nth (value n list)
(ecase n
((0) (list* value (rest list)))
((1) (list* (first list) value (rest (rest list))))
((2) (list* (first list) (second list) value (rest (rest (rest list)))))))
(defun copy-tree-jgp (tree)
(copy-tree-stack
(stack-push* (list 'copy tree)
'(done nil)
(make-stack))))
(defun copy-tree-stack (stack)
(declare (notinline copy-tree-stack))
(ecase (first (stack-top stack))
((done) ; (done node-copy) --
(second (stack-top stack)))
((copy) ; (copy ?node) (op ?x . ?r) -- (op ?node-copy . ?r)
(let ((node (second (stack-top stack)))
(place (stack-top (stack-pop stack))))
(copy-tree-stack (if (tree-empty-p node)
(stack-push (substitute-nth (make-empty-tree) 1 place)
(stack-pop (stack-pop stack)))
(stack-push* (list 'copy (tree-left node))
(list 'store :_ 2 1)
(list 'copy (tree-right node))
(list 'store :_ 0 2)
(list 'cons :left :right node)
(stack-pop stack))))))
((store) ; (store ?value ?down ?right) .. (op .. ?place ..) -- .. (op .. ?value ..)
;; Store the value in the ?down-th element in the stack, in the ?right-th slot.
;; ?down and ?right must be (member 0 1 2).
(copy-tree-stack
(destructuring-bind (op value down right) (stack-top stack)
(ecase down
((0)
(stack-push (substitute-nth value right (stack-top (stack-pop stack)))
(stack-pop (stack-pop stack))))
((1)
(stack-push*
(stack-top (stack-pop stack))
(substitute-nth value right (stack-top (stack-pop (stack-pop stack))))
(stack-pop (stack-pop (stack-pop stack)))))
((2)
(stack-push*
(stack-top (stack-pop stack))
(stack-top (stack-pop (stack-pop stack)))
(substitute-nth value right (stack-top (stack-pop (stack-pop (stack-pop stack)))))
(stack-pop (stack-pop (stack-pop (stack-pop stack))))))))))
((cons) ; (cons ?left ?right tree) (op ?place . ?rest) -- (op ?tree-copy . ?rest)
(destructuring-bind (op left right tree) (stack-top stack)
(copy-tree-stack (stack-push (substitute-nth (make-tree :label (tree-label tree)
:left left
:right right)
1
(stack-top (stack-pop stack)))
(stack-pop (stack-pop stack))))))))
--
__Pascal Bourguignon__
From: J Kenneth King
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <85y6skdma4.fsf@agentultra.com>
···@informatimago.com (Pascal J. Bourguignon) writes:
> Jean Guillaume Pyraksos <······@hotmail.com> writes:
>
>> Yes, this CPS solution is standard and clean, but the problem now is to
>> transform closure into a first-order (still functional) stack...
>> I think that my two-phase solution is optimal, as the cost of walking
>> the tree is O(n) and the cost of building it is O(n) too. I would be
>> happy if I could interleave the two in a unique stack...
>
> But your solution uses O(n) temporary storage, while mines use only
> O(depth(tree)). On the other hand mines being purely functional rely
> either on a good compiler or a garbage collector.
>
>
>
> ;;; A copy-tree function that is functional (no setf),
> ;;; terminal-recursive, without continuations, and without functional
> ;;; parameters (1st order) and using only one stack:
>
>
> ;; First, two silly macros and functions avoiding recursion and need
> ;; for a stack:
>
> (defmacro stack-push* (&rest elements-and-stack)
> "(macroexpand '(stack-push* 1 2 3 4 stack))
> --> (STACK-PUSH 1 (STACK-PUSH 2 (STACK-PUSH 3 (STACK-PUSH 4 STACK))))"
> (if (endp (rest elements-and-stack))
> (first elements-and-stack)
> `(stack-push* ,@(butlast elements-and-stack 2)
> (stack-push ,(first (last (butlast elements-and-stack)))
> ,(first (last elements-and-stack))))))
>
> (defun substitute-nth (value n list)
> (ecase n
> ((0) (list* value (rest list)))
> ((1) (list* (first list) value (rest (rest list))))
> ((2) (list* (first list) (second list) value (rest (rest (rest list)))))))
>
>
> (defun copy-tree-jgp (tree)
> (copy-tree-stack
> (stack-push* (list 'copy tree)
> '(done nil)
> (make-stack))))
>
>
>
> (defun copy-tree-stack (stack)
> (declare (notinline copy-tree-stack))
> (ecase (first (stack-top stack))
> ((done) ; (done node-copy) --
> (second (stack-top stack)))
> ((copy) ; (copy ?node) (op ?x . ?r) -- (op ?node-copy . ?r)
> (let ((node (second (stack-top stack)))
> (place (stack-top (stack-pop stack))))
> (copy-tree-stack (if (tree-empty-p node)
> (stack-push (substitute-nth (make-empty-tree) 1 place)
> (stack-pop (stack-pop stack)))
> (stack-push* (list 'copy (tree-left node))
> (list 'store :_ 2 1)
> (list 'copy (tree-right node))
> (list 'store :_ 0 2)
> (list 'cons :left :right node)
> (stack-pop stack))))))
>
> ((store) ; (store ?value ?down ?right) .. (op .. ?place ..) -- .. (op .. ?value ..)
> ;; Store the value in the ?down-th element in the stack, in the ?right-th slot.
> ;; ?down and ?right must be (member 0 1 2).
> (copy-tree-stack
> (destructuring-bind (op value down right) (stack-top stack)
> (ecase down
> ((0)
> (stack-push (substitute-nth value right (stack-top (stack-pop stack)))
> (stack-pop (stack-pop stack))))
> ((1)
> (stack-push*
> (stack-top (stack-pop stack))
> (substitute-nth value right (stack-top (stack-pop (stack-pop stack))))
> (stack-pop (stack-pop (stack-pop stack)))))
> ((2)
> (stack-push*
> (stack-top (stack-pop stack))
> (stack-top (stack-pop (stack-pop stack)))
> (substitute-nth value right (stack-top (stack-pop (stack-pop (stack-pop stack)))))
> (stack-pop (stack-pop (stack-pop (stack-pop stack))))))))))
> ((cons) ; (cons ?left ?right tree) (op ?place . ?rest) -- (op ?tree-copy . ?rest)
> (destructuring-bind (op left right tree) (stack-top stack)
> (copy-tree-stack (stack-push (substitute-nth (make-tree :label (tree-label tree)
> :left left
> :right right)
> 1
> (stack-top (stack-pop stack)))
> (stack-pop (stack-pop stack))))))))
>
> --
> __Pascal Bourguignon__
Been lurking this thread and I have to say, you're quite impressive Mr. Bourguignon. :)
From: Pascal J. Bourguignon
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <874ovbyddk.fsf@galatea.local>
Jean Guillaume Pyraksos <······@hotmail.com> writes:
> None, I do *want* a tail-recursive, purely functional, first order solution.
> I'll try myself, or prove me that this is impossible.
> I have already such a tail-recursive, purely functional, first order solution
> in O(n) but two-phase, in 2n iterative steps.
> I'm looking for a one-phase solution. I don't see on the theoretical side why
> I couldn't find one.
There exist one.
50 years ago, John McCarthy demonstrated that lambda-calculus was Turing complete.
The question is whether you really want to see it? I mean, usually
this kind of functions are produced by compilers, they're not pretty.
;;; A stack ADT:
(defun make-stack () '())
(defun stack-empty-p (stack) (endp stack))
(defun stack-push (element stack) (list* element stack ))
(defun stack-pop (stack) (rest stack))
(defun stack-top (stack) (first stack))
;;; A binary tree ADT:
(shadow 'copy-tree) ;; defstruct tree creates a copy-tree...
(defstruct tree label left right)
(defun make-empty-tree () 'nil)
(defun tree-empty-p (tree) (null tree))
(defun tree-leaf-node-p (tree) (and (not (tree-empty-p tree))
(tree-empty-p (tree-left tree))
(tree-empty-p (tree-right tree))))
(defmacro define-set-child-function (name child-accessor)
`(defun ,name (tree child)
(when (tree-empty-p tree)
(error "Cannot attach a child to an empty tree."))
(setf (,child-accessor tree) child)
tree))
(define-set-child-function tree-node-set-left-child tree-left)
(define-set-child-function tree-node-set-right-child tree-right)
;; ;; Note you may also use the following abstraction for a label-less
;; ;; binary-tree of CONS cells:
;;
;; (defun make-empty-tree () 'nil)
;; (defun tree-empty-p (tree) (null tree))
;; (defun tree-leaf-node-p (tree) (and (not (tree-empty-p tree))
;; (tree-empty-p (tree-left tree))
;; (tree-empty-p (tree-right tree))))
;; (defun make-tree (&key label left right) (cons left right))
;; (defun tree-label (tree) nil)
;; (defun tree-left (tree) (car tree))
;; (defun tree-right (tree) (cdr tree))
;;; A copy-tree function that is functional (no setf),
;;; terminal-recursive, without continuations, and without functional
;;; parameters (1st order):
(defun copy-tree-jgp (tree)
(copy-tree-state
(stack-push tree (make-stack))
(stack-push 'copy (stack-push 'done (make-stack)))))
(defun copy-tree-state (data state)
(declare (notinline copy-tree-state))
(let ((state-step))
(ecase (stack-top state)
((done) ; node-copy --
(stack-top data))
((copy) ; node -- node-copy
(copy-tree-state data
(stack-push 'left (stack-push 'right (stack-push 'cons (stack-pop state))))))
((left) ; node -- node left-copy
(let ((node (stack-top data)))
(if (tree-empty-p (tree-left node))
(copy-tree-state (stack-push node (stack-push (make-empty-tree) (stack-pop data)))
(stack-pop state))
(copy-tree-state (stack-push (tree-left node) data)
(stack-push 'copy (stack-push 'swap (stack-pop state)))))))
((right) ; node -- node right-copy
(let ((node (stack-top data)))
(if (tree-empty-p (tree-right node))
(copy-tree-state (stack-push node (stack-push (make-empty-tree) (stack-pop data)))
(stack-pop state))
(copy-tree-state (stack-push (tree-right node) data)
(stack-push 'copy (stack-push 'swap (stack-pop state)))))))
((swap) ; a b -- b a
(let ((a (stack-top data))
(b (stack-top (stack-pop data))))
(copy-tree-state (stack-push b (stack-push a (stack-pop (stack-pop data))))
(stack-pop state))))
((cons) ; node right-copy left-copy -- node-copy
(copy-tree-state (stack-push (make-tree :label (tree-label (stack-top data))
:right (stack-top (stack-pop data))
:left (stack-top (stack-pop (stack-pop data))))
(stack-pop (stack-pop (stack-pop data))))
(stack-pop state))))))
(copy-tree-jgp (make-tree :label 7))
(copy-tree-jgp (make-tree :label 7 :left (make-tree :label 6)))
(copy-tree-jgp (make-tree :label 7 :right (make-tree :label 8)))
(copy-tree-jgp (make-tree :label 7 :left (make-tree :label 6) :right (make-tree :label 8)))
(copy-tree-jgp
(make-tree :label 6
:left (make-tree :label 3
:left (make-tree :label 2
:left (make-tree :label 1))
:right (make-tree :label 4
:right (make-tree :label 5)))
:right (make-tree :label 8
:left (make-tree :label 7)
:right (make-tree :label 9))))
--
__Pascal Bourguignon__
From: Kaz Kylheku
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <20090604053122.130@gmail.com>
On 2009-05-23, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> None, I do *want* a tail-recursive, purely functional, first order solution.
> I'll try myself, or prove me that this is impossible.
The recursive form requires a transformation to continuation style, which
you said you didn't want.
I.e. you take the state variables from the iterative version, and turn them
into function parameters. Instead of updating the values of the variables and
iterating, you call back, specifying the new values of the state variables
as arguments to the parameters.
This is continuation style because your algorithm proceeds (i.e. continues) by
calling a function which is understood never to return. This is the essence
of how tail recursion expresses algorithms.
Anyway, here is a rewrite of the original copy-tree-iterative according
to this concept. This version no longer borrows conses from the stack, because
that requires us to destructively manipulate the cons.
(defun copy-tree-tail (tree)
(labels
((copy-it (state stack car cdr tree)
(cond
((atom tree) tree)
((and (eq state :up) (null stack)) (cons car cdr))
(t
(ecase state
(:car
(cond
((consp (car tree))
(copy-it :car (cons `(:cdr ,tree nil) stack)
car cdr (car tree)))
(t
(copy-it :cdr stack (car tree) nil tree))))
(:cdr
(cond
((consp (cdr tree))
(copy-it :car (cons `(:up ,tree ,car) stack)
car cdr (cdr tree)))
(t
(copy-it :up stack car (cdr tree) tree))))
(:up
(destructuring-bind (pop-state pop-tree pop-car) (first stack)
(ecase pop-state
(:car (error "copy-tree-tail: internal error"))
(:cdr (copy-it pop-state (cdr stack)
(cons car cdr) nil pop-tree))
(:up (copy-it pop-state (cdr stack)
pop-car (cons car cdr) pop-tree))))))))))
(copy-it :car nil nil nil tree)))
Now, this isn't really tail recursion because Lisp doesn't have tail recursion.
Lisp compilers provide tail recursion as an optimization, not as the semantics
of function calling.
However, we can convert the above to tail recursion by making a trivial change,
namely changing
(labels ...)
to
(tailprog () ...)
This TAILPROG is not a standard Lisp macro, but one that I developed.
TAILPROG allows iteration to be expressed using constructs that resemble
functions; i.e. it implements tail recursion. The difference between this
and the usual implementations of tail recursion is that the tail calls are
always tail calls, even if they are not in a tail position. They are
understood to be a syntactic sugar for GO, and thus never return.
TAILPROG has a syntax similar to LABELS except that complex lambda lists are
not supported (&optional, &rest, etc) and there is an extra syntactic element:
the provision for binding some additional state variables, similar to PROG.
The source code is this:
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun argtags-compile-goto (label args block-name labels)
(let* ((matching-label (find label labels :key #'first)))
(unless matching-label
(error "ARGTAGS: goto undefined label ~a in block ~a"
label block-name))
(destructuring-bind (name vars gensyms thunk-label)
matching-label
(declare (ignore name))
(when (/= (length args) (length vars))
(error "ARGTAGS: label ~a called with wrong argument count in block ~a"
label block-name))
`(progn
,@(if args `((psetf ,@(mapcan (lambda (gensym arg)
`(,gensym ,arg))
gensyms args))))
(go ,thunk-label))))))
(defmacro argtags (block-name &rest labels-and-forms)
(unless (symbolp block-name)
(error "ARGTAGS: block name must be a symbol, not ~a!" block-name))
(let (labels forms thunks thunk-gensyms)
(dolist (item labels-and-forms)
(cond
((symbolp item)
(push `(,item () () ,item) labels)
(push item forms))
((and (consp item)
(eq (first item) 'label))
(unless (and (symbolp (second item))
(listp (rest (rest item)))
(every #'symbolp (rest (rest item))))
(error "ARGTAGS: bad label syntax ~a in block ~a" item block-name))
(destructuring-bind (op label &rest vars) item
(let ((gensyms (mapcar (lambda (var)
(gensym (symbol-name var)))
vars))
(thunk-label (gensym (symbol-name label))))
(push `(,label ,vars ,gensyms ,thunk-label) labels)
(push thunk-label thunks)
(push
`(psetf ,@(mapcan (lambda (realvar gensym)
`(,realvar ,gensym))
vars gensyms))
thunks)
(push `(go ,label) thunks)
(setf thunk-gensyms (append gensyms thunk-gensyms))
(push label forms))))
(t
(push item forms))))
`(macrolet ((goto (label &rest args)
(argtags-compile-goto label args ',block-name ',labels)
))
(block ,block-name
(let (,@thunk-gensyms)
(tagbody
,@(nreverse forms)
(return-from ,block-name)
,@(nreverse thunks)))))))
(defmacro tailprog (let-bindings pseudo-funcs &rest forms)
(let (argtags-forms macrolet-elems)
(dolist (pfunc pseudo-funcs)
(destructuring-bind (name vars &rest forms) pfunc
(push `(label ,name ,@vars) argtags-forms)
(push `(return (progn ,@forms)) argtags-forms)
(push `(,name (&rest args) `(goto ,',name ,@args)) macrolet-elems)))
`(macrolet (,.(nreverse macrolet-elems))
(let ,let-bindings
(argtags nil
(return (progn ,@forms))
,.(nreverse argtags-forms))))))
From: Kaz Kylheku
Subject: Re: iterative copying of binary expression trees
Date:
Message-ID: <20090602085107.26@gmail.com>
On 2009-05-21, Jean Guillaume Pyraksos <······@hotmail.com> wrote:
> Hi, a small problem. Let's use binary trees. Leaves are themselves
> and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
>
> Ex: tree(+,tree(*,x,2),tree(-,y,1))
> which represents (+ (* x 2) (- y 1)) in Lisp for example.
>
> Problem : program copytree(t) which returns a copy of the tree t,
> functionally of course, but with an iterative (tail recursive)
> process, using a stack.
Common Lisp has a function called copy-tree. You're wasting your time
on useless exercises. The greatest lesson a student can learn is
``know thy standard library, and don't reinvent the wheel''.
> I solve this with a two-phase algorithm :
>
> 1. first build *iteratively* the postfix walking of the tree into a list :
> (+ x 2 * y 1 - +)
> For that I push the left son onto the stack and dive into the right son.
> 2. then walk *iteratively* this list to rebuild a new tree.
Your requirements are conflicting. The iterative solution to the problem
will certainly not be working ``functionally of course'', since it will
have to contain stack manipulation (push/pop) which is destructive, and
probably assignments.
Secondly, if you use a stack, then you're not really avoiding recursion. Even
tail recursion with an explicit stack is not really tail recursion. All you
have done is taken the call stack, and turned it into an explicit data
structure which does exactly the same thing and has the same memory use
complexity as recursion.
I.e. this is a disingenous way of avoiding recursion that relies on word
semantics, rather than actually changing the recursive algorithm to one
that requires only constant space.
Explicit stacks make sense when there are some implementation problems to
overcome. Perhaps the regular stack is too small; the recursion runs into stack
exhaustion. Maybe function calls are badly optimized; profiling shows that the
iterative version with explicit stack runs faster.
We could try to rescue this approach, be re-using nodes from the stack as
the building material for the copied tree. Ideally, if the entire stack
(i.e. with no waste) could be re-used for the copied tree structure, we could
claim that the algorithm requires no additional memory for its own bookkeeping.
Here is a version which has waste. The stack is used as the source of material
for building the copied tree, but the stack has has four conses
per record, and each record supplies only one cons to the tree being built.
I.e. the cons structure of the copied tree is only ``25% recycled materials'',
so to speak.
The challenge is to improve this. One obvious way is to use a slightly denser
representation for the stack. I.e. instead of a stack like
((:cdr <tree> <tree>) (:up <tree> <tree>) ...)
it could be flat, so that it only uses three conses per record:
(:cdr <tree> <tree> :up <tree> <tree> ...)
The function:
(defun copy-tree-iterative (tree)
(if (atom tree)
tree
(loop with stack = nil
with state = :car ;; tells us which way to navigate
with car = nil ;; holds left data of tree node to build
with cdr = nil ;; holds right data of tree node to build
until (and (eq state :up) (null stack))
finally (return (cons car cdr))
do
(ecase state
(:car
(cond
((consp (car tree))
(push `(:cdr ,tree nil) stack)
(setf tree (car tree)))
(t
(setf car (car tree))
(setf state :cdr))))
(:cdr
(cond
((consp (cdr tree))
(push `(:up ,tree ,car) stack)
(setf tree (cdr tree))
(setf state :car))
(t
(setf cdr (cdr tree))
(setf state :up))))
(:up
(destructuring-bind (pop-state pop-tree pop-car) (first stack)
(let ((cons (pop stack)))
(setf (car cons) car)
(setf (cdr cons) cdr)
(ecase pop-state
(:car
(error "copy-tree-iterative: internal error"))
(:cdr
(setf car cons))
(:up
(setf car pop-car)
(setf cdr cons))))
(setf state pop-state)
(setf tree pop-tree)))))))
On May 21, 2:27 pm, Jean Guillaume Pyraksos <······@hotmail.com>
wrote:
> Hi, a small problem. Let's use binary trees. Leaves are themselves
> and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
>
> Ex: tree(+,tree(*,x,2),tree(-,y,1))
> which represents (+ (* x 2) (- y 1)) in Lisp for example.
>
> Problem : program copytree(t) which returns a copy of the tree t,
> functionally of course, but with an iterative (tail recursive)
> process, using a stack.
>
> I solve this with a two-phase algorithm :
>
> 1. first build *iteratively* the postfix walking of the tree into a list :
> (+ x 2 * y 1 - +)
> For that I push the left son onto the stack and dive into the right son.
> 2. then walk *iteratively* this list to rebuild a new tree.
>
> Is there a more simple one-phase way (iterative and functional,
> first order please, no CPS) to get this algorithm ?
>
Use a standard explicit-stack post-order tree traversal. As you visit
each node in post order, you'll have all the information needed to
build a copy.
In article
<····································@g20g2000vba.googlegroups.com>,
Gene <············@gmail.com> wrote:
> On May 21, 2:27�pm, Jean Guillaume Pyraksos <······@hotmail.com>
> wrote:
> > Hi, a small problem. Let's use binary trees. Leaves are themselves
> > and nodes are built with tree(r,ls,rs). I won't speak in Lisp.
> >
> > Ex: tree(+,tree(*,x,2),tree(-,y,1))
> > which represents (+ (* x 2) (- y 1)) in Lisp for example.
> >
> > Problem : program copytree(t) which returns a copy of the tree t,
> > functionally of course, but with an iterative (tail recursive)
> > process, using a stack.
> >
> > I solve this with a two-phase algorithm :
> >
> > 1. first build *iteratively* the postfix walking of the tree into a list :
> > � (+ x 2 * y 1 - +)
> > � For that I push the left son onto the stack and dive into the right son.
> > 2. then walk *iteratively* this list to rebuild a new tree.
> >
>
> Use a standard explicit-stack post-order tree traversal. As you visit
> each node in post order, you'll have all the information needed to
> build a copy.
It's exactly my solution... Thanks.
JG