Binomial coefficient in Prolog

I am using SWI-Prolog and we need to include the header files from SWI-Prolog so we can build a dynamic library that Prolog can call. We also include GMP so we can get access to the mpz_bin_ui function that calculates the binomial coefficient.

1: #include <SWI-Prolog.h>
2: #include <gmp.h>

Defining predicates in C is pretty similar to defining them in Prolog. In this case I define a predicate that takes three terms as arguments: The size of the set to choose from, the number of distinct elements to draw from the set, and the resulting binomial coefficient.

In contrast to defining predicates in Prolog, it is also neccessary to state what the types of the function and arguments are. The function also has a return type. The return from the function is there to signal to Prolog if the predicate succeeded in unifying the terms or not.

 3: static foreign_t
 4: pl_choose(term_t size, term_t take, term_t result)
 5: {
 6:   mpz_t rop;
 7:   mpz_t n;
 8:   unsigned long int k;
 9:   int rc;
10: 
11:   mpz_init(rop);
12:   mpz_init(n);
13: 
14:   if ( PL_get_mpz(take, rop) && PL_get_mpz(size, n) )
15:     {
16:       k = mpz_get_ui(rop);
17:       mpz_bin_ui(rop, n, k);
18:       rc = PL_unify_mpz(result, rop);
19:     }
20:   else
21:     {
22:       rc = FALSE;
23:     }
24: 
25:   mpz_clear(rop);
26:   mpz_clear(n);
27:   return rc;
28: }

At line 3 the return type of the predicate is defined. We see that it is a static function and that it will return the type foreign_t. All predicates implemented in C needs to have the return type as foreign_t.

We can see on line 4 that the predicate has 3 arguments. These arguments function mostly in the same way that they do in Prolog. In this predicate it is only the last argument that is allowed to be a (Prolog) variable. The other two are needed to calculate the binomial coefficient.

From line 6 the variables that we need are defined. mpz_t is the type of numbers in the GMP library.

The mpz_t variables needs to be initialized in memory and we do that on line 11.

In the if statement on line 14 we try to convert the values in the Prolog terms into mpz values. If any of the input variables are not a number, the PL_get_mpz function will return a false value and the if statement will fail.

Since the binomial coefficient function takes a unsigned int as the 3rd argument we need to convert the mpz value from the input to a unsigned int. That is done on line 16.

mpz_bin_ui is the function that calculates the binomial coefficient. It takes two mpz_t values and an unsigned int. You might notice that we are using the same variable that we used for converting one of the term_t to an mpz value. This is perfectly fine as we converted that number and stored it in the k variable. We could clear the variable first, but it is not needed as mpz_bin_ui will just overwrite the value stored in the variable.

mpz_bin_ui stores the result of the calculation in the first argument. The second argument is the size of the set and the third is the number of elements to draw from th set.

After calculating the binomial coefficient we unify the value stored in rop with the result variable. We do that with PL_unify_mpz on line 18. rc, which is the return value for the predicate, is set to the result of unifying the two variables; either true or false.

If the function, for some reason, didn't recieve the correct input it will instead of trying to calculate the binomial coefficient just set the return value of the predicate to false (line 22).

Before we exit the predicate we need to clear the mpz variables as otherwise we will leak memory (line 25).

In the end we return rc so that we can tell Prolog if we succeeded in calculating the binomial coefficient or not.

29: install_t
30: install_choose()
31: {
32:   PL_register_foreign("choose", 3, pl_choose, 0);
33: }

Prolog also needs to be told which functions in the file are predicates (line 30). We do this by creating a function that returns install_t and has the name install_*, where the * is the name of the file it is in. In our case it is "choose". We also need to call PL_register_foreign on every function that we want to export to Prolog. PL_register_foreign takes 4 arguments. The name of the function as it will appear in Prolog, the number of arguments, the C-function to call and, some flags. You can learn more about the flags in the SWI-Prolog documentation.

Building the C-code has been made pretty easy¹. We use the swipl-ld command that is packaged with SWI-Prolog. On my OS X box I need to add gmp as a library that we depend on. The -shared argument ensures that we are building a dynamic library. We need it to be a dynamic library if Prolog is going to be able to call it. -o sets what to call the compiled library. Depending on if you are on OS X, Linux or, Windows the extension will be .dylib, .so or .dll.

swipl-ld -lgmp -shared -o choose choose.c

Calling the newly built library from Prolog is quite easy. All you have to do is call :- use_foreign_library with the the name of the library you want to load as an argument. I my case I also defined a module to export the foreign code from.

:- module(binomial, [choose/3]).
:- use_foreign_library(choose).

You can see uninterrupted source at:

• choose.c
• build.sh
• binomial.pl