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))))
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
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.
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)))
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.
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.
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
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.
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))))Kaihao
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,
let g(x,y)=ax+by+c0, h(x,y)= dx+ey+c1 so for all x0,
So for all x0,
②-①, 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
chm
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)))master
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.
tf3
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?
Anon
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)))Tianxiang Xiong
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)))))shyam
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:
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.
To be clearly out of doubt see this:
pluies
(define f (let ((init (- 1))) (lambda (x) (if (= init (- 1)) (set! init x) 0))))aaa
(define f (let ((init (/ 1 2))) (lambda (x) (set! init (- x init)) init)))MathieuBorderé
Dumb solution :-)
GP
My solution
(define f (let ((x 1)) (lambda (y) (if (= x 1) (begin (set! x (+ x 1)) y) 0))))musungujim
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)))))x3v
Exercise illustrates the potential dangers which can arise from assignment.
pat
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))))haha
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)))