Creating a new stack from an exisiting one.

[Chad]

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

}

 

[Ben Bacarisse]

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.

 

[Chad]

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.

 

[markspace]

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.

 

[BartC]

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

 

[Jeff Higgins]

This just deepens the mystery.

No mystery, just eternal student Chad.

 

[Lew]

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 + "]");
}
}

 

[Pascal J. Bourguignon]

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.

 

[Ben Bacarisse]

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.

 

[Pascal J. Bourguignon]

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

 

[Ben Bacarisse]

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>

 

[Thomas Richter]

Am 04.11.2012 13:48, schrieb Ben Bacarisse:

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?

 

[Jeff Higgins]

No mystery, just eternal student Chad.

<http://code.google.com/p/csc413/>

 

[Pascal J. Bourguignon]

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.

 

[BartC]

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

 

[Pascal J. Bourguignon]

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.

 

[Ben Bacarisse]

Am 04.11.2012 13:48, schrieb Ben Bacarisse:

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.

 

[Jeff Higgins]

<http://code.google.com/p/csc413/>

Extra credit:
<http://markfaction.wordpress.com/20...rtual-machine-architecture-and-the-dalvik-vm/>
<http://www.cs.tcd.ie/David.Gregg/papers/Gregg-SoCP-2005.pdf>

 

[markspace]

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.

 

[Jeff Higgins]

Extra credit:
<http://markfaction.wordpress.com/20...rtual-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>