What is a computational process?
bobu...@yahoo.com
- "We are about to study the idea of a computational process.
Computational processes are abstract beings that inhabit computers. As
they evolve, processes manipulate other abstract things called data.
The evolution of a process is directed by a pattern of rules called a
program. People create programs to direct processes. In effect, we
conjure the spirits of the computer with our spells.
A computational process is indeed much like a sorcerer's idea of a
spirit. It cannot be seen or touched. It is not composed of matter at
all. However, it is very real. It can perform intellectual work. It can
answer questions. It can affect the world by disbursing money at a bank
or by controlling a robot arm in a factory. The programs we use to
conjure processes are like a sorcerer's spells. They are carefully
composed from symbolic expressions in arcane and esoteric programming
languages that prescribe the tasks we want our processes to perform."
What is this? Several alternatives
1. This is a joke
2. Authors try to impress me by talking nonsense
3. There is something I don't understand, but more learned persons do
Since the authors seem to be intelligent, alternative 3 is most
probable.
According to a dictionary a process is
'a natural series of changes'
'a series of actions toward achieving an end'
'operations on data by means of a program'
Let's go back to SICP
- "We are about to study the idea of a computational process"
This seems to say that computational processes are really important.
- "Computational processes are abstract beings that inhabit computers."
This I don't undertand. Abstract things inhabit our brains. Abstract
things are models, simplified pictures we make in our minds so that we
can reason about complex realities by studying our simplified pictures.
Yes, numbers, gravity law, democracy and so on are just models in our
minds, simplified pictures of a complex reality". So the authors must
mean that there are physical things happening inside the computer that
we can model with something they call "computational processes".
- "A computational process is indeed much like a sorcerer's idea of a
spirit. It cannot be seen or touched. It is not composed of matter at
all. However, it is very real. It can perform intellectual work".
This seems like plain nonsense to me, but maybe there are things here I
don't understand.
Why bring this vague idea of process in at all? Why isn't it sufficient
to talk about programs, procedures, data and so on. What do you miss if
you take away the concept of "computational process".
I have used the concept of "computational process" but with other
meaning then SICP.
A computational process is for instance the act of
1. Executing a program
2. Parsing (transforming ASCII strings representing program text and
build higher-level tree representations for the text)
3. Process of detecting and signalling errors.
Bob
Brian Harvey
>Why bring this vague idea of process in at all? Why isn't it sufficient
>to talk about programs, procedures, data and so on. What do you miss if
>you take away the concept of "computational process".
Perhaps it'll help to look at the places in the book where they use "process"
in more specific, less poetic contexts. The two examples I can think of right
offhand are
1. The discussion of tail calling, in which they distinguish between a
"recursive procedure" and a "recursive process."
2. The discussion of concurrency, in which multiple processes might be running
the same procedure at the same time.
These seem to agree, not disagree, with your
>I have used the concept of "computational process" but with other
>meaning then SICP.
>A computational process is for instance the act of
>1. Executing a program
My interpretation of the language you don't like at the beginning of the book
is that they want to call our attention to the running of the program as the
place where the magic happens; the program itself is just another kind of data.
I hadn't thought about the question much before, but now that you call my
attention to it, I think this emphasis helps explain why they think that
interpretation (the second half of the book) belongs in a freshman course.
It's the interpreter that turns the program into a process, so to speak.
bobu...@yahoo.com
You are of course right. But why didn't they just say something like:
"A computational process is the act of executing a program. The
computer has an infinite ability to execute all kind of computational
processes but it will not do it unless you conjure it with the right
spells (that is writing a correct program). In this sense the computer
is like a powerful spirit and when you see it execute it is like real
'magic'."
Then I would have no problems understanding.
Bob
Adam Fabian
reading up through most of chapter 2. It seems like a hard read, not
for conceptual density but for poor authoring. Considering that the
text above was the introduction to chapter 1, ("a section without a
point" in a book where the authors seem to find having a point to be a
challenge even in subsections with very specific headers), I wouldn't
waste too much time mulling it over.
bobu...@yahoo.com
are divided in two camps, those praising the book and those that are
disappointed. I'm in the process of reading the book now and haven't
really made up my mind yet. I have seen some of the free video lectures
and I think they are great (especially those by Hal Abelson). For
instance the strategy for making a language to solve not just the
problem at hand, but a whole bunch of similar problems. Another nice
concept is the "abstraction barriers". The reason I started to look at
Scheme was this concept of not distinguishing between the data and the
procedures. I mean both of them are zeros and ones inside a computer so
why should you make difference between them. That many programming
languages do so, feels like blocking a world of opportunities.
Bob
Marlene Miller
Ulrich Hobelmann
> The reason I started to look at
> Scheme was this concept of not distinguishing between the data and the
> procedures. I mean both of them are zeros and ones inside a computer so
> why should you make difference between them. That many programming
> languages do so, feels like blocking a world of opportunities.
SICP was my first good programming book to read. But with Scheme I
never quite grasped why it's in any way important or even useful that
code and data are the same, lexically (after all, you can write
interpreters in non-sexp languages and for non-sexp languages pretty
well). The book doesn't at all show that advantage, IMHO because it
doesn't use macros at all. For me it took Common Lisp (and associated
reading) to show me why code=data is a cool thing.
For everything else though, I found SICP quite nifty. Most who don't
like it don't really seem to get it (Scheme), which is fine. They "move
on" to "real" languages like Java.
--
Every decent man is ashamed of the government he lives under.
H. L. Mencken
bobu...@yahoo.com
Strange that SICP makes such a big number of code=data when they don't
show the advantage of it. Could you give an example of why code=data is
a cool thing or/and point to some web page or book that exemplifies or
discusses this.
Bob
Ulrich Hobelmann
As I mentioned, one area where code=data is very useful are macros.
This book http://www.gigamonkeys.com/book/ (Common Lisp) has some easy
to read introduction in chapters 7 and 8. IMHO Scheme macros don't
really use the code=data thing, as they don't require (or allow)
explicit manipulation of the generated code, but feel free to show me
nice counter-examples in one of the various macro languages.
Other uses are using s-expressions as data storage (kind of like XML,
only it's much easier to use; just "read" the file). If the file
contains code, you can modify it with Scheme's builtin functions and
maybe call eval (ok, that's ugly). Anyway you leverage lisp, or list,
manipulation functions to access and maybe modify general semistructured
data, and thus perhaps code in whatever language you represent as such data.
--
the bottom line is that a JavaSchool that won't teach C and won't teach
Scheme is not really teaching computer science, either. -- Joel Spolsky
Pascal Costanza
Read Paul Graham's On Lisp, available at
http://www.paulgraham.com/onlisp.html
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Jens Axel Søgaard
> bobu...@yahoo.com wrote:
>
>> The reason I started to look at
>> Scheme was this concept of not distinguishing between the data and the
>> procedures.
Procedures are data. Data is not always procedures.
>> I mean both of them are zeros and ones inside a computer so
>> why should you make difference between them. That many programming
>> languages do so, feels like blocking a world of opportunities.
> SICP was my first good programming book to read. But with Scheme I
> never quite grasped why it's in any way important or even useful that
> code and data are the same, lexically (after all, you can write
> interpreters in non-sexp languages and for non-sexp languages pretty
> well).
> The book doesn't at all show that advantage, IMHO because it
> doesn't use macros at all.
In my view interpreters and compilers are the prime examples of
programs that utilizes that code is data. And SICP does spend quite a
few pages on writing interpreters and compilers.
--
Jens Axel Søgaard
Brian Harvey
>I found the book to be needlessly verbose, desultory, and dry from
>reading up through most of chapter 2. It seems like a hard read, not
>for conceptual density but for poor authoring.
Some of my students say things like this, but usually not the "verbose" part;
SICP is criticized for not being verbose enough if you don't already get the
central ideas.
But when I met the book (15 or 20 years into a programming career) it was an
incredible eye-opener, the first book that really made big ideas the center of
attention rather than technical details. I imagine some of the critics of
SICP in this group (as opposed to critics among my beginning students) must
have grown up on the children-of-SICP books and don't really understand what a
revolution SICP was, back when it was all alone, like modern teenagers who
don't really get why their elders make such a fuss about the Beatles.
You'd think that the children-of-SICP ought to be better than it, having the
advantage of the big ideas layed out for them, plus the authors' experiences
reading SICP and remembering what was hard for them to follow in the text.
But (ymmv) none of them has conveyed the same excitement to me that SICP does,
with the possible exception of (the non-Scheme-based) Van Roy and Haridi.
(That doesn't mean I think the others are bad books, or useless, etc.!)
Anton van Straaten
> Thanks Brian,
> You are of course right. But why didn't they just say something like:
>
> "A computational process is the act of executing a program.
This doesn't capture the idea of a computational process as an
independent entity (or "being"), which is an important concept
communicated by the SICP passage which you quoted.
> The
> computer has an infinite ability to execute all kind of computational
> processes but it will not do it unless you conjure it with the right
> spells (that is writing a correct program). In this sense the computer
> is like a powerful spirit and when you see it execute it is like real
> 'magic'."
>
> Then I would have no problems understanding.
But that doesn't communicate everything that the SICP version does. The
first part of the SICP passage provides at least five important facts
about computational processes, which provide answers to the following
questions:
1. What kind of entities (or "beings") are computational processes?
2. Where do computational processes reside?
3. What do computational processes manipulate as they evolve?
4. What directs the evolution of a process?
5. Why do people create programs?
The second part of the passage provides a more metaphorical
characterization of these facts. Such characterizations can be very
important -- it isn't really possible to understand something new
without reference to something else that you already understand. In
this particular case, the metaphor is used to underscore some of the
facts alluded to above, such as that computational processes are
abstract entities: it is pointed out that they "cannot be seen or
touched", and that they are "not composed of matter at all". However,
it is then pointed out that despite their abstract nature, such
processes are nevertheless "very real", and gives examples of how that
is the case.
Your version provides a summary using the metaphor, but doesn't cover as
many facts about the nature of processes and programs.
SICP is packed with information. If something doesn't make sense to you
the first time you read it, it probably means that you should either
read it again more carefully, or come back to it later when you've
learned more.
But if you find SICP is just not your style, as some apparently do, then
you might find www.htdp.org useful, or as already mentioned,
http://www.cs.indiana.edu/eopl/.
Anton
alex...@gmail.com
Anton van Straaten
> Please don't feed the Common Lips trolls! >:-0
?*}
Pascal is right, "On Lisp" is an excellent book on the subject...
Ulrich Hobelmann
> Please don't feed the Common Lips trolls! >:-0
I guess most CL users are a bit biased in that direction. :(
I'd actually like a Schemer to take on the code=data subject, and maybe
the macro subject as well (how do you develop a lex or yacc macro in
Scheme?), but as long as nobody does...
Ulrich Hobelmann
>> The book doesn't at all show that advantage, IMHO because it doesn't
>> use macros at all.
>
> In my view interpreters and compilers are the prime examples of
> programs that utilizes that code is data. And SICP does spend quite a
> few pages on writing interpreters and compilers.
It does, and quite well, IMHO. But i never quite saw why the being
Scheme was an advantage there. Later, when I learned SML, I found some
things even easier in the interpretation area, but in ML you
pattern-match constructors, instead of EQ-ing symbols, so it'd be hard
to do something like macros there. (Actually, the point where I decided
to kind of quit ML was when I needed something to EQ constructors but it
wasn't there; instead I had to write an explicit comparator function for
the whole datatype, ugh.)
Jens Axel Søgaard
> alex...@gmail.com wrote:
>
>> Please don't feed the Common Lips trolls! >:-0
>
> I guess most CL users are a bit biased in that direction. :(
>
> I'd actually like a Schemer to take on the code=data subject, and maybe
> the macro subject as well (how do you develop a lex or yacc macro in
> Scheme?), but as long as nobody does...
?
--
Jens Axel Søgaard
Pascal Costanza
> alex...@gmail.com wrote:
>
>> Please don't feed the Common Lips trolls! >:-0
>
> I guess most CL users are a bit biased in that direction. :(
>
> I'd actually like a Schemer to take on the code=data subject, and maybe
> the macro subject as well (how do you develop a lex or yacc macro in
> Scheme?), but as long as nobody does...
There are quite a few Scheme-related papers available at
http://library.readscheme.org/page3.html
I also recall reading a historical overview of macro systems for Scheme
that was posted here or in a mailing list which was interesting.
Paul Graham's "On Lisp" is an excellent book because it focuses on how
to write one's own macros. Although the book focuses on Common Lisp, it
also refers to Scheme quite a few times, and most of the material should
be interesting for, and understandable by, Schemers as well. I am not
aware of such a comprehensive coverage for Scheme macro systems, but
would be very happy to hear about it.
Jens Axel Søgaard
> Jens Axel Søgaard wrote:
>
>>> The book doesn't at all show that advantage, IMHO because it doesn't
>>> use macros at all.
>>
>> In my view interpreters and compilers are the prime examples of
>> programs that utilizes that code is data. And SICP does spend quite a
>> few pages on writing interpreters and compilers.
>
> It does, and quite well, IMHO. But i never quite saw why the being
> Scheme was an advantage there.
How many lexers do they write in SICP?
--
Jens Axel Søgaard
Anton van Straaten
> I'd actually like a Schemer to take on the code=data subject, and maybe
> the macro subject as well (how do you develop a lex or yacc macro in
> Scheme?), but as long as nobody does...
You might find "Lexer and Parser Generators in Scheme" of interest:
http://library.readscheme.org/servlets/cite.ss?pattern=sw2004-owens
It describes the implementation of a macro-based lexer and parser
system. There's a related implementation in PLT Scheme.
The paper also has a nice summary (section 2.3) of other parser
approaches in Scheme, including for example Essence:
http://www.informatik.uni-freiburg.de/proglang/software/essence/
...which uses partial evaluation, instead of macros, to generate
parsers. This is a good reminder that "code is data" is a bigger
concept than "just" macros. Like macros, partial evaluation treats
programs as input to other programs, and produces programs as output,
dealing with code=data in a different way than traditional macros.
Anton
Ulrich Hobelmann
What I was trying to say is that apart from macros that can generate
code (i.e. Common Lisp, PLT Scheme, but not standard Scheme) I haven't
yet seen an example or demonstration that showed me why code=data is a
cool thing for Scheme.
Anton's mention of partial evaluation below is interesting, although I
don't know enough of how it works exactly to know if code=data plays a
big role there. I'd imagine it being roughly similar to interpretation,
though without direct execution involved.
Ulrich Hobelmann
> Ulrich Hobelmann wrote:
>> I'd actually like a Schemer to take on the code=data subject, and
>> maybe the macro subject as well (how do you develop a lex or yacc
>> macro in Scheme?), but as long as nobody does...
>
> You might find "Lexer and Parser Generators in Scheme" of interest:
>
> http://library.readscheme.org/servlets/cite.ss?pattern=sw2004-owens
>
> It describes the implementation of a macro-based lexer and parser
> system. There's a related implementation in PLT Scheme.
Yes, but that's PLT macros, which seem to be able to create arbitrary
code (the paper mention syntax-rules, but it doesn't really explain the
actual code generation phase for the DFAs). I'm not sure standard
Scheme macros can do all the work of that.
Maybe my impression is wrong, but for some reason Scheme macros never
quite got into my head, just like parts of Haskell; I felt too much
tied up and deprived of freedom.
Ulrich Hobelmann
I don't remember if they do write one. Probably not, and that's what
the READ function gives you. But most work in a program isn't (or
shouldn't be) in the parsing stage, so I don't consider that a
particularly huge advantage (though I do like it). Writing a lisp
parser yourself in any other language isn't too much work to do. I'd
look at other language features that make my life easier, in the real
work part.
Lauri Alanko
B. C. Smith's dissertation, Section 1.c (p. 50) in particular.
http://www.lcs.mit.edu/publications/specpub.php?id=840
But if you didn't like the style in SICP's introduction, you perhaps
won't like Smith's somewhat rambling style either...
Lauri
Jens Axel Søgaard
> What I was trying to say is that apart from macros that can generate
> code (i.e. Common Lisp, PLT Scheme, but not standard Scheme) I haven't
> yet seen an example or demonstration that showed me why code=data is a
> cool thing for Scheme.
The "code is data" idea comes in two flavors so to speak. The important
one is that programs can manipulate other programs. This is what SICP
demonstrates by writing interpreters and compilers. On a lower level a
von Neuman machine can't see whether a particular number in its memory
represents a machine instruction or a piece of data.
When someone states that Scheme/Lisp is well suited to expolit that code
is data, there are two possibilities. One is that the language has a
lexer/parser builtin in terms of READ and that is easy to manipulate the
syntax tree in the language. The other possibility is that they are
thinking of macros, which builds upon the ease language supports
manipulation of s-expressions. None of these properties are exclusive to
Scheme though. The idea of macros doesn't even hinge on using
s-expressions, which is witnessed by how other languages has adopted the
ideas from Scheme/Lisp (see e.g. [1]).
Btw - in my world "Scheme" doesn't equal "R5RS Scheme", but rather the
"Scheme family".
> Anton's mention of partial evaluation below is interesting, although I
> don't know enough of how it works exactly to know if code=data plays a
> big role there. I'd imagine it being roughly similar to interpretation,
> though without direct execution involved.
See Darius Bacon's excellent introduction:
<http://web.archive.org/web/20050218210258/http://www.lisp-p.org/htdocs/peval/peval.cgi>
[1] "Growing Languages with Metamorphic Syntax Macros"
Claus Brabrand and Michael I. Schwartzbach
<http://www.brics.dk/RS/00/24/BRICS-RS-00-24.pdf>
--
Jens Axel Søgaard
Jens Axel Søgaard
> I don't remember if they do write one. Probably not, and that's what
> the READ function gives you. But most work in a program isn't (or
> shouldn't be) in the parsing stage, so I don't consider that a
> particularly huge advantage (though I do like it).
Who said it were :-)
> Writing a lisp
> parser yourself in any other language isn't too much work to do. I'd
> look at other language features that make my life easier, in the real
> work part.
Presumably you'd need an X-parser in X and not a Lisp-parser in X.
--
Jens Axel Søgaard
Ulrich Hobelmann
> When someone states that Scheme/Lisp is well suited to expolit that code
> is data, there are two possibilities. One is that the language has a
> lexer/parser builtin in terms of READ and that is easy to manipulate the
> syntax tree in the language. The other possibility is that they are
> thinking of macros, which builds upon the ease language supports
> manipulation of s-expressions. None of these properties are exclusive to
> Scheme though. The idea of macros doesn't even hinge on using
> s-expressions, which is witnessed by how other languages has adopted the
> ideas from Scheme/Lisp (see e.g. [1]).
Ok.
> See Darius Bacon's excellent introduction:
>
> <http://web.archive.org/web/20050218210258/http://www.lisp-p.org/htdocs/peval/peval.cgi>
Sweet. Thanks.
Neelakantan Krishnaswami
>
> Yes, but that's PLT macros, which seem to be able to create arbitrary
> code (the paper mention syntax-rules, but it doesn't really explain the
> actual code generation phase for the DFAs). I'm not sure standard
> Scheme macros can do all the work of that.
>
> Maybe my impression is wrong, but for some reason Scheme macros
> never quite got into my head, just like parts of Haskell; I felt too
> much tied up and deprived of freedom.
They certainly can; syntax-rules macros are Turing-complete. However,
it's really, really painful to do so. The reason for that is that they
are a rewriting system, and so you can't easily build "macro
functions" using syntax rules, which makes it extremely painful to
write a large macro in a modular way.
Jonathan Bachrach and Keith Playford wrote a paper that suggested a
way to add direct macro calls to Dylan's macro system (which is very
similar to Scheme's) -- look at Appendix B of their paper
"D-Expressions: Lisp Power, Dylan Style".
<http://people.csail.mit.edu/jrb/Projects/dexprs.pdf>
--
Neel Krishnaswami
ne...@cs.cmu.edu
Anton van Straaten
> Anton van Straaten wrote:
>
>> Ulrich Hobelmann wrote:
>>
>>> I'd actually like a Schemer to take on the code=data subject, and
>>> maybe the macro subject as well (how do you develop a lex or yacc
>>> macro in Scheme?), but as long as nobody does...
>>
>>
>> You might find "Lexer and Parser Generators in Scheme" of interest:
>>
>> http://library.readscheme.org/servlets/cite.ss?pattern=sw2004-owens
>>
>> It describes the implementation of a macro-based lexer and parser
>> system. There's a related implementation in PLT Scheme.
>
>
> Yes, but that's PLT macros, which seem to be able to create arbitrary
> code
More generally, it is the syntax-case macro system, which is quite
standard in Scheme, if not "standardized". Syntax-case can be found in
Chez, Chicken, Gambit, PLT, SISC, and other implementations.
> (the paper mention syntax-rules, but it doesn't really explain the
> actual code generation phase for the DFAs). I'm not sure standard
> Scheme macros can do all the work of that.
By "standard Scheme macros", I assume you mean syntax-rules, but that's
an arbitrary and impractical restriction. Syntax-rules is a very simple
system, with a pretty focused purpose -- implementing fully hygienic
macros using pattern matching and rewriting. It's not designed to do
everything that systems like syntax-case and defmacro can do.
> Maybe my impression is wrong, but for some reason Scheme macros never
> quite got into my head, just like parts of Haskell; I felt too much
> tied up and deprived of freedom.
If you expected syntax-rules to give you everything that defmacro does,
that might explain your reaction. If you'd like to learn more about
Scheme macros, try Kent Dybvig's paper, "Writing Hygenic Macros in
Scheme with Syntax-Case", at:
http://www.cs.indiana.edu/~dyb/pubs/tr356.pdf
There are additional resources at:
http://www.cs.indiana.edu/chezscheme/syntax-case/
...and in TSPL: http://www.scheme.com/tspl/
At the very least, this will provide a much deeper perspective on
code=data than anything you can get from experience with defmacro.
Defmacro treats code almost as raw data, without "understanding" it,
beyond its list-based tree structure. In defmacro, it is entirely up to
the programmer to deal with the actual meaning of the code.
Systems like syntax-case provide syntax comprehension features, and
mechanisms for safely controlling the scope of identifiers introduced or
captured by macros. To support these features, it also provides an
abstract data type for syntax, which provides other benefits, such as
supporting the clean integration of code location information into the
syntax representation.
Syntax-case can be thought of as defmacro with lists-as-syntax replaced
by an ADT, plus a few optional but very commonly used features: syntax
pattern matching and rewriting, and hygiene control.
It's kind of like defmacro 2.0.
Anton
Max Hailperin
Abstractions, as another place you might look, because that book is
now available for free, so I don't stand to gain anything:
http://www.gustavus.edu/+max/concrete-abstractions.html
In particular, my co-authors and I provide two somewhat less poetic
descriptions of "computational process" than SICP does: one in the
Preface and one in Section 1.1.
I suspect either of these would come closer to what you are looking
for without completely losing the spirit of SICP.
Beyond this one term, though, I don't think Concrete Abstractions will
satisfy your desire for crisp definitions any more than SICP does --
at best, it might give an alternative set of examples that helps you
understand the way the vocabulary is used. When I showed a manuscript
of the book to my father, a mathematical logician, he said something
like "I see you have decided to teach the language by taking the
students to the country where they speak it." I don't think that he
meant that as a criticism; even though his own professional career has
contained more than its share of formal definitions, he recognizes the
value of immersion for learning natural languages, and was willing to
entertain the notion that it might make sense for an introductory
computer science textbook. -Max Hailperin
bobu...@yahoo.com
Very Good book. I've seen in several books that claim that study of
interpreters and compilers is a key to understanding computers and
becoming a good programmer. Without being abla to say why, this sounds
true. Why is this so?
Bob
Pascal Bourguignon
Because processors are but "interpreters" of the microcode. They are
all Turing-equivalent. There is no difference of nature between an
interpreter, a virtual machine or a chip implementing a "processor".
The fact that compilers exist is the proof: you can translate programs
for one language=machine to another.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
Marlene Miller
> Why bring this vague idea of process in at all? Why isn't it sufficient
> to talk about programs, procedures, data and so on. What do you miss if
> you take away the concept of "computational process".
Here are two contrasting perspectives on SICP (familier to Schemers, but
maybe not to the OP):
"The most important books are those that change the way one looks at the
world. So we will begin our reading list with two books in this category.
The first is _Structure and Interpretation of Computer Programs_, by Hal
Abelson and Gerry Sussman with Julie Sussman (1985; 1996). This is a
challenging introduction to programming that emphasizes general
problem-solving techniques and uses Scheme throughout. We often list this
book as a required text in our courses, just because every computer
scientist and programmer should read it. [...]"
- EOPL, Appendix B For Further Reading, Friedman, Wand, Haynes
Felleisen, Findler, Flatt, Krishnamurthi
( Journal of Functional Programming )
The Structure and Interpretation of the Computer Science Curriculum
PS PDF
(from http://www.ccs.neu.edu/scheme/pubs/)
(It is interesting to notice that the authors of The Little Schemer are
Daniel Friedman and Matthias Felleisen)
Marlene Miller
>
> Very Good book. I've seen in several books that claim that study of
> interpreters and compilers is a key to understanding computers and
> true. Why is this so?
Gulp!
1. I very much want to know/understand the answer to your question.
comp.lang.c++.moderated EOPL May 31 2004, 4:04 am :
http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/536fe06492437f2a/fb48ad5f3b8246d6?q=EOPL&rnum=1#fb48ad5f3b8246d6
comp.lang.scheme creating a procedure May 25, 2004 10:49 am:
http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/399a9d7bd53636dd/3bda12702c4cfc61?q=compiler&rnum=141#3bda12702c4cfc61
2. I've decided the only way I am going to find out is to live with the
natives.
I followed a course that guided me through the writing of an interpreter (6
assignments in 3 weeks, lots of fun and recommended).
http://web.cs.swarthmore.edu/~meeden/cs22/s03/cs22.html
Now I am studying EOPL. When I finish I might also study PLAI
(Krishnamurthi).
(I am also studying the dragon book. I think it helps.)
3. So far, I am not so sure it will help us to become better programmers. (A
heresy.) In my opinion, the people I regard as the best programmers in the
everyday real world are able to invent meaningful abstractions (not
necessarily OO). They see things a level above the nitty-gritty problem.
However, in the forward to EOPL, Hal Abelson says "If you don't understand
interpreters, you can still write programs; you can even be a competent
programmer. But you can't be a master". You can read the whole forward here
http://www.cs.indiana.edu/eopl/
There is one curious idea in SICP about "metalinguistic abstractions"
(Chapter 4). In EOPL forward, Abelson mentions embedded sublanguages.
Brian Harvey
>3. So far, I am not so sure it will help us to become better programmers. (A
>heresy.) In my opinion, the people I regard as the best programmers in the
>everyday real world are able to invent meaningful abstractions (not
>necessarily OO). They see things a level above the nitty-gritty problem.
I think that inventing abstractions is the point. There are degrees of
complexity of abstractions. At the lowest level are trivial data abstractions
such as representing a rational number as a pair of integers. At the highest
level, though, are special-purpose "little languages"; you can't invent those
unless you understand what an interpreter is and how to write one.
Well, I guess the *highest* level is a *general*-purpose language using a new
paradigm, like Lisp or Smalltalk or Prolog.
As for compilers, I think they're all about efficiency; knowing how a compiler
works doesn't increase your ability to express ideas (supposing you already
understand interpreters), but perhaps it makes it more likely that your
programs will actually get the job done reasonably quickly. This is
especially true in these days of multilevel caching, when the key optimization
may be to rearrange things in memory rather than to attack the order of growth
of the algorithm.
Prabhakar Ragde
> At the highest
> level, though, are special-purpose "little languages"; you can't invent those
> unless you understand what an interpreter is and how to write one.
This isn't strictly true; I think some knowledge of Scheme macros will
suffice, at least at the beginning. But I agree that understanding
interpreters and being able to implement them is a superior approach. --PR
--
Prabhakar Ragde, Professor plragde at uwaterloo dot ca
Cheriton School of Computer Science http://www.cs.uwaterloo.ca/~plragde
Faculty of Mathematics DC 1314, (519)888-4567,x4660
University of Waterloo Waterloo, Ontario CANADA N2L 3G1
Anton van Straaten
> <bobu...@yahoo.com> wrote in
>
>>Very Good book. I've seen in several books that claim that study of
>>interpreters and compilers is a key to understanding computers and
>>becoming a good programmer. Without being able to say why, this sounds
>>true. Why is this so?
>
>
> Gulp!
>
> 1. I very much want to know/understand the answer to your question.
Brian Harvey gave an excellent answer to this earlier:
"It's the interpreter that turns the program into a process, so to speak."
Programs are static things -- just data. If the data was all there was
to programs, they wouldn't be all that interesting. It's the fact that
programs can be used to generate processes, and the processes that they
generate, that makes programs interesting. And as Brian says, it's the
interpreter that actually generates the processes from a program.
To understand computers and programming, you certainly need to
understand both programs and processes. To do that, you need some kind
of understanding of the link between the two.
Imagine there were no machine-executable interpreters, and you're to
trying to understand what a program is supposed to do, given the rules
of the language it's written in. You have to reason about the program,
at least partly interpreting it in your head, or on paper. So you
become the interpreter. This shows that it's impossible to understand
programs and processes without interpreters, even if the interpreter is
only in your head.
Even programmers who haven't studied interpreters develop an intuitive
understanding of the link between programs and processes. They do this
in two main ways: by reasoning about programs, i.e. interpreting them in
their head; and by using an interpreter as a black box to generate
processes, watching what those processes do, and learning from them.
Using an interpreter as a black box is not always as enlightening as one
might hope -- you see the inputs and outputs, but you don't necessarily
know exactly how the input was turned into the output. Reasoning about
programs is more enlightening, because now instead of residing in an
external machine, the black box of the interpreter is in your mind.
This still leaves something to be desired. I doubt any of us would
claim to be competitive with even a very small, slow CPU when it comes
to interpreting most real programs. Also, our mental interpretation
tends to be full of gaps, because we can always rely on the crutch of a
machine-executable interpreter when the going gets tough. But that's
also often exactly where things gets interesting! This means that the
gaps in our knowledge about the program-process link are quite likely to
occur in some of the most important areas.
So, the only way to really fill in our knowledge of that important link
is to study interpreters themselves.
Anton
Joe Marshall
Anton van Straaten wrote:
> I doubt any of us would
> claim to be competitive with even a very small, slow CPU when it comes
> to interpreting most real programs. Also, our mental interpretation
> tends to be full of gaps, because we can always rely on the crutch of a
> machine-executable interpreter when the going gets tough. But that's
> also often exactly where things gets interesting! This means that the
> gaps in our knowledge about the program-process link are quite likely to
> occur in some of the most important areas.
Not competitive in terms of raw instruction execution, but human beings
can do things
like interpret buggy and incomplete programs (determine the *intended*
correct result
rather than the actually computed one). Humans don't seem to have as
much difficulty
as computers do when attempting to determine if a program halts or not.
Marlene Miller
> Imagine there were no machine-executable interpreters, and you're to
> trying to understand what a program is supposed to do, given the rules
> of the language it's written in. You have to reason about the program,
> at least partly interpreting it in your head, or on paper. So you
> become the interpreter. This shows that it's impossible to understand
> programs and processes without interpreters, even if the interpreter is
> only in your head.
What goes on in my head when I read a program does not seem similar to the
SICP interpreter I implemented for a class. I visualize a memory space
similar to what I see when I use the debugger - a stack, a heap, registers.
When I want to understand a language feature, I sometimes look at the
compiled instructions. I step through the instructions to watch the process.
I used to assume I had to understand the compiled code, the architecture of
the machine and the electronics. People at this forum explained to me the
compiled instructions are another language. The hardware might be an
interpreter for that language.
Is the C++ Standard an informal way of describing how an interpreter
evaluates the source code? Will the interpreters of EOPL explain everything
in the C++ Standard?
Tom Lord
statement that a computational process "is not composed of
matter at all". A more subtle confusion is that while data and
processes are both mentioned, signals are not (except by
unexplained implication of the remark that computational
processes can disburse money at a bank or control a robot arm).
It is true that all programs studied in SICP are composed from
symbolic expressions that prescibe tasks but that is a poor
description of programs in general.
My instinct, if I were writing such a book, would be to make the
introduction harder to get but more accurate. Something like:
In this book we will study computer programs, written in
symbolic programming languages, prescribing discrete
computational processes. Let's start by informally explaining
what these words mean.
* Computational Processes
A "computational process" in general is a way to abstractly
describe the behavior, over time, of certain physical systems.
In ordinary physics we most often describe physical processes
directly in terms of those fundamental laws of matter and time
that most directly apply. For example, if describing a system
of gears we might quantify the mass of the gears, friction of
the materials, and how they are configured. From those we
might compute how much force needs to be applied to rotate
gear A in order to advance gear B by a certain amount.
When studying computational processes, we are interested in a
different abstract view -- we are interested in the way a
system processes information. We might note, for example,
that each second the system receives an input signal (from a
swinging pendulum) and that from the state of the system,
output can be read: the position of gear A records the number
of seconds since some earlier time, modulo 43,200 (the number
of seconds in 12 hours) while gear B records the number of
seconds since that same time, modulo 3,600 (the number of
seconds in 1 hour).
The computationally interesting aspect of this physical
system, in this context, is that given a regular input signal,
it adds up seconds to compute the current time, according to a
12hr clock.
A very useful aspect of working with abstractions which are
computational processes rather than simple physical processes
is that we can recognize many cases where very different
physical systems are, in spite of their differences,
performing the same computation. My electronic wristwatch may
have no gears at all and so the equations of force used to
study my pendulum clock don't apply. But one computational
model of at least part of my wristwatch notes that it, too,
receives a signal once per second and counts those ticks
modulo 43,200 and modulo 3,600. The same analysis that tells
me what my pendulum clock will read after 500 clicks also
tells me what my wristwatch will read after 500 clicks.
As an engineering concern, we have discovered that is very
useful for people to be able to specify an abstract
computational process and then efficiently realize it as a
physical process that performs that computation. Modern
computers are devices designed to enable that translation from
abstract specification to physical realization. The programs
we will study are symbolic texts representing specifications
of computational processes. We'll be studying the form these
specifications take and some of the best techniques for
writing them. To make sure we understand how to do this well
we'll be looking at how our programs are translated into
physical processes -- how they are interpreted to perform
actual computations.
* Discrete Computational Processes
When we talk about computational processes we'll generally
find it useful to discuss their internal state, their input
signals, and their output signals. In our pendulum clock
example, the internal state is the position of the gears at a
given time. The I/O signals are the swings of the pendulum
and the positions of hands mounted on the gears, again,
varying over time.
Broadly speaking, those are ways to describe the information
recorded in the system as well as the information received and
transmitted.
A useful distinction can be made between *continuous* and
*discrete* signals and internal states. For example, in our
clock example, for the purpose of our analysis, the gears are
at every time in one of 311,040,000 possible states. At a
given instant, the pendulum is in one of two states: a "tick"
is occuring at this instant or a tick is not occuring. As far
as we are concerned, the gears advance instantaneously and in
discrete steps -- there are no quantities in our analysis that
vary continuously over time. In contrast, in electrical
engineering, a transistor used as an amplifier is (for the
purpose of analysis) performing a continuous computational
process, at least under normal operating conditions: the input
and output signals vary continuously over time.
People build and program devices for both continuous and
discrete computational processes but there is very little
overlap between these fields. In this book we will be
concerned exclusively with discrete computational processes.
* Symbolic Programming Languages
We've built up an informal model of discrete computational
processes: they are time-varying properties physical systems
with discrete internal state, receiving discrete input signals
and transmitting discrete output signals; the way we are
interested in analyzing these processes revolves not around
the fundamental physics of how they operate so much as the
*information* they receive, store, transform, and transmit.
Modern general purpose computers are devices constructed to be
inexpensively reconfigurable. Once in a given configuration,
they become an instance of a physical process realizing a
particular abstract computational process.
Symbolic programming languages are formal, mathematical
dialects for describing computational processes. We will be
studying languages designed in such a way that a statement in
one of these languages -- a specification of a computational
process -- can be automatically transformed into a
configuration of a general purpose computer. As software
engineers we develop specifications of desired computational
processes, refine those into programs written in symbolic
programming languages, and then execute those programs on
computers -- translating the specification into an actual
configuration of the real machine.
We'll be studying how programs translate to configurations
because understanding how that translation works is essential
to writing good programs (programs that give the desired
answers in an acceptable amount of time consuming an
acceptable amount of resources).
Within that context we'll also be studying "elements of style"
-- how best to organize a program, and why, given
considerations such as: the specification for the program may
change over time -- some programs are more adaptable to
changing specifications than others; the program may later
become a small part of a still larger program -- some programs
are more re-usable than others; and, very importantly, the
idea for a program may be very difficult to translate
accurately into a correct program -- some programs are easier
to verify the accuracy of than others.
I know that that's long-winded and a bit stiff. It could sure
be spiced up with hyperlinks to, for example, material on analog
computers or material on Babbage/Lovelace.
I'll be embarassed if there's a real boner of a misstatement in
it but I'd like to know if there is.
One thing I like about what I wrote is that I think it serves
well not just as a launching point for SICP but also for a lot
of more advanced stuff too -- even though I tried to keep it
informal and intuitive. I think that's a half-decent conceptual
framework to start from and go to automata theory, programming
language semantics of all sorts, complexity theory, and
real-time systems, at least.
BTW, and this indirectly speaks to Brian Harvey's comments in
this thread:
I like SICP a lot too and was also one of the first-generation
readers of the book. However, my experience of the book is
definately not that of the intended target audience. To me, 90%
of the material was, by that point, purely review and notational
cleanup. I was impressed at the economy of the book -- packing
a hefty amount into so few pages while no one part of it was
suddenly overwhelming.
To me, SICP did an 80% job of summing up (and presumably
replacing) the lasting lessons I'd gotten from a small set of
earlier books ranging from 1980s intros to assembly language
programming on micro-computers to lots of lisp-community
effluvia (papers, manuals, word-of-mouth folklore) to (what I
recall as but no longer possess) Wirth's original version of
algorithms+datastructures=programs (whatever book I'm thinking
of it was by Wirth and the critical thing for me was that it
walked through the design and implementation of a compiler for
at least a subset of Pascal -- meta-circularity on the cheap).
-t
Anton van Straaten
> "Anton van Straaten" <an...@appsolutions.com> wrote
>
>
>>Imagine there were no machine-executable interpreters, and you're to
>>trying to understand what a program is supposed to do, given the rules
>>of the language it's written in. You have to reason about the program,
>>at least partly interpreting it in your head, or on paper. So you
>>become the interpreter. This shows that it's impossible to understand
>>programs and processes without interpreters, even if the interpreter is
>>only in your head.
>
>
> What goes on in my head when I read a program does not seem similar to the
> SICP interpreter I implemented for a class.
There are an infinite number of ways to compute anything, so this isn't
surprising, and of course there's a reason for it:
> I visualize a memory space
> similar to what I see when I use the debugger - a stack, a heap, registers.
> When I want to understand a language feature, I sometimes look at the
> compiled instructions. I step through the instructions to watch the process.
Right, so you're simulating the hardware in your mind, sometimes using
the machine to assist, and interpreting programs in terms of the
hardware. This is quite common, of course, but not necessarily the most
effective approach.
> I used to assume I had to understand the compiled code, the architecture of
> the machine and the electronics. People at this forum explained to me the
> compiled instructions are another language. The hardware might be an
> interpreter for that language.
>
> Is the C++ Standard an informal way of describing how an interpreter
> evaluates the source code? Will the interpreters of EOPL explain everything
> in the C++ Standard?
EOPL should give you many of the tools you need to explain the C++
standard, but the nature of C++ does require an understanding of at
least an idealized machine. I don't think EOPL alone provides this.
However, what EOPL and similar books provide is an understanding that
the conceptual similarities between different languages can be dealt
with at a higher level than mentally translating them to roughly the
level of a machine. Translating to the machine level too early tends
to create a trees vs. forest problem, and doesn't help you deal with the
commonality between languages.
Anton
H.
>>What is this? Several alternatives
>>1. This is a joke
>>2. Authors try to impress me by talking nonsense
>>3. There is something I don't understand, but more learned persons do
I believe there is a fourth alternative, which is that different people
have ways of stating things. Some people like to be very poetic, and
stretch conventional meanings of words to their limit or even extend
them somewhat. Other people state things in a more literal way and
prefer a more "be a little less poetic about things" approach.
I speak as someone from the second camp. It's not that I can't
understand why is being said in the first few paragraphs of SICP; I'm
just the type of person who prefers a little less talk about sorcerers,
spirits, and spells. But I didn't write the book, and the thing about
writing any given book is that it's the author's discretion to use
exactly which style s/he chooses.