3 Intermezzo: BSL

Thus far we have approached BSL as if it were a spoken language. Like a toddler, you first learn the vocabulary of the language with an intuitive understanding of its meaning. Next you figure out some basic rules of how to compose and not to compose sentences. Truly effective communication, however, requires some formal study of a language’s vocabulary, its grammar, and its meaning.

A programming language is in many ways like a spoken language. It has a vocabulary and a grammar. The vocabulary is the collection of those “basic words” from which we can compose “sentences” in our language. A sentence in a programming language is an expression or a function; the language’s grammar dictates how to form complete sentences from words. Programmers use the terminology syntax to refer to the vocabularies and grammars of programming languages.

Not all grammatical sentences are meaningful—neither in English nor in a programming language. For example, the English sentence “the cat is round” is a meaningful sentence, but “the brick is a car” makes no sense even though it is completely grammatical. To determine whether a sentence is meaningful, we must know the meaning of a language; programmers call this semantics.

The intermezzos of this book introduce ideas from programming languages that programmers must eventually understand and appreciate but are secondary to program design. In this intermezzo, we discuss the meaning of BSL programs as if it were an extension of the familiar laws of arithmetic and algebra. After all, computation starts with this form of simple mathematics, and we should understand the connection between this mathematics and computing. The first three sections present the vocabulary, grammar, and meaning of a good portion of BSL. Based on this new understanding of BSL, the fourth one resumes our discussion of errors. The remaining three sections revisit and and or expressions, constant definitions, and structure types.

3.1 BSL: Vocabulary

Figure 24 introduces and defines BSL’s basic vocabulary. It consists of names that may or may not have meaning according to BSL and of constants, also known as values and pieces of data.

An name or a variable is a sequence of characters not including a space or one of the following: " , ' ` ( ) [ ] { } | ; #:

• A primitive is a name to which BSL assigns meaning, e.g., + or sqrt.

• A variable is a name without preassigned meaning.

A value, also a called a piece of data, is one of:

• A number is one of: 1, -1, 3/5, 1.22, 1.22, 0+1i, etc.

• A boolean is one of: #t or #f.

• A string is one of: "a", "doll", "he says \"hello world\" ok", etc. In general, it is a sequence of characters enclosed by a pair of ". For example, are all strings.

• An image is a png, jpg, tiff, etc. We intentionally omit a precise definition.

We use v, v-1, v-2 etc. when we wish to say “value” without being precise.

Figure 24: The core vocabulary

Each of the explanations defines a set via a suggestive iteration of its elements. Although it is possible to specify these collections in their entirety and in a formal manner, we consider this superfluous here and trust in your intuition. Just keep in mind that all of these sets may come with some extra elements.

program		=		def-or-expr ...
def-or-expr		=		definition
		|		expr
definition		=		(define (variable variable variable ...) expr)
expr		=		variable
		|		value
		|		(primitive expr expr ...)
		|		(variable expr expr ...)
		|		(cond [expr expr] ... [expr expr])
		|		(cond [expr expr] ... [else expr])

Figure 25: The core grammar

3.2 BSL: Grammar

The final point about grammars concerns the three “words” that come in a distinct font: define, cond, and else. According to the definition of BSL vocabulary, these three words are names. What the vocabulary definition does not tell you is that these names have a pre-defined meaning. In BSL, these words serve as markers that differentiate some compound sentences from others, and in acknowledgment of their role, such words are called keywords.

The interesting parts of the grammar show how to form compound sentences, which are sentences built from other sentences. For example, the definition part tells us that a function definition is formed by using “(”, followed by the keyword define, followed by another “(”, followed by a sequence of at least two variables, followed by “)”, followed by an expr, and closed by a right parenthesis “)” that matches the very first one. You can see from this example how the leading keyword, define, distinguishes definitions from expressions.

Expressions, called expr, come in six flavors: variables, constants, primitive applications, (function) applications, and two varieties of conditionals. While the first two are atomic sentences, the last four are compound sentences. Note how the keyword cond distinguishes conditional expressions from primitive and function applications.

Here are three examples of expressions: "all", x, and (f x). The first one belongs to the class of strings and is therefore an expression. The second is a variable, and every variable is an expression. Finally, the third is a function application, because f and x are variables.

In contrast, the following parenthesized sentences are not expressions: (f define), (cond x), and ((f 2) 10). The first one partially matches the shape of a function application but it uses define as if it were a variable. The second one fails to be a correct cond expression because it contains a variable as the second item and not a pair of expressions surrounded by parentheses. The last one is neither a conditional nor an application because the first part is an expression.

Finally, you may notice that the grammar does not mention white space: blank spaces, tabs, newlines. BSL is a permissive language, meaning as long as there is some white space between the elements of any sequence in a program, DrRacket can cope. Good programmers, however, adopt a consistent and easily recognized style of using white space. They pick up this style from reading code examples in books carefully.

Exercise 98: Explain why the following sentences are syntactically legal expressions

x

(= y z)

(= (= y z) 0)

Exercise 99: Explain why the following sentences are syntactically illegal

(3 + 4)

number?(l)

(x)

Exercise 100: Explain why the following sentences are syntactically legal definitions

(define (f x) x)

(define (f x) y)

(define (f x y) 3)

Exercise 101: Explain why the following sentences are syntactically illegal

