[Openmcl-devel] consing

[Ron Garret]

Yes, the Ackerman function is notorious for this behavior.  Have you read anything about the Ackerman function?  Or tried to use some basic debugging tools (like TRACE and PRINT) to explore its behavior?

rg


On May 14, 2013, at 9:23 AM, Taoufik Dachraoui wrote:

> I did the following test with (fac 100) and (ack 3 12) and (ack 3 13) ;;  ack is the ackermann function
> 
> CL-USER> (time (fac 100))
> (FAC 100)
> took 0 milliseconds (0.000 seconds) to run.
> During that period, and with 1 available CPU core,
>      0 milliseconds (0.000 seconds) were spent in user mode
>      0 milliseconds (0.000 seconds) were spent in system mode
>  3,864 bytes of memory allocated.
> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> 
> CL-USER> (time (ack 3 12))
> (ACK 3 12)
> took 3,325 milliseconds (3.325 seconds) to run.
> During that period, and with 1 available CPU core,
>      3,360 milliseconds (3.360 seconds) were spent in user mode
>          0 milliseconds (0.000 seconds) were spent in system mode
> 32765
> 
> (ack 3 13) fails with stack overflow, this I do not understand; (ack 3 12) did not show any use of memory allocation 
> and (ack 3 13) fails for stack overflow?
> 
> Taoufik
> 
> 
> 
> 
> 
> On Tue, May 14, 2013 at 6:09 PM, Joshua TAYLOR <joshuaaaron at gmail.com> wrote:
> On Tue, May 14, 2013 at 11:52 AM, Taoufik Dachraoui
> <dachraoui.taoufik at gmail.com> wrote:
> > What is not true? I am not saying that stacks are conses; we can push and
> > pop elements from a stack and macroexpanding (PUSH 1 X) gives (SETQ X (CONS
> > 1 X)); so the stack, used by pop/push, in CCL is implemented
> > using conses; we can implement stacks using arrays (no consing) if we wish
> > so.
> >
> > Now, the reason I am asking, is that I am implementing an interpreter for a
> > small language and I am using 3 stacks with a lot of consing. I wanted to
> > find a solution so that I can avoid consing; I recalled when we call a
> > function the passed parameters are pushed into a stack (implemented with
> > registers ESP/EBP), I am wondering if I can find a way to use the
> > processor's stack as for function calls to avoid consing.
> >
> > Or, how do you implement a VM using CCL for a new language? (any thing
> > offered by CCL even if it is not
> > standard would be acceptable).
> 
> 1) Although the machine stack stores things in machine memory (the
> program stack), when people talk about a program "cons'ing a lot" or
> allocating lots of memory, they're almost always talking about
> heap-allocated space.  Even though they use the word "cons'ing", it
> doesn't even have to be cons cells;  it's any heap allocation (so
> class objects, arrays, etc., are all included).  This code doesn't
> really need any heap space, so it's not consing.
> 2) Although the program has a stack, the program/machine stack is not
> (typically (does anyone know of any exceptions?)) implemented by a
> reusable abstract data structure known as a stack.  The push/pop model
> happens to be the same, but the program stack is just about
> incrementing and decrementing the CPU's stack pointer.
> 
> //JT
> --
> Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
> 
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.clozure.com/pipermail/openmcl-devel/attachments/20130514/70f01777/attachment.htm>