marmar@mtk.UUCP (Mark Martino) (05/23/89)
When is it useful to implement additional stacks? What characteristics of a programming problem suggest that multiple stacks would be a good solution? More specifically, when applying Forth to graphics, would it be useful to use imitate the stacks that PostScript uses? Would it be useful to create even more stacks for specific classes of operations?
ZMLEB@SCFVM.BITNET (Lee Brotzman) (05/24/89)
>When is it useful to implement additional stacks? What characteristics >of a programming problem suggest that multiple stacks would be a good >solution? The most common use of additional stacks that I know of is the floating point stack. All floating point numbers are maintained on a stack separate from the normal data stack. All floating point operators, such as F+ FSIN etc., take their operands from the FP stack. Having more than one stack can allow you to write code that just doesn't look like it should work. For instance, given that + adds two single-precision integers on the data stack and replaces them with the sum, and the F+ does the same, only on the floating point stack, does the following execute correctly? 1 1.0E0 2 2.0E0 + F+ The answer is yes. The 1 and 2 go to the data stack, the 1.0E0 and 2.0E0 go to the FP stack. They look like this: Data FP SP --> +-------+ +-------+ <-- FSP | 2 | | 2.0E0 | +-------+ +-------+ | 1 | | 1.0E0 | +-------+ +-------+ After executing + the value 3 is left on the data stack. After F+ 3.0E0 is left on the FP stack. It is because of this kind of intermixing of data types and operators that it is very important to know whether your floating point package uses a separate stack or not. I believe that the standard floating point word set that the ANSI committee is working on stipulates a separate stack. > >More specifically, when applying Forth to graphics, would it be useful >to use imitate the stacks that PostScript uses? Would it be useful to >create even more stacks for specific classes of operations? I'm not a graphics programmer, but I think that like everything in programming, there are tradeoffs here. Additional stacks can make programs easier to write and, in my humble opinion, easier to read (if you avoid doing something like my silly example above). But, the more stacks you have, the more stack pointers you need, and that can slow down the system. If all the stack pointers can not be kept in registers -- and even the 68000 and VAX processors have a limited number of registers that can be dedicated to the purpose -- they have to be kept in memory. That means additional memory accesses for each stack operation, i.e. slower execution. How many stacks did you have in mind? -- Lee Brotzman (FIGI-L Moderator) -- BITNET: ZMLEB@SCFVM SPAN: CHAMP::BROTZMAN -- Internet: zmleb@scfvm.gsfc.nasa.gov GEnie: L.BROTZMAN -- The government and my company don't know what I'm saying. -- Let's keep it that way. -- Isn't Cold Fusion how Eskimos are made?
dredick@bbn.com (Donald Redick) (05/24/89)
In article <442@mtk.UUCP> marmar@mtk.UUCP (Mark Martino) writes:
->When is it useful to implement additional stacks? What characteristics
->of a programming problem suggest that multiple stacks would be a good
->solution?
->
->More specifically, when applying Forth to graphics, would it be useful
->to use imitate the stacks that PostScript uses? Would it be useful to
->create even more stacks for specific classes of operations?
In the recent issue of Fig's Forth Dimensions, there is an article
discussing a 3 stack Forth implementation. I am not to sure, since I
don't have my copy around at work, what their uses are but I can follow
up on it. Also, in past issues of Forth Dimension, various author have
discussed mutiple stack usage and implementation including a string
stack and a stack of stacks.
I'll see what I can find....
-- The Druid
===============================================================================
= The Druid (dredick@bbn.com) =
= "Did you ever feel that you were a typewriter, =
= when everone else in the world was a wordprocessor" =
===============================================================================wmb@SUN.COM (Mitch Bradley) (05/25/89)
I use multiple stacks for things like floating point and a stack of open file descriptors for the input stream. The use of a memory variable for a stack pointer in these cases rarely causes any significant speed degradataion, because there is nearly always something else that is more of a bottleneck. The thing that I do worry about is error recovery. When you have multiple stacks, you should make sure that at least ABORT and perhaps also QUIT clears those other stacks. Otherwise you will have a flaky system that tends to blow up "randomly" after several ABORTs. When writing floating point code, it is wise to at least try to structure the calculation so that it doesn't matter whether or not there is a separate floating point stack. This results in code that is more portable and easier to read and maintain. It's not always possible to achieve this goal, but it's good to at least try. Mitch Bradley Bradley Forthware
dredick@bbn.com (Donald Redick) (05/25/89)
In Forth Dimensions, Vol. 10, Num. 3 the following articles are present on Multiple Stacks: A Convenient Extra Stack -- Victor H. Yngve The extra stack is used instead of the return stack for temporary storage, for input that would otherwise complicate parameter-stack operations. A Shadow Stack for Double Numbers - Darrel Johansen This "shadow stack" saves the high 16 bits of numeric entries and silently surrenders them when 32-bit arguments are required. Using a String Stack - Ron Braithwaite This paper presents an implementation based on string-manipulation principles found in MUMPS. Includes Pattern Matching. In this month's Forth Dimensions, Vol 11, #1 the following article was present: Forth needs Three More Stacks - Ayman Abu-Mostafa This article discusses an alternate to the standard Forth use of the return stack -- an auxlilary stack for loop parameters and temporary storage, a condition stack and case stack for handling conditionals withcout branching that can allow the use of conditionals outside of colon definitions. -- The Druid =============================================================================== = The Druid (dredick@bbn.com) = = "Did you ever feel that you were a typewriter, = = when everone else in the world was a wordprocessor" = ===============================================================================
toma@tekgvs.LABS.TEK.COM (Tom Almy) (05/26/89)
In article <442@mtk.UUCP> marmar@mtk.UUCP (Mark Martino) writes: >When is it useful to implement additional stacks? What characteristics >of a programming problem suggest that multiple stacks would be a good >solution? > Well, STOIC (a variant of Forth) had separate "Loop" and "Return" stacks. That way you could access values on the Return stack (which, like Forth, is commonly used as a second parameter stack) easily from within a loop structure. I have used the 8087 internal floating point stack in Forth. It's actually easier to use floating point when the values are on a separate stack since you don't have to figure out how to (for instance) swap a float (is it 32 or 64 bits?) with an integer (is it 16 or 32 bits?). I have also seen string stacks, but I find them inefficient. Tom Almy toma@tekgvs.labs.tek.com
ZMLEB@SCFVM.BITNET (Lee Brotzman) (06/01/89)
I got the following from Mark Martino, who was the original poster of some questions about using multiple stacks. Since I don't have the background to reply with any sort of confidence, I thought you'd all like to try. -- Lee Brotzman (FIGI-L Moderator) -- BITNET: ZMLEB@SCFVM SPAN: CHAMP::BROTZMAN -- Internet: zmleb@scfvm.gsfc.nasa.gov GEnie: L.BROTZMAN -- The government and my company don't know what I'm saying. -- Let's keep it that way. -- Isn't Cold Fusion how Eskimos are made? ------------------< Message Starts >-------------------- Date: Thu, 25 May 89 01:31:43 PDT From: uw-beaver!mtk!marmar@ucsd.edu (Mark Martino) Subject: Re: Multiple Stacks In-Reply-To: <8905241402.AA11788@jade.berkeley.edu> References: <sumax!thebes!mtk!marmar@BEAVER.CS.WASHINGTON.EDU> Organization: Mannesmann Tally, Kent, WA 98032 > I'm not a graphics programmer, but I think that like everything in >programming, there are tradeoffs here. Additional stacks can make programs >easier to write and, in my humble opinion, easier to read (if you avoid >doing something like my silly example above). But, the more stacks you >have, the more stack pointers you need, and that can slow down the system. >If all the stack pointers can not be kept in registers -- and even the >68000 and VAX processors have a limited number of registers that can be >dedicated to the purpose -- they have to be kept in memory. That means >additional memory accesses for each stack operation, i.e. slower execution. > How many stacks did you have in mind? > > >-- Lee Brotzman (FIGI-L Moderator) Thanks for replying. Your answer cleared up a lot of things for me. I hadn't really thought about a specific number of stacks. PostScript has four stacks. I was trying to think of a way to separate out the different types of PostScript objects instead of putting them all on the operand stack. I don't know a lot about the innards of PostScript, but I read somewhere that a PostScript operand is actually 8 bytes on the stack. Even integers take up that much. The reason for this seems to be to provide all of the necessary overhead information for the larger objects and still keep the stack on even boundaries. Not being formally trained, I don't know if a stack has to be pushed and popped by the same increment all the time or if it can somehow handle different sized objects directly. I realize that PostScript was created over a fairly long period of time by more than one person, but I'd like to create a graphic language for artists that is faster and takes less memory than PostScript. I like Forth and I like PostScript, but I want to be able to extend their compiling/binding features to speed them up. So, in short, I guess I could be talking about as many as a dozen stacks. I have lots of other questions if you can take the time to read them. Thanks for your help so far.
wmb@SUN.COM (06/01/89)
> I was trying to think of a way to separate out the > different types of PostScript objects instead of putting them all on > the operand stack. I don't know a lot about the innards of PostScript, If you separate the PostScript object stack into several "single data type" stacks, you will run into the problem that a "generic" operator like "+" can no longer easily determine which values to operate on. Solutions: a) keep a separate "type stack" which maps the single "logical stack" into several other stacks. This is undoubtedly more expensive both in space and time than having 8-byte stack entries. b) Eliminate generic operators, using either 1) A full set of mixed-type operators, 1 for each pair of types or 2) A set of type conversion operators which "promote" objects of one type to the "higher" type, so that the operator for the higher type can be used. This is what Forth does when you want to add an integer to a floating point number; you convert the integer to a float and then add with F+ In some cases, it may be possible to determine the data types at compile time, thus allowing the use of generic operators at the source code level, which compile to single-type operators. In a full PostScript environment, this is clearly not always possible, because name binding is done very very late in PostScript. The overhead for 8-byte stack entries in PostScript is no big deal. Run-time switching of generic operators is worse. > I don't know if a stack has to be pushed and popped by > the same increment all the time or if it can somehow handle different > sized objects directly. It is certainly possible to deal with different-sized objects on the same stack. It is probably not worthwhile though. > but I'd like to create a graphic language for > artists that is faster and takes less memory than PostScript. My gut feel is that the PostScript language interpreter and the stacks aren't prohibitively large. The large number of wonderful graphics operators is what takes up the space. James Gosling, the implementor of the NeWS window system (which was probably the first non-Adobe implementation of PostScript), told me that he spent about a week on the PostScript language interpreter and about a year on the graphics.