Emacs LISP exercises in Structure and Interpretation of Computer Programs: Section 1.1
Peter Prevos |
1967 words | 10 minutes
Share this content
This article contains proposed solutions to the exercises in section 1.1 of Structure and Interpretation of Computer Programs (SICP) by Abelson, Sussman and Sussman. MIT hosts video lectures to accompany the book on MIT OpenCourseWare.
The textbook uses the Scheme dialect of Lisp. I have written these solutions to help me learn Emacs Lisp (Elisp). Some of the solutions are derived from the work by Andres Raba. Most of the solutions include links to the online version of the GNU Emacs Lisp Reference Manual.
Chapter 1: The Elements of Programming
The first chapter of the textbook introduces the elements of the Lisp language. Harold Abelson starts the lecture with the interesting statement that computer science is neither a science, nor is it about computers, just like physics is not about particle accelerators.
The first 28 minutes are an introduction to computer programming, after which the LISP lecture starts.
Exercise 1.1
Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.
Answer
In Emacs, you can type this code in the scratch buffer and evaluate an expression with the eval-last-sexp function or the C-x C-e keyboard shortcut, placing the cursor after the end of the expression. The eval-last-sexp function evaluates the last expression before the cursor (point). The results will appear in the minibuffer at the bottom of the screen.
Emacs also has a REPL (Read-Eval-Print Loop), which you can access with M-x ielm. In REPL mode, the results appear below the expression after you hit enter.
Emacs provides the result in decimal numbers. The output between parenthesis is the result in octal (#o) and hexadecimal (#x) numeral system, e.g.: 1969 (#o3661, #x7b1). For values below 128, the output also includes an associated character, e.g. 26 (#o32 #x1a ?\C-z), where z is the character 26 in ASCII.
The code below shows the solutions in the comments after the expressions. The first lines demonstrate Arithmetic Operations in Emacs Lisp. Lisp uses Polish notation to resolve mathematical expressions. In this system, the operatore precede the operands, e.g. + 3 4 is the same as $3+4$ in infix notation.
The second set of expressions demonstrates setting variable values. The setq function sets universal variables. The q relates to the fact that the variable name is quoted. Without quoting the variable (the set function), Emacs will evaluate the name of the variable as a function and cause an error. You can also add a quotation mark to prevent Emacs from evaluating an expression. The following two expressions have the same result:
;; Equivalent expressions
(setq a 10)
(set 'a 10)
Emacs is a self-documenting editor and you can document your programming on the fly. The defvar function allows you to define a new variable plus a documentation string. This function is helpful when the variable will be available to other users. The help string that you define is available through the help function with the C-h v shortcut.
;; Arithmetic operations
10 ; => 10
(+ 5 3 4) ; => 12
(- 9 1) ; => 8
(/ 6 2) ; => 3
(+ (* 2 4) (- 4 6)) ; => 10
;; Seting variable names
(setq a 3)
(setq b (+ a 1))
(setq a 3
b (+ a 1))
(defvar example (* a b)
"An example of a documented variable.")
(+ a b (* a b)) ; => 19
(= a b) ; => nil
These last lines of code look provide an example of basic conditionals. The first expression is a an if-then-else statement. The second expression is a conditional. The last clause is executed when none of the other conditions is true. The t parameter ensures that this expression is always evaluated.
;; Conditionals
(if (and (> b a) (< b (* a b)))
b
a) ;; => 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(t 25)) ;;=> 16
(+ 2 (if (> b a) b a)) ; => 6
(* (cond ((> a b) a)
((< a b) b)
(t -1))
(+ a 1)) ;; => 16Exercise 1.2
Translate the following expression into prefix form:
$$\frac{5 + 4 + (2 - (3 - (6 + \frac{5}{4})))}{3(6 - 2)(2 - 7)}$$
Answer
When Emacs Lisp divides two integers, the outcome will also be integer, e.g. (/ 22 7) results in 3 instead of 3.142… To force a floating point output, add a decimal to one of the parameters: (/ 22 7.0).
Elisp can evaluate this expression in a single line, but it becomes hard to read. This example demonstrates the multitude of parenthesis in Lisp expressions. Some people jokingly suggest that Lisp means “Lots of Irritating Superfluous Parentheses”. The smartparens package can help you write code.
Prettyprinting is a way to format source code to make it easier for human readers to understand. In Emacs, you can convert a convoluted expression to prettyprinting with the pp-macroexpand-last-sexp function. Run this function at the end of an expression, and the pp package, the pretty printer for Emacs Lisp, will provide a better formatted version.
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4.0 5))))) (* 3 (- 6 2 ) (- 2 7)))
;; Pretty printing (pp-macroexpand-last-sexp)
(/
(+ 5 4
(- 2
(- 3
(+ 6
(/ 4.0 5)))))
(* 3
(- 6 2 )
(- 2 7)))Exercise 1.3
Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
Answer
defun declares a new function in Emacs Lisp. The name of the function appears after defun and its parameters are listed between parentheses. The quoted string on the next line is the documentation. The doc string will be accessible via the Emacs help functions.
The square function returns the square of a number and the sum-of-squares helper function produces the sum of squares. The main function determines the two largest numbers of three and provides the sum of their squares..
;; Exercise 1.3
(defun square (a)
"Squaring a number"
(* a a))
(defun sum-of-squares (a b)
"Sum the squares of two numbers"
(+
(square a)
(square b)))
(defun largest-sum-of-squares (a b c)
"Find the largest sum of squares for two out of three numbers"
(cond ((and (< a b) (< a c)) (sum-of-squares b c))
((and (< b a) (< b c)) (sum-of-squares a c))
(t (sum-of-squares a b))))
(largest-sum-of-squares 2 3 5)
(largest-sum-of-squares 3 2 5)
(largest-sum-of-squares 5 2 3)The three functions are bow available through the whole Emacs session. The variables are only available within each function (scoping rules).
Exercise 1.4
Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:
(defun a-plus-abs-b (a b)
(funcall
(if (> b 0)
'+
'-)
a b))
(a-plus-abs-b 10 -20)Answer
The function evaluates as follows:
- If
bis positive, the function evaluates(+ a b) - If
bis negative, the function evaluates(- a b)
funcall evaluates the expression (if (> b 0) '+ '-)) and uses the result (either + or -) as a function. The quote is needed to ensure the + and - are not evaluated in the conditional.
The original Scheme implementation used in the book and lectures did not use a function call. Scheme is a Lisp-1 and Emacs Lisp is Lisp-2. In scheme names and procedures are located in the same namespace, so it is possible to return a procedure name from a condition and evaluate it. In Lisp-2, procedures have their own namespace, so in order to call procedure from name you have to use funcal (Source: /u/andreyorst).
Exercise 1.5
Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:
(defun p () (p))
(defun test (x y)
(if (= x 0)
0
y))Then he evaluates the expression:
(test 0 (p))What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)
Answer
- Applicative order: The function call results in an infinite loop, as the function
pcalls itself (Emacs' behaviour). - Normal order: The function never reaches
pbecause it exits with 0 as a result.
Exercise 1.6
Alyssa P. Hacker doesn't see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:
(defun new-if (predicate then-clause else-clause)
(cond (predicate then-clause)
(t else-clause)))Eva demonstrates the program for Alyssa:
(new-if (= 2 3) 0 5)
(new-if (= 1 1) 0 5)Delighted, Alyssa uses new-if to rewrite the square-root program:
(defun sqrt-iter (guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))What happens when Alyssa attempts to use this to compute square roots? Explain.
Answer
(defun sqrt (x)
(defun square (x)
(* x x))
(defun good-enough? (guess)
(< (abs (- (square guess) x)) 0.001))
(defun average (a b)
(/ (+ a b) 2.0))
(defun improve (guess)
(average guess (/ x guess)))
(defun sqrt-iter (guess)
(new-if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
(sqrt 2)
(average 12 13)
The version with new-if function crashes because of a nesting error (Lisp nesting exceeds ‘max-lisp-eval-depth). The sqrt function works fine with the regular if function.
Exercise 1.7
The good-enough? test used in computing square roots will not be effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for huge numbers.
Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough?,is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess.
Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?
Answer
The float function forces floating point answers. See Elisp manual about Numeric Conversions.
;; Exercise 1.7
(defun sqrt-heron (x)
"Determine a square root using Heron’s method."
(defun avg (x y) (/ (+ (float x) y) 2))
(defun abs (x) (if (< x 0) (- x) x ))
(defun improve (guess)
(avg guess (/ x guess)))
(defun good-enough? (guess next-guess)
(< (abs (- guess next-guess)) 1e-20))
(defun try (guess)
(if (good-enough? guess (improve guess))
guess
(try (improve guess))))
(try 1.0))
(sqrt-heron 1234567890)
(* (sqrt-heron 1e-5) (sqrt-heron 1e-5))Exercise 1.8
Newton’s method for cube roots is based on the fact that if $y$ is an approximation to the cube root of $x$, then a better approximation is given by the value:
$$\frac{x/y^2 +2y}{3}$$
Use this formula to implement a cube-root procedure analogous to the square-root procedure.
Answer
;; Exercise 1.8
(defun cube-root-newton (x)
"Newton’s method for cube roots"
(defun abs (x) (if (< x 0) (- x) x ))
(defun improve (guess)
(/ (+ (/ x (* guess guess)) (* 2 guess)) 3.0))
(defun good-enough? (guess next-guess)
(< (abs (- guess next-guess)) 1e-20))
(defun try (guess)
(if (good-enough? guess (improve guess))
guess
(try (improve guess))))
(try 1.0))
(cube-root-newton (* 4 4 4))
(cube-root-newton 1e-5)Share this content
