Alternatives to Stack for Function Call Semantics

continuationsemanticsstack-orientedtail-callvirtual machine

We all know and love that function calls are usually implemented using the stack; there are frames, return addresses, parameters, the whole lot.

However, the stack is an implementation detail: calling conventions may do different things (i.e. x86 fastcall uses (some) registers, MIPS and followers use register windows, and so on) and optimizations can do even other things (inlining, frame pointer omission, tail-call optimization..).

Sure, the presence of convenient stack instruction on many machines (VMs like JVM and the CLR, but also real machines like x86 with their PUSH/POP etc.) make it convenient to use it for function calls, but in some cases it is possible to program in a way in which a call stack is not needed (I am thinking about Continuation Passing Style here, or Actors in a message passing system)

So, I was beginning to wonder: is it possible to implement function call semantics without a stack, or better, using a different data structure (a queue, perhaps, or an associative map?)
Of course, I understand that a stack is very convenient (there is a reason why it is ubiquitous) but I recently bumped into an implementation that made me wonder..

Do any of you know if it has ever been done in any language/machine/virtual machine, and if so which are the striking differences and shortcomings?

EDIT:
My gut feelings are that different sub-computation approaches can use different data structures.
For example, lambda calculus is not stack based (the idea of function application is captured by reductions) but I was looking at a real language/machine/example. That's why I am asking…

Best Answer

Depending on the language, it may not be necessary to use a call stack. Call stacks are only necessary in languages that allow recursion or mutual recursion. If the language does not allow recursion, then only one invocation of any procedure may be active at any moment, and local variables for that procedure may be statically allocated. Such languages do have to make provision for context changes, for interrupt handling, but this still does not require a stack.

Refer to FORTRAN IV (and earlier) and early versions of COBOL for examples of languages that do not require call stacks.

Refer to the Control Data 6600 (and earlier Control Data machines) for an example of a highly-successful early supercomputer that did not provide direct hardware support for call stacks. Refer to the PDP-8 for an example of a very successful early minicomputer that did not support call stacks.

As far as I know, the Burroughs B5000 stack machines were the first machines with hardware call stacks. The B5000 machines were designed from the ground up to run ALGOL, which required recursion. They also had one of the first descriptor-based architectures, which laid groundwork for capability architectures.

As far as I know, it was the PDP-6 (which grew into the DEC-10) that popularized call stack hardware, when the hacker community at MIT took delivery of one and discovered that the PUSHJ (Push Return Address and Jump) operation allowed the decimal print routine to be reduced from 50 instructions to 10.

The most basic function call semantics in a language that allow recursion require capabilities that match nicely with a stack. If that's all you need, then a basic stack is a good, simple match. If you need more than that, then your data structure has to do more.

The best example of needing more that I have encountered is the "continuation", the ability to suspend a computation in the middle, save it as a frozen bubble of state, and fire it off again later, possibly many times. Continuations became popular in the Scheme dialect of LISP, as a way to implement, among other things, error exits. Continuations require the ability to snapshot the current execution environment, and reproduce it later, and a stack is somewhat inconvenient for that.

Abelson & Sussman's "Structure and Interpretation of Computer Programs" goes into some detail on continuations.

Related Solutions

Object-Oriented Readability – Using Empty Subclasses to Enhance Class Hierarchy Semantics

Your second example has the benefit of no case statement, and no CommandType. This means you can a new statement type without having to modify a case statement. A case statement ought to cause an OOP programmer to pause a moment and consider whether the design should be changed to get rid of the case statement. A variable denoting a thing's type ought to cause the programmer to pause a long while.

However, the visitor pattern doesn't seem to be needed here. Simpler would be to use a class hierarchy, as you did, but then put the SQL generation inside that hierarchy rather than having it be a separate class:

class SqlCommand {
  abstract String sql;
}

class InsertCommand : SqlCommand {
  overrides String sql {...};
}

class DeleteCommand : SqlCommand {
  overrides String sql {...};
}

The code inside the sql functions will probably turn out to have shared behavior, or enough complexity, that moving the shared behavior and complexity into a separate SqlBuilder class would be good:

class InsertCommand : SqlCommand {
  overrides String sql {
    builder = SqlBuilder.new
    builder.add("insert into")
    builder.add_identifier(table_name)
    buidler.add("values")
    builder.add_value_list(column_names)
    ...
    return builder.sql
  };
}

The SqlCommand drives the process of creating the sql, pushing its details into the SqlBuilder. This keeps the SqlCommand and SqlBuilder decoupled, since the SqlCommands do not have to expose their entire state for the builder to use. This has the benefits of your second example, but without the complexity of the visitor pattern.

If it turns out that sometimes you need the sql built one way and sometimes another (perhaps you want to support more than one SQL back end), then you abstract the SqlBuilder class, like so:

class SqlBuilder {
  abstract void add(String s);
  abstract void add_identifier(String identifier);
  abstract void add_value_list(String[] value_list);
  ...
}

class PostgresSqlBuilder : SqlBuilder {
  void add(String s) {...}
  void add_identifier(String identifier) {...}
  void add_value_list(String[] value_list) {...}
  ...
}

class MysqlSqlBuilder : SqlBuilder {
  void add(String s) {...}
  void add_identifier(String identifier) {...}
  void add_value_list(String[] value_list) {...}
  ...
}

Then the sql functions use the builder passed into them, rather than creating one:

class InsertCommand : SqlCommand {
  overrides String sql (SqlBuilder builder) {
    builder.add("insert into")
    builder.add_identifier(table_name)
    buidler.add("values")
    builder.add_value_list(column_names)
    ...
    return builder.sql
  };
}

Virtual Machine Stack – Fundamental Stack Manipulation Operations

Many stack based languages use roll as well, which is a generalized rot on an arbitrary number of elements in the stack. They also implement the reverse operation for rotating the stack the other way.

I would say that roll is more fundamental than rot.

I have no answer though about Turingness of this.