Programming Languages (CS302 2006S)

Notes on the Semantics of Scheme, Part 1

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, Davis Hart, Alex Leach, Brad Miller, Angeline Namai, Mark Nettling.

No Comments from: Michael Claveria, Dimitar Tasev,


I failed utterly to understand the reading. while as far as I can tell I understand the begining of 7.2 once I hit 7.2.3 I get a mental block, even if I try to break each function into smaller parts once I get to the bunches of symbols I hit the block and end up no where.

While the abstract syntax and domain equations made sense to me, I had trouble understanding what the equations in the Semantic Functions section, as well as the helper functions described on page 42. Is it possible that we could go over these in class?

Can you go over 7.2.3-7.2.4 (Semantic Functions-Auxiliary functions) in class? Those were the parts of chapter 7 that I had most difficulty comprehending.

I'll do what I can in class.

Generally, I'm not sure I understand what purpose this section serves and how it is useful.

It's an attempt to formalize the definition of the language.

As a broad question, I wonder how this semantic description varies between languages.

It varies significantly from Scheme to more pure imperative languages. For example, most languages would not need to define lambda. It varies less between imperative language.

One specific thing I was confused about however, was the use of the psi character in the definition of the single command. Maybe I'm just missing where it is defined, but I couldn't find it.

Yeah. They need a symbol for element of (E->C).

My last specific question is how the . and indentations are used in the definitions. Should we read it like lambda calculus and atoms, where .'s indicate pairs?

You should read it like pure lambda calculus. The stuff after the period is the body of the lambda expression.

What is the meaning of \wxy.z?

A function of three parameters, w, x, and y, that returns z.

I think reaching an understanding of this would not be as hard if we covered some of the sematics defined in Stoy's Denotational Semantics. I assume that he defines the maning of a lot of the constructs in 7.2. My main questions are:

Does a right-faced arrow denote the mapping of something from one domain to another?

In the type definitions, yes. Otherwise, it's a McCarthy conditional.

In the definition for single, what is the meaning of the parentheses in the clause PSI(...)?

Finally, I don't understand why pairs are defined as a cross product of two locations and a boolean value. I think the new function suggests that the boolean marks a location false when something is stored there. Is that right?

Nope. The third parameter is for mutability.

Why are they so reluctant to leave out a definition of Kappa? On page 41, they state "Definition of Kappa deliberately omitted." Are the other ones defined(any better) in that same section?

Kappa, which assigns meanings to constants, is not very interesting. They note that it was deliberately omitted to make it clear that it is not accidental. (Think about the wonderful This page intentionally left blank that you often see in technical manuals.)

Why does "E[[(lambda (I*) (Gamma)* E0)]]" check for available memory first, while cwcc checks second? Does it matter?

I'm not sure what you mean by first and second, but both check immediately after calling new.

I like that the reading distinguishes between unspecified and undefined. I have always used these terms interchangeably when talking about programs, but based on the semantic functions, I think undefined sends an error message while unspecified sends an ignore-current-command message.

Well ... it's more than the messages they send. Undefined things have no definition. They are like the results of an incorrect or infinite computation. Unspecified things have a value, but we don't care what the value is.

I also find it interesting that both if-functions on page 41 call the truish function as a helper, because the idea of truism came up several times in 151. I recall that any expression that does not explicitly return false, or is itself not the Boolean, false, is true by default in Scheme, as opposed to Java, where any expression that does not explicitly return true defaults to false. However, I am not sure how truism is useful. Doesn't such an approach create more room for error, since it is a more inclusive than selective one?

It's the old how much power do you give the programmer thing. Scheme likes to give the programmer extra power. The truish is also useful for the typical use of assoc

(let ((result (assoc key lst)))
  (if (result) 
      ... ; What to do if the key appears in the list.
      ... ; What to do if the key does not appear in the list.
      ))

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 Mon Feb 20 08:55:38 2006.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2006S/Readings/scheme-semantics-1.html.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu