2.3.1 Strings - SICP Comparison Edition

Permalink copied!

2.3.1

So far, we have used strings in order to display messages, using the functions display and error (as for example in exercise 1.22). We can form compound data using strings and have lists such as

list("a", "b", "c", "d") list(23, 45, 17) list(list("Jakob", 27), list("Lova", 9), list("Luisa", 24))

In order to distinguish strings from names, we surround them with double quotation marks. For example, the JavaScript expression z denotes the value of the name z, whereas the JavaScript expression "z" denotes a string that consists of a single character, namely the last letter in the English alphabet in lower case.

Via quotation marks, we can distinguish between strings and names:

const a = 1;
const b = 2;

list(a, b);

[1, [2, null]]

list("a", "b");

["a", ["b", null]]

list("a", b);

["a", [2, null]]

In section 1.1.6, we introduced === and !== as primitive predicates on numbers. From now on, we shall allow two strings as operands of === and !==. The predicate === returns true if and only if the two strings are the same, and !== returns true if and only if the two strings are not the same.

[1]

Using ===, we can implement a useful function called member. This takes two arguments: a string and a list of strings or a number and a list of numbers. If the first argument is not contained in the list (i.e., is not === to any item in the list), then member returns null. Otherwise, it returns the sublist of the list beginning with the first occurrence of the string or number:

function member(item, x) {
    return is_null(x)
           ? null
           : item === head(x)
           ? x
           : member(item, tail(x));
}

For example, the value of

member("apple", list("pear", "banana", "prune"))

is null, whereas the value of

member("apple", list("x", "y", "apple", "pear"))

is list("apple", "pear").

Exercise 2.53

What is the result of evaluating each of the following expressions, in box notation and list notation?

list("a", "b", "c")

list(list("george"))

tail(list(list("x1", "x2"), list("y1", "y2")))

tail(head(list(list("x1", "x2"), list("y1", "y2"))))

member("red", list("blue", "shoes", "yellow", "socks"))

member("red", list("red", "shoes", "blue", "socks"))

["a", ["b", ["c", null]]]

[["george", null], null]

[["y1", ["y2", null]], null]

["x2", null]

null

["red", ["shoes", ["blue", ["socks", null]]]]

Exercise 2.54

Two lists are said to be equal if they contain equal elements arranged in the same order. For example,

equal(list("this", "is", "a", "list"), list("this", "is", "a", "list"))

is true, but

equal(list("this", "is", "a", "list"), list("this", list("is", "a"), "list"))

is false. To be more precise, we can define equal recursively in terms of the basic === equality of numbers and strings by saying that a and b are equal if they are both strings or both numbers and they are ===, or if they are both pairs such that head(a) is equal to head(b) and tail(a) is equal to tail(b). Using this idea, implement equal as a function.

The following function implements general structural equality for chapters 1 and 2, assuming that === can only be applied to two numbers or two strings, and otherwise report an error. The equal function below will only encounter an error when both arguments are functions, because it is not clear in chapters 1 and 2 what equality on functions would mean.

function equal(xs, ys) {
    return is_pair(xs)
           ? (is_pair(ys) &&
              equal(head(xs), head(ys)) && 
              equal(tail(xs), tail(ys)))
           : is_null(xs)
           ? is_null(ys)
           : is_number(xs)
           ? (is_number(ys) && xs === ys)
           : is_boolean(xs)
           ? (is_boolean(ys) && ((xs && ys) || (!xs && !ys)))
           : is_string(xs)
           ? (is_string(ys) && xs === ys)
           : is_undefined(xs)
           ? is_undefined(ys)
           : // we know now that xs is a function
             (is_function(ys) && xs === ys);
}

In chapter 3, we extend === such that it can be applied to any value and give meaningful results (pointer equality). The equal function above will still be valid with this extended meaning of ===, but can be simplified as follows:

function equal(xs, ys) {
    return is_pair(xs)
           ? (is_pair(ys) &&
              equal(head(xs), head(ys)) && 
              equal(tail(xs), tail(ys)))
           : xs === ys;
}

Exercise 2.55

The JavaScript interpreter reads the characters after a double quotation mark " until it finds another double quotation mark. All characters between the two are part of the string, excluding the double quotation marks themselves. But what if we want a string to contain double quotation marks? For this purpose, JavaScript also allows single quotation marks to delimit strings, as for example in 'say your name aloud'. Within singly-quoted strings, we can use double quotation marks, and vice versa, so 'say "your name" aloud' and "say 'your name' aloud" are valid strings that have different characters at positions 4 and 14, if we start counting at 0. Depending on the font in use, two single quotation marks might not be easily distinguishable from a double quotation mark. Can you spot which is which and work out the value of the following expression?

'"' === ""

The given expression checks if a string containing only one double-quote character is equal to the empty string. The resulting value is false.

[1]

We can consider two strings to be the same if they consist of the same characters in the same order. Such a definition skirts a deep issue that we are not yet ready to address: the meaning of sameness in a programming language. We will return to this in chapter 3 (section 3.1.3).

< Previous

Next >

2.3.1

Strings