The Artima Developer Community
Sponsored Link

Weblogs Forum
Adding another Stack to Cat

12 replies on 1 page. Most recent reply: Jul 11, 2006 7:24 AM by Emil Cristian Alexandrescu

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 12 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Adding another Stack to Cat (View in Weblogs)
Posted: Jul 4, 2006 5:43 PM
Reply to this message Reply
Summary
When two stacks are better than one. Also an introduction to the type annotation syntax which will be introduced in an upcoming version of Cat.
Advertisement
The main role of Cat is to provide an intermediate representation of an arbitrary functional or imperative high-level language which can be:
  • easily optimized
  • easily translated
Mapping Cat to a lower level language like the MSIL poses some particular challenges since the MSIL is based on two stacks:
  • a variable/argument stack
  • an evaluation stack
Any straightforward mapping from Cat to MSIL slow and cumbersome because I have to emulate an open-ended stack. Whenever I want to add or subtract two numbers the compiler has to move the values from the Cat stack to the evaulation stack, execute the MSIL opcode, and then move the result back to the Cat stack.

A nice solution to this problem, is to extend Cat with a second stack.

Internally Cat uses a type notation for the purposes of optimization, and to prepare for the fact that upcoming versions will support static typing. The challenge I faced was to express the type of a Cat program in a multi-stack language.

The best way to explain my proposed notation is throught the example of an integer addition function:

  add : (a:int, b:int)() => (c:int)()
I would read this as follows: the function add consumes two integer values from the main stack, and no values on the second stack. When add terminates it produces a single integer value on the main stack.

Now since I want to map my dialect of Cat to various byte-codes such as MSIL, there will be no primitive which actually adds values from the top of the main stack. All primitive arithmetic operations occur on the secondary stack. This means that the integer add function will need to be defined as a standard library function in terms of the following primitives:

  $cat.standard.integer.add 
  [
    loadint   // (a:int)() => ()(a)
    loadint   // (a:int)() => ()(a)
    addint    // ()(a:int b:int) => ()(c:int)
    storeint  // ()(a:int) => (a)()
  ] // (a:int b:int)() => (c)()
  def 
The type notation for def in future versions will be optional. I want to support dynamic type checking, static type checking, and static type inference (ambitious I know).

So this in of itself hasn't yet solved the problem of frequent moving back and forth of values between stacks, however, there is now potential for the Cat optimization algorithms to be applied intelligently. For example I can write the following optimization rule:

  (storeint loadint) = ()
This optimization rule states simply that any-time you have a consecutive storeint and loadint operation you can simply eliminate them both. This becomes useful when you see something like:
  [
    1 2 3 
    cat.standard.integer.add 
    cat.standard.integer.add 
  ]
When the compiler inlines these functions it reads:
  [
    1 2 3 
    loadint loadint addint storeint
    loadint loadint addint storeint
  ]
Notice that the optimizer can now find the storeint/loadint pattern and eliminate it.
  [
    1 2 3 
    loadint loadint addint 
    loadint addint storeint
  ]

This is only the tip of the iceberg of the optimization engine which I have planned for Cat. The ultimate goal is to develop a pattern-matching and rewriting macro language for Cat which is type-aware. What I find amusing is that the type annotations are more complicated than the actual code.

That's it for now, my brain hurts.


Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Adding another Stack to Cat Posted: Jul 6, 2006 1:06 AM
Reply to this message Reply
I'm too busy to hurt my brain by thinking through all the implications of the above but the first thought that popped into my head was:

isn't this moving closer to the Forth model and, if so, does that mean running Cat on top of an ANSI Forth would be easier?

Vincent O'Sullivan

Posts: 724
Nickname: vincent
Registered: Nov, 2002

Re: Adding another Stack to Cat Posted: Jul 6, 2006 4:56 AM
Reply to this message Reply
If two stacks are better than one, might it not follow that n+1 stacks would be better than n?

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

2 stacks good, 3 stacks not-quite-bad Posted: Jul 6, 2006 1:26 PM
Reply to this message Reply
/* If two stacks are better than one, might it not follow that n+1 stacks would be better than n?
*/

