1. Inner loop compiler

Hi Barbarella,

>First to you, Mike,

>>Yes, although the [more] Euphoric it is the better I say.  

>If by 'Euphoric' you mean 'flexible and easy to use', I'm afraid my 
>plans does not go in that direction.
>For the inner loop, I'd like to sacrifice flexibility and ease of use 
>for safety and speed whenever possible.

>>I have often thought about the usefulness of such a system and if I 
>>believed my namesake (MTS) then a more comprehensive compiler/converter 
>>already exists. Getting access to it might be a problem though.  

>That's interesting! Would you please tell me more about the system you 
>have been thinking about?
>Maybe you could even expand a little bit on how it compares to your 
>perception of my extremely unclear plans?

In recent years a gentleman called Mike the Spike (MTS) used to frequent 
the Euphoria mailing list and he
apparently wrote a Euphoria to C translator which was claimed to produce 
lightning code. I sometimes wonder
if some list readers thought that MTS' claims were a merely ploy to 
prompt Rob to write his translator.
As you will know the RDS translator *is* in existence and, at the risk 
of seeming disloyal to Rob,
let's just us say it could be faster. Anyway, a search on this mailing 
list should give you enough 
background info about all of this.

After reading your earlier thoughts on what you may wish to achieve it 
seems to me there is
practically no end of the complexity that a compiler could have and I 
agree that
"minimalist, simple, safe and fast" are desirable attributes. I wonder 
if you might
consider a more generic approach in that the "language" could be 
modelled on Euphoria.
You could have a simplified version of the syntax which converts to asm 
and then
machine code by using asm.e
Since tight code loops are an obvious starting point for speed-up you 
could focus on those
sorts of constructs, eg:

This line of code...

integer plot_x, plot_y
plot_y = 10
for i = 1 to 100
	plot_x = i
	PlotLine()
end for

..is converted into..

def int plot_x, plot_y
      mov eax, #000A
      mov [plot_y], eax
      mov ecx, #0001
loop: push ecx
      mov [plot_x], ecx
      call PlotLine
      pop ecx
      inc ecx
      cmp ecx, #0064
      jmpgt loop

Please excuse this code travesty but I'm sure you get the picture.

Just a few ideas..
i) Since Eu's integer size is a subset of asm 32-bit integer type why 
not just assume all integers
are 32 bits? It is not as if the machine code is going to call a 
Euphoria routine, is it.
ii) All variables could simply have their own memory location instead of 
being forced into a register.
This would make the project much easier to write and register 
optimisation could be left till
later, if at all.
iii) loop variables *could* have	their own register but what happens for 
several nested loops?
iv) Leave out all: labels, GOTO's and any other nasty C stuff, and don't 
listen to anyone
that tells you otherwise.
v) There are times when the result of a floating point operation should 
be converted to an integer so
why not provide automatic conversion (for declared atoms) in such cases 
(also the reverse one too)?
vi) Since all variables have their own memory location then you could 
pass sub-routine parameters
using registers. Of course, there would be a limited number to go around 
but still, it is an idea..
Maybe a better idea is to have a stack that parameters can be pushed 
onto and a register is used
to advise the called routine just how many parameters are available to 
use..
vii) Include a provision to decode expressions, someone must know how to 
do this.

Regards,
Mike

new topic     » topic index » view message » categorize

2. Re: Inner loop compiler

Hello, Mr. E! :D=20

Thanks for your reply, I've been so busy in the real-world these days, =
but now I finally got plenty of time to reply. This LONGISH post answers =
several of your recent postings, ok?



> Euphoria Win and Linux both have a call_back function for writing your =

> own call back routines.  I've been able to call these from machine =
code,=20
> so you can still do the hard stuff in Euphoria.  But it would limit =
you=20
> to exu or exw.
=20
> -- call.exw -- demonstrates use of call near instruction

Great, that snippet looks very useful, compiler or no compiler!

> The BOUND instruction would work nicely for checking index values in=20
> sequences.  Just set up a nice interrupt handler for out-of-range =
errors=20
> and you're good to go.

I was preparing to use cmp index, lowest / jb error / cmp index highest =
/ ja error... 'Bound' seems a much better alternative.
=20
> Peek, poke and call - each can be done with a single asm instruction =
...=20
> for integers though.

However, it would be a problem if people found themselves 'forced' to =
use peek and poke on a regular basis. That would compromise safety. One =
possibility is to adopt a safe version of the c pointer type. Such a =
pointer could either address an array that was safely allocated by =
Euphoria, or an area of memory (say, bios video memory) that the =
programmer would want to access. Unlike in c, the pointer would not be =
allowed to be misaligned with its type or moved out of it's own bounds. =
E.g. :

    -- Integer 'video_mem' is allowed to point to any byte in the mode =
19 screen.
    BYTE POINTER video_mem 0xA0000, 64000


> >     Basically, this leaves us with statements for program flow,
> I have some eucode that generates machine code branches automatically=20
> from a sequence of conditions, and correctly uses the right sized=20
> (signed byte or signed doubleword) jump instruction.
Great, that code would make an eventual direct-to-machine-code compiler =
easier to write...
=20
> > ...and arrays that must be compatible with Euphoria sequences.

> Has anyone reverse-engineered Rob's sequence format from the=20
> Euphoria-to-C translator yet? I guess that information wouldn't be =
that=20
> useful anyway.. since we can't get the address of a sequence by any=20
> means I know of.  Someone might be able to poke around in memory and=20
> find some global sequence index and then locate other sequences from=20
> there...  Manipulating sequences would also have to be required to=20
> emulate the translator conventions on reference counts and whatnot.
>=20
> OR... you could just write your own sequence engine in asm and use =
that.

My fault, "compatible with Euphoria sequences" was a very misleading and =
clumsy expression. All I had in mind was that it should be easy to peek =
and poke sequences into and out of static memory. For example, Euphoria =
can only read and write 32 bit ints, and 32 or 64 bit floats, so any =
other types of data in the arrays would be incompatible.

Actually, I was thinking in the opposite direction of Euphoria's =
arbitrarily structured sequences. Sequence trees with recursive pointers =
are great in high level, but in the inner loop, I'd like to sacrifice =
this kind of flexibility and instead go for fast, direct indexing. =
Something like arrays of (preferably) power-of-2 aligned data, e.g. int =
a[17][512] would be great. Of course, sometimes arrays like [600][800] =
might also be nice, (to save memory), which could hopefully be arranged =
for with a few lea operations. Your own mode 19 pixel(x,y) in asm.ex, is =
an example.

> Asm.e also assembles directly to memory, which should be an option for =

> the compiler to.  Generating functions at run-time is always nice.

Agreed. Now to your next posting:
=20
> Here are some more ideas I had on what to implement first in a simple=20
> compiler:
>=20
>   Functions and Procedures.=20
=20
I guess you are right. One thing I would like to maintain is that the =
code should fit well into the code cache (I think it's like 4, 8 or =
16Kb). Simply in-lining all 'calls'would quickly result in too much =
code. So subs are necessary.

> Parameters are passed on the stack, using=20
> push instructions.  Space for local variables is created by moving the =

> stack pointer.  Parameters and local variables are accessed by reading =

> memory at the stack pointer + an offset.  Recursion should be allowed =
-=20
> that's why we have a stack. =20
=20
But what happens if a program runs out of stack memory at run-time?

> Function results should be returned in the=20
> eax register.  No registers need to be saved before calling =
subroutines,=20
> but a subroutine may modify any register except the stack pointer. =20
> (Ideas for later implementation: allow complex calling conventions =
like=20
> passing parameters in registers, store local variables in registers,=20
> etc)

You see, I think it might be possible to do without the stacked =
parameters for calls that are internal to the code currently being =
compiled. Parameters would not be necessary if the compiler would knows =
where it has all its data at any given time. For example, if a variable =
FOO is currently in either a register or memory position, lets call it =
R/M_X, it would be a waste to move it to EAX and then make the call. One =
could just call the procedure right away, and the compiler would know =
that FOO is currently at R/M_X (say, it could be in EBP, or [EBP] or =
[FOO_PTR]). I will write more about this below.
=20
>   Global Variables.  Global variables are simply a pointer to =
someplace=20
> allocated on the heap.  (Variables can be optimized to be stored as=20
> registers later.)

Actually, I first imagined everything to be global... :)

>   Data Types.  Let's stick with 32-bit integers for now.  (We can add=20
> floating point and arrays later.)  (We could also probably implement=20
> arrays just using peek/poke.)

Yes, let's wait with the floats. But simple arrays, with max 2 =
dimensions and only power-of-2 width could more easily be implemented at =
an early stage.
=20
> Simple Assignment and Arithmetic.  Assignments will be initially=20
> limited to "x =3D y" where y is another variable or a literal value. =20
> Arithmetic can only be done on existing variables, in the form "x +=3D =
y".=20
>(We can add more arithmetic operations later.)

Concurred. For x86 this would sure make sense. I just thought that since =
Eu was available for both Linux and BSD that maybe it also currently ran =
on other computers. But Bernie says that Rob Craig is 'hand coding' some =
of his routines, does this mean Eu runs only on x86?
=20
> If and While statements.  Each statement may have only one=20
> comparison.  Comparisons can have the form "x < y" where x or y may be =

> a variable or a literal value.  (For loops can be implemented using=20
> while loops.  From what I've heard, the first versions of Euphoria=20
> didn't have for loops for that reason.)

For some time I thought GOTO would be easier to compile, but I guess =
WHILE is actually easier to deal with. IF and WHILE is sufficient for my =
needs.

> Now, for the intermediate representation, a tree structure would=20
> probably be appropriate.  The parser would take the text =
representation=20
> of the program (the source code) and convert it to an intermediate=20
> representation.  This intermediate representation is where the=20
> optimization would take place, but we'll leave that out for now.  Then =

> the code generation would use the optimized intermediate =
representation=20
> to create the actual machine code.

Ok, Pete. What you are describing (I snipped away the rest) is a very =
direct, and simple approach. It would compile in no time, it would run =
quite fast (at least much faster than Euphoria) and it basically solves =
my original request. Moreover, it looks easy to debug, so there is =
reason to believe it would quickly get stable. Even though I'd like to =
attempt a more complex solution later, I think it would be a good idea =
to complete this compiler first, and see what kind of problems we =
encounter.

> Comments?  Suggestions?  Clarifications?
>=20
> Or "shut up man and start coding"?  grin
>=20
> Pete

Sure, go ahead, but give me/us a chance to help! Maybe the job could be =
cut up into pieces somehow, so we can exploit the principle of =
parallelism? Anyhow, my humble programming services are at your command =
:)




Finally I'd like to give a general outline of my plans for a compiler =
based on the a-star algorithm. I hope to be able to write a much better =
and more detailed description later.=20

The compiler could be compared to a chess engine. The compiler generates =
lists of compiled statements, a chess engine lists of chess moves. Both =
programs will not only relate to one list, but to huge trees of lists =
branching out from a root.

A chess engine cannot make an illegal move (unless it's buggy). =
Likewise, the compiler,  is unable to produce a statement or list of =
statements that could result in an error. It would always create a =
program that correctly would execute the source code.

A chess engine must know 'everything' relevant to the game, including =
such things as which rooks has moved, so as to play by the correct =
castling rules. But it cannot limit itself to perfect knowledge about =
the current situation on the board. In order to think ahead, it must =
search as far as it can, through a huge branching tree, in which it must =
have the same perfect knowledge about every possible node. Else, it =
couldn't plan it's moves correctly.

The compiler also prowls through a search tree. and must know =
'everything' about each node on that tree, that is, about as much as a =
human programmer would. Perhaps the most important information the =
compiler has is WHERE the different variables are located (is 'foo' in =
memory or in one of the registers?). Mostly, it will not be aware of the =
values in these variables, but sometimes it will, and then it could =
exploit it. It's the same with flags, they are either known as 'set', =
'cleared' or more usually 'undefined'. =20

One useful way to exploit knowledge of contents, is when at some point =
you need to compile something like Frodo =3D 0. Before setting out to =
free up a register and zero it to hold this value, the compiler could =
first see whether it already had a unused register with a value known to =
be zero. That's not unthinkable, maybe a loop counter has recently ended =
up with that value. Now the compiler could simply use that register =
right away, without any code.

Still,  the most important thing about the compiler is it's ability to =
'juggle' registers and variables in memory, so as to minimalize the need =
for constant swapping out of registers.=20

Basically, the compiler could be described in terms of 4 concepts.

 1. A code generator.
 2. A cost evaluator.
 3. A priority queue.
 4. A heuristic estimation.

1. The code generator has the task of producing  a correct piece of =
assembly code that will do what a single source statement expects. How =
this piece of code will look like depends on many factors, all of which =
can be deduced from the list of code prior to this statement. If the =
statement was foo -=3D bar, then the code would have to take into =
account the whereabouts of these two variables. If 'bar' is in memory =
and 'foo' happens to be in ecx, then one correct piece of code could be: =
add ecx, [bar_ptr].=20

There may of course be many other ways to accomplish the same thing. The =
value of 'bar' could for example be loaded into another register, (the =
contents of which would then have to be written out to memory), and =
thereafter the two regs could be added. So far, this could seem like a =
less optimal solution, simply wasting some clocks, doing approximately =
the same thing.

But it may turn out that the most expensive version of the statement =
later will turn out to be the best. It's like in chess: sometimes you =
can sacrifice a knight or even a queen, and find that this move can be =
made to improve your situation several moves later.

The code generator should therefore not worry about how much each =
statement costs, just generate the set of correct ways to resolve a =
statement at a given point in the body of the code.


2. The cost evaluator sums up the 'cost' of the generated assembly =
statements. Cost would be measured out in clocks. The execution cost of  =
an XOR REG, REG might be 2 clocks. In addition comes instruction =
fetching and decoding. It must be possible to look up the correct (more =
or less) cost values for most instruction and instruction combinations =
by fine-reading appropriate literature. Certain things would still be =
unpredictable of course, so the average time a processor will spend down =
a pipe after a mispredicted jump must simply be guesstimated (one must =
still attempt to figure out reasonable penalties for this).

The compiler would provide the best results when these costs are as =
close to reality as possible. In chess too, it is important to hint the =
engine in the right direction (the best moves) by giving the 'best' =
values to the different pieces. Often these are: 1 for pawn, 3 for =
knight, 3.25 for bishop, 5 for a rook, 9 or 10 for a queen and 'inf' for =
the king. One can play around with these values of course, and see if =
the engine would play better chess if the rook was worth 8 points =
instead. It probably would play worse.


3. The priority queue has the mission of always knowing which node among =
the compilers lists of programs is the 'best'. That is, the one with the =
least clock-cost in relation to how many statements it has completed. =
This is as simple as 'keeping the minimum'. A data structure known as a =
'heap' is often used for this, but there may be other alternatives that =
are better for this application. I'd expect that optimizing the priority =
queue means optimizing the compiler, since it's here most of the =
compile-time will be spent.


4. At any point in the developing of the assembly code, a 'heuristic' is =
produced that attempts to guess how 'good' the current node is in =
comparison to all other possible nodes. This guess is the current cost =
for the node in the tree (which is a hard fact) + a negative estimate of =
how much is left before the final source statement is reached. The =
latter estimate can be multiplied with a floating point factor to make =
the engine search either in 'breadth', meaning more brute force, or =
'depth', meaning 'take some chances, advance quickly towards the goal'.

When this heuristic factor is set to 1, a perfectly optimized* =
compilation would be the result, but the engine might spend quite some =
time, even on small programs (compilation time would increase =
exponentially with the number of statements in the program). As the =
heuristic factor is incremented, the resulting code will be less =
optimized, but compilation time would be drastically reduced.=20

The beauty of a-star is that one can always diddle this number to get a =
search time which balances one's needs. Just increment the number to =
trade in run-time efficiency against compile-time!

* Perfect optimization means that, given only the statement building =
blocks that the code generator can produce, and given that the clock =
estimates for all these code snippets are correct, it would be =
impossible to compile the program to more effective assembly. No =
kidding, and before you burst out in protest, please make sure you =
understood the two premises in that sentence... :)




Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

3. Re: Inner loop compiler

RForno,

> Of course, the compiler generates assembly or machine code. But to
> write such a compiler, you should know assembly coding, maybe much
> better than if you were trying to write the routines by hand.

Absolutely, I 'should' be an expert assembly coder. :)

> Regarding the examples you gave, I think that only an extremely
> powerful optimizing compiler could perform such a kind of analysis.
> To the best of my knowledge, C/C++ compilers in existence aren't=20
> as efficient as this. So, it  seems that the task in front of us is
> a very demanding one.

I realize I'm very ambitious here. My original inspiration was that even =
a very naive and simple-minded compiler can generate code fast enough to =
outclass Euphoria's interpreted instructions, because of such things as =
more efficient code and data caching, better access to bit manipulation, =
less overhead and so on. Highly optimzed compiled code is not really =
necessary to make the project interesting.

> Moreover, with the later processors (486, Pentium), there is no
> timing difference for many instruction pairs, like ADD - INC, so
> that you get the same timing assuming a non-optimizing C compiler
> translates i +=3D 1 to ADD i,1 and i++ to INC i;=20

Basically you are right. I had misread an html file concerning not only
pairing but also agi stalls. However, pairing and agi stalls should be
considered when dealing with early Pentiums with or without MMX. This
problem seems to be removed in Pentium Pro, II and III.

> and the compiler should take into account whether the
> program is to be run on an 80386 or a Pentium, for example (remember
> that many Euphoria users, like Igor, still use a 386). So,=20

I agree. I guess a lot of people around the world are using computers =
from throughout the 90s. Developing countires has of course a large park =
of 386+ machines, but in industrialized countries too, including USA and =
UK, large portions of the populations are poor and use older cpu's.

It ought to be a matter of decency and politeness to have this in mind =
when developing general purpose software. 386 is still a good lower =
basis, since it's 32 bit, can run Linux etc.

> So, I think the job is really a big one, maybe an impossible one.=20
> Well, "impossible" is maybe too much, but you know how things=20
> are...smile

Writing a naive compiler ought to be a question of some hard work, time =
and determination. Writing a "good compiler" for a limited programming =
language seems, as I see it right now, to be within reach. I hope to =
provide some concrete code examples of what I mean later, but it will =
definately take a lot of time and pondering.


Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

4. Re: Inner loop compiler

Barbarella:
Perhaps you should emphasize the "may" in "may be impossible". It also "may
be possible".
I didn't really try to discourage you.
What I was thinking is that your proposal means too much effort for only an
addition to Euphoria. It seems that what you propose should be, in its own
right, a full new compiler.
As an anecdote, I recall that some years ago I programmed a sort (in
Commodore Basic) that I thought was performing an impossible task: merge in
place. I was convinced it did it, and in fact it sorted data, but its rate
of growth for the timing was steeper than O(n log (n)). I sent it to Donald
Knuth, who never answered. About a month ago, I revised the code, and found
that in fact the task was impossible: it was sorting inside the sort,
instead of merging!
----- Original Message -----
From: <OthelloVivaldi at hotmail.com>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, September 11, 2002 7:58 AM
Subject: SV: Inner loop compiler



> > From: Pete E [mailto:xseal at harborside.com]
>
> > The thing I haven't figured out how to do yet is convert the nested
> > expression into a flat instruction sequence.  Some temporary storage
> > will always be required.
>
> <SNIP>
> > A smarter compiler might try to use a second register, but
> > what happens
> > when you run out of registers for a complex expression...  the stack
> > will have to used somehow.  Maybe some temporary variables can be
> > inserted by the parser when it sees a complicated
> > expression... and let
> > the optimizer substitute registers for the temp variables.

> Matthew Lewis wrote:
> You will probably rarely need very many registers/temp vars.
> I'm not sure there's any easy way to compute the exact number
> you'd need for any expression, but here's a way to bound the
> problem as far as you'll probably need:
> <Big snip>

Maybe it would be possible to have the parser break arbitrarily complex
expressions down to simple intermediate statements and then let the compiler
deal with the register juggling? For example, an expression such as:

    x = (t > i * 2) + (3 / i) - (7 + n) * (j - 1)

could be broken down to the intermediate statements:

    x = i
    x *= 2
    x = t > x -- simple comparison that the compiler can understand
    temp1 = 3
    temp1 /= i
    x += temp1
    temp1 = 7
    temp1 += n
    temp2 = j
    temp2 -= 1
    temp1 *= temp2
    x -= temp1

and the rest could be left to the compiler. The parser could define however
many temporary vars it needed. Of course, the compiler would have to be
capable of taking it from there, using the minimum number of regs to
accomplish the task. But this, I believe, could be solved with a generic
compiler solution rather than a routine relying on explicitly named
registers.


By the way, I think I may have found one reason why not everyone are already
using A* or similar state searching techniques for compiling.

The A* method rely on the compilers ability to exploit knowledge about what
it has just done in the previous compiled statements.

E.g. if the compiler has just put 'Merry' into edx...

    mov edx, Merry      ; Compiled result of...
    add edx, 3          ; ...Merry += 3

then, in the consequtive lines it will know that Merry is still in edx,
right? So if the next source statement says "swap Merry, Pippin", and Pippin
happend to be in a register too, say ebx, then the compiler could simply
swap it's own references, without actually producing any assembly.


                       ; compiled result of "swap Perry, Pippin"
                       ; (i.e. nothing)

Later, perhaps after some operations on these variables, when the time came
to move the vars back out to memory, they would simply end up in each
other's previous memory positions.

    mov [Merry_ptr], ebx    ; used to be Pippin's place
    mov [Pippin_ptr], edx   ; used to be Merry's place

This does not quite work inside if-blocks. Since the compiler would
(generally) not have any idea whether or not the if-jump is taken.
Everything that the statments inside the if-block COULD have affected must
be labeled 'undefined'. A true swap of some kind must therefore be performed
inside an if block.

    test God_exists, 0  ; if God_exists then
    jz not_true         ;
    xor Merry, Pippin   ;    swap Pippin, Merry
    xor Pippin, Merry   ;    (Of course, there may be faster ways
    xor Merry, Pippin   ;     than using the 3 xors...)
    not_true:           ; end if

    mov [Merry_ptr], edx   ; This time, the compiler has not
    mov [Pippin_ptr], ebx  ; changed any of it's references.


Fair enough, I can live with this. If-blocks can easily *) be dealt with
because they jump forward in the list of statements. Loops are a different
matter all together...

*) Defintion of 'easy': "much less difficult than *extremely* difficult".

Loops break with the linear chain of dependencies that my initial ideas were
based on. Here is an example, using do...while for clarity:

1    mov ecx, 300    ;    counter = 300
2    label:          ;    do
3    dec ecx         ;        counter -= 1
4    jnz label       ;    while counter != 0

at line 2, the compiler would normally think it knew the value of ecx
exactly. At line 3, it would note that the value is now 299... :)

I bet you get the point. Simply put, line 4 is like like an if-statement
that jumps backwards, so the compilers assumtions that ecx = 300 or 299 are
unreliable. In general, anything modified inside the loop should be assumed
to be 'undefined' by the compiler, just as if it was inside an if-block.

That's easier said than done. Because the linear model of A* compilation is
based on knowing what, at any point, is defined and what is not defined, the
compiler would first have to know how the loop will eventually look like,
and to know this, it must first compile that very same loop...

RFornos inauspicious predictions keeps echoing in my head "It may be
impossible, ... may be impossible, ... may be impossible, ... " :)

This is no reason to give up, though. One must just THINK for a while...

Hmmmmm...


Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

5. Inner loop compiler

A long time ago, Barbarella wrote, "I have practically no experience with
assembly or compilers, but I 
thought writing a compiler might give me some experience."

I'd like to suggest that, at least to start to get a handle on compilers,
that you look at Jack Crenshaw's tutorials called "Let's Build a Compiler."
The original had code in Turbo Pascal (!), but I believe someone translated
the Pascal to C. The tutorial, while it is somewhat incomplete in that it
does not go into strings and the like, is excellent for learning how a
compiler compiles. The files are on Simtel.net (www.simtel.net). Just do a
search for "Crenshaw", and it will come right up.

Also, take a look at his articles in Embedded Systems Programming Magazine
(www.embedded.com). Go into the archives for 1998. The articles are found in
the issues from May through December.

--Rich


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.386 / Virus Database: 218 - Release Date: 9/9/02

new topic     » goto parent     » topic index » view message » categorize

6. Re: Inner loop compiler

Rich,

> I'd like to suggest that, at least to start to get a handle on=20
> compilers, that you look at Jack Crenshaw's tutorials called=20
> "Let's Build a Compiler."=20

That's the spirit! :)

> The original had code in Turbo Pascal (!), but I believe=20
> someone translated the Pascal to C. The tutorial, while it is=20
> somewhat incomplete in that it does not go into strings and the
> like, is excellent for learning how a compiler compiles. The files
> are on Simtel.net (www.simtel.net). Just do a search for "Crenshaw",
> and it will come right up.
> Also, take a look at his articles in Embedded Systems=20
> Programming Magazine (www.embedded.com). Go into the archives for
> 1998. The articles are found in the issues from May through=20
> December.

Thanks for the link! I will certainly check out that tutorial. I read =
Jack's article and found it well written and very entertaining.=20


Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

7. Re: Inner loop compiler

Rforno,

> Perhaps you should emphasize the "may" in "may be impossible".=20
> It also "may  be possible". I didn't really try to discourage you.

I understood that. :)

> What I was thinking is that your proposal means too much effort for
> only an addition to Euphoria. It seems that what you propose should
> be, in its own right, a full new compiler.

That would be nice, but then it would need tons of code for I/O, =
interfacing with OS and memory managers, etc. And I would have to worry =
about things like garbage collecting if I wanted that, to mention just =
one thing. It would amount to years of hard work!

> As an anecdote, I recall that some years ago I programmed a sort=20
> (in Commodore Basic) that I thought was performing an impossible
> task: merge in place. I was convinced it did it, and in fact it
> sorted data, but its rate of growth for the timing was steeper than
> O(n log (n)). I sent it to Donald Knuth, who never answered. About
> a month ago, I revised the code, and found that in fact the task
> was impossible: it was sorting inside the sort, instead of merging!

Forgive my utter obtuseness, I didn't quite grok that. What does it mean =
to "merge in place"? And what do you mean with "sorting inside the =
sort"?=20



Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

8. Re: Inner loop compiler

Bernie,

> Why are you all trying to reinvent the wheel and missing
> the point of the real challange.
=20
Oh, writing a compiler is to me a challenge.

> I think that it would be a better idea to use the many
> assemblers/compilers out there that are fully able to do a good
> job of optimising code, to generate a object module.=20

Which compiler do you suggest?
=20
> Then the challange is to find a easy way to embed or
> interface that object code into Euphoria.

Well, that is a good idea, but one thing does not exclude the other. You =
sound like an experienced programmer, why not pick up the glove and give =
it a try yourself?


Yours Sincerely,
Barbarella

new topic     » goto parent     » topic index » view message » categorize

9. Re: Inner loop compiler

{{{ Anyone involved in this should read a few "interesting" papers &/or investigate around a bit.

Maybe I should just bite my tongue, but here is one *entirely* irrelevant paper probably (Icon, my 2nd fav lang):

http://citeseer.nj.nec.com/proebsting97simple.html

You should definitely at least know about this one:

http://citeseer.nj.nec.com/franz94technological.html

with plenty background on that matter at:

http://citeseer.nj.nec.com/50197.html

Not at all what you had in mind, I guessblink

Pete PS click somewhere/anywhere top right to view the paper in a format your PC can read.

new topic     » goto parent     » topic index » view message » categorize

10. Inner loop compiler

This is a multi-part message in MIME format.

------=_NextPart_000_0059_01C2515B.BDBAB980
	charset="iso-8859-1"


Hi, Everybody!

Are anyone here interested in looking into the possibilities
of a minimalist, compiled machine oriented language to be used
with Euphoria?=20

I would like the language to generate small routines that could
interface with Euphoria and speed up the inner loops of programs.
I would prefer to give safety, speed and simple design priority.=20

I've attached a zipped text file that describes my ideas in a
little bit more detail. Please remember it's just unclear=20
thoughts so far, much have yet to be worked out.

It would extremely nice to hear your opinion!


Yours Sincerely,
Barbarella




------=_NextPart_000_0059_01C2515B.BDBAB980
Content-Type: application/x-compressed;
	name="compiler.zip"

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu