CSci 555-01: Functional Programming
Spring 2016

Sandwich DSL Case Study and Exercises

Building the DSL

Suppose Emerald de Gassy, the owner of the Oxford-based catering business Deli-Gate, hires us to design a domain-specific language (DSL) for describing sandwich platters. The DSL scripts will direct Deli-Gate's robotic kitchen appliance SueChef (Sandwich and Utility Electronic Chef) to assemble platters of sandwiches.

In discussing the problem with Emerald and the Deli-Gate staff, we discover the following:

• A sandwich platter consists of zero or more sandwiches. (Zero? Why not! Although a platter with no sandwiches may not be a useful, or profitable, case, there does not seem to be any harm in allowing this degenerate case. It may simplify some of the coding and representation.)
• Each sandwich consists of layers of ingredients.
• The categories of ingredients are breads, meats, cheeses, vegetables, and condiments.
• Available breads are white, wheat, and rye.
• Available meats are turkey, chicken, ham, roast beef, and tofu. (Okay, tofu is not a meat, but it is a good protein source for those who do not wish to eat meat. This is a college town after all. Oh, there is also a special meat served for football games Thanksgiving week called "bulldog", but it is really just chicken, so we can ignore that choice for our purposes here.)
• Available cheeses are American, Swiss, jack, and cheddar.
• Available vegetables are tomato, lettuce, onion, and bell pepper.
• Available condiments are mayo, mustard, relish, and Tabasco. (Of course, this being the South, the mayo is Blue Plate Mayonnaise and the mustard is a Creole mustard.)

Let's define this as an internal DSL--in particular, by using a relatively deep embedding.

What is a sandwich? ... Basically, it is a stack of ingredients.

Should we require the sandwich to have a bread on the bottom? ... Probably. ... On the top? Maybe not, to allow "open-faced" sandwiches. ... What can the SueChef build? ... We don't know at this point, but let's assume it can stack up any ingredients without restriction.

For simplicity and flexibility, let's define a Scala data type Sandwich to model sandwiches. It wraps a possibly empty list of ingredient layers. We assume the head of the list to be the layer at the top of the sandwich.

    case class Sandwich(sandwich: List[Layer])

Note: In this case study, we implement Scala algebraic data type constructors (i.e., product types) as case class or case object entities. We implement union types using a trait with subtypes for the variants.

Data type Sandwich gives the specification for a sandwich. When "executed" by the SueChef, it results in the assembly of a sandwich that satisfies the specification.

As defined, the Sandwich data type does not require there to be a bread in the stack of ingredients. However, we add function newSandwich that starts a sandwich with a bread at the bottom and a function addLayer that adds a new ingredient to the top of the sandwich. We leave the implementation of these functions as exercises.

    def newSandwich(b: Bread): Sandwich
    def addLayer(s: Sandwich)(x: Layer): Sandwich 

Ingredients are in one of five categories: breads, meats, cheeses, vegetables, and condiments. Because both the categories and the specific type of ingredient is important, we choose to represent both in the type structures and define the following types. A value of type Layer represents a single ingredient. Type Layer has five variants (subtypes) Bread, Meat, Cheese, Vegetable, and Condiment. Each of these variants itself has several variants. For example, Bread has variants (subtypes) White, Wheat, and Rye.

    sealed trait Layer

    sealed trait Bread     extends Layer
    case object White      extends Bread
    case object Wheat      extends Bread
    case object Rye        extends Bread

    sealed trait Meat      extends Layer
    case object Turkey     extends Meat
    case object Chicken    extends Meat
    case object Ham        extends Meat
    case object RoastBeef  extends Meat
    case object Tofu       extends Meat

    sealed trait Cheese    extends Layer
    case object American   extends Cheese
    case object Swiss      extends Cheese
    case object Jack       extends Cheese
    case object Cheddar    extends Cheese

    sealed trait Vegetable extends Layer
    case object Tomato extends Vegetable
    case object Onion extends Vegetable
    case object Lettuce extends Vegetable
    case object BellPepper extends Vegetable

    sealed trait Condiment extends Layer
    case object Mayo       extends Condiment
    case object Mustard    extends Condiment
    case object Ketchup    extends Condiment
    case object Relish     extends Condiment
    case object Tabasco    extends Condiment

We need to be able to compare ingredients for equality and convert them to strings. Because the automatically generated definitions are appropriate, we do not need to do anything further. We will need to provide an appropriate definition of equality for Sandwich because the default element-by-element equality of lists does not seem to be the appropriate equality comparison for sandwiches.

