Home » forums » LtU Forum

Language support for generating functions?

We've got languages with support for iterators and lazy lists and other sequence oriented structures. Is there any language with built in support for generating functions? I don't have any immediate application in mind, I'm just curious as to what could be possible.

By Greg Buchholz at 2005-07-29 01:54 | LtU Forum | previous forum topic | next forum topic | other blogs | 5935 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

This is largely the realm of CAS

Functional languages allow you to build libraries that provide functionality that is pretty darn close to "built in." Higher-order functions, macros, parametric polymorphism, and type inference can all be huge wins for creating libraries that allow the expression of concepts at, or nearly at the "textbook" level.

Admittedly, the "syntax" that your library provides will be shaped by the language your library is in. It'll probably be slightly off of what you might consider "natural" for the subject at hand. But, to quote Alan Perlis, "Syntactic sugar causes cancer of the semicolon."

There has been quite a bit of research into extensible syntax, but it's never really taken off. Maybe it'll take off with Guy Steele's Fortress, which is attempting to replace Fortran. Hygenic macros are a pretty good substitute for extensible syntax, though, plus you get to compute things at compile time.

Speaking to generating functions specifically, I did do some stuff with finite polynomial generating functions in Haskell, which was sufficient for the problem at hand. Doing much more than that would involve a fair bit of grunt work implementing (parts of) a Computer Algebra System.

Docon looks pretty darn interesting. I've not gotten too deep into it, so I can't attest to issues of speed and correctness, but I expect it to be correct and moderately slow, for a CAS system. (Though beautiful...) I don't like the user's manual. :-( Currently, it doesn't offer much in the way of calculus.

Mathematica has a number of operations for generating functions, and I would imagine that Maple does too.

What applications would a reasonably general generating function library enable? I'm not sure... most of the applications I know use fairly specific generating functions, and usually have a very specific user base.

By Leon P Smith at Fri, 2005-07-29 05:37 | login or register to post comments

Previously on LtU...

This thread might be of interest (not the topic itself, but some of the discussion).

By Anton van Straaten at Fri, 2005-07-29 08:08 | login or register to post comments

Thanks, Anton

Thanks Anton. I wasn't aware of potential connections between generating functions and type theory, though I'm not buying it yet. There are still many issues that are fuzzy in my mind.

TAPL has generating functions in the index, but Pierce uses "generating functions" as a friendlier name for monotonic induction/coinduction operators. Which is something I'm a bit more comfortable with, admittedly.

The problem I have with X / (1 - X) representing non-null lists, at least as discussed in the thread, is that the algebraic properties of addition and multiplication are different than the properties of union and cartesian product / intersection. Although the addition of ring ideals is the join operator of that lattice... which, algebraically, is a lot closer to the union of sets than addition inside the ring.

Wouldn't exponential generating functions make more sense for lists? Exponential generating functions offer a convenient way of counting permutations of a multiset, a.k.a. lists.

By Leon P Smith at Fri, 2005-07-29 20:13 | login or register to post comments

FIDIL: Finite Difference Language

The FIDIL language, designed by Paul Hilfinger and his colleagues, is a kind of bridge between computer algebra systems and standard programming languages. It can do calculations with finite differences (using high level concepts of domains and maps), and then execute the resulting programs on multiprocessors. The finite difference calculations are related to generating function calculations. You can find more by Googling for FIDIL and Hilfinger.

By Peter Van Roy at Fri, 2005-07-29 10:00 | login or register to post comments

What support do you need?

By strange coinicdence I've been writing a small lazy formal power series library in Haskell. Many operations ranging from power series addition to hyperbolic cosine are simple one-liners (and both are fairly efficient too). The one thing I haven't figured out is a lazy version of Karatsuba multiplication so I have a naive convolution algorithm instead. This stuff was so easy to code up it was as if Haskell was purpose built for the task. Without laziness it would have taken considerably more work.

It was then an easy task to implement a mini combinatorial DSL to answer questions like "how many rooted trees of size n are there where a tree is defined to be the union of a root and a set of trees". I also found a bunch of other interesting uses.

By sigfpe at Fri, 2005-07-29 20:38 | login or register to post comments

Needs

I don't have any support "needs", I was just browsing through my discrete math book, came upon the generating functions section, which led me to _Generatingfunctionology_. Then I started having half-baked ideas like having versions of "map" which operated on (and returned) generating functions. That's when I thought I'd post something to LtU and see what else was out there.

By Greg Buchholz at Fri, 2005-07-29 20:57 | login or register to post comments

Reading most of generatingfunctionology...

...recently was one of the things that inspired me to have a go at formal power series code. I also lifted the algorithm for exp() from here and adapted it to all of the other standard transcendental functions.

Although I only considered power series, a friend of mine also just implemented Dirichlet series in Haskell too.

By sigfpe at Fri, 2005-07-29 21:08 | login or register to post comments