Share
Embed
ADT Pattern Matching Java Devoxx 2.0
Balkrishna Rawool
January 10, 2024
Transcript
25 slides
-
Alignment indicator 11 Dec 2023 Balkrishna Rawool Algebraic Data Types
+ Pattern matching = Elegant and readable Java code -
2 Process A problem Design a solution Implementation (using Algebraic
Data Types and pattern matching) Easy to read, understand code -
4 The problem S E N D M O R
E + Y E N O M -
5 The rules/ requirements Ø Cryptarithmetic puzzle Ø Each letter
corresponds to a single digit (non-negative) number Ø All letters have unique numbers Ø Letters placed together form a multi-digit number (e.g. SEND) Ø The letter M cannot be 0 (zero) Ø This equality constraint holds true: SEND + MORE = MONEY S E N D M O R E + Y E N O M -
6 Problem analysis Ø There are 8 letter: S, E,
N, D, M, O, R, Y Rule/ Constraint Each letter has 10 possibilities (0 to 9), except M. Number of possible solutions 107 * 9 = 90,000,000 Each letter has a unique value. 9 * 9C7 = 1,632,960 M cannot be 0. (That means M is1.) 9C7 = 181,440 SEND + MORE = MONEY ? -
7 Constraint programming Ø Variables and constraints Ø Constraints Satisfaction
Problems Ø Java libraries: Choco-solver, Jsolver, OptaPlanner, MiniCP etc. Ø We are not going to use any library. Variables Constraints > = < -
8 Goals (and non-goals) We don’t aim: To write the
most concise implementation. (This is not a code golf.) To write the fastest running program. We do aim: To solve the problem at hand. To keep it verbose enough to be clear and readable. To make it extensible. To learn about Algebraic Data Types and pattern matching in Java. -
9 The solution design Ø Generate all possible combinations of
values for all variables → Generator Ø Evaluate the expressions → Expression evaluator Ø If all the constraints hold true for a combination of values, we have a solution → Puzzle solver Expression Evaluator Generator Puzzle Solver S E ND MO RE + Y E N O M -
10 Expression evaluator Ø An example of an expression: SEND
Ø If the values of S, E, N, D are s, e, n, d respectively, then The value of SEND = s*1000 + e*100 + n*10 + d Grammar: Expression = a constant | a variable | (an expression) + (an expression) | (an expression) * (an expression) d e * 1000 100 10 n + s * * + + -
11 Algebraic Data Types Ø Data types created by combining
existing data types (mainly by applying algebraic operations) Ø Common categories: Sum types and Product types -
12 Product Types Ø Each possible value of new type
has value for each of its constituent types. Ø Examples Ø A point has two coordinates: x and y. Ø An address has a house-number, a street, a city and a country. -
13 Sum Types Ø Each possible value of new type
is one of the values of its constituent types. Ø Example Ø A shape can either be a triangle, a quadrilateral or a circle. -
14 Pattern matching Ø Pattern matching is checking for the
presence of a pattern in a given sequence of tokens. Ø Features in Java 21 Ø Pattern matching for instanceof (JEP-394) Ø Record patterns (JEP-440) Ø Pattern matching for switch (JEP-441) Ø Unnamed patterns and variables - Preview (JEP-443) -
15 Pattern matching examples Ø Pattern matching for instanceof Ø
Record patterns -
16 Pattern matching examples Ø Pattern matching for switch Ø
Unnamed patterns and variables -
18 Solution steps Ø Each letter corresponds to a single
digit (non-negative) number Ø Create Variable to represent each letter Ø Create RangeConstraint to represent possible values of a variable Ø Create Expression with evaluation function Ø Generator should generate all possible combinations of variable-values Ø Create more constraint types Ø All values must be unique → UniqueValuesConstraint Ø Equality constraints must be satisfied → Create EqualityConstraint Ø Puzzle solver needs to use Generator and Expression-s to find solution(s). Expression Evaluator Generator Puzzle Solver S E ND MO RE + Y E N O M -
20 Expression evaluator Grammar: Expression = a constant | a
variable | (an expression) + (an expression) | (an expression) * (an expression) -
21 Summary Ø We kept data separate from behaviour. Ø
Algebraic data types helped us to model data so that only valid states are allowed to exist. Ø We used records and sealed types to implement product and sum types. Ø Pattern matching features helped us with implementing behaviour/ functions that operated on the data. -
22 Data Oriented Programming Ø Data-oriented programming encourages us to
model data as immutable data and keep the code, that embodies the business logic, separate. Ø Explained by Brian Goetz (Java Language Architect at Oracle) in this article: bit.ly/DOPJava Ø Principles Ø Model the data, the whole data, and nothing but the data. Ø Data is immutable. Ø Validate at the boundary. Ø Make illegal states unrepresentable. Ø ADT and pattern matching (in other words records, sealed types, and pattern matching in Java) work together to enable easier data-oriented programming. Ø OOP and DOP: OOP is useful when modelling large complex systems and DOP is suitable for simpler/ smaller (sub) system.