Which is exactly why a dequeue or vector is overkill. You never need to index the stack. You might need to look into the stack for outer scopes, but this is just done by following the pointers.Originally Posted by King Mir
The machine stack is also a linked list. It happens to be allocated contiguously down the stack memory. But unless you're omitting frame pointers, the frames on the stack are literally a linked list, and you can walk them exactly that way.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
The program stack is a continuous memory array, which is a boon, because it doesn't have to allocate memory for each function call. It has frame pointers, because it has variable size frames. But that's not needed for storing the same kind of object.
Both deques and lists have constant time insertion and deletion for the last element, but the per element memory overhead of a linked list is more. If a deque doesn't store a pointer to the last element, which it likely does, it's because the extra derefeence + index is nothing to fuss over. With a list, every time an element is added, the system has to reserve memory for it, which takes more than a few dereferences. A deque will preallocate a large chunk, and only increment the number of elements, untill that chunk runs out. Then it will add another chunk, but unlike a vector it won't copy the old elements into the new chunk. This also helps with chacheing and especially paging (though that's less of an issue these days), because recently pushed and popped elements in a row will be adjacent in memory. Of course that last benefit applies to some cases more than others; in this case it would benefit the parse stack, but probably not the function stack, especially because a map is itself a complex object.
Deques are the way to go for arbitrary size stacks and queues. For small sizes a vector works better for a stack, and a circular buffer works better for a queue.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
What happens if an exception is thrown? The pop function is never called.
But mana isn't doing that. Hence, it is not exception safe.
It is possible to do as you say, but that is a hack and a mess, and is no different from Java.
You have to somehow determine where the exception occurred and fix up that mess before re-throwing an exception.
It is completely against the idea of RAII.
I'd say that in such cases, an exception should be thrown with enough information to actually log the error (example, state of the stack).
Not cleaning up after an exception is irresponsible and leaves a mess. It also leads to bugs later on if you somehow need to restart the operation that failed.
>What happens if an exception is thrown? The pop function is never called.
It isn't meant to be called there.
Depending on the exception, the program would offer the user to correct the input (Common Lisp does it...but it'd take some time for me to implement all that)
And ..if the user just decides to forget the old input and start a new one.. all the necessary popping will be done by the catch.
A dangerous approach.
Ideally, each function should clean up after itself. Otherwise it will lead to bugs.
You didn't even clear up for me where the exception problem is.
What makes you say that. try catch is the way to deal with exceptions, apart from just not catching them at all.It is possible to do as you say, but that is a hack and a mess, and is no different from Java.
This is what confuses me even more. How many different exception errors do you even see? The only error I can see is bad_alloc, and the only one this function should maybe handle. And I'm not even sure about that. I thought that when exceptions where thrown, things go out of scope normally. It's only when you have to manually release memory that it's a problem.You have to somehow determine where the exception occurred and fix up that mess before re-throwing an exception.
How do you figure? malloc and free can be used in accordance with the RAII idiom as can push and pop, or constructors and destructors.It is completely against the idea of RAII.
If it isn't obvious, it's the manual popping. Any manual cleaning up or "undo action" is an exception problem because those statements will be skipped when an exception is thrown.
Consider this:What makes you say that. try catch is the way to deal with exceptions, apart from just not catching them at all.
If an exception is thrown, p is leaked. In Java, you have to declare p outside the try block and check if p isn't null, and if so, release it (that is assuming p is some resource, like say, a database).Code:try { int * p = new int; function_that_can_throw(p); std::cout << *p << std::endl; } catch (const std::exception& ex) { std::cout << "Oops, something went wrong!\n"; }
Now scale that up. Add more statements and more paths and you will yourself having to add a lot of code in every function to properly clean up and re-throw.
Clearly, this is not desirable and it costs its fair share of cpu time.
Ideally, we'd like for every function to just clean up after itself so we don't have to do it manually.
But if you push something that requires a manual pop, that pop never gets done, does it? Hence the problem.This is what confuses me even more. How many different exception errors do you even see? The only error I can see is bad_alloc, and the only one this function should maybe handle. And I'm not even sure about that. I thought that when exceptions where thrown, things go out of scope normally. It's only when you have to manually release memory that it's a problem.
Yes, if you do it properly. Clean up after yourself in the destructor and you've got RAII. Do it manually and you don't have the RAII idom.How do you figure? malloc and free can be used in accordance with the RAII idiom as can push and pop, or constructors and destructors.
Except it doesn't require a manual pop. Maybe I'm just too stupid for the conversation, but the whole scope object would be destroyed eventually if you never caught the exception. If you did catch the exception somewhere, I don't think that var_scope is out of scope -- in fact it's declared elsewhere and not local to the function we are talking about. That means you could pop when you catch. And it doesn't have the problem you illustrated with your example.But if you push something that requires a manual pop, that pop never gets done, does it? Hence the problem.
And in C++ you don't!In Java, you have to declare p outside the try block and check if p isn't null,
Safe.Code:int* p = nullptr; try { p = new int; function_that_can_throw(p); std::cout << *p << std::endl; } catch (const std::exception& ex) { delete p; std::cout << "Oops, something went wrong!\n"; }
But mana doesn't catch and rethrow. It is one possible solution.
A better solution is to force a pop when the object goes out of scope.
I would write it as:And in C++ you don't!
Code:try { std::unique_ptr<int> p = new int; function_that_can_throw(p); std::cout << *p << std::endl; } catch (const std::exception& ex) { std::cout << "Oops, something went wrong!\n"; }
That is 'almost' what I was aiming to do... (Instead of deleting, I'd be popping values from a global stack).
Good for you. But in relation to your earlier post however, the key difference is that delete on null is safe. It isn't like Java in that sense. If I went and used the STL I wonder if I could have still made that point at all, or if you'd've replied with another problem... like me straying from the example that you wrote.
The point was that if that was Java, and p was a database, then you'd have to do
if (p) p.Release();
For that matter, how do we even know that the state of p is well-defined at the catch block? The exception can happen anywhere.
So we have to poll and figure out WTH happened so we can undo it. That's just a pain.
And we have to do it in every local function.
Again the only exception I see possible with scope is bad_alloc... and it's a global object so in general it's a pain and things will happen in every local function (emphasis yours)... Is it still inappropriate to catch that error associated with the stack of an interpreter in something important, like main()?So we have to poll and figure out WTH happened so we can undo it. That's just a pain.
And we have to do it in every local function.
I don't really want to talk about this anymore. But try and keep in mind the actual job at hand. It's like you want to lecture me on the general case.
If you don't want to talk about it, that's fine. But let me just clear up that.
It's not about catching it in main--obviously you will want to--but about what happens in the functions as the stack unwinds.
Will the object end up in some inconsistent state because you fail to pop the scopes? If so, how do you deal with that?
I'd say that's fine, especially if you might pop different amounts of data during error recovery.
Though you should probably have (at least) two stacks, one for tokens, and one for function call data. I get the impression that you don't.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
