From: chopps@ro-chp.UUCP (Chris Hopps)
Newsgroups: comp.lang.c,comp.programming
Subject: Re: A LITTLE BRAINTEASER...
Date: Sun, 16 Aug 1992 09:00:18 GMT
Keywords: Junk
Organization: Not an Organization
X-Newsreader: Arn V1.00 beta rel2

In article <9222810.19441@mulga.cs.mu.OZ.AU>, Fergus James HENDERSON writes:

> halderen@fwi.uva.nl (Berry van Halderen (I88)) writes:
>
> >The solutions so far posted were or: totally incorrect, did use datastructures
> >(translating pascal ain't no good coz strings are datastructures)
>
> The problem is not that the translation may introduce strings; there were
> no strings in the Pascal program posted. The problem is that the translation
> will almost certainly introduce pointers and structures.

What are you trying to do here?  Prove that pascal is a better language to
apply resrictions to and write bad code (no data structures)?  If so, we
need no rwars here, please take it somewhere else.

> [... Program that uses varargs to access stack ...]
>
> >It works. It implicitly builds a linked list into the stack. There are
> >no pointers (well, ap is a pointer in most implementations) structs or
> >whatever, and no calculation of stack addresses is done (which is cleaner).
>
> Well, you can't be *sure* that there are no structs or dynamic allocation,
> since you don't know how varargs is implemented. Clever idea, though.
>
> Another way of solving the problem is to create a temporary file using the
> old unbuffered i/o library. (You only need ints for the file-handles: no data
> structures required! No structs, no pointer variables, no heap allocation, no
> implicit linked lists, no hacking around the stack!). Just goes to show that
> you've got to specify exactly what you mean when you say "no heap allocation
> allowed" :-)

This is getting ridiculous.  First you tell him that his program isn't good
enough because it may implicitly use structures (which are not apparent in the
program.)  And then your own solution is to use a file library that uses only
ints to represent files.  Whats to say that the implementation of the file
library doesn't use data structures.  Windows(yuck) programs use ints all over
for handles, handles that represent data structures.

I guess I don't understand what it is you exactly want.  Should the program
be portable?  What _is_ a data structure to you?  To me recursing and saving
values on the stack is a data structure, albeit an ugly and not very usefull
one in this case, it still represents a logical structuring of data.

Furthermore, I mainly write my "just having fun" code on my amiga, which unlike
unix, does not have an unlimited stack (yes the compilers can generate stack
growing code, but...)  and so I can tell you that if you want a portable
program that does no allocation, forget the stack only thing.

I was able to produce a program that used only a single data structure
and used the stack for allocating it.  The data structure was defined inside
the recursing function, so I think that it should satisfy the requirement.
(It is basically just a way to portably reference the previous functions
stack frame.)  I also though that the varargs version posted earlier was
even closer to satisfying your undefined demands.  (that doesn't make sense
but maybe it explains the problem.)

> --
> Fergus Henderson             fjh@munta.cs.mu.OZ.AU
> This .signature VIRUS is a self-referential statement that is true - but
> you will only be able to consistently believe it if you copy it to your own
> .signature file!

Ansi (I hope :^) ) code follows:
---------------
#include <stdio.h>

#ifndef EOL
#define EOL '\n'
#endif

int print_a_line( struct PrevChar *, struct PrevChar * );
int reverse_lines( void );

int main( int argc, char ** argv )
{
	return( reverse_lines() );
}

int reverse_lines( void )
{
	print_a_line( NULL, NULL );
	return( 0 );
}

int print_a_line( struct PrevChar *p, struct PrevChar *start )
{
	struct PrevChar {
		struct PrevChar *next;
		int    ch;
	} this = { NULL, 0 };

	int ch = getchar();

	if( ch != EOL && ch != EOF ) {
		if( p ) {
			/* this is a recurse. */
			p->next = &this;
			this.ch = ch;
			return(print_a_line(&this,start));
		} else {
			/* this is first invocation for a line */
			this.ch = ch;
			return(print_a_line(&this,&this));
		}
	} else {

		if( ch == EOL )
			reverse_lines();

		if( p ) {
			/* this is a recurse. */
			if( ch != EOF ) {
				p->next = &this;
				this.ch = ch;
			}
		} else {
			/* this is first invocation for a line */
			if( ch != EOF ) {
				start = &this;
				this.ch = ch;
			}
		}
		p = start;
		while( p ) {
			putchar( p->ch );
			p = p->next;
		}
		return( 0 );
	}
}

------------------------
The Royal Oak Chophouse >> Chris Hopps
Royal Oak, Michigan     >> sycom.mi.org!ro-chp!chopps