Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #19604 > unrolled thread

Creating a new stack from an exisiting one.

Back to article view | Back to comp.lang.java.programmer

Contents

  Creating a new stack from an exisiting one. Chad <cdalten@gmail.com> - 2012-11-03 07:45 -0700
    Re: Creating a new stack from an exisiting one. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-11-03 15:51 +0000
      Re: Creating a new stack from an exisiting one. Chad <cdalten@gmail.com> - 2012-11-03 09:22 -0700
        Re: Creating a new stack from an exisiting one. markspace <-@.> - 2012-11-03 11:20 -0700
        Re: Creating a new stack from an exisiting one. "BartC" <bc@freeuk.com> - 2012-11-03 18:58 +0000
        Re: Creating a new stack from an exisiting one. "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-04 00:49 +0100
        Re: Creating a new stack from an exisiting one. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-11-04 00:44 +0000
          Re: Creating a new stack from an exisiting one. "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-04 13:14 +0100
            Re: Creating a new stack from an exisiting one. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-11-04 12:48 +0000
              Re: Creating a new stack from an exisiting one. Thomas Richter <thor@math.tu-berlin.de> - 2012-11-04 14:14 +0100
                Re: Creating a new stack from an exisiting one. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-11-04 15:38 +0000
              Re: Creating a new stack from an exisiting one. "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-04 14:41 +0100
            Re: Creating a new stack from an exisiting one. "BartC" <bc@freeuk.com> - 2012-11-04 14:11 +0000
              Re: Creating a new stack from an exisiting one. "Pascal J. Bourguignon" <pjb@informatimago.com> - 2012-11-04 16:00 +0100
            Re: Creating a new stack from an exisiting one. markspace <-@.> - 2012-11-04 11:02 -0800
            Re: Creating a new stack from an exisiting one. Martin Gregorie <martin@address-in-sig.invalid> - 2012-11-04 19:56 +0000
      Re: Creating a new stack from an exisiting one. Jeff Higgins <jeff@invalid.invalid> - 2012-11-03 16:46 -0400
        Re: Creating a new stack from an exisiting one. Jeff Higgins <jeff@invalid.invalid> - 2012-11-04 08:22 -0500
          Re: Creating a new stack from an exisiting one. Jeff Higgins <jeff@invalid.invalid> - 2012-11-04 11:30 -0500
            Re: Creating a new stack from an exisiting one. Jeff Higgins <jeff@invalid.invalid> - 2012-11-04 19:40 -0500
    Re: Creating a new stack from an exisiting one. Lew <lewbloch@gmail.com> - 2012-11-03 16:02 -0700

Page 1 of 2  [1] 2  Next page →

#19604 — Creating a new stack from an exisiting one.

I have stack like the following..

[1, 4, 10, 20]

What I need to do is pop the top item off the stack such that it looks
like the following..

[1, 4, 10] [20]

Then, starting at [20], I need to be able to push the numbers 78 and
99 onto this stack such that the output looks like

[1, 4, 10] [20, 78, 99]

Can this be done without creating a new stack? If so how? I just need
some general idea.  Here is what I came up with so far..

import java.util.*;

public class funcTest {


    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.add(1);
        stack.add(4);
        stack.add(10);
        stack.add(20);

        System.out.println(stack);

        Object temp = stack.pop();

        System.out.println(stack + " " + "["+ temp + "]");

        //This part from here on down doesn't work
        /*
        stack = (Stack)temp;
        stack.push(78);
        stack.push(99);

        System.out.println(stack + " " + "["+ temp + "]");
         *
         */
    }//end main()

}

[toc] | [next] | [standalone]

#19605

Chad <cdalten@gmail.com> writes:

> I have stack like the following..
>
> [1, 4, 10, 20]
>
> What I need to do is pop the top item off the stack such that it looks
> like the following..
>
> [1, 4, 10] [20]
>
> Then, starting at [20], I need to be able to push the numbers 78 and
> 99 onto this stack such that the output looks like
>
> [1, 4, 10] [20, 78, 99]
>
> Can this be done without creating a new stack? If so how? I just need
> some general idea.

