% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={CSci 555: Functional Programming Sandwich DSL Case Study (Scala)},
  pdfauthor={H. Conrad Cunningham},
  hidelinks,
  pdfcreator={LaTeX via pandoc}}
\urlstyle{same} % disable monospaced font for URLs
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 555: Functional Programming\\
Sandwich DSL Case Study (Scala)}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{14 May 2019}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2018, 2019, \href{http://www.cs.olemiss.edu/~hcc}{H.
Conrad Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Advisory}: The HTML version of this document requires use of a
browser that supports the display of MathML. A good choice as of April
2019 is a recent version of Firefox from Mozilla.

\hypertarget{sandwich-dsl-case-study-scala}{%
\section{Sandwich DSL Case Study
(Scala)}\label{sandwich-dsl-case-study-scala}}

\hypertarget{introduction}{%
\subsection{Introduction}\label{introduction}}

Few computer science graduates will design and implement a
general-purpose programming language during their careers. However, many
graduates will design and implement---and all likely will
use---special-purpose languages in their work.

These special-purpose languages are often called \emph{domain-specific
languages} (or DSLs). For more discussion of DSL concepts and
terminology, see the accompanying notes on
\href{../../DomainSpecificLanguages.html}{Domain-Specific Languages}.

In this case study, we design and implement a simple \emph{internal
DSL}. This DSL describes simple ``programs'' using a set of Scala
algebraic data types. We express a program as an \emph{abstract syntax
tree} using the DSLs data types.

The case study first builds a package of functions for creating and
manipulating the abstract syntax trees. It then extends the package to
translate the abstract syntax trees to a sequence of instructions for a
simple ``machine''.

\hypertarget{building-the-dsl}{%
\subsection{Building the DSL}\label{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:

\begin{itemize}
\item
  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.)
\item
  Each sandwich consists of layers of ingredients.
\item
  The categories of ingredients are breads, meats, cheeses, vegetables,
  and condiments.
\item
  Available breads are white, wheat, and rye.
\item
  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.)
\item
  Available cheeses are American, Swiss, jack, and cheddar.
\item
  Available vegetables are tomato, lettuce, onion, and bell pepper.
\item
  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.)
\end{itemize}

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

What is a sandwich? \ldots{} Basically, it is a stack of ingredients.

Should we require the sandwich to have a bread on the bottom? \ldots{}
Probably. \ldots{} On the top? Maybe not, to allow ``open-faced''
sandwiches. \ldots{} What can the SueChef build? \ldots{} 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
\VERB|\NormalTok{Sandwich}| to model sandwiches. It wraps a possibly
empty list of ingredient layers. \emph{We assume the head of the list to
be the layer at the top of the sandwich.}

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case} \KeywordTok{class} \FunctionTok{Sandwich}\NormalTok{(sandwich: List[Layer])}
\end{Highlighting}
\end{Shaded}

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

