Functional programming and equation solvers

Question

Hi all,

Just as a personal experiment, in order to try to learn better about programming and formal language theory and the like, I'm trying to write a language that basically takes in a bunch of equations and solves for unknowns more or less automatically or heuristically. I'm trying to do this by writing an interpreter in C.

All that's not super-relevant, though... more importantly, I've discovered functional programming in the last few days (by which I mean I read Wikipedia's entry for it and a brief Haskell tutorial) and it seems to deal with very similar things to what I want to do.

I guess what I'm wondering is, are there any other languages I should look into, or any non-functional languages that have libraries or programs that try to do similar things, such that I might gain a better understanding of what I'm setting out to do?

Also, are there any good references out there for writing interpreters, etc.?

Thanks.

P.S. Oh, and I'm aware I could and should use Google. I am, on the side. More than anything I'm looking for a collective of "second opinions" for what's good, and what people have used before. Also, I'm trying to get to know the community a little better, since I'm new here. Thanks for your patience :-)

Answer 1

Disclaimer: I did not seriously explore this field, but hope this small write-up might be useful to you - and awaiting to see more answers from the others.

I think there are multiple questions in one:

1) Equation solvers.

if you mean "solving for unknowns" symbolically - it's a pretty big pile of work that you are about to get started with, IMHO :-) You're about to embark on creating a computer algebra system.

Term rewriting is a rather big topic on its own. If you are specifically interested in the manipulations at this level, C might be not the easiest to work with - you'd probably be more at ease with Lisp for that task.

Notably, not every set of equations is going to have a solution - and "just" figuring out the fact whether it does have a solution or not is a tough task on its own.

On the other hand, if you look up to solving the equations numerically, something like this might be interesting to look at.

2) Functional programming in general.

Haskell is a great language for that (although I am still a very beginner in it - I think it might be one of the most elegant ones). OCaml might be another path to explore. Then, of course, there is Scheme. A language with immediate practical implications could be XSLT if you are dealing with web programming.

And of course you can easily write functional style in Ruby and Python. It is very interesting to observe how learning the new languages changes your programming patterns in "main" language overall. So, language theory or not - the more languages you touch, the better.

3) Writing the interpreters, etc.

I suspect that given the flavour of the question, the most interesting practical application for what you would like to do would be not the interpreter, but the optimization code in the compiler. For that - Dragon book and MIT computer language engineering course would be useful in my opinion to start with. Then you could grab e.g. a copy of TCC and play with it. If you want to tinker with something less conventional, take a look at potion - a very interesting language experiment that has x86 machine code as its "bytecode" (hence the performance on x86 machines is pretty spectacular).

This question on SO actually references most of the of the links from (3) above, and quite a few more.

Answer 2

As Andrew suggested, the heart of what you describe is known as "computer algegra systems", and more generally "term-rewriting systems". Reading up on those two areas ought to get you oriented.

And, yes, I expect you'll find functional programming a well-suited paradigm. Perhaps logic programming as well.

My hunch is that your question about interpreters is jumping the gun and results from Greenspun's Tenth Rule, which is

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

where you might replace "Common Lisp" with "a functional programming language".

In other words, if you choose and embrace a consciously designed functional programming language (for your computer algebra system), you won't have to create one unconsciously (and badly).

My personal favorite among functional languages is Haskell. For newbies, Haskell has the advantage making you admit--via static typing--when you're still programming imperatively.