### Intermezzo: BSL

Fixed-Size Data deals with BSL as if it were a natural language. It introduces the “basic words” of the language, suggests how to compose “words” into “sentences,” and appeals to your knowledge of algebra for an intuitive understanding of these “sentences.” While this kind of introduction works to some extent, truly effective communication requires some formal study.

In many ways, the analogy of Fixed-Size Data is correct. A programming
language does have a vocabulary and a grammar, though programmers use the
word syntax for these elements. A sentence in BSL is an
expression or a definition. The grammar of BSL dictates how to form
these phrases. But not all grammatical sentences are meaningful—

This intermezzo presents BSL as if it were an extension of the familiar language of arithmetic and algebra in middle school. 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 syntax and semantics of a good portion of Programmers must eventually understand these principles of computation but they are complementary to the principles of design. BSL. Based on this new understanding of BSL, the fourth resumes our discussion of errors. The remaining sections expand this understanding to the complete language; the last one expands the tools for expressing tests.

#### BSL Vocabulary

Figure 47 introduces and defines BSL’s basic vocabulary. It consists of literal constants, such as numbers or Boolean values; names that have meaning according to BSL, for example, cond or +; and names to which programs can give meaning via define or function parameters.

A 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, for example, + or sqrt.

A variable is a name without preassigned meaning.

A value is one of:

A number is one of: 1, -1, 3/5, 1.22, #i1.22, 0+1i, and so on. The syntax for BSL numbers is complicated because it accommodates a range of formats: positive and negative numbers, fractions and decimal numbers, exact and inexact numbers, real and complex numbers, numbers in bases other than 10, and more. Understanding the precise notation for numbers requires a thorough understanding of grammars and parsing, which is out of scope for this intermezzo.

A boolean is one of: #true or #false.

A string is one of: "", "he says \"hello world\" to you", "doll", and so on. In general, it is a sequence of characters enclosed by a pair of ".

An image is a png, jpg, tiff, and various other formats. We intentionally omit a precise definition.

We use v, v-1, v-2 and the like when we wish to say “any possible value.”

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

#### BSL Grammar

(define (variable variable) expr)

(define (variable variable variable) expr)

(define (variable variable variable variable) expr)

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

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 us 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 first syntactic category says that a program is a def-expr. Expressions may refer to the definitions.

The second one tells us that a def-expr is either a def or an expr.In DrRacket, a program really consists of two distinct parts: the definitions area and the expressions in the interactions area.

The last definition lists all ways of forming an expr, and the second one is value.

The interesting parts of the grammar show how to form compound sentences, those built from other sentences. For example, the def 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. Note how the leading keyword define distinguishes definitions from expressions.

Expressions (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. Like define, the keyword cond distinguishes conditional expressions from 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. The third is a function application, because f and x are variables.

In contrast, these parenthesized sentences are not legal 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, and newlines. BSL is a permissive language. As long as there is some white space between the elements of any sequence in a program, DrRacket can understand your BSL programs. Good programmers, Keep in mind that two kinds of readers study your BSL programs: people and DrRacket. however, may not like what you write. These programmers use white space to make their programs easily readable. Most importantly, they adopt a style that favors human readers over the software applications that process programs (such as DrRacket). They pick up this style from careful reading code examples in books, paying attention to how it is formatted.

x

(= y z)

(= (= y z) 0)

(3 + 4)

number?

(x)

(define (f x) x)

(define (f x) y)

(define (f x y) 3)

(define (f "x") x)

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

(x)

(+ 1 (not x))

(+ 1 2 3)

Note on Grammatical Terminology The components of compound sentences have names. We have introduced some of these names on an informal basis. Figure 49 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]

In addition to the terminology of figure 49, 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 the term actual arguments for the arguments in a function application.

#### BSL Meaning

When you hit the return key on your keyboard and ask DrRacket to evaluate an
expression, it uses the laws of arithmetic and algebra to obtain a
value. For the variant of BSL treated so far,
figure 47 defines grammatically what a value
is—

(+ 1 1) == 2 (- 2 1) == 1 ...

