## Monday, May 18, 2015

### The internet of code

In this post I will introduce a proof-of-concept implementation for distributing typed code over the internet where the unit of compilation is individual expressions.

#### The core language

To motivate this post, consider this Haskell code:

``````data Bool = True | False

and :: Bool -> Bool -> Bool
and b1 b2 = if b1 then b2 else False

or :: Bool -> Bool -> Bool
or b1 b2 = if b1 then True else b2

data Even = Zero | SuccE Odd

data Odd = SuccO Even

four :: Even
four = SuccE (SuccO (SuccE (SuccO Zero)))

doubleEven :: Even -> Even
doubleEven (SuccE o) = SuccE (SuccO (doubleOdd o)
doubleEven  Zero     = Zero

doubleOdd :: Odd -> Even
doubleOdd (SuccO e) = SuccE (SuccO (doubleEven e)``````

I will encode each one of the above types, terms, and constructors as separate, closed, non-recursive expressions in the calculus of constructions. You can think of the calculus of constructions as a typed assembly language for functional programs which we will use to distribute program fragments over the internet. You can learn more about the calculus of constructions and other pure type systems by reading this clear paper by Simon Peyton Jones: "Henk: a typed intermediate language".

For example, here is how you encode the `True` constructor in the calculus of constructions:

``λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True``

Note that the entire expression is the `True` constructor, not just the right-hand side:

``````             This is the True constructor
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True
^^^^
Not this``````

I just chose the variable names so that you can tell at a glance what constructor you are looking at from the right-hand side of the expression.

Similarly, here is how you encode the type `Bool` in the calculus of constructions:

``````               This is the `Bool` type
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool
^^^^
Not this``````

Again, the entire expression is the `Bool` type, but I chose the variable names so that you can tell which type you are looking at from the right-hand side.

You can learn more about the full set of rules for translating data types to System F (a subset of the calculus of constructions) by reading the paper: "Automatic synthesis of typed Λ-programs on term algebras". Also, I will soon release a compiler named `annah` that automates this translation algorithm, and I used this compiler to translate the above Haskell code to the equivalent expressions in the calculus of constructions.

#### Distribution

We can distribute these expressions by hosting each expression as text source code on the internet. For example, I encoded all of the above types, terms and constructors in the calculus of constructions and hosted them using a static web server. You can browse these expressions by visiting sigil.place/post/0/.

Click on one of the expressions in the directory listing to see how they are encoded in the calculus of constructions. For example, if you click the link to `four` you will find an ordinary text file whose contents look like this (formatted for clarity):

``````  λ(Even : *)                        -- This entire
→ λ(Odd : *)                         -- expression is
→ λ(Zero : Even)                     -- the number `four`
→ λ(SuccE : ∀(pred : Odd) → Even)    --
→ λ(SuccO : ∀(pred : Even) → Odd)    --
→ SuccE (SuccO (SuccE (SuccO Zero))) -- Not just this last line``````

Each one of these expressions gets a unique URL, and we can embed any expression in our code by referencing the appropriate URL.

#### Remote imports

We can use the `morte` compiler to download, parse, and super-optimize programs written in the calculus of constructions. The morte compiler reads in a program from standard input, outputs the program's type to standard error, then super-optimizes the program and outputs the optimized program to standard output.

For example, we can compute `and True False` at compile time by just replacing `and`, `True`, and `False` by their appropriate URLs:

``````\$ cabal install 'morte >= 1.2'
\$ morte
#http://sigil.place/post/0/and
#http://sigil.place/post/0/True
#http://sigil.place/post/0/False``````

When we hit `<Ctrl-D>` to signal end of standard input then `morte` will compile the program:

``````\$ morte
#http://sigil.place/post/0/and
#http://sigil.place/post/0/True
#http://sigil.place/post/0/False
<Ctrl-D>
∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False``````

The program's type is `Bool` and `morte` optimizes away the program to `False` at compile time. Both the type (`Bool`) and the value (`False`) are encoded in the calculus of constructions.

Here we are using `morte` as a compile-time calculator, mainly because Morte does not yet compile to a backend language. When I release a backend language I will go into more detail about how to embed expressions to evaluate at runtime instead of compile time.

#### Local imports

We can shorten this example further because `morte` also lets you import expressions from local files using the same hashtag syntax. For example, we can create local files that wrap remote URLs like this:

``````\$ echo "#http://sigil.place/post/0/Bool"  > Bool
\$ echo "#http://sigil.place/post/0/True"  > True
\$ echo "#http://sigil.place/post/0/False" > False
\$ echo "#http://sigil.place/post/0/or"    > or``````

We can then use these local files as convenient short-hand aliases for remote imports:

``````\$ morte
#or #True #False
<Ctrl-D>
∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True``````

We can use imports anywhere in our program, even as types! For example, in the calculus of constructions you encode `if` as the identity function on `#Bool`s:

``λ(b : #Bool ) → b  # Note: Imports must end with whitespace``

We can then save our implementation of `if` to a file named `if`, except using the ASCII symbols `\` and `->` instead of `λ` and `→`:

``\$ echo "\(b : #Bool ) -> b" > if``

Now we can define our own `and` function in terms of `if`. Remember that the Haskell definition of `and` is:

``and b1 b2 = if b1 then b2 else False``

Our definition won't be much different:

``\$ echo "\(b1 : #Bool ) -> \(b2 : #Bool ) -> #if b1 #Bool b2 #False" > and``

Let's confirm that our new `and` function works:

``````\$ echo "#and #True #False" | morte
∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False``````

We can also ask `morte` to resolve all imports for our `and` function and optimize the result:

``````\$ morte < and
∀(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ ∀(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

λ(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ λ(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ b1 (∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
b2
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)``````

We can then compare our version with the `and` expression hosted online, which is identical:

``````\$ curl sigil.place/post/0/and
λ(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ λ(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ b1 (∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
b2
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)``````

#### Reduction

When we write an expression like this:

``#or #True #False``

The compiler resolves all imports transitively until all that is left is an expression in the calculus of constructions, like this one:

``````-- or
( λ(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ b1 (∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)
)
-- True
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True )
-- False
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)``````

Then the compiler reduces this expression using β-reduction and ε-reduction. We can safely reduce these expressions at compile time because these reductions always terminate in the calculus of constructions, which is a total and non-recursive language.

For example, the above expression reduces to:

``````  ( λ(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ b1 (∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)
)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True )
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)

-- β-reduce
= (λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True )
(∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)

-- β-reduce
= ( λ(True : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ λ(False : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ True
)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)

-- β-reduce
= ( λ(False : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True
)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)

-- β-reduce
= λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True``````

The `and` we defined is "dynamically linked", meaning that the file we saved has not yet resolved all imports:

``````\$ cat and
\(b1 : #Bool ) -> \(b2 : #Bool ) -> #if b1 #Bool b2 #False``````

The `morte` compiler will resolve these imports every time we import this expression within a program. To be precise, each import is resolved once per program and then cached and reused for subsequent duplicate imports. That means that the compiler only imports `#Bool` once for the above program and not three times. Also, we can transparently cache these expressions just like any other web resource by providing the appropriate `Cache-Control` HTTP header. For example, my static web server sets `max-age` to a day so that expressions can be cached for up to one day.

If our imported expressions change then our program will reflect those changes, which may or may not be desirable. For the above program dynamic linking is undesirable because if we change the file `#False` to point to sigil.place/post/0/True then we would break the behavior of the `and` function.

Alternatively, we can "statically link" the `and` function by resolving all imports using the `morte` compiler. For example, I statically linked my remote `and` expression because the behavior should never change:

``````\$ curl sigil.place/post/0/and
λ(b1 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ λ(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ b1 (∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
b2
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False)``````

In other scenarios you might want to dynamically link expressions if you want to automatically pull in upgrades from trusted upstream sources. This is the same rationale behind service-oriented architectures which optimize for transparent system-wide updates, except that instead of updating a service we update an expression.

#### Partial application

We can store partially applied functions in files, too. For example, we could store `and True` in a statically linked file named `example` using `morte`:

``````\$ echo "#and #True" | morte > example
∀(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool)
→ ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool``````

The type still goes to standard error, but the partially applied function goes to the `example` file. We can use the partially applied function just by referencing our new file:

``````\$ morte
#example #False  -- Same as: #and #True #False
<Ctrl-D>
∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool

λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → False``````

We can even view `example` and see that it's still just an ordinary text source file:

``````\$ cat example
λ(b2 : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool) → b2``````

We can also see that `morte` was clever and optimized `#and #True` to the identity function on `#Bool`s.

If we wanted to share our `example` code with our friends, we'd just host the file using any static web server. I like to use Haskell's `warp` server (from the `wai-app-static` package) for static hosting, but even something like `python -m SimpleHTTPServer` would work just as well:

``````\$ cabal install wai-app-static
\$ warp
Serving directory /tmp/code on port 3000 with ["index.html","index.htm"] index files.``````

Then we could provide our friends with a URL pointing to the `example` file and they could embed our code within their program by pasting in our URL.

#### Types

The calculus of constructions is typed, so if you make a mistake, you'll know immediately:

``````\$ morte
#True #True
<Ctrl-D>
Expression:
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)
(λ(Bool : *) → λ(True : Bool) → λ(False : Bool) → True)

Error: Function applied to argument of the wrong type

Expected type: *
Argument type: ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool``````

Types are what differentiates `morte` from a curl into sh. You can use the type system to whitelist the set of permissible values to import.

For example, in this code, there are only two values of `#x` that will type-check (up to α-conversion):

``(λ(b : ∀(Bool : *) → ∀(True : Bool) → ∀(False : Bool) → Bool) → b) #x``

Therefore, we can safely import a remote value knowing that the type-checker will reject attempts to inject arbitrary code.

When building a program with effects, we can similarly refine the set of permissible actions using the types. I introduced one such example in my previous post on `morte`, where the `recursive.mt` program restricts the effects to reading and printing lines of text and nothing else. You could then import a remote expression of type:

``````  ∀(String : *)
→ ∀(U : *)
→ ∀(Unit : U)
→ ∀(IO : *)
→ ∀(GetLine : String → IO → IO)
→ ∀(PutStrLn : (String → IO) → IO)
→ ∀(Return : U → IO)
→ IO``````

... which is the type of an effect syntax tree built from `GetLine`/`PutStrLn`/`Return` constructors. The type-checker will then enforce that the imported syntax tree cannot contain any other constructors and therefore cannot be interpreted to produce any other effects.

#### Recursive data types

You can encode recursive data types and functions in the calculus of constructions. This is all the more amazing when you realize that the calculus of constructions does not permit recursion! Also, `morte`'s import system forbids recursion as well. If you try to recurse using imports you will get an error:

``````\$ echo "#foo" > bar
\$ echo "#bar" > foo
\$ morte < foo
morte:
⤷ #bar
⤷ #foo
Cyclic import: #bar ``````

Joe Armstrong once proposed that the core language for an internet of code would require built-in support for recursion (via `letrec` or something similar), but that's actually not true! The paper "Automatic synthesis of typed Λ-programs on term algebras" spells out how to encode recursive data types in the non-recursive System F language. What's amazing is that the algorithm works even for mutually recursive data types like `Even` and `Odd` from our original Haskell example.

You don't have to take my word for it! You can verify for yourself that the `Even` and `Odd` types and the `Zero`/`SuccE`/`SuccO` constructors that I hosted online are not recursive:

Let's create local aliases for the constructors so we can built our own `Even` or `Odd` values:

``````\$ echo "#http://sigil.place/post/0/Zero"  > Zero
\$ echo "#http://sigil.place/post/0/SuccE" > SuccE
\$ echo "#http://sigil.place/post/0/SuccO" > SuccO``````

We can then assemble the number `four` using these constructors:

``````\$ morte
#SuccE (#SuccO (#SuccE (#SuccO #Zero )))
<Ctrl-D>
∀(Even : *)
→ ∀(Odd : *)
→ ∀(Zero : Even)
→ ∀(SuccE : ∀(pred : Odd) → Even)
→ ∀(SuccO : ∀(pred : Even) → Odd)
→ Even

λ(Even : *)
→ λ(Odd : *)
→ λ(Zero : Even)
→ λ(SuccE : ∀(pred : Odd) → Even)
→ λ(SuccO : ∀(pred : Even) → Odd)
→ SuccE (SuccO (SuccE (SuccO Zero)))``````

The result is identical to the `four` that I hosted:

``````\$ curl sigil.place/post/0/four
λ(Even : *)
→ λ(Odd : *)
→ λ(Zero : Even)
→ λ(SuccE : ∀(pred : Odd) → Even)
→ λ(SuccO : ∀(pred : Even) → Odd)
→ SuccE (SuccO (SuccE (SuccO Zero)))``````

We can even encode functions over mutually recursive types like `doubleEven` and `doubleOdd`. You can verify that the ones I wrote are not recursive:

... and then we can test that they work by doubling the number `four`:

``````\$ morte
#http://sigil.place/post/0/doubleEven
#http://sigil.place/post/0/four
<Ctrl-D>
∀(Even : *)
→ ∀(Odd : *)
→ ∀(Zero : Even)
→ ∀(SuccE : ∀(pred : Odd) → Even)
→ ∀(SuccO : ∀(pred : Even) → Odd)
→ Even

λ(Even : *)
→ λ(Odd : *)
→ λ(Zero : Even)
→ λ(SuccE : ∀(pred : Odd) → Even)
→ λ(SuccO : ∀(pred : Even) → Odd)
→ SuccE (SuccO (SuccE (SuccO (SuccE (SuccO (SuccE (SuccO Zero)))))))``````

We get back the `Even` number eight encoded in the calculus of constructions.

#### Stack traces

`morte` will provide a "stack trace" if there is a type error or parse error:

``````\$ echo "\(a : *) ->" > foo  # This is a malformed program
\$ echo "#foo" > bar
\$ echo "#bar" > baz
\$ echo "#baz" > qux
\$ morte < qux
morte:
⤷ #qux
⤷ #baz
⤷ #bar
⤷ #foo

Line:   2
Column: 1

Parsing: EOF

Error: Parsing failed``````

You can learn more about how `morte`'s import system works by reading the newly add "Imports" section of the `morte` tutorial.

#### Comparison to other software architectures

`morte`'s code distribution system most closely resembles the distribution model of Javascript, meaning that code can be downloaded from any URL and is compiled or interpreted client-side. The most important difference between the two is the granularity of imports and the import mechanism.

In `morte` the unit of distribution is individual types, terms, and constructors and you can inject a remote expression anywhere in the syntax tree by referencing its URL. This is why we can do crazy things like use a URL for a type:

``λ(b : #http://sigil.place/post/0/Bool ) → ...``

The second difference is that `morte` is designed from the ground up to be typed and highly optimizable (analogous to `asm.js`, a restricted subset of Javascript designed for ease of optimization).

The third difference is that `morte` lets you precisely delimit what remote code can do using the type system, unlike Javascript.

#### Future directions

This is just one piece of the puzzle in a long-term project of mine to build a typed and distributed intermediate language that we can use to share code across language boundaries. I want to give people the freedom to program in the language of their choice while still interoperating freely with other languages. In other words, I'm trying to build a `pandoc` for programming languages.

However, this project is still not really usable, even in anger. There are several missing features to go, some of which will be provided by my upcoming `annah` library:

Requirement #1: There needs to be a way to convert between restricted subsets of existing programming languages and the calculus of constructions

`annah` currently provides logic to encode medium-level language abstractions to and from the calculus of constructions. In fact, that's how I converted the Haskell example at the beginning of this post into the calculus of constructions. For example, I used `annah` to derive how to encode the `SuccE` constructor in the calculus of constructions:

``````\$ annah compile
type Even
data Zero
data SuccE (pred : Odd)

type Odd
data SuccO (pred : Even)

in SuccE
<Ctrl-D>``````

... and `annah` correctly deduced the type and value in the calculus of constructions:

``````  ∀(pred : ∀(Even : *)
→ ∀(Odd : *)
→ ∀(Zero : Even)
→ ∀(SuccE : ∀(pred : Odd)
→ Even )
→ ∀(SuccO : ∀(pred : Even) → Odd) → Odd)
→ ∀(Even : *)
→ ∀(Odd : *)
→ ∀(Zero : Even)
→ ∀(SuccE : ∀(pred : Odd) → Even)
→ ∀(SuccO : ∀(pred : Even) → Odd)
→ Even

λ(pred : ∀(Even : *)
→ ∀(Odd : *)
→ ∀(Zero : Even)
→ ∀(SuccE : ∀(pred : Odd) → Even)
→ ∀(SuccO : ∀(pred : Even) → Odd)
→ Odd )
→ λ(Even : *)
→ λ(Odd : *)
→ λ(Zero : Even)
→ λ(SuccE : ∀(pred : Odd) → Even)
→ λ(SuccO : ∀(pred : Even) → Odd)
→ SuccE (pred Even Odd Zero SuccE SuccO)``````

Among other things, `annah` automates the algorithm from "Automatic synthesis of typed Λ-programs on term algebras", which is known as "Böhm-Berarducci encoding".

Requirement #2: There must be an efficient way to transmit bytes, text, and numbers alongside code.

My plan is to transmit this information out-of-band as a separate file rather than embedding the data directly within the code and `annah` will provide a systematic convention for distributing data and referencing that data within source code.

Requirement #3: There needs to be a standard library of types, data structures, functions, and side effects that all target languages must support.

In other words, there needs to be some sort of `thrift` for code so that languages can maximize code sharing.

Requirement #4: There must be better tooling for mass installation and hosting of expressions.

For example, I'd like to be able to alias all imports within a remote directory to local files with a single command.

Requirement #5: I need to figure out a way to mesh type inference with an expression-level distribution system.

As far as I can tell this is still an open research problem and this is most likely going to be the greatest obstacle to making this usable in practice.

#### Resources

If you would like to learn more about Morte or contribute, then check out the following resources:

## Wednesday, May 6, 2015

Recently somebody posted a template for generating blog comment spam, so I thought: "What sillier way to show how elegant Haskell is than generating comment spam?!"

The first "stanza" of the template looks like this:

``````{I have|I've} been {surfing|browsing} online
more than {three|3|2|4} hours today, yet
I never found any interesting article like yours.
{It's|It is}
pretty worth enough for me. {In my
opinion|Personally|In my view},
if all {webmasters|site owners|website owners|web
owners} and bloggers made good content as you
did, the {internet|net|web} will be {much more|a
lot more} useful than ever before.|
I {couldn't|could not} {resist|refrain from}
commenting.
{Very well|Perfectly|Well|Exceptionally well}
written!|
{I will|I'll} {right away|immediately} {take
{allow|permit|let} me
{realize|recognize|understand|recognise|know} {so
that|in order that} I {may
just|may|could} subscribe. Thanks.|
{It is|It's} {appropriate|perfect|the best}
time to
make some plans for the future and {it is|it's}
time to be happy. ``````

Anything of the form `{x|y|z}` represents a choice between alternative text fragments `x`, `y`, and `z`. The above template has four large alternative comments to pick from, each with their own internal variations. The purpose of these alternatives is to evade simple spam detection algorithms, much like how some viruses evade the immune system by mutating antigens.

I wanted to write a Haskell program that selected a random template from one of the provided alternatives and came up with this:

``````{-# LANGUAGE OverloadedStrings #-}

import Control.Foldl (random)  -- Requires `foldl-1.0.10` or higher
import Turtle

main = do
x <- foldIO spam random
print x

spam :: Shell Text
spam =  -- 1st major template
""
* ("I have" + "I've")
*  " been "
* ("surfing" + "browsing")
*  " online more than "
* ("three" + "3" + "2" + "4")
*  " hours today, yet I never found any interesting article like yours. "
* ("It's" + "It is")
*  " pretty worth enough for me. "
* ("In my opinion" + "Personally" + "In my view")
*  ", if all "
* ("webmasters" + "site owners" + "website owners" + "web owners")
*  " and bloggers made good content as you did, the "
* ("internet" + "net" + "web")
*  " will be "
* ("much more" + "a lot more")
*  " useful than ever before."

-- 2nd major template
+   " I "
* ("couldn't" + "could not")
*  " "
* ("resist" + "refrain from")
*  " commenting. "
* ("Very well" + "Perfectly" + "Well" + "Exceptionally well")
*  " written!"

-- 3rd major template
+    " "
* ("I will" + "I'll")
*  " "
* ("right away" + "immediately")
*  " "
* ("take hold of" + "grab" + "clutch" + "grasp" + "seize" + "snatch")
*  " as I "
* ("can not" + "can't")
*  " "
* ("in finding" + "find" + "to find")
* ("email" + "e-mail")
*  " subscription "
*  " or "
*  " service. Do "
* ("you have" + "you've")
*  " any? "
*  " "
* ("allow" + "permit" + "let")
*  " me "
* ("realize" + "recognize" + "understand" + "recognise" + "know")
*  " "
* ("so that" + "in order that")
*  " I "
* ("may just" + "may" + "could")
*  " subscribe. Thanks."

-- 4th major template
+    " "
* ("It is" + "It's")
*  " "
* ("appropriate" + "perfect" + "the best")
*  " time to make some plans for the future and "
* ("it is" + "it's")
*  " time to be happy."``````

Conceptually, all I did to embed the template in Haskell was to:

• add a quote to the beginning of the template: `"`
• replace all occurences of `{` with `"*("` (including quotes)
• replace all occurences of `}` with `")*"` (including quotes)
• replace all occurences of `|` with `"+"` (including quotes)
• add a quote to the end of the template: `"`

In fact, I mechanically transformed the template to Haskell code using simple `sed` commands within `vi` and then just formatted the result to be more readable.

Before explaining why this works, let's try our program out to verify that it works:

``````\$ ghc -O2 spam.hs
\$ ./spam
Just " I will right away grab your rss feed as I
recognise in order that I could subscribe.
Thanks."
\$ ./spam
Just " I'll immediately seize your rss as I can not find
you have any? Please allow me realize in order that I may
subscribe. Thanks."``````

You might wonder: how does the above program work?

#### Types

Let's begin from the type of the top-level utility named `foldIO`:

``````foldIO
:: Shell a       -- A stream of `a`s
-> FoldM IO a b  -- A fold that reduces `a`s to a single `b`
-> IO b          -- The result (a `b`)``````

`foldIO` connects a producer of `a`s (i.e. a `Shell`) to a fold that consumes `a`s and produces a single `b` (i.e. a `FoldM`). For now we will ignore how they are implemented. Instead we will play type tetris to see how we can connect things together.

The first argument we supply to `foldIO` is `spam`, whose type is:

``spam :: Shell Text``

Think of a `Shell` as a stream, and `spam` is a stream whose elements are `Text` values. Each element of this stream corresponds to one possible alternative for our template. For example, a template with exactly one alternative would be a stream with one element.

When we supply `spam` as the first argument to `foldIO`, the compiler infers that the first `a` in the type of `foldIO` must be `Text`

``````foldIO :: Shell a -> FoldM IO a b -> IO b
^
|
|
|
spam   :: Shell Text``````

... therefore, the second `a` must also be `Text`:

``````foldIO :: Shell a -> FoldM IO a b -> IO b
^             ^
|             |
+-------------+
|
spam   :: Shell Text``````

... so in this context `foldIO` has the more specialized type:

``foldIO :: Shell Text -> FoldM IO Text b -> IO b``

... and when we apply `foldIO` to `spam` we get the following narrower type:

``foldIO spam :: FoldM IO Text b -> IO b``

Now all we need to do is to provide a fold that can consume a stream of `Text` elements. We choose the `random` fold, which uses reservoir sampling to pick a random element from the stream. The type of `random` is:

``random :: FoldM IO a (Maybe a)``

In other words, given an input stream of `a`s, this fold reduces the stream to a single `Maybe a`. The `Maybe` is either `Nothing` if the stream is empty or `Just` some random element from the stream if the stream is non-empty.

When we supply `random` as the second argument to `foldIO`, the compiler infers that the `a` in `random` must be `Text`:

``````foldIO spam :: FoldM IO Text        b -> IO b
|
|
|
v
random      :: FoldM IO a    (Maybe a)``````

... therefore the second `a` must also be `Text`:

``````foldIO spam :: FoldM IO Text        b -> IO b
|
+-----------+
|           |
v           v
random      :: FoldM IO a    (Maybe a)``````

So the specialized type of `random` becomes:

``````foldIO spam :: FoldM IO Text        b     -> IO b

random      :: FoldM IO Text (Maybe Text)``````

Now we can apply type inference in the opposite direction! The compiler infers that the `b` in the type of `foldIO` must be `Maybe Text`:

``````foldIO spam :: FoldM IO Text        b     -> IO b
^
|
|
|
random      :: FoldM IO Text (Maybe Text)``````

... therefore the other `b` must also be `Maybe Text`:

``````foldIO spam :: FoldM IO Text        b     -> IO b
^           ^
|           |
+-----------+
|
random      :: FoldM IO Text (Maybe Text)``````

... so we specialize `foldIO`'s type even further to:

``foldIO spam :: foldM IO Text (Maybe Text) -> IO (Maybe Text)``

... and when we apply that to `random` the type simplifies down to:

``foldIO spam random :: IO (Maybe Text)``

The end result is a subroutine that loops over the stream using reservoir sampling, selects a random element (or `Nothing` if the stream is empty), and then returns the result.

All that's left is to `print` the result:

``````main = do
x <- foldIO spam random
print x``````

So that explains the top half of the code, but what about the bottom half? What is up with the addition and multiplication of strings?

The first trick is that the strings are actually not strings at all! Haskell lets you overload string literals using the `OverloadedStrings` extension so that they type-check as any type that implements the `IsString` type class. The `Shell Text` type is one such type. If you provide a string literal where the compiler expects a `Shell Text` then the compiler will instead build a 1-element stream containing just that string literal.

The second trick is that Haskell lets you overload numeric operatoins to work on any type that implements the `Num` type class. The `Shell Text` type implements this type class, so you can add and multiply streams of text elements.

The behavior of addition is stream concatenation. In our template, when we write:

``"Very well" + "Perfectly" + "Well" + "Exceptionally well"``

... we are really concatenating four 1-element streams into a combined 4-element stream representing the four alternatives.

The behavior of multiplication is to sequence two templates. Either template may be a stream of multiple alternatives so when we sequence them we take the "cartesian product" of both streams. When we multiply two streams we concatenate every alterntaive from the first stream with every alternative from the second stream and return all possible combinations.

For example, when we write:

``("couldn't " + "could not ") * ("resist" + "refrain from")``

This reduces to four combinations:

``````  "couldn't resist"
+ "couldn't refrain from"
+ "could not resist"
+ "could not refrain from"``````

You can actually derive this using the rules of addition and multiplication:

``````("couldn't " + "could not ") * ("resist" + "refrain from")

-- Multiplication distributes over left addition
"couldn't "  * ("resist" + "refrain from")
+ "could not " * ("resist" + "refrain from")

-- Multiplication distributes again
"couldn't "   * "resist"
+ "couldn't "   * "refrain from"
+ "could not "  * "resist"
+ "could not "  * "refrain from"

-- Multiplying 1-element templates just sequences them
"couldn't resist"
+ "couldn't refrain from"
+ "could not resist"
+ "could not refrain from"``````

Notice how if we sequence two 1-element templates

``"I have " * "been"``

... it's identical to string concatenation:

``"I have been"``

And that's it! We build the template using arithmetic and then we fold the results using `random` to select one template at random. That's the complete program! Or did we?

#### Weighting

Actually there's one catch: our spam generator is very heavily biased towards the third major template. This is because the generator weights all alternatives equally, but each major template has a different number of alternatives:

• 1st template: 2304 alternatives
• 2nd template: 16 alternatives
• 3rd template: 829440
• 4th template: 12 alternatives

As a result we're 360 times more likely to get the 3rd template than the next most common template (the 1st one). How can we weight each template to undo this bias?

The answer is simple: we can weight each template by using multiplication, scaling each template by the appropritae numeric factor.

In this case, the weights we will apply are:

• 1st template: Increase frequency by 360x
• 2nd template: Increase frequency by 51840x
• 3rd template: Keep frequency the same (1x)
• 4th template: Increase frequency by 69120x

Here's the implementation:

``````spam =  -- 1st major template
360
*  ""
* ("I have" + "I've")
*  " been "
* ("surfing" + "browsing")
*  " online more than "
* ("three" + "3" + "2" + "4")
*  " hours today, yet I never found any interesting article like yours. "
* ("It's" + "It is")
*  " pretty worth enough for me. "
* ("In my opinion" + "Personally" + "In my view")
*  ", if all "
* ("webmasters" + "site owners" + "website owners" + "web owners")
*  " and bloggers made good content as you did, the "
* ("internet" + "net" + "web")
*  " will be "
* ("much more" + "a lot more")
*  " useful than ever before."

-- 2nd major template
+    51840
*  " I "
* ("couldn't" + "could not")
*  " "
* ("resist" + "refrain from")
*  " commenting. "
* ("Very well" + "Perfectly" + "Well" + "Exceptionally well")
*  " written!"

-- 3rd major template
+    1
*  " "
* ("I will" + "I'll")
*  " "
* ("right away" + "immediately")
*  " "
* ("take hold of" + "grab" + "clutch" + "grasp" + "seize" + "snatch")
*  " as I "
* ("can not" + "can't")
*  " "
* ("in finding" + "find" + "to find")
* ("email" + "e-mail")
*  " subscription "
*  " or "
*  " service. Do "
* ("you have" + "you've")
*  " any? "
*  " "
* ("allow" + "permit" + "let")
*  " me "
* ("realize" + "recognize" + "understand" + "recognise" + "know")
*  " "
* ("so that" + "in order that")
*  " I "
* ("may just" + "may" + "could")
*  " subscribe. Thanks."

-- 4th major template
+    69120
*  " "
* ("It is" + "It's")
*  " "
* ("appropriate" + "perfect" + "the best")
*  " time to make some plans for the future and "
* ("it is" + "it's")
*  " time to be happy."``````

Now this produces a fairer distribution between the four major alternatives:

``````\$ ./spam
Just "I have been surfing online more than three
hours today, yet I never found any interesting
article like yours. It's pretty worth enough for
me. In my view, if all web owners and bloggers
made good content as you did, the internet will
be a lot more useful than ever before."
\$ ./spam
Just " It's the best time to make some plans for
the future and it's time to be happy."
\$ ./spam
or newsletter service. Do you have any? Kindly
let me understand so that I may just subscribe.
Thanks."
\$ ./spam
Just " I could not refrain from commenting. Exceptionally well written!"``````

Remember how we said that `Shell Text` implements the `Num` type class in order to get addition and multiplication? Well, you can also use the same `Num` class to overload integer literals. Any time the compiler sees an integer literal where it expects a `Shell Text` it will replace that integer with a stream of empty strings whose length is the given integer.

For example, if you write the number 3, it's equivalent to:

``````-- Definition of 3
3 = 1 + 1 + 1

-- 1 = ""
3 = "" + "" + ""``````

So if you write:

``3 * "some string"``

... that expands out to:

``("" + "" + "") * "some string"``

... and multiplication distributes to give us:

``("" * "some string") + ("" * "some string") + ("" * "some string")``

... which reduces to three copies of `"some string"`:

``"some string" + "some string" + "some string"``

This trick works even when multiplying a number by a template with multiple alternatives:

``````2 * ("I have" + "I've")

-- 2 = 1 + 1
= (1 + 1) * ("I have" + "I've")

-- 1 = ""
= ("" + "") * ("I have" + "I've")

-- Multiplication distributes
= ("" * "I have") + ("" * "I've") + ("" * "I have") + ("" * "I've")

-- Simplify
= "I have" + "I've" + "I have" + "I've"``````

#### Arithmetic

In fact, `Shell Text` obeys all sort of arithmetic laws:

``````-- `0` is the identity of addition
0 + x = x
x + 0 = x

(x + y) + z = x + (y + z

-- `1` is the identity of multiplication
1 * x = 1
x * 1 = 1

-- Multiplication is associative
(x * y) * z = x * (y * z)

(x + y) * z = (x * z) + (y * z)

-- 1-element streams left-distribute over addition
"string" * (x + y) = ("string" * x) + ("string" * y)``````

I'm not sure what the mathematical name is for this sort of structure. I usually call this a "semiring", but that's technically not correct because in a semiring we expect addition to commute, but here it does not because `Shell Text` preserves the ordering of results. For the case of selecting a random element ordering does not matter, but there are other operations we can perform on these streams that are order-dependent.

In fact, the laws of arithmetic enforce that you weigh all fine-grained alternatives equally, regardless of the frequencies of the top-level coarse-grained alternatives. If you weighted things based on the relative frequencies of top-level alternatives you would get very inconsistent behavior.

For example, if you tried to be more "fair" for outer alternatives, then addition stops being associative, meaning that these templates would no longer behave the same:

``````{x|{y|z}}
{{x|y}|z}
{x|y|z}``````

#### Conclusion

The Haskell template generator was so concise for two main reasons:

• We embedded the template directly within Haskell, so we skipped having to parse the template
• We reuse modular and highly generic components (like `random`, `foldIO`, `(+)`, and `(*)` and numeric literals) instead of writing our own custom code

Also, our program is easily modifiable. For example, if we want to collect all the templates, we just replace `random` with `vector`:

``````import Control.Foldl (vector)
import Data.Vector (Vector)

main = do
x <- foldIO spam vector
print (x :: Vector Text)``````

That efficiently builds a vector in place using mutation that stores all the results, then purifies the result.

However, these sorts of tricks come at a cost. Most of the awesome tricks like this are not part of the standard library and instead exist in libraries, making them significantly harder to discover. Worse, you're never really "done" learning the Haskell language. The library ecosystem is a really deep rabbit hole full of jewels and at some point you just have to pick a point to just stop digging through libraries and build something useful ...

... or useless, like a comment spam generator.