You seem to be using [...] to denote a stack so what you want as the
result clearly has two stacks.  That seems to suggest you must make
another one (unless there is a spare one lying around for some reason).

>  Here is what I came up with so far..
>
> import java.util.*;
>
> public class funcTest {
>
>
>     public static void main(String[] args) {
>         Stack<Integer> stack = new Stack<Integer>();
>         stack.add(1);
>         stack.add(4);
>         stack.add(10);
>         stack.add(20);
>
>         System.out.println(stack);
>
>         Object temp = stack.pop();
>
>         System.out.println(stack + " " + "["+ temp + "]");
>
>         //This part from here on down doesn't work
>         /*
>         stack = (Stack)temp;
>         stack.push(78);
>         stack.push(99);
>
>         System.out.println(stack + " " + "["+ temp + "]");
>          *
>          */
>     }//end main()
>
> }

This just deepens the mystery.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#19607

On Nov 3, 8:51 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Chad <cdal...@gmail.com> writes:
> > I have stack like the following..
>
> > [1, 4, 10, 20]
>
> > What I need to do is pop the top item off the stack such that it looks
> > like the following..
>
> > [1, 4, 10] [20]
>
> > Then, starting at [20], I need to be able to push the numbers 78 and
> > 99 onto this stack such that the output looks like
>
> > [1, 4, 10] [20, 78, 99]
>
> > Can this be done without creating a new stack? If so how? I just need
> > some general idea.
>
> You seem to be using [...] to denote a stack so what you want as the
> result clearly has two stacks.  That seems to suggest you must make
> another one (unless there is a spare one lying around for some reason).
>
>
>
>
>
> >  Here is what I came up with so far..
>
> > import java.util.*;
>
> > public class funcTest {
>
> >     public static void main(String[] args) {
> >         Stack<Integer> stack = new Stack<Integer>();
> >         stack.add(1);
> >         stack.add(4);
> >         stack.add(10);
> >         stack.add(20);
>
> >         System.out.println(stack);
>
> >         Object temp = stack.pop();
>
> >         System.out.println(stack + " " + "["+ temp + "]");
>
> >         //This part from here on down doesn't work
> >         /*
> >         stack = (Stack)temp;
> >         stack.push(78);
> >         stack.push(99);
>
> >         System.out.println(stack + " " + "["+ temp + "]");
> >          *
> >          */
> >     }//end main()
>
> > }
>
> This just deepens the mystery.
>

That what I thought. However, I don't think so. Let me elaborate. This
is part of a much much larger software project. The part is question
is the RunTimeStack module. In this module, we have one stack which is
called runStack. This is an ArrayList that is supposed to hold the
data pushed onto the stack. In other words, after I push the numbers
onto the stack, it would look something like..

[1, 4, 10, 20]

There is another stack, of type Stack, that is called framePointers.
This holds the current offset. So if I have something like f(3) in the
source code, the corresponding runTimeStack is supposed to go
something like

LIT 3  //private machine code
[1, 4, 10, 20, 3]

ARGS 1 //ditto
[1, 4, 10, 20] [3]

CALL F<<20>>
[1, 4, 10, 20] [3]



I don't see how to create the new "stack" when I'm only given one
stack to hold the data and another to hold the offsets.

[toc] | [prev] | [next] | [standalone]

#19608

On 11/3/2012 9:22 AM, Chad wrote:
 >
 > That what I thought. However, I don't think so. Let me elaborate. This
 > is part of a much much larger software project. The part is question
 > is the RunTimeStack module. In this module, we have one stack which is
 > called runStack. This is an ArrayList that is supposed to hold the
 > data pushed onto the stack. In other words, after I push the numbers
 > onto the stack, it would look something like..
 >
 > [1, 4, 10, 20]
 >
 > There is another stack, of type Stack, that is called framePointers.
 > This holds the current offset. So if I have something like f(3) in the
 > source code, the corresponding runTimeStack is supposed to go
 > something like


Well, most of us remember our lessons from our coursework, so there's 
not much chance we'll do your homework for you.  Most real machine code 
that I've seen only uses one stack for both local variables and the 
frame pointers.  I don't know where you get two stacks from.

