Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to build a calculator in Scala". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn how to build a calculator in Scala.

Domain-specific language

Maybe you can't (or don't have the time) to withstand the pressure from your project manager, so let me get this straight: a domain-specific language is nothing more than trying (again) to put the functionality of an application where it belongs-in the hands of the user.

By defining a new text language that users can understand and use directly, programmers get rid of the hassle of constantly dealing with UI requests and enhancements, and it also enables users to create their own scripts and other tools to create new behaviors for the applications they build. Although this example may be a bit risky (there may be a few complaining emails), I would say that the most successful example of DSL is the Microsoft ®Office Excel "language", which is used to express the various calculations and contents of spreadsheet cells. Some people even think that SQL itself is DSL, but this time it's a language designed to interact with relational databases (imagine what it would be like if programmers were to get data from Oracle through traditional API read () / write () calls).

The DSL built here is a simple calculator language for getting and evaluating mathematical expressions. In fact, the goal here is to create a small language that allows users to enter relatively simple algebraic expressions, and then the code evaluates it and produces results. To be as simple and clear as possible, the language will not support many of the features supported by full-featured calculators, but I don't and don't want to limit its use to teaching-the language must be extensible enough to enable readers to use it as the core of a more powerful language without revamping it. This means that the language must be easily extensible and be as encapsulated as possible without any hindrance to its use.

In other words, the (ultimate) goal is to allow clients to write code to do the following:

Listing 1. Calculator DSL: target

/ / This is Java using the Calculator String s = "(5 * 10) + 7"; double result = com.tedneward.calcdsl.Calculator.evaluate (s); System.out.println ("We got" + result); / / Should be 57

We won't finish all the discussions in one article, but we can learn part of it in this article and finish it all in the next article.

From an implementation and design point of view, you can start with building a string-based parser to build a parser that can "pick each character and calculate it dynamically", which is tempting, but it only applies to simpler languages. and its scalability is not very good. If the goal of a language is to achieve simple extensibility, let's take a moment to think about how to design the language before delving into the implementation.

According to the quintessence of the basic compilation theory, you can know that the basic operation of a language processor (including an interpreter and a compiler) consists of at least two stages:

A parser that takes the input text and converts it to Abstract Syntax Tree (AST).

The code generator (in the compiler's case) is used to get the AST and generate the required bytecode from it, or the evaluator (in the interpreter's case) is used to get the AST and evaluate what it finds in the AST.

If you realize that having an AST can optimize the result tree to some extent, the reason for the difference becomes even more obvious. For calculators, we may want to examine the expression carefully to find out where the entire segment of the expression can be truncated, such as the position in the multiplication expression where the Operand is "0" (it indicates that no matter what the other operands are, the result will be "0").

The * thing you need to do is define the AST for the calculator language. Fortunately, Scala has case classes: classes that provide rich data and use very thin wrappers, and they have some features that make them ideal for building AST.

More information about DSL

The topic of DSL is wide-ranging; its richness and extensiveness cannot be described in one paragraph of this article. Readers who want to learn more about DSL can check out Martin Fowler's "Books in Progress" listed at the end of this article; pay particular attention to the discussion between "internal" and "external" DSL. With its flexible syntax and powerful functions, Scala has become a powerful language for building internal and external DSL. For a more specific introduction, please refer to the preliminary article on DSL domain-specific languages previously released by 51CTO.

Case class

Before diving into the AST definition, let me give you a brief overview of what a case class is. The case class is a convenient mechanism that allows scala programmers to create a class using certain hypothetical default values. For example, when writing something like this:

Listing 2. Using the case class with person

Case class Person (first:String, last:String, age:Int) {}

The Scala compiler can not only generate the expected constructor as we expect of it-the Scala compiler can also generate equals (), toString (), and hashCode () implementations in the general sense. In fact, this case class is very common (that is, it has no other members), so the contents of the curly braces after the case class declaration are optional:

Listing 3. The shortest list of classes in the world

Case class Person (first:String, last:String, age:Int)

This can be easily verified by our old friend javap:

Listing 4. Sacred code generator, Batman!

