Programming Languages (CS302 2006S)

Notes on the Semantics of Scheme, Part 2

Comments on:

Kelsey, R., Clinger, W., and Rees, J. (Eds). (1998). Revised5 Report on the Algorithmic Language Scheme. Section 7.2

Comments from: Peter Brown, Michael Claveria, Davis Hart, Alex Leach (-), Brad Miller, Angeline Namai, Mark Nettling, Dimitar Tasev, David Ventresca.

I did the reading for Friday for Wednesday's class, so I have no new comments.

The most of the reading for tomorrow's class is rather straightforward once you helped us get in the mood of thinking of programming languages in terms of math. It seems to cover the definition of if-then-else, if-then, aliasing, empty expressions/commands, and encapsulation of expressions (commands) within other expressions (commands).

When you told us to think about the reason for having three definitions of lambda, pg 41 is what I read and commented on. After reading the script definitions a few more times, I can't say that I feel more enlightened about these definitions. That is not to say that I'm not getting better at reading the lambda calculus-form definitions, but more that it is still difficult to read and comprehend. I do understand the underlying ideas that we've been talking about, but again (much like the problem I had with continuations) I'm not entirely certain I could generate lambda calculus definitions of functions on my own. Perhaps that will come with time. One new question I do have about the definitions on pg 41 is, about the meaning of the parenthecized syntax between tievalsrest and (#I*) in the second lambda definition? I don't understand the differences between the similar statement in the first definition and this definition. Other than that I believe I get the rest of it. I am still having a load of trouble mentally parsing the notation, it seems very foreign to me. However, I understand some of the fundamentals of each function. I think I would have a much easier time without all the Greek symbols being mashed together, and also if more significantly named variables were used instead of Greek letters. For instance, a confusing bit for me was in the set! function. What is the purpose / significance of the epsilon after "assign (lookup p I)"?

Note that assign takes three parameters: a location, an expressed value (the value to store in the location), and a continuation (that is, what to do afterwards). It returns a new continuation that includes the assignment. Hence, the epsilon represents the value to be stored.

Could you please go over the difference between set! and set-car!? I think you mentioned it in class, but I am still not sure why we need both.

set! changes the memory location associated with a name (that is, it changes the environment). set-car! changes the first element of a pair.

In the definitions of onearg and twoarg what is the snake looking symbol and what does it mean?

The authors need a notation for the first parameter in both functions, so they use a new symbol. It's a lowercase zeta. In the first case, it represents a value of type E->K>C. In the second, it represents a value of type E->E->K>C.

permute is a bunch of expressions mapped to a bunch of expressions. Don't they have to be of the same number and just in a different order similar to a permutation? Exp*->Exp* doesn't seem to be enough to support this. Does the wording implementation dependent account for this?

There's an assumption that the reader knows what permute means, as does the implementer. Note that there's a discussion in the R6RS group as to whether the order of evaluation should be specified, rather than left unspecified.

Why are wrong and new also implementation dependent?

The implementers do not want to limit the memory allocation mechanism, so new must be implementation dependent. They also don't want to specify how errors are returned (e.g., is a message printed, a dialog box shown, whatever), so wrong is also implementation dependent.

Why does tievalsrest need natural numbers in its definition: (L*->C) -> E* ->N ->C?

While I do not have a firm idea of exactly what is happening every step of the way I do have a vague idea, which while not much is at least progress over what I had before. From what I can tell the major difference between the structure of the two (since the third is a special case of the second) is that the first has tievals and the second has tievalsrest, and from what I can tell the difference between those two is that tievalsrest allows for the extra values inputed into the second by the . I by cycleing through them as a list.

Regarding the auxiliary functions my opinion is that we would have done almost the same even without their definition, especially for being defined at such a late point in the paper.

The semantics comes late because it's difficult, and it helps to have formal definitions of the key functions.

I've put about 1.5 hrs into these lambda definitions but I am being blocked by an inability to understand tievals.

The tievals function basically allocates a sequence of memory locations for some expressed values and stores them in those locations.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 10 09:03:20 2006.
The source to the document was last modified on Fri Feb 24 10:03:16 2006.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,