Topics:SICP in other languages:Forth:Chapter 1
From CTMWiki
| Table of contents |
|
|
[edit]
About Forth and SICP
The following Forth code is derived from the examples provided in the book:
"Structure and Interpretation of Computer Programs, Second Edition"
by Harold Abelson and Gerald Jay Sussman with Julie Sussman.
http://mitpress.mit.edu/sicp/
(These were started in Quartus Forth, a 16-bit Forth for the old style Palm. They have now been tested on GNU Forth, which is available for most desktop systems.)
A reference to the standard words used in the example code may be found here:
Another tutorial by Mitch Bradley for potential OLPC Open Firmware users:
[edit]
SICP Chapter #01 Examples in Forth
[edit]
\ 1.1.1 The Elements of Programming - Expressions
Forth expressions are postfix, unlike Scheme, which is a prefix language. Numbers are pushed onto a data stack and operators and other words take their arguments from that stack and push their results back to the stack.
486 . 137 349 + . 1000 334 - . 5 99 * . 10 5 / .
Forth is an untyped language rather than a dynamically typed language like Scheme. Most operators work upon the untyped data stack, which may contain integers, characters or addresses. Many Forths have a separate floating point stack with separate words for dealing with this stack.
2.7e 10.0e f+ f.
Forth words normally take constant numbers of parameters off the data stack, unlike Scheme which allows words to take variable numbers of arguments.
21 35 + 12 + 7 + . 25 4 * 12 * .
Like Scheme, there is no need for operator precedence or grouping parentheses in a postfix language.
3 5 * 10 6 - + . 3 2 4 * 3 5 + + * 10 7 - 6 + + .
[edit]
\ 1.1.2 The Elements of Programming - Naming and the Environment
variable size 2 size ! size @ . size @ 5 * . 3.14159e fconstant pi fvariable radius 10e radius f! radius f@ fdup f* pi f* f. fvariable circumference radius f@ pi f* 2e f* circumference f! circumference f@ f.
[edit]
\ 1.1.3 The Elements of Programming - Evaluating Combinations
2 4 6 * + 3 5 + 7 + * .
[edit]
\ 1.1.4 The Elements of Programming - Compound Procedures
: square ( x -- x^2 ) dup * ; 21 square . 2 5 + square . 3 square square . : sum-of-squares ( x y -- x^2+y^2 ) square swap square + ; 3 4 sum-of-squares . : f ( a -- f ) dup 2* swap 1+ sum-of-squares ; 5 f .
[edit]
\ 1.1.5 The Elements of Programming - The Substitution Model for Procedure Application
5 f . 5 dup 2* swap 1+ sum-of-squares . 6 10 square swap square + . 6 10 dup * swap dup * + . 100 36 + . 5 f . 5 dup 2* swap 1+ sum-of-squares . 5 5 2* swap 1+ sum-of-squares . 5 10 swap 1+ sum-of-squares . 10 5 1+ sum-of-squares . 10 6 sum-of-squares . 10 6 square swap square + . 10 6 dup * swap square + . 10 6 6 * swap square + . 10 36 swap square + . 36 10 square + . 36 10 dup * + . 36 10 10 * + . 36 100 + . 136 .
[edit]
\ 1.1.6 The Elements of Programming - Conditional Expressions and Predicates
\ ABS is a standard function
: abs-0 ( x -- x )
dup 0> if else
dup 0= if else
negate then then ;
: abs ( x -- x ) dup 0< if negate then ;
6 value x
x 5 > x 10 < and . \ 0 is false, -1 is true, "and" is bitwise
x 6 10 within . \ synonym
7 to x \ a value is like a constant that can be changed
: ge-0 ( x y -- ? )
2dup > >r = r> or ;
: ge-1 ( x y -- ? ) < 0= ;
\ Exercise 1.1
10 .
5 3 + 4 + .
9 1- . \ decrement
6 2/ . \ arithmetic shift right 1
2 4 * 4 6 - + .
3 value a
a 1+ value b
a b 2dup * + + .
a b = .
: fn ( a b -- n )
2dup < if
2dup * over > if
swap
then
then
drop ;
a b fn .
: fn ( a b -- n )
over 4 = if
2drop 6
else 4 = if
6 + 7 +
else
drop 25
then then ;
a b fn .
a b max 2 + .
: fn ( a b -- n )
2dup = if 2drop -1 else max then ;
a b fn a 1+ * .
\ Exercise 1.2
5e 4e f+ 2e 3e 6e 4e 5e f/ f+ f- f- f+
3e 6e 2e f- f* 2e 7e f- f* f/ f.
\ Exercise 1.4
: abs+ ( a b -- n ) abs + ;
\ Exercise 1.5
: p recurse ;
: test ( x y -- ) swap 0= if drop 0 then ;
\ commented out as this is in infinite loop
\ 0 p test
[edit]
\ 1.1.7 The Elements of Programming - Example: Square Roots by Newton's Method
: fsquare ( f -- f^2) fdup f* ;
: good-enough ( x guess -- ? )
fsquare f- fabs 0.001e f< ;
\ or using the standard function f~ ( fa fb margin -- ? )
: good-enough? ( x guess -- ? )
fsquare 0.001e f~ ;
: f2/ ( x -- x/2 ) 0.5e f* ;
: average ( x y -- )
f+ f2/ ;
: improve ( guess x -- new-guess )
fover f/ average ;
: sqrt-iter ( x guess -- x^0.5 )
fover fover good-enough? if
fswap fdrop \ fnip
else
fover improve recurse
then ;
: sqrt-rec ( x -- x^0.5 ) 1e sqrt-iter ;
: sqrt-loop ( x -- x^0.5 )
1e
begin
fover improve
fover fover good-enough?
until
fswap fdrop ;
: sqrt sqrt-loop ;
9e sqrt f.
100e 37e f+ sqrt f.
2e sqrt 3e sqrt f+ sqrt f.
1000e sqrt fsquare f.
Unlike Scheme, Forth is not guaranteed to optimize tail recursion, so most of the tail recursive examples will also be expressed using the standard loop constructs BEGIN-WHILE-REPEAT, BEGIN-UNTIL, and DO-LOOP. It is interesting to note that Charles H. Moore, the inventor of Forth, later went on to create the dialect colorForth (http://www.colorforth.com/cf.html) which does guarantee tail recursion optimization, where it is used for many types of iteration.
Exercise 1.6 has little meaning in Forth, it being an exploration of the Scheme if special form and the difference between eager and lazy evaluation. In Forth, IF-THEN and other structured programming constructs are handled differently: they are IMMEDIATE words which lay down branches at compile-time. Evaluation in Forth is extremely eager.
[edit]
\ 1.1.8 The Elements of Programming - Procedures as Black-Box Abstractions
: f2* ( f -- 2*f ) fdup f+ ;
: square-log ( f -- f^2 ) fln f2* fexp ;
: sqrt-log ( f -- f^0.5) fln f2/ fexp ;
: good-enough? ( x guess -- ? )
fsquare-log 0.001e f~ ;
: improve ( guess x -- new-guess )
fover f/ average ;
: sqrt ( x -- x^0.5 )
1e
begin
fover improve
fover fover good-enough?
until
fswap fdrop ;
5e fsquare f.
5e fsquare-log f.
Forth is a far more static langauge than Scheme. There are no scoping equivalents in Forth, but you have DEFER-IS for late-bound replaceable functions like fsquare. Although you can have anonymous functions with :NONAME, you cannot declare them within the local scope of a word definition.
You can achieve something like lexical scope using wordlists, but that is a rather advanced topic. Such mechanisms have been used to construct object syntax and other sub-languages within Forth.
[edit]
\ 1.2.1 Procedures and the Processes They Generate - Linear Recursion and Iteration
\ Recursive
: factorial ( n -- n! )
dup 1 = if
else dup 1- recurse * then ;
\ Iterative
: fact-iter ( n -- n! )
1 swap 1 ?do
i *
loop ;
\ tail-recursive
: (fact) ( p n -- p*n )
dup 1 = if drop else
tuck * swap 1- ( p*n n-1 )
recurse
then ;
: factorial-2 ( n -- n! ) 1 swap (fact) ;
\ Exercise 1.9
: inc 1+ ;
: dec 1- ;
: plus ( a b -- a+b )
?dup if
dec + inc
then ;
: plus-1
?dup if
dec swap inc +
then ;
\ Exercise 1.10 (Ackermann function)
: ack ( n m -- p)
dup 0= if drop 1+ exit then
swap dup 0= if 1+ else
1- over recurse
then
swap 1- recurse ;
10 1 ack .
4 2 ack .
3 3 ack .
: fx ( n -- n ) 0 ack ;
: g ( n -- n ) 1 ack ;
: h ( n -- n ) 2 ack ;
: k ( n -- n ) dup * 5 * ;
\ Exercise 1.11
: fi ( n -- n )
dup 3 < if else
1- dup 1- dup 1-
recurse 3 * swap recurse 2* + swap recurse +
then ;
: fi-iter ( n -- n )
0 1 2
3 roll 0 ?do
rot 3 * 2 pick 2* + over +
loop 2drop ;
\ Exercise 1.12
: pascals-triangle ( k n -- p )
dup 0= if 2drop 1 exit then
over 0= if 2drop 1 exit then
2dup = if 2drop 1 exit then
1- over 1- over
recurse -rot recurse + ;
[edit]
\ 1.2.2 Procedures and the Processes They Generate - Tree Recursion
\ Recursive
: fib ( n -- f )
dup 2 < if exit then
1- dup recurse swap 1- recurse + ;
\ Iterative
: fib-iter ( n -- f )
0 1
rot 0 ?do
over + swap
loop drop ;
\ Counting change
: table create does> swap cells + @ ;
table coin-value 0 , 1 , 5 , 10 , 25 , 50 ,
: count-change ( total coin -- n )
over 0= if
2drop 1
else over 0< over 0= or if
2drop 0
else
2dup coin-value - over recurse
>r 1- recurse r> +
then then ;
100 5 count-change .
[edit]
\ 1.2.3 Procedures and the Processes They Generate - Orders of Growth
\ Exercise 1.15
: cubed ( f -- f^3 ) fdup fdup f* f* ;
: p ( f -- p ) fdup 3e f* fswap cubed 4e f* f- ;
: sine ( radians -- sin )
fdup fabs 0.1e f> if
3e f/ recurse p
then ;
\ check
1e sine f.
1e fsin f. \ built-in
[edit]
\ 1.2.4 Procedures and the Processes They Generate - Exponentiation
\ Linear recursion
: expt ( b n -- b^n )
dup 0= if 2drop 1 else
over swap 1- recurse * then ;
\ Linear iteration
: expt-iter ( b n -- b^n )
1 swap
0 ?do
over *
loop nip ;
\ Logarithmic iteration
: even? 1 and 0= ;
: fast-expt ( b n -- b^n )
dup 0= if 2drop 1 else
dup 1 = if drop else
dup 2 = if drop dup * else
dup even? If >r dup * r> 2/ recurse
else over dup * swap 2/ recurse *
then then then then ;
: odd? 1 and ;
: faster-expt
1 swap begin dup while
dup odd? If >r over * else >r then
>r dup * r> r> 2/
repeat drop nip ;
\ Exercise 1.17
: multiply ( a b -- a*b )
dup 0= if nip exit then
1- over * + ;
\ Exercise 1.19
\ exercise left to reader to solve for p' and q'
: fib-iter ( b a q p count -- fib )
dup 0= if 2drop 2drop exit then
dup even? if
2/ >r ( exercise: q p -- q' p' ) r> recurse
else
\ local variable syntax is simplest
{ b a q p count }
b p * a q * +
b q * a q * + a p * +
q p count 1- recurse
then ;
: fib ( n -- fib ) >r 0 1 1 0 r> fib-iter ;
[edit]
\ 1.2.5 Procedures and the Processes They Generate - Greatest Common Divisors
: gcd ( m n -- gcd ) begin ?dup while tuck mod repeat ;
[edit]
\ 1.2.6 Procedures and the Processes They Generate - Example: Testing for Primality
\ prime
: divides? ( a b -- f ) mod 0= ;
\ optimization: above 2, we only need to look at odd divisors
: next-d dup 2 > if 1+ then 1+ ;
: find-divisor ( n t -- d )
2dup square < if drop else
2dup divides? if nip else
1+ ( next-d) recurse then then ;
: prime? dup 2 find-divisor = ;
\ fast prime
: expmod ( nbase m exp -- n )
dup 0= if drop 2drop 1 exit then
dup even? if
2/ over >r recurse square r> mod
else
1- >r 2dup r> recurse rot * swap mod
then ;
\ Forth doesn't define a standard random number generator
\ linear congruential RNG choose ( n -- 0..n-1 )
HEX
HERE VALUE seed
: RANDOM ( -- u ) seed 107465 * 234567 + DUP TO seed ;
: CHOOSE ( n -- 0 <= u < n ) RANDOM UM* NIP ;
DECIMAL
: fermat ( n -- )
dup choose 1+ ( n a )
dup rot dup expmod = ;
: fast-prime? ( n count -- ? )
0 ?do
dup fermat 0= if drop false unloop exit then
loop
drop true ;
\ Exercise 1.22: timing comparison
\ second timer (warning: rolls over at the end of the month)
\ (modern computers would rather have a subsecond timer)
: secs time&date ( s m h D M Y )
2drop 24 * + 60 * + 60 * + ;
: (time) ( [s] xt -- )
secs >r execute
secs r> - ." *** " . ." seconds" cr ;
: time: ( [s] -- ) ' (time) ;
101 time: prime? .
1010101 9 time: fast-prime?
\ Exercise 1.25
: expmod-1 ( nbase m nexp -- n )
swap >r fast-expt r> mod ;
\ Exercise 1.26
\ not sure about this: the JavaScript solution is identical to expmod
[edit]
\ 1.3 Formulating Abstractions with Higher-Order Procedures
: fcube ( f -- f^3 ) fdup fdup f* f* ;
[edit]
\ 1.3.1 Formulating Abstractions with Higher-Order Procedures - Procedures as Arguments
: sum-integers ( a b -- s )
2dup > if 2drop 0 exit then
over 1+ swap recurse + ;
: sum-integers ( a b -- sum )
0 -rot 1+ swap do i + loop ;
: sum-cubes ( a b -- sum )
0 -rot 1+ swap do i dup dup * * + loop ;
: 1/f 1e fswap f/ ;
: pi-sum ( a b -- fsum )
0e 1+ swap do
i s>d d>f fdup 2e f+ f* 1/f f+
4 +loop ;
\ DEFER-IS
defer term ( a -- f[a] )
: sum ( a b -- sum )
0 -rot 1+ swap do
i term +
loop ;
: cube ( a -- a^3 ) dup dup * * ;
: sum-cubes ( a b -- s )
['] cube is term sum ;
: noop ( a -- a ) ; \ predefined in many Forths
: sum-integers ( a b -- s )
['] noop is term sum ;
1 10 sum-cubes .
1 10 sum-integers .
\ execution token (XT) on the stack
fvariable finc
: fsum ( xt F: fb fa -- fsum )
0e frot frot ( F: sum b a )
begin fover fover f< 0=
while frot fover ( xt F: b a sum a ) dup execute f+
frot frot finc f@ f+
repeat
fdrop fdrop drop ;
: pi-term ( a -- f[a] ) fdup 2e f+ f* 1/f ;
: pi-sum ( fb fa -- fsum )
['] pi-term 4e finc f! fsum ;
1000e 1e pi-sum 8e f* f.
: integral ( xt fb fa fdx -- )
fdup finc f! f2/ f+ fsum finc f@ f* ;
' fcube 1e 0e 0.01e integral f.
' fcube 1e 0e 0.001e integral f.
\ Exercise 1.29
: simpson ( xt-fn n F: a b -- f )
fover f- fabs dup s>f f/ ( a inc )
fswap 0e ( inc a accum )
0 do
frot frot fover f+ frot
fover dup execute f+
loop fnip fnip drop ;
' fcube 100 0e 1e simpson f.
\ Exercise 1.30
: f1+ 1e f+ ;
: sum ( xt-fn xt-inc F: a b -- f )
fswap 0e frot frot ( acc b a )
begin
frot fover over execute f+
frot frot dup execute
fover fover f<
until fdrop fdrop ;
: sum-cubes ( a b -- f ) ['] fcube ['] f1+ sum ;
1e 10e sum-cubes f.
\ Exercise 1.31
\ a. & b.
: product ( xt-fn xt-inc F: a b -- f )
fswap 1e frot frot ( acc b a )
begin
frot fover over execute f*
frot frot dup execute
fover fover f<
until fdrop fdrop ;
: factorial ( n -- f ) 1e s>f ['] noop ['] f1+ product ;
[edit]
GOT TO HERE
Code following this heading is yet to be converted from JavaScript to Forth.
// Exercise 1.32
// a.
function accumulate(combiner, nullValue, term, a, next, b) {
if (a > b)
return nullValue;
else return combiner(term(a), accumulate(combiner, nullValue, term, next(a), next, b));
}
// sum: accumulate(plus, 0, identity, a, inc, b);
//
// function times(a, b) { return a * b; }
// product: accumulate(times, 1, identity, a, inc, b);
// b.
// NOTE: starting value of 'acc' is 'nullValue'
function accumulate_iter(combiner, term, a, next, b, acc) {
if (a > b)
return acc;
else return accumulate_iter(combiner, term, next(a), next, b, combiner(acc, term(a)));
}
// sum: accumulate_iter(plus, identity, a, inc, b, 0);
//
// function times(a, b) { return a * b; }
// product: accumulate_iter(times, identity, a, inc, b, 1);
// Exercise 1.33
function filtered_accumulate(combiner, nullValue, term, a, next, b, pred) {
if (a > b)
return nullValue;
else if (pred(a))
return combiner(term(a), filtered_accumulate(combiner, nullValue, term, next(a), next, b, pred));
else return filtered_accumulate(combiner, nullValue, term, next(a), next, b, pred);
}
// a.
filtered_accumulate(plus, 0, square, 1, inc, 5, prime); // 39
// b. Not sure how to implement this without modifying 'filtered_accumulate' to have 'pred'
// accept two arguments
[edit]
// 1.3.2 Formulating Abstractions with Higher-Order Procedures - Constructing Procedures Using Lambda
function pi_sum_2(a, b) {
return sum(
function(x) { return 1.0 / (x * (x + 2.0)); },
a,
function(x) { return x + 4.0 },
b);
}
function integral_1(f, a, b, dx) {
return sum(f, a + (dx / 2.0), function(x) { return x + dx; }, b) * dx;
}
function plus4(x) { return x + 4; }
plus4_1 = function(x) { return x + 4; }
print ((function(x, y, z) { return x + y + square(z) }) (1, 2, 3));
// Using let
function f_1(x, y) {
function f_helper(a, b) {
return (x * square(a)) + (y * b) + (a * b);
}
return f_helper(1 + (x * y), 1 - y)
}
function f_2(x, y) {
return (function(a, b) { return (x * square(a)) + (y * b) + (a * b); }) (1 + (x * y), 1 - y);
}
function f_3(x, y) {
a = 1 + (x * y);
b = 1 - y;
return (x * square(a)) + (y * b) + (a * b);
}
// javascript does not have let binding - used lambda to emulate
var x = 5;
print (function() {
var x = 3;
return x + (x * 10);
}() + x);
var x = 2;
print (function(x) {
var y = x + 2;
var x = 3;
return x * y;
}(x));
function f_4(x, y) {
a = 1 + (x * y);
b = 1 - y;
return (x * square(a)) + (y * b) + (a * b);
}
// Exercise 1.34
function f_5(g) { return g(2); }
print (f_5(square));
print (f_5(function(z) { return z * (z + 1) } ));
[edit]
// 1.3.3 Formulating Abstractions with Higher-Order Procedures - Procedures as General Methods
// Half-interval method
function close_enough(x, y) {
return (abs(x - y) < 0.001);
}
function positive(x) { return (x >= 0.0); }
function negative(x) { return !(positive(x)); }
function search(f, neg_point, pos_point) {
midpoint = average(neg_point, pos_point);
if (close_enough(neg_point, pos_point)) return midpoint;
else
test_value = f(midpoint);
if (positive(test_value)) return search(f, neg_point, midpoint);
else if (negative(test_value)) return search(f, midpoint, pos_point);
else return midpoint;
}
function half_interval_method(f, a, b) {
a_value = f(a);
b_value = f(b);
if (negative(a_value) && positive(b_value)) return search(f, a, b);
else if (negative(b_value) && positive(a_value)) return search(f, b, a);
else throw ("Exception: Values are not of opposite sign " + a + " " + b);
}
print (half_interval_method(Math.sin, 2.0, 4.0));
print (half_interval_method(function(x) { return (x * x * x) - (2.0 * x) - 3.0; }, 1.0, 2.0));
// Fixed points
tolerance = 0.00001
function fixed_point(f, first_guess) {
function close_enough(v1, v2) {
return abs(v1 - v2) < tolerance;
}
function tryit(guess) {
next = f(guess);
if (close_enough(guess, next)) return next;
else return tryit(next);
}
return tryit(first_guess);
}
print (fixed_point(Math.cos, 1.0));
print (fixed_point(function(y) { return Math.sin(y) + Math.cos(y); }, 1.0));
// note: this function does not converge
function sqrt_4(x) {
return fixed_point(function(y) { return parseFloat(x) / y; }, 1.0)
}
function sqrt_5(x) {
return fixed_point(function(y) { return average(y, parseFloat(x) / y); }, 1.0)
}
// Exercise 1.35
function golden_ratio() {
return fixed_point(function(x) { return 1.0 + 1.0 / x; }, 1.0);
}
// Exercise 1.36
// Add the following line to function, 'fixed_point':
// ... var next = f(guess);
// print(next);
// ... if (close_enough(guess, next))
print(fixed_point(function(x) { return Math.log(1000.0) / Math.log(x); }, 1.5));
// Exercise 1.37
// exercise left to reader to define cont_frac
// cont_frac(function(i) { return 1.0; }, function(i) { return 1.0; }, k)
// Exercise 1.38 - unfinished
// Exercise 1.39 - unfinished
[edit]
// 1.3.4 Formulating Abstractions with Higher-Order Procedures - Procedures as Returned Values
function average_damp(f) {
return (function(x) { return average(parseFloat(x), f(x)); } )
}
print ((average_damp(square)) (10.0));
// Exercise 1.36 continued ...
print(fixed_point(average_damp(function(x) { return Math.log(1000.0) / Math.log(x); }), 1.5));
function sqrt_6(x) {
return fixed_point(average_damp(function(y) { return parseFloat(x) / y; }), 1.0);
}
function cube_root(x) {
return fixed_point(average_damp(function(y) { return parseFloat(x) / square(y); }), 1.0)
}
print (cube_root(8));
// Newton's method
dx = 0.00001
function deriv(g) {
return (function(x){ return parseFloat(g(x + dx) - g(x)) / dx; });
}
function cube_2(x) { return x * x * x; }
print (deriv(cube_2) (5.0));
function newton_transform(g) {
return (function(x) { return x - (parseFloat(g(x)) / (deriv(g) (x))); });
}
function newtons_method(g, guess) {
return fixed_point(newton_transform(g), guess);
}
function sqrt_7(x) {
return newtons_method(function(y) { return square(y) - x; } , 1.0);
}
// Fixed point of transformed function
function fixed_point_of_transform(g, transform, guess) {
return fixed_point(transform(g), guess);
}
function sqrt_8(x) {
return fixed_point_of_transform(function(y) { return x / y; }, average_damp, 1.0);
}
function sqrt_9(x) {
return fixed_point_of_transform(function(y) { return square(y) - x; }, newton_transform, 1.0)
}
// Exercise 1.40
function cubic(a, b, c) {
return function(x) { return x * x * x + a * x * x + b * x + c; };
}
print(newtons_method(cubic(5.0, 3.0, 2.5), 1.0)); // -4.452...
// Exercise 1.41
function double_(f) {
return function(x) { return f(f(x)); };
}
print((double_(inc))(5)); // 7
print((double_(double_(inc)))(5)); // 9
print((double_(double_(double_(inc))))(5)); // 13
// Exercise 1.42
function compose_(f, g) {
return function(x) { return f(g(x)); };
}
print((compose_(square, inc))(6)); // 49
// Exercise 1.43
function repeated(f, n) {
function iterate(arg, i) {
if (i > n)
return arg;
else return iterate(f(arg), i + 1);
}
return function(x) { return iterate(x, 1); };
}
print((repeated(square, 2))(5)); // 625
// Exercise 1.44 ('n-fold-smooth' not implemented)
function smooth(f, dx) {
return function(x) { return average(x, (f(x - dx) + f(x) + f(x + dx)) / 3.0); };
}
print(fixed_point(smooth(function(x) { return Math.log(1000.0) / Math.log(x); }, 0.05), 1.5));
// Exercise 1.45 - unfinished
// Exercise 1.46 ('sqrt' not implemented)
function iterative_improve(good_enough, improve) {
function iterate_(guess) {
var next = improve(guess);
if (good_enough(guess, next))
return next;
else return iterate_(next);
}
return function(x) { return iterate_(x); };
}
function fixed_point_(f, first_guess) {
var tolerance = 0.00001;
function good_enough(v1, v2) {
return Math.abs(v1 - v2) < tolerance;
}
return (iterative_improve(good_enough, f))(first_guess);
}
print(fixed_point_(average_damp(function(x) { return Math.log(1000.0) / Math.log(x); }), 1.5));
// Note: Must be careful using lexical scoping in JavaScript.
// The following will print "after"
var vx = "before";
function fv() { return vx; }
var vx = "after";
print (fv());
// The following will print "second" two times
function fg() { return "first"; }
print(fg());
function fg() { return "second"; }
print(fg());
</script>
</body>
</html>
![[Main Page]](/wiki/stylesheets/images/wiki.png)