let* to evaluate
the arguments of let in order.Here's some useful code about the equality of different functions in the context of the end of 3.1
#lang sicp
(define (make-decrementer balance)
(lambda (amount)
(- balance amount)))
(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))
(eq? D1 D2) ; => #f
(eqv? D1 D2) ; => #f
(equal? D1 D2) ; => #f
(define D3 D2)
(eq? D2 D3)
(eqv? D2 D3)
(equal? D2 D3)
#f #f #f #t #t #t
Relating to the "order of updates", I recently stumbled across an interesting post by Dan Piponi about changing the order of updates of an iterative algorithm and looking at the result. mathoverflow post, mathstodon.xyz post.
Referential transparency : "Absence of side effects is a necessary, but not sufficient, condition for referential transparency. Referential transparency means that an expression (such as a function call) can be replaced with its value. This requires that the expression is pure, that is to say the expression must be deterministic (always give the same value for the same input) and side-effect free."
Resources on writing a Lisp interpreter:
Not related to this chapter, but I forgot about it until now:
An accumulator is a
procedure that is called repeatedly with a single numeric argument and
accumulates its arguments into a sum. Each time it is called, it returns the
currently accumulated sum. Write a procedure make-accumulator that
generates accumulators, each maintaining an independent sum. The input to
make-accumulator should specify the initial value of the sum; for
example
(define A (make-accumulator 5))
(A 10)
15
(A 10)
25
#lang sicp
(define (make-accumulator n)
(let ((total n))
(lambda (arg)
(begin
(set! total (+ total arg))
total))))
(define A (make-accumulator 5))
(A 10)
(A 10)
15 25
In software-testing applications,
it is useful to be able to count the number of times a given procedure is
called during the course of a computation. Write a procedure
make-monitored that takes as input a procedure, f, that itself
takes one input. The result returned by make-monitored is a third
procedure, say mf, that keeps track of the number of times it has been
called by maintaining an internal counter. If the input to mf is the
special symbol how-many-calls?, then mf returns the value of the
counter. If the input is the special symbol reset-count, then mf
resets the counter to zero. For any other input, mf returns the result
of calling f on that input and increments the counter. For instance, we
could make a monitored version of the sqrt procedure:
(define s (make-monitored sqrt))
(s 100)
10
(s 'how-many-calls?)
1
#lang sicp
(define (make-monitored func)
(let ((ncalls 0))
(lambda (arg)
(cond ((eq? arg 'how-many-calls?) ncalls)
((eq? arg 'reset-count) (set! ncalls 0))
(else (begin
(set! ncalls (+ ncalls 1))
(func arg)))))))
(define s (make-monitored sqrt))
(s 100)
(s 9)
(s 'how-many-calls?)
(s 'reset-count)
(s 'how-many-calls?)
10 3 2 0
Modify the make-account
procedure so that it creates password-protected accounts. That is,
make-account should take a symbol as an additional argument, as in
(define acc
(make-account 100 'secret-password))
The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint:
((acc 'secret-password 'withdraw) 40)
60
((acc 'some-other-password 'deposit) 50)
"Incorrect password"
#lang sicp
(define (make-account balance pw)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (errorfunc . args)
"Incorrect Password")
(define (dispatch pw-arg m)
(cond ((not (eq? pw pw-arg)) errorfunc)
((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request:
MAKE-ACCOUNT" m))))
dispatch)
(define acc
(make-account 100 'secret-password))
((acc 'secret-password 'withdraw) 40)
;60
((acc 'some-other-password 'deposit) 50)
;"Incorrect password"
60 "Incorrect Password"
Modify the make-account
procedure of Exercise 3.3 by adding another local state variable so that,
if an account is accessed more than seven consecutive times with an incorrect
password, it invokes the procedure call-the-cops.
I structured this answer in a bit of a weird way, I want the "cops called" message to display when the function is returned. Not when the returned function is called by the user.
#lang sicp
(define (make-account balance pw)
(let ((num-consec-fails 0))
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (call-the-cops)
(display ">:( cops called") (newline))
(define (return-errorfunc)
(begin
(set! num-consec-fails (+ num-consec-fails 1))
(if (> num-consec-fails 7)
(begin (call-the-cops)
(lambda args "N/A"))
(lambda args "Incorrect Password"))))
(define (dispatch pw-arg m)
(if (not (eq? pw pw-arg))
(return-errorfunc)
(begin
(set! num-consec-fails 0)
(cond
((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request:
MAKE-ACCOUNT" m))))))
dispatch))
(define acc
(make-account 100 'secret-password))
((acc 'secret-password 'withdraw) 40)
;60
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
;"Incorrect password"
60 "Incorrect Password" "Incorrect Password" "Incorrect Password" "Incorrect Password" "Incorrect Password" "Incorrect Password" "Incorrect Password" >:( cops called "N/A"
Monte Carlo integration is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate $P(x, y)$ that is true for points $(x, y)$ in the region and false for points not in the region. For example, the region contained within a circle of radius 3 centered at (5, 7) is described by the predicate that tests whether ${(x - 5)^2 + {(y - 7)^2 \le 3^2}}$. To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at (2, 4) and (8, 10) contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points $(x, y)$ that lie in the rectangle, and testing $P(x, y)$ for each point to determine whether the point lies in the region. If we try this with many points, then the fraction of points that fall in the region should give an estimate of the proportion of the rectangle that lies in the region. Hence, multiplying this fraction by the area of the entire rectangle should produce an estimate of the integral.
Implement Monte Carlo integration as a procedure estimate-integral that
takes as arguments a predicate P, upper and lower bounds x1,
x2, y1, and y2 for the rectangle, and the number of trials
to perform in order to produce the estimate. Your procedure should use the
same monte-carlo procedure that was used above to estimate $\pi$.
Use your estimate-integral to produce an estimate of $\pi$ by
measuring the area of a unit circle.
You will find it useful to have a procedure that returns a number chosen at
random from a given range. The following random-in-range procedure
implements this in terms of the random procedure used in
1.2.6, which returns a nonnegative number less than its
input.
(define (random-in-range low high)
(let ((range (- high low)))
(+ low (random range))))
#lang sicp
(define RAND-MAX 2147483647)
(define (random-float low high)
(let ((range (- high low)))
(+ low (* range (/ (* 1.0 (random RAND-MAX) ) RAND-MAX)))))
(define (estimate-integral P x1 x2 y1 y2 ntrials)
(define (e-inner n estimate)
(if (< n 1)
estimate
(e-inner (- n 1)
(+ estimate (if (P (random-float x1 x2)
(random-float y1 y2)) 1 0)))))
(* (/ (* 1.0 (e-inner ntrials 0)) ntrials)
(- x2 x1)
(- y2 y1)))
(define (square x) (* x x))
(estimate-integral
(lambda (x y) (< (+ (square x) (square y)) 1))
-1 1 -1 1 1000000)
3.142948
It is useful to be able to reset a
random-number generator to produce a sequence starting from a given value.
Design a new rand procedure that is called with an argument that is
either the symbol generate or the symbol reset and behaves as
follows: (rand 'generate) produces a new random number; ((rand
'reset) ⟨new-value⟩) resets the internal state variable to the
designated ⟨new-value⟩. Thus, by resetting the state, one can generate
repeatable sequences. These are very handy to have when testing and debugging
programs that use random numbers.
#lang sicp
(define A 1664525)
(define B 1013904223)
(define C 4294967296)
(define random-init 1000000)
(define (rand-update arg)
(remainder (+ (* A arg) B) C))
(define rand
(let ((x random-init))
(lambda (m)
(cond ((eq? m 'generate)
(set! x (rand-update x)) x)
((eq? m 'reset)
(lambda (arg) (set! x arg)))
(else (error "invalid message" m))))))
(rand 'generate)
(rand 'generate)
(rand 'generate)
(display "Resetting") (newline)
((rand 'reset) 12345)
(rand 'generate)
(rand 'generate)
(display "Resetting") (newline)
((rand 'reset) 12345)
(rand 'generate)
(rand 'generate)
3386560671 187819378 394593833 Resetting 87628868 71072467 Resetting 87628868 71072467
Consider the bank account objects
created by make-account, with the password modification described in
Exercise 3.3. Suppose that our banking system requires the ability to
make joint accounts. Define a procedure make-joint that accomplishes
this. Make-joint should take three arguments. The first is a
password-protected account. The second argument must match the password with
which the account was defined in order for the make-joint operation to
proceed. The third argument is a new password. Make-joint is to create
an additional access to the original account using the new password. For
example, if peter-acc is a bank account with password
open-sesame, then
(define paul-acc
(make-joint peter-acc
'open-sesame
'rosebud))
will allow one to make transactions on peter-acc using the name
paul-acc and the password rosebud. You may wish to modify your
solution to Exercise 3.3 to accommodate this new feature.
#lang sicp
(define (make-account balance pw)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (errorfunc . args)
"Incorrect Password")
(define (dispatch pw-arg m)
(cond ((not (eq? pw pw-arg)) errorfunc)
((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request:
MAKE-ACCOUNT" m))))
dispatch)
(define (make-joint orig-account orig-password new-password)
(lambda (pw-arg m)
(if (eq? pw-arg new-password)
(orig-account orig-password m)
(lambda args "Incorrect password"))))
(define peter-acc
(make-account 100 'peter-password))
(define paul-acc
(make-joint peter-acc
'peter-password
'paul-password))
((peter-acc 'peter-password 'withdraw) 10)
;; 90
((paul-acc 'paul-password 'withdraw) 10)
;; 80
((paul-acc 'peter-password 'withdraw) 10)
;; "Incorrect password"
90 80 "Incorrect password"
When we defined the evaluation
model in 1.1.3, we said that the first step in evaluating an
expression is to evaluate its subexpressions. But we never specified the order
in which the subexpressions should be evaluated (e.g., left to right or right
to left). When we introduce assignment, the order in which the arguments to a
procedure are evaluated can make a difference to the result. Define a simple
procedure f such that evaluating
(+ (f 0) (f 1))
will return 0 if
the arguments to + are evaluated from left to right but will return 1 if
the arguments are evaluated from right to left.
#lang sicp
(define my-num 0)
(define (f a)
(let ((prev my-num))
(begin (set! my-num (+ my-num a))
prev)))
;; Default evaluation
(+ (f 0) (f 1))
;; Forcing things to evaluate the opposite order
(set! my-num 0)
(let ((sec (f 1))
(fir (f 0)))
(+ fir sec))
0 1