## Greg Buchholz's blog

### Anyone out there?

on March 22, 2013 - 9:01pm

Just testing whether posting still works. Kerneltrap was offline for a couple of years there, and I see that no one has posted anything for quite some time.

### Logical variables in Prolog

on June 22, 2009 - 8:55pm

I came across this code, which was supposed to demonstrate a Prolog program that couldn't be written in Mercury. I couldn't help but rewrite that as:

rank(Xs,Rs) :- pairs_keys_values(Decorated,Xs,Rs),
keysort(Decorated,Sorted),
numerate(Sorted,1).

numerate([],_).
numerate([_-N|Rest],N) :- N1 is N + 1, numerate(Rest,N1).


...This computes the rank order of a list of elements. For example rank([40,20,50,10],L). unifies L with [3,2,4,1], since 40 is the third largest element, etc.

### Partition a list numerically?

on June 9, 2009 - 8:13pm

Over on the Haskell Cafe mailing list, the topic of which of the following two definitions was better came up:

buildPartitions xs ns = zipWith take ns . init $scanl (flip drop) xs ns  ...or... takeList :: [Int] -> [a] -> [[a]] takeList [] _ = [] takeList _ [] = [] takeList (n : ns) xs = head : takeList ns tail where (head, tail) = splitAt n xs  ...with various parties declaring the first example as "too smart", and others claiming that the second example is newbie level code. Well I'm much too lazy to try to reason out what those snippets might do at a glance. But the type signature was a pretty big hint as to what the intent was. So I fired up ### Non-ugly average in Haskell on November 7, 2008 - 9:01pm data E a b = L (E a b) | R b deriving (Show) fold f acc [] = R acc fold f acc (x:xs) = let x' = f acc x in x' seq (L$ fold f x' xs)

lift2 f = \x y -> par_eval x y
where par_eval   (L x)   (L y) = par_eval x y
par_eval x@(R _)   (L y) = par_eval x y
par_eval   (L x) y@(R _) = par_eval x y
par_eval   (R x)   (R y) = R $f x y lift1 f (L x) = lift1 f x lift1 f (R x) = R (f x) sum' xs = fold (+) 0 xs len' xs = fold (\x y->succ x) 0 xs avg xs = (sum' xs) / (len' xs) main = print$ avg [1..1e7]

instance Eq b => Eq (E a b) where
a == b = case (lift2 (==) a b) of (R x) -> x

instance Num b => Num (E a b) where
(+) = lift2 (+)
(*) = lift2 (*)
fromInteger = R . fromInteger
abs = lift1 abs
signum = lift1 signum

instance Fractional b => Fractional (E a b) where
(/) = lift2 (/)
fromRational = R . fromRational



### Entering unicode

on November 23, 2007 - 5:57pm

Here's the configuration file I use to help me enter some of the fun mathematical unicode characters with vim. The commands were borrowed from TeX...

imap jj <ESC>
imap \div ÷
imap \times ×
imap \sum ∑
imap \int ∫
imap \oint ∮
imap \angle ∠
imap \forall ∀
imap \exists ∃
imap \partial ∂
imap \prod ∏
imap \infty ∞
imap \pm ±
imap \sqrt √
imap \circ ∘
imap \Re ℛ
imap \Im ℑ

### Misc. ray tracers

on October 10, 2007 - 2:01pm

By popular demand, here's the more web accessible versions of a couple of simple ray tracers that I quickly cranked out in Perl and Haskell. Along with the respective source code.

It takes a POV-like scene file, and spits out a *.ppm file onto STDOUT.

### Cellular Automata

on March 8, 2007 - 3:15pm

After seeing a cellular automata simulator in F#, I thought I'd make a more general version with Perl/TK which was also shorter. Invoke with a numeric argument on the command line to see automata other than rule 30 (e.g. 90, 110).

### SWI-Prolog and Unicode.

on February 15, 2007 - 11:17am

