Pure - gregorymorrison/euler1 GitHub Wiki
The Pure language, introduced in 2008, is a Functional language aimed mostly at academic mathematical and scientific uses. It's the successor to an earlier effort, Q, by the same author, Albert Gräf. Given its math roots, it has the expected equation-like syntax of a language like ML or Haskell. Here is an example of Euler1 in Pure:
// Euler1 in Pure
using system;
mySum [] = 0;
mySum (x:xs) = x + mySum xs;
euler1 n = mySum [x | x = 0..n; x mod 3 == 0 || x mod 5 == 0];
printf "%d\n" (euler1 999);
Pure has full support for functional operations. Here's an example using the canonical functions map, filter, and fold. Map’s only purpose here obviously is for illustration, since it returns itself. It also demonstrates use of lambda - an anonymous inline function using the \ operator, and function composition, where we chain together our three functions with the $ operator:
// Euler1 in Pure
using system;
myMap xs = map id xs;
myFilter xs = filter (\ x -> x mod 3 == 0 || x mod 5 == 0) xs;
myFold xs = foldl (+) 0 xs;
euler1 n = myFold $ myFilter $ myMap (1..n);
printf "%d\n" (euler1 999);
Notice that we are not maintaining any state to solve our problem. No loops, no variables, no mutable state - only function application. We simply call map, filter, and fold, and get the solution. This is an important part of the solution of the concurrency problem – how do you keep threads from stepping on each other’s states? By eliminating mutable state!
Next is a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler is deterministic – it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation – there are instead only functions which return values. The other main point is that this recursion uses tail call optimization – it’s written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.
// Euler1 in Pure
using system;
euler1 n = euler n 0 with
euler 0 acc = acc;
euler n acc = euler (n-1) (acc+n) if (n mod 3 == 0 || n mod 5 == 0);
= euler (n-1) acc;
end;
printf "%d\n" (euler1 999);
Here, our function euler takes two parameters, but we wrap it in an outer function using the with keyword so that we can expose a simpler signature euler1 having only one parameter. Unlike imperative languages, which require each function to have a unique signature, Pure allows multiple instances having the same signature. The runtime uses pattern matching and guards to resolve which instance to call. When a function is called, the runtime checks all functions with a given name, and starting at the top of the code and working down, it finds the first function that matches and executes that. Obviously then, you'll need to order your functions from most restrictive to least.
With pattern matching, not only does the runtime match parameter types, but it matches parameter values. If the first parameter has value 0, it calls the first function, else it calls the second. Obviously, the version with 0 needs to be listed first; if the version with n was listed first, the runtime would always choose it:
euler 0 acc = acc;
euler n acc = euler (n-1) (acc+n) if (n mod 3 == 0 || n mod 5 == 0);
Guards are additional checks against parameters. Here a guard is added to assert that n be divisible by 3 and 5. Again, obviously, this version must be listed first:
euler n acc = euler (n-1) (acc+n) if (n mod 3 == 0 || n mod 5 == 0);
= euler (n-1) acc;
Pure has an extensible type system. Here we create a new type - an int that is divisible by 3 and 5. Types can be used as guards; let's use it to replace the if condition from the last version:
// Euler1 in Pure
using system;
type mod_3_5 n::int = n mod 3 == 0 || n mod 5 == 0;
mod_3_5 n = typep mod_3_5 n;
euler1 n = euler 0 n with
euler acc 0 = acc;
euler acc n::mod_3_5 = euler (acc+n) (n-1);
euler acc n = euler acc (n-1);
end;
printf "%d\n" (euler1 999);
Pure's native data structure is the linked list. Here's an example where we work with lists. Let's modify the internal euler above to take two arguments - a list of functions and a list of ints. Each recursive call to euler will peel off another function from the list and apply it to the ints. Here, the first version of euler matches an empty list of functions, and whose job is to simply return the last calculated value. The function list in the other version is symbolized as (f:fs), where f matches the first item in the list, and fs matches to the rest of the list:
// Euler1 in Pure
using system;
myMap xs = map id xs;
myFilter xs = filter (\x -> x mod 3 == 0 || x mod 5 == 0) xs;
myFold xs = foldl (+) 0 xs;
euler1 n = euler [myMap,myFilter,myFold] (1..n) with
euler [] x = x;
euler (f:fs) xs = euler fs (f xs);
end;
printf "%d\n" (euler1 999);
Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler returns euler calculated on the half of the list before the pivot element, euler calculated on the half of the list after the pivot element, and the pivot element or 0, all added together. It demonstrates some of Pure's string operations such as slicing:
// Euler1 in Pure
using system;
euler1 n = euler (1..n) with
mod_3_5 n = if (n mod 3 == 0 || n mod 5 == 0) then n else 0;
// the midpoint of the list
mid xs = int(#xs / 2);
// return a value for the midpoint element
val xs = mod_3_5 (xs ! mid xs);
// plus euler on the first half of the list
pre xs = xs !! (0..(mid xs)-1);
// plus euler on the last half of the list
post xs = xs !! ((mid xs)+1..#xs);
euler [] = 0;
euler xs = euler(pre xs) + (val xs) + euler(post xs);
end;
printf "%d\n" (euler1 999);
I'm a little concerned with this version's efficiency - you can see that for every call to euler xs, mid xs gets called three times - by pre, val, and post. I can't put it in a local variable since I only have a collection of functions. I'm not sure how the compiler or runtime will optimize this.
Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation.
// Euler1 in Pure
using system;
euler1 n = euler n with
mySum n size = int (n * (floor(size/n)^2 + floor(size/n)) / 2);
euler n = mySum 3 n + mySum 5 n - mySum 15 n;
end;
printf "%d\n" (euler1 999);
Being foremost a language for math, Pure has a symbolic macro system. It's actually not the textual substitution found in most languages such as C or Lisp. Pure's substitution is actually real algebraic manipulation of terms. In the following example, the interpreter sees that the term mySum x n is a phrase to be redefined before being executed instead of it being a function call. Ironically, we get the same result whether the keyword def is included here or not even though they're executed very differently:
// Euler1 in Pure
using system;
def mySum n size = int (n * (floor(size/n)^2 + floor(size/n)) / 2);
euler1 n = mySum 3 n + mySum 5 n - mySum 15 n;
printf "%d\n" (euler1 999);
Pure has more interesting math-oriented functionality, like full support for matrix operations. I wanted to show an example using matrix manipulation, but because our problem is so linear, any solution I came up with just seemed too contrived. The weirdest part of Pure is its support for undefined symbols. The runtime lets you define algebraic formulas with undefined symbols on the right-hand side. This isn't allowed in imperative languages, but Pure is perfectly happy dealing with the abstract. Here, we define function foo equal to the sum of some undefined symbols, and when we ask the runtime for foo's value, it returns an equation:
> foo = a + b + c;
> show foo
foo = a+b+c;
>
So be careful - if you try to pass the wrong type to a function, its pattern matching will see that no function signature exists with that type, the runtime will simply create a new symbol (symbolic) instance of that signature. The new symbol has no value, but the runtime doesn't care! Expect to pull out some of your hair wondering why your program doesn't produce expected results. Actually, like most new languages, Pure has a great REPL for debugging that you're going to want to make friends with.
Overall, I had a lot of fun with Pure and would recommend it for those looking to expand their horizons. To kick the tires on the language and run your program from the command-line, simply yum-install pure, then pass your file as an argument to the runtime:
$ pure euler1.pure
233168
$