Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!henry
From: henry@utzoo.UUCP (Henry Spencer)
Newsgroups: comp.lang.c
Subject: interesting type problem
Message-ID: <8626@utzoo.UUCP>
Date: Sat, 19-Sep-87 22:30:21 EDT
Article-I.D.: utzoo.8626
Posted: Sat Sep 19 22:30:21 1987
Date-Received: Sat, 19-Sep-87 22:30:21 EDT
Organization: U of Toronto Zoology
Lines: 28

Consider the following problem.  We are trying to write a table-driven
scanner for a garden-variety programming language.  We decide on a fairly
quick approach:  we use the current character to index into a table,
which contains pointers to the appropriate next table for each character.
When we hit a NULL pointer, we're done.  We will have some cyclic structures
for tokens like identifiers that can be of unlimited length.

Question:  what is the type of one of those pointers?

It can't be done in strictly portable C using "efficient" pointers (where
character pointers and "void *" are "inefficient" because they require
extra-bulky and extra-slow representations on some machines).  The cyclic
structures are what kill it; somewhere along the line, one has to lie about
the types to avoid infinite regress.  And the only portable way to do such
lying is to use "void *".

The irksome aspect of it is that on every machine I can think of, including
several that do have an efficient/inefficient distinction in pointer
representations, the problem could be solved in assembler without using any
inefficient pointers!  "Pointer to pointer to X" is generally an efficient
pointer with a representation independent of X, and this algorithm never
uses any other flavor of pointer.

I'm not advocating a change to C to fix this.  I was just a bit bemused by
the discovery of the situation, and thought others might be interested.
-- 
"There's a lot more to do in space   |  Henry Spencer @ U of Toronto Zoology
than sending people to Mars." --Bova | {allegra,ihnp4,decvax,utai}!utzoo!henry