compilation of tail recursive functions

--Alt-Boundary-6156.32940475
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Content-description: Mail message body

Am 16 Feb 2006 um 21:56 hat Mario Rodriguez geschrieben: 

Hello Mario, 
I am using Windows-Maxima 5.9.2 with GCL. 

Are you able to calculate n_sum_1(1000000,0);  
without compilation? 

My interest is concentrated on the compilation behaviour. What does clisp do, when you  
compile n-sum-1? 
Is there a tail recursive optimization? 

If I compile Lisp code with GCL, there is a tail recursive optimization. 
I would like to have it under Maxima as well.  

The problem seems to be, that the translated function is wrapped with the additional  
SIMPLIFY . After this the compiler is not able to recognize the function as tail recursive. 

(PROGN 
  (DEFPROP $N_SUM_1 T TRANSLATED) 
  (ADD2LNC '$N_SUM_1 $PROPS) 
  (DEFMTRFUN ($N_SUM_1 $ANY MDEFINE NIL NIL) ($N $RES) 
      (DECLARE (SPECIAL $RES $N)) 
      (COND 
        ((LIKE $N 0) $RES) 
        (T ;(SIMPLIFY 
               (MFUNCTION-CALL $N_SUM_1 (ADD* $N -1) (ADD* $N $RES))))));) 

The translation is done by Maxima. So I expect, that you have the same code and I  
expect, that clisp will not optimize too. 

The optimization is a conceptual thing. Will Maxima generally miss this or is there a  
way to realize it? 

Volker 

> Hallo Volker, 
>  
>  
>  
> >  
> > (C1) n_sum_1(n,res):= 
> >   if n=0 then res 
> >   else n_sum_1(n-1,n+res)$ 
> > (C2) n_sum_1(1000,0);	--->  Bind stack overflow. 
> >  
>  
> I don't see any problems here: 
>  
> Maxima 5.9.2.19cvs http://maxima.sourceforge.net 
> Using Lisp CLISP () 
> Distributed under the GNU Public License. See the file COPYING. 
> Dedicated to the memory of William Schelter. 
> This is a development version of Maxima. The function bug_report() 
> provides bug reporting information. 
> (%i1) n_sum_1(n,res):= 
>   if n=0 then res 
>   else n_sum_1(n-1,n+res)$ 
> (%i2) n_sum_1(1000,0); 
> (%o2)                               500500 
>  
>  
>  
> could that be a GCL specific problem? 
>  
> By the way, which Maxima version are you running? 
>  
> Bis bald. 
> --  
> Mario Rodriguez Riotorto 
> www.biomates.net 
>  



--Alt-Boundary-6156.32940475
Content-type: text/html; charset=US-ASCII
Content-transfer-encoding: 7BIT
Content-description: Mail message body

<?xml  version="1.0" ?><html>
<head>
<title></title>
</head>
<body>
<div align="left"><font face="Arial"><span style="font-size:10pt">Am 16 Feb 2006 um 21:56 hat Mario Rodriguez geschrieben: </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Hello Mario, </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">I am using Windows-Maxima 5.9.2 with GCL. </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Are you able to calculate </span></font><font face="Arial" color="#7f0000"><span style="font-size:10pt">n_sum_1(1000000,0);&#160; </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">without compilation? </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">My interest is concentrated on the compilation behaviour. What does clisp do, when you 
compile n-sum-1? </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Is there a tail recursive optimization? </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">If I compile Lisp code with GCL, there is a tail recursive optimization. </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">I would like to have it under Maxima as well.&#160; </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">The problem seems to be, that the translated function is wrapped with the additional&#160; </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">SIMPLIFY . After this the compiler is not able to recognize the function as tail recursive. </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">(PROGN </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160; (DEFPROP $N_SUM_1 T TRANSLATED) </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160; (ADD2LNC '$N_SUM_1 $PROPS) </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160; (DEFMTRFUN ($N_SUM_1 $ANY MDEFINE NIL NIL) ($N $RES) </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160;&#160;&#160;&#160;&#160; (DECLARE (SPECIAL $RES $N)) </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160;&#160;&#160;&#160;&#160; (COND </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160;&#160;&#160;&#160;&#160;&#160;&#160; ((LIKE $N 0) $RES) </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160;&#160;&#160;&#160;&#160;&#160;&#160; (T ;(SIMPLIFY </span></font></div>
<div align="left"><font face="Arial"><span style="font-size:10pt">&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; (MFUNCTION-CALL $N_SUM_1 
(ADD* $N -1) (ADD* $N $RES))))));) </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">The translation is done by Maxima. So I expect, that you have the same code and I 
expect, that clisp will not optimize too. </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">The optimization is a conceptual thing. Will Maxima generally miss this or is there a 
way to realize it? </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial"><span style="font-size:10pt">Volker </span></font></div>
<div align="left"><br/>
</div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Hallo Volker, </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt; (C1) n_sum_1(n,res):= </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt;&#160;&#160; if n=0 then res </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt;&#160;&#160; else n_sum_1(n-1,n+res)$ </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt; (C2) n_sum_1(1000,0);&#160;&#160;&#160;&#160;&#160;&#160;&#160;---&gt;&#160; Bind 
stack overflow. </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; &gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; I don't see any problems here: </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Maxima 5.9.2.19cvs </span></font><font face="Arial" color="#008000"><span style="font-size:10pt"><u>http://maxima.sourceforge.net</u></span></font><font 
face="Arial" color="#7f0000"><span style="font-size:10pt"> </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Using Lisp CLISP () </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Distributed under the GNU Public License. See the file COPYING. </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Dedicated to the memory of William Schelter. </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; This is a development version of Maxima. The function bug_report() </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; provides bug reporting information. </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; (%i1) n_sum_1(n,res):= </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160;&#160; if n=0 then res </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160;&#160; else n_sum_1(n-1,n+res)$ </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; (%i2) n_sum_1(1000,0); </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; (%o2)&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; 
500500 </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; could that be a GCL specific problem? </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; By the way, which Maxima version are you running? </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Bis bald. </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; --&#160; </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; Mario Rodriguez Riotorto </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt; www.biomates.net </span></font></div>
<div align="left"><font face="Arial" color="#7f0000"><span style="font-size:10pt">&gt;&#160; </span></font></div>
<div align="left"><br/></div>
<div align="left"></div>
</body>
</html>

--Alt-Boundary-6156.32940475--