Proposed DSL for math expressions
Background
In Scala, numbers are objects, and infix expressions like "1 + 2", are compiled to "1.+(2)". This has benefits and drawbacks. The core language is simplified greatly by removing math operators to number objects. On the other hand, an expression like "f + g", with expensive functions f and g, must first evaluate f to a number object, then pass the result of evaluating g to the + operator. This serial evaluation is enforced even if f and g are independent and could be evaluated concurrently with no change in the result. Furthermore, the concrete types f and g must be known to the compiler where + is used in the code, since there is no abstract super-type of numbers with the + operator.
As a partial fix to that concrete type requirement, Scala supplies trait Numeric. If all you need is +, -, or * operators, then importing Numeric.Implicits._ makes implicit conversions available when calling methods with Numeric parameters, like "def doubleIt[A: Numeric](x: A) = x + x".
An alternative to Scala's Numeric trait is Azavea's Numeric trait, found here: "https://github.com/azavea/numeric". Azavea's version has better performance due to more extensive use of specialization. Another alternative is my NumVal trait found here: "https://github.com/kabob/NumVal". NumVal acts implicitly like a super-type of all numeric types, and supplies all common math operations, including transcendentals. It also permits a simpler version of the above method: "def doubleIt(x:NumVal) = x + x". However NumVal suffers poor performance due to: implicit conversions, lack of specialization, and lack of parallelization.
Recently I looked into using functional operations on primitive collections, including Array, to speed up math operations on large collections (see https://groups.google.com/forum/#!topic/scala-debate/eTwCGNgPtYs). Unfortunately I rediscovered what others already knew, that functional methods on primitive arrays are much slower than imperative (while loop) code, due to auto boxing and unboxing required by the generic collection implementations.
Solution?
So, despite the promise of FP as a way to write fast parallel code that's safe and scalable for future many-core hardware, Scala's FP implementation has some opportunities for improvement. My intent is not to find fault, but to take a fresh look at the issues, and see if they can be solved in one fell swoop!
After a hint by Rex Kerr on avoiding un/boxing by using a "scratch space", I was reminded of Java NIO and primitive type buffers. This is not exactly the same idea, but inspired by Rex (there's been a lot of interest in this idea of late!). During expression evaluation, intermediate values of any type can be stored in a spot reserved for that part of the calculation. Using primitive (long) buffers allows each sub-expression to evaluate to a different type on each re-evaluation, if needed. After some feasibility tests, I'm convinced that fast parallel evaluation of mixed-type math expressions is possible, without boxing and without the bloat and compile-time overhead of serialization. But for now I'd like to focus less on implementation and more on requirements.
Description
These are capabilities I would like to see when writing math expressions in Scala:
1. Math expressions can include common numeric operations, e.g.: conversions, comparisons, arithmetic, and transcendental functions.
2. Each operation supports all 10 "built-in" number types (numeric type abstraction). This includes 6 primitives and 2 Bigs.
3. Preserve precision on mixed (binary) operations.
4. In an expression, anywhere a single value is valid, a numeric Array is also valid (cardinality abstraction).
5. Exploit parallelism where possible (assume operations have no side effects).
6. Accommodate user-supplied operations.
7. Debugging aides, TBD (or just rely on logging intermediate results?)
If all this looks like a tall order, NumVal already implements 1-3, and I have code that partially implements 4 and 5.
Questions
1. Is anyone else working on this? (I hate to reinvent the wheel!)
2. Which approach is better: DSL or compiler plugin?
3. If implemented as described, would you find it useful?
4. Any interest in sponsoring this project (for release as open source)?
5. In a first release would you require other numeric types, like Complex and Rational?
Thanks!
kabob
--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-debate+unsubscribe <at> googlegroups.com.
For more options, visit
https://groups.google.com/groups/opt_out.