sicp-ex-3.8

bro_chenzox

I have tried to use all of solutions but no any of them is accepting my test that you can find below the solution. I just have a little bit redone aaa's answer.

``` (define f
(let ((init 0))
(λ (x)
(set! init (- x init))
(- x init))))
```
```(+ (f 0) (f 1))
(+ (f 1) (f 0))
(+ (f 0) (f 1))
(+ (f 1) (f 0))
(+ (f 1) (f 0))
(+ (f 0) (f 1))
(+ (f 0) (f 1))
```

Here is a more generalized solution.

let

``` (define f
(let ((init x0))
(lambda (x)
(set! init (g init x))
(h init x))))
```

g and h are procedures to be detemined.

So for all x0,

```h(g(x0,0),0)+h(g(g(x0,0),1),1)=0
h(g(x0,1),1)+h(g(g(x0,1),0),0)=1
```

let g(x,y)=ax+by+c0, h(x,y)= dx+ey+c1 so for all x0,

```h(ax0+c0,0)+h(a^2*x0+(a+1)c0+b,1)=0
h(ax0+b+c0,1)+h(a^2*x0+ab+(a+1)c0,0)=1
```

So for all x0,

```d((a^2+a)x0+(a+2)c0+b)+e+2c1=0 ①
d((a^2+a)x0+(a+1)b+(a+2)c0)+2+2c1=0 ②
```

②-①, we get abd=1 ③

and for all x0, both ① and ② are true. So d(a^2+a)=0 ④

from ③ and ④, we have a=-1 and bd=-1. So ① becomes c0d+e+2c1=1

So all of h(x,y) and g(x,y) are ok as long as a=-1, bd=-1 and c0d+e+2c1=1

for example, a=-1, b=1, c0=0, d=-1, e=1, c1=0 and we have

``` ;; here we have x0 set to 0, but any value is ok
(define f
(let ((init 0))
(lambda (x)
(set! init (- x init))
(- x init))))

;; Test
(+ (f 0) (f 1))
(+ (f 1) (f 0))
(+ (f 0) (f 1))
(+ (f 1) (f 0))
(+ (f 1) (f 0))
(+ (f 0) (f 1))
(+ (f 0) (f 1))
```

Lot's of solutions already, but I figured I might add this since it's pretty simple and in my opinion more elegant than some of the others, since it's a function that could be useful in some situations other than just solving this exercise

``` (define f
(let ((count 1))
(lambda (x)
(set! count (* count x))
count)))
```

Nice idea but unfortunately it isn't quite right, the answer depends on whether f has ever been called with an argument of zero, whereas I think it is supposed to depend only on the evaluation order.

There's no problem in his code, as it satisfies the requirements of the question.

But to be frank, here we have two calls to the same function f and we are summing them like f(0) + f(1). Ordinarily, if you see a function f which returns numerical values (as is the case here) which are then added in successive calls to the function (eg. like during recursive calls to fibonacci), you wouldn't want them to behave in such a way in the first place. I mean such a behaviour is definitely contrived (it was asked here so no problem), but in a language like C, which I assume would evaluate such an expression on a first come basis, this behaviour can be demonstrated, if you just do f(1) + f(0) instead of f(0) + f(1), if you keep a static variable inside of it and use it in calculating the return value of f.

But the question is, why would anyone do this?

```why would anyone do this?
```

IMHO your 2nd paragraph is a bit messy with one long sentence "I mean such a behaviour ... return value of f". You may want to ask why f(1) will be designed to "change over time" and then still used as "f(0) + f(1)". This is so weird.

---

bro_chenzox's and Kaihao's actually do 2 op's for each call of f. IMHO this is a bit too complex for this problem.

If we just think simpler and follow the pattern of the book 1st (withdraw amount), i.e. doing 1 op. Then we can think of this op is one binary operation f-op. Then we have (+ (f-op v 0) (f-op (f-op v 0) 1)) for "from left to right" and (+ (f-op v 1) (f-op (f-op v 1) 0)) for "from right to left". The interesting thing here is that 1 is identity of * and 0 is identity of +. So I tried to let f-op be *. So we have 0 for "from left to right" and v for "from right to left" (Here many things are consumed by 0 when doing * operation).

Although the above thought process to get chm's * solution is a bit by coincidence, but the idea of "consumed by 0" makes sense for this exercise.

The simplest solution to me is based on an observation that the whole expression is essentially supposed to evaluate to the first argument given to f. I.e. when evaluating from the left, we start with 0 and get 0 in the end; when evaluating from the right, we start with 1 and get 1 in the end.