% fun with SWI-Prolog and Unicode.  Try some queries like...
% Ans ≔ ∫x d x.
% Ans ≔ ∫ 2 + x^3 d x.

:- encoding(utf8).
:- op(699, xfy, ≔).
:- op(600, fx, ∫).
:- op(510, xfx, d).
:- op(200, xf, ²).

A+B ≔ ∫ Y+Z d X :- A ≔ ∫ Y d X, B ≔ ∫ Z d X.
C*A ≔ ∫ C*Y d X :- free(C,X), A ≔ ∫ Y d X.
C*X ≔ ∫ C d X   :- free(C,X).
X² / 2 ≔ ∫ X d X.
X^N1/N1 ≔ ∫ X^N d X :- free(N,X), N =\= -1, N1 is N + 1.
(log(A*X+B)/A) ≔ ∫ 1/(A * X + B) d X :- free(A,X),free(B,X).
(exp(A*X+B)/A) ≔ ∫ exp(A*X+B) d X    :- free(A,X), free(B,X).
∫ E d X ≔ ∫ E d X.

free(C,X) :- \+ bound(C,X).

bound(X,X).
bound(A+B,X) :- bound(A,X); bound(B,X).
bound(A-B,X) :- bound(A,X); bound(B,X).
bound(A*B,X) :- bound(A,X); bound(B,X).
bound(A/B,X) :- bound(A,X); bound(B,X).
bound(A^B,X) :- bound(A,X); bound(B,X).



### Breaking free

on January 4, 2007 - 8:27pm

If you really want to break free from the von Neumann bottleneck , grab yourself an FPGA starter kit and start playing with Verilog or VHDL. FPGAs are quite interesting now that features like hardware multipliers are becoming more widespread.

on December 18, 2006 - 9:26am

C++ is a complicated language, but it doesn't have to be that complicated. Here a simple maybe monad implemented in C++...

### Planet "Programming Language Dilettante"

on December 14, 2006 - 4:12pm

Planet "Programming Language Dilettante". That's one one blog aggregator I'd really like to read.

### The more things change the more they stay the same...

on December 13, 2006 - 10:25pm

After we correct for the algorithmic differences, is there really that much difference between...

fibo 0 = 1
fibo 1 = 1
fibo x = fibo (x-1) + fibo (x-2)

### Blub is the language you know.

on November 20, 2006 - 12:02pm

Pascal Costanza wrote:

But in the general case, dynamic typing and static typing are not compatible. In Common Lisp, there are a lot of cases where you can very conveniently change types at runtime. So a static check of types would be a great burden. Here is my standard example for this:

(defclass person ()
((name :initarg :name)))

(let ((p (make-instance 'person :name "Pascal")))


There is no chance to see up front whether this program will fail or not, since the user can redefine the class person when (eval (read)) is executed. At that time, the slot 'address could be added to the class person.

I don't see any reason why that's not amenable to static typing...

### Memoizing fixed point combinator in C++

on November 14, 2006 - 10:41am

Over on comp.lang.c++ they're discussing memoization of functions. Here's my version of a memoized fix point combinator...

#include<iostream>
#include<map>

std::map<int,int> memo_table;

struct Fix
{
int (*f)(int,Fix);

int operator()(int x, Fix g)
{
return (memo_table.find(x) != memo_table.end())
? memo_table[x]
: memo_table[x] = g.f(x,g);
};
};

int fib(int n, Fix f) { return n < 2 ? n : f(n-1,f) + f(n-2,f); }

int main(int argc, char *argv[])
{
Fix g = {fib};
std::cout << g(40,g) << std::endl;
return 0;
}



### Type system computation

on November 8, 2006 - 12:03pm

Over on comp.lang.lisp we have a comparison of between the type systems of lisp and ML. I don't know enough about ML to know whether it is or isn't up to the challenge, but here's a teaser of how you could go about it in Haskell. First off, we need a data type that knows about the range of possible values for its integral argument. And then we need to be able to exponentiate the range...