Data type \VERB|\NormalTok{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 \VERB|\NormalTok{Sandwich}| data type does not require
there to be a bread in the stack of ingredients. However, we add
function \VERB|\NormalTok{newSandwich}| that starts a sandwich with a
bread at the bottom and a function \VERB|\NormalTok{addLayer}| that adds
a new ingredient to the top of the sandwich. We leave the implementation
of these functions as exercises.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{newSandwich}\NormalTok{(b: Bread): Sandwich}
    \KeywordTok{def} \FunctionTok{addLayer}\NormalTok{(s: Sandwich)(x: Layer): Sandwich }
\end{Highlighting}
\end{Shaded}

Ingredients are in one of five categories: breads, meats, cheeses,
vegetables, and condiments.

Because both the categories and the specific type of ingredient are
important, we choose to represent both in the type structures and define
the following types. A value of type \VERB|\NormalTok{Layer}| represents
a single ingredient. Type \VERB|\NormalTok{Layer}| has five variants
(subtypes) \VERB|\NormalTok{Bread}|, \VERB|\NormalTok{Meat}|,
\VERB|\NormalTok{Cheese}|, \VERB|\NormalTok{Vegetable}|, and
\VERB|\NormalTok{Condiment}|. Each of these variants itself has several
variants. For example, \VERB|\NormalTok{Bread}| has variants (subtypes)
\VERB|\NormalTok{White}|, \VERB|\NormalTok{Wheat}|, and
\VERB|\NormalTok{Rye}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Layer}

    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Bread     }\KeywordTok{extends}\NormalTok{ Layer}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ White      }\KeywordTok{extends}\NormalTok{ Bread}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Wheat      }\KeywordTok{extends}\NormalTok{ Bread}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Rye        }\KeywordTok{extends}\NormalTok{ Bread}

    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Meat      }\KeywordTok{extends}\NormalTok{ Layer}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Turkey     }\KeywordTok{extends}\NormalTok{ Meat}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Chicken    }\KeywordTok{extends}\NormalTok{ Meat}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Ham        }\KeywordTok{extends}\NormalTok{ Meat}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ RoastBeef  }\KeywordTok{extends}\NormalTok{ Meat}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Tofu       }\KeywordTok{extends}\NormalTok{ Meat}

    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Cheese    }\KeywordTok{extends}\NormalTok{ Layer}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ American   }\KeywordTok{extends}\NormalTok{ Cheese}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Swiss      }\KeywordTok{extends}\NormalTok{ Cheese}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Jack       }\KeywordTok{extends}\NormalTok{ Cheese}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Cheddar    }\KeywordTok{extends}\NormalTok{ Cheese}

    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Vegetable }\KeywordTok{extends}\NormalTok{ Layer}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Tomato     }\KeywordTok{extends}\NormalTok{ Vegetable}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Onion      }\KeywordTok{extends}\NormalTok{ Vegetable}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Lettuce    }\KeywordTok{extends}\NormalTok{ Vegetable}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ BellPepper }\KeywordTok{extends}\NormalTok{ Vegetable}

    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Condiment }\KeywordTok{extends}\NormalTok{ Layer}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Mayo       }\KeywordTok{extends}\NormalTok{ Condiment}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Mustard    }\KeywordTok{extends}\NormalTok{ Condiment}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Ketchup    }\KeywordTok{extends}\NormalTok{ Condiment}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Relish     }\KeywordTok{extends}\NormalTok{ Condiment}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Tabasco    }\KeywordTok{extends}\NormalTok{ Condiment}
\end{Highlighting}
\end{Shaded}

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
\VERB|\NormalTok{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 \VERB|\NormalTok{Platter}| to wrap
a list of sandwiches.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case} \KeywordTok{class} \FunctionTok{Platter}\NormalTok{(platter: List[Sandwich])}
\end{Highlighting}
\end{Shaded}

We also define functions \VERB|\NormalTok{newPlatter}| to create a new
\VERB|\NormalTok{Platter}| and \VERB|\NormalTok{addSandwich}| to add a
sandwich to the \VERB|\NormalTok{Platter}|. We leave the implementation
of these functions as exercises.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ newPlatter: Platter}
    \KeywordTok{def} \FunctionTok{addSandwich}\NormalTok{(p: Platter)(s: Sandwich): Platter}
\end{Highlighting}
\end{Shaded}

\hypertarget{exercise-set-a}{%
\subsection{Exercise Set A}\label{exercise-set-a}}

Please put these functions in a Scala module
\VERB|\NormalTok{SandwichDSL}|. You may use functions defined earlier in
the exercises to implement those later in the exercises.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Define and implement the Scala functions
  \VERB|\NormalTok{newSandwich}|, \VERB|\NormalTok{addLayer}|,
  \VERB|\NormalTok{newPlatter}|, and \VERB|\NormalTok{addSandwich}|
  described above.
\item
  Define and implement the Scala query functions below that take an
  ingredient (i.e.~\VERB|\NormalTok{Layer}|) and return
  \VERB|\KeywordTok{true}| if and only if the ingredient is in the
  specified category.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{isBread}\NormalTok{(x: Layer): Boolean }
    \KeywordTok{def} \FunctionTok{isMeat}\NormalTok{(x: Layer): Boolean}
    \KeywordTok{def} \FunctionTok{isCheese}\NormalTok{(x: Layer): Boolean }
    \KeywordTok{def} \FunctionTok{isVegetable}\NormalTok{(x: Layer): Boolean }
    \KeywordTok{def} \FunctionTok{isCondiment}\NormalTok{(x: Layer): Boolean}
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Scala function \VERB|\NormalTok{noMeat}| that
  takes a sandwich and returns \VERB|\KeywordTok{true}| if and only if
  the sandwich contains no meats.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    def noMeat(x}\OperatorTok{:} \DataTypeTok{Sandwich}\NormalTok{)}\OperatorTok{:} \DataTypeTok{Boolean}