(define (f 'x) x)

(define (f x y z) (x))

(define (f) 10)

Exercise 102: Pick the legal from the legal from illegal sentences in the following list:

1. (x)

2. (+ 1 (not x))

3. (+ 1 2 3)

Explain why the sentences are legal or illegal. Determine whether they belong the category expr or definition.

Note on Grammatical Terminology: The components of compound sentences have names. We have introduced some of these names on an informal basis. Figure 26 provides a summary of the conventions.

; function application:

(function argument ... argument)

; function definition:

(define (function-name parameter ... parameter)

function-body)

; conditional expression:

(cond

cond-clause

...

cond-clause)

; cond clause

[condition answer]

Figure 26: Syntactic naming conventions

In addition to the terminology of figure 26, we say function header for second component of a definition. Accordingly, the expression component is called function body. People who consider programming languages as a form of mathematics use left-hand side for a header and right-hand side for the body.

On occasion, you also hear or read actual arguments for the arguments in a function application.

3.3 BSL: Meaning

When DrRacket evaluates an expression, it uses nothing but the laws of arithmetic and algebra to convert an expression into a value—see figure 24. In ordinary mathematics courses, values are just numbers. As you know from the figure, the values of BSL also include Booleans, String, and Images. You should note how the collection of values is thus just a subset of the collection of expressions.

Exercise 103: Evaluate the following expressions step by step:

(+ (* (/ 12 8) 2/3)

(- 20 (sqrt 4)))

(cond

[(= 0 0) false]

[(> 0 1) (string=? "a" "a")]

[else (= (/  1 0) 9)])

(cond

[(= 2 0) false]

[(> 2 1) (string=? "a" "a")]

[else (= (/  1 2) 9)])

Exercise 104: Suppose the program contains these definitions:

(define (f x y)

(+ (* 3 x) (* y y)))

Show how DrRacket evaluates the following expressions, step by step:

(+ (f 1 2) (f 2 1))

(f 1 (* 2 3))

(f (f 1 (* 2 3)) 19)

3.4 BSL: Errors

When DrRacket discovers that some parenthesized phrase does not belong to BSL, it signals a syntax error. To determine whether a fully-parenthesized program is syntactically legal, DrRacket uses the grammar in figure 25 and reasons along the lines explained above. Not all syntactically legal programs have meaning, however.

3.5 Boolean Expressions

Our current definition of the Beginning Student BSL language omits two forms of expressions: and and or expressions. Adding them provides a case study of how to study new language constructs. We must first understand their syntax and then their semantics.

Exercise 105: The use of if may have surprised you in another way because this intermezzo does not mention this form elsewhere. In short, the intermezzo appears to explain and with a form that has no explanation either. At this point, we are relying on your intuitive understanding of if as a short-hand for cond. Write down a rule that shows how to reformulate

(if exp-test exp-then exp-else)

as a cond expression.

3.6 Constant Definitions

Exercise 106: Evaluate the following program:

(define PRICE 5)

(define SALES-TAX (* 0.08 PRICE))

(define TOTAL (+ PRICE SALES-TAX))

Does the evaluation of the following program signal an error?

(define COLD-F 32)

(define COLD-C (fahrenheit->celsius COLD-F))

(define (fahrenheit->celsius f)

(* 5/9 (- f 32)))

How about the next one?

(define LEFT -100)

(define RIGHT 100)

(define (f x) (+ (* 5 (expt x 2)) 10))

(define f@LEFT (f LEFT))

(define f@RIGHT (f RIGHT))

3.7 Structure Type Definitions

Exercise 107: Pick the legal from the legal from illegal sentences in the following list:

1. (define-struct oops ())

2. (define-struct child (parents dob date))

3. (define-struct (child person) (dob date))

Explain why the sentences are legal or illegal.

Exercise 108: Identify which of the following expressions are values:

1. (make-point 1 2 3)

2. (make-point (make-point 1 2 3) 4 5)

3. (make-point (+ 1 2) 3 4)

Explain why the expressions are values or not.

Exercise 109: Suppose the program contains

(define-struct ball (x y speed-x speed-y))

Predict the results of evaluating the following expression:

1. (number? (make-ball 1 2 3 4))

2. (ball-speed-y (make-ball (+ 1 2) (+ 3 3) 2 3))

3. (ball-y (make-ball (+ 1 2) (+ 3 3) 2 3))

4. (ball-x (make-posn 1 2))

5. (ball-speed-y 5)

Verify your predictions with DrRacket.

3.8 BSL: Tests

Figure 27 collects all the elements of BSL that this intermezzo explains plus the tests: check-expect, check-within, and check-error. The actual grammar of BSL is even a bit larger; see the Help Desk for details.

program		=		def-or-expr ...
def-or-expr		=		definition
		|		expr
		|		test-case
definition		=		(define (name variable variable ...) expr)
		|		(define name expr)
		|		(define-struct name (name ...))
expr		=		(name expr expr ...)
		|		(cond [expr expr] ... [expr expr])
		|		(cond [expr expr] ... [else expr])
		|		(and expr expr expr ...)
		|		(or expr expr expr ...)
		|		name
		|		number
		|		string
		|		image
test-case		=		(check-expect expr expr)
		|		(check-within expr expr expr)
		|		(check-error expr)

Figure 27: Beginning Student Language, Full Grammar

The meaning of testing expressions is easy to explain. When you click the “Run” button DrRacket collects all testing expressions and moves them from the middle of the program to the end, retaining in the order in which they appear. Then it evaluates the definitions, expressions, and tests and allows you to explore additional expressions in the interactions area.

In principle, the evaluation of a test evaluates its pieces and then compares them with an equality predicate, equal? to be precise. Beyond that, tests communicate with DrRacket to collect some success and failure statistics and information on how to display test failures.