Since your specification sounds hookey to me, I'd ask you to ask your 
instructor what is really going on.  Without understanding the exact 
specification it's impossible to say what is really going on here.


 >
 > LIT 3  //private machine code
 > [1, 4, 10, 20, 3]
 >
 > ARGS 1 //ditto
 > [1, 4, 10, 20] [3]
 >
 > CALL F<<20>>
 > [1, 4, 10, 20] [3]
 >
 >
 >
 > I don't see how to create the new "stack" when I'm only given one
 > stack to hold the data and another to hold the offsets.
 >

[toc] | [prev] | [next] | [standalone]

#19610

"Chad" <cdalten@gmail.com> wrote in message 
news:b227ba50-ccbc-4da0-9f6a-31bb809f329d@ah9g2000pbd.googlegroups.com...

> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset.

So this is some sort of language where you can have a stack of frame 
pointers (presumably due to nested functions)?

(Instead of the ones I'm used to where there only one frame pointer is 
visible at any time, and usually kept in a register.)

So you have two stacks; why shouldn't that be enough? (Normally only one is 
used.)

>So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3  //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]

> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.

It's not clear what you're trying to do. You haven't shown the stack of 
frame pointers.

I would guess that when F is called, it has to create some space on the data 
stack (for its local data), create a new frame pointer to point to that 
space, and push that frame pointer onto the frame pointer stack (or maybe it 
keeps the current one off the stack).

But if you are implementing something to do with such a language, then you 
need to find out a bit more about how these things are done.