\end{Highlighting}
\end{Shaded}
\item
  According to a proposed City of Oxford ordinance, in the future it may
  be necessary to assemble all sandwiches in \emph{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 and implement a Scala function \VERB|\NormalTok{inOSO}| that
  takes a sandwich and determines whether it is in OSO and another
  function \texttt{intoOSO} that takes a sandwich and a default bread
  and returns the sandwich with the same ingredients ordered in OSO.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{inOSO}\NormalTok{(s: Sandwich): Boolean }
    \KeywordTok{def} \FunctionTok{intoOSO}\NormalTok{(s: Sandwich)(defaultbread: Bread): Sandwich }
\end{Highlighting}
\end{Shaded}

  Hint: Remember library functions like \VERB|\NormalTok{dropWhile}|.

  Note: It is impossible to rearrange the layers into OSO if the
  sandwich does not include exactly two breads of the same type. If the
  sandwich does not include any breads, then the default bread type
  (second argument) should be specified for both. If there is at least
  one bread, then the bread type nearest the \emph{bottom} can be chosen
  for both top and bottom.
\item
  Assuming that the price for a sandwich is the base price plus the sum
  of the prices of the individual ingredients, define and implement a
  Scala function \VERB|\NormalTok{priceSandwich}| that takes a price
  list, a base price, and a sandwich and returns the price of the
  sandwich.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{priceSandwich}\NormalTok{(pl: List[(Layer,Int)], base: Int)(s: Sandwich): Int }
\end{Highlighting}
\end{Shaded}

  Use the following price list as a part of your testing:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ prices = List( }
\NormalTok{        (White,}\DecValTok{20}\NormalTok{),(Wheat,}\DecValTok{30}\NormalTok{),(Rye,}\DecValTok{30}\NormalTok{), }
\NormalTok{        (Turkey,}\DecValTok{100}\NormalTok{),(Chicken,}\DecValTok{80}\NormalTok{),(Ham,}\DecValTok{120}\NormalTok{),(RoastBeef,}\DecValTok{140}\NormalTok{),(Tofu,}\DecValTok{50}\NormalTok{), }
\NormalTok{        (American,}\DecValTok{50}\NormalTok{),(Swiss,}\DecValTok{60}\NormalTok{),(Jack,}\DecValTok{60}\NormalTok{),(Cheddar,}\DecValTok{60}\NormalTok{), }
\NormalTok{        (Tomato,}\DecValTok{25}\NormalTok{),(Onion,}\DecValTok{20}\NormalTok{),(Lettuce,}\DecValTok{20}\NormalTok{),(BellPepper,}\DecValTok{25}\NormalTok{), }
\NormalTok{        (Mayo,}\DecValTok{5}\NormalTok{),(Mustard,}\DecValTok{4}\NormalTok{),(Ketchup,}\DecValTok{4}\NormalTok{),(Relish,}\DecValTok{10}\NormalTok{),(Tabasco,}\DecValTok{5}\NormalTok{) }
\NormalTok{      ) }
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Scala function \VERB|\NormalTok{eqSandwich}|
  that compares two sandwiches for equality.

  What does equality mean for sandwiches? Although the definition of
  equality could differ, you can use ``bag equality''. That is, two
  sandwiches are equal if they have the same number of layers (zero or
  more) of each ingredient, regardless of the order of the layers.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{eqSandwich}\NormalTok{(sl: Sandwich)(sr: Sandwich): Boolean}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

\hypertarget{compiling-the-program-for-the-suechef-controller}{%
\subsection{Compiling the Program for the SueChef
Controller}\label{compiling-the-program-for-the-suechef-controller}}

