Pike - gregorymorrison/euler1 GitHub Wiki
Introduced in 1994, Pike is a language in the C/C++ family which was originally designed for the development of MUDs. It's interpreted, both statically and dynamically typed with strong typing, has garbage collection, and support for multiple language paradigms including first-class functions and object-oriented programming.
Here's a standard iterative example of Euler1 in Pike, which looks very much like C:
#!/usr/bin/pike
// Euler1 in Pike
int euler1 (int size) {
int retval = 0;
for (int i = 1; i < size; i++) {
if (i % 3 == 0 || i % 5 == 0) {
retval += i;
}
}
return retval;
}
int main() {
int euler = euler1(1000);
write (euler + "\n");
return 0;
}
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.
#!/usr/bin/pike
// Euler1 in Pike
int euler (int n, int acc) {
if (n == 0) return acc;
if (n % 3 == 0 || n % 5 == 0) {
return euler (n-1, acc+n);
} else {
return euler (n-1, acc);
}
}
int euler1 (int size) {
return euler (size, 0);
}
int main() {
write (euler1(999) + "\n");
return 0;
}
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. Pike doesn't seem to have a range generator function, so we've written our own. Also note here array slicing, which is welcome but verbose; Pike doesn't allow negative indices, unlike say Python.
#!/usr/bin/pike
// Euler1 in Pike
array(int) myrange(int size) {
array(int) ints = allocate(size);
for (int i=0; i<size; i++) {
ints[i] = i+1;
}
return ints;
}
int euler(array(int) ints) {
if (sizeof(ints) == 0) return 0;
int pivot = sizeof(ints) / 2;
int pivotval = ints[pivot];
if (pivotval % 3 > 0 && pivotval % 5 > 0)
pivotval = 0;
int pre = 0;
if (0 < pivot)
pre = euler( ints[0..pivot-1] );
int post = 0;
if (pivot+1 < sizeof(ints))
post = euler( ints[pivot+1..sizeof(ints)-1] );
return pre + pivotval + post;
}
int euler1 (int size) {
return euler( myrange(size) );
}
int main () {
write (euler1(999) + "\n");
return 0;
}
Does Pike support Functional programming? Well, it's built-in support is fairly weak; this is after all a language from the C family. It does support first-class functions and immutable objects using the constant keyword. There are no built-in map/filter/reduce, though we can try to write our own. A real Functional style requires immutability, which we can accomplish through the use of recursion. Notice that there is not a single assignment now, which guarantees that any multithreading will not step on each others' toes. And as you can see at the bottom with the calls made to map/filter/reduce, lambdas are defined as a code block surrounded by curly braces. Now, this might look like a lot of boilerplate, but the actual problem solution is now only a single elegant line (the italicized, bold line):
#!/usr/bin/pike
// Euler1 in Pike
array(int) _myrange(int size, array(int) ints) {
if (size > 0) {
return _myrange(size-1, ({size})+ints);
} else {
return ints;
}
}
array(int) myrange(int size) {
return _myrange(size, ({}));
}
array(mixed) map (function f, array(mixed) objs) {
if (sizeof(objs) == 1) {
return ({ f(objs[0]) });
} else {
return ({ f(objs[0]) }) + objs[1..sizeof(objs)];
}
}
array(mixed) filter (function f, array(mixed) objs) {
if (f(objs[0])) {
if (sizeof(objs) == 1) {
return ({ objs[0] });
} else {
return ({ objs[0] }) + filter(f, objs[1..sizeof(objs)]);
}
} else if (sizeof(objs) == 1) {
return ({});
} else {
return filter(f, objs[1..sizeof(objs)]);
}
}
mixed reduce(function f, mixed acc, array(mixed) objs) {
if (sizeof(objs) == 0) {
return acc;
} else if (sizeof(objs) == 1) {
return reduce(f, f(acc, objs[0]), ({}));
} else {
return reduce(f, f(acc, objs[0]), objs[1..sizeof(objs)-1]);
}
}
// now let's do our actual work //
int euler1(int size) {
return reduce(lambda(int x, int y) {return x+y;}, 0,
filter(lambda(int x) {return x%3==0 || x%5==0;},
map(lambda(int x) {return x;},
myrange(size))));
}
int main() {
write( euler1(999) + "\n");
}
Another interesting characteristic of Pike is its use of types. They are mandatory, but you can specify a parameter to be a range of types. Above, we've declared map/filter/reduce to take an array of type mixed, Pike's base generic type, which guarantees that our map/filter/reduce are actually generic.
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.
#!/usr/bin/pike
// Euler1 in Pike
int mysum (int n, int size) {
return (pow((size/n),2) + (size/n)) * n / 2;
}
int euler1 (int size) {
return mysum(3,size) + mysum(5,size) - mysum(15,size);
}
int main () {
write (euler1(999) + "\n");
}
My experience with this language was okay. It's documentation is not excellent but adequate, though I found its C-style syntax and learning curve to be quite easy. I didn't find a useful debugger, though its error messages are very good. Pike can be installed on Debian with apt install pike. Add a shebang to your code and you can execute your Pike program directly from the command line:
$ euler1.pike
233168
$