On Mon, Sep 11, 2000 at 05:02:13PM -0400, Dan Sugalski wrote:
> If you're essentially adding stack primitives to C, sure. If you're talking
> about a whole new language it's still an issue.
OK, I think I've got my brains in order now. I *think*. This is probably still
going to be a little fuzzy. I'm making this up as I go along.
Let's say, initially, that I'm suggesting adding features to a current
language - any language - which *facilitates the implementation of stack-based
virtual machines*: a Basis for Developing Stack Machines.
Let's also, initially, say that we're targeting C. So, if I refer to bdsm, I
mean C-with-bdsm-extensions. We'll implement bdsm using a Perl program to
preprocess this into real C, and we'll probably need an additional library
too.
So, here's the first thing we can do: we'll add stack primitives "push" and
"pop". Here's program 1 in bdsm:
-------------
MainStack; /* This is the declaration of the global variable */
int main (int argc, char** argv) {
InitStack; /* This sets up the stack */
pushy_thing();
poppy_thing();
}
void pushything() {
Frame x; /* What you put in a frame is up to you */
x = 10;
push(x);
}
void poppy_thing() {
Frame y;
y = pop;
/* y is 10 here. */
}
---------------
Here you have complete control over what goes into a frame; our "Frame" type
here looks to be typedef'd to an int or something similar. We could equally
have it being a struct and we put things into and get them out of the struct
in the usual way. That's nice and simple, and we'll call that "level 1".
Let's add a couple more primitives, and call it bdsm level 1a:
Frame backup(int x); /* Returns the frame x below the current frame */
Mark mark; /* Inserts a marker and returns a label to it */
Frame retrieve(Mark x); /* Retrieves a marked frame */
narrow; /* Hides everything underneath the current frame */
narrow(x); /* Hides everything x frames down and below */
widen; /* Cancels the previous narrow */
These aren't proper prototypes because they might not be proper functions;
they may be implemented using the Perl preprocessor, or as C preprocessor
macros. At this point you should be able to see that we could add these
primitives to any language, so long as we can write a Perl program to
preprocess them and whatever code we need to implement them. But we'll stick
with C for now because it's nice.
Level 2 comes when we start dictating what goes into a frame and how we get at
it. Let's make a Frame into a hash because it's a good place to store things.
-------------
MainStack;
int main (int argc, char** argv) {
InitStack;
pushy_thing();
poppy_thing();
}
void pushything() {
Frame x;
x->put("foo", 10);
push(x);
}
void poppy_thing() {
Frame y;
y = pop;
/* y->get("foo") is 10 here. */
}
---------------
Note that, with sufficiently sophisticated preprocessing, we can still
implement this in any language we choose.
In bdsm level 3, we add the concepts of a stash and context. Read carefully:
I'm about to use terms which are familiar in Perl 5 internals but will have
different meanings here.
A stash is very much like what we've seen in the previous program: a stash is
a stack of hashes. The difference is that, in our main stack - the operand
stack - we can't get to variables in frames (in stashes, we'll call them
"pads") below the current one. In our stashes, we can get at a variable in any
pad. Stashes are indexed for efficiency, so you have an index of which pad
things are in.
"Context" refers to the frames of our *TARGET* language - the stuff that
pp_enter and pp_leave are made of. Let's say, for instance, we want to store
our Perl-space variables in a stash. (This is, incidentally, what stashes are
intended for. :) Entering a block in Perl space is equivalent to pushing an
empty pad onto the stash; leaving a block pops the top pad. fetchgv looks up a
variable in the stash's index and pulls it out of the appropriate frame.
We have to explicitly push and pop pads from the stash - that's one of the
things pp_enter and pp_leave would do.
Level 4 is where it gets silly; level 3 used a stash to handle "external"
variables and the pads corresponded to frames of our target languages, level 4
uses an additional stash to handle the variables of the language we're
programming in. A pad is pushed onto the "internal" stash when we enter a
block in C and popped when we leave.
---------------
MainStack;
MainStash;
int main (int argc, char** argv) {
InitStack;
StashPut("foo",10);
deeper();
/*
StashGet("bar") returns NULL here, because deeper()'s
pad has been popped.
*/
}
void deeper() {
printf("This should be 10: %i\n", StashGet("foo"));
StashPut("bar",20);
}
---------------
OK, this is where we start needing Parse::RecDescent and really heavy stuff,
but it's still possible, and it's still possible to do it in any language you
choose.
By level 6, variable allocation in the internal stash is automatic.
---------------
MainStack;
MainStash;
int main (int argc, char** argv) {
InitStack;
PadVar foo = 10; /* PadVar int foo? */
Frame x; /* This is still to do with the operand stack: see P.2 */
deeper();
/* Use of "bar" here generates an error */
x = pop;
printf("This should be \"hi\"\n", x->get("frob"));
}
void deeper() {
PadVar bar = 20;
Frame x;
x->put("frob", "hi"); /* This is the operand stack, not a stash */
push(x);
printf("This should be 10: %i\n", foo);
}
---------------
It's getting harder to parse, since you start having to watch all the
variables everywhere to see if they're PadVars somewhere in a call stack or
not, but C is well-defined and we can do that. We can do it in C++ too, or
Java, or PASCAL, or whatever else we feel like.
It's also steadily turning into an independent language, but it's still being
translated into an existing language - any existing language. Level 6, which
I'm currently only dreaming of, takes this into its logical extreme, creating
an intermediary language based on stacks; it'll look like a bastard cross of C
and Perl with lots of bizarre primitives, but it'll be translatable into
anything we can write a translator for.
How far do you want to go?
--
Oh my god! They killed Kennedy!
-- edfromo