In this section, we look at compiling the \VERB|\NormalTok{Platter}| and
\VERB|\NormalTok{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
\VERB|\NormalTok{SandwichOp}| below represents the instructions.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ StartSandwich }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ FinishSandwich }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{class}  \FunctionTok{AddBread}\NormalTok{(bread: Bread) }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{class}  \FunctionTok{AddMeat}\NormalTok{(meat: Meat) }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{class}  \FunctionTok{AddCheese}\NormalTok{(cheese: Cheese) }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{class}  \FunctionTok{AddVegetable}\NormalTok{(vegetable: Vegetable) }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{class}  \FunctionTok{AddCondiment}\NormalTok{(condiment: Condiment) }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ StartPlatter }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ MoveToPlatter }\KeywordTok{extends}\NormalTok{ SandwichOp}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ FinishPlatter }\KeywordTok{extends}\NormalTok{ SandwichOp}
\end{Highlighting}
\end{Shaded}

Note: You may find the builtin Scala methods
\VERB|\NormalTok{isInstanceOf}| and \VERB|\NormalTok{asInstanceOf}|
helpful for use of the above.

We also define the type \VERB|\NormalTok{Program}| to represent the
sequence of commands resulting from compilation of a
\VERB|\NormalTok{Sandwich}| or \VERB|\NormalTok{Platter}| specification.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case} \KeywordTok{class} \FunctionTok{Program}\NormalTok{(program: List[SandwichOp])}
\end{Highlighting}
\end{Shaded}

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

\begin{verbatim}
    StartPlatter
    for each sandwich needed
        StartSandwich
        for each ingredient needed
            Add ingredient on top
            FinishSandwich
            MoveToPlatter
    FinishPlatter
\end{verbatim}

Consider a sandwich defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{Sandwich}\NormalTok{(List(Rye,Mayo,Swiss,Ham,Rye))}
\end{Highlighting}
\end{Shaded}

The corresponding sequence of SueChef commands would be the following.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    List(StartSandwich,}\FunctionTok{AddBread}\NormalTok{(Rye),}\FunctionTok{AddMeat}\NormalTok{(Ham),}\FunctionTok{AddCheese}\NormalTok{(Swiss),}
         \FunctionTok{AddCondiment}\NormalTok{(Mayo),}\FunctionTok{AddBread}\NormalTok{(Rye),FinishSandwich,MoveToPlatter)}
\end{Highlighting}
\end{Shaded}

\hypertarget{exercise-set-b}{%
\subsection{Exercise Set B}\label{exercise-set-b}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Define and implement a Scala function
  \VERB|\NormalTok{compileSandwich}| to convert a sandwich specification
  into the sequence of SueChef commands to assemble the sandwich.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{compileSandwich}\NormalTok{(s: Sandwich): List[SandwichOp]}
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Scala function \VERB|\NormalTok{compile}| to
  convert a platter specification into the sequence of SueChef commands
  to assemble the sandwiches on the platter.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{compile}\NormalTok{(p: Platter): Program }
\end{Highlighting}
\end{Shaded}
\end{enumerate}

\hypertarget{source-code}{%
\subsection{Source Code}\label{source-code}}

The Scala source code for this case study is in file
\href{SandwichDSL_base.scala}{\texttt{SandwichDSL\_base.scala}}.

\hypertarget{acknowledgements}{%
\subsection{Acknowledgements}\label{acknowledgements}}

I devised the first version of the Sandwich DSL problem for a question
on a take-exam in the Lua-based, Fall 2013 offering of CSci 658
(Software Language Engineering). I subsequently developed a full
Haskell-based case study for the Fall 2014 offering of CSci 450
(Organization of Programming Languages). I then converted the case study
to use Scala for the Spring 2016 offering of CSci 555 (Functional
Programming).

In Spring and Fall 2017, I converted case study document from HTML to
Pandoc Markdown and updated it for use in the Haskell-based, Fall 2017
offering of CSci 450. In Fall 2018, I updated the Haskell case study to
be more compatible with the ELIFP textbook materials.

In Spring 2018, I recreated this separate Scala-based version of the
case study by combining aspects of Haskell-based version with the
Scala-based version from Spring 2016. In Spring 2019, I further updated
the materials to use the current approach to formatting.

I maintain these notes as text in Pandoc's dialect of Markdown using
embedded LaTeX markup for the mathematical formulas and then translate
the notes to HTML, PDF, and other forms as needed. The HTML version of
this document may require use of a browser that supports the display of
MathML.

\hypertarget{references}{%
\subsection{References}\label{references}}

TODO

\hypertarget{concepts}{%
\subsection{Concepts}\label{concepts}}

TODO

\end{document}