home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / c / 12855 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  2.0 KB
  1. Xref: sparky comp.lang.c:12855 comp.programming:2498
  2. Path: sparky!uunet!mcsun!sunic!dkuug!diku!juul
  3. From: juul@diku.dk (Anders Juul Munch)
  4. Newsgroups: comp.lang.c,comp.programming
  5. Subject: Re: A LITTLE BRAINTEASER... -- generalized
  6. Message-ID: <1992Aug25.170209.22466@odin.diku.dk>
  7. Date: 25 Aug 92 17:02:09 GMT
  8. References: <aet.713608023@munagin>
  9. Sender: juul@rimfaxe.diku.dk
  10. Organization: Department of Computer Science, U of Copenhagen
  11. Lines: 47
  12.  
  13. aet@mullian.ee.mu.OZ.AU (bert thompson) writes:
  14. [...]
  15. >the rules of the game are you can use anything but data structures, or more
  16. >specifically you cannot use the heap.
  17. [...]
  18. >can we make do using only the stack? do any functions require more?
  19. >(non-primitive recursive functions like ackermann's -- just guessing. 8^)
  20.  
  21. >apologies if this question turns out to be really easy.
  22.  
  23. You are asking if C without heap allocation is Turing equivalent. I think it
  24. is.
  25.  
  26. Here's a memory allocator that allocates off the stack...
  27.  
  28. typedef struct mem { DATA d; struct mem* next; } MEM;
  29.  
  30. void stackalloc(int cnt,MEM* tail, void (*fn)(MEM*))
  31. {
  32.   if(cnt == 0)
  33.     fn(tail);
  34.   else
  35.   {
  36.     MEM m;
  37.     m.next = tail;
  38.     stackalloc(cnt-1,&m,fn);
  39.   }
  40. }
  41.  
  42. How to write accessor functions
  43.     DATA At(MEM*,int loc);
  44. and    void AtPut(MEM*,int loc,DATA val);
  45. should be obvious.
  46.  
  47. When you need n units of storage, you just call
  48.     stackalloc(cnt,NULL,my_memory_consumer);
  49. my_memory_consumer is a continuation function that uses the memory
  50. allocated (circumventing the problem that the memory cannot be returned
  51. directly due to stack unwinding with dangling pointers). Using
  52. continuations is impractical, but I don't think it's a serious restriction.
  53. Further arguments to the continutiations could easily be passed through a
  54. modificed `stackalloc'.
  55.   Ackerman's function is certainly no problem (just a lot of work).
  56.  
  57. Anders Munch        |  Department of Computer Science
  58. juul@diku.dk        |  University of Copenhagen, Denmark
  59. "Confused? The thing is to get confused at a higher level" - Jorgen Thorslund
  60.