Path: utzoo!attcan!uunet!midway!ncar!zaphod.mps.ohio-state.edu!usc!snorkelwacker!mintaka!spdcc!esegue!compilers-sender
From: td@alice.UUCP (Tom Duff)
Newsgroups: comp.compilers
Subject: Re: Help on disassembler/decompilers
Summary: bug introduced
Keywords: disassemble, translate
Message-ID: <11368@alice.UUCP>
Date: 21 Sep 90 13:30:28 GMT
References: <HOW.90Sep5173755@sundrops.ucdavis.edu> <6839.26ea3b0e@vax1.tcd.ie> <6412@uwm.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: td@alice.UUCP (Tom Duff)
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 61
Approved: compilers@esegue.segue.boston.ma.us

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.)
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.