Creating a new stack from an exisiting one.

Discussion in 'Java' started by Chad, Nov 3, 2012.

  1. Chad

    Chad Guest

    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()

    }
     
    Chad, Nov 3, 2012
    #1
    1. Advertising

  2. Chad <> 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.
     
    Ben Bacarisse, Nov 3, 2012
    #2
    1. Advertising

  3. Chad

    Chad Guest

    On Nov 3, 8:51 am, Ben Bacarisse <> wrote:
    > Chad <> 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.
     
    Chad, Nov 3, 2012
    #3
  4. Chad

    markspace Guest

    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.
    >
     
    markspace, Nov 3, 2012
    #4
  5. Chad

    BartC Guest

    "Chad" <> wrote in message
    news:...

    > 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
     
    BartC, Nov 3, 2012
    #5
  6. Chad

    Jeff Higgins Guest

    On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
    > Chad<> writes:
    >> I just need some general idea.

    >
    > This just deepens the mystery.
    >

    No mystery, just eternal student Chad.
     
    Jeff Higgins, Nov 3, 2012
    #6
  7. Chad

    Lew Guest

    Chad wrote:
    > I have stack like the following..
    >
    > [1, 4, 10, 20]


    Others have commented on the vagueness of your spec. I'll just assume things.

    I assume you mean that '20' is at the top of the stack, based on your later
    remarks.

    > What I need to do is pop the top item off the stack such that it looks
    > like the following..
    >
    > [1, 4, 10] [20]


    By this I assume you mean stack [1, 4, 10] and item '20' in its own memory.

    > 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]


    So here you push first 20, then the others onto a second stack.

    > Can this be done without creating a new stack? If so how? I just need


    Based on what you said and my assumptions, no. The very definition of your
    operations is to push '20' onto a new stack, so you have to create a new
    stack onto which to push '20'.

    > some general idea. Here is what I came up with so far..
    >
    > import java.util.*;
    >
    > public class funcTest {


    Java naming conventions call for an initial upper-case letter in type names.

    > 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();


    Really 'temp' should be declared 'Integer'.

    > System.out.println(stack + " " + "["+ temp + "]");
    >
    > //This part from here on down doesn't work


    And by "doesn't work", you mean ...?

    > /*
    > stack = (Stack)temp;


    Oh, /that's/ what you mean. This violates the type system of Java.

    You see, the object in 'temp' is not itself a stack. So there.


    > stack.push(78);


    You can't "push" onto an 'Integer'.

    > stack.push(99);


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


    Don't make comments that contribute no information.

    > }


    The fundamentals of Java rest on its type system. You tried to break it and
    of course you ran afoul of type enforcement.

    Don't do that.

    Part of your misstep was to duck the generics. Don't try to run away from
    generics. Generics turns the attempt to 'push()' an 'Integer' into a compile
    error instead of a production exception.

    When you program in Java, take time to think about types. You want two stacks
    of integers by your very problem statement.

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

    System.out.println(stack);

    Integer temp = stack.pop();
    System.out.println(popped + " "+ temp);

    Stack<Integer> spill = new Stack<>();
    spill.push(temp);
    spill.push(78);
    spill.push(99);

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

    --
    Lew
     
    Lew, Nov 3, 2012
    #7
  8. Chad <> writes:

    > On Nov 3, 8:51 am, Ben Bacarisse <> wrote:
    >> Chad <> 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
     
    Pascal J. Bourguignon, Nov 3, 2012
    #8
  9. Chad <> 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.
     
    Ben Bacarisse, Nov 4, 2012
    #9
  10. Ben Bacarisse <> 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
     
    Pascal J. Bourguignon, Nov 4, 2012
    #10
  11. "Pascal J. Bourguignon" <> 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.
     
    Ben Bacarisse, Nov 4, 2012
    #11
  12. Am 04.11.2012 13:48, schrieb Ben Bacarisse:
    > "Pascal J. Bourguignon"<> 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?
     
    Thomas Richter, Nov 4, 2012
    #12
  13. Chad

    Jeff Higgins Guest

    On 11/03/2012 04:46 PM, Jeff Higgins wrote:
    > On 11/03/2012 11:51 AM, Ben Bacarisse wrote:
    >> Chad<> writes:
    >>> I just need some general idea.

    >>
    >> This just deepens the mystery.
    >>

    > No mystery, just eternal student Chad.
    >

    <http://code.google.com/p/csc413/>
     
    Jeff Higgins, Nov 4, 2012
    #13
  14. Ben Bacarisse <> writes:

    > "Pascal J. Bourguignon" <> 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
     
    Pascal J. Bourguignon, Nov 4, 2012
    #14
  15. Chad

    BartC Guest

    "Pascal J. Bourguignon" <> wrote in message
    news:...
    > Ben Bacarisse <> 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
     
    BartC, Nov 4, 2012
    #15
  16. "BartC" <> writes:

    > "Pascal J. Bourguignon" <> wrote in message
    > news:...
    >> Ben Bacarisse <> 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
     
    Pascal J. Bourguignon, Nov 4, 2012
    #16
  17. Thomas Richter <-berlin.de> writes:

    > Am 04.11.2012 13:48, schrieb Ben Bacarisse:
    >> "Pascal J. Bourguignon"<> 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.
     
    Ben Bacarisse, Nov 4, 2012
    #17
  18. Chad

    Jeff Higgins Guest

    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<> 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>
     
    Jeff Higgins, Nov 4, 2012
    #18
  19. Chad

    markspace Guest

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

    > Ben Bacarisse <> 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.
     
    markspace, Nov 4, 2012
    #19
  20. Chad

    Jeff Higgins Guest

    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<> 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>
     
    Jeff Higgins, Nov 5, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Guillaume Hanique
    Replies:
    3
    Views:
    2,866
    Guillaume Hanique
    Sep 6, 2006
  2. Casey Hawthorne
    Replies:
    3
    Views:
    1,152
    Flash Gordon
    Nov 1, 2009
  3. Adnan Qamar

    Customizing exisiting DataGrid Functionality

    Adnan Qamar, Apr 28, 2004, in forum: ASP .Net Datagrid Control
    Replies:
    1
    Views:
    138
    Rick Spiewak
    Apr 29, 2004
  4. Sean Warburton
    Replies:
    6
    Views:
    164
    Brian Candler
    Jan 27, 2010
  5. korssane korssane

    how to update an exisiting .PO file

    korssane korssane, Mar 15, 2011, in forum: Ruby
    Replies:
    0
    Views:
    142
    korssane korssane
    Mar 15, 2011
Loading...

Share This Page