Calculator App

October 16, 2004 11:43 AM

I'm working on something like a glorified graphing calculator application, based on a small functional programming language. Each input program describes a function of some number of parameters, and the app's job is to plot the function's output across various input ranges. Is there an existing language with an open-source parser I can reuse for this job instead of inventing and implementing a new language from scratch?

I've never done any programming with functional languages before, and while web searches have turned up lists of dozens of them, I have no idea how they work or which ones might be suitable for a small embedded application like this.

The critical requirement is concurrency: the whole point of this project is to compile the program using SIMD instructions so I can run four passes at once. I'm sure threads and dual processor machines will get involved too.

I don't need integer math, or any data types other than single-precision floats. The language needs to include, or I need to be able to supply, a library of intrinsic math functions (sine, tangent, square root, etc). The finished app needs to run on Unix, Windows, and Mac OS.

I call this thing a compiler, but there's no need to write out an executable; it just needs to load the program, run it some thousands of times using different parameter sets, save each result value in an image buffer, and write the output to disk as a PNG or JPEG file.

posted by Mars Saxman to computers & internet (12 answers total)

Any reason not to use an existing graphing programming language / toolset? I'm thinking Matlab or gnuplot as two off the top of my head, there are dozens. I'm a huge fan of matlab, you can do most anything with it. it has a built in, fairly simple programming language (which is vector based, and very neat), a C programming api, you can create executables, do all kinds of weird stuff. There are jillions of plugins for various stuff. I wrote a rather extensive neural network library some years ago.

gnuplot is very simplistic in terms of it's abilities but is OK for 2-d plots (never tried a 3-d, don't know if it really can even do them).
posted by RustyBrooks at 12:38 PM on October 16, 2004

There are a number of math input languages out there: Mathematica, s-language (Splus or R), Maple are some of the most common. Any of these would work. Gnuplot would have to be driven by a scripting language, bash or something, to do what you need.

R can do exactly what you're looking for, though output would most easily be encapsulated postscript. You'll need to write a small R script, though from the sounds of things, that won't be difficult. R/s-lang is procedural rather than functional though. It's cross-platform, free and open-source so you can do your custom compilations.
posted by bonehead at 1:25 PM on October 16, 2004

Well, it has to be some kind of open-source library I can integrate into or at least distribute with my GPL app. Matlab does look pretty cool but it isn't free. gnuplot looks interesting but I can't see any way to configure it to produce the specific output I need.

Also, performance really is critical. While the initial version will simply render its output to image files, the eventual goal is to run the process in realtime and display the output as video. This will require about 2.5 million sample computations per second, where the expressions involved have roughly 200-300 terms. This ought to be achievable on standard PC hardware but there is not a lot of room for slop; it's hard for me to imagine any way to pull this off without compiling down to native machine code. But I'm even less familiar with graphics programming languages than with functional ones, so who knows - maybe someone has already built a system like this, and I can save a lot of work...
posted by Mars Saxman at 1:45 PM on October 16, 2004

what language are you using for implementation?

if i understand you correctly, the parser doesn't have to be particularly efficient - the expensive bit is going to be all the plotting, not the initial parsing, right? and by "parser" i'm assuming you mean that you want to go from a string to an abstract synax tree? if so, then it's "easy" to write a recursive descent parser, for some value of "easy" :o) seriously - it's pretty common. i've written a bunch of them (was working on one last night). the approach is described in cousineau + mauny (can't remember the title, but it's in english and something like "functional programming"). they use an early version of ocaml.

of course, "easy" is relative. i wrote a parser for very simple arithmetic in a couple of hours in python (not really "functional enough", but you can make it work), but that's after a fair amount of practice. on the other hand, doing it the first time probably took me weeks. so it's not trivial, but you might be interested anyway because it's a really cool thing to learn.

alternatively, if you've used similar tools with imperative languages, then many functional languages (ml and, i believe, haskell, for example) have equivalents of lex and yacc.

alternatively, just use lisp or scheme and it's done for you, as long as you keep the same syntax style.

getting back to what you asked for, you seem to want an already existing parser you can extend? that will depend on the language you're already using, which is why i asked.

or are you saying "what functional language should i use for this project, if part of it will involve parsing this little language?". in that case, scheme is the obvious choice, as long as you don't mind the parentheses.

you might be best asking the good people at lambda or comp.lang.functional. both are good sources of help.
posted by andrew cooke at 3:15 PM on October 16, 2004 [1 favorite]

incidentally, prolog is also a good language to write parsers in, becuase the recursive descent is really just a search to find the program consistent with the input code, within the tree of all possible programs, and prolog's backtracking search makes this trivial.

that's the theory - i haven't done it, but i'm slowly starting to see why it makes sense.
posted by andrew cooke at 3:19 PM on October 16, 2004 [1 favorite]

this thread at lambda may be relevant - i'm still not clear what you want, but i was trying to find a simple language written in a functional language. of the answers i received, Q seems like it might fit what you want.
posted by andrew cooke at 3:31 PM on October 16, 2004

sorry to post again, but it was this page that i was remembering from the Q site that made me think it would be what you wanted.
posted by andrew cooke at 3:34 PM on October 16, 2004

andrew: thanks for the pointer to Q. Looks a lot like what I had in mind.

Ideally, I'd like a library that translates a string of source code into some kind of pcode; then I can write a backend that translates the pcode to machine language, which is the part of this project that most interests me. I've written parsers before, but designing a small functional language, writing a parser for it, designing an appropriate pcode, and writing a treewalker that generates said pcode adds up to a fair amount of work that I would rather avoid if I can help it. I'm basically just being lazy, or "trying to avoid reinventing the wheel" if you want to phrase it more positively.

You're right, parser speed really doesn't matter. Implementation language is probably C++, because it's easy and convenient and I don't actually know any functional languages, but I could use Java instead.

I've never looked at prolog, but your description makes it sound really interesting.
posted by Mars Saxman at 12:12 AM on October 17, 2004

If you're implementation language is C++, then maybe you could use the Boost Spirit parser:
http://spirit.sourceforge.net/

"Spirit is an object oriented recursive descent parser generator framework implemented using template meta-programming techniques. "
posted by Meridian at 4:29 AM on October 17, 2004

ah, ok - i thought you were implementing in a functional language (for some reason which i don't understand it seems to be a lot easier to write a parser in a functional language than in an imperative one).

don't know if any od these help (from googling, so i guess you've already found them); they're limited to expressions, i think, but for a functional language that's almost all you need anyway (you'd need to add the syntax to assign the expression a name and variable list):
UCalc Fast Math Parser allows programs to evaluate math expressions that are defined at run time.
Function parser for C++
mathematical expression parsers.
posted by andrew cooke at 5:31 AM on October 17, 2004

(oh, stating the obvious, but i'd forgotten - you also need to check that they will parse new function names, so pick one that doesn't have a fixed list of functions that it recognises. assuming you want to parse an extensible language rather than just expressions.)
posted by andrew cooke at 5:41 AM on October 17, 2004

Wow Meridian, Spirit looks really clever - that ought to be a great tool for config files, little languages, expression evaluators, etc.
posted by Mars Saxman at 10:43 PM on October 17, 2004