(not #true) == #false (string=? "a" "a") == #true ...

(boolean? (= (string-length (string-append "h" "w")) (+ 1 3))) == (boolean? (= (string-length (string-append "h" "w")) 4)) == (boolean? (= (string-length "hw") 4)) == (boolean? (= 2 4)) == (boolean? #false) == #true

(define (f x-1 ... x-n) f-body)

(f v-1 ... v-n) == f-body ; with all occurrences of x-1 ... x-n ; replaced with v-1 ... v-n, respectively

(define (poly x y) (+ (expt 2 x) y))

(poly 3 5) == (+ (expt 2 3) 5) ... == (+ 8 5) == 13

(cond == (cond [#false ...] ; first line removed [condition2 answer2] [condition2 answer2] ...) ...)

(cond == answer-1 [#true answer-1] [condition2 answer2] ...)

(cond [(zero? 3) 1] [(= 3 3) (+ 1 1)] [else 3]) == ; by plain arithmetic and “equals for equals” (cond [#false 1] [(= 3 3) (+ 1 1)] [else 3]) == ; by rule condfalse (cond [(= 3 3) (+ 1 1)] [else 3]) == ; by plain arithmetic and “equals for equals” (cond [#true (+ 1 1)] [else 3]) == ; by rule condtrue (+ 1 1)

(+ (* (/ 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)])

(define (f x y) (+ (* 3 x) (* y y)))

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

(f 1 (* 2 3))

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

#### Meaning and Computing

The stepper tool in DrRacket mimics a student in a pre-algebra course. In a sense, the stepper is like a mechanized student from a pre-algebra course, and it is extremely good at, and also extremely fasy, applying the laws of A scientist calls the stepper a model of DrRacket’s evaluation mechanism. Refining Interpreters presents another model, an interpreter. arithmetic and algebra as spelled out here.

You can, and you ought to, use the stepper when you don’t understand how a new language construct works. The sections on Computing suggest exercises for this purpose, but you can make up your own examples, run them through the stepper, and ponder why it takes certain steps.

Finally, you may also wish to use the stepper when you are surprised by the result that a program computes. Using the stepper effectively in this way requires practice. For example, it often means copying the program and pruning unnecessary pieces. But once you understand how to use the stepper well this way, you will find that this procedure clearly explains run-time errors and logical mistakes in your programs.

#### BSL Errors

When DrRacket discovers that some parenthesized phrase does not belong to BSL, it signals a syntax error. To determine whether a For a nearly full list of error messages, see the last section of this intermezzo. fully-parenthesized program is syntactically legal, DrRacket uses the grammar in figure 48 and reasons along the lines explained above. Not all syntactically legal programs have meaning, however.

> (/ 1 0) /: division by zero

> (+ (* 20 2) (/ 1 (- 10 10))) /: division by zero

(+ (* 20 2) (/ 1 (- 10 10))) == (+ (* 20 2) (/ 1 0)) == (+ 40 (/ 1 0))

(define (my-divide n) (cond [(= n 0) "inf"] [else (/ 1 n)]))

(my-divide 0) == (cond [(= 0 0) "inf"] [else (/ 1 0)])

(my-divide 0) == (cond [(= 0 0) "inf"] [else (/ 1 0)]) == (cond [#true "inf"] [else (/ 1 0)]) == "inf"

(+ (* 20 2) (/ 20 2))

(cond [(= 0 0) "inf"] [else (/ 1 0)])

Always choose the outermost and left-most nested expression that is ready for evaluation.

(define (checked-area-of-disk v) (cond [(number? v) (area-of-disk v)] [else (error "number expected")]))

(- (checked-area-of-disk "a") (checked-area-of-disk 10)) == (- (cond [(number? "a") (area-of-disk "a")] [else (error "number expected")]) (checked-area-of-disk 10)) == (- (cond [#false (area-of-disk "a")] [else (error "number expected")]) (checked-area-of-disk 10)) == (- (error "number expected") (checked-area-of-disk 10))

(error "number expected")

#### Boolean Expressions

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

Here is the revised grammar of expressions:

expr | = | ... | ||

| | (and expr expr) | |||

| | (or expr expr) |

(define (check n r) (and (not (= n 0)) (= (/ 1 n) r)))

(check 0 1/5) == (and (not (= 0 0)) (= (/ 1 0) 1/5))

(and exp-1 exp-2)

is short for

(cond [exp-1 exp-2] [else #false])

(or exp-1 exp-2)

is short for

(cond [exp-1 #true] [else exp-2])

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

#### Constant Definitions

definition = ... | (define name expr)

(define RADIUS 5)

(define DIAMETER (* 2 RADIUS))

(define RADIUS 5) (define DIAMETER (* 2 RADIUS))

(define RADIUS 5) (define DIAMETER 10)

(define RADIUS 10) (define DIAMETER (* 2 RADIUS)) (define (area r) (* 3.14 (* r r))) (define AREA-OF-RADIUS (area RADIUS))

(define RADIUS 10) (define DIAMETER (* 2 RADIUS)) (define AREA-OF-RADIUS (area RADIUS)) (define (area r) (* 3.14 (* r r)))

(define PRICE 5) (define SALES-TAX (* 0.08 PRICE)) (define TOTAL (+ PRICE SALES-TAX))

(define COLD-F 32) (define COLD-C (fahrenheit->celsius COLD-F)) (define (fahrenheit->celsius f) (* 5/9 (- f 32)))

(define LEFT -100) (define RIGHT 100) (define (f x) (+ (* 5 (expt x 2)) 10)) (define f@LEFT (f LEFT)) (define f@RIGHT (f RIGHT))

#### Structure Type Definitions

definition = ... | (define-struct name [name ...])

(define-struct point [x y z])

(define-struct [point x y z]) (define-struct point x y z)

(define-struct c [s-1 ... s-n])

make-c: a constructor;

c-s-1... c-s-n: a series of selectors; and

c?: a predicate.

A value is one of: a number, a boolean, a string, an image,

or a structure value:

(make-c _value-1 ... _value-n) assuming a structure type c is defined.

(make-point 1 2 -1) (make-point "one" "hello" "world") (make-point 1 "one" (make-point 1 2 -1)) ...

(c-s-1 (make-c V-1 ... V-n)) == V-1 (c-s-n (make-c V-1 ... V-n)) == V-n

(point-x (make-point V U W)) == V (point-y (make-point V U W)) == U (point-z (make-point V U W)) == W

(c? (make-c V-1 ... V-n)) == #true (c? V) == #false

(point? (make-point U V W)) == #true (point? X) == #false

(define-struct oops [])

(define-struct child [parents dob date])

(define-struct (child person) [dob date])

(define-struct point [x y z]) (define-struct none [])

(make-point 1 2 3)

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

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

(make-none)

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

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

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

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

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

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

(ball-speed-y 5)

#### BSL Tests

check-expect,The actual grammar of BSL is even a bit larger; see the Help Desk.

check-within,

check-member-of,

check-range,

check-error,

check-random, and

check-satisfied.

def-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-member-of expr expr ...) | (check-range expr expr expr) | (check-error expr) | (check-random expr expr) | (check-satisfied expr name)

The general meaning of testing expressions is easy to explain. When you click the RUN button, DrRacket collects all testing expressions and moves them to the end of the program, retaining the order in which they appear. It then evaluates the content of the definitions area. Each test evaluates its pieces and then compares them with the expected outcome via some predicate. Beyond that, tests communicate with DrRacket to collect some statistics and information on how to display test failures.

; check-expect compares the outcome and the expected value with equal? (check-expect 3 3) ; check-member-of compares the outcome and the expected values with equal? ; if one of them yields #true, the test succeeds (check-member-of "green" "red" "yellow" "green") ; check-within compares the outcome and the expected value with a predicate ; like equal? but allows for a tolerance of epsilon for each inexact number (check-within (make-posn #i1.0 #i1.1) (make-posn #i0.9 #i1.2) 0.2) ; check-range is like check-within ; but allows for a specification of an interval (check-range 0.9 #i0.6 #i1.0) ; check-error checks whether an expression signals (any) error (check-error (/ 1 0)) ; check-random evaluates the sequences of calls to random in the ; two expressions such that they yield the same number (check-random (make-posn (random 3) (random 9)) (make-posn (random 3) (random 9))) ; check-satisfied determines whether a predicate produces #true ; when applied to the outcome, that is, whether outcome has a certain property (check-satisfied 4 even?)

(check-expect 3 4) (check-member-of "green" "red" "yellow" "grey") (check-within (make-posn #i1.0 #i1.1) (make-posn #i0.9 #i1.2) 0.01) (check-range #i0.9 #i0.6 #i0.8) (check-error (/ 1 1)) (check-random (make-posn (random 3) (random 9)) (make-posn (random 9) (random 3))) (check-satisfied 4 odd?)

#### BSL Error Messages

A BSL program may signal many kinds of syntax errors. While we have developed BSL and its error reporting system specifically for novices who, by definition make mistakes, error messages need some getting used to.

the code fragments that signal the error message;

the error message; and

an explanation with a suggestion on how to fix the mistake.

| A cond expressions consists of the keyword followed by an arbitrarily long sequence of cond clauses. In turn, every clause consists of two parts: a condition and an answer, both of which are expressions. In this definition of absolute, the first clause starts with <, which is supposed to be a condition but isn't even an expression according to our definition. This confuses BSL so much that it doesn't ``see'' the open parenthesis to the left of <. The fix is to use (< n 0) as the condition. |

So, when an error shows up and you need help, find the appropriate figure, search the entries for a match, and then study the complete entry.

##### Error Messages about Function Applications in BSL

| The application names f as the function, and f is not defined in the definitions area. Define the function, or make sure that the variable name is spelled correctly. |

| An open parenthesis must always followed by a keyword or the name of a function, and 1 is neither. A function name is either defined by BSL, say +, or in the definitions area, say average. |

| This function call applies average to one argument, 7, even though its definition calls for two numbers. |

| Here average is applied to three numbers instead of two. |

| Functions defined by BSL must also be applied to the correct number of arguments. For example, make-posn must be applied to two arguments. |

##### Error Messages about Wrong Data in BSL

| A function must be applied to the arguments it expects. For example, posn-x expects an instance of posn. |

| A function defined to consume two Numbers must be applied to two Numbers; here average is applied to Strings. The error message is triggered only when average applies + to these Strings. Like all primitive operations, + is a checked function. |

##### Error Messages about Conditionals in BSL

; N in [0,1,...10) (define 0-to-9 (random 10))

| Every cond clause must consist of exactly two parts: a condition and an answer. Here (>= 0-to-9 5) is apparently intended as the condition; the answer is missing. |

| In this case, the cond clause consists of three parts, which also violates the grammar. While (>= 0-to-9 5) is clearly intended to be the condition, the clause comes with two answers: "head" and "tail". Pick one or create a single value from the two strings. |

| A conditional must come with at least one cond clause and usually it comes with at least two. |

##### Error Messages about Function Definitions in BSL

All of the following error scenarios assume that you have placed the code snippet into the definitions area and hit RUN.

| A definition consist of three parts: the define keyword, a sequence of variable names enclosed in parentheses, and an expression. This definition consists of four parts; this definition is an attempt to use the standard notation from algebra courses for the header f (x) instead of (f x). |

| The sequence of parameters in a function definition must not contain duplicate variables. |

| In BSL a function header must contain at least two names. The first one is the name of the function; the remaining variable names are the parameters, and they are missing here. |

| The sequence of parameters in a function definition must not contain duplicate variable names. |

| The function header contains (x), which is not a variable name. |

| This function definition comes with two expressions following the header: x and y. |

##### Error Messages about Structure Type Definitions in BSL

Now you need to place the structure type definitions into the definitions area and hit RUN to experiment with the following errors.

| A structure type definition consists of three parts: the define-struct keyword, the structure's name, and a sequence of names in parentheses. Here the structure's name is missing. |

| The sequence of field names in a structure type definition must not contain duplicate names. |

| These structure type definitions lack the sequence of field names, enclosed in parentheses. |

| Here the sequence of field names contains (z), which is not just a name but a name inside of parentheses. |