What are some books or papers that one should read for implementing a 100% R7RS-small compliant Scheme? The interpreter in SICP is just a toy that is missing a huge amount of standard Scheme features such as syntax-rules macros, IO, exception handling, vectors, records, quasiquotation, library system, call/cc, etc. I am okay with toys, but I want 100% standards compliance. How do I learn to implement Scheme? This is for educational purposes only.
Read SICP.
>>3
I have already read SICP! That's how I know that its interpreter is missing a large number of standard Scheme features.
Well, i am talking out of my ass mostly but if you've already studied an incomplete solution you should be able to (mostly) reuse their approaches to add the missing features. Unless of course you are of the opinion those approaches weren't optimal but then you should be knowing superior solutions anyways. Parsing code doesn't get all that different after all. Parse text, check for correctness, make events happen, maybe remember some kind of state, repeat.
>>1
Essentials of Programming Languages, and Lisp in Small Pieces are the definitive books on Lisp implementation. I'm in the same position as you though in terms of having understood the meta-circular interpreters in The Structure and Interpretations of Computer Programs, The Little Schemer, and The Seasoned Schemer, but not a full implementation.
I will note that the interpreter from The Seasoned Schemer does have continuations, and you can implement an exception system in terms of continuations. Also Lisp in Small Pieces while being very comprehensive does not have some of what you requested. Reading other implementations, or papers on optimizing scheme would likely be your only help if you got stuck after this.
You should also consider targeting an older version of the standard at first. R4RS doesn't have a module system, and doesn't require hygenic macros for example. It's perfectly valid to conform to an older version of the standard, these are not invalidated by future revisions.
>>5
Essentials of Programming Languages is not a book on Lisp implementation. The example code in the book is written in Scheme but the languages being implemented are not Lisp-like. They are not even read-able, they need custom parsers.
Also Lisp in Small Pieces while being very comprehensive does not have some of what you requested.
What is it missing? At the moment, my highest priority is the syntax-rules macro system. Does Lisp in Small Pieces show how to implement a hygienic macro system?
>>7
I don't beleive so.
>>7,8
It does however describe a low-level macro system which you can build a hygenic system on top of.
>>9
Is that "low-level macro system" similar to R4RS macros?
Do you know where I can learn to implement syntax-rules macros based on a low-level macro system?
Can't you just like, sit down and figure out how to do it on your own?
>>11
Guess that's asking a bit much these days. People don't like to invent anymore. All they want is checking off boxes.
>>10
R4RS specifies optional hygenic and low-level macros. Here's a paper which seems to be writing a hygenic macro system on top of a low-level macro system https://www.p-cos.net/documents/hygiene.pdf We're mostly out of my knowledge base at this point however, and it might be that someone else has pointers to better resources.
Can't you just like, sit down and figure out how to do it on your own?
I have already done so. I am stuck on the syntax-rules macro system. I want to read a book so that I can:
* See alternative implementations.
* See how syntax-rules is implemented.
I have tried. I really have. My Scheme interpreter has far more features than the one in SICP: more standard procedures, a defmacro-like macro system, quasiquotation, etc.
Can you attempt reading code from other scheme implementations or too much of a cheat for you.
I have tried. I really have.
What did you try and why didn't it work?
I tried to implement a 100% compliant R7RS-small macro system. The problem is that I lack the necessary knowledge to jump from defmacro to syntax-rules. Apparently, it is not possible to build syntax-rules on defmacro. I have looked at "Macro by Example" in SLIB which implements non-compliant syntax-rules using defmacro.
>>17
I found the following paper this morning: https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-1-1-pp53-75.pdf The system seems to be more complex than necessary but there is most of the relevant changes to the interpreter there.
>>18
I heard Chez used this macrosystem and assumed they build a define-syntax style macro system on top. They were apparently independent implementations. I'm going to stop talking now, although I hope someone has something to offer.