Thursday, September 10, 2009

Type Safe Builder in Scala, Part 4

A type-safe builder with mutually exclusive parameters.

In my previous three posts I presented various versions of a type-safe builder that enforced, at compile time, that required setters were called exactly once and optional setters were called no more than once. In those examples there was a one-to-one correspondence between the setters (such as withBrand) and type variables that were used to enforce the number of calls to those methods (such as HAS_BRAND). We can use the type variables in different ways to change what combination of methods calls is allowed. In particular, we can have multiple parameters which can be set in various combinations, only some of which are allowed. For example, we can have two mutually exclusive parameters, where you must set either one but not the other.

To show how this works, I have created a builder for a Pyramid calculator that can be used to calculate the physical parameters of a rectangular pyramid. After creating a builder, you can call various setter methods to set some of the physical parameters of the pyramid, including the length, width and area of the base, the height, and the length of an upright edge. You must set exactly two out of three of the length, width and area of the base, and you must set one but not both of the height and edge. Once you have done that, you call build to get back the calculator from which you can retrieve any of the five physical parameters listed above plus volume. If you call too few or too many of the setters in each group, the call to build will not compile.
object Pyramid { //A small collection of class types to define a state machine that counts abstract class COUNTER { type Count <: COUNTER } abstract class MANY extends COUNTER { type Count = MANY } abstract class TWO extends COUNTER { type Count = MANY } abstract class ZERO_OR_ONE extends COUNTER abstract class ONE extends ZERO_OR_ONE { type Count = TWO } abstract class ZERO extends ZERO_OR_ONE { type Count = ONE } //We require positive values for our calls class Positive(val d:Double) { if (d<=0) throw new IllegalArgumentException("non-positive value") } implicit def doubleToPositive(d:Double) = new Positive(d) implicit def intToPositive(n:Int) = new Positive(n) //The class that manages the state of our specification class Specs private[Pyramid]() { self:Specs => //Caller must set exactly two out of three of these val length:Double = 0 val width:Double = 0 val area:Double = 0 //Caller must set exactly one of these two heights val height:Double = 0 //vertical height to the tip val edge:Double = 0 //from base to tip along an edge //We maintain compiler-time state to count the two types of calls type TT <: { type COUNT_LENGTH <: COUNTER type COUNT_WIDTH <: COUNTER type COUNT_AREA <: COUNTER type COUNT_BASE <: COUNTER // length, width or area type COUNT_HEIGHT <: COUNTER type COUNT_EDGE <: COUNTER type COUNT_VERT <: COUNTER // height or edge } class SpecsWith(bb:Specs) extends Specs { override val length = bb.length override val width = bb.width override val area = bb.area override val height = bb.height override val edge = bb.edge } def setLength(d:Positive) = new SpecsWith(this) { override val length:Double = d.d type TT = self.TT { type COUNT_LENGTH = self.TT#COUNT_LENGTH#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setWidth(d:Positive) = new SpecsWith(this) { override val width:Double = d.d type TT = self.TT { type COUNT_WIDTH = self.TT#COUNT_WIDTH#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setArea(d:Positive) = new SpecsWith(this) { override val area:Double = d.d type TT = self.TT { type COUNT_AREA = self.TT#COUNT_AREA#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setHeight(d:Positive) = new SpecsWith(this) { override val height:Double = d.d type TT = self.TT { type COUNT_HEIGHT = self.TT#COUNT_HEIGHT#Count type COUNT_VERT = self.TT#COUNT_VERT#Count } } def setEdge(d:Positive) = new SpecsWith(this) { override val edge:Double = d.d type TT = self.TT { type COUNT_EDGE = self.TT#COUNT_EDGE#Count type COUNT_VERT = self.TT#COUNT_VERT#Count } } } //Starting point: nothing is set def apply() = new Specs { type TT = { type COUNT_LENGTH = ZERO type COUNT_WIDTH = ZERO type COUNT_AREA = ZERO type COUNT_BASE = ZERO type COUNT_HEIGHT = ZERO type COUNT_EDGE = ZERO type COUNT_VERT = ZERO } } //Required ending point: two base measures, one height measure, //no single parameter more than once type CompleteSpecs = Specs { type TT <: { type COUNT_LENGTH <: ZERO_OR_ONE type COUNT_WIDTH <: ZERO_OR_ONE type COUNT_AREA <: ZERO_OR_ONE type COUNT_BASE = TWO type COUNT_HEIGHT <: ZERO_OR_ONE type COUNT_EDGE <: ZERO_OR_ONE type COUNT_VERT = ONE } } //Calc1 includes the first set of values that can be calculated class Calc1 private[Pyramid](spec:CompleteSpecs) { import java.lang.Math.sqrt //The three related base measures lazy val length = if (spec.length!=0) spec.length else spec.area/spec.width lazy val width = if (spec.width!=0) spec.width else spec.area/spec.length lazy val area = if (spec.area!=0) spec.area else spec.length*spec.width //The two related height measures lazy val height = if (spec.height!=0) spec.height else sqrt(spec.edge*spec.edge-length*length/4-width*width/4) lazy val edge = if (spec.edge!=0) spec.edge else sqrt(length*length/4+width*width/4+spec.height*spec.height) lazy val volume = length * width * height / 3 } implicit def specsOK(spec:CompleteSpecs) = new { def build = new Calc1(spec) } }
As before, remember to import Pyramid._ when using this code.

Let's examine the code.

To start, I have a small type-based state machine, similar to what I used in my previous post. I changed the names of the classes to more accurately reflect the fact that I am counting the number of calls to methods, and I added a class to represent a count of two as distinct from larger numbers.

Next I define a class that ensures that the values passed to the setters are all strictly positive numbers (since they represent physical quantities), and I add a couple of implicit conversion methods to allow the caller to pass in ints or doubles. If the caller passes in a negative number, the builder will throw a runtime exception.

The Specs class is where I maintain my state information as the builder is being constructed. I use the same basic approach as in my previous post, with a set of parameter values and a set of compile-time constraints, the latter represented by the TT compound type. Note that in addition to the type parameter values that are directly associated with the parameters, which are used to ensure that each individual setter is called not more than once, there are two additional type values that do not directly correspond to parameter values or individual setters. The COUNT_BASE type value is associated with the length, width and area parameters, while the COUNT_VERT type value is associated with the height and edge parameters. This association is specified in the setter methods.

The SpecsWith class allows me to default all values to the previous step in the builder chain, so that I can override just the value I want to change in each setter.

Each of the five setters sets its parameter value, sets a new value for its individual type value counter, and also sets a new type value for one of the non-individual counters. Note how the setters for length, width and area all refer to COUNT_BASE, while the setters for height and edge both refer to COUNT_VERT.

I chose to define an apply() method rather than call it builder. This allows me to start my builder chain by specifying just Pyramid().

The CompleteSpecs type definition defines the end point that will be valid for a call to build. You can see here how it requires that COUNT_BASE be TWO and COUNT_HEIGHT be ONE. The other call counts can be zero or one.

Calc1 is the class that actually does the calculation of the physical parameters.

Finally, the specsOK implicit method provides the link that allows only a complete builder to call the build method that returns the calculator.

Here is an example of how you use it:
import Pyramid._ //we need the implicit conversion to be in scope val p = Pyramid().setLength(10).setWidth(8).setHeight(6).build p.length //returns 10 p.area //returns 80 p.volume //returns 160
Each of the following will give a compiler error:
Pyramid().setWidth(2).setHeight(2).build //only one BASE param, need 2 Pyramid().setWidth(2).setLength(3).setArea(6).setHeight(2).build //too many BASE params Pyramid().setWidth(2).setWidth(3).setHeight(2).build //setWidth called twice
Note the second example: even though the base area (6) is compatible with the width and length, this line gives a compiler error because three BASE parameters were specified; the compile time checks do not look at the values of the parameters.

Let's add a parameter for density such that, if we have called the setter for density, we can get back a calculator that can tell us the mass of the pyramid as well as everything else. The code below shows, in bold, what needs to be added to the above example in order to do that.
object Pyramid { //A small collection of class types to define a state machine that counts abstract class COUNTER { type Count <: COUNTER } abstract class MANY extends COUNTER { type Count = MANY } abstract class TWO extends COUNTER { type Count = MANY } abstract class ZERO_OR_ONE extends COUNTER abstract class ONE extends ZERO_OR_ONE { type Count = TWO } abstract class ZERO extends ZERO_OR_ONE { type Count = ONE } //We require positive values for our calls class Positive(val d:Double) { if (d<=0) throw new IllegalArgumentException("non-positive value") } implicit def doubleToPositive(d:Double) = new Positive(d) implicit def intToPositive(n:Int) = new Positive(n) //The class that manages the state of our specification class Specs private[Pyramid]() { self:Specs => //Caller must set exactly two out of three of these val length:Double = 0 val width:Double = 0 val area:Double = 0 //Caller must set exactly one of these two heights val height:Double = 0 //vertical height to the tip val edge:Double = 0 //from base to tip along an edge //Optional value; if set, we can calculate mass val density:Double = 0 //We maintain compiler-time state to count the two types of calls type TT <: { type COUNT_LENGTH <: COUNTER type COUNT_WIDTH <: COUNTER type COUNT_AREA <: COUNTER type COUNT_BASE <: COUNTER // length, width or area type COUNT_HEIGHT <: COUNTER type COUNT_EDGE <: COUNTER type COUNT_VERT <: COUNTER // height or edge type COUNT_DENSITY <: COUNTER } class SpecsWith(bb:Specs) extends Specs { override val length = bb.length override val width = bb.width override val area = bb.area override val height = bb.height override val edge = bb.edge override val density = bb.density } def setLength(d:Positive) = new SpecsWith(this) { override val length:Double = d.d type TT = self.TT { type COUNT_LENGTH = self.TT#COUNT_LENGTH#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setWidth(d:Positive) = new SpecsWith(this) { override val width:Double = d.d type TT = self.TT { type COUNT_WIDTH = self.TT#COUNT_WIDTH#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setArea(d:Positive) = new SpecsWith(this) { override val area:Double = d.d type TT = self.TT { type COUNT_AREA = self.TT#COUNT_AREA#Count type COUNT_BASE = self.TT#COUNT_BASE#Count } } def setHeight(d:Positive) = new SpecsWith(this) { override val height:Double = d.d type TT = self.TT { type COUNT_HEIGHT = self.TT#COUNT_HEIGHT#Count type COUNT_VERT = self.TT#COUNT_VERT#Count } } def setEdge(d:Positive) = new SpecsWith(this) { override val edge:Double = d.d type TT = self.TT { type COUNT_EDGE = self.TT#COUNT_EDGE#Count type COUNT_VERT = self.TT#COUNT_VERT#Count } } def setDensity(d:Positive) = new SpecsWith(this) { override val density:Double = d.d type TT = self.TT { type COUNT_DENSITY = self.TT#COUNT_DENSITY#Count } } } //Starting point: nothing is set def apply() = new Specs { type TT = { type COUNT_LENGTH = ZERO type COUNT_WIDTH = ZERO type COUNT_AREA = ZERO type COUNT_BASE = ZERO type COUNT_HEIGHT = ZERO type COUNT_EDGE = ZERO type COUNT_VERT = ZERO type COUNT_DENSITY = ZERO } } //Required ending point: two base measures, one height measure, //no single parameter more than once type CompleteSpecs = Specs { type TT <: { type COUNT_LENGTH <: ZERO_OR_ONE type COUNT_WIDTH <: ZERO_OR_ONE type COUNT_AREA <: ZERO_OR_ONE type COUNT_BASE = TWO type COUNT_HEIGHT <: ZERO_OR_ONE type COUNT_EDGE <: ZERO_OR_ONE type COUNT_VERT = ONE } } //Calc1 includes the first set of values that can be calculated class Calc1 private[Pyramid](spec:CompleteSpecs) { import java.lang.Math.sqrt //The three related base measures lazy val length = if (spec.length!=0) spec.length else spec.area/spec.width lazy val width = if (spec.width!=0) spec.width else spec.area/spec.length lazy val area = if (spec.area!=0) spec.area else spec.length*spec.width //The two related height measures lazy val height = if (spec.height!=0) spec.height else sqrt(spec.edge*spec.edge-length*length/4-width*width/4) lazy val edge = if (spec.edge!=0) spec.edge else sqrt(length*length/4+width*width/4+spec.height*spec.height) lazy val volume = length * width * height / 3 } implicit def specsOK(spec:CompleteSpecs) = new { def build = new Calc1(spec) } //Second set of allowable computations type CompleteSpecs2 = Specs { type TT <: { type COUNT_LENGTH <: ZERO_OR_ONE type COUNT_WIDTH <: ZERO_OR_ONE type COUNT_AREA <: ZERO_OR_ONE type COUNT_BASE = TWO type COUNT_HEIGHT <: ZERO_OR_ONE type COUNT_EDGE <: ZERO_OR_ONE type COUNT_VERT = ONE type COUNT_DENSITY = ONE } } class Calc2 private[Pyramid](spec:CompleteSpecs2) extends Calc1(spec) { lazy val mass = spec.density * volume } implicit def specsOK2(spec:CompleteSpecs2) = new { def build2 = new Calc2(spec) } }
To get the mass, we have to call all of the appropriate setters, including density, then call build2 rather than build to get our calculator. That will give us a calculator that can give us the mass value as well as all the values in the calculator returned by build.
val p = Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).build2 p.volume //returns 4 p.mass //returns 8
These examples fail:
Pyramid().setHeight(2).setWidth(3).setArea(6).build2 //no density Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).setDensity(3).build2 //density specified twice
I intentionally left out one line when adding the density code, so the following code compiles:
Pyramid().setHeight(2).setWidth(3).setArea(6).setDensity(2).setDensity(3).build
Since the build method returns a calculator that does not do anything with the density, this is perhaps not a problem. You can test your understanding of Scala types by figuring out what one line you need to add to the density example to make this last call fail to compile.

Wednesday, September 9, 2009

Type Safe Builder in Scala, Part 3

Another solution to implementing a type-safe builder in Scala.

In my previous two posts I presented a couple of different implementations of the type-safe builder pattern originally presented by Rafeal de F. Ferreira. But there was something about them that bothered me: both of my implementations, both of Rafael's implementations, and gambistics' implementation written in response to my second attempt, all exhibit the same bothersome characteristic: every setter includes references to all of the state information (both type information and parameter values) being built up in the Builder.

I found this to be a very inelegant aspect of these solutions. Given N parameters with their corresponding setters, there is an O(N^2) maintenance problem: every time you add or remove a parameter, or make certain changes to existing parameters, such as changing name or type, you have to make that change in every setter method.

Below is an implementation without any source code interaction between the setters or parameters; each setter only deals with its own data. Adding, removing or changing any parameter and corresponding setter can be done without dealing with any of the other parameters, making this implementation O(N) for N parameters. As with my Part 2 implementation, this implementation handles both optional and required parameters, ensuring at compile time that required setters are called exactly once and optional setters are not called more than once.
object Scotch { //A small collection of class types to define a state machine abstract class STATE { type TrueOnce <: STATE } abstract class NOT_MULTI extends STATE abstract class MULTI extends STATE { type TrueOnce = MULTI } abstract class TRUE extends NOT_MULTI { type TrueOnce = MULTI } abstract class FALSE extends NOT_MULTI { type TrueOnce = TRUE } sealed abstract class Preparation case object Neat extends Preparation case object OnTheRocks extends Preparation case object WithWater extends Preparation sealed abstract class Glass case object Short extends Glass case object Tall extends Glass case object Tulip extends Glass case class OrderOfScotch private[Scotch] ( val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass]) class ScotchBuilder private[Scotch]() { self:ScotchBuilder => val theBrand:Option[String] = None val theMode:Option[Preparation] = None val theDoubleStatus:Option[Boolean] = None val theGlass:Option[Glass] = None type TT <: { type HAS_BRAND <: STATE type HAS_MODE <: STATE type HAS_DOUBLE <: STATE type HAS_GLASS <: STATE } class ScotchBuilderWith(sb:ScotchBuilder) extends ScotchBuilder { override val theBrand = sb.theBrand override val theMode = sb.theMode override val theDoubleStatus = sb.theDoubleStatus override val theGlass = sb.theGlass } def withBrand(b:String) = new ScotchBuilderWith(this) { override val theBrand:Option[String] = Some(b) type TT = self.TT { type HAS_BRAND = self.TT#HAS_BRAND#TrueOnce } } def withMode(p:Preparation) = new ScotchBuilderWith(this) { override val theMode:Option[Preparation] = Some(p) type TT = self.TT { type HAS_MODE = self.TT#HAS_MODE#TrueOnce } } def isDouble(b:Boolean) = new ScotchBuilderWith(this) { override val theDoubleStatus:Option[Boolean] = Some(b) type TT = self.TT { type HAS_DOUBLE = self.TT#HAS_DOUBLE#TrueOnce } } def withGlass(g:Glass) = new ScotchBuilderWith(this) { override val theGlass:Option[Glass] = Some(g) type TT = self.TT { type HAS_GLASS = self.TT#HAS_GLASS#TrueOnce } } } //Starting point: nothing is set lazy val builder = new ScotchBuilder { type TT = { type HAS_BRAND = FALSE type HAS_MODE = FALSE type HAS_DOUBLE = FALSE type HAS_GLASS = FALSE } } //Required ending point: TRUE for required, NOT_MULTI for optional type CompleteBuilder = ScotchBuilder { type TT <: { type HAS_BRAND = TRUE type HAS_MODE = TRUE type HAS_DOUBLE = TRUE type HAS_GLASS <: NOT_MULTI } } implicit def enableBuild(builder:CompleteBuilder) = new { def build() = new OrderOfScotch( builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass); } }
It actually took me quite a while to come up with this solution. I spent a lot of time trying different things that almost worked. Scala's type system is powerful, but debugging is a bear.

Monday, September 7, 2009

Type Safe Builder in Scala, Part 2

Here is a way to limit the number of calls to each setter method in a builder without using Church Numerals.

Update 2009-09-09: See also Part 3, which shows an O(N) implementation.
Copyright Note: The code in this post may not be covered by the LGPL.

The BuilderPattern code is a derivative of code posted by Rafael de F. Ferreira, so is covered by his copyright.

All code is used here for educational purposes under Fair Use.
A number of people commented in response to Rafael's original post that this type-safe builder approach (of explicitly using types to track desired behavior at compile-time) is much more complicated than a simple builder class in which the required parameters are constructor args to the builder, and the optional parameters are setters. Of course that's true, and with named parameters and default values coming in Scala 2.8, defining and using such builders can be even simpler. But, besides the fact that the type-safe approach can be used in more complex builders in which the constructor approach does not work well, the issue is not relevant, because the main point of this exercise is to see how Scala's type system can be used to do interesting things.

In my previous blog post I showed how to use Church Numerals to limit (at compile time) calls to setters to no more than once per setter. Using Church Numerals was handy for me because I already had them, so it was easy to switch from booleans to integers to keep track of how many times a setter was called.

Keeping count of calls this way could be useful in some context, but in this case all I was doing was ensuring that an item was called no more than once. Also, the recommendation I made in my closing paragraph to use multiple implicit conversion functions to deal with optional setters does not scale well when there are multiple optional setters.

Below is a simpler approach that ensures that required setters are called exactly once, that optional setters are called not more than once, that doesn't require Church Numerals, and that uses only a single implicit conversion method. As before, my changes from Rafael's original are in bold.
object BuilderPattern { sealed abstract class Preparation case object Neat extends Preparation case object OnTheRocks extends Preparation case object WithWater extends Preparation sealed abstract class Glass case object Short extends Glass case object Tall extends Glass case object Tulip extends Glass case class OrderOfScotch private[BuilderPattern] (val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass]) abstract class STATE { type TrueOnce <: STATE } abstract class NOT_MULTI extends STATE abstract class MULTI extends STATE { type TrueOnce = MULTI } abstract class TRUE extends NOT_MULTI { type TrueOnce = MULTI } abstract class FALSE extends NOT_MULTI { type TrueOnce = TRUE } abstract class ScotchBuilder { self:ScotchBuilder => protected[BuilderPattern] val theBrand:Option[String] protected[BuilderPattern] val theMode:Option[Preparation] protected[BuilderPattern] val theDoubleStatus:Option[Boolean] protected[BuilderPattern] val theGlass:Option[Glass] type HAS_BRAND <: STATE type HAS_MODE <: STATE type HAS_DOUBLE_STATUS <: STATE type HAS_GLASS <: STATE def withBrand(b:String) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = Some(b) protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND#TrueOnce type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS type HAS_GLASS = self.HAS_GLASS } def withMode(p:Preparation) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = Some(p) protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE#TrueOnce type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS type HAS_GLASS = self.HAS_GLASS } def isDouble(b:Boolean) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = Some(b) protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS#TrueOnce type HAS_GLASS = self.HAS_GLASS } def withGlass(g:Glass) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = Some(g) type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS type HAS_GLASS = self.HAS_GLASS#TrueOnce } } type CompleteBuilder = ScotchBuilder { type HAS_BRAND = TRUE type HAS_MODE = TRUE type HAS_DOUBLE_STATUS = TRUE type HAS_GLASS <: NOT_MULTI } implicit def enableBuild(builder:CompleteBuilder) = new { def build() = new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass); } def builder = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = None protected[BuilderPattern] val theMode:Option[Preparation] = None protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = None protected[BuilderPattern] val theGlass:Option[Glass] = None type HAS_BRAND = FALSE type HAS_MODE = FALSE type HAS_DOUBLE_STATUS = FALSE type HAS_GLASS = FALSE } }
As before, remember to import BuilderPattern._ to ensure that the implicit conversion method is in scope when using this patterm.

The changes are straightforward:
  1. I added the HAS_GLASS type to track the state of the number of calls to the withGlass method. It is coded in exactly the same way as the other state tracking types with the one exception of its value in the CompleteBuilder type. The CompleteBuilder type encodes which parameters are optional and which are required.
  2. Rather than having two states (just TRUE and FALSE), I am using a little class hierarchy with three states, representing no calls to a setter (FALSE), one call to a setter (TRUE), and more than one call to a setter (MULTI).
  3. Instead of just setting a state to TRUE when a setter is called, I am using a type member of the current state to implement a little state machine. The state machine transitions from FALSE to TRUE to MULTI and then stays in the MULTI state.
  4. The TRUE and FALSE states are in a separate subtree NOT_MULTI so that I can specify a value that includes either of those states, but not the MULTI state. I use this value in the CompleteBuilder type to specify that the HAS_GLASS value can be either TRUE or FALSE.
Bottom line: this implementation provides compile-time checking that the required setters are called exactly once, that the optional setters are called at most once, and is much simpler than the Church Numerals implementation.

Sunday, September 6, 2009

Type Safe Builder in Scala Using Church Numerals

I present another possibly practical application of Church Numerals in Scala.

Update 2009-09-07: See also Part 2, which shows similar functionality without using Church Numerals.

Update 2009-09-09: See also Part 3, which shows an O(N) implementation.
Copyright Note: The code in this post may not be covered by the LGPL.

The BuilderPattern code is a derivative of code posted by Rafael de F. Ferreira, so is covered by his copyright.

The Church Numerals code is from my Practical Church Numerals blog post; see that post for copyright information.

All code is used here for educational purposes under Fair Use.
Recently I came across an article by Rafael de F. Ferreira, and a followup article with an alternate approach, on how to implement the Builder pattern in Scala in a way that is type-safe. In particular, his implementation allows for compile-time checking to ensure that each required field has been set by a call to a setter (in Rafael's code, the withXXX methods) in the Builder object. If the developer fails to call all of the required methods, the application will not compile. The error messages given by the compiler in this case are not necessarily clear, but I like the concept.

One of the thoughts that crossed my mind was, what happens if you call one of the setter methods twice? Rafael's type-safe code does not prevent that scenario; if the coder puts in two calls to the same setter method, it compiles without problem and calls the setter twice at run time.

Perhaps that is not a concern, but if we can use the compiler to ensure that required setters are called, could we also use it to ensure that setters are called no more than once? Rafael's code uses boolean type values to encode whether or not a value has been set. By using integer values for the types, we can keep a count of how many times a setter has been called. That sounds like a job for Church Numerals.

In my post Practical Church Numerals in Scala I showed how you could encode integers in the Scala type system using the Church Numerals construct, and use those numerals to construct a type-safe units class. We can do something similar here.

First, here is an implementation of Church Numerals taken from that blog posting. See that post for a description of how it works.
object ChurchNumerals { trait CInt { type Succ <: CInt type Add[N <: CInt] <: CInt } trait CPos extends CInt class CSucc[P <: CPos] extends CPos { type Succ = CSucc[CSucc[P]] type Add[N <: CInt] = P#Add[N]#Succ } final class _0 extends CPos { type Succ = CSucc[_0] type Add[N <: CInt] = N } type +[N1<:CInt, N2<:CInt] = N1#Add[N2] type _1 = _0#Succ type _2 = _1#Succ type _3 = _2#Succ }
Below is my modified version of the type-safe Builder pattern using Church Numerals instead of booleans for the types. My changes from Rafael's original are in bold.
object BuilderPattern { import ChurchNumerals._ sealed abstract class Preparation case object Neat extends Preparation case object OnTheRocks extends Preparation case object WithWater extends Preparation sealed abstract class Glass case object Short extends Glass case object Tall extends Glass case object Tulip extends Glass case class OrderOfScotch private[BuilderPattern] (val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass]) //FALSE and TRUE are not used, we use _0 and _1 instead abstract class ScotchBuilder { self:ScotchBuilder => protected[BuilderPattern] val theBrand:Option[String] protected[BuilderPattern] val theMode:Option[Preparation] protected[BuilderPattern] val theDoubleStatus:Option[Boolean] protected[BuilderPattern] val theGlass:Option[Glass] type HAS_BRAND <: ChurchNumerals.CInt type HAS_MODE <: ChurchNumerals.CInt type HAS_DOUBLE_STATUS <: ChurchNumerals.CInt def withBrand(b:String) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = Some(b) protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND + _1 type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS } def withMode(p:Preparation) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = Some(p) protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE + _1 type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS } def isDouble(b:Boolean) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = Some(b) protected[BuilderPattern] val theGlass:Option[Glass] = self.theGlass type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS + _1 } def withGlass(g:Glass) = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = self.theBrand protected[BuilderPattern] val theMode:Option[Preparation] = self.theMode protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = self.theDoubleStatus protected[BuilderPattern] val theGlass:Option[Glass] = Some(g) type HAS_BRAND = self.HAS_BRAND type HAS_MODE = self.HAS_MODE type HAS_DOUBLE_STATUS = self.HAS_DOUBLE_STATUS } } type CompleteBuilder = ScotchBuilder { type HAS_BRAND = _1 type HAS_MODE = _1 type HAS_DOUBLE_STATUS = _1 } implicit def enableBuild(builder:CompleteBuilder) = new { def build() = new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass); } def builder = new ScotchBuilder { protected[BuilderPattern] val theBrand:Option[String] = None protected[BuilderPattern] val theMode:Option[Preparation] = None protected[BuilderPattern] val theDoubleStatus:Option[Boolean] = None protected[BuilderPattern] val theGlass:Option[Glass] = None type HAS_BRAND = _0 type HAS_MODE = _0 type HAS_DOUBLE_STATUS = _0 } } //Remember to use "import BuilderPattern._" in your code
As you can see, I have replaced the use of the boolean values TRUE and FALSE by the Church Numerals _0 and _1. Specifying the CompleteBuilder type as requiring _1 in all the positions ensures that the enableBuild implicit method will only be available if each setter has been called exactly once. You can try this out yourself in the Scala REPL. Copy and paste the above two chunks of code, plus the command import BuilderPattern._ to ensure the implicit conversion is in scope. You can then try the following examples. In particular, the third example contains two calls to withBrand, which fails in this implementation but succeeds in Rafael's original implementation.
builder.withBrand("x").withMode(BuilderPattern.Neat).build //error builder.withBrand("x").withMode(BuilderPattern.Neat).isDouble(true).build //ok builder.withBrand("x").withMode(BuilderPattern.Neat).isDouble(true).withBrand("y").build //error
You may have noticed that I did not modify the withGlass method, so that method could be called more than once. If you want to restrict that method to be called zero or one time, you could add a HAS_GLASS type parameter for it, which you would keep track of in exactly the same way as the other three type parameters. The only difference would then be that you would have two flavors of CompleteBuilder, one with type HAS_GLASS = _1 and one with type HAS_GLASS = _0, along with two implicit conversion methods, one for each of the two CompleteBuilder types. This is an example of Rafael's comment that "we can specify any other point in the lattice" as a legal state from which to execute the build method. I leave the implementation of that step as an exercise for the reader.