[MUD-Dev] Storing tokens with flex & bison

[cg at ami-cg.GraySage.Edmonton.AB.CA]

[Jon A. Lambert:]

> Not to belabor the point, since I think we're in agreement although coming from
> different angles.  The interesting thing about Crenshaw's toy compiler is that it's a 
> single phase compiler.   The AST is the current state of the compiler's run-time 
> stack and code generation is done as it parser executes.   Admittedly this 
> limits your optimizing options since the AST disappears when the parsing is
> complete.  It is rather elegantly simple though.

I'm guilty of never actually going to read the Crenshaw stuff. I think my
excuse was that for some reason I didn't end up with a full set of articles
at the time.

That same one-phase technique is exactly what I use in my Draco compiler
and in my Toy compiler. Definitely works well, especially if you are
memory-tight, like I was on CP/M systems.

> I thought I'd include another example clipped from the Crenshaw tutorial for the 
> benefit of anyone else reading.   He also discusses the unary negate optimization 
> you mention above elsewhere. 
>
> ---cut---
> There is  a concept in compiler theory called "lazy" translation.

[...]

OK, now I understand the relevance of the term "lazy" translation. I've
seen similar terms used for other things, and that was likely getting me
down the wrong path. I understand the technique.

> As you can see Crenshaw is in conflict with your .sig ---
> He designs in inefficiency in and removes it later... ;-)

Hmm. :-) A peephole optimizer is a prime example of that, although it is
more a matter of removing inefficiency efficiently!

> Hmm, I was thinking in terms of how many instructions my VM will be traversing 
> rather than how the hardware is going to handle those instructions. 
> Now I could implement my VM class as a 3 register machine using the
> members:

Ah, OK. That makes sense. If your register count is small, that works fine.
Now reminded, my 8080 emulator on x86 simply used the one-byte opcode as
a direct index into a 256 entry dispatch table.

> >From the bytecode angle the register is an intrinsic part of the opcode, that is
> it is determined at compilation time.  Now push() and pop() operations 
> in the VM are going to be to checking for a stack overflow or underflow, no?

Actually, no. If you don't allow users to directly generate byte-code, and
you are careful with your compiler, there is never any need to check for
stack underflow. (Well, my interpreter checks the SP after a 'return'
instruction to see if it should return from this level of execution.)
Stack overflow can be handled by a combination of a few checks at run-time
(e.g. at function entry), and compilation checks. This is the exact code for
integer addition from my sources:

	CASE(bc_add) {
	    ULONG_T ul;

	    ul = *sp++;
	    *sp += ul;
	    BREAK;
	}

Macros 'CASE' and 'BREAK' allow the code to compile either using the
gcc dynamic goto stuff, or not. Note: use lots of small scopes and very
local variables like this, so that the compiler can do maximum re-use of
the limited X86 register set.

> I don't know.  It may be something worth revisiting.  
> Besides is there anything more swell than a VM that looks like a 6502? :-)

I decline comment. :-)

> I guess this might lead to the question of whether it is better to have more 
> or less opcodes for your VM's instruction set.  I will note that the Java VM 
> has quite a boatload of special case opcodes, it even distinguishes between 
> pushing an int and pushing a constant one or zero.  So is it better to accomplish 
> something by generating a longer series of simple bytecode operations, or 
> implement a lot of special purpose bytecodes?

I say go for the special-case ones. I have some like 'pshz', 'psh1', etc.
They are very easy to do and use, and can have a noticeable speedup. I'm
real tempted to go add 'add1' and 'sub1', as in our earlier discussion,
to see what effect they have. Should take about 15 minutes.

> I don't think speed of compilation is really an issue at least in the context of 
> a mud server's internal programming language.  Typically in an LP, Moo, Cold,
> Muck, etc. you are compiling rather small pieces of method code or single objects
> so you can add as many phases or passes to the compilation as you need.
> Of course online compilation should be multitasked and handled just like any 
> other mud event especially if you have a user programmable setup.

Well, when you have a system that works well, you tend to use it a lot.
I've gotten into the habit of changing one line of scenario source and then
recompiling all 20,000 lines, rather than making the change online! Too
many times I've forgotten to make the change in the master sources.

> Other than me tripping over terminology again, I still don't agree with the
> following:
>
> --->Byte-code execution really only makes sense, I believe, for a strongly
> typed language. If run-time checks and conversions are needed, they will
> likely cost far more time than the basic interpretation of the code, and
> so going to byte-code instead of staying with something more direct, could
> be a waste of time, in that byte-code won't speed execution up much.
>
> I agree that overhead is higher, I still think it's less than direct
> interpretation.

I don't understand your sentence, I'm afraid. The overhead of byte-code
execution is less than that of direct interpretation, certainly. Otherwise
no-one, myself included, would bother with byte-code. My point, however,
is that if the overheads of non-static typing are significant, then going
to byte-code could be rather pointless, since it might gain only a few
percent speedup. With strong typing, there is virtually no run-time
overhead for type-checking sorts of things, so going from direct
interpration to byte-code is almost certainly a big win. This is just
a case of one of the general rules concerning speeding programs up: fix
the big things first, then the little things.

> It looks like what one would do with a strongly-typed system.  All the  
> complexity and overhead is hiding under the covers of C++. 
>
> Var& Var::operator=(const Var& value);  
> friend Var operator+(const Var& v1,const Var& v2) throw(TypeError);
>
> You'll find all the switches, if-else chains, and conversion exceptions in 
> those functions.  Yes it's overhead but it is not complex.  Maintenance, 
> debugging and readability are very good.  At least I think so.

Any idea how much overhead? Just guessing, comparing my snippet of source
against what you are showing here, I'd guess a factor of 25 or more. That
is actually *more* than I had thought. And heaven help you if you end
up with some temporary copies of variables because of problems with
reference parameters! I have practically zero experience with C++, so
the presense of all those '&'s would make me *very* nervous about that.

--
Don't design inefficiency in - it'll happen in the implementation.

Chris Gray     cg at ami-cg.GraySage.Edmonton.AB.CA
               http://www.GraySage.Edmonton.AB.CA/cg/



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev