Hi,
While you're enumerating these possibilities, I think it's worthwhile to
mention a technique related to the FORTH implementation technique: Marc
Feeley style compilation (see "Using Closures For Code Generation" in
Computer Language Vol 12 No 1 pages 47-66). This idea is also mentioned in
SICP.
-Arthur
==============================================================
Arthur Nunes-Harwitt
Computer Science Department, Rochester Institute of Technology
Room GOL-3509
585-475-4916
==============================================================
"I don't know what the language of the future will be
called, but it will look like LISP."
This email is confidential and intended for the named recipient(s). In
the event the email is received by someone other than the recipient,
please notify the sender at a...@cs.rit.edu.
On Wed, 29 Jul 2020, Hendrik Boom wrote:
On Wed, Jul 29, 2020 at 01:56:05AM -0700, zeRusski wrote:
This is a really cool piece of history! Thank you.
I'll admit I'm somewhat fuzzy here - it maybe a bit too meta for me or
perhaps I don't quite understand what you're trying to say. Isn't
interpreting n levels deep also linear in n?
Answer 1.
Let's say, for example, that it takes 10 instructions executed in an
interpreter to decode, take decisions, and execute an interpreted
instruction. (In real life this varies a lot between interpreters and
between interpreted instructions but let's keep the example simple.)
(and, also to keep things simple, let's say the interpreter in
interpreting the machine language of the machne it's running on --
not an unusual technique in a debugger.)
Then interpreting a program using an interpreter running on hardware
would take ten times as long as executing the program on the same
hardware.
And likewise, interpreting the program in an interpreter being
interpreted by the interpeter running on the hardware would take another
ten times as lng as just interpreting the program with an interpreter
running on the hardware.
Thus 10 x 10, times as slow; this is where the exponential comes in.
Only difference between the
two approaches I see is that compiler lets you persist the fruits of its
labor so you don't have to start from scratch every time. Couldn't you
accommodate this with an interpreter (with some effort) although at this
point it becomes a compiler I suppose. Definitely fuzzy here.
That is exactly the difference between a compiler and an interpreter.
Answer 2:
Time to muddy the situation.
There are mixed-style language implementations.
If you only execute each piece of code once, interpreters tend to be
faster. But if you are to execute code many times, it's faster to
compile. It takes time to compile, but you get it back by saving time
in later executions.
So what thee mixed implementations to is to interpret the code, but
keeping track how often each piece of code (such as a function) is
called.
When the count reaches a particular threshold, it pauses interpretation
and compiles that code, the compiled code to be used thereafter.
There is some time penalty over compilation, because you waste time
interpreting functions several times before you compile them.
This is offset by not having to compile code that is used only a few
times.
The time behaviour of this kind of system overall is more like a
compiler than an interpreter because the code that is executed the most
does eventually get compiled and the rest gets interpeted only a limited
number of
times.
However, if it were to execute a copy of its own code, it would have to
recompile it, unless it had a mechanism to check if the newly input
program is the same as one it has already compiled. This isn't
impossible, but is not usually done.
But when going n levels deep, the total execution time with a compiler
is linear in n, and with an interpreter it's exponential.
I use this criterion to tell whether a particular implementation is more
like an interpreter or a compiler.
That makes interpreting interpreters impractical when n gets large (even
with n around 3 or 4); whereas compiling compilers can be done even for
larger n.
Answer 3.
On modern machines, it is also important to keep memory demands low.
Accessing large amounts of memory regularly tends to push other data our
of cache, or even out of RAM onto disk.
Conserving storage is a common reason for using interpreted bytecode as
the target language for a compiler. The bytecode is usually smaller
than the machine language. If the bytecode interpreter is small enough,
this is a definite win. Bytecode was first used, as far as I know, on
machines with small memories -- about 64K RAM total or even less.
Byte-code can also be portable. You just need to write a (usually
amall) bytecode interpreter for each new machine.
Of course it's still possible to, at run-time, compile the most-used
byte-coded functions in to actual machine code to trade memory use for
execution time.
Answer 4: An example:
The language FORTH used a *word*-code interpreter instead of a
byte-code interpreter, each word being two bytes, and containing the
address of the interpreter's machine-code routine that implemented that
instruction.
This meant each word representing an instruction could be
executed in the interpreter by a hardware function call to an
indirect address. In fact, user-coded functions could be called the
same way -- each would be a sequence of addresses preceded by the
machine code that invokes the word-code interpreter.
Still very compact on a machine with two-byte addresses.
Utterly impractical on a modern machine with 64-bit addresses, where the
machine code for an operation can often be smaller than a machine
address.
-- hendrik
I hope this set of answers clarifies the distinction between an
interpeter and compiler, how the distinction gets blurred in practice,
and what the criteria are for choosng between them.
-- hendrik
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/2f288d86-d90c-4881-b001-389b580fece8o%40googlegroups.com.
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/20200729154310.dol2c2ks3d6kome6%40topoi.pooq.com.
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/alpine.DEB.2.21.2007301040200.12855%40kakita.
