Re: to big nest level of recursion

Re: to big nest level of recursion

[David Reitter]

[-- Attachment #1.1: Type: text/plain, Size: 680 bytes --]

> 2) Pascal Bourguignon mentioned TCO. Is it relatively right recursion
> handling? Why does it works only with boolean expressions? I thought
> that it is enougth to make recursive call the last in the expression
> (as it is in Haskell). Where can I read about it?

TCO = tail call optimization, just what you were referring to.

In Prolog, I'd formulate the algorithm just like you did. In elisp,  
you can't, because stack size is small and there is obviously no TCO.

http://en.wikipedia.org/wiki/Tail_recursion

Maybe it's a consolation for you that for every recursive algorithm,  
you can formulate an iterative version. And you don't bloat a call  
stack when you do so.


[-- Attachment #1.2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2454 bytes --]

[-- Attachment #2: Type: text/plain, Size: 152 bytes --]

_______________________________________________
help-gnu-emacs mailing list
help-gnu-emacs@gnu.org
http://lists.gnu.org/mailman/listinfo/help-gnu-emacs

Re: to big nest level of recursion

[Alan Mackenzie]

David Reitter <david.reitter@gmail.com> wrote on Tue, 21 Mar 2006
21:31:29 +0000:

[ .... ]

> Maybe it's a consolation for you that for every recursive algorithm,
> you can formulate an iterative version. And you don't bloat a call
> stack when you do so.

This is not true.  There are algorithms that are intrinsically recursive
and cannot be formulated with mere iteration (such as the Ackermann
function, specially invented to demonstrate this).

-- 
Alan Mackenzie (Munich, Germany)
Email: aacm@muuc.dee; to decode, wherever there is a repeated letter
(like "aa"), remove half of them (leaving, say, "a").

Re: to big nest level of recursion

[David Kastrup]

Alan Mackenzie <acm@muc.de> writes:

> David Reitter <david.reitter@gmail.com> wrote on Tue, 21 Mar 2006
> 21:31:29 +0000:
>
> [ .... ]
>
>> Maybe it's a consolation for you that for every recursive algorithm,
>> you can formulate an iterative version. And you don't bloat a call
>> stack when you do so.
>
> This is not true.  There are algorithms that are intrinsically
> recursive and cannot be formulated with mere iteration (such as the
> Ackermann function, specially invented to demonstrate this).

They cannot be formulated with iteration _without_ a stack.  But of
course, when using a stack as a data structure, you can map any
recursion onto iteration.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: to big nest level of recursion

[david.reitter]

David Kastrup:

> They cannot be formulated with iteration _without_ a stack.  But of
> course, when using a stack as a data structure, you can map any
> recursion onto iteration.

Yes, and such a stack is likely to be more space-efficient than a call
stack, as it can be manually optimized to only contain what's
necessary.

The interesting question here is, of course, whether elisp should
support recursion better than it does now, with larger call stacks and
the necessary optimization. It has survived decades without it...

to big nest level of recursion

[Anton V. Belyaev]

Hi! I wrote a simple function which fails on lists long enougth with
reason "(error "Lisp nesting exceeds `max-lisp-eval-depth'")". But the
function contains right recursion. Does Emacs LISP interpreter unwind
right recursion calls?

(defun contains (lst el)
  (if (null lst)
      nil
    (if (eq (car lst) el)
	t
      (contains (cdr lst) el)
      )
    )
  )

PS: Does Emacs built-in functions have an equivalent of my contains?

Re: to big nest level of recursion

[Hans-Christoph Wirth]

Anton V. Belyaev <anton.belyaev@gmail.com> wrote:
> 
>  PS: Does Emacs built-in functions have an equivalent of my contains?

member

Re: to big nest level of recursion

[David Kastrup]

"Anton V. Belyaev" <anton.belyaev@gmail.com> writes:

> Hi! I wrote a simple function which fails on lists long enougth with
> reason "(error "Lisp nesting exceeds `max-lisp-eval-depth'")". But the
> function contains right recursion. Does Emacs LISP interpreter unwind
> right recursion calls?
>
> (defun contains (lst el)
>   (if (null lst)
>       nil
>     (if (eq (car lst) el)
> 	t
>       (contains (cdr lst) el)
>       )
>     )
>   )
>
> PS: Does Emacs built-in functions have an equivalent of my contains?

Hardly ever seen something more contorted.  This can be written as

(defun contains (lst el)
  (and lst
       (or (eq (car lst) el)
           (contains (cdr lst) el))))

And without recursion as

(defun contains (lst el)
  (while (and lst (not (eq (car lst) el)))
     (pop lst))
  lst)

And it is available anyway as the basic function "memq", cf
(info "(elisp) Sets and Lists")

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: to big nest level of recursion

[Pascal Bourguignon]

"Anton V. Belyaev" <anton.belyaev@gmail.com> writes:

> Hi! I wrote a simple function which fails on lists long enougth with
> reason "(error "Lisp nesting exceeds `max-lisp-eval-depth'")". But the
> function contains right recursion. Does Emacs LISP interpreter unwind
> right recursion calls?
>
> (defun contains (lst el)
>   (if (null lst)
>       nil
>     (if (eq (car lst) el)
> 	t
>       (contains (cdr lst) el)
>       )
>     )
>   )

Let's make it readable:

1- indentation and parenthesis placement:

(defun contains (lst el)
   (if (null lst)
       nil
       (if (eq (car lst) el)
          t
          (contains (cdr lst) el))))

2- use of cond in place of if sequences:

 (defun contains (lst el)
   (cond ((null lst)         nil)
         ((eq (car lst) el)  t))
         (t                  (contains (cdr lst) el)))

3- since all the branches return a boolean anyway, we can write it as
   a boolean expression directly:

 (defun contains (lst el)
   (and (not (null lst))  (or (eq (car lst) el)  (contains (cdr lst) el))))



Otherwise, emacs doesn't do TCO.


> PS: Does Emacs built-in functions have an equivalent of my contains?

member


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

HANDLE WITH EXTREME CARE: This product contains minute electrically
charged particles moving at velocities in excess of five hundred
million miles per hour.

Re: to big nest level of recursion

[Anton V. Belyaev]

Thanks too all of you!

I have some questions relative to your answers. Maybe I should post
them into separate topic, but anyway.

1) This nice intendation:

(defun contains (lst el)
   (if (null lst)
       nil
       (if (eq (car lst) el)
          t
          (contains (cdr lst) el))))

When I place it to my Emacs and do M-x intend-region, it applies the
crazy intendation from my first post. How can I enable nice
intendation?

2) Pascal Bourguignon mentioned TCO. Is it relatively right recursion
handling? Why does it works only with boolean expressions? I thought
that it is enougth to make recursive call the last in the expression
(as it is in Haskell). Where can I read about it?

Re: to big nest level of recursion

[Stefan Monnier]

> When I place it to my Emacs and do M-x intend-region, it applies the
> crazy intendation from my first post. How can I enable nice
> intendation?

Pascal's indentation is the one used in Scheme and (IIRC) Common Lisp.
In Emacs Lisp, we use the so-called "crazy" indentation.


        Stefan