(BTW what's the difference between .add and .push in your OP?)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#19613

Chad <cdalten@gmail.com> writes:

> On Nov 3, 8:51 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> Chad <cdal...@gmail.com> writes:
>> > I have stack like the following..
>>
>> > [1, 4, 10, 20]
>>
>> > What I need to do is pop the top item off the stack such that it looks
>> > like the following..
>>
>> > [1, 4, 10] [20]
>>
>> > Then, starting at [20], I need to be able to push the numbers 78 and
>> > 99 onto this stack such that the output looks like
>>
>> > [1, 4, 10] [20, 78, 99]
>>
>> > Can this be done without creating a new stack? If so how? I just need
>> > some general idea.
>>
>> You seem to be using [...] to denote a stack so what you want as the
>> result clearly has two stacks.  That seems to suggest you must make
>> another one (unless there is a spare one lying around for some reason).
>>
>>
>>
>>
>>
>> >  Here is what I came up with so far..
>>
>> > import java.util.*;
>>
>> > public class funcTest {
>>
>> >     public static void main(String[] args) {
>> >         Stack<Integer> stack = new Stack<Integer>();
>> >         stack.add(1);
>> >         stack.add(4);
>> >         stack.add(10);
>> >         stack.add(20);
>>
>> >         System.out.println(stack);
>>
>> >         Object temp = stack.pop();
>>
>> >         System.out.println(stack + " " + "["+ temp + "]");
>>
>> >         //This part from here on down doesn't work
>> >         /*
>> >         stack = (Stack)temp;
>> >         stack.push(78);
>> >         stack.push(99);
>>
>> >         System.out.println(stack + " " + "["+ temp + "]");
>> >          *
>> >          */
>> >     }//end main()
>>
>> > }
>>
>> This just deepens the mystery.
>>
>
> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset. So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3  //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]
>
>
>
> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.


Well, pure stacks have only those operations:

    (empty-stack) --> stack
    (push element stack) --> stack
    (pop stack) --> element
    (is-empty-stack? stack) --> boolean

If you are considering this kind of pure stack, then you must indeed use
two stacks.


But when implementing programming languages, we don't use pure stacks
usually.  We have a data structure that's more complex, with indeed
frame pointers, and ways to refer frame members below and above frame
pointers, in addition to elements below the top of the stack.

It's more like:

    (empty-stack) --> stack
    (push element stack) --> stack
    (pop stack) --> element
    (is-empty-stack? stack) --> boolean
    (push-frame stack) --> stack-frame
    (pop-frame stack-frame) --> stack
    (stack-ref stack-frame offset) --> element
    (stack-set! stack stack-frame offset value) --> stack

You can implement that with an array and an index to the "top of stack",
and represent the stack frames as indices inside this array.


-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#19614

Chad <cdalten@gmail.com> writes:
<snip the old description>
> That what I thought. However, I don't think so. Let me elaborate. This
> is part of a much much larger software project. The part is question
> is the RunTimeStack module. In this module, we have one stack which is
> called runStack. This is an ArrayList that is supposed to hold the
> data pushed onto the stack. In other words, after I push the numbers
> onto the stack, it would look something like..
>
> [1, 4, 10, 20]
>
> There is another stack, of type Stack, that is called framePointers.
> This holds the current offset. So if I have something like f(3) in the
> source code, the corresponding runTimeStack is supposed to go
> something like
>
> LIT 3  //private machine code
> [1, 4, 10, 20, 3]
>
> ARGS 1 //ditto
> [1, 4, 10, 20] [3]
>
> CALL F<<20>>
> [1, 4, 10, 20] [3]
>
>
> I don't see how to create the new "stack" when I'm only given one
> stack to hold the data and another to hold the offsets.

That seems to be a different question.  Thank goodness I was not able
to answer the old one!

I think you are probably confusing yourself by writing []s and calling
the contents a stack.  I am still not sure what you want, but the new
words "runStack" and "framePointers" and the function call example put
this in a context I understand.

Why do think a new stack is needed?  The conventional thing to do is to
push the function's arguments and the record the new top of stack in the
frame pointer.  Since the previous frame pointer will need to be
restored when this function exits, it is reasonable to record these
frame pointers in a stack, though some implementations will use the main
stack for these as well (often just relying on the register save/restore
mechanism).  Anyway, that aside, the effect is that the 3 won't be on a
new stack, just in a portion of the main stack identified by the frame
pointer for this function call.

If function G calls function F we get a stack that looks like this at
the point that F starts to run:

  ][args for G | G's locals][args for F |

Now the []s don't denote stacks.  Each bracketed part is a stack
frame -- a region on the main stack.  The |s mark the frame pointers.
Function arguments are to the left, and locals are to the right.

To be very explicit, let's assume that your stack uses plain integer
indexes and the functions look like this

  function G(a) { c = 42; F(c, a) }
  function F(a, b) { ... don't care about what's in F }

and G is called like this, G(99).  If 66 stack cells have already been
used, we get the following situation:

  index            ...  67  68  69  70 71
  content          ...  99  42  99  42
  corresponding to ... G:a G:C F:b F:a
   
  frame pointer stack: ...  68  71
   
  Top of stack: 71.

The two numbers in the frame pointer stack mark the |s in the previous
schematic.  The code is now ready to allocate the first local variables
in F (if any).

All this excludes any mention of the return address.  Maybe that's being
handled separately.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#19616

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> I think you are probably confusing yourself by writing []s and calling
> the contents a stack.  I am still not sure what you want, but the new
> words "runStack" and "framePointers" and the function call example put
> this in a context I understand.
>
> Why do think a new stack is needed?  The conventional thing to do is to
> push the function's arguments and the record the new top of stack in the
> frame pointer.  Since the previous frame pointer will need to be
> restored when this function exits, it is reasonable to record these
> frame pointers in a stack, though some implementations will use the main
> stack for these as well (often just relying on the register save/restore
> mechanism).  Anyway, that aside, the effect is that the 3 won't be on a
> new stack, just in a portion of the main stack identified by the frame
> pointer for this function call.
>
> If function G calls function F we get a stack that looks like this at
> the point that F starts to run:
>
>   ][args for G | G's locals][args for F |
>
> Now the []s don't denote stacks.  Each bracketed part is a stack
> frame -- a region on the main stack.  The |s mark the frame pointers.
> Function arguments are to the left, and locals are to the right.
>
> To be very explicit, let's assume that your stack uses plain integer
> indexes and the functions look like this
>
>   function G(a) { c = 42; F(c, a) }
>   function F(a, b) { ... don't care about what's in F }
>
> and G is called like this, G(99).  If 66 stack cells have already been
> used, we get the following situation:
>
>   index            ...  67  68  69  70 71
>   content          ...  99  42  99  42
>   corresponding to ... G:a G:C F:b F:a
>    
>   frame pointer stack: ...  68  71
>    
>   Top of stack: 71.
>
> The two numbers in the frame pointer stack mark the |s in the previous
> schematic.  The code is now ready to allocate the first local variables
> in F (if any).
>
> All this excludes any mention of the return address.  Maybe that's being
> handled separately.

Well, I don't know of any processor that uses a separate stack for the
frame pointers.  See for example the instructions LINK and UNLK of the
680x0 (there are similar instructions on X86 and others).  The top frame
pointer is usually kept in A6, while the stack pointer is A7=SP.

At the entry point of functions, there's an instruction:

   LINK A6,#-localSpace

and at the exit of them, there are:

   UNLK A6
   RTN


So for functions like:

>   function G(a) { c = 42; F(c, a) }
>   function F(a, b) { ... don't care about what's in F }

and starting with A7=SP=0xfff0 (stacks tend to grow downward in
processors, but it makes no differences, only the offsets are
opposites):

     A7:       0xfff0           
     A6:       0xfff8

the caller pushes 99 for the argument of G, then calls G, with a JSR G,
which pushes the return address onto the stack:

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      
      A7:      0xffe8
      A6:      0xfff8

then G executes LINK A6,#-4 since it needs one local variable.

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  random value for c

      A7:      0xffe0
      A6:      0xffe4                   ; G frame pointer

c:=42 This writes into the local frame at the address -4(A6):

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  42                       ; c

      A7:      0xffe0
      A6:      0xffe4                   ; G frame pointer


F(c,a) this reads the local frame: c is in the local variables at
-4(A6), and a is in the parameters at 8(A6).  The arguments are pushed
on the stack:

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  42                       ; c
      0xffdc:  42
      0xffd8:  99

      A7:      0xffd8
      A6:      0xffe4                   ; G frame pointer

then F is called.

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  42                       ; c
      0xffdc:  42
      0xffd8:  99
      0xffd4:  return address into G

      A7:      0xffd4
      A6:      0xffe4                   ; G frame pointer

So F executes LINK A6,#-n (n depending on the local storage F needs):

And so on.  When F returns, it calls:

   UNLK A6

which restores the stack to:\

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  42                       ; c
      0xffdc:  42
      0xffd8:  99
      0xffd4:  return address into G

      A7:      0xffd4
      A6:      0xffe4                   ; G frame pointer


and:

   RTN

which returns to G

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      0xffe4:  0xfff8                   ; old fram pointer
      0xffe0:  42                       ; c
      0xffdc:  42
      0xffd8:  99

      A7:      0xffd8
      A6:      0xffe4                   ; G frame pointer

When G returns, it executes:

     UNLK A6

which restores the stack to:

      0xfff0:
      0xffec:  99
      0xffe8:  return-address-to-caller
      
      A7:      0xffe8
      A6:      0xfff8

and then:

    RTN

and we're back to the caller:

      0xfff0:
      0xffec:  99
      
      A7:      0xffec
      A6:      0xfff8


-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#19617

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:
<snip>
> Well, I don't know of any processor that uses a separate stack for the
> frame pointers.

No, me neither.  The description also lacked any mention of the return
address so I don't think this is about hardware.  Maybe it's coursework,
and the separate stacks are there to keep the concepts clear?  I don't
know.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#19618

Am 04.11.2012 13:48, schrieb Ben Bacarisse:
> "Pascal J. Bourguignon"<pjb@informatimago.com>  writes:
> <snip>
>> Well, I don't know of any processor that uses a separate stack for the
>> frame pointers.
>
> No, me neither.  The description also lacked any mention of the return
> address so I don't think this is about hardware.  Maybe it's coursework,
> and the separate stacks are there to keep the concepts clear?  I don't
> know.

Didn't FORTH have the concept of separate stacks, one for passing 
arguments, and one for expression evaluation?

[toc] | [prev] | [next] | [standalone]

#19624

Thomas Richter <thor@math.tu-berlin.de> writes:

> Am 04.11.2012 13:48, schrieb Ben Bacarisse:
>> "Pascal J. Bourguignon"<pjb@informatimago.com>  writes:
>> <snip>
>>> Well, I don't know of any processor that uses a separate stack for the
>>> frame pointers.
>>
>> No, me neither.  The description also lacked any mention of the return
>> address so I don't think this is about hardware.  Maybe it's coursework,
>> and the separate stacks are there to keep the concepts clear?  I don't
>> know.
>
> Didn't FORTH have the concept of separate stacks, one for passing
> arguments, and one for expression evaluation?

That rings a bell.  There are certainly other abstract machines with
multiple stacks such as Landin's SECD machine.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#19620

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> <snip>
>> Well, I don't know of any processor that uses a separate stack for the
>> frame pointers.
>
> No, me neither.  The description also lacked any mention of the return
> address so I don't think this is about hardware.  Maybe it's coursework,
> and the separate stacks are there to keep the concepts clear?  I don't
> know.

That said, in early Fortran and Pascal compilers, they used a "display
record" vector, which would point to the visible frames.  While such a
"display record" could be managed as a stack, static analysis allows
for a fixed size and direct updating.


So for example:

    function f (x:integer)
      function g (y:integer)
      begin
         if x>y then
            g:=x+y+f(x-y)-g(y+1)
         else
            g:=x+y;
      end;
    begin
      if x<0
         f:=1
      else
         f:=g(x-1)
    end;

while one could need an unbounded number of stack frames (depending on
the value of the parameters),  the invocations of the function g see
only the frame of one invocation of the function f, so we need a
"display record" of size 2.


          stack:
   -------------------
    stack frame for f
    stack frame for g
    stack frame for g
    stack frame for g
    stack frame for f
    stack frame for g
    stack frame for g
    stack frame for f <----+     display:
    stack frame for g      |     ---------
    stack frame for g      +------- f
    stack frame for g <------------ g

The display record is a kind of stack of lexical scopes.  If we get
outside of f, and enter another embedding of lexical scopes, another set
of stack frame pointers may be "stacked" into the display record.

-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#19622

"Pascal J. Bourguignon" <pjb@informatimago.com> wrote in message 
news:87vcdllg3u.fsf@informatimago.com...
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>> All this excludes any mention of the return address.  Maybe that's being
>> handled separately.
>
> Well, I don't know of any processor that uses a separate stack for the
> frame pointers.

Usually because you only need access to one at a time. The OP mentioned a 
stack just for frame pointers; I assumed (perhaps wrongly), then access to 
any of them might be needed at any time. If not then a single stack will do. 
(Or perhaps no real stack at all, as a software data structure seems to be 
used. Then, any scheme could be employed.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#19623

"BartC" <bc@freeuk.com> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> wrote in message
> news:87vcdllg3u.fsf@informatimago.com...
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>>> All this excludes any mention of the return address.  Maybe that's being
>>> handled separately.
>>
>> Well, I don't know of any processor that uses a separate stack for the
>> frame pointers.
>
> Usually because you only need access to one at a time. The OP
> mentioned a stack just for frame pointers; I assumed (perhaps
> wrongly), then access to any of them might be needed at any time. If
> not then a single stack will do. (Or perhaps no real stack at all, as
> a software data structure seems to be used. Then, any scheme could be
> employed.)

Yes.  And languages like C don't allow embedded functions like Pascal,
so the problem solved by display records doesn't occur, and otherwise
for recursive embedded functions, one can also pass the references to
the outer stack frames as invisible parameters, if they're needed.  So
as you say, there's a single access at a time.



But the important point is that it's not a pure stack, but a vector
where you can access elements at given offsets.


-- 
__Pascal Bourguignon__
http://www.informatimago.com

[toc] | [prev] | [next] | [standalone]

#19628

On 11/4/2012 4:14 AM, Pascal J. Bourguignon wrote:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> I think you are probably confusing yourself by writing []s and calling
>> the contents a stack.  I am still not sure what you want, but the new
>> words "runStack" and "framePointers" and the function call example put
>> this in a context I understand.


> Well, I don't know of any processor that uses a separate stack for the
> frame pointers.  See for example the instructions LINK and UNLK of the
> 680x0 (there are similar instructions on X86 and others).  The top frame
> pointer is usually kept in A6, while the stack pointer is A7=SP.


After reviewing some of the diagrams and information on call stacks on 
wikipedia, I wonder if Chad is mistakenly calling the second "stack" is 
actually a register file.  It seems sensible for a routine to receive 
two data structures, one stack and one set of registers, to simulate 
execution.  One register would normally be choose to point to the start 
of the current stack frame, which seems similar to what he is describing.

He could also be confused and assuming that the current stack frame is 
separate from the main call stack, which isn't normally the case.  These 
are really the only two ideas I have here.

[toc] | [prev] | [next] | [standalone]

#19629

On Sun, 04 Nov 2012 13:14:45 +0100, Pascal J. Bourguignon wrote:

> Well, I don't know of any processor that uses a separate stack for the
> frame pointers.  See for example the instructions LINK and UNLK of the
> 680x0 (there are similar instructions on X86 and others).  The top frame
> pointer is usually kept in A6, while the stack pointer is A7=SP.
>
I can name two for you. Both are Motorola parts, though they belong to 
different chipsets:

MC6809
====== - an 8/16 bit chip, has two stack pointers, S and U. Both can be 
mapped anywhere in RAM. The S pointer is used during subroutine calls, 
while the U pointer is available for use as a secondary stack: unlike the 
S pointer, there are no automatic operations tied to it, so it will only 
be be changed by user-written instructions such as PSHU, PULU, LEAU and 
LDU.     

MC68000
=======, its variants and derivatives, e.g. 68000, 68008, 68020, 68030 
and 68040. These have a file of 8 32 bit address registers. In a similar 
way to the 6809, any or all of the 8 can be used as stack pointers, i.e. 
all can by the subject of push and pop instructions, but D7 (also 
referred to as SP) is used as the system stack for subroutine calls, etc.

HTH


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#19611

On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
> Chad<cdalten@gmail.com>  writes:
>> I just need some general idea.
>
> This just deepens the mystery.
>
No mystery, just eternal student Chad.

[toc] | [prev] | [next] | [standalone]

#19619

On 11/03/2012 04:46 PM, Jeff Higgins wrote:
> On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
>> Chad<cdalten@gmail.com> writes:
>>> I just need some general idea.
>>
>> This just deepens the mystery.
>>
> No mystery, just eternal student Chad.
>
<http://code.google.com/p/csc413/>

[toc] | [prev] | [next] | [standalone]

#19625

On 11/04/2012 08:22 AM, Jeff Higgins wrote:
> On 11/03/2012 04:46 PM, Jeff Higgins wrote:
>> On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
>>> Chad<cdalten@gmail.com> writes:
>>>> I just need some general idea.
>>>
>>> This just deepens the mystery.
>>>
>> No mystery, just eternal student Chad.
>>
> <http://code.google.com/p/csc413/>
Extra credit:
<http://markfaction.wordpress.com/2012/07/15/stack-based-vs-register-based-virtual-machine-architecture-and-the-dalvik-vm/>
<http://www.cs.tcd.ie/David.Gregg/papers/Gregg-SoCP-2005.pdf>

[toc] | [prev] | [next] | [standalone]

#19630

On 11/04/2012 11:30 AM, Jeff Higgins wrote:
> On 11/04/2012 08:22 AM, Jeff Higgins wrote:
>> On 11/03/2012 04:46 PM, Jeff Higgins wrote:
>>> On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
>>>> Chad<cdalten@gmail.com> writes:
>>>>> I just need some general idea.
>>>>
>>>> This just deepens the mystery.
>>>>
>>> No mystery, just eternal student Chad.
>>>
>> <http://code.google.com/p/csc413/>
> Extra credit:
> <http://markfaction.wordpress.com/2012/07/15/stack-based-vs-register-based-virtual-machine-architecture-and-the-dalvik-vm/>
>
> <http://www.cs.tcd.ie/David.Gregg/papers/Gregg-SoCP-2005.pdf>
Additional reading:
<http://docs.oracle.com/javase/tutorial/>
<http://www.artima.com/insidejvm/ed2/jvm.html>
<http://www.drdobbs.com/architecture-and-design/the-design-of-llvm/240001128>

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web