Example:
// This module implements the Fibonacci function. It also gives a
// solution to the second problem from Project Euler
// (projecteuler.net), viz.,
//
// "Each new term in the Fibonacci sequence is generated by adding the
// previous two terms. By starting with 1 and 2, the first 10 terms
// will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
//
// By considering the terms in the Fibonacci sequence whose values do
// not exceed four million, find the sum of the even-valued terms.
// Answer: 4613732"
val (+) = mod32::+;
// This is a simple but reasonably efficent implementation of the
// Fibonacci function.
val fun fib(x i32) = purify i32 {
new a = new_i32(0);
new b = new_i32(1);
for _ in 0..x {
val old_a = get a;
val old_b = get b;
a := old_b;
b := old_a + old_b;
}
yield(get a);
};
// Test the first few terms of the Fibonacci function.
assert fib(0) = 0 is i32;
assert fib(1) = 1 is i32;
assert fib(2) = 1 is i32;
assert fib(3) = 2 is i32;
assert fib(4) = 3 is i32;
assert fib(5) = 5 is i32;
assert fib(6) = 8 is i32;
assert fib(7) = 13 is i32;
assert fib(8) = 21 is i32;
assert fib(46) = 1836311903 is i32;
// Compile the Fibonacci function.
compile fib(x i32) i32 = block { yield(fib(x)); };
test fib(46) = 1836311903;
// Here is the resulting LLVM listing.
//
// define i32 @fib(i32 %x) {
// entry:
// br label %begin
//
// begin: ; preds = %loop, %entry
// %b = phi i32 [ 1, %entry ], [ %1, %loop ]
// %a = phi i32 [ 0, %entry ], [ %b, %loop ]
// %range = phi i32 [ 0, %entry ], [ %2, %loop ]
// %0 = icmp ult i32 %range, %x
// br i1 %0, label %loop, label %end
//
// loop: ; preds = %begin
// %1 = add i32 %a, %b
// %2 = add i32 %range, 1
// br label %begin
//
// end: ; preds = %begin
// ret i32 %a
// }
val (<) = mod32::<;
val (==) = mod32::==;
val fun (x bool) && (y bool) = x ? y : false;
val fun (x bool) || (y bool) = x ? true : y;
val fun (x i32) <= (y i32) = x < y || x == y;
val and = mod32::and;
val fun (I interface) ++ (J interface) interface = meth {
false: I,
true: J
};
val fun !(x bool) = x ? false : true;
val i_range interface = meth(_ i32) void;
val range type = i_range => void;
val i_break interface = meth(_ i32) bool;
val break type = i_break => bool;
assert catch is
dep(b type) ->
dep(i interface) ->
dep(a type) ->
dep(f b -> i => a) ->
(i ++ (meth(_ b) enum{}) => a) ->
i => a;
val fun breakable(rng range) break =
catch(void)(i_break)(bool)(fun(_) block { yield(false); })(
block {
for c in rng {
val x = do call(false@c);
if !x { val y = do call(true@()); yield(do fun{}(y)); }
}
yield(true);
});
// This solution to the second Euler problem is very inefficient and
// doesn't use any properties of the Fibonacci sequence to optimize
// the algorithm.
//
// One natural solution to this problem is to use a while loop, but
// there are currently no plans to implement while loops in IPL, as
// all programs in type theory must be terminating.
//
// A future version of IPL will support range loops with break and
// continue, and, more generally, an efficiently implemented
// throw/catch construct that can be used to break out of (possibly
// nested) loops.
val fun euler2(max i32) = purify i32 {
new sum = new_i32(0);
val _ bool = for i in breakable(0..max) {
val a = fib(i);
// Count a if a <= max and the lsb of a is unset.
if a <= max {
if and(a, 1) == 0 {
sum := sum + a;
}
yield(true); // continue
} else {
yield(false); // break
}
}
yield(get sum);
};
// Check that we have a correct solution.
assert euler2(4000000) = 4613732 is i32;
// Compile the solution to the second Euler problem.
compile euler2(max i32) i32 = block { yield(euler2(max)); };
// Check that the compiled function works too.
test euler2(4000000) = 4613732;
// The compiled version of euler2 is rather interesting.
//
//
// define i32 @euler2(i32 %max) {
// entry:
// %0 = icmp sgt i32 %max, 2
// br i1 %0, label %merge37, label %false38
//
// merge37: ; preds = %false38, %entry
// %merge40 = phi i32 [ %phitmp, %false38 ], [ 2, %entry ]
// %1 = icmp sgt i32 %max, 8
// %2 = icmp eq i32 %max, 8
// %. = select i1 %1, i1 true, i1 %2
// %3 = or i32 %merge40, 8
// %local_cell.6 = select i1 %., i32 %3, i32 %merge40
// %4 = icmp sgt i32 %max, 34
// %5 = icmp eq i32 %max, 34
// %.793 = select i1 %4, i1 true, i1 %5
// %6 = add i32 %local_cell.6, 34
// %local_cell.9 = select i1 %.793, i32 %6, i32 %local_cell.6
// %7 = icmp sgt i32 %max, 144
// %8 = icmp eq i32 %max, 144
// %.794 = select i1 %7, i1 true, i1 %8
// %9 = add i32 %local_cell.9, 144
// %local_cell.12 = select i1 %.794, i32 %9, i32 %local_cell.9
// %10 = icmp sgt i32 %max, 610
// %11 = icmp eq i32 %max, 610
// %.795 = select i1 %10, i1 true, i1 %11
// %12 = add i32 %local_cell.12, 610
// %local_cell.15 = select i1 %.795, i32 %12, i32 %local_cell.12
// %13 = icmp sgt i32 %max, 2584
// %14 = icmp eq i32 %max, 2584
// %.796 = select i1 %13, i1 true, i1 %14
// %15 = add i32 %local_cell.15, 2584
// %local_cell.18 = select i1 %.796, i32 %15, i32 %local_cell.15
// %16 = icmp sgt i32 %max, 10946
// %17 = icmp eq i32 %max, 10946
// %.797 = select i1 %16, i1 true, i1 %17
// %18 = add i32 %local_cell.18, 10946
// %local_cell.21 = select i1 %.797, i32 %18, i32 %local_cell.18
// %19 = icmp sgt i32 %max, 46368
// %20 = icmp eq i32 %max, 46368
// %.798 = select i1 %19, i1 true, i1 %20
// %21 = add i32 %local_cell.21, 46368
// %local_cell.24 = select i1 %.798, i32 %21, i32 %local_cell.21
// %22 = icmp sgt i32 %max, 196418
// %23 = icmp eq i32 %max, 196418
// %.799 = select i1 %22, i1 true, i1 %23
// %24 = add i32 %local_cell.24, 196418
// %local_cell.27 = select i1 %.799, i32 %24, i32 %local_cell.24
// %25 = icmp sgt i32 %max, 832040
// %26 = icmp eq i32 %max, 832040
// %.800 = select i1 %25, i1 true, i1 %26
// %27 = add i32 %local_cell.27, 832040
// %local_cell.30 = select i1 %.800, i32 %27, i32 %local_cell.27
// %28 = icmp sgt i32 %max, 3524578
// %29 = icmp eq i32 %max, 3524578
// %.801 = select i1 %28, i1 true, i1 %29
// %30 = add i32 %local_cell.30, 3524578
// %local_cell.33 = select i1 %.801, i32 %30, i32 %local_cell.30
// %31 = icmp sgt i32 %max, 14930352
// %32 = icmp eq i32 %max, 14930352
// %.802 = select i1 %31, i1 true, i1 %32
// %33 = add i32 %local_cell.33, 14930352
// %local_cell.36 = select i1 %.802, i32 %33, i32 %local_cell.33
// %34 = icmp sgt i32 %max, 63245986
// %35 = icmp eq i32 %max, 63245986
// %.803 = select i1 %34, i1 true, i1 %35
// %36 = add i32 %local_cell.36, 63245986
// %local_cell.39 = select i1 %.803, i32 %36, i32 %local_cell.36
// %37 = icmp sgt i32 %max, 267914296
// %38 = icmp eq i32 %max, 267914296
// %.804 = select i1 %37, i1 true, i1 %38
// %39 = add i32 %local_cell.39, 267914296
// %local_cell.42 = select i1 %.804, i32 %39, i32 %local_cell.39
// %40 = icmp sgt i32 %max, 1134903170
// %41 = icmp eq i32 %max, 1134903170
// %.805 = select i1 %40, i1 true, i1 %41
// %42 = add i32 %local_cell.42, 1134903170
// %local_cell.45 = select i1 %.805, i32 %42, i32 %local_cell.42
// ret i32 %local_cell.45
//
// false38: ; preds = %entry
// %43 = icmp eq i32 %max, 2
// %phitmp = select i1 %43, i32 2, i32 0
// br label %merge37
// }
Last modified 27 November 2024