\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 658: Software Language Engineering Sandwich DSL Case Study (Haskell)},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace 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}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 658: Software Language Engineering\\
Sandwich DSL Case Study (Haskell)}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{3 March 2018}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2013, 2014, 2016, 2017, 2018,
\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 March
2018 is a recent version of Firefox from Mozilla.

TODO:

\begin{itemize}
\tightlist
\item
  (For Haskell book) Integrate into existing or new chapter
\item
  Add additional exercises (e.g., construction of a Menu of named
  sandwiches).
\end{itemize}

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

\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 Haskell
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 Haskell data type
\texttt{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.} We derive \texttt{Show} so we can display
sandwiches.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Sandwich} \FunctionTok{=} \DataTypeTok{Sandwich}\NormalTok{ [}\DataTypeTok{Layer}\NormalTok{]}
                    \KeywordTok{deriving} \DataTypeTok{Show}
\end{Highlighting}
\end{Shaded}

Note: In this case study, we use the same name for an algebraic data
type and its only constructor. Above the \texttt{Sandwich} after
\texttt{data} defines a type and the one after the ``\texttt{=}''
defines the single constructor for that type.

Data type \texttt{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 \texttt{Sandwich} data type does not require there to be
a bread in the stack of ingredients. However, we add function
\texttt{newSandwich} that starts a sandwich with a bread at the bottom
and a function \texttt{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}[]
\OtherTok{    newSandwich ::} \DataTypeTok{Bread} \OtherTok{->} \DataTypeTok{Sandwich}
\OtherTok{    addLayer    ::} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{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 \texttt{Layer} represents a single
ingredient. Note that we use names such as \texttt{Bread} both as a
constructor of the \texttt{Layer} type and the type of the ingredients
within that category.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Layer}     \FunctionTok{=} \DataTypeTok{Bread} \DataTypeTok{Bread}         \FunctionTok{|} \DataTypeTok{Meat} \DataTypeTok{Meat}
                   \FunctionTok{|} \DataTypeTok{Cheese} \DataTypeTok{Cheese}       \FunctionTok{|} \DataTypeTok{Vegetable} \DataTypeTok{Vegetable}
                   \FunctionTok{|} \DataTypeTok{Condiment} \DataTypeTok{Condiment}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{,}\DataTypeTok{Show}\NormalTok{)}

    \KeywordTok{data} \DataTypeTok{Bread}     \FunctionTok{=} \DataTypeTok{White} \FunctionTok{|} \DataTypeTok{Wheat} \FunctionTok{|} \DataTypeTok{Rye}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}

    \KeywordTok{data} \DataTypeTok{Meat}      \FunctionTok{=} \DataTypeTok{Turkey} \FunctionTok{|} \DataTypeTok{Chicken} \FunctionTok{|} \DataTypeTok{Ham} \FunctionTok{|} \DataTypeTok{RoastBeef} \FunctionTok{|} \DataTypeTok{Tofu}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}

    \KeywordTok{data} \DataTypeTok{Cheese}    \FunctionTok{=} \DataTypeTok{American} \FunctionTok{|} \DataTypeTok{Swiss} \FunctionTok{|} \DataTypeTok{Jack} \FunctionTok{|} \DataTypeTok{Cheddar}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}

    \KeywordTok{data} \DataTypeTok{Vegetable} \FunctionTok{=} \DataTypeTok{Tomato} \FunctionTok{|} \DataTypeTok{Onion} \FunctionTok{|} \DataTypeTok{Lettuce} \FunctionTok{|} \DataTypeTok{BellPepper}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}

    \KeywordTok{data} \DataTypeTok{Condiment} \FunctionTok{=} \DataTypeTok{Mayo} \FunctionTok{|} \DataTypeTok{Mustard} \FunctionTok{|} \DataTypeTok{Ketchup} \FunctionTok{|} \DataTypeTok{Relish} \FunctionTok{|} \DataTypeTok{Tabasco}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

We need to be able to compare ingredients for equality and convert them
to strings. Because the automatically generated default definitions are
appropriate, we derive both classes \texttt{Show} and \texttt{Eq} for
these ingredient types.

We do not derive \texttt{Eq} for \texttt{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 \texttt{Platter} to wrap a list of
sandwiches.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data}  \DataTypeTok{Platter} \FunctionTok{=} \DataTypeTok{Platter}\NormalTok{ [}\DataTypeTok{Sandwich}\NormalTok{] }
                    \KeywordTok{deriving} \DataTypeTok{Show}
