Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!world!esegue!compilers-sender
From: kym@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.compilers
Subject: Re: Help on disassembler/decompilers
Keywords: assembler, debug, translator
Message-ID: <4028@bingvaxu.cc.binghamton.edu>
Date: 15 Sep 90 16:49:08 GMT
References: <HOW.90Sep5173755@sundrops.ucdavis.edu> <6839.26ea3b0e@vax1.tcd.ie> <3972@bingvaxu.cc.binghamton.edu> <1990Sep14.181616.26890@dce.ie>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: kym@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell)
Organization: SUNY Binghamton, NY
Lines: 102
Approved: compilers@esegue.segue.boston.ma.us


In article <1990Sep14.181616.26890@dce.ie> ch@dce.ie (Charles Bryant) writes:
>Well how would you translate this C function into Pascal.
>
>	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;
>	}

I'm not sure at what level to aim this so I'll play it straight.

I think we can try at least:

	type 
		list = 0..maxmem;
		listinfo = record next: list; item: integer; end
			{listinfo};
	var
		mem: array[0..maxmem] of listinfo;
		head: list;

	procedure insert(newelem: list);
	var	p: list; break: boolean;
	begin
		p := head;
		break := false;
		while (p<>0) and not break do
		if mem[p].item>=mem[newelem].item then break:=true
		else p := mem[p].next;
		mem[newelem].next = p;
		mem[p].next = newelem;
	end {insert};

It even duplicates the same bug as the original code! (:-)

Complaints about _efficiency_ can be countered by resorting to arguments re
code optimization (which has come a long way since even Pascal was designed)
and various tricks that architects get up to (i.e. since _all addressing_ on
a given machine might be register-relative the indexing in my Pascal code
will not actually cost anything cf the C code). In any case efficiency issues
were not (originally) in question.

We might also translate the code to Fortran as follows:

	subroutine insert(newelem)
	common mem(0:maxmem)
	integer list
	integer p
	p = head
10	if(p.eq.0) goto 20
	if(mem(p+ITEMOFFSET)>=mem(newelem+ITEMOFFSET)) goto 20
	p = mem(p+NEXTOFFSET)
	goto 10
20	mem(newelem+NEXTOFFSET) = p
	mem(p+NEXTOFFSET) = newelem
	return
	end

Again, same bug...

You can perform any syntactic sugar to get this into (whatever)
version of Basic you like.

There may be some transcription errors here & there above, but
I don't think anything is essentially _wrong_ with the code,
so don't get too picky.

The good thing about theoretical results from formal language theory
(and thank you Manfred von Thun) is that we _can_ say (all too few) general 
things about programming and be sure we're right.

Of course none of this has _proved_ that things are ``equally hard''
as indicated in my original post -- that _would_ be much harder.

-Kym Horsell

[I suspect that the original author expected the Pascal version to use Pascal
pointers.  My Pascal is rusty enough that I don't immediately see what the
problem is, other than perhaps the static list head.
My experience is that translating from one language to another is 90% easy,
but the 10% can be incredibly hard.  In about 1970, I took a very vanilla
Fortran calendar printing program and ran it though IBM's Fortran to PL/I.
Although most of the Fortran was recognizable more or less statement by
statement, some of it, particularly the I/O, expanded by orders of magnitude.
Most of the blow-up handled cases that I knew wouldn't happen (most notably
reading into a literal in Format statement) but it was hard for the
translator to know that.  This is a long way from decompiling assembler into
some language. -John]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.