Programming Languages (CS302 2005S)

Questions on R5RS, Sections 1-5

Kelsey, R., Clinger, W., and Rees, J., Editors (1998). Revised5 Report on the Algorithmic Language Scheme. Section 7: Formal Syntax and Semantics.

Questions from: Edwards, Erickson, Fletcher, French, Guha, Nyombayire, Ramdial, Rosenbluh, Schmitz, Shireman, Smith, Yilma

Questions missing from: Barnes, Brantley, Kasidhi, Kuo, Petersen (MIA)


General Confusion

I am really confused about the notations in the section 7.2.3 covering Semantic functions. Is there any way you could explain this in class?

Can you explain the Formal Semantics for Scheme? I am not making any progress through it.

In section 7.2, the report focuses on formal semantics. It is hard to understand what some of the functions represent so I was wondering if you could go through a few of them?

Confusion on Syntax

I had a lot of trouble reading Section 7.2 on the formal syntax. I tried reading the mathmatical notation, but I had trouble understanding what it meant.

I'm not quite to the point of having this make no sense at all. In fact, I suspect I might be getting the hang of it. However, I'm having a slow enough time of it that I'm going to ask "could we please go over eBNF in class?"


Expressions, E, are functions U -> K -> E*, where U is the environment, K is the expression continuation and E* is the result sequence. When evaluating a top-level expression, the environment would be empty. But what would be the top-level (i.e. empty) expression continuation?

Could you elaborate on the answer domain, A?

What is the significance of the boolean in the definition of pairs, strings and vectors (7.2.2) ?


At the end of page 40 of the scheme report, an expression ((lambda (I*) P') <undefined>) is given to be the meaning of a program for which all variables are assigned before use. Since we thus know the code is robust, what is accomplished by the term <undefined>?

I had problems with the syntax past section 7.2.1

Also, most the definitions of semantic functions have a statement, [weird letter]pk, where [weird letter] isn't defined and p is environment, k expression continuation. What does that statement mean? Does it involve continuation that we discussed in class on Wed.?

First of all, what's a quasiquote? Come to think of it, I never quite understood it when they went over it in the previous chapters. Second of all, does the non-context free nature of quasiquotes make them slow down compilation if used too liberally?

Short Questions

What is K (not the constant, the greek letter)? Why was it's definition omitted?

It provides meaning for constant values. It's difficult and not very useful to define it.

Consider the following rules:

Is there a practical reason for recognizing a prefix followed by a datum as a list?

Remember: Each of those prefixes represents a form of the quote operation. Hence, you'll get the list (quote datum) or some variant thereof.

Does the unspecified order of operations allow the scheme interpreter to skip unnecessary operations or accelerate a program? Does it make parallel processing possible or easy?

Mostly to choose the order-of-operations that is most efficient for the architecture. It makes parallel processing easier, but the implementation must still coordinate with a sequential implementation.

The denotational semantics from 7.2 seem particularly apt to describe functional programming languages. Is this system commonly used to describe object oriented and procedural languages or are other systems used for these?

Denotational semantics works nicely for many imperative languages. I haven't seen it used for object-oriented languages, but I suppose it could be.

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 Mar 2 11:39:35 2005.
The source to the document was last modified on Fri Feb 11 09:07:55 2005.
This document may be found at

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

Samuel A. Rebelsky,