\end{Highlighting}
\end{Shaded}

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

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    newPlatter  ::} \DataTypeTok{Platter} 
\OtherTok{    addSandwich ::} \DataTypeTok{Platter} \OtherTok{->} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Platter} 
\end{Highlighting}
\end{Shaded}

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

Please put these functions in a Haskell module \texttt{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 Haskell functions \texttt{newSandwich},
  \texttt{addLayer}, \texttt{newPlatter}, and \texttt{addSandwich}
  described above.
\item
  Define and implement the Haskell query functions below that take an
  ingredient (i.e., \texttt{Layer}) and return \texttt{True} if and only
  if the ingredient is in the specified category.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    isBread     ::} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isMeat      ::} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isCheese    ::} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isVegetable ::} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isCondiment ::} \DataTypeTok{Layer} \OtherTok{->} \DataTypeTok{Bool}
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Haskell function \texttt{noMeat} that takes a
  sandwich and returns \texttt{True} if and only if the sandwich
  contains no meats.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    noMeat ::} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Bool}
\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 Haskell function \texttt{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}[]
\OtherTok{    inOSO   ::} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    intoOSO ::} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Bread} \OtherTok{->} \DataTypeTok{Sandwich}
\end{Highlighting}
\end{Shaded}

  Hint: Remember Prelude functions like \texttt{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
  Suppose we store the current prices of the sandwich ingredients in an
  association list with the following type synonym:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{type} \DataTypeTok{PriceList} \FunctionTok{=}\NormalTok{ [(}\DataTypeTok{Layer}\NormalTok{,}\DataTypeTok{Int}\NormalTok{)]}
\end{Highlighting}
\end{Shaded}

  Assuming that the price for a sandwich is base price plus the sum of
  the prices of the individual ingredients, define and implement a
  Haskell function \texttt{priceSandwich} that takes a price list, a
  base price, and a sandwich and returns the price of the sandwich.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    priceSandwich ::} \DataTypeTok{PriceList} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Int} 
\end{Highlighting}
\end{Shaded}

  Hint: Consider using the \texttt{lookup} function from the Prelude.
  The library \texttt{Data.Maybe} may also include helpful functions.

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

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    prices }\FunctionTok{=}\NormalTok{ [ (}\DataTypeTok{Bread} \DataTypeTok{White}\NormalTok{, }\DecValTok{20}\NormalTok{), (}\DataTypeTok{Bread} \DataTypeTok{Wheat}\NormalTok{, }\DecValTok{30}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Bread} \DataTypeTok{Rye}\NormalTok{, }\DecValTok{30}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Meat} \DataTypeTok{Turkey}\NormalTok{, }\DecValTok{100}\NormalTok{), (}\DataTypeTok{Meat} \DataTypeTok{Chicken}\NormalTok{, }\DecValTok{80}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Meat} \DataTypeTok{Ham}\NormalTok{, }\DecValTok{120}\NormalTok{), (}\DataTypeTok{Meat} \DataTypeTok{RoastBeef}\NormalTok{, }\DecValTok{140}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Meat} \DataTypeTok{Tofu}\NormalTok{, }\DecValTok{50}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Cheese} \DataTypeTok{American}\NormalTok{, }\DecValTok{50}\NormalTok{), (}\DataTypeTok{Cheese} \DataTypeTok{Swiss}\NormalTok{, }\DecValTok{60}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Cheese} \DataTypeTok{Jack}\NormalTok{, }\DecValTok{60}\NormalTok{), (}\DataTypeTok{Cheese} \DataTypeTok{Cheddar}\NormalTok{, }\DecValTok{60}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Vegetable} \DataTypeTok{Tomato}\NormalTok{, }\DecValTok{25}\NormalTok{), (}\DataTypeTok{Vegetable} \DataTypeTok{Onion}\NormalTok{, }\DecValTok{20}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Vegetable} \DataTypeTok{Lettuce}\NormalTok{, }\DecValTok{20}\NormalTok{), (}\DataTypeTok{Vegetable} \DataTypeTok{BellPepper}\NormalTok{,}\DecValTok{25}\NormalTok{),}
\NormalTok{               (}\DataTypeTok{Condiment} \DataTypeTok{Mayo}\NormalTok{, }\DecValTok{5}\NormalTok{), (}\DataTypeTok{Condiment} \DataTypeTok{Mustard}\NormalTok{, }\DecValTok{4}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Condiment} \DataTypeTok{Ketchup}\NormalTok{, }\DecValTok{4}\NormalTok{), (}\DataTypeTok{Condiment} \DataTypeTok{Relish}\NormalTok{, }\DecValTok{10}\NormalTok{), }
\NormalTok{               (}\DataTypeTok{Condiment} \DataTypeTok{Tabasco}\NormalTok{, }\DecValTok{5}\NormalTok{) }
\NormalTok{             ]}
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Haskell function \texttt{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}[]
\OtherTok{    eqSandwich ::} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Sandwich} \OtherTok{->} \DataTypeTok{Bool} 
\end{Highlighting}
\end{Shaded}

  Hint: The ``sets'' operations in library \texttt{Data.List} might be
  helpful
\item
  Give the Haskell declaration needed to make \texttt{Sandwich} an
  instance of class \texttt{Eq}. You may use \texttt{eqSandwich} if
  applicable.
\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 \texttt{Platter} and
\texttt{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 data type \texttt{SandwichOp} below
represents the instructions.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{SandwichOp} \FunctionTok{=} \DataTypeTok{StartSandwich}    \FunctionTok{|} \DataTypeTok{FinishSandwich} 
                    \FunctionTok{|} \DataTypeTok{AddBread} \DataTypeTok{Bread}   \FunctionTok{|} \DataTypeTok{AddMeat} \DataTypeTok{Meat}
                    \FunctionTok{|} \DataTypeTok{AddCheese} \DataTypeTok{Cheese} \FunctionTok{|} \DataTypeTok{AddVegetable} \DataTypeTok{Vegetable}
                    \FunctionTok{|} \DataTypeTok{AddCondiment} \DataTypeTok{Condiment}
                    \FunctionTok{|} \DataTypeTok{StartPlatter} \FunctionTok{|} \DataTypeTok{MoveToPlatter} \FunctionTok{|} \DataTypeTok{FinishPlatter} 
                      \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Show}\NormalTok{) }
\end{Highlighting}
\end{Shaded}

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

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Program} \FunctionTok{=} \DataTypeTok{Program}\NormalTok{ [}\DataTypeTok{SandwichOp}\NormalTok{]}
                   \KeywordTok{deriving} \DataTypeTok{Show}
\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}[]
    \DataTypeTok{Sandwich}\NormalTok{ [ }\DataTypeTok{Bread} \DataTypeTok{Rye}\NormalTok{, }\DataTypeTok{Condiment} \DataTypeTok{Mayo}\NormalTok{, }\DataTypeTok{Cheese} \DataTypeTok{Swiss}\NormalTok{,}
               \DataTypeTok{Meat} \DataTypeTok{Ham}\NormalTok{, }\DataTypeTok{Bread} \DataTypeTok{Rye}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}

The corresponding sequence of SueChef commands would be the following:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ }\DataTypeTok{StartSandwich}\NormalTok{, }\DataTypeTok{AddBread} \DataTypeTok{Rye}\NormalTok{, }\DataTypeTok{AddMeat} \DataTypeTok{Ham}\NormalTok{, }\DataTypeTok{AddCheese} \DataTypeTok{Swiss}\NormalTok{,}
      \DataTypeTok{AddCondiment} \DataTypeTok{Mayo}\NormalTok{, }\DataTypeTok{AddBread} \DataTypeTok{Rye}\NormalTok{, }\DataTypeTok{FinishSandwich}\NormalTok{, }\DataTypeTok{MoveToPlatter}\NormalTok{ ]}
\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 Haskell function \texttt{compileSandwich} to
  convert a sandwich specification into the sequence of SueChef commands
  to assemble the sandwich.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    compileSandwich ::} \DataTypeTok{Sandwich} \OtherTok{->}\NormalTok{ [}\DataTypeTok{SandwichOp}\NormalTok{]}
\end{Highlighting}
\end{Shaded}
\item
  Define and implement a Haskell function \texttt{compile} to convert a
  platter specification into the sequence of SueChef commands to
  assemble the sandwiches on the platter.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    compile ::} \DataTypeTok{Platter} \OtherTok{->} \DataTypeTok{Program} 
\end{Highlighting}
\end{Shaded}
\end{enumerate}

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

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

\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 Spring 2018, I updated the Haskell case study
to be more compatible with the other CSci 658 course materials.

In Spring 2018, I also recreated a separate Scala-based version of this
case study by combining aspects of this document with the Scala-based
version from Spring 2016.

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}