The Expression Problem can be summarized into three ideas:
The goal is to define a data type by cases, where
- one can add new cases to the data type and
- (one can add) new functions over the data type,
- without recompiling existing code, and
- while retaining static type safety.
|Pre-existing compiled function||Function is added|
|Pre-existing compiled data type||All languages||FP: Add a function in a new file|
|Data type is added||FP: ???|
OO: Add a subclass in a new file
^^ This cannot be defined until the corresponding FP/OO issue (marked as
???) is resolved
The paper, Data Types à la carte, synthesized a number of known-at-the-time-of-writing ideas into a solution to the Expression problem by figuring out a way to compose complicated data types. When they applied their findings to the
Free monad, they found that they could "run" multiple monads inside of one monad.
This folder is a summmary and commentary on the paper linked above. It is meant to be read alongside of or after you read the paper. While you, the reader, could just read the paper and ignore the rest of this folder's contents, there are some advantages to reading through this folder's contents alongside of the paper:
- Sometimes, the above paper will state that something is true, but not show why. This folder will explore that more and show why it's true.
- Sometimes, the paper may use unfamiliar terminology or use symbolic data types. This folder will explain the terminology and use alphabetical names to refer to some data types.
- The last file in this folder (i.e.
Embedded Compilers.md) explains one of the key features one obtains by using the
Rather than follow the paper exactly, this folder will define and solve a simpler version of the Expression Problem to demonstrate the basic idea of the solution. With that foundation, the paper's real problem will be explored and solved.
In addition, the paper explains how to write a
show function that pretty prints the mathetmatical expression. This folder's contents will not overview that part of the paper. The full reasons will be explained when we get to that part.
The paper above has 8 sections:
- Introduction (what is the expression problem and an example of it?)
- Fixing the Expression Problem (how do we compose data types?)
- Evaluation (how do we evaluate composed data types?)
- Automating Injections (how do we reduce boilerplate when working with composed data types?)
- Examples (Provide a full example of a solution to our problem)
- Monads for Free (Why is this relevant to Free monads?)
- Applications (Using this approach to define extensible effects by composing Free monads)
This folder has 8 files:
- Seeing and Solving a Simple Problem
- Reducing boilerplate via Either
- Seeing and Solving a Harder Problem
- Writing the Evaluate Function
- Writing the Show function (optional)
- From Expression to Free
- Defining Modular Monads
- Embedded Compilers
|This Folder||General Idea||Corresponding Paper section||General idea|
|1 (File)||Prep work: Defining and solving a simple version of the problem by composing data types||Sections 1/2/3/5 (ish)||Laying a foundation|
|2 (File)||Prep work: Abstract data type composition via ||Section 4 (ish)||Laying a foundation|
|3 (File)||Showing why the paper's problem is hard to solve, but still solvable; reveal ||Sections 1/2/4/5 (ish)||-|
|4 (File)||-||Sections 3/5||Writing the |
|5 (File)||Optional reading||Sections 3/5||Writing the |
|6 (Folder)||Show that ||Section 6||-|
|7 (File)||Using 'languages' to model effects||Section 6||Simulating the State monad|
|8 File||Defining abstract syntax trees via ||Sections 6/7||Its relevance to and application for |