Hi, there seem to be a lot of implementor users out there. I tried to download the source code for a few CL implementations but I definitely don't know enough to study how it works with just the source. So imagine that I feel ready to implement a Lisp (not CL, something smaller but more than Scheme). What should I read? I would like my implementation to be both an interpreter and a compiler, ideally to native code. I like the idea of type inference but maybe this is an advanced subject. How much code could be borrowed from actual implementations? Is there an implementation out there that is easy to study? Self hosting is cool but it looks like a pain to bootstrap. Would an implementation benefit from a small kernel in C or something?
Ok thats a lot of questions and I probably can't attack them until I learn more. So what should I read?
Yannick Gingras <yging...@ygingras.net> writes: > Ok thats a lot of questions and I probably can't attack them > until I learn more. So what should I read?
Lisp in Small Pieces, if you can find a copy. (My local university library had one.)
Also, study simpler lisp implementations. GNU Guile is where I learned a lot of what I ended up putting to use in ALisp. You can also have a look at Mosquito Lisp, available under the LGPL from its developers at http://www.ephemeralsecurity.com/ - it's not terribly hard to follow their (very Schemeish) implementation.
Another thing you will want to do is define your goals. What do you want to be possible in your lisp? I wrote mine as a secure (no capability of modifying anything outside its environment, such as files on disk) application extension language with a particular use in mind. Have your goals in mind before you lay down any code.
As to reusing code, I have not found that it would be terribly useful to do that. Most of the major open-source CL implementations have enough pervasive internal structures that cutting out any one part and making real use of it seems like more work than it would be worth.
As to having a C (or other language) kernel do some of the work for you, that will depend on what goals you eventually adopt. If you want to be able to compile down to an ELF executable, you will likely not need one by the time you are done. Otherwise, if you value your sanity, you will probably do certain parts, such as loading a memory image and collecting garbage, in C or some other language more suitable to low-level memory management and OS interface.
Ari Johnson <iamthe...@gmail.com> wrote: +--------------- | Yannick Gingras <yging...@ygingras.net> writes: | > Ok thats a lot of questions and I probably can't attack them | > until I learn more. So what should I read? | | Lisp in Small Pieces, if you can find a copy. +---------------
Absolutely!! A great book! Especially the section on "fast interpretation" where he [Christian Queinnec] presents several different ways to manage lexical environments.
Also read the chapters on interpreters & compilers in Peter Norvig's "Paradigms of Artificial Intelligence Programming" <http://www.norvig.com/paip.html>.
+--------------- | Also, study simpler lisp implementations. +---------------
Lisp500, SIOD, SCM. [Though the latter two are Schemes.]
And I've found the source code for CMUCL to be surprisingly readable, *except* the interpreter and compiler proper. That is, all the code for the built-in CL "library" functions [the stuff in "src/code/" as opposed to the stuff in "src/compiler/"] is quite readable.
-Rob
----- Rob Warnock <r...@rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607
Yannick Gingras wrote: > Hi, there seem to be a lot of implementor users out there. I > tried to download the source code for a few CL implementations > but I definitely don't know enough to study how it works with > just the source.
I think this is not a productive approach for what you are trying to do. Let me recite an old joke:
Q: How do you carve a sculpture of an elephant? A: Start with a large block of marble and chip away everything that doesn't look like an elephant.
You are combining the goal of learning Lisp (in Lisp) with the goal of implementing Lisp. Would you do the same thing with C++? With assembly language?
Lisp is nearly always implemented in Lisp. (Just like C is nearly always implemented in C, and Java is nearly always implemented in Java.) Before you deal with the complexity and unfamiliarity of implementing Lisp you should first learn to be a Lisp programmer. This will go faster and will be more productive for you.
Peter Seibel's book is a good modern choice, but there are a number of others as well.
Steven Haflich <s...@alum.mit.edu> writes: > You are combining the goal of learning Lisp (in Lisp) with the goal of > implementing Lisp. Would you do the same thing with C++? With assembly > language?
Steven Haflich <s...@alum.mit.edu> writes: > You are combining the goal of learning Lisp (in Lisp) with the goal of > implementing Lisp.
A reasonably trivial google search (I used "yannick gingras lisp") suggests that this is unlikely to be the case.
To the OP: Lisp in Small Pieces is a good book for implementors; I would also recommend lisp500's source code over any more production-quality lisp, as it is relatively simple (at least once the C code has been deobfuscated).
Yannick Gingras <yging...@ygingras.net> writes: > Hi, there seem to be a lot of implementor users out there. I > tried to download the source code for a few CL implementations > but I definitely don't know enough to study how it works with > just the source. So imagine that I feel ready to implement a > Lisp (not CL, something smaller but more than Scheme). What > should I read? I would like my implementation to be both an > interpreter and a compiler, ideally to native code. I like the > idea of type inference but maybe this is an advanced subject. > How much code could be borrowed from actual implementations? Is > there an implementation out there that is easy to study? Self > hosting is cool but it looks like a pain to bootstrap. Would an > implementation benefit from a small kernel in C or something?
> Ok thats a lot of questions and I probably can't attack them > until I learn more. So what should I read?
Others have given good suggestions here. I'd also recommend a good compiler book (like _Modern Compiler Design in ML_) if you're not familiar with the interesting parts of a compiler (ie, everything after you have an AST).
As for a dialect, you might look at ISLISP. It's small, simple, but with enough goodies that you could do real work in it. The spec seems to be written to allow for very static, batch-compile-then-deploy implementations, but doesn't preclude you from making a nice dynamic, interactive one.
On the question of bootstrapping, it's not hard if you begin your implementation in CL -- you can port your compiler and runtime to its own dialect when it's time. Or, write your low-level VM in C, but in such a way that you'll be able to replace it later.
Thanks for all the suggestions! There was some minor confusion on my intent. I indeed know a reasonable part of CL and I'm only interested in doing the implementation of a small dialect at the moment.
What I want is a concise Lisp for shell scripting that will scale well to medium size projects. You can think of Python with sexp syntax and macros. I know many scheme implementation have large shell scripting libraries but I really want to try to make my own dialect.
I won't start coding soon but as I do my reading I want to let ideas for my small dialect assemble slowly into a coherent structure. What features should a shell scripting oriented dialect have?
Yannick Gingras wrote: > What > features should a shell scripting oriented dialect have?
"# blah <EOL>" as comment syntax (or at least a special casing of the first line of a file if it begins with #!) so that "#!" works like people have come to expect. ;-)
t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Others have given good suggestions here. I'd also recommend a good > compiler book (like _Modern Compiler Design in ML_) if you're not > familiar with the interesting parts of a compiler (ie, everything > after you have an AST).
For that matter, read the paper on CMUCL's Python compiler. I forget where it's hosted but I wish I had read it prior to ever writing a compiler.
Ari Johnson <iamthe...@gmail.com> writes: > t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>> Others have given good suggestions here. I'd also recommend a good >> compiler book (like _Modern Compiler Design in ML_) if you're not >> familiar with the interesting parts of a compiler (ie, everything >> after you have an AST).
> For that matter, read the paper on CMUCL's Python compiler. I forget > where it's hosted but I wish I had read it prior to ever writing a > compiler.
t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> I'd also recommend a good compiler book (like _Modern Compiler > Design in ML_) if you're not familiar with the interesting parts of > a compiler (ie, everything after you have an AST).
I assume you mean Appel's "Modern Compiler Implementation in ML"? There's another book called "Modern Compiler Design".
For quite some time, I've been meaning to pick up a few good compiler books that cover techniques not found in the Dragon book, like SSA. This might be a good opportunity to ask for recommendations.
Other than the Appel book (which seems to fit my bill well), are there any other titles I should look into?
Lars Brinkhoff <lars.s...@nocrew.org> writes: > For quite some time, I've been meaning to pick up a few good compiler > books that cover techniques not found in the Dragon book, like SSA. > This might be a good opportunity to ask for recommendations.
> Other than the Appel book (which seems to fit my bill well), are there > any other titles I should look into?
Here are the big books on my shelf:
Muchnik, Advanced Compiler Design & Implementation. Morgan, Building an Optimizing Compiler. Cooper & Torczon, Engineering a Compiler. Ellis, Bulldog: A Compiler for VLIW Architectures.
Have a look at 2nd ed. Dragon Book and Srikant, The Compiler Design Handbook. (I haven't got either yet, but they seem worth owning.)
(At this point, one starts to get into the twilight zone of computer architecture.)
For program analysis:
Nielson et al, Principles of Program Analysis. Pierce, Types and Programming Languages. Jones et al, Partial Evaluation and Automatic Program Generation.
Serious discussions of advanced programming languages is a bit scarce. I liked this one, which concerns ML in particular:
Appel, Compiling with Continuations. (Cf. also his article, "A Runtime System")
On Sat, 30 Sep 2006 10:43:49 -0400, Yannick Gingras wrote: > I won't start coding soon but as I do my reading I want to let ideas for my > small dialect assemble slowly into a coherent structure. What features > should a shell scripting oriented dialect have?
Being able to trivially execute other programs and perform I/O redirection is essential. It is the defining feature of a shell scripting language.
A good FFI is probably not essential, if you can mitigate the loss via my above point, but it /is/ very very useful.
Minimize typing. It should be possible to construct useful programs in one line of text (80 column lines or less). Common Lisp fails here, Scheme is a bit better, but Arc is a clear winner. Or at least what little we've seen of it so far. Tab completion doesn't count: The point is to make visually compact programs, not to make it easy to type sesquipedilian[1] names.
[1]Literally, 'foot and a half long'.
Having strong text support is essential. Being able to handle UTF-8 intelligently is an element of this, and you should choose an implementation method that helps you here. This may or may not mean regular expressions, but being able to leverage cl-ppcre will make the regex path easier if you choose it. There are other ways of parsing text.[2] Regardless, Lisp's memory management model makes this kind of thing painless.
[2]I've never seen an EBNF implementation in a shell scripting language, but it would seem to fit well with the generally recursive model of Lisp. EBNF is more powerful than regexes are because it can be used to match arbitrarily nested structures, such as sexps.
-- My address happens to be com (dot) gmail (at) usenet (plus) chbarts, wardsback and translated. It's in my header if you need a spoiler.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Chris Barts <puonegf+hfr...@tznvy.pbz> writes: > Being able to trivially execute other programs and perform I/O redirection > is essential. It is the defining feature of a shell scripting language. > [...] > Minimize typing. It should be possible to construct useful programs in one > line of text (80 column lines or less). Common Lisp fails here, Scheme is > a bit better, but Arc is a clear winner. Or at least what little we've > seen of it so far. Tab completion doesn't count: The point is to make > visually compact programs, not to make it easy to type sesquipedilian[1] > names.
This requirement is even older than LISP (when the hardware didn't allow typing, storing or printing longer names), and doesn't matter at all for _scripts_. You might want to keep it for _interactive_ usage, but not for scripts.
For example, AppleScript is rather verbose.
I write all my scripts in Common Lisp (no problem with the length of the command names), but indeed, I still don't use routinely CL or scsh as my login shell.
When the name 'ls' was choosen for the command to list a directory contents, the time needed to type and echo it thru a 300 bps terminal was, including the final newline:
send 3 character: l s CR = 30 bits, 0.100 second receive 4 characters: l s CR LF = 40 bits, 0.133 second total: 0.233 second
Nowadays, during this time, you can receive up to 58250 bytes, whole scripts, on an ADSL 2 Mb/s line, or you can spend about 700,000,000 processor cycles on analysing your speach, or your gestures to infer the command, on a 3 GHz processor.
READ THIS BEFORE OPENING PACKAGE: According to certain suggested versions of the Grand Unified Theory, the primary particles constituting this product may decay to nothingness within the next four hundred million years.
Yannick Gingras wrote: > So imagine that I feel ready to implement a > Lisp (not CL, something smaller but more than Scheme). What > should I read? I would like my implementation to be both an > interpreter and a compiler, ideally to native code.
Much as I (and we all, I think) appreciate your enthusiasm, I (speaking now for myself) would strongly discourage you from implemeting your own Lisp. The fact that one *can* implement their own Lisp leads many to in fact do this, and this is a, IMHO, a huge part of what has fragmented the Lisp community. I suspect that people don't go out and implement their own Rubys, Perls, Pythons, or C++s; they use the excellent sanctioned free implementations. Why would you build your own Lisp instead of throwing your considerable skill and effort behind, for example, SBCL? In fact, why isn't everyone on this list who has considerable skill and effort [and who isn't paying for a Lisp] helping build The One True Open Lisp?
JShra...@gmail.com wrote: > Yannick Gingras wrote: > > So imagine that I feel ready to implement a > > Lisp (not CL, something smaller but more than Scheme). What > > should I read? I would like my implementation to be both an > > interpreter and a compiler, ideally to native code.
> Much as I (and we all, I think) appreciate your enthusiasm, I (speaking > now for myself) would strongly discourage you from implemeting your own > Lisp. The fact that one *can* implement their own Lisp leads many to in > fact do this, and this is a, IMHO, a huge part of what has fragmented > the Lisp community. I suspect that people don't go out and implement > their own Rubys, Perls, Pythons, or C++s; they use the excellent > sanctioned free implementations. Why would you build your own Lisp > instead of throwing your considerable skill and effort behind, for > example, SBCL? In fact, why isn't everyone on this list who has > considerable skill and effort [and who isn't paying for a Lisp] helping > build The One True Open Lisp?
I agree and believe that SBCL needs a lot of help in this stage. For example, I would add a way of loading only one SBCL core for multiple Lisp applications (now, SBCL wastes more than 30Mb of memory each time it runs a program), and of course a stable Windows version.
On Sun, 01 Oct 2006 17:16:49 +0200, Pascal Bourguignon wrote: > Chris Barts <puonegf+hfr...@tznvy.pbz> writes: >> Minimize typing. It should be possible to construct useful programs in one >> line of text (80 column lines or less). Common Lisp fails here, Scheme is >> a bit better, but Arc is a clear winner. Or at least what little we've >> seen of it so far. Tab completion doesn't count: The point is to make >> visually compact programs, not to make it easy to type sesquipedilian[1] >> names.
> This requirement is even older than LISP (when the hardware didn't > allow typing, storing or printing longer names), and doesn't matter at > all for _scripts_. You might want to keep it for _interactive_ usage, > but not for scripts.
I still think it's a win to make the interactive language the scripting language. People in the Bad Old Days, back before the Bourne-like shells had job control or command-line editing or anything else of note, had to learn the C shell for interactive work and the Bourne shell for scripting, because the C shell has never had a real syntax. (That is, it's always been a buggy unportable ad-hoc mess.)
This is stupid because... well, this is a Lisp group. Do I really need to enthuse about the REPL here? ;)
> For example, AppleScript is rather verbose.
I don't know if there was ever an AppleScript REPL.
> I write all my scripts in Common Lisp (no problem with the length of > the command names), but indeed, I still don't use routinely CL or scsh > as my login shell.
Which means both the CL standard library and the majority of your CL functions (those not embedded in freestanding programs)[1] are unavailable to you in the command line.
[1]Yes, that's an assumption. You could make a new program for every function you create. ;)
> Nowadays, during this time, you can receive up to 58250 bytes, whole > scripts, on an ADSL 2 Mb/s line, or you can spend about 700,000,000 > processor cycles on analysing your speach, or your gestures to infer > the command, on a 3 GHz processor.
Or not, and spend those cycles doing what you bought the machine to do.
-- My address happens to be com (dot) gmail (at) usenet (plus) chbarts, wardsback and translated. It's in my header if you need a spoiler.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Just to be clear: I'm not pushing SBCL -- I don't have a leaning for one free lisp v. another. My point is just that one shouldn't be implementing new lisps -- one should be working with the community to provide a single agreed implementation, or else one should be paying others (whether Franz or the Open Lisp group). I personally pay Franz at the moment, but I'd be happy as well to help financially support a free lisp project if there was some agreement by the community on which one we were going to support, and if everyone would just get behind that one!
JShra...@gmail.com wrote: > Yannick Gingras wrote: > > So imagine that I feel ready to implement a > > Lisp (not CL, something smaller but more than Scheme). What > > should I read? I would like my implementation to be both an > > interpreter and a compiler, ideally to native code.
> Much as I (and we all, I think) appreciate your enthusiasm, I (speaking > now for myself) would strongly discourage you from implemeting your own > Lisp. The fact that one *can* implement their own Lisp leads many to in > fact do this, and this is a, IMHO, a huge part of what has fragmented > the Lisp community. I suspect that people don't go out and implement > their own Rubys, Perls, Pythons, or C++s; they use the excellent > sanctioned free implementations. Why would you build your own Lisp > instead of throwing your considerable skill and effort behind, for > example, SBCL? In fact, why isn't everyone on this list who has > considerable skill and effort [and who isn't paying for a Lisp] helping > build The One True Open Lisp?
JShra...@gmail.com writes: > Just to be clear: I'm not pushing SBCL -- I don't have a leaning for > one free lisp v. another. My point is just that one shouldn't be > implementing new lisps -- one should be working with the community to > provide a single agreed implementation, or else one should be paying > others (whether Franz or the Open Lisp group). I personally pay Franz > at the moment, but I'd be happy as well to help financially support a > free lisp project if there was some agreement by the community on which > one we were going to support, and if everyone would just get behind > that one!
I disagree. Currently, perhaps some implementations like gcl or ecl may need more work (to increase conformance), but I don't think there's too many of them. On the contrary, I think we'd need more different implementations, targetted at different kind of usage.
We'd need one implementation that is easily portable to any random architecture. We'd need an implementations good for PDA. One for other embedded devices. We'd need an implementation for development, with better debugger and better analysis tools. Etc.
It's possible that some layer be common to several of these implementations, like the "library" layer, or the "extensions" layer. But it would still be nice to have _more_ different implementations.
The wost case might be cmucl vs. sbcl. But even with this close fork, cmucl and sbcl are still differentiated enough.
> I wish that there was just one
I wish there was ever more different implementations.
I think it's realistic to get behind SBCL "as the one". It's fast, doesn't have licensing issues, getting there with all the major platforms, and I believe 0.9.17 is tentatively being called a 1.0 beta.
JShra...@gmail.com wrote: > Just to be clear: I'm not pushing SBCL -- I don't have a leaning for > one free lisp v. another. My point is just that one shouldn't be > implementing new lisps -- one should be working with the community to > provide a single agreed implementation, or else one should be paying > others (whether Franz or the Open Lisp group). I personally pay Franz > at the moment, but I'd be happy as well to help financially support a > free lisp project if there was some agreement by the community on which > one we were going to support, and if everyone would just get behind > that one!
> I wish that there was just one > JShra...@gmail.com wrote: > > Yannick Gingras wrote: > > > So imagine that I feel ready to implement a > > > Lisp (not CL, something smaller but more than Scheme). What > > > should I read? I would like my implementation to be both an > > > interpreter and a compiler, ideally to native code.
> > Much as I (and we all, I think) appreciate your enthusiasm, I (speaking > > now for myself) would strongly discourage you from implemeting your own > > Lisp. The fact that one *can* implement their own Lisp leads many to in > > fact do this, and this is a, IMHO, a huge part of what has fragmented > > the Lisp community. I suspect that people don't go out and implement > > their own Rubys, Perls, Pythons, or C++s; they use the excellent > > sanctioned free implementations. Why would you build your own Lisp > > instead of throwing your considerable skill and effort behind, for > > example, SBCL? In fact, why isn't everyone on this list who has > > considerable skill and effort [and who isn't paying for a Lisp] helping > > build The One True Open Lisp?
Javier <javu...@gmail.com> wrote: > I agree and believe that SBCL needs a lot of help in this stage. For > example, I would add a way of loading only one SBCL core for multiple > Lisp applications (now, SBCL wastes more than 30Mb of memory each time > it runs a program)
It doesn't. The core file is already mapped as private copy-on-write memory on most operating systems, so any pages that are only read are shared between processes.
Also, the RSS of a fresh SBCL process on x86/Linux is only about 5MB. Even the silly little applets in my Gnome panel are using twice that...
Yannick Gingras wrote: > Hi, there seem to be a lot of implementor users out there. I > tried to download the source code for a few CL implementations > but I definitely don't know enough to study how it works with > just the source. So imagine that I feel ready to implement a > Lisp (not CL, something smaller but more than Scheme). What > should I read? I would like my implementation to be both an > interpreter and a compiler, ideally to native code.
> We'd need one implementation that is easily portable to any random > architecture.
ECL has not yet failed to be ported to any architecture where Gnu MP works. It is 64-bit and endian clean. I agree that...
> We'd need an implementations good for PDA. One for > other embedded devices.
... in memory constrained environments it could do better, but I do not see why it could not run on a PDA -- of course you would probably need cross compilation, but ECL can be cross-compiled.
> We'd need an implementation for development, > with better debugger and better analysis tools. Etc.
This is definitely doable, but I do not see why you need an specific implementation for that. All implementations should converge to a degree where they offer the best code analysis tools they can. This does not interfere with other goals, does it?
