Re: Help on disassembler/decompilers

markh@csd4.csd.uwm.edu (Mark William Hopkins @ University of Wisconsin-Milwaukee)
rewrites the following code (due to ch@dce.ie (Charles Bryant)):
typedef struct list {
struct list *next;
int item;
} list;


list *head;


insert(list *newelem)
{
list **p;
for (p = &head; *p; p = &(*p)->next)
if ( (*p)->item >= newelem->item) break;
newelem->next = *p;
*p = newelem;
}
as
typedef struct List {
struct List *Next; int Item;
} *List;


List Head;


Insert(List NewElem) {
List P;


for (P = Head; P != NULL; P = P->Next)
if (P->Item >= NewElem->Item) break;
NewElem->Next = P; P = NewElem;
}


claiming that the result is trivially translatable into Pascal, (indeed, it
is written in the Pascal subset of C), and that the two are semantically
equivalent.


Unfortunately, the two are not equivalent. In the first, the assignment
*p=newelem; can change the value of `head' (say when head==0). In
the rewritten version, no assignment to Head is possible, since it is never
mentioned on the left of an assignment, and no pointer to it is ever
developed. Of course, the code is useless without the potential side-effect
on head.


The problem is that the rewrite has decreased p's level of indirection by 1.
So p (in the rewritten version) has the same rvalue as *p (in the original),
but a different lvalue. Unfortunately, on the left side of an assignment it
is the lvalue that matters.


Mr. Bryant's whole point was that occasionally the assignment
*p = newelem; can change head. This effect is not directly
achievable in Pascal, because it is not possible to develop a pointer to data
not allocated on the heap. (Well, maybe call-by-reference is a partial
exception, but the implicit pointer there is not a first class citizen.)


Many Pascal programmers (apparently including Mr. Hopkins) consider the
semantic notions of lvalue and rvalue to be needless complication in the
description of C, since there is little need for them in describing Pascal,
which contains no lvalue-to-rvalue conversion operator (unary & in C.)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.