Re: Yet Another Spinoza Challenge

Richard Heathfield <rjh@xxxxxxxxxxxxxxx> writes:
In <lnr5ufvjrn.fsf@xxxxxxxxxxxxxxx>, Keith Thompson wrote:
Richard Heathfield <rjh@xxxxxxxxxxxxxxx> writes:
<snip>

Stack-like semantics? Sure. But you don't *have* to use a stack.
It's obviously a very, very sensible choice, but it is not the only
choice. Any searchable dynamic data structure will do. I suspect
the reason some people are defending stacks so valiantly is simply
that that's the only way they've ever seen it done.

In what sense are you using the word "stack" in the above paragraph?

The usual sense - a chain of data structures, each (other than the
last, obviously) linked to the next in the chain, either via a
pointer or by virtue of being adjacent in memory, where new items can
be added only at the top and where only the top item can be removed.

If you allow chaining via a pointer or by being adjacent in memory,
two very different mechanisms, it seems inconsistent not to allow
chaining by other means, such as by information stored in some
outside data structure. (I'm using the word "allow" in the sense
that anything not meeting the definition isn't a stack, not that
it's forbidden).

Wikipedia's definition:

<http://en.wikipedia.org/wiki/Stack_(data_structure)>

seems reasonable to me:

In computer science, a stack is a last in, first out(LIFO)
abstract data type and data structure. A stack can have any
abstract data type as an element, but is characterized by only two
fundamental operations, the push and the pop. The push operation
adds to the top of the list, hiding any items already on the
stack, or initializing the stack if it is empty. The pop operation
removes an item from the top of the list, and returns this value
to the caller. A pop either reveals previously concealed items, or
results in an empty list.

A stack is a restricted data structure, because only a small
number of operations are performed on it. The nature of the pop
and push operations also means that stack elements have a natural
order. Elements are removed from the stack in the reverse order to
the order of their addition: therefore, the lower elements are
typically those that have been in the list the longest.

<snip>

I assert that anything with "stack-like semantics" *is* a stack in
the general LIFO sense of the word.

Then we have a terminology clash, so I think we're done here.

--
Keith Thompson (The_Other_Keith) kst-u@xxxxxxx <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
.

Relevant Pages

  • Re: Is there a clean, simple way to do this stack change?
    ... doing that is for setting up a special data structure. ... and second cleanest ways I can see to do this use return stack ... Once everything is ready on the stack, ... word wraps it all up by moving everything above the left marker into ...
    (comp.lang.forth)
  • Re: CFileDialog: "My Computer" not shows files and dirs
    ... CFileDialog, the dialog and the programm crashes! ... invalid instruction exception caused by a stack clobber, ... the data structure is actually longer and a memory overwrite occurs. ... You can install ...
    (microsoft.public.vc.mfc)
  • Controlled types and exception safety
    ... I can classify the stack's operations by assigning them any of the above four levels, so that I know what can be expected when an exception is thrown for any reason (like inability to allocate more memory, or alike). ... For example, if the Push method of the stack gives me the strong guarantee, then I *know* that by calling this method either the new element will be appended to the stack, or the stack will remain unchanged, so that even if the exception is thrown, I don't have to worry about the stack's internal consistency. ... Since stack can be a dynamic data structure, assigning one stack object to another may involve destroying one existing data structure *and* creating a new one in its place. ...
    (comp.lang.ada)
  • Re: using MISC (post 1987 Forth hardware) opcodes
    ... still need to travel onto a stack every time you branch within the tree. ... Or without altering the data structure and using a threaded tree. ... restricted environment is also easier to program. ...
    (comp.lang.forth)
  • Re: Encrypt/ Decrypt in NdisIM with Ethernet
    ... That again could be because stack gets corrupted. ... write to an array or initialize a data structure? ... when I break the debug to enter some ... >>> A fatal system error has occurred. ...
    (microsoft.public.development.device.drivers)