To complete the model, we define type Platter to wrap a list of sandwiches.

    case class Platter(platter: List[Sandwich])

We also define functions newPlatter to create a new Platter and addSandwich to add a sandwich to the Platter. We leave the implementation of these functions as exercises.

    def newPlatter: Platter
    def addSandwich(p: Platter)(s: Sandwich): Platter

Exercise Set 1

Please put these functions in a Scala module SandwichDSL. You may use functions defined earlier in the exercises to implement those later in the exercises.

1. Define the Scala functions newSandwich, addLayer, newPlatter, and addSandwich described above.
2. Define the Scala query functions below that take an ingredient (i.e., Layer) and return true if and only if the ingredient is in the specified category.

   def isBread(x: Layer): Boolean 
   def isMeat(x: Layer): Boolean
   def isCheese(x: Layer): Boolean 
   def isVegetable(x: Layer): Boolean 
   def isCondiment(x: Layer): Boolean
   

3. According to a proposed City of Oxford ordinance, in the future it may be necessary to assemble all sandwiches in Oxford Standard Order (OSO): a slice of bread on the bottom, then zero or more meats layered above that, then zero or more cheeses, then zero or more vegetables, then zero or more condiments, and then a slice of bread on top. The top and bottom slices of bread must be of the same type. Define a Scala function inOSO that takes a sandwich and determines whether it is in OSO and another function intoOSO that takes a sandwich and returns the sandwich with the same ingredients ordered in OSO.

   def inOSO(s: Sandwich): Boolean 
   def intoOSO(s: Sandwich)(defaultbread: Bread): Sandwich 
   

4. Assuming that the price for a sandwich is the sum of the prices of the individual ingredients, define a Scala function priceSandwich that takes a sandwich and returns its price. You may use the price "database" prices given below.

   def priceSandwich(s: Sandwich): Int 
   
   val prices = List( 
       (White,20),(Wheat,30),(Rye,30), 
       (Turkey,100),(Chicken,80),(Ham,120),(RoastBeef,140),(Tofu,50), 
       (American,50),(Swiss,60),(Jack,60),(Cheddar,60),
       (Tomato,25),(Onion,20),(Lettuce,20),(BellPepper,25),
       (Mayo,5),(Mustard,4),(Ketchup,4),(Relish,10),(Tabasco,5) 
     )
   

5. Define a Scala function eqSandwich that compares two sandwiches for equality. (What does equality mean for sandwiches?)

   def eqSandwich(sl: Sandwich)(sr: Sandwich): Boolean
   

Compiling the Program for the SueChef Controller

In this section, we look at compiling the Platter and Sandwich descriptions to issue a sequence of commands for the SueChef's controller.

The SueChef supports the special instructions that can be issued in sequence to its controller. The algebraic data type SandwichOp below represents the instructions.

    sealed trait SandwichOp
    case object StartSandwich extends SandwichOp
    case object FinishSandwich extends SandwichOp
    case class  AddBread(bread: Bread) extends SandwichOp
    case class  AddMeat(meat: Meat) extends SandwichOp
    case class  AddCheese(cheese: Cheese) extends SandwichOp
    case class  AddVegetable(vegetable: Vegetable) extends SandwichOp
    case class  AddCondiment(condiment: Condiment) extends SandwichOp
    case object StartPlatter extends SandwichOp
    case object MoveToPlatter extends SandwichOp
    case object FinishPlatter extends SandwichOp

We also define the type Program to represent the sequence of commands resulting from compilation of a Sandwich or Platter specification.

    case class Program(program: List[SandwichOp])

The flow of a program is given by the following pseudocode:

    StartPlatter
    for each sandwich needed
        StartSandwich
        for each ingredient needed
            Add ingredient on top
        FinishSandwich
        MoveToPlatter
    FinishPlatter

Consider a sandwich defined as follows:

    Sandwich(List(Bread Rye,Condiment Mayo,Cheese Swiss,
              Meat Ham,Bread Rye))

The corresponding sequence of SueChef commands would be the following.

    List(StartSandwich,AddBread Rye,AddMeat Ham,AddCheeseSwiss,
     AddCondiment Mayo,AddBread Rye,FinishSandwich,MoveToPlatter)

Exercise Set 2

1. Define a Scala function compileSandwich to convert a sandwich specification into the sequence of SueChef commands to assemble the sandwich.

   def compileSandwich(s: Sandwich): List[SandwichOp]
   

2. Define a Scala function compile to convert a platter specification into the sequence of SueChef commands to assemble the sandwiches on the platter.

   def compile(p: Platter): Program 
   

UP to CSci 555 Lecture Notes root document?