Please give a lot of detail, not just answer. 1. When the eq? function in Scheme
ID: 3600278 • Letter: P
Question
Please give a lot of detail, not just answer.
1.
When the eq? function in Scheme is used for comparing symbols it must return #t if and only if the the two symbols have the same name (where uppercase and lowercase characters are not distin- guished). E.g.,
(eq? ’x ’x)returns#t
(eq? ’x ’X)returns#t
(eq? ’x ’y)returns#f
With our current implementation, the parser constructs a new Ident object for every occurrence of a symbol. For comparing symbols, it is, therefore, necessary to use string comparison for comparing the names stored in these Ident objects. Explain, how you would modify your processing of symbols (data structure, lexical analysis, and parsing), so that eq? could be implemented using simple pointer comparison, i.e., using == in Java.
Explanation / Answer
valuation
The symbol "==>" in these examples means "evaluates to." For example,
(+ 5 8) ==> 40
means that the expression (+ 5 8) evaluates to 40.
Where the value returned by an expression is marked unspecified, Scheme does not guarantee what the value will be. For example,
(set! x 3) ==> unspecified
Feel free to experiment to determine what Scheme returns in any particular case, but remember that a new version of Scheme might return a different value. Avoid writing programs that rely on unspecified values, particularly when working on problem sets.
4.1.3 Numbers
Scheme numbers are expressed exactly as normal numbers, except that scientific notation looks slightly different. In Scheme scientific notation, the numbers of the exponent are not raised, but instead are separated from the base number by the letter e. For example,
123e10 is Scheme notation for 123 x 1010, and -123.45e-1 is Scheme notation for -123.45 x 10-1.
4.1. NOTATION AND TERMINOLOGY 59
4.1.4 Identifiers
A Scheme identifier is a sequence of letters, digits, and punctuation characters that is not a number. Here are some identifiers:
lambda
q
<=?
list->vector
soup
a34kTMNs
+
V17a
the-word-recursion-has-many-meanings
Upper and lower case forms of a letter are never distinguished except within character and string constants. For example, Foo is the same identifier as FOO.
Identifiers have several uses within Scheme programs:
• Certain identifiers are reserved for use as special forms, and cannot be used as variables. They are:
and
else
or
begin
error
quote
cond
if
sequence
cons-stream
lambda
set!
define
let
the-environment
delay
make-environment
unquote
• Any identifier that does not refer to a special form may be used as a variable (see section 4.2 ).
• When an identifier appears as a quoted constant or within a quoted constant, it denotes a symbol (see section 4.7 ).
4;1.5 Whitespace and Comments
Whitespace characters are spaces and line breaks (newlines). Whitespace is used to improve readability and to separate tokens (identifiers and numbers) from each other. Whitespace may also occur inside a string value.
A semicolon starts a comment, text which will be seen as whitespace by Scheme. The comment continues from the semicolon to the end of the line. For example:
60 CHAPTER 4. SCHEME REFERENCE
;; The FACT procedure computes the factorial
;; of a nonnegative integer.
(define fact
(lambda (n )
(if(= (n ) 0)
1 ;Base case: return 1
(* (n ) (fact (- (n ) 1))))))
4.1.6 Special Characters in Scheme Notations
Here are the special characters used in Scheme notations:
/ < = > ! ? : $ % _ & ~ ^
These characters may be used in identifiers as if they were letters.
. + -
These appear in numbers and identifiers. The period character is also used in the notation for pairs (section 4.6 ).
( )
Parentheses surround expressions and lists (section 4.6 ).
'
The single quote character indicates literal data (section 4.3.2 ).
"
Double quote characters surround string values (section 4.9 ).
Backslash is an escape character within string constants (section 4.9 ).
[ ] { }
Left and right square brackets and curly braces are reserved for possible future extensions to the language.
#t #f
These are the boolean constants true and false (section 4.5 ).
#
Represents the ASCII standard number representing the immediately following character.
#(
Introduces a vector constant (section 4.10).
4.2. VARIABLES AND BINDINGS 61
Variables and bindings
Any identifier that does not refer to a special form (see section 4.1.4 ) may be used as a variable. A variable may name a location where a value can be stored. A variable that does so is said to be bound to the location. The set of all bindings in effect at some point in a program is the environment.
Certain expressions create new locations and bind variables to them. The most fundamental of these binding constructs is the lambda expression, because all other binding constructs can be explained in terms of lambda expressions. See section 4.3.5.
Like Algol and Pascal, and unlike most other dialects of Lisp except Common Lisp, Scheme is statically scoped and has block structure. To each place where a variable is bound in a program there corresponds a region of the program text within which the binding is effective. The region is determined by the particular binding construct that establishes the binding; if the binding is established by a lambda expression, for example, then its region is the entire lambda expression. Every reference to or assignment of a variable refers to the
lambda
q
<=?
list->vector
soup
a34kTMNs
+
V17a
the-word-recursion-has-many-meanings