Re: Ack function hanging LWL 4.4

Sean,

Unsafe, compiled recursive code has a tendency to behave a little bit  
aggresive when the stack overflows ;-)
If you expand the stack enough, things are fine:

CL-USER 1 > (defun ack (m n)
               (cond
                ((zerop m) (1+ n))
                ((zerop n) (ack (1- m) 1))
                (t (ack (1- m) (ack m (1- n))))))
ACK

CL-USER 2 > (compile 'ack)
ACK
NIL
NIL

CL-USER 3 > (ack 3 10)

Stack overflow (stack size 32000).
   1 (continue) Extend stack by 50%.
   2 Extend stack by 300%.
   3 (abort) Return to level 0.
   4 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed,  or :? for other  
options

CL-USER 4 : 1 > :c

Stack overflow (stack size 48000).
   1 (continue) Extend stack by 50%.
   2 Extend stack by 300%.
   3 (abort) Return to level 0.
   4 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed,  or :? for other  
options

CL-USER 5 : 1 > :c
8189

CL-USER 6 > (time (ack 3 10))
Timing the evaluation of (ACK 3 10)

user time    =      1.500
system time  =      0.020
Elapsed time =   0:00:02
Allocation   = 7180 bytes
3 Page faults
8189

CL-USER 7 > (defun ack (m n)
               (declare (fixnum n m) (values fixnum)
                        (optimize (speed 3) (debug 0) (safety 0)))
               (cond
                ((zerop m) (1+ n))
                ((zerop n) (ack (1- m) 1))
                (t (ack (1- m) (ack m (1- n))))))
ACK

CL-USER 8 > (compile 'ack)
ACK
NIL
NIL

CL-USER 9 > (ack 3 10)
8189

CL-USER 10 > (time (ack 3 10))
Timing the evaluation of (ACK 3 10)

user time    =      1.340
system time  =      0.030
Elapsed time =   0:00:02
Allocation   = 5248 bytes
1 Page faults
8189

The declarations don't seem to add a lot of speedup though ;-)
This was done on LispWorks for Macintosh 4.4 on a PowerBook G4.

HTH,

Sven

On 01 Mar 2005, at 09:20, Sean Ross wrote:

>
> Hi,
>
> I've run across a problem when running the following ack function
> on LWL 4.4
>
> (defun ack (m n)
>   (declare (fixnum n m) (values fixnum)
>            (optimize (speed 3) (debug 0) (safety 0)))
>   (cond
>    ((zerop m) (1+ n))
>    ((zerop n) (ack (1- m) 1))
>    (t (ack (1- m) (ack m (1- n))))))
>
> (compile 'ack)
>
>
> Running (ack 3 10) causes the editor the hang
> indefinitely (or it at least seems that way).
>
> Running (ack 3 10) in a console image ends up
> in the return value being printed out but then
> the image dies without an error.
>
> Timing it however causes the following error messages.
>
> CL-USER 1 > (time (ack 3 10))
> Timing the evaluation of (ACK 3 10)
> ; Loading fasl file  
> /usr/local/lib/LispWorks/lib/4-4-0-0/load-on-demand/pcl/util/ 
> callcoun.ufsl
> <**>Fatal recursive stack overflow.
> Simple backtrace:
>
> 21423e28 200487ea #<cfo 200487a2>
>
> 21423e40 207b750e DEMAND-LOOKUP-METHOD-GUARDED
>
> 21423e48 20ae98de DCODE-MISS-NEW
>
> 21423e94 20808d98 CACHE-MISS-FUNCTION
>
> 21423ebc 207e24dd #<cfo 207e23e2>
>
> 21423ee8 20848b09 MAKE-INSTANCE-FROM-CLASS-1
>
> 21423f18 207b5052 MAKE-CONDITION
>
> 21423f28 2032be32 SAFE-COERCE-TO-CONDITION
>
> 21423f84 00000001 NIL
>
> I'm assuming that the (safety 0) declaration is involved in
> this, but with safety > 0 a stack overflow error is signalled.
>
> I've also noticed the same thing happening when computing factorials
> using a naive algorithm. Is it possible to get this to work
> while keeping the recursive algorithm or is this a known
> limitation?
>
>
> Thanks,
>   Sean.
>
> -- 
> "My doctor says that I have a malformed public-duty gland and a
>  natural  deficiency in moral fibre," he muttered to himself, "and
>  that I am therefore excused from saving Universes."
>  - Life, the Universe, and Everything     Douglas Adams.
>
>

--
Sven Van Caekenberghe - mailto:sven@beta9.be
Beta Nine - software engineering - http://www.beta9.be
..Mac - svc@mac.com - http://homepage.mac.com/svc

"Lisp isn't a language, it's a building material." - Alan Kay

Re: Ack function hanging LWL 4.4 (int32 api)

Sven Van Caekenberghe <sven@beta9.be> writes:

> Sean,
> 
> Unsafe, compiled recursive code has a tendency to behave a little bit
> aggresive when the stack overflows ;-)
> If you expand the stack enough, things are fine:
Thanks, 
  Lispworks for Linux doesn't have restarts to increase the stack
  size, but one of the config options in the editor does which 
  fixes the problem.
  
 I've also tried experimenting with the int32 api but I'm unable
 to get anything working at nearly the same speed as a plain ack
 with no declarations.  Currently I've got the following function
 
 (defun ack2 (m n)
  (declare (optimize (float 0)))
  (cond ((sys:int32-zerop m) (sys:int32-1+ n))
         ((sys:int32-zerop n) (ack2 (sys:int32-1- m) sys:+int32-1+))
         (t (ack2 (sys:int32-1- m) (ack2 m (sys:int32-1- n))))))
 
 but this is about 20-30 times slower than the plain ack.
 It seems like this is caused by ack2 consing a lot more
 (100321688 bytes standard / 3421 bytes conses) as opposed 
 to (0 bytes standard / 0 bytes conses).

 Declaring the type m and n along with declarations for 
 return types has a small effect but is still much slower.

 Has anyone else had more luck using these new functions?
 
Thanks,
 Sean.

-- 
"My doctor says that I have a malformed public-duty gland and a
 natural  deficiency in moral fibre," he muttered to himself, "and
 that I am therefore excused from saving Universes."
 - Life, the Universe, and Everything     Douglas Adams.

Re: Ack function hanging LWL 4.4 (int32 api)

Unable to parse email body. Email id is 3582