Therefore, we can just return 0 if f has never been called (rendering this call meaningless in the addition expression), and the argument given in the previous call otherwise.

``` (define f (let ((second-last-call 0)
(last-call 0))
(lambda (n)
(set! second-last-call last-call)
(set! last-call n)
second-last-call)))
```

aaa's solution is incorrect.

pluies' solution is nearly correct, except that set! does not return a value.

The following makes use of the simple observation that we can solve the problem if we return the argument of f if we have not called it before and 0 if we have previously called it.

``` (define f
(let ((called #f))
(lambda (x)
(if called
0
(begin
(set! called #t)
x)))))
```

Exercise 3.8. When we defined the evaluation model in section 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.

Solution:

``` (define (g y)
(define (f x)
(let ((z y))
(set! y x)
z))
f)
(define f (g 0))
```
``` The question is given in the context of explaining how the introduction of assignment in procedure produce differences in result when the same procedure is evaluated repeatedly with arguments in different order. i.e to show that calling f twice with arguments in the order (f 0) and then (f 1) is different from (f 1) and (f 0).
```

Anyway it is pretty obvious that we are to design f with a local state variable in it ;-)

We can write the function in many ways to make the local state variable give the desired result for the above two calls. I Wrote it the way that the local state variable introduces a delayed response. procedure g is used to set the local environment for f. So we can initialize the local state variable as the argument to g. In this case g returns the desired f when called with the argument 0

In order to simulate the left to right and right to left evaluation, we can change the order of arguments to the given + as shown below. It is evaluated in MIT GNU/Scheme. It is seen to be evaluating from right to left Just to be clear, g and f are revaluated after each experiment.

```1 ]=>
;Value: g

1 ]=>
;Value: f

1 ]=> (+ (f 1) (f 0))

;Value: 0

1 ]=>
;Value: g

1 ]=>
;Value: f

1 ]=> (+ (f 0) (f 1))

;Value: 1
```

To be clearly out of doubt see this:

```1 ]=>
;Value: g

1 ]=>
;Value: f

1 ]=> (f 0)

;Value: 0

1 ]=> (f 1)

;Value: 0

1 ]=>
;Value: g

1 ]=>
;Value: f

1 ]=> (f 1)

;Value: 0

1 ]=> (f 0)

;Value: 1

1 ]=>
```

``` (define f
(let ((init (- 1)))
(lambda (x) (if (= init (- 1))
(set! init x)
0))))
```

``` (define f
(let ((init (/ 1 2)))
(lambda (x)
(set! init  (- x init))
init)))
```

``` (define f
(let ((state 0))
(lambda (arg)
(begin state (set! state arg)))))

;;; testing - rename to avoid confusion
(define g
(let ((state 0))
(lambda (arg)
(begin state (set! state arg)))))

(+ (g 0) (g 1))
Value: 1

(define h
(let ((state 0))
(lambda (arg)
(begin state (set! state arg)))))

(+ (h 1) (h 0))
Value: 0

```

``` (define left_to_right 666)

(define (f x)
(cond ((= x 0) (begin (set! left_to_right 999)
0))
((and (= x 1) (= left_to_right 666)) 0)
((and (= x 1) (= left_to_right 999)) 1)))
```

My solution

```
(define f
(let ((x 1))
(lambda (y)
(if (= x 1)
(begin (set! x (+ x 1)) y)
0))))
```

Simple back and forth state switching. Reusable in the context of a sub-expression of 2 argument addition. Odd number of calls switches the initial state.

```
(define f
(let ((state 0))
(lambda (x)
(if (= state 1)
(begin (set! state 0)
state)
(begin (set! state 1)
x)))))
```

Exercise illustrates the potential dangers which can arise from assignment.

```
(define f
(let ((x 0))
(lambda (y)
(if (> y x)
(set! x y)
x))))

;; Scheme evaluates arguments from right to left
(+ (f 0) (f 1)) ;; 1
(+ (f 1) (f 0)) ;; 0
```

This behavior can also simply arise from caching values, starting with 0 cached, and then returning the cached value and resetting each time.

```
(define f
(let ((cached 0))
(lambda (new)
(let ((return-value cached))
(set! cached new)
return-value))))

```

My solution

```
(define ff
(let ((first #t))
(lambda (s)
(define r 0)
(if (and first (= s 1))
(set! r 1))
(set! first (not first))
r)))

```