Every so often I get a hankering to learn assembly code. Generally, CPUs have more than one stack (for instance, http://www.embeddedrelated.com/usenet/embedded/show/31646-1.php ), so even if MSIL didn't have two stacks, a second stack makes sense.

But there is a point of diminishing returns. I wouldn't recommend as many stacks as Parrot ( http://www.parrotcode.org/ ), for instance.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: 2 stacks good, 3 stacks not-quite-bad Posted: Jul 6, 2006 1:32 PM
Reply to this message Reply
OK, my example of more than one stack wasn't so good. A better example can be found at http://cm.bell-labs.com/cm/cs/who/dmr/clcs.html (the original "how C works on a PDP-11" paper). This paper refers to a stack pointer that points to the next instruction to execute (and where return adresses are stored when calling a function), and a stack to hold arguments passed to the function. I believe these stacks are often merged into one, but they don't have to be.

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: 2 stacks good, 3 stacks not-quite-bad Posted: Jul 6, 2006 2:44 PM
Reply to this message Reply
> Every so often I get a hankering to learn assembly code.
> Generally, CPUs have more than one stack

x86 has only one stack? I believe you can have as many stacks as you want by changing the stack pointer though.

So you could dynamically add stacks:

def next_stack: stack_pointer += size_of_one_stack
def prev_stack: stack_pointer -= size_of_one_stack

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Adding another Stack to Cat Posted: Jul 6, 2006 3:34 PM
Reply to this message Reply
It doesn't seem to get much more discussion but I bookmarked a thread for Reva Forth talking about using an aux third stack instead of locals

http://ronware.org/reva/viewtopic.php?id=63

I assume from the silence on their wiki that the idea didn't generate rabid discussion.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: 2 stacks good, 3 stacks not-quite-bad Posted: Jul 6, 2006 4:15 PM
Reply to this message Reply
/* [me] Generally, CPUs have more than one stack

[Jules] x86 has only one stack?
*/

To be honest, I'm not sure. The book I bought on assembly code was for the Motorola 68000 (yes, it's outdated), and I didn't check it before posting earlier. And although I was positive that the 68000 series had two stacks, Wikipedia says it didn't really ( http://en.wikipedia.org/wiki/Motorola_68000 ).

Well, Wikipedia says there was a second stack pointer for supervisory mode, but it did exactly the same thing as the "regular" stack pointer. When I get home I'll have to check my books to see where I got the "most CPUs have more than one stack" idea from.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Adding another Stack to Cat Posted: Jul 6, 2006 5:20 PM
Reply to this message Reply
> If two stacks are better than one, might it not follow
> that n+1 stacks would be better than n?

As a note of interest: a push-down automaton (PDA) with only one stack is not a Turing machine but a PDA with two stacks is.

http://en.wikipedia.org/wiki/Stack_machine

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Adding another Stack to Cat Posted: Jul 7, 2006 4:18 AM
Reply to this message Reply
You can emulate a turing machine with one stack if you have certain primitives like dip.

Sean Conner

Posts: 19
Nickname: spc476
Registered: Aug, 2005

Re: Adding another Stack to Cat Posted: Jul 9, 2006 1:50 AM
Reply to this message Reply
The Intel x86 has one hardware stack register, ESP. Function calls place the return address on the stacked pointed to by ESP. There are other opcodes that add/remove data from the stack pointed to by ESP, but they all manipulate the ESP register.

What you might be getting confused by is that each protection ring on the x86 architecture has its own copy of ESP, but that's not a detail that readily inpacts code written.

The Motorola 68000 has one hardware stack register, A7. Like the Intel version, there are various opcodes that manipulate the stack pointed to by A7. And like the Intel, usermode has one copy of A7, and the supervisor mode has a separate copy of A7. Again, not normally a concern.

The only CPU that I know of that has two explicit stacks is the Motorola 6809, an 8-bit CPU that was the precursor to the Motorola 68000. In this CPU, the stacks are registers S and U---S is used for saving return addresses, but other than that, there is no real difference between using the S stack and the U stack (other than realizing that the S stack may have return addresses on it). All opcodes (except those that involve function calls) that manipulate the stack have opcodes that work with S or U. This CPU has no usermode/supervisor mode distinction.

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Adding another Stack to Cat Posted: Jul 11, 2006 7:20 AM
Reply to this message Reply
Yes, working with many stacks is always a good idea. Exception handling with "try-catch" blocks is yet another example where stacks are needed / useful.
What if you'll need to use a lot of stacks?? A syntax like:
add ()()()...(a:int, b:int)()...() => ()()()...(c:int)()...()
would be very inappropriate.

Instead, I propose you to:

(1) The majority of the functions will work with the default stack.

(2) There must be two UNARY operators (MOVE / COPY) which moves / copies the top of a given stack to the top of the default one.

(3) There must be a UNARY operator (SET_DEFAULT_STCACK) which does exactly what its name suggests.

This stuff ALWAYS works (can work with dynamic stacks) and it's appropriate for handling as many stacks as nneeded.

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Adding another Stack to Cat Posted: Jul 11, 2006 7:24 AM
Reply to this message Reply
Yes, but having dip and an idefinite number of stacks makes... a distributed TM!

Distributed computing on a small PL - GooD stuff.

Flat View: This topic has 12 replies on 1 page
Topic: Adding another Stack to Cat Previous Topic   Next Topic Topic: Pure and Impure Functions


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us