C:\ Projects\ Exploration\ Scala > javap Person Compiled from "case.scala" public class Person extends java.lang.Object implements scala.ScalaObject,scala. Product,java.io.Serializable {public Person (java.lang.String, java.lang.String, int); public java.lang.Object productElement (int); public int productArity (); public java.lang.String productPrefix (); public boolean equals (java.lang.Object); public java.lang.String toString (); public int hashCode (); public int $tag (); public int age (); public java.lang.String last () Public java.lang.String first ();}

As you can see, a lot of things happen with the case class that traditional classes don't normally cause. This is because the case class is intended to be used in conjunction with Scala's pattern matching (which was briefly analyzed in "Collection types").

Using case classes is somewhat different from using traditional classes because they are usually not constructed from the traditional "new" syntax; in fact, they are usually created through a factory method with the same name as the class:

Listing 5. Do not use new syntax?

Object App {def main (args: Array [String]): Unit = {val ted = Person ("Ted", "Neward", 37)}}

Case classes themselves may not be more interesting than traditional classes, or how different they are, but there is an important difference when using them. The code generated by the case class prefers the bitwise equation to the reference equation, so the following code is an interesting surprise for Java programmers:

Listing 6. This is not the previous class.

Object App {def main (args: Array [String]): Unit = {val ted = Person ("Ted", "Neward", 37) val ted2 = Person ("Ted", "Neward", 37) val amanda = Person ("Amanda", "Laucher") 27) System.out.println ("ted = = amanda:" + (if (ted = = amanda) "Yes" else "No") System.out.println ("ted = = ted:" + (if (ted = = ted) "Yes" else "No") System.out.println ("ted = = ted2:" + (if (ted = = ted2) "Yes" else "No"))} } / * C:\ Projects\ Exploration\ Scala > scala App ted = = amanda: No ted = = ted: Yes ted = = ted2: Yes * /

The real value of the case class lies in pattern matching, and readers of this series can review pattern matching (see the second article in this series on the various control constructs in Scala), which is similar to Java's "switch/case", except that it is more powerful and powerful. Pattern matching can not only check the value of the match construct to perform value matching, but also match values against local wildcards (something similar to local "default values"), case can also include protection for test matching, values from matching criteria can be bound to local variables, and even types that meet the matching criteria can match themselves.

With the case class, pattern matching is more powerful, as shown in listing 7:

Listing 7. This is not the old switch either.

Case class Person (first:String, last:String, age:Int) Object App {def main (args: Array [String]): Unit = {val ted = Person ("Ted", "Neward", 37) val amanda = Person ("Amanda", "Laucher") 27) System.out.println (process (ted)) System.out.println (process (amanda))} def process (p: Person) = {"Processing" + p + "reveals that" + (p match {case Person (_, a) if a > 30 = > "they're certainly old." Case Person (_, "Neward", _) = > "they come from good genes...." Case Person (first, last, ageInYears) if ageInYears > 17 = > first + "" + last + "is" + ageInYears + "years old." Case _ = > "I have no idea what to do with this person"} / * C:\ Projects\ Exploration\ Scala > scala App Processing Person (Ted,Neward,37) reveals that they're certainly old. Processing Person (Amanda,Laucher,27) reveals that Amanda Laucher is 27 years old. , /

A lot of things happen in listing 7. Let's take a closer look at what's going on, and then go back to the calculators and see how to apply them.

First, the entire match expression is wrapped in parentheses: this is not a requirement for pattern matching syntax, but it is because I concatenate the results of a pattern matching expression according to its prefix (remember, everything in a functional language is an expression).

Second, there are two wildcards in the * case expression (the underlined character is the wildcard), which means that the match will get any value for those two fields in the matching Person, but it introduces a local variable, the value in the Person P. age will be bound to this local variable. This case will only succeed if the protective expression provided at the same time (the if expression that follows it) succeeds, but only the * Person will do so, and the second will not. The second case expression uses a wildcard in the firstName part of Person, but uses the constant string Neward to match in the lastName part and wildcard characters in the age part.

Since the * Person has been matched by the previous case, and the second Person does not have a last name Neward, the match will not be triggered for any Person (however, Person ("Michael", "Neward", 15) will go to the second case due to the failure of the guard clause in the * case).

The third example shows a common use of pattern matching, sometimes called extraction, in which the values in the matching object p are extracted into local variables (* *, * *, and ageInYears) so that they can be used within the case block. The case expression of * * is the default value of normal case, and it will be triggered only if other case expressions are unsuccessful.

After a brief look at the case class and pattern matching, let's get back to the task of creating the calculator AST.

Computer AST

First of all, the calculator's AST must have a common base type, because mathematical expressions usually consist of subexpressions; you can easily see this with "5 + (2 * 10)", in this case, the subexpression "(2 * 10)" will be the right Operand of the "+" operation.

In fact, this expression provides three AST types:

◆ base expression

The Number type of ◆ that carries constant values

◆ carries the BinaryOperator of operations and two operands

Think about it. Unary operators are also allowed to be used as negative operators (minus signs) to convert values from positive to negative, so we can introduce the following basic AST:

Listing 8. Computer AST (src/calc.scala)

Package com.tedneward.calcdsl {private [calcdsl] abstract class Expr private [calcdsl] case class Number (value: Double) extends Expr private [calcdsl] case class UnaryOp (operator: String, arg: Expr) extends Expr private [calcdsl] case class BinaryOp (operator: String, left: Expr, right: Expr) extends Expr}

Note that the package declaration places all of this in a package (com.tedneward.calcdsl), and the access modifier declaration in front of each class indicates that the package can be accessed by other members or subpackages in the package. This is noted because you need to have a series of JUnit tests that can test the code; the actual client of the calculator does not have to see the AST. Therefore, to write the unit test as a subpackage of com.tedneward.calcdsl:

Listing 9. Computer Test (testsrc/calctest.scala)

Package com.tedneward.calcdsl.test {class CalcTest {import org.junit._, Assert._ @ Test def ASTTest = {val N1 = Number (5) assertEquals (5, n1.value)} @ Test def equalityTest = {val binop = BinaryOp ("+", Number (5), Number (10)) assertEquals (Number (5)) Binop.left) assertEquals (Number (10), binop.right) assertEquals ("+", binop.operator)}}

So far so good. We already have AST.

Come to think of it, we used four lines of Scala code to build a type hierarchy that represents a collection of mathematical expressions of arbitrary depth (simple, of course, but still useful). This is nothing compared to Scala's ability to make object programming easier and more expressive (don't worry, the really powerful features are yet to come).

Next, we need an evaluation function that will take the AST and find its numeric value. With the power of pattern matching, it is easy to write such a function:

Listing 10. Calculator (src/calc.scala)

Package com.tedneward.calcdsl {/ /... Object Calc {def evaluate (e: Expr): Double = {e match {case Number (x) = > x case UnaryOp ("-", x) = >-(evaluate (x)) case BinaryOp ("+", x1, x2) = > (evaluate (x1) + evaluate (x2)) case BinaryOp ("-", x1, x2) = > (evaluate (x1)-evaluate (x2)) case BinaryOp ("*") X1, x2) = > (evaluate (x1) * evaluate (x2)) case BinaryOp ("/", x1, x2) = > (evaluate (x1) / evaluate (x2))}

Notice that evaluate () returns a Double, which means that each case in the pattern match must be evaluated to a Double value. This is not difficult: numbers simply return the values they contain. But for the remaining case (there are two operators), we must also calculate the operands before performing the necessary operations (minus, addition, subtraction, and so on). As you often see in functional languages, recursion is used, so we just need to call evaluate () on each Operand before performing the overall operation.

Most object-oriented programmers will think that the idea of performing operations outside the various operators themselves is simply wrong-an idea that clearly violates the principles of encapsulation and polymorphism. Frankly, this is not even worth discussing; it clearly violates the principle of encapsulation, at least in the traditional sense.

A bigger question we need to consider here is: where exactly do we package the code? Keep in mind that the AST class is not visible outside the package, and that clients will (eventually) pass in only a string representation of the expression they want to evaluate. Only unit tests are working directly with the AST case class.

But this is not to say that all packages are useless or out of date. In fact, the opposite is true: it tries to convince us that there are many other design methods that work well in addition to the methods we are familiar with in the object domain. Don't forget that Scala is both object and functional; sometimes Expr needs to attach other behaviors to itself and its subclasses (for example, toString methods that implement good output), in which case you can easily add these methods to Expr. The combination of functional and object-oriented provides another option. Neither functional programmer nor object programmer ignores the design method of the other half, and will consider how to combine the two to achieve some interesting results.

From a design perspective, some other options are problematic; for example, using strings to host operators can lead to small input errors that eventually lead to incorrect results. In production code, enumerations may be used (or must be used) instead of strings, and using strings means that we may potentially "open" operators, allowing more complex functions (such as abs, sin, cos, tan, etc.) and even user-defined functions that are difficult to support based on enumerations.

For all designers and implementations, there is no appropriate decision-making method and can only bear the consequences. At your own risk.

But an interesting trick can be used here. Some mathematical expressions can be simplified, thus (potentially) optimizing the evaluation of expressions (thus demonstrating the usefulness of AST):

◆ any Operand with "0" can be reduced to a non-zero Operand.

◆ any Operand multiplied by "1" can be reduced to a non-zero Operand.

Any Operand multiplied by "0" in ◆ can be reduced to zero.

It's more than that. So we introduced a step called simplify () that is performed before evaluation, and uses it to perform these specific simplifications:

Listing 11. Calculator (src/calc.scala)

Def simplify (e: Expr): Expr = {e match {/ / Double negation returns the original value case UnaryOp ("-", UnaryOp ("-", x)) = > x / / Positive returns the original value case UnaryOp ("+", x) = > x / / Multiplying x by 1 returns the original value case BinaryOp ("*", x, Number (1)) = > x / / Multiplying 1 by x returns the original value case BinaryOp ("*", Number (1)) X) = > x / / Multiplying x by 0 returns zero case BinaryOp ("*", x, Number (0)) = > Number (0) / / Multiplying 0 by x returns zero case BinaryOp ("*", Number (0), x) = > Number (0) / / Dividing x by 1 returns the original value case BinaryOp ("/", x, Number (1)) = > x / / Adding x to 0 returns the original value case BinaryOp ("+", x) Number (0) = > x / / Adding 0 to x returns the original value case BinaryOp ("+", Number (0), x) = > x / / Anything else cannot (yet) be simplified case _ = > e}}

Also pay attention to how to use the constant matching and variable binding features of pattern matching, making it easy to write these expressions. The only change to evaluate () is that it includes a simplified call before evaluation:

Listing 12. Calculator (src/calc.scala)

Def evaluate (e: Expr): Double = {simplify (e) match {case Number (x) = > x case UnaryOp ("-", x) = >-(evaluate (x)) case BinaryOp ("+", x1, x2) = > (evaluate (x1) + evaluate (x2) case BinaryOp ("-", x1, x2) = > (evaluate (x1)-evaluate (x2)) case BinaryOp ("*", x1) X2) = > (evaluate (x1) * evaluate (x2)) case BinaryOp ("/", x1, x2) = > (evaluate (x1) / evaluate (x2))}}

It can be further simplified; note: how does it simplify only the * layer of the tree? If we have a BinaryOp that contains BinaryOp ("*", Number (0), Number (5)) and Number (5), then the internal BinaryOp can be simplified to Number (0), but the external BinaryOp will also be the same, because one of the operands of the external BinaryOp is zero.

I suddenly suffered from an occupational disease as a writer, so I want to leave it to the reader to define. Actually, it's just to make it a little more interesting. If readers are willing to send me their implementation, I will put it in the code analysis of the next article. There will be two test units to test this situation and will fail immediately. Your task (if you choose to accept it) is to make these tests-and any other test-pass as long as the test takes any degree of nesting of BinaryOp and UnaryOp.

Thank you for your reading, the above is the content of "how to build calculators in Scala". After the study of this article, I believe you have a deeper understanding of how to build calculators in Scala, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.