3 ms·
The problem with SICP as a compiler book is that it doesn't really doesn't teach you much about compilers. At least beyond Lisp compilers. Even something rela
by kenjackson 16y ago
The problem with SICP as a compiler book is that it doesn't really doesn't teach you much about compilers. At least beyond Lisp compilers. Even something relatively simple, like stack layout isn't really covered, at least that I recall. Or intermediate representations (unless you simpler consider Lisp your IL), or even how different parsing techniques will interplay with what you can parse (easily at least).
It's like saying that reading CLR's algorithms text will teach you how to build real databases, because it teaches you about trees and hash functions.
- mahmud 16y agoTypically, most people just want to learn how to get something up and running, and how to have a pipeline where they can introduce new phases to the processing to test out algorithms. In that sense, the architecture of the underlying machine, even a VM, is a redundant detail. Who cares what's there as long as it executes? Stack discipline is not a compiler thing, but an Algol thing. Wanna figure out how to implement lexical scope on a modern processor without much fuss? Implement Oberon/Pascal and be done with it. You will get your usual stack and base pointers, and you can even have fun with the C kids, even read the Aleph1 and Mudge papers. But there is more to control semantics than the petty static/dynamic links of Algol to implement nested functions and dynamic environments without first-class closures, if not continuations. "push ebp, mov esp, ebp" is trite when your "procedures" are heap allocated objects that can change at runtime, even get garbage collected. So a change in the complexity and the semantic geography of the problem necessitates a departure from more primitive implementation techniques. As for IRs; the traditional lisp intermediate representations are just the primitives for binding, closure construction and closure application. Straight out of theory. This is what the lambda conversions spit out, and they're directly executable by your underlying system. So now you have more time to tinker with the semantics, improve the optimization phases, and generally do more. Having said that, you will recall that SICP implements both a register machine, and has section on evaluating reverse polish expressions :-)
- kenjackson 16y ago"Stack discipline is not a compiler thing, but an Algol thing." That's an absurd statement. That's like saying "text" is simply one representation of a program. While technically true, it covers a wide enough portion of the space that its interesting to anyone writing real programs. Furthermore, I'd say it has more to do with what you're targeting, rather than the source language. In any case, it captures such a wide space, it's naive to think that it's just a detail. And I'm not sure what compilers you've written, but modern compilers... even less modern compilers, like gcc, use IRs for more than simply that -- unless your definition for binding is exceptionally wide. And even the most primitive compilers use the IR for control flow. Some use it for modeling all possible control flow. Others to capture data flow. Unless your goal is to write an HP 48S calculator or reimplement Scheme, I think you'll need a fair bit more than SICP.
- mahmud 16y agoWhat stack discipline would you use for translating business rules written in pseudo-English sentences to prolog? Compiler construction != native machine code generation.
- kenjackson 16y agoI don't know Prolog very well, and I don't know what this pseudo language structure is like. But one place where you will often see stacks even when compiling down to languages where you think you needn't use it is for handling exceptional and failures, e.g., OOM. At a lower-level, function composition is a form of stack discipline, where ordering is important, but placement less so. In any case, I'm sure you can write a compiler that translates from X to Y, for some X and for some Y, using only Tic-Tac-Toe as your language, with readings from the back of Lucky Charms as the totality of your knowledge base. My point was that to really know compilers, you need to know a bit more than that.
- mahmud 16y agoI actually agree with you that SICP doesn't cover all of compiler construction; but that point didn't need to be made, because not even the book claims to be that. What it is is a gateway drug to serious computing, including compiler construction. However, let me just come back to your point that stack discipline is necessary for control structures and non-local transfer of control. Well, that depends on the execution model of the machine, and I would say explicit stacks are a performance hack, made to model the mathematical concepts of closure and application. -- Sorry, I had to remove my wordy examples explaining "Scope and Extent", and how they can be represented with environment pointers, and heap allocated activation records. TODO: Point yet again to the "3 Implementations of Scheme" paper, Scheme being the cleanest Algol variant this side of modern computing. Then I found this: http://www.cs.man.ac.uk/~pjj/cs211/ho/node14.html http://www.cs.man.ac.uk/~pjj/cs211/ho/node14.html
- jerf 16y ago"stack layout" At this point you've already gone off the rails, because you've implicitly accepted that a compiler is "something that emits machine code". The reason why compilers should be a required course is that people need to realize that compilers that emit machine code are nothing more than a special case of compilers. A very interesting and important one for both practical and historical reasons, but a special case nonetheless. The problem with this definition is that then people think that it's not a big deal that they don't understand compiler theory because it's just for the guys writing gcc and stuff. Wrong, wrong, wrong, wrong, wrong. A compiler is a basic tool in the computer science toolchest and I tend to agree that if you don't get them you shouldn't call yourself a Programmer with a capital P. The definition Steve gives is much more accurate.
- kenjackson 16y agoWrong. Understanding stack layout is much richer than emitting machine code. Admittedly, throwing the term "machine code" around is already a loaded term. Do you mean x86 code? Do you mean Java bytecode or CIL/MSIL? Do you mean C? In any case part of understanding compilers is understanding what you're targeting... unless your only goal is to accept or decline a program for a given language. And if you read the context of my post, my point was exactly what you said regarding pragmatics of understanding compilers. Sure you can say "kill sets are the figment of a design choice relating to languages for which destruction can exist". But that's like saying you know computer architecture, but nothing of registers, TLBs, caches, voltage, pipelining, etc..., because those are simply remnants of a special case of computer architecture, albeit a popular case. If you came to me and said, "I'm a compiler expert" and you knew nothing about stack layout, I'd seriously question your credentials. Maybe I'd be off base, but I'm pretty confident I'd be right a lot more times than not. Update: And I did want to add one more thing on the stack layout discussion. Stack layout is a "fundamental" device in the Turing machine model for handling important language constructs. Sure you can argue that with the lambda calculus you can avoid some of this. But, I still think you miss out on understanding a KEY part of compilers. It would be like leaving CS education and only learning about Turing machines, and never the Lambda Calculus. Obviously, you can rationalize it by saying its completely redundant, But I think most of us would agree that you wouldn't have had a full education.