Stack mechanics to achieve the effect of local variables as in C
Standish P
is cl.forth.
Here is a quote from Forth Inc HDBK 3rd ed., p61.
All Forth defining words are immediately followed by the name of the
object being defined. All define permanent (static) global objects.
These are independent definitions, just like colon definitions. Forths
data stack fills the role used by local variables in other languages.
ANS
Forth has a limited provision for local variables, but they are rarely
used and and are NOT recommended for beginners because their use tends
to inhibit the development of good stack management skills.
So how does Forth, postscript or even assembly achieve the effect of
named or unnamed but referrable "temporary" , "automatic" ie
temporarily allocated variables referrable multiple times without
having to copy and dup them multiple times and avoid unreadablility.
What are the collected patterns of such "stack management skills" ? Is
there any documentation or animations or applets to show this ?
Alexei A. Frounze
I'm very vaguely familiar with Forth and its intricacies of stack
manipulation, so, I'll speak from assembly and C stand point instead.
Most C compilers generate code for CPUs that have a stack and support
operations like PUSH something on the stack, POP something from the
stack and read/write something located on the stack in a way very
similar to shown in the following example. Many assembly subroutines
are implemented in a very similar way too.
-------8<-------
// file stck.c
// compile with: gcc -c stck.c -O0 -S -o stck.s
int calculate (int a, int b, int c, int d, int e)
{
int tmp1 = c - d + e;
int tmp2 = a + b;
int tmp3 = tmp1 * tmp2;
return tmp3;
}
-------8<-------
Let's compile this little function into assembly with gcc and specify
zero optimization to demonstrate how things work on i80386+:
-------8<-------
; file stck.s
; comments added manually
.file "stck.c"
.section .text
.globl _calculate
_calculate:
; on the entry to this function the stack contains (from higher
addresses to lower addresses):
; e
; d
; c
; b
; a
; return address
pushl %ebp
movl %esp, %ebp ; ebp = esp and points to ebp just saved on
the stack
subl $12, %esp ; allocate 12 bytes on the stack
; you can now use ebp to access parameters and local variables:
; ebp+24 = address of e
; ebp+20 = address of d
; ebp+16 = address of c
; ebp+12 = address of b
; ebp+8 = address of a
; ebp+4 = address of the return address
; ebp = address of the old ebp value saved on the stack
; ebp-4 = address of tmp1
; ebp-8 = address of tmp2
; ebp-12 = address of tmp3
movl 20(%ebp), %edx ; edx = memory[ebp+20] (AKA d)
movl 16(%ebp), %eax ; eax = memory[ebp+16] (AKA c)
subl %edx, %eax ; eax = eax - edx = c - d
addl 24(%ebp), %eax ; eax = eax + memory[ebp+24] (AKA e) =
c - d + e
movl %eax, -4(%ebp) ; memory[ebp-4] (AKA tmp1) = eax = c -
d + e
movl 12(%ebp), %eax ; eax = memory[ebp+12] (AKA b) = b
addl 8(%ebp), %eax ; eax = eax + memory[ebp+8] (AKA a) = a
+ b
movl %eax, -8(%ebp) ; memory[ebp-8] (AKA tmp2) = eax = a +
b
movl -4(%ebp), %eax ; eax = memory[ebp-4] (AKA tmp1) = c -
d + e
imull -8(%ebp), %eax ; (edx:)eax = eax * memory[ebp-8] (AKA
tmp2) = (c - d + e) * (a + b)
movl %eax, -12(%ebp) ; memory[ebp-12] (AKA tmp3) = eax = (c
- d + e) * (a + b)
movl -12(%ebp), %eax ; eax = memory[ebp-12] (AKA tmp3) = (c
- d + e) * (a + b)
leave ; equivalent to "mov esp, epb" followed by "pop ebp";
reclaim stack space used by the local variables and restore ebp
ret
.ident "GCC: (GNU) 3.3.4"
-------8<-------
So, here the subroutine parameters and local variables are all at very
well known locations relative to the stack pointer (esp) and frame
pointer (that is, helper pointer, ebp) values. Inside the subroutine
you can access them directly as many times as necessary and wherever
necessary. Even if something gets additionally stored on the stack in
this subroutine and causes the stack pointer (esp) to change, these
parameters and local variables are still accessible through the same
ebp register at the same offset, e.g. a is at ebp+8 and tmp3 is at
ebp-12 no matter what (provided, of course, ebp remains intact).
I don't know what restrictions Forth imposes on stack operations, but
even in the C world one has to use the stack with caution, because the
stack isn't unbounded and therefore prone to overflows. Overflows are
typically caused by allocation of large arrays on the stack and
recursion.
Now, if calculate() needed to pass any of its parameters or local
variables to another subroutine, it would have to create their copies
on the stack and have them in a certain order there, just like a, b,
c, d and e appeared on calculate()'s stack as parameters, first to
last.
Does this clarify things sufficiently?
Alex
Doug Hoffman
Here some Forth solutions of the above.
calculate1 and calculate2 use only standard ANS Forth words.
calculate1 only uses stack manipulation and uses stack comments on
each line to illustrate what is going on. Not all Forth programmers
would use/need comments like this.
calculate2 uses local variables.
calculate3 uses an available extension to ANS Forth.
Note the ease of testing each definition.
-Doug
-------8<-------
: calculate1 ( a b c d e -- tmp3 )
swap \ a b c e d
- \ a b c e-d
+ \ a b c+e-d or a b tmp1
rot \ b tmp1 a
rot \ tmp1 a b
+ \ tmp1 tmp2
* ;
1 2 3 4 5 calculate1 . 12 ok
: calculate2 { a b c d e -- tmp3 }
c d - e +
a b +
* ;
1 2 3 4 5 calculate2 . 12 ok
: calculate3 { a b c d e | tmp1 tmp2 tmp3 -- tmp3 }
i' tmp1 = c - d + e '
i' tmp2 = a + b '
i' tmp3 = tmp1 * tmp2 '
tmp3 ;
1 2 3 4 5 calculate3 . 12 ok
-------8<-------
Rod Pemberton
news:0cfdd7f2-72b2-4b5b...@l6g2000yqb.googlegroups.com...
> This is being xposted to cl.postscript and al.asm, but my main group
> is cl.forth.
>
2 out 3...
> Here is a quote from Forth Inc HDBK 3rd ed., p61.
>
> [snip quote]
>
> So how does Forth, postscript or even assembly achieve the effect of
> named or unnamed but referrable "temporary" , "automatic" ie
> temporarily allocated variables referrable multiple times without
> having to copy and dup them multiple times and avoid unreadablility.
>
Assembly
has no named variables
data in memory is accessed via an address
data in a register is accessed via a register name encoded into the
instruction
data on the stack is access via push or pop instruction, or via memory
address
it's up to the programmer to keep track of data, it's type, and it's
location
arithmetic manipulations can be performed against the stack, memory, or
registers
C
has named variables
compiler may move variable's data between memory, register, or stack
compiler emits code to access the variable wherever it is at that point in
the code
a variable's data is unaddressable while in a register
the compiler shouldn't move data into register if variable's address is
required
arithmetic operations are performed against the named variable, the
compiler will emit correct assembly code for wherever the variable is
Forth
has named variables
a variable's data is stored into memory within the compiled "word" when
the word is compiled
when a named variable is "executed", it's address is stored onto the data
stack from which data can be retrieved or stored
arithmetic manipulations are performed on the data stack with stack based
operations
> What are the collected patterns of such "stack management skills" ?
>
Uh, ...
Assembly, it's up to the programmer... Good luck.
For FORTH, to manipulate the data stack, the programmer needs a handful of
stack operations, at a minimum: swap, dup, drop, rot, over. These
manipulate the top few elements of the stack. Most other Forth data stack
manipulating words can be built from those. The x86 microprocessor has no
convenient method to do stack shifts, e.g., Forth's rot, over, or roll
words. These move multiple elements up or down the stack while leaving part
of the stack where it is. I.e., they're "expensive" and should be avoided.
Push/pop operations on x86 are easy to implement: dup, drop. Swap can be
expensive or not depending on the implementation, e.g., top-of-stack etc. in
register. To access the return stack: r>, >r, r@ etc. are also needed.
For C, the C compiler keeps track of everything. The programmer doesn't
need to have any "stack management skills". C compilers put almost
everything onto the stack, at first. Objects that are too large or must be
referenced via a pointer are left in memory. If the data has not been
loaded into a register or isn't so large it must be in memory, then it'll
typically be moved to the stack. If the data is not on the top of the
stack, i.e., accessable via a pop, it will access the stack directly via a
memory read. The top-of-stack is usually pointer to the start of a "stack
frame" for the current procedure which requires an addition of an offset to
get to the needed data. Various algorithms have been developed to determine
the optimal placing of data for compilers.
E.g., start with register allocation:
http://en.wikipedia.org/wiki/Register_allocation
Call stack, e.g., used by C, Fortran, Pascal, etc., but not Forth:
http://en.wikipedia.org/wiki/Call_stack
Forth is a stack machine, i.e., 0-operand instruction set using threaded
code.
Intro to instruction operands
http://en.wikipedia.org/wiki/Model_of_computation
Number of instruction operands for stack machine, register machine,
CISC/RISC machine, etc.
http://en.wikipedia.org/wiki/Instruction_set#Number_of_operands
Threaded Code
http://en.wikipedia.org/wiki/Threaded_code
HTH,
Rod Pemberton
Standish P
by starting with a concrete example, Doug Hoffman and Rod Pemberton
for extensive details. The part on
> What are the collected patterns of such "stack management skills" ? Is
> there any documentation or animations or applets to show this ?
has more scope for replies from anyone else who wishes to contribute
and make it enjoyable and deeper learning for all of us.
I want to add some quote from Koopman so you can add material which is
clearer and detailed than his because his has a lot to be desired :
[Begin Quote]
WHY ARE STACKS USED IN COMPUTERS?
Both hardware and software stacks have been used to support four major
computing requirements:
1/ expression evaluation. [1.4.1 Expression evaluation stack]
2/ subroutine return address storage. [1.4.2 The return address
stack]
3/ dynamically allocated local variable storage, [1.4.3 The local
variable stack] and
4/ subroutine parameter passing. [1.4.4 The parameter stack]
[and C/Pascal combine some or all of them into [1.4.5 Combination
stacks], one for each routine. What is a frame pointer register and
how is it used to store local variables in an area of program
memory? ]
[End Quote]
He has more than enough details on 1/ which is much simpler as
compared to other stack-operations, so we skip it. The details on all
other stack-operations is terribly insufficient (although I credit him
with giving full names to the stacks .. very good for newbies), the
sections are indicated and the link to book is cited for convenience:
http://www.ece.cmu.edu/~koopman/stack_computers/sec1_4.html#142
He brings in requirement of reentrancy which is necessary for
recursion and also in its own right possibly for multitasking. After
defining reentrancy as "the possibility of multiple uses of the same
code by different threads of control" and emphasizing the importance
of "the management of local variables." he devotes no more attention
to the details of its implementation.
However, lets take a look at the stack mechanics for subroutine call.
Forth has what is called an inner interpreter. The general idea of
subroutine call is that parameters are placed on "the parameter stack"
according to the expectation of the function/subr and indicated by its
"interface" denoted in Forth style as
( vars expected on top of "the parameter stack" before call -- results
left on top of "the parameter stack" after call )
Before changing the IP (the instruction pointer) to the subroutine
code, the return address (to the code after the subroutine call) is
placed on the "Return Address Stack"
The exact details and examples are missing for the mechanics and usage
of each of the three remaining stacks, and finally there must be a
whole set of considerations for architecting the combination stacks
which he skips completely and presents an opportunity for anyone to
add more material from a generic perspective and the particular
perspective of forth/assembly/postscript, explaining their terms to
readers not familiar with all of them.
Alex McDonald
Standard Forth only requires two stacks; a "parameter"/"evaluation"
stack, and a return stack. Forget locals and where they live until
you've got to grips with those two stacks.
Only the data stack is used directly with zero operand operations. The
return stack is only used to push and pop entries from the data stack
-- there are no operations that work on the return stack -- and for
return addresses. Named variables live elsewhere in a data area.
All this is covered in entry level texts available on the internet.
Try the late Julian Noble's text http://galileo.phys.virginia.edu/classes/551.jvn.fall01/primer.htm.
You might want to pick up a copy of the opensource Win32Forth from
http://sourceforge.net/projects/win32forth/ and run the worked
examples.
Learning and working with Forth will help remove some of the
conceptual problems you are experiencing; you're attempting to run
before you can walk.
Rod Pemberton
> Many thanks to Alexei A Frounze for setting the course of the replies
> by starting with a concrete example, Doug Hoffman and Rod Pemberton
> for extensive details. The part on
>
> > What are the collected patterns of such "stack management skills" ? Is
> > there any documentation or animations or applets to show this ?
>
> has more scope for replies from anyone else who wishes to contribute
> and make it enjoyable and deeper learning for all of us.
>
> I want to add some quote from Koopman so you can add material which is
> clearer and detailed than his because his has a lot to be desired :
>
ISTM, more bait for the fishes...
I don't mean to be critical, but are you collecting information for research
report, an analysis, or planning some programming project? You've posted
quite a wide range of moderately in-depth CS (Computer Science) questions to
various groups fairly recently. I.e., you can't possibly be using all the
CS information provided to you so far... It takes time and experience to
use it. Before you've had time to read some of the answers, let alone
digest or comprehend them, you've posted even more questions. If you just
tell someone what you're project plans are, maybe you'll find an expert, or
someone who knows a solution. I.e., if you're not writing a PHD thesis, it
might be better to just say: "I need to do this, starting with this, and
ending with this. How can I do this?"
Rod Pemberton
io_x
"Rod Pemberton" <do_no...@notreplytome.cmm> ha scritto nel messaggio
news:i4rem0$qm1$1...@speranza.aioe.org...
> "Standish P" <stn...@gmail.com> wrote in message
> news:0cfdd7f2-72b2-4b5b...@l6g2000yqb.googlegroups.com...
>> This is being xposted to cl.postscript and al.asm, but my main group
>> is cl.forth.
>>
>
> 2 out 3...
>
>> Here is a quote from Forth Inc HDBK 3rd ed., p61.
>>
>> [snip quote]
>>
>> So how does Forth, postscript or even assembly achieve the effect of
>> named or unnamed but referrable "temporary" , "automatic" ie
>> temporarily allocated variables referrable multiple times without
>> having to copy and dup them multiple times and avoid unreadablility.
>>
>
> Assembly
> has no named variables
yes it could be, the name of variable is just one number
accessed tru esp
exmple: for "mov dword [esp + 24] , 0"
%define NameOfVar 24
mov dword [esp + NameOfVar] , 0
io_x
"io_x" <a...@b.c.invalid> ha scritto nel messaggio
news:4c7183a5$0$40285$4faf...@reader2.news.tin.it...
>
> "Rod Pemberton" >> Assembly
>> has no named variables
>
> yes it could be, the name of variable is just one number
> accessed tru esp
> exmple: for "mov dword [esp + 24] , 0"
>
> %define NameOfVar 24
> mov dword [esp + NameOfVar] , 0
%undef NameOfVar
Elizabeth D Rather
...
> So how does Forth, postscript or even assembly achieve the effect of
> named or unnamed but referrable "temporary" , "automatic" ie
> temporarily allocated variables referrable multiple times without
> having to copy and dup them multiple times and avoid unreadablility.
>
> What are the collected patterns of such "stack management skills" ? Is
> there any documentation or animations or applets to show this ?
Any book on Forth includes the words used for stack manipulation: DUP,
SWAP, etc.
But the important point is that it's remarkably effortless. Here is a
very simple example:
The word EMIT takes as an argument the numeric value of an ASCII
character, and sends it to the current display device. So:
: STAR ( -- ) [CHAR] * EMIT ;
...will display an asterisk. No variables needed, no stack twiddling.
: STARS ( n -- ) 0 ?DO STAR LOOP ;
...will display 'n' stars. To test it, just type:
7 STARS ( to display seven asterisks )
: BOX ( ncols nrows -- ) 0 DO DUP STARS CR LOOP DROP ;
4 5 BOX
...will display a box consisting of 5 rows of 4 stars each. In this
case, we had to make a copy of the argument for STARS, because its value
will be consumed every time STARS is called, and we discard it at the
end because it's no longer needed. But isn't that a lot simpler than
having to declare named temporary values, construct and pass stack
frames, etc.?
Yes, that's a simple example. But, in practice, quite a lot of Forth
code is just that simple and straightforward.
Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com
"Forth-based products and Services for real-time
applications since 1973."
==================================================
P.M.Lawrence
.
.
.
> So how does Forth, postscript or even assembly achieve the effect of
> named or unnamed but referrable "temporary" , "automatic" ie
> temporarily allocated variables referrable multiple times without
> having to copy and dup them multiple times and avoid unreadablility.
I THINK you may be asking, just how does Forth implement local
variables. If not, please ignore this.
IMHO, the easiest way to get a feel for this is to start by looking at
something related but simpler, a sort of poor man's local variable.
Suppose you want to have X and Y as local variables. First, set them
up as global variables. Then, around the code where you want to use
the locals, do something like this:-
... X @ >R Y @ >R ... ( do something with locals ) ... R> Y ! R>
X ! ...
You should be able to see that the values in X and Y are behaving as
though they were locals, with older values being stored temporarily on
the return stack (it's important not to muck that up during all
this!). This is not quite the same as local variables, though, because
pointers to X and Y don't stay pointing at the older values. You would
need another layer of indirection to achieve that effect.
The actual mechanisms that set up local variables do things like that,
only more so and with more hidden. So I thought that describing this
poor man's version would be more helpful as an introduction to the
sort of thing going on, even though it isn't quite the same thing and
needs the programmer to be more involved and careful - both of those
precisely because less is hidden. P.M.Lawrence.
Hugh Aguilar
> So how does Forth, postscript or even assembly achieve the effect of
> named or unnamed but referrable "temporary" , "automatic" ie
> temporarily allocated variables referrable multiple times without
> having to copy and dup them multiple times and avoid unreadablility.
This thread discusses locals:
http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4b9f67406c6852dd/0218831f02564410
> What are the collected patterns of such "stack management skills" ? Is
> there any documentation or animations or applets to show this ?
Why don't you just try writing some programs? That is the best way to
learn the "patterns" of "stack management skills." Download my novice
package --- it is for novices:
http://www.forth.org/novice.html
There are no animations, however "Starting Forth" does have cartoons
--- kind of like animations except that they don't move. Maybe someday
some graphical artist will make an actual animation, so we can see the
two-headed bird representing SWAP actually fly in and swap the top two
stack elements --- that would be pretty cool!
I think that if you had been living in Europe in the late 1400s, you
would have been the guy who said:
"Well, I *would* discover America --- but I'm waiting for the jet
airplane to be invented."
Nathan
> On Aug 22, 2:50 am, Standish P <stnd...@gmail.com> wrote:
>
> > So how does Forth, postscript or even assembly achieve the effect of
> > named or unnamed but referrable "temporary" , "automatic" ie
> > temporarily allocated variables referrable multiple times without
> > having to copy and dup them multiple times and avoid unreadablility.
>
What the heck does "unreadability" mean? Are not all executable
binaries readable by default? I guess you must be using a copyright-
protected Operating System?
> This thread discusses locals:http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4...
>
Darn, your link is broken! To be precise, I was hoping to meet some
"hot lonely locals," preferably wearing nothing but what they were
born in. :)
[Is alt.lang.spam leaking through??]
> > What are the collected patterns of such "stack management skills" ? Is
> > there any documentation or animations or applets to show this ?
>
Well, there is that "debugger" game. Or... am I thinking of Frogger??
> Why don't you just try writing some programs?
Huh?
I'm pretty sure you lost me there.
> That is the best way to
> learn the "patterns" of "stack management skills." Download my novice
> package --- it is for novices:http://www.forth.org/novice.html
>
Will that help me stop smoking?
> There are no animations, however "Starting Forth" does have cartoons
> --- kind of like animations except that they don't move. Maybe someday
> some graphical artist will make an actual animation, so we can see the
> two-headed bird representing SWAP actually fly in and swap the top two
> stack elements --- that would be pretty cool!
>
I would actually make a trip to the theatre to see that movie. When
is it being released?
> I think that if you had been living in Europe in the late 1400s, you
> would have been the guy who said:
> "Well, I *would* discover America --- but I'm waiting for the jet
> airplane to be invented."
Didn't they have buses in the 1400s??
Nathan.
Nathan
> "Rod Pemberton" <do_not_h...@notreplytome.cmm> ha scritto nel messaggionews:i4rem0$qm1$1...@speranza.aioe.org...
>
>
>
> > "Standish P" <stnd...@gmail.com> wrote in message
> >news:0cfdd7f2-72b2-4b5b...@l6g2000yqb.googlegroups.com...
> >> This is being xposted to cl.postscript and al.asm, but my main group
> >> is cl.forth.
>
> > 2 out 3...
>
> >> Here is a quote from Forth Inc HDBK 3rd ed., p61.
>
> >> [snip quote]
>
> >> So how does Forth, postscript or even assembly achieve the effect of
> >> named or unnamed but referrable "temporary" , "automatic" ie
> >> temporarily allocated variables referrable multiple times without
> >> having to copy and dup them multiple times and avoid unreadablility.
>
> > Assembly
> > has no named variables
>
> yes it could be, the name of variable is just one number
> accessed tru esp
> exmple: for "mov dword [esp + 24] , 0"
>
> %define NameOfVar 24
>
> mov dword [esp + NameOfVar] , 0
Perhaps a SWAP macro to emulate Forth:
{assumes 'ecx' points to the top of evaluation stack}
mov eax, [ecx]
mov ebx, [ecx+4]
mov [ecx], ebx
mov [ecx+4], eax
Maybe a DUP macro...
mov eax, [ecx]
sub ecx, 4
mov [ecx], eax
Nathan.
Albert van der Horst
Standish P <stn...@gmail.com> wrote:
>This is being xposted to cl.postscript and al.asm, but my main group
>is cl.forth.
>
>Here is a quote from Forth Inc HDBK 3rd ed., p61.
>
>
>All Forth defining words are immediately followed by the name of the
>object being defined. All define permanent (static) global objects.
>These are independent definitions, just like colon definitions. Forths
>data stack fills the role used by local variables in other languages.
>ANS
>Forth has a limited provision for local variables, but they are rarely
>used and and are NOT recommended for beginners because their use tends
>to inhibit the development of good stack management skills.
>
>
>So how does Forth, postscript or even assembly achieve the effect of
>named or unnamed but referrable "temporary" , "automatic" ie
>temporarily allocated variables referrable multiple times without
>having to copy and dup them multiple times and avoid unreadablility.
The effect of local named variables can be achieved by macro's in
assembler. Forth is a very good macro assembler too.
If used by a skilled person, the problems with assembler and Forth lie
in safety, not in readability and understandability, or the attainable
level of abstraction.
>
>What are the collected patterns of such "stack management skills" ? Is
>there any documentation or animations or applets to show this ?
Do you really want to see an animation of the swapping of
2 stack items? You can. Google for "starting Forth" and
read that book on Marcel Hendrix website.
Groetjes Albert
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
io_x
"Nathan" ha scritto nel messaggio
news:8c0f16ce-27f9-499c...@d8g2000yqf.googlegroups.com...
>Maybe a DUP macro...
>Nathan.
don't know them, i never use them
what i say it is possible use stack for "automatic" variables e.g
funzione:
; reserve 1024 chars
sub esp, 1024
; define the name of variables
; as offset from the top of the stack that point
; to reserve memory
%define var1 0
%define var2 4
%define array 8
%define var3 1000
mov dword[esp + var1], 0 ; access the variable var1 and zero it
...
; use var1, var2, array, var3
...
; undef them because they have one meaning only in this function
%undef var1
%undef var2
%undef array
%undef var3
; free 1024 chars
add esp, 1024
ret
easy