None of the books I have read explain this and I know very little about
it (I have only run programs at the REPL).
My question is: how can machine code be compiled from a lisp code if
all lisp programs use garbage collection? Isn't a virtual
machine/interpreter needed for that?
·········@gmail.com wrote:
> None of the books I have read explain this and I know very little about
> it (I have only run programs at the REPL).
>
> My question is: how can machine code be compiled from a lisp code if
> all lisp programs use garbage collection? Isn't a virtual
> machine/interpreter needed for that?
Or, more generally, how can machine language, with its supreme power
over nearly the entire state of the data processor, be used to
represent high-level language programs which are supposed to be secure,
robust against run-time errors such as array overruns and type
mismatches, and have accurate resource management?
The answer is that the compiler does not produce arbitrary machine
code, but machine code which sticks to certain rules regarding the
representation of values and preserving their integrity. (A mature
language implementation lets you locally relax those rules to obtain
efficiency).
You could use garbage collection in direct, raw, assembly language
programming if you write a suitable run-time support, and meticulously
stick to the rules. For instance, you would design a type-tagged
representation and use it for every single piece of data manipulated by
your machine language program. You would store values that are pointers
only in locations known to the garbage collector, and never stash them
in hidden locations and resurrect them later. And you would never
clobber the type field of an object or otherwise manipulate it to make
the garbage collector malfunction. You would also obey calling
conventions so that the stack of a suspended thread could be
comprehended accurately.
With all these types of rules in place, the garbage collector can run
over suspended threads, and scan their stacks and registers for root
references to objects, in addition to scanning global areas. The
garbage collector knows about the representation of everything and so
can determine what is reachable, and recycle the rest.
Nopw about that other question from the subject line: how can it be
both compiled or interpreted? Actually, there can be more choices. A
Lisp implementation could have an intepreter that basically works with
the source code or something close to it, a virtual machine for byte
code, and a native compiler. These are all just different
representations of the program, and all are possible in the same image.
This is just basic abstraction. As long as all the pieces obey certain
rules about how they interact with the environment, they can all play
along. It's all just machine code in the end. If a function is being
interpreted, what is going on? An interpreter written in machine code
is scanning some data, and turning it into actions, which are just
execution pathways through that interpreter's machine code body. A
compiler takes pieces which resemble those pathways and glues them to
make a program. It's all the same.
in message <························@i40g2000cwc.googlegroups.com>, Kaz
Kylheku (·········@gmail.com') wrote:
> With all these types of rules in place, the garbage collector can run
> over suspended threads, and scan their stacks and registers for root
> references to objects, in addition to scanning global areas. The
> garbage collector knows about the representation of everything and so
> can determine what is reachable, and recycle the rest.
Or, if you use reference counting, you don't even need a garbage
collector at all, and you don't have to periodically suspend threads to
clean them. Yes, I know all the classic objections to reference
counting, but I still see it as a good solution in some problem spaces.
--
·····@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; Usenet: like distance learning without the learning.
From: Ken Tilton
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <bQ%Rf.11$B47.6@fe11.lga>
·········@gmail.com wrote:
> None of the books I have read explain this and I know very little about
> it (I have only run programs at the REPL).
It cannot. Your Lisp vendor can provide /both/ a compiler and
interpreter, but it might just provide a compiler. If so, the REPL only
seems to be an interpreter; it is compiling sneakily to binary and then
answering without you knowing it is running native compiled code (or
bytecode in the case of Clisp).
>
> My question is: how can machine code be compiled from a lisp code if
> all lisp programs use garbage collection? Isn't a virtual
> machine/interpreter needed for that?
In short, no, GC has nothing to do with virtual machines. You could have
a VM that did not do GC, and you can have GC without a VM. really
completely unrelated concepts.
kt
--
Cells: http://common-lisp.net/project/cells/
"And I will know my song well before I start singing." - Bob Dylan
From: Rainer Joswig
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <C03E4D46.30FD7%joswig@lisp.de>
Am 15.03.2006 22:28 Uhr schrieb ··········@gmail.com" unter
<·········@gmail.com> in
························@i39g2000cwa.googlegroups.com:
> None of the books I have read explain this and I know very little about
> it (I have only run programs at the REPL).
Typically any Lisp system provides some kind of runtime support.
One thing that the runtime support usually provides is garbage
collection. Most (almost all) Lisp systems are providing
garbage collection (plus maybe other facilities for memory
management). For many Lisp systems the runtime support also
contains the functionality that is built into Common Lisp.
For example a compiler. Or I/O. Or routines for handling
bignums.
If you have a Lisp program like:
(defun foo (n)
(make-array n))
You can compile it:
(compile 'foo)
And you can look at the generated code:
(disassemble 'foo)
If you allocate memory in your compiled code, the memory management
routines will be called. That's all. That's not much different from
a C program, where you also allocate memory and some subsystem
takes care. But you also have to deallocate memory via this subsystem.
Where the Garbage Collection would detect that it either should
do a little work sometimes (say, routinely triggered by some timer)
or does free memory when it is needed.
> My question is: how can machine code be compiled from a lisp code if
> all lisp programs use garbage collection? Isn't a virtual
> machine/interpreter needed for that?
No, just some runtime support that typically is provided with the Lisp
system.
From: Edi Weitz
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <uacbrfjei.fsf@agharta.de>
On 15 Mar 2006 13:28:58 -0800, ·········@gmail.com wrote:
> My question is: how can machine code be compiled from a lisp code if
> all lisp programs use garbage collection? Isn't a virtual
> machine/interpreter needed for that?
There are also garbage collectors for C, and C doesn't have a virtual
machine either: <http://www.hpl.hp.co.uk/personal/Hans_Boehm/gc/>.
Actually, there's at least one Common Lisp implementation (ECL) which
compiles to C code (which is then compiled to machine code) and uses
the garbage collector mentioned above.
As others have already said - you'll usually have a runtime support
library, but that's not a virtual machine.
--
European Common Lisp Meeting 2006: <http://weitz.de/eclm2006/>
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Pascal Costanza
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <47rocmFh7291U1@individual.net>
Edi Weitz wrote:
> On 15 Mar 2006 13:28:58 -0800, ·········@gmail.com wrote:
>
>>My question is: how can machine code be compiled from a lisp code if
>>all lisp programs use garbage collection? Isn't a virtual
>>machine/interpreter needed for that?
>
> There are also garbage collectors for C, and C doesn't have a virtual
> machine either: <http://www.hpl.hp.co.uk/personal/Hans_Boehm/gc/>.
> Actually, there's at least one Common Lisp implementation (ECL) which
> compiles to C code (which is then compiled to machine code) and uses
> the garbage collector mentioned above.
There is a sense in which languages / language implementations that
support garbage collection can be considered to be interpreted.
I recall discussions of about 10 years ago with people who consider code
only compiled when the actual structures that are expressed in a program
are not (necessarily) recognizable anymore in the compiled code. For
example, if you strip away type tags from compiled code, you cannot
determine its type anymore at runtime - hopefully, the compiler got the
static type checks right, so such tagless values will automagically only
be stored in the correct variables, and thus also automagically only the
"correct" operations can ever be executed on such values.
If you add type tags to runtime values, and use those type tags to
determine what operations are or are not acceptable, this is, in a
sense, a kind of interpretation. Like in an interpreter which performs
operations based on runtime values that represent commands, type tags
are checked and operations are selected (especially in OOP systems!)
based on such type tags.
Languages / language implementations that support garbage collection
typically provide the garbage collector with useful information about
the types that are stored in the various structures / classes / objects
/ whatever. This allows a garbage collector to know exactly what data
must be considered as pointers to be followed and what data must be
considered to be plain data / primitive types. In a language / language
implementation that doesn't support garbage collection, collectors have
to be a lot more conservative and have to consider all kinds of data to
be pointers, including those that are actually not used as pointers at
all. The checks that exact garbage collectors perform to determine the
pointer locations in memory can be considered as interpretative operations.
If you buy into that view that performing (essentially) type checks at
runtime should be considered to be interpretative, then a good way to
describe typical Common Lisp implementations is by saying that they are
a implementation by hybrid interpreter/compiler architecture. Which, by
the way, is true of most mature languages nowadays.
Pascal
--
3rd European Lisp Workshop
July 3-4 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
Pascal Costanza wrote:
> Edi Weitz wrote:
> > On 15 Mar 2006 13:28:58 -0800, ·········@gmail.com wrote:
> >
> >>My question is: how can machine code be compiled from a lisp code if
> >>all lisp programs use garbage collection? Isn't a virtual
> >>machine/interpreter needed for that?
> >
> > There are also garbage collectors for C, and C doesn't have a virtual
> > machine either: <http://www.hpl.hp.co.uk/personal/Hans_Boehm/gc/>.
> > Actually, there's at least one Common Lisp implementation (ECL) which
> > compiles to C code (which is then compiled to machine code) and uses
> > the garbage collector mentioned above.
>
> There is a sense in which languages / language implementations that
> support garbage collection can be considered to be interpreted.
All software is interpreted. Whenever a program's meaning lies entirely
in that program, and not in the processor, the evolving process by
which the meaning is liberated is interpretation. Fetching, decoding
and executing an instruction is interpretation.
A program that is largely driven by data is not any "more" interpreted
than one that is driven by data to a smaller extent. What matters is
that it's the program itself which is interpreting the data, rather
than that program's interpreter. E.g. if you have type tags and are
dispatching on them or whatever, it's that program which is doing the
dispatching. The tags are interpreted by that program, not by the
mechanism which interprets that program.
If I write a table-driven parser in C, that parser is compiled code.
The table built into it is a program which is interpreted by that
parser. The parser itself is hardware-interpreted, and its table is
software-interpreted.
Compilation is the name given to changing the representation from one
kind of interpreted language to another, and interpretation is how we
get it running. The two aren't opposites, but we use them that way,
because we use sometimes use compilation as a synonym for "execution of
a program by changing it to a representation that can be
hardware-interpreted" and we mean "software-interpreted" when we just
say "interpreted".
> I recall discussions of about 10 years ago with people who consider code
> only compiled when the actual structures that are expressed in a program
> are not (necessarily) recognizable anymore in the compiled code. For
That is never the case. If you look hard enough, you can recognize
everything.
in message <························@i39g2000cwa.googlegroups.com>, Kaz
Kylheku (·········@gmail.com') wrote:
> A program that is largely driven by data is not any "more" interpreted
> than one that is driven by data to a smaller extent. What matters is
> that it's the program itself which is interpreting the data, rather
> than that program's interpreter. E.g. if you have type tags and are
> dispatching on them or whatever, it's that program which is doing the
> dispatching. The tags are interpreted by that program, not by the
> mechanism which interprets that program.
Remember that the program itself is data; and that the interpreter, at
whatever level, is data-driven.
--
·····@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; 'I think we should trust our president in every decision
;; that he makes and we should just support that'
;; Britney Spears of George W Bush, CNN 04:09:03
From: Rainer Joswig
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <C03E72FB.31013%joswig@lisp.de>
Am 16.03.2006 1:04 Uhr schrieb "Pascal Costanza" unter <··@p-cos.net> in
··············@individual.net:
> If you buy into that view that performing (essentially) type checks at
> runtime should be considered to be interpretative,
I'd say interpreting a (interned) source representation of a program
and doing runtime checks (type checks, type dispatches, size checks, ...)
is something very different. If I have a Pascal ;-) program that at runtime
checks some array size, it isn't interpreted because of that.
That Lisp (compiled programs and its data) doesn't map exactly to
stock hardware and needs some additional operations doesn't make
it 'interpreted'. That at some point some machinery
(the processor or the virtual machine) has to look
at the instructions and execute them is another topic.
The computer next to me even has a processor which does all
that in hardware ( http://www.rcsri.org/rcs/Symbolics/ivory/ivory.html ).
> then a good way to
> describe typical Common Lisp implementations is by saying that they are
> a implementation by hybrid interpreter/compiler architecture. Which, by
> the way, is true of most mature languages nowadays.
Not really...
From: Pascal Bourguignon
Subject: Re: Question: How can Lisp be both compiled and interpreted? does it use a virtual machine?
Date:
Message-ID: <8764mff66o.fsf@thalassa.informatimago.com>
Rainer Joswig <······@lisp.de> writes:
> Am 16.03.2006 1:04 Uhr schrieb "Pascal Costanza" unter <··@p-cos.net> in
> ··············@individual.net:
>
>> If you buy into that view that performing (essentially) type checks at
>> runtime should be considered to be interpretative,
>
> I'd say interpreting a (interned) source representation of a program
> and doing runtime checks (type checks, type dispatches, size checks, ...)
> is something very different. If I have a Pascal ;-) program that at runtime
> checks some array size, it isn't interpreted because of that.
Not so fast. The microprocessors themselves do some type or range
checking and trap out when there's an invalid value. It's proof the
binary not a compiled representation of the program, but is still
interpreted by the processor. It's even more true when you consider
that most microprocessors actually really interpret the binary code,
with a microcoded microprogram inside the processor. It's turtles^W
interpreters all the way down!
> That Lisp (compiled programs and its data) doesn't map exactly to
> stock hardware and needs some additional operations doesn't make
> it 'interpreted'. That at some point some machinery
> (the processor or the virtual machine) has to look
> at the instructions and execute them is another topic.
>
> The computer next to me even has a processor which does all
> that in hardware ( http://www.rcsri.org/rcs/Symbolics/ivory/ivory.html ).
Perhaps we should erase the terms interpreter and interpretation, and
replace them by processor and execution.
And compiler and compilation can be replaced by translator and translation.
This would probably lead to a clearer view of these things. (The
distinction between software, virtual machines (bytecode), firmware,
microcode or hardware is irrelevant).
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
Pascal Bourguignon wrote:
> Perhaps we should erase the terms interpreter and interpretation, and
> replace them by processor and execution.
>
> And compiler and compilation can be replaced by translator and translation.
>
> This would probably lead to a clearer view of these things. (The
> distinction between software, virtual machines (bytecode), firmware,
> microcode or hardware is irrelevant).
Trying to reduce the software world to the simple "interpreted /
compiled" dichotomy is an exercise of questionable value (IMHO). Folks
have pointed out various nuances already (compiled C++ code that
includes RTTI, JIT compilation of java code) that don't fit neatly into
the dichotomy.
It seems more fruitful to focus on various performance metrics
(performance benchmarks, developer productivity, etc...). Then, when
there are concrete metrics to compare, discussing the implementation
details that result in the different results (e.g. "VM with JIT" vs
"compiled to native x86") makes more sense.
--jfc
in message <··············@individual.net>, Pascal Costanza
(···@p-cos.net') wrote:
> If you add type tags to runtime values, and use those type tags to
> determine what operations are or are not acceptable, this is, in a
> sense, a kind of interpretation.
Interpreting which circuits to switch on in the processor on the basis of
bits in the instruction word are kinds of interpretation. And certainly
using processor opcodes to fire particular bits of micro-code is a kind
of interpretation. But if you push it to that extent then the
distinction between 'interpreted' and 'compiled' becomes essentially
meaningless.
As you say, provided all the versions are semantically identical, it
really doesn't matter at what level in the machine - 'interpeter',
virtual machine, statically or JIT-compiled opcodes, or microcode - the
interpretation is done, the results of the computation are the same.
--
·····@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; It's dangerous to be right when the government is wrong.
;; Voltaire RIP Dr David Kelly 1945-2004
in message <························@i39g2000cwa.googlegroups.com>,
·········@gmail.com (··········@gmail.com') wrote:
> None of the books I have read explain this and I know very little about
> it (I have only run programs at the REPL).
>
> My question is: how can machine code be compiled from a lisp code if
> all lisp programs use garbage collection? Isn't a virtual
> machine/interpreter needed for that?
There is absolutely no relationship between the concept of a virtual
machine and the concept of automated memory management (except that
modern program environments are likely to feature both). Equally there's
absolutely no relationship between whether code is interpreted or
compiled and automated memory management.
Whether the underlying machine is virtual or not is or should be
completely invisible to the program running on the machine. The Java VM
instruction set has been implemented in hardware, and the overwhelming
majority of 'real' CPU instruction sets have been implemented in
software (google for 'emulators'). A program has no way of knowing
whether it's running on 'the real hardware' (whatever that may mean) or
on an emulator.
Automated memory management is usually implemented in software anyway;
the Java Virtual Machine, for example, has no instructions which
explicitly relate to garbage collection (I think; if I'm wrong someone
will be along in a minute to correct me).
--
·····@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; Semper in faecibus sumus, sole profundum variat.