?

Log in

No account? Create an account
Jan. 21st, 2014 @ 07:36 pm Numerical Evaluation
About this Entry
Spiketail Hatchling
To the tune of: http://celticradio.net/
In the past, I've written about making a mathematical calculator in Java using a JavaScript engine. Deep down, I've always wanted to write my own. I thought it would be all mathy, but, in truth, it's a whole bunch of teaching a computer algebra. As such, I have my own evaluator in Java! It's the heart of "Parametron" (links: here or here). Trick is to separate, evaluate recursively in order.

  public static double evaluate(String input) throws IllegalArgumentException {
                // INFLATE THE CALL-STACK, CAPTAIN!
                int i, j;
                //Log.i("***MARKDEBUG***", "Evaluating " + input  );


                // If it's a number, just return that number!
                // It's smart enough to handle negatives.
                try {
                        return Double.parseDouble(input);
                } catch ( Exception e ) { }


                // Named function!
                for ( i = 0; i < namedFunctions.length; i++ ) {
                        if ( input.indexOf(namedFunctions[i] + "(") >= 0 ) {
                                return doNamedFunction(input, namedFunctions[i]);
                        }
                }
               // Find any other parentheses...
                i = input.indexOf("(");
                if ( i >= 0 ) {
                        j = findMatchingParen(input, i);
                        if ( j < 0 ) {
                                throw new IllegalArgumentException(input + " ...open '(' with no ')'.");
                        }
                        return evaluate(
                                        input.substring(0,i) +
                                        evaluate ( input.substring(i+1, j) ) +
                                        input.substring(j + 1, input.length())
                                        );
                }

                // FIND ADDITION!
                i = input.indexOf("+");
                if ( i > 0 )
                        return  evaluate(input.substring(0,i)) +
                                        evaluate( input.substring(i+1, input.length()) ); 

                // Find SUBTRACTION!
                for ( i = 0; i < input.length(); i++ ) {
                        if ( input.charAt(i) == '-' && i >= 1 && Character.isDigit( input.charAt(i - 1) ) )
                                return  evaluate(input.substring(0,i)) -
                                                evaluate( input.substring(i+1, input.length()) );
                        else if ( input.charAt(i) == '-' && i < input.length() - 1 &&
                                !Character.isDigit( input.charAt(i + 1) ) ) //UNARY MINUS (ACK! A HACK!)
                                return evaluate(input.substring(0,i) + "-1*" + input.substring(i+1, input.length()) );
                }

                // Find DIVISION!
                i = input.indexOf("/");
                if ( i > 0 )
                        return  evaluate(input.substring(0,i)) /
                                evaluate( input.substring(i+1, input.length()) );

                // Find MULTIPLICATION!
                i = input.indexOf("*");
                if ( i > 0 )
               return  evaluate(input.substring(0,i)) *
                                evaluate( input.substring(i+1, input.length()) );

                // Find EXPONENTS! (Evaluated last)
                i = input.indexOf("^");
                if ( i > 0 )
                        return Math.pow(
                                evaluate(input.substring(0,i)),
                                evaluate( input.substring(i+1, input.length() )) );

                return 0;


I think it's pretty self-documenting in the Java kind of way. There are a coupla helper functions (findMatchingParen, doNamedFunction) which do exactly what you'd think. findMatchingParen takes a string and an index of a parenthesis. It iterates down the string incrementing some counter c when it encounters another opening parenthesis and decrements c on finding a closing one. When the counter is 0 (or wherever-it-started-minus-one), then that's the index that evaulate is looking for.

doNamedFunction does something only slightly more complicated than replacing a string like "cos" with a call to Math.cos(...).

Let me take a moment to discuss LISP. Seems a little out of the blue, but I've been doing pretty healthy amounts of fudging with Emacs Lisp as of late. It's got two things that make things easier: firstly, lambda expressions, and, secondly, a means to execute strings as part of a program. I understand that JavaScript borrowed both of these features... but let's look at how they'd apply to this numerical evaluator.

First and foremost, a user could type "cos(3.1415)" to get "-0.99996". In Java I had to parse out the string literal "cos" and call Double.parseDouble on the "3.1415" part. Then, conditionally, based on the function name, make a call to a Java function. In Lisp, I'd be able to transform "cos(3.1415)" to "(cos 3.1415)" then evaluate it with (eval (read-from-string "(cos 3.1415)" )) in Emacs Lisp it requires a call to car before read-from-string, but once again, it's a one-liner instead of an entire song-and-dance routine.

Speaking of which... wanna see how difficult it is to program a REPL in Common Lisp? Here: (do () (nil) (eval (read-from-string (read-line)))) In Emacs Lisp, the looping part is even nicer-looking and the program is generally more friendly: (while t (eval (car (read-from-string (read-from-minibuffer "> ")))))

Let's go back and talk about the first bit-- lambda expressions (λ!). It lets you pass functions around as parameters to other functions. In Java (or any organized, object-oriented language, but mainly java), each class is defined in its own file on the filesystem like Foo.java. If you have a bunch of public classes that are used everywhere, they need their own file. If you've got an interface, its methods have to be implemented in each file. This works.

But what if you've got a lot of implementors? Well, here's where OO-programming gets weak. I once wrote a little Nethack-ish game for homework in a programming course. It was a pain in the arse that each monster (inherits from Monster) had to have its own file when most of the things inside were basically the same. Integer for health, integers for possible damages and attacks, a couple of strings, etc. This could be realized in JSON much easier, but that requires even more Java overhead and it poses scope-problems... anyway, in Lisp, each monster type could be a line item in a list. Each instance could carry a copy of that list around, and special attacks (or other code hooks) could be mere elements of that list that defines the monster.

Anyway, download Parametron.
--Mark
From:(Anonymous)
Date:March 7th, 2014 05:54 pm (UTC)
(Permanent Link)
Pretty nice post. I just stumbled upon your blog and wanted to
say that I've truly enjoyed browsing your blog posts.
After all I'll be subscribing to your feed and I hope you write again soon!