jlg@lanl.gov (Jim Giles) (10/20/90)
> QUESTION 5: Do you realize the difference between arguing *for* pointers > and arguing *against* recursive data structures? Yes or no? Well? The distinction is quite clear to me. But, I don't understand the point of this question. Are you claiming _not_ to have argued *for* pointers? You have. Or, are you claiming _not_ to have argued *against* recursive data structures? You have. You have consistently argued _both_ positions. As and example of your campaign *against* recursive data structures, here is your next question: > QUESTION 6: How do you express a bounded-memory reverse-direction stack > or tree traversal in Nemesis? I don't believe you can. Recursive type Stack Some_type :: value !value component of node Stack :: next !link component of node End type Stack Aliased stack :: a, b !Declare two Stack variables which !are allowed to be aliased (but only !to each other) [... some code to define 'a' as a stack to be reversed ...] !!! STACK REVERSAL CODE NEXT 4 LINES !!! b=nil !set-up for loop while (a ~= nil) (a, b, a.next) <- (a.next,a,b) end while Variable 'b' now holds the reverse of the original 'a'. The variable 'a' is now nil (and the original ordering can be accessed only by traversing the stack again and reversing it). Note that the value components of the stack aren't even referenced. They aren't moved or examined in any way - the stack was reversed by "flipping links." The '<-' is the "shallow copy" assignment operator that I've mentioned numerous times before (which is only allowed between objects which appear in the same "aliased" declaration or components thereof). "Shallow copy" assignment copies the _reference_ part of the right hand side - not the _value_ part (the right hand side must therefore be an l-value). The concurrent assignment prevents me from needing an auxilliary variable to hold temporaries during the swap of links. The above loop (with the preset of 'b') is the _entire_ stack reversal code. The semantics are _identical_ to the way (say) Pascal pointers would do the same operation. The syntax is cleaner, easier to read, and more explicit (and so, easier to debug). Since aliasing is actually present, there are probably no performance benefits to using recursive data structures - on the other hand, since the semantics are _identical_, the performance should be the same as a pointer version. As interesting as all this is, I usually prefer to implement stacks as sequences or arrays. The contiguous storage of these makes accessing arbitrary elements of the stack a simple matter (no traversing - can binary search it, etc.). In this case, reversing the stack can be accomodated simply by modifying the push and pop routines to use a direction flag to determine which is the "active" end of the stack. Now, stack reversal would be just a boolean assignment to the direction flag. End of chapter 3 J. Giles