Topics:SICP in other languages:Prolog:Chapter 1
From CTMWiki
| Table of contents |
[edit]
About SICP
The following Prolog 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/
[edit]
SICP Chapter #1 Examples in Prolog
% Execute using following command-line ['sicp01.pro' assumed to be source name]:
%
% pl -q -t halt -g main -s sicp01.pro
%
eval(Expr, Evaluator, Result) :-
P =.. [Evaluator, Result, Expr],
call(P).
is_arithmetic(Expr) :- catch(is(_, Expr), _, fail).
println(Expr) :-
(var(Expr) ->
format('*unbound Variable*~n')
;
(compound(Expr) ->
(is_arithmetic(Expr) ->
eval(Expr, is, Result), format('~a~n', [Result])
;
(callable(Expr) ->
(call(Expr) -> Result = succeeded ; Result = failed),
format('~p : ~a~n', [Expr, Result])
;
format('~p~n', [Expr])))
;
format('~a~n', [Expr]))).
%
% The code between %SWI% markers is used in the higher-order programming examples; it was
% obtained from the mailing list submission:
%
% http://gollem.science.uva.nl/SWI-Prolog/mailinglist/archive/old/2073.html
%
% My thanks to Richard O'Keefe for making public such simple, but profoundly instructive, code.
%
%SWI%
:-(lambda, Body) :- call(Body).
:-(lambda(X1), Body, A1) :- subst([X1=A1], Body, Body1), call(Body1).
:-(lambda(X1,X2), Body, A1, A2) :- subst([X1=A1,X2=A2], Body, Body1), call(Body1).
:-(lambda(X1,X2,X3), Body, A1, A2, A3) :- subst([X1=A1,X2=A2,X3=A3], Body, Body1), call(Body1).
:-(lambda(X1,X2,X3,X4), Body, A1, A2, A3, A4) :- subst([X1=A1,X2=A2,X3=A3,X4=A4], Body, Body1), call(Body1).
subst(Map, B0, B) :-
(var(B0) ->
(member(V=R, Map), V == B0 -> B = R ; B = B0)
;
functor(B0, F, N), functor(B, F, N), subst(N, B0, B, Map)).
subst(N, B0, B, Map) :-
(N > 1 ->
arg(N, B0, A0), arg(N, B, A), subst(Map, A0, A), M is N - 1, subst(M, B0, B, Map)
;
N < 1 ->
true
;
arg(1, B0, A0), arg(1, B, A), subst(Map, A0, A)).
%SWI%
main :-
section_1_1_1,
section_1_1_2,
section_1_1_3,
section_1_1_4,
section_1_1_5,
section_1_1_6,
section_1_1_7,
section_1_1_8,
section_1_2_1,
section_1_2_2,
section_1_2_3,
section_1_2_4,
section_1_2_5,
section_1_2_6,
section_1_3_1,
section_1_3_2,
section_1_3_3,
section_1_3_4.
[edit]
% 1.1.1 The Elements of Programming - Expressions
section_1_1_1 :- println(486), println(137 + 349), println(1000 - 334), println(5 * 99), println(10 mod 5), println(2.7 + 10), println(21 + 35 + 12 + 7), println(25 * 4 * 12), println((3 * 5) + (10 - 6)), println((3 * ((2 * 4) + (3 + 5))) + ((10 - 7) + 6)).
[edit]
% 1.1.2 The Elements of Programming - Naming and the Environment
section_1_1_2 :- Size is 2, println(Size), println(Size * 5), Pi is 3.14259, Radius is 10.0, println(Pi * Radius * Radius), Circumference is 2.0 * Pi * Radius, println(Circumference).
[edit]
% 1.1.3 The Elements of Programming - Evaluating Combinations
section_1_1_3 :- println((2 + (4 * 6)) * (3 + 5 + 7)).
[edit]
% 1.1.4 The Elements of Programming - Compound Procedures
:- arithmetic_function(square/1). :- arithmetic_function(sum_of_squares/2). :- arithmetic_function(f/1). square(X, Result) :- Result is (X) * (X). sum_of_squares(X, Y, Result) :- Result is (X) * (X) + (Y) * (Y). f(A, Result) :- sum_of_squares(A + 1, A * 2, Result). section_1_1_4 :- println(square(21)), println(square(2 + 5)), println(square(square(3))), sum_of_squares(3, 4, _), println(f(5)).
[edit]
% 1.1.5 The Elements of Programming - The Substitution Model for Procedure Application
section_1_1_5 :- println(f(5)), println(sum_of_squares(5 + 1, 5 * 2)), println(square(6) + square(10)), println((6 * 6) + (10 * 10)), println(36 + 100), println(f(5)), println(sum_of_squares(5 + 1, 5 * 2)), println(square(5 + 1) + square(5 * 2)), println(((5 + 1) * (5 + 1)) + ((5 * 2) * (5 * 2))), println((6 * 6) + (10 * 10)), println(36 + 100), println(136).
[edit]
% 1.1.6 The Elements of Programming - Conditional Expressions and Predicates
:- arithmetic_function(abs0/1).
:- arithmetic_function(abs1/1).
:- arithmetic_function(three_n/3).
:- arithmetic_function(a_plus_abs_b/2).
abs0(X, Result) :- number(X), abs_0(X, Result).
abs_0(0, 0).
abs_0(X, Result) :- X < 0, Result is -X ; Result is X.
abs1(X, Result) :- number(X), abs_1(X, Result).
abs_1(X, Result) :- X < 0, Result is -X ; Result is X.
ge(X, Y) :- (X > Y) ; (X =:= Y).
ge_1(X, Y) :- \+(X < Y).
% Exercise 1.3 %
three_n(N1, N2, N3, Result) :-
(N1 > N2 ->
(N1 > N3 ->
(N2 > N3 ->
Result is N1 * N1 + N2 * N2
;
Result is N1 * N1 + N3 * N3)
;
Result is N1 * N1 + N3 * N3)
;
(N2 > N3 ->
(N1 > N3 ->
Result is N2 * N2 + N1 * N1
;
Result is N2 * N2 + N3 * N3)
;
Result is N2 * N2 + N3 * N3)).
% Exercise 1.4 %
a_plus_abs_b(A, B, Result) :-
(B > 0), Result is A + B ; Result is A - B.
% Exercise 1.5 %
p :- p.
test(X, Y, Result) :- ((X =:= 0), Result is 0 ; call(Y)).
section_1_1_6 :-
X = 6,
println(((X > 5), (X < 10))),
% Exercise 1.1 %
println(10),
println(5 + 3 + 4),
println(9 - 1),
println(6 // 2),
println((2 * 4) + (4 - 6)),
A = 3,
B is A + 1,
println(A + B + (A * B)),
println(A =:= B),
((B > A), (B < (A * B)), R = B ; R = A),
println(R),
((A =:= 4), R1 is 6 ; ((B =:= 4), R1 is 6 + 7 + A ; R1 = 25)),
println(R1),
((B > A), R2 = B ; R2 = A),
println(2 + R2),
((A > B), R3 = A ; ((A < B), R3 = B ; R3 = -1)),
println(R3 * (A + 1)),
% Exercise 1.2 %
println((5.0 + 4.0 + (2.0 - (3.0 - (6.0 + (4.0 / 5.0))))) / (3.0 * (6.0 - 2.0) * (2.0 - 7.0))),
% Exercise 1.3 %
println(three_n(1, 2, 3)),
println(three_n(1, 3, 2)),
println(three_n(2, 1, 3)),
println(three_n(2, 3, 1)),
println(three_n(3, 2, 1)),
println(three_n(3, 1, 2)),
% Exercise 1.4 %
println(a_plus_abs_b(1, 3)),
println(a_plus_abs_b(1, -3)),
% Exercise 1.5 %
% Infinite loop if first argument is not 0
test(0, p, _).
[edit]
% 1.1.7 The Elements of Programming - Example: Square Roots by Newton's Method
:-arithmetic_function(average/2).
:-arithmetic_function(sqrt/1).
:-arithmetic_function(sqrt_gp/1).
:-arithmetic_function(cube_root/1).
good_enough(Guess, X) :- Result is square(Guess) - X, abs0(Result) < 0.001.
average(X, Y, Result) :- Result is (X + Y) / 2.0.
improve(Guess, X, Result) :- Result is average(Guess, X / Guess).
sqrt_iter(Guess, X, Result) :-
(good_enough(Guess, X) ->
Result is Guess
;
improve(Guess, X, NewGuess),
sqrt_iter(NewGuess, X, Result)).
sqrt(X, Result) :- sqrt_iter(1.0, X, Result).
% Exercise 1.6 - unfinished %
% Exercise 1.7 %
good_enough_gp(Guess, Prev) :- Result is abs0(Guess - Prev) / Guess, Result < 0.001.
sqrt_iter_gp(Guess, Prev, X, Result) :-
(good_enough_gp(Guess, Prev) ->
Result is Guess
;
improve(Guess, X, NewGuess),
sqrt_iter_gp(NewGuess, Guess, X, Result)).
sqrt_gp(X, Result) :- sqrt_iter_gp(4.0, 1.0, X, Result).
% Exercise 1.8 %
improve_cube(Guess, X, Result) :- Result is (2.0 * Guess + X / (Guess * Guess)) / 3.0.
cube_iter(Guess, Prev, X, Result) :-
(good_enough_gp(Guess, Prev) ->
Result is Guess
;
improve_cube(Guess, X, NewGuess),
cube_iter(NewGuess, Guess, X, Result)).
cube_root(X, Result) :- cube_iter(27.0, 1.0, X, Result).
section_1_1_7 :-
println(sqrt(9)),
println(sqrt(100 + 37)),
println(sqrt(sqrt(2) + sqrt(3))),
println(square(sqrt(1000))),
% Exercise 1.6 - unfinished %
% Exercise 1.7 %
println(sqrt_gp(9)),
% Exercise 1.8 %
println(cube_root(27)).
[edit]
% 1.1.8 The Elements of Programming - Procedures as Black-Box Abstractions
:-arithmetic_function(double/1).
:-arithmetic_function(square_1/1).
:-arithmetic_function(sqrt_1/1).
double(X, Result) :- Result is X + X.
square_1(X, Result) :- Result is exp(double(log(X))).
good_enough_1(Guess, X) :- Result is square_1(Guess) - X, abs0(Result) < 0.001.
improve_1(Guess, X, Result) :- Result is average(Guess, X / Guess).
sqrt_iter_1(Guess, X, Result) :-
(good_enough_1(Guess, X) ->
Result is Guess
;
improve_1(Guess, X, NewGuess),
sqrt_iter_1(NewGuess, X, Result)).
sqrt_1(X, Result) :- sqrt_iter_1(1.0, X, Result).
section_1_1_8 :-
% Prolog is not a functional language, and has no built-in support for many facilities found
% in such languages, including:
%
% * Block Structure i.e. lexical scoping, nested procedures, and closures
% * Anonymous Procedures
%
% Put simply, the ready lack of such facilities ensures that higher-order programming ala
% Scheme is not idiomatic in Prolog [though it can be done, albeit a little clumsily, using
% call/N and 'univ']. However, with some work, it is possible to approximate the behaviour of
% some of the aforementioned facilities, so as to allow higher-order programming 'ala Scheme'.
%
% The code to do this is included in the header [between the %SWI% markers].
%
% The examples in sections 1.3.2 onwards make use of this code. The block structured and
% lexically scoped examples in this section, which require the definition of nested procedures,
% cannot be completed because:
%
% * Procedure definitions must be top-level
% * Variable scope is procedure-level i.e. local to each procedure
%
println(sqrt_1(25)).
[edit]
% 1.2.1 Procedures and the Processes They Generate - Linear Recursion and Iteration
:- arithmetic_function(factorial/1).
:- arithmetic_function(factorial_1/1).
:- arithmetic_function(inc/1).
:- arithmetic_function(dec/1).
:- arithmetic_function(plus_0/2).
:- arithmetic_function(plus_1/2).
:- arithmetic_function(a/2).
:- arithmetic_function(f_1/1).
:- arithmetic_function(g_1/1).
:- arithmetic_function(h_1/1).
:- arithmetic_function(k_1/1).
% Recursive %
factorial(1, 1).
factorial(N, Result) :- N1 is N - 1, factorial(N1, R1), Result is R1 * N.
% Iterative %
fact_iter_1(Product, Counter, Max_Count, Result) :-
(Counter > Max_Count ->
Result = Product
;
fact_iter_1(Counter * Product, Counter + 1, Max_Count, Result)).
factorial_1(N, Result) :- fact_iter_1(1, 1, N, Result).
% Exercise 1.9 %
inc(A, Result) :- Result is A + 1.
dec(A, Result) :- Result is A - 1.
plus_0(0, B, B).
plus_0(A, B, Result) :- Result is inc(dec(A) + B).
plus_1(0, B, B).
plus_1(A, B, Result) :- Result is dec(A) + inc(B).
% Exercise 1.10 %
a(_, 0, 0).
a(_, 1, 2).
a(0, Y, Result) :- Result is 2 * Y.
a(X, Y, Result) :- Result is a(X - 1, a(X, Y - 1)).
f_1(N, Result) :- Result is a(0, N).
g_1(N, Result) :- Result is a(1, N).
h_1(N, Result) :- Result is a(2, N).
k_1(N, Result) :- Result is 5 * N * N.
section_1_2_1 :-
println(a(1, 10)),
println(a(2, 4)),
println(a(3, 3)).
[edit]
% 1.2.2 Procedures and the Processes They Generate - Tree Recursion
:- arithmetic_function(fib/1).
:- arithmetic_function(fib_1/1).
:- arithmetic_function(first_denomination/1).
:- arithmetic_function(cc/2).
:- arithmetic_function(count_change/1).
:- arithmetic_function(fi/1).
:- arithmetic_function(fi_1/1).
:- arithmetic_function(pascals_triangle/2).
% Recursive %
fib(0, 0).
fib(1, 1).
fib(N, Result) :- Result is fib(N - 1) + fib(N - 2).
% Iterative %
fib_iter(A, B, Counter, Result) :-
(Counter < 1 ->
Result = B
;
fib_iter(A + B, A, Counter - 1, Result)).
fib_1(N, Result) :- fib_iter(1, 0, N, Result).
% Counting change %
first_denomination(1, 1).
first_denomination(2, 5).
first_denomination(3, 10).
first_denomination(4, 25).
first_denomination(5, 50).
cc(0, _, 1).
cc(Amount, _, Result) :- Amount < 0, Result is 0.
cc(_, 0, 0).
cc(Amount, Kinds_Of_Coins, Result) :-
Result is cc(Amount, Kinds_Of_Coins - 1) +
cc(Amount - first_denomination(Kinds_Of_Coins), Kinds_Of_Coins).
count_change(Amount, Result) :- cc(Amount, 5, Result).
% Exercise 1.11 %
fi(N, Result) :- N < 3, Result is N.
fi(N, Result) :- Result is fi(N - 1) + 2 * fi(N - 2) + 3 * fi(N - 3).
fi_iter(A, B, C, Count, Result) :-
(Count < 1 ->
Result is C
;
fi_iter(A + 2 * B + 3 * C, A, B, Count - 1, Result)).
fi_1(N, Result) :- fi_iter(2, 1, 0, N, Result).
% Exercise 1.12 %
pascals_triangle(0, _, 1).
pascals_triangle(_, 0, 1).
pascals_triangle(N, N, 1).
pascals_triangle(N, K, Result) :-
Result is pascals_triangle(N - 1, K - 1) + pascals_triangle(N - 1, N).
section_1_2_2 :-
println(fib(5)),
println(fib_1(5)),
println(count_change(100)),
println(fi(5)),
println(fi_1(5)),
println(pascals_triangle(3, 5)).
[edit]
% 1.2.3 Procedures and the Processes They Generate - Orders of Growth
:-arithmetic_function(cube/1). :-arithmetic_function(p_1/1). :-arithmetic_function(sine/1). % Exercise 1.15 % cube(X, Result) :- Result is X * X * X. p_1(X, Result) :- Result is (3.0 * X) - (4.0 * cube(X)). sine(Angle, Angle) :- \+(abs0(Angle) > 0.001), !. sine(Angle, Result) :- sine(Angle / 3.0, R1), Result is p_1(R1). section_1_2_3 :- println(cube(3)), println(p_1(3)), % Compare 'sine' results with built-in, 'sin' println(sin(60.0)), println(sine(60.0)).
[edit]
% 1.2.4 Procedures and the Processes They Generate - Exponentiation
:-arithmetic_function(even/1).
:-arithmetic_function(expt/2).
:-arithmetic_function(expt_1/2).
:-arithmetic_function(fast_expt/2).
:-arithmetic_function(expt_2/2).
% Linear recursion %
expt(_, 0, 1).
expt(B, N, Result) :- Result is B * expt(B, (N - 1)).
% Linear iteration %
expt_iter(B, Counter, Product, Result) :-
(Counter < 1 ->
Result is Product
;
expt_iter(B, Counter - 1, B * Product, Result)).
expt_1(B, N, Result) :- expt_iter(B, N, 1, Result).
% Logarithmic iteration %
even(N) :- ((N mod 2) =:= 0).
fast_expt(_, 0, 1).
fast_expt(B, N, Result) :-
(even(N) ->
Result is square(fast_expt(B, N // 2))
;
Result is B * fast_expt(B, N - 1)).
expt_2(B, N, Result) :- fast_expt(B, N, Result).
% Exercise 1.16 - unfinished %
% Exercise 1.17 - unfinished %
% Exercise 1.18 - unfinished %
% Exercise 1.19 - unfinished %
section_1_2_4 :-
println(even(3)),
println(expt(2, 3)),
println(expt_1(2, 3)),
println(expt_2(2, 3)).
[edit]
% 1.2.5 Procedures and the Processes They Generate - Greatest Common Divisors
:-arithmetic_function(gcd/2).
gcd(A, B, Result) :-
(B < 1 ->
Result is A
;
gcd(B, A mod B, Result)).
section_1_2_5 :-
println(gcd(12, 8)).
[edit]
% 1.2.6 Procedures and the Processes They Generate - Example: Testing for Primality
:-arithmetic_function(expmod/3).
:-arithmetic_function(expmod_2/3).
:-arithmetic_function(smallest_divisor/1).
% prime %
divides(A, B) :- ((B mod A) =:= 0).
find_divisor(N, Test_Divisor, Result) :-
(square(Test_Divisor) > N ->
Result is N
;
(divides(Test_Divisor, N) ->
Result is Test_Divisor
;
find_divisor(N, Test_Divisor + 1, Result))).
smallest_divisor(N, Result) :- find_divisor(N, 2, Result).
prime(N) :- smallest_divisor(N, N).
% fast_prime %
expmod(_, 0, _, 1) :- !.
expmod(Nbase, Nexp, M, Result) :-
(even(Nexp) ->
Result is square(expmod(Nbase, Nexp // 2, M)) mod M
;
Result is (Nbase * (expmod(Nbase, (Nexp - 1), M))) mod M).
fermat_test(1).
fermat_test(N) :- A is 1 + random(N - 1), expmod(A, N, N, A).
fast_prime(_, 0) :- !.
fast_prime(N, Ntimes) :- fermat_test(N), N1 is Ntimes - 1, fast_prime(N, N1).
prime_1(N) :- fast_prime(N, 2).
% Exercise 1.22 - unfinished %
% Exercise 1.23 - unfinished %
% Exercise 1.24 - unfinished %
% Exercise 1.25 %
expmod_1(Nbase, Nexp, M, Result) :- Result is fast_expt(Nbase, Nexp) mod M.
fermat_test_1(1).
fermat_test_1(N) :- A is 1 + random(N - 1), expmod_1(A, N, N, A).
fast_prime_1(_, 0) :- !.
fast_prime_1(N, Ntimes) :- fermat_test_1(N), N1 is Ntimes - 1, fast_prime_1(N, N1).
prime_1e(N) :- fast_prime_1(N, 2).
% Exercise 1.26 %
expmod_2(_, 0, _, 1) :- !.
expmod_2(Nbase, Nexp, M, Result) :-
(even(Nexp) ->
Result is (expmod_2(Nbase, (Nexp // 2), M) * expmod_2(Nbase, (Nexp // 2), M)) mod M
;
Result is (Nbase * expmod_2(Nbase, Nexp - 1, M)) mod M).
fermat_test_2(1).
fermat_test_2(N) :- A is 1 + random(N - 1), expmod_2(A, N, N, A).
fast_prime_2(_, 0) :- !.
fast_prime_2(N, Ntimes) :- fermat_test_2(N), N1 is Ntimes - 1, fast_prime_2(N, N1).
prime_2e(N) :- fast_prime_2(N, 2).
% Exercise 1.27 - unfinished %
% Exercise 1.28 - unfinished %
section_1_2_6 :-
println(prime(3)),
println(prime_1(3)),
println(prime_1e(3)),
println(prime_2e(3)),
% Exercise 1.21 %
println(smallest_divisor(199)),
println(smallest_divisor(1999)),
println(smallest_divisor(19999)).
[edit]
% 1.3 Formulating Abstractions with Higher-Order Procedures
% 'cube' from section_1_2_2
[edit]
% 1.3.1 Formulating Abstractions with Higher-Order Procedures - Procedures as Arguments
:-arithmetic_function(sum_integers/2).
:-arithmetic_function(sum_integers_1/2).
:-arithmetic_function(sum_cubes/2).
:-arithmetic_function(sum_cubes_1/2).
:-arithmetic_function(sum_cubes_2/2).
:-arithmetic_function(pi_sum/2).
:-arithmetic_function(pi_sum_1/2).
:-arithmetic_function(integral/4).
:-arithmetic_function(simpson/4).
:-arithmetic_function(factorial_2/1).
:-arithmetic_function(factorial_3/1).
:-arithmetic_function(accumulate/6).
:-arithmetic_function(accumulate_iter/6).
:-arithmetic_function(filtered_accumulate/7).
sum_integers(A, B, 0) :- A > B, !.
sum_integers(A, B, Result) :- Result is A + sum_integers(A + 1, B).
sum_cubes(A, B, 0) :- A > B, !.
sum_cubes(A, B, Result) :- Result is cube(A) + sum_cubes(A + 1, B).
pi_sum(A, B, 0.0) :- A > B, !.
pi_sum(A, B, Result) :- Result is (1.0 / (A * (A + 2.0))) + pi_sum(A + 4.0, B).
sum(_, A, _, B, 0) :- A > B, !.
sum(Term, A, Next, B, Result) :-
% Invocation of passed-in procedures 'repackaged' with local-value arguments. This approach
% allows procedures to be passed-in with zero or more arguments; such arguments can be used
% to represent the 'environment' associated with a closure [see comments below]
call(Term, A, T1),
call(Next, A, N1),
% Recursive invocation and value return
sum(Term, N1, Next, B, R1),
Result is T1 + R1.
% Using sum %
identity(X, X).
sum_cubes_1(A, B, Result) :- sum(cube, A, inc, B, Result).
sum_integers_1(A, B, Result) :- sum(identity, A, inc, B, Result).
pi_term(X, Result) :- Result is 1 / (X * (X + 2)).
pi_next(X, Result) :- Result is X + 4.0.
pi_sum_1(A, B, Result) :- sum(pi_term, A, pi_next, B, Result).
% Prolog has no support for closures. To approximate their behaviour, the 'environment' is
% packaged into the procedure argument list, and both it and the procedure [rather than
% just the procedure name] passed as an argument. The receiving procedure is expected to know
% how to handle these arguments
add_dx(Dx, X, Result) :- Result is Dx + X.
integral(F, A, B, Dx, Result) :- sum(F, A + Dx / 2, add_dx(Dx), B, R1), Result is R1 * Dx.
% Exercise 1.29 %
simpson(F, A, B, N, Result) :-
H is abs(B - A) / N,
% Were closures supported in Prolog, then 'A' and 'H' would be part of the environment.
% Here, these 'environment variables' are packaged as a list, and passed as an extra
% argument to the iterative support procedure, 'simpson_'. Note: It is possible to pass
% a procedure combined with arguments [e.g. simpson_(F(A, H), 1, ...)], but where the
% individual arguments are required (e.g. in an arithmetic computation), it is probably
% best to pass them in separately [as was done in the example]
simpson_(F, 1, inc, N, [A, H], 0.0, R1),
Result is H * R1.
% Since Prolog does not support nested procedures, top level procedures must be used [unless
% one resorts to pattern matching 'tricks' as per the code described in Section 1.1.8; in
% practice, however, this approach would probably be avoided since it impinges on code
% clarity]. In order to indicate that such procedures operate as support / helper procedures,
% stylistic conventions are often adopted. One such convention is to:
% * Name the support / helper procedure(s) the same as the parent procedure, but append
% an underscore character
% * Define these procedure(s) below the parent procedure, as well as indented the same as
% the parent procedure's code
simpson_(_, Start, _, Stop, _, Acc, Acc) :- Start > Stop, !.
simpson_(Term, Start, Next, Stop, EnvList, Acc, Result) :-
% Unpack 'environment variables'
[A, H] = EnvList,
TermArg is Start * H + A,
call(Term, TermArg, T1),
call(Next, Start, N1),
simpson_(Term, N1, Next, Stop, EnvList, Acc + T1, Result).
% Exercise 1.30 %
sum_iter(_, A, _, B, Acc, Acc) :- A > B, !.
sum_iter(Term, A, Next, B, Acc, Result) :-
call(Term, A, T1),
call(Next, A, N1),
sum_iter(Term, N1, Next, B, Acc + T1, Result).
% 'sum_cubes_2' reimplements 'sum_cubes_1' but uses 'sum_iter' in place of 'sum'
sum_cubes_2(A, B, Result) :- sum_iter(cube, A, inc, B, 0, Result).
% Exercise 1.31 %
% a.
product(_, A, _, B, 1) :- A > B, !.
product(Term, A, Next, B, Result) :-
call(Term, A, T1),
call(Next, A, N1),
product(Term, N1, Next, B, R1),
Result is T1 * R1.
factorial_2(N, Result) :- product(identity, 1, inc, N, Result).
% b.
product_iter(_, A, _, B, Acc, Acc) :- A > B, !.
product_iter(Term, A, Next, B, Acc, Result) :-
call(Term, A, T1),
call(Next, A, N1),
product_iter(Term, N1, Next, B, Acc * T1, Result).
factorial_3(N, Result) :- product_iter(identity, 1, inc, N, 1, Result).
plus_(X, Y, Result) :- Result is X + Y.
times_(X, Y, Result) :- Result is X * Y.
% Exercise 1.32 %
% a.
accumulate(_, NullValue, _, A, _, B, NullValue) :- A > B, !.
accumulate(Combiner, NullValue, Term, A, Next, B, Result) :-
call(Term, A, T1),
call(Next, A, N1),
accumulate(Combiner, NullValue, Term, N1, Next, B, R1),
call(Combiner, T1, R1, Result).
% sum: accumulate(plus_, 0, identity, A, inc, B).
% product: accumulate(times_, 1, identity, A, inc, B).
% b.
% NOTE: starting value of 'Acc' is 'NullValue'
accumulate_iter(_, _, A, _, B, Acc, Acc) :- A > B, !.
accumulate_iter(Combiner, Term, A, Next, B, Acc, Result) :-
call(Term, A, T1),
call(Next, A, N1),
call(Combiner, Acc, T1, C1),
accumulate_iter(Combiner, Term, N1, Next, B, C1, Result).
% sum: accumulate_iter(plus_, identity, A, inc, B, 0).
% product: accumulate_iter(times_, identity, A, inc, B, 1).
% Exercise 1.33 %
filtered_accumulate(_, NullValue, _, A, _, B, Pred, NullValue) :- A > B, !.
filtered_accumulate(Combiner, NullValue, Term, A, Next, B, Pred, Result) :-
call(Next, A, N1),
(call(Pred, A) ->
filtered_accumulate(Combiner, NullValue, Term, N1, Next, B, Pred, R1),
call(Term, A, T1),
call(Combiner, T1, R1, Result)
;
filtered_accumulate(Combiner, NullValue, Term, N1, Next, B, Pred, Result)).
% a.
% filtered_accumulate(plus, 0, square, 1, inc, 5, prime).
section_1_3_1 :-
println(sum_cubes(1, 10)),
println(sum_cubes_1(1, 10)),
println(sum_integers(1, 10)),
println(sum_integers_1(1, 10)),
println(8.0 * pi_sum(1.0, 1000.0)),
println(8.0 * pi_sum_1(1.0, 1000.0)),
integral(cube, 0.0, 1.0, 0.01, R1), println(R1),
integral(cube, 0.0, 1.0, 0.001, R2), println(R2),
simpson(cube, 0.0, 1.0, 100, R3), println(R3),
println(sum_cubes_2(1, 10)),
println(factorial_2(5)),
println(factorial_3(5)),
accumulate(plus_, 0, identity, 1, inc, 5, R4), println(R4),
accumulate(times_, 1, identity, 1, inc, 5, R5), println(R5),
accumulate_iter(plus_, identity, 1, inc, 5, 0, R6), println(R6),
accumulate_iter(times_, identity, 1, inc, 5, 1, R7), println(R7),
filtered_accumulate(plus_, 0, square, 1, inc, 5, prime, R8), println(R8).
[edit]
% 1.3.2 Formulating Abstractions with Higher-Order Procedures - Constructing Procedures Using Lambda
%
% Prolog does not directly support anonymous functions i.e. lambdas. However, it is
% possible to mimic such functionality through pattern matching. Importantly, the
% 'anonymous' function is actually named ['lambda' in the current example] so that it
% can be 'executed'. The relevant code is described in Section 1.1.8, and can be found
% in the header.
%
:-arithmetic_function(pi_sum_2/2).
:-arithmetic_function(integral_2/4).
:-arithmetic_function(f_2/2).
:-arithmetic_function(f_3/2).
:-arithmetic_function(f_4/2).
:-arithmetic_function(f_5/2).
:-arithmetic_function(f_6/2).
pi_sum_2(A, B, Result) :-
sum((lambda(X, Result) :- Result is 1.0 / (X * (X + 2.0))),
A,
(lambda(X, Result) :- Result is X + 4.0),
B,
Result).
integral_2(F, A, B, Dx, Result) :-
sum(F,
A + Dx / 2,
(lambda(X, Result) :- Result is Dx + X),
B,
R1),
Result is R1 * Dx.
plus4(X) :- X + 4.
% Using let %
f_2(X, Y, Result) :-
F_Helper = (lambda(A, B, Result) :- Result is (X * square(A)) + (Y * B) + (A * B)),
call(F_Helper, (1 + (X * Y)), (1 - Y), Result).
f_3(X, Y, Result) :-
call((lambda(A, B, Result) :- Result is (X * square(A)) + (Y * B) + (A * B)),
(1 + (X * Y)), (1 - Y), Result).
f_4(X, Y, Result) :-
A is 1 + (X * Y),
B is 1 - Y,
Result is (X * square(A)) + (Y * B) + (A * B).
f_5(X, Y, Result) :-
A is 1 + (X * Y),
B is 1 - Y,
Result is (X * square(A)) + (Y * B) + (A * B).
% Exercise 1.34 %
f_6(G, Result) :- call(G, 2, Result).
section_1_3_2 :-
println(8.0 * pi_sum_2(1.0, 1000.0)),
integral_2(cube, 0.0, 1.0, 0.001, R1), println(R1),
Plus4 = (lambda(X, Result) :- Result is X + 4),
call(Plus4, 8, R4), println(R4),
call((lambda(X, Y, Z, Result) :- Result is X + Y + square(Z)), 1, 2, 3, R5),
println(R5),
println(f_2(1, 2)),
println(f_3(1, 2)),
println(f_4(1, 2)),
println(f_5(1, 2)),
% Exercise 1.34 %
f_6(square, R6), println(R6),
f_6((lambda(Z, Result) :- Result is Z * (Z - 1)), R7), println(R7).
[edit]
% 1.3.3 Formulating Abstractions with Higher-Order Procedures - Procedures as General Methods
section_1_3_3 :- true.
[edit]
% 1.3.4 Formulating Abstractions with Higher-Order Procedures - Procedures as Returned Values
section_1_3_4 :- true.
![[Main Page]](/wiki/stylesheets/images/wiki.png)