I am currently involved in writing a byte-code compiler and a virtual
machine to execute it. The compiler will be written in lisp, however I
thought C was a good choice to implement the virtual machine in as it
let me do my own memory management etc..
But now I find myself using a C/C++ garbage collector for all the
bookkeeping code of the VM, So, anyone think it would be better to
implement the VM in lisp? if so, I would like to know the reasons why I
should choose lisp over C there and the advantages in doing so.
regards,
vishnu vyas.
vishnuvyas wrote:
> I am currently involved in writing a byte-code compiler and a virtual
> machine to execute it. The compiler will be written in lisp, however I
> thought C was a good choice to implement the virtual machine in as it
> let me do my own memory management etc..
>
> But now I find myself using a C/C++ garbage collector for all the
> bookkeeping code of the VM, So, anyone think it would be better to
> implement the VM in lisp?
Of Course, but this is comp.lang.lisp. I suspect you'd get a different
set of opinions on c.l.c. :)
> if so, I would like to know the reasons why I
> should choose lisp over C there and the advantages in doing so.
1) You are already using lisp for the compiler (this assumes it is
preferable to work in a single language).
2) You find yourself using a C/C++ GC, even though your stated reason
for choosing C was so you could do your own memory management.
3) You haven't offered any arguments against lisp, so are obviously
predisposed to a lisp solution.
Besides that, there are the many obvious advantages that Lisp has over
C, which you must be aware of, having chosen lisp for the compiler.
Are there any reasons you can come up with as to why you should _not_
use lisp for your VM? Posting those here will probably get you a better
response than what i have offered above, which was really just me
re-stating your question as an answer.
If you're just looking for reassurance that using lisp for the VM is a
good idea, go for it! Especially if your VM is dynamic in nature, you'll
save a lot of implemtation effort by hosting it on lisp.
--
Drew Crampsie
drewc at tech dot coop
"... the most advanced use of lisp in the field of bass lure sales"
-- Xach on #lisp
> 2) You find yourself using a C/C++ GC, even though your stated reason
> for choosing C was so you could do your own memory management.
I want to do my own memory management for the bytecode program's heap,
(which will be garbage collected by the VM). I use the C/C++ gc for the
bookkeeping code that goes along with VM (like maintaining a runtime
stack which the bytecode doesn't have direct access to..)
>Besides that, there are the many obvious advantages that Lisp has over
>C, which you must be aware of, having chosen lisp for the compiler.
Initially I was very sure that C was going to be the language of
implementation of the VM, but when I started writing the code, I ended
up doing a lot of things from scratch (half the things common lisp
already provided), that is why I even considered LISP for the VM.
My only doubts with lisp, is that would it be able get away with doing
pretty low level stuff like mallocing arbitrary blocks of memory
without any structure..? Interfacing to the dynamic libraries, etc?
>If you're just looking for reassurance that using lisp for the VM is a
>good idea, go for it! Especially if your VM is dynamic in nature, you'll
>save a lot of implemtation effort by hosting it on lisp.
One of the main reasons for doing a VM is to learn how they work (from
the inside), So, there is very little question of 'saving the effort',
while learning nothing, I wasn't sure wether LISP would allow me to
actually let me manage a custom bytecode heap, so thats why I posted
here. (Is there anyway to allocate and access a block of memory in LISP
, just a random block of arbitrary size with no structure imposed on
it? )
"vishnuvyas" <··········@gmail.com> writes:
> I want to do my own memory management for the bytecode program's heap,
> (which will be garbage collected by the VM). I use the C/C++ gc for the
> bookkeeping code that goes along with VM (like maintaining a runtime
> stack which the bytecode doesn't have direct access to..)
Perhaps you'll be interested in having a look at my heap.lisp, which
implements a heap with a simple mark-and-sweep GC written in Common Lisp.
http://www.informatimago.com/develop/lisp/index.html
cvs -z3 -d ··················@cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/common-lisp
cvs -z3 -d ··················@cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/clisp
Lisp is one of the best languages to manipulate bits, with LDB, DPB,
ASH, and LOGAND, LOGIOR, LOGNOT, etc.
Compare:
Lisp C
(ldb (byte 5 7) word) (word>>7)&0x1f
(dpb bits (byte 5 7) word) word=((word&(~(0x1f<<7)))|((bits&0x1f)<<7));
There is no standard API to get at the raw bytes in memory, but if
you're writting a VM, you can store the words in normal integer
arrays, ignoring the fact that you may be working with bignums. Or if
you have a FFI, you can easily write some stub functions in C to
access the raw memory.
Now, of course, writing a VM, you don't need to map the VM types to
basic processor types: you're implementing the VM on Common Lisp, you
you need to mal the VM types to Common Lisp types!
Another point, is that it might be interesting performance-wise to
implement a JIT compiler in the VM. You can do this easily in Lisp,
since you have the Lisp compiler always available. It would be harder
to do in C: you'd have to write your own JIT compiler.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
vishnuvyas wrote:
> I want to do my own memory management for the bytecode program's heap,
> (which will be garbage collected by the VM).
So, do it. Allocate a big byte vector, or whatever memory unit you'd
like.
> My only doubts with lisp, is that would it be able get away with doing
> pretty low level stuff like mallocing arbitrary blocks of memory
> without any structure..?
Of course it would. Why would you think that you can't convert 4 bytes
into an int, a float, or a pointer into something in your heap?
To use lisp ops on said bytes, you'll have to arrange to get them into
a
value with the appropriate dynamic type, but that's (conceptually) like
writing code that takes the string "123" and returns an integer.
FWIW, you have to do much the same thing in C. And, if you really
wanted,
you could call a c op with pointers into your heap and let it do work.
-andy
Pascal Bourguignon wrote :
>Another point, is that it might be interesting performance-wise to
>implement a JIT compiler in the VM. You can do this easily in Lisp,
>since you have the Lisp compiler always available. It would be harder
>to do in C: you'd have to write your own JIT compiler.
How will the lisp compiler help if I have to convert from bytecode ->
m/c code? Or should I convert my the program into s-expressions? (I
am pretty much a newbie to lisp, so I really don't know about that
bit).
······@earthlink.net wrote:
>So, do it. Allocate a big byte vector, or whatever memory unit you'd
>like.
Hmm, thats what I am planning to doing currently.. anyway thanks for
the suggestions..
>you could call a c op with pointers into your heap and let it do work.
I don't understand that part, can you please explain?
-vishnu vyas
vishnuvyas wrote:
> >you could call a c op with pointers into your heap and let it do work.
> I don't understand that part, can you please explain?
Arranging to call "AddInC(<destptr>, <src1ptr>, <src2ptr>)" when you
want to c-like-add two values can be done in any language. If AddInC
is defined in C and the rest of the VM is written in lisp, said
arrangment is a foreign function call.
"vishnuvyas" <··········@gmail.com> writes:
> Pascal Bourguignon wrote :
>>Another point, is that it might be interesting performance-wise to
>>implement a JIT compiler in the VM. You can do this easily in Lisp,
>>since you have the Lisp compiler always available. It would be harder
>>to do in C: you'd have to write your own JIT compiler.
>
> How will the lisp compiler help if I have to convert from bytecode ->
> m/c code?
Because the Lisp compiler probably knows how to generate machine
code. So all you have to do is translate your bytecodes into Common
Lisp and then use COMPILE to compile them.
> Or should I convert my the program into s-expressions? (I am pretty
> much a newbie to lisp, so I really don't know about that bit).
Not just s-expressions but s-expressions that can be compiled as
Common Lisp. But note that you can define your own "target machine"
above the level of raw Common Lisp by defining functions and macros
and then compiling your bytecodes into calls to those new operators.
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
In article <·······················@g47g2000cwa.googlegroups.com>,
"vishnuvyas" <··········@gmail.com> wrote:
> I am currently involved in writing a byte-code compiler and a virtual
> machine to execute it. The compiler will be written in lisp, however I
> thought C was a good choice to implement the virtual machine in as it
> let me do my own memory management etc..
>
> But now I find myself using a C/C++ garbage collector for all the
> bookkeeping code of the VM, So, anyone think it would be better to
> implement the VM in lisp? if so, I would like to know the reasons why I
> should choose lisp over C there and the advantages in doing so.
>
> regards,
> vishnu vyas.
There are excellent books to study.
'Lisp in Small Pieces'
http://youpou.lip6.fr/queinnec/WWW/LiSP.html
'Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp'
http://www.norvig.com/paip.html
>Peter Seibel wrote :
>So all you have to do is translate your bytecodes into Common
>Lisp and then use COMPILE to compile them.
Hmm.. that is sort of misses the whole point of 'having bytecodes'.. If
I wanted to get s-expressions wouldn't it be easier from the parse
trees directly, rather than byte-code ?
>But note that you can define your own "target machine"
>above the level of raw Common Lisp by defining functions and macros
> and then compiling your bytecodes into calls to those new operators.
Is this actually better than compiling JIT? anyway the bytecodes will
be represented as functions and the VM would have to execute a
function call in the least to do the operation of the bytecode .. Are
there any advantages in doing it like this?
(Btw, Great book.. I got started in common lisp using your book..)
>Rainer Joswig wrote:
>There are excellent books to study.
>
>'Lisp in Small Pieces'
>http://youpou.lip6.fr/queinnec/WWW/LiSP.html
>
>'Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp'
>http://www.norvig.com/paip.html
Are there any freely available (online) books in this area? Its pretty
hard to find books like
LISP in small pieces, etc.. here in india..
vishnuvyas wrote:
>>Peter Seibel wrote :
>>So all you have to do is translate your bytecodes into Common
>>Lisp and then use COMPILE to compile them.
>
> Hmm.. that is sort of misses the whole point of 'having bytecodes'.. If
> I wanted to get s-expressions wouldn't it be easier from the parse
> trees directly, rather than byte-code ?
There are actually people arguing this. See
http://www.ics.uci.edu/~franz/Site/pubs-pdf/C05.pdf
Indeed, parts of what a JVM does during compilation is to reconstruct
information that would be more easily available in a syntax tree in the
first place (for example, the types of local variables).
Pascal
--
OOPSLA'05 tutorial on generic functions & the CLOS Metaobject Protocol
++++ see http://p-cos.net/oopsla05-tutorial.html for more details ++++
Pascal Costanza <··@p-cos.net> writes:
> vishnuvyas wrote:
>
> >>Peter Seibel wrote :
> >>So all you have to do is translate your bytecodes into Common
> >>Lisp and then use COMPILE to compile them.
> > Hmm.. that is sort of misses the whole point of 'having
> > bytecodes'.. If
> > I wanted to get s-expressions wouldn't it be easier from the parse
> > trees directly, rather than byte-code ?
>
> There are actually people arguing this. See
> http://www.ics.uci.edu/~franz/Site/pubs-pdf/C05.pdf
Not only are there people arguing for that, but IBM mainframes has implemented
binary encoded abstract syntax trees instead of bytecode as executables for a long
time, as far as I understand.
> Indeed, parts of what a JVM does during compilation is to reconstruct
> information that would be more easily available in a syntax tree in
> the first place (for example, the types of local variables).
The Source -> Bytecode -> Machine Instructions path is anyway far from optimal
when it comes to a portable executable layer, and this has been known for a long
time. The complexity of making an efficient JIT system would have been smaller, although
maybe not for an inefficient one.
--
Gisle Sælensminde, Phd student, Scientific programmer
Computational biology unit, BCCS, University of Bergen, Norway,
Email: ·····@cbu.uib.no
I had a brief look at the above mentioned paper and it's an interesting
idea, but also kind of weird.
It seems that the idea of distributing programs in a platform
independent way using a syntax tree is a lot like distributing C
programs in source form. When you get them you compile them and then
run them. There are _some_ differences with what is proposed above, as
the compile and execute stages both happen when the program is loaded,
rather than explicitly compiling separately. In this respect it seems
quite a bit like using (load "some-file.lisp") on a version of lisp
that always compiles everything. The main difference being the
text/binary AST storage distinction. Of course, with lisp you're coding
(more or less) directly in the AST rather than in a 'surface'
representation of the source. I guess it's possible to make the compile
phase fast.
Before I started using lisp I tried implementing some (crude,
interpreted) programming languages. I wouldn't have considered trying
to make compilers for them because the machine code generation phase
seemed like a lot of work compared to just interpreting. Now that I use
lisp I could get that for free though, just by translating my language
to lisp on the fly (ok, so I could have translated to C before, and
compiled that, but it's not quite the same). This seems a fairly common
thing to do when using DSLs of course, and there are prolog-in-lisp
implementations (for example) which do just that, and probably run
fairly efficiently.
If one were implementing a language like, say, perl, would it not be a
good way to go to translate your parse tree to lisp sexps and
implemented whatever support functions/macros were required to run that
code? I would have thought that given a common lisp implementation
which had a good compiler that this would give you a very fast perl
runtime - faster than the normal perl5 in most cases I would think,
since this runs an interprative stack based VM of sorts (I think - no
JIT here). There may be cases where the current perl5 would still win
unless you hacked the lisp implementation quite hard - maybe its regexp
engine is very fast (though PPCRE is reckoned faster), or its string
handling? If one were to implement a strongly and statically typed
language then I presume this information could be passed over to the
lisp compiler too, where it would be made good use of to produce
efficient code.
It seems to me that for most programming languages one could easily
make a rather good implementation just by translating to lisp which is
then compiled. I'm quite tempted to have a go at writing a programming
language of my own now, just because I think it would be so much easier
and better. The thing which prevents me is the fact that I like lisp so
much :-)
Sorry for the long rambling post!
-- David
David wrote:
> If one were implementing a language like, say, perl, would it not be a
> good way to go to translate your parse tree to lisp sexps and
> implemented whatever support functions/macros were required to run that
> code? I would have thought that given a common lisp implementation
> which had a good compiler that this would give you a very fast perl
> runtime - faster than the normal perl5 in most cases I would think,
> since this runs an interprative stack based VM of sorts (I think - no
> JIT here).
Yes, I think you're basically right. That's also how I did my first
project in Common Lisp a few years ago - I have implemented a JVM that
basically translates bytecode to s-expressions at load time and leaves
the rest to the Common Lisp compiler. I learned quite a big chunk of
Common Lisp that way in a very short amount of time.
I have never "finished" that project though, and I will probably not in
the foreseeable future. It's still on my todo list to open source the
code so that other people can take over if they are interested...
Pascal
--
OOPSLA'05 tutorial on generic functions & the CLOS Metaobject Protocol
++++ see http://p-cos.net/oopsla05-tutorial.html for more details ++++
>Pascal Costanza wrote
>I have never "finished" that project though, and I will probably not in
>the foreseeable future. It's still on my todo list to open source the
>code so that other people can take over if they are interested...
Hmm.. my virtual machine project is virtually identical, just that
instead of JVM's bytecodes.. I am oscillating between using binary
coded abstract syntax trees and bytecodes.. It would be helpful if you
would let me take a look at that code... you can mail me the code at
··········@gmail.com or give me a url where i can find it.
vishnu vyas
vishnuvyas wrote:
>>Pascal Costanza wrote
>>I have never "finished" that project though, and I will probably not in
>>the foreseeable future. It's still on my todo list to open source the
>>code so that other people can take over if they are interested...
>
> Hmm.. my virtual machine project is virtually identical, just that
> instead of JVM's bytecodes.. I am oscillating between using binary
> coded abstract syntax trees and bytecodes.. It would be helpful if you
> would let me take a look at that code... you can mail me the code at
> ··········@gmail.com or give me a url where i can find it.
I have made a zip file of the code and uploaded it to
http://p-cos.net/lisp/Gina-JVM.zip
I have attached a MIT/BSD-style license so that you can basically do
whatever you want with it.
Note that this was my first Common Lisp project and was foremostly
intended as a way for me to learn Common Lisp. There are probably some
non-idiomatic elements in the code that I would probably do very
differently by now.
Note that I don't have the time to support this in any way. I may be
able to give some comments on the code, but don't expect any timely answers.
Cheers,
Pascal
--
OOPSLA'05 tutorial on generic functions & the CLOS Metaobject Protocol
++++ see http://p-cos.net/oopsla05-tutorial.html for more details ++++
Pascal Costanza wrote
>I have made a zip file of the code and uploaded it to
>http://p-cos.net/lisp/Gina-JVM.zip
>I have attached a MIT/BSD-style license so that you can basically do
>whatever you want with it.
Thank you! will check it out.
vishnu vyas
"vishnuvyas" <··········@gmail.com> writes:
>>Peter Seibel wrote :
>>So all you have to do is translate your bytecodes into Common
>>Lisp and then use COMPILE to compile them.
>
> Hmm.. that is sort of misses the whole point of 'having
> bytecodes'.. If I wanted to get s-expressions wouldn't it be easier
> from the parse trees directly, rather than byte-code ?
Well, I assumed you wanted (or already had) bytecodes for some other
reason. For instance you want to allow folks to distributed "compiled"
code or beacuse you already implmented an interpreter for your
bytecodes.
>>But note that you can define your own "target machine" above the
>>level of raw Common Lisp by defining functions and macros and then
>>compiling your bytecodes into calls to those new operators.
>
> Is this actually better than compiling JIT?
I'm not sure what you mean by "compiling JIT" that's different than
what I'm suggesting.
> anyway the bytecodes will be represented as functions and the VM
> would have to execute a function call in the least to do the
> operation of the bytecode .. Are there any advantages in doing it
> like this?
If you're going to have a function per bytecode maybe not. But if you
have fine grained bytecodes and you compile down into something that
inlines the bytecodes' implementations, you give the Lisp compiler a
chance to do various kinds of optimizations for you.
> (Btw, Great book.. I got started in common lisp using
> your book..)
Thanks.
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/