kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (09/19/90)
In article <1990Sep18.103653.24032@dce.ie> ch@dce.ie (Charles Bryant) writes: >That's funny, I can't see any bug in the original. I can see a bug in the >Pascal one though: when the list is empty new elements can't be inserted >because 'head' is never changed. The ``bug'' was the lack of initialization (_not_ really a bug in C but it _is_ so in other languages, and therefore in general). It was a rotten trick anyway. If you initialize ``head'' to 0 and allocate ``mem'' cells starting at 0 the Pascal program's ok. As for saying ``well ok -- _try_ to perform the translation using Pascal pointers''. This is the same as asking ``translate this program, that uses language feature F, into one that _doesn't have_ feature F''. A non sequitur? As I said in the original post, matters of _efficiency_ are quite distinct from the original statement that "X->Y is easy and Y->X is a hard translation". >From the point of view of formal language thy _all_ translation is _very hard_ (i.e. ``impossible'' and therefore equally ``easy''). Saying that a Pascal program that implements lists using integers and arrays is either _time_ inefficient and/or _space_ inefficient is beside the (original) point. In any case, efficiency is (usually) a matter of a particular underlying architecture (WELL off the track of the original question). On some systems using an array is actually preferred to manipulating pointers; the former is under more-or-less control, whereas the latter is subject to the vagueries of the C memory management. It may be possible to maintain locality-of-reference with integers and arrays and ``cache misses'' can kill dominate program performance considerations. Also, on VM systems allocating ``huge arrays'' does not present such an overhead as you seem to think. In fact, the C malloc routine on _some_ systems essentially declares a _huge_ static array to which it passes out pointers; the VM mechanism does the rest. -Kym Horsell -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.