Binding Flint Library for multivariate polynomials

Learning
1

Hello,

I’ve been looking for a library to compute the gcd of multivariate polynomials quickly in ocaml. It seems like the best option at the moment is to create bindings to the Flint library http://flintlib.org/doc/index.html

The main issue is that most functions in the library are use in the following pattern

out;
init out;
f out in1 in2;

where out is pointer to the output.

In order to use such a function I need to make a pointer to a complicated struct to pass into this function and in order to use the allocate function of ctypes I need to know the size of this struct. The initialization functions also appear to dereference the pointer that is passed in so I can’t just cast a null pointer.

My understanding was that I can use Cstubs_struct to parse all the .h files and automatically determine how big the structs should be. However I am getting errors that the structs are forward declared.

For example the fmpz_poly_struct is defined in the .h file as:

typedef struct
{
    fmpz * coeffs;
    slong alloc;
    slong length;
} fmpz_poly_struct;

The types fmpz and slong are defined in other .h files that are included earlier. However when I try to add the following to type_description.ml (following the ctypes dune tutorial file structure)

open Ctypes

module Types(F: TYPE) =
  struct
    open F
    type s
    let s : s Ctypes.structure F.typ = F.structure "fmpz_poly_struct"
    let () = F.seal s
end

I get the following errors:
error: invalid application of ‘sizeof’ to an incomplete type ‘struct fmpz_poly_struct’
note: forward declaration of ‘struct fmpz_poly_struct’
sizeof(struct fmpz_poly_struct)

I suspect the issue is that the type fmpz has a different definition based on #ifdef in the other .h files, but I don’t know how to have Cstubs process this.

Is there a better way to handle creating these pointers/ figure out the size of these structs?

2

Simply asking the question is enough to find an answer

The issue is that the structs are of the form typedef struct {stuff} name not struct name {stuff}. As such I needed to use the Ctypes typedef command declare them. For example:

module Types(F: TYPE) =
  struct
   type s
   let s : s Ctypes.structure F.typ = typedef (F.structure "fmpz_poly_struct") "fmpz_poly_struct"
   let () = F.seal s
  end

In this case the struct doesn’t have an initial identifier, but using (F.structure “”) in multiple structs gave errors. Is it ok to have any name if the struct itself doesn’t have a name?

1 Like
3

I don’t know anything about Flint. By some chance, do you have an example program you could point at, which demonstrates Flint in-use, and that, if ported to OCaml, could be a good example?
Figured it out. Comes with examples.

4

I’ve been thinking about your problem, and maybe this is completely not the way you’d like to approach it, but … well, heck, I got bored, and started writing some code …, so, here’s a repo: GitHub - chetmurthy/ocaml-flint: OCaml wrappers for Flint library

The idea is:

  1. you rightly observe that the memory-ownership and initialization and such in C is a pain, and any C-based wrappering is going to be … painful.

  2. But Flint has a C++ wrapper, that tries to hide all of that.

  3. And in the past, I’ve found that well-behaved C++ wrappers using templates can often be converted into OCaml C-based libraries with mostly-automated conversion based on using those templates, and template metaprogramming.

  4. So I started doing that with your little problem. I’ve converted the “partition” example, and am going to proceed to a few of the other ones. I thought I’d just toss this out there, and if you’re at all interested, I can clean it up.

Also, if you have specfic API calls that you could use right away, lifted into OCaml, I could lift those first, rather than just working thru the examples willy-nilly.

The key idea is that with the template metaprogramming doing most of the heavy-lifting, data-structure-conversion-wise, it might not be very painful to wrapper Flint for OCaml. The maintainer/author claims that the C++ layer of the API is pretty thin, so maybe even efficient. Though I have no idea (I only downloaded/built it today).

I did this work with Flint version 2.9.0.

P.S. re: “clean it up”, for instance, the directory-paths still refer to paths on my machine, so you’d have to change them (in the Makefile) to get it to build.

5

I’m mostly interested in the fmpz_mpoly code (in particular fmpz_mpoly_gcd, but I need all the creation/standard arithmetic operations as well). I’m trying to do a lot of computation involving rational functions in multiple variables. I found flint because it is the library that sage (a common computer algebra library in python uses), but I don’t want to abandon the other nice ocaml code I have.

I don’t really know enough about the c++ metaprogramming to know how much of a difference that would make, but I’m curious to see how it works out.

For your reference I’ve put the code I’ve started here: ocaml-flint. The module BigIntMpoly is the important one for my use case. It seems to work locally so far, but I haven’t figured out how to build it as package to reference in my other code and really try it out.