# News aggregator

### FP Complete: Call C functions from Haskell without bindings

Because Haskell is a language of choice for many problem domains, and for scales ranging from one-off scripts to full scale web services, we are fortunate to by now have over 8,000 open source packages (and a few commercial ones besides) available to build from. But in practice, Haskell programming in the real world involves interacting with myriad legacy systems and libraries. Partially because the industry is far older than the comparatively recent strength of our community. But further still, because quality new high-performance libraries are created every day in languages other than Haskell, be it intensive numerical codes or frameworks for shuffling bits across machines. Today we are releasing inline-c, a package for writing mixed C/Haskell source code that seamlessly invokes native and foreign functions in the same module. No FFI required.

The joys of programming with foreign codeImagine that you just found a C library that you wish to use for your project. The standard workflow is to,

- check Hackage if a package with a set of bindings for that library exists,
- if one does, program against that, or
- if it doesn't, write your own bindings package, using Haskell's FFI.

Writing *and maintaining* bindings for large C libraries is hard work.
The libraries are constantly updated upstream, so that the bindings
you find are invariably out-of-date, providing only partial coverage
of library's API, sometimes don't compile cleanly against the latest
upstream version of the C library or need convoluted and error-prone
conditional compilation directives to support multiple versions of the
API in the package. Which is a shame, because typically you only need
to perform a very specific task using some C library, using only
a minute proportion of its API. It can be frustrating for a bindings
package to fail to install, only because the binding for some function
that you'll never use doesn't match up with the header files of the
library version you happen to have installed on your system.

This is especially true for large libraries that expose sets of related but orthogonal and indepedently useful functions, such as GTK+, OpenCV or numerical libraries such as the GNU Scientific Library (GSL), NAG and IMSL. inline-c lets you call functions from these libraries using the full power of C's syntax, directly from client code, without the need for monolithic bindings packages. High-level bindings (or "wrappers") may still be useful to wrap low-level details into an idiomatic Haskell interface, but inline-c enables rapid prototyping and iterative development of code that uses directly some of the C library today, keeping for later the task of abstracting calls into a high-level, type safe wrapper as needed. In short, inline-c let's you "pay as you go" when programming foreign code.

We first developed inline-c for use with numerical libraries, in particular the popular and very high quality commercial NAG library, for tasks including ODE solving, function optimization, and interpolation. If getting seamless access to the gold standard of fast and reliable numerical routines is what you need, then you will be interested in our companion package to work specifically with NAG, inline-c-nag.

A taste of inline-cWhat follows is just a teaser of what can be done with inline-c. Please refer to the Haddock documentation and the README for more details on how to use the showcased features.

Let's say we want to use C's variadic printf function and its convenient string formats. inline-c let's you write this function call inline, without any need for a binding to the foreign function:

{-# LANGUAGE QuasiQuotes #-} {-# LANGUAGE TemplateHaskell #-} import qualified Language.C.Inline as C C.include "<stdio.h>" C.include "<math.h>" main :: IO () main = do x <- [C.exp| int{ printf("Some number: %.2f\n", cos(0.5)) } |] putStrLn $ show x ++ " characters printed."Importing Language.C.Inline brings into scope the Template Haskell function include to include C headers (<stdio.h> and <math.h>), and the exp quasiquoter for embedding expressions in C syntax in Haskell code. Notice how inline-c has no trouble even with C functions that have advanced calling conventions, such as variadic functions. This is a crucial point: we have the full power of C available at our fingertips, not just whatever can be shoe-horned through the FFI.

We can capture Haskell variables to be used in the C expression, such as when computing x below:

mycos :: CDouble -> IO CDouble mycos x = [C.exp| double{ cos($(double x)) } |]The anti-quotation $(double x) indicates that we want to capture the variable x from the Haskell environment, and that we want it to have type double in C (inline-c will check at compile time that this is a sensible type ascription).

We can also splice in a block of C statements, and explicitly return the result:

C.include "<stdio.h>" -- | @readAndSum n@ reads @n@ numbers from standard input and returns -- their sum. readAndSum :: CInt -> IO CInt readAndSum n = do x <- [C.block| int { int i, sum = 0, tmp; for (i = 0; i < $(int n); i++) { scanf("%d ", &tmp); sum += tmp; } return sum; } |] print xFinally, the library provides facilities to easily use Haskell data in C. For example, we can easily use Haskell ByteStrings in C:

{-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE QuasiQuotes #-} import qualified Data.ByteString as BS import Data.Monoid ((<>)) import Foreign.C.Types import qualified Language.C.Inline as C import Text.RawString.QQ (r) C.context (C.baseCtx <> C.bsCtx) -- | Count the number of set bits in a 'BS.ByteString'. countSetBits :: BS.ByteString -> IO CInt countSetBits bs = [C.block| int { int i, bits = 0; for (i = 0; i < $bs-len:bs; i++) { unsigned char ch = $bs-ptr:bs[i]; bits += (ch * 01001001001ULL & 042104210421ULL) % 017; } return bits; } |]In this example, we use the bs-len and bs-ptr anti-quoters to get the length and pointer for a Haskell ByteString. inline-c has a modular design: these anti-quoters are completely optional and can be included on-demand. The C.context invocation adds the extra ByteStrings anti-quoters to the base set. Similar facilities are present to easily use Haskell Vectors as well as for invoking Haskell closures from C code.

Larger examplesWe have included various examples in the inline-c and inline-c-nag repositories. Currently they're geared toward scientific and numerical computing, but we would welcome contributions using inline-c in other fields.

For instance, gsl-ode.hs is a great example of combining the strengths of C and the strengths of Haskell to good effect: we use a function from C's GNU Scientific Library for solving ordinary differential equations (ODE) to solve a Lorenz system, and then take advantage of the very nice Chart-diagrams Haskell library to display its x and z coordinates:

In this example, the vec-ptr anti-quoter is used to get a pointer out of a mutable vector:

$vec-ptr:(double *fMut)Where fMut is a variable of type Data.Storable.Vector.Mutable.Vector CDouble. Moreover, the fun anti-quoter is used to get a function pointer from a Haskell function:

$fun:(int (* funIO) (double t, const double y[], double dydt[], void * params))Where, funIO is a Haskell function of type

CDouble -> Ptr CDouble -> Ptr CDouble -> Ptr () -> IO CIntNote that all these anti-quoters (apart from the ones where only one
type is allowed, like vec-len or bs-ptr) force the user to specify
the target C type. The alternative would have been to write the
Haskell type. Either way *some* type ascription is unfortunately
required, due to a limitation of Template Haskell. We choose C type
annotations because in this way, the user can understand precisely and
state explicitly the target type of any marshalling.

Note that at this stage, type annotations are needed, because it is not possible to get the type of locally defined variables in Template Haskell.

How it works under the hoodinline-c generates a piece of C code for most of the Template Haskell functions and quasi-quoters function that it exports. So when you write

[C.exp| double{ cos($(double x)) } |]a C function gets generated:

double some_name(double x) { return cos(x); }This function is then bound to in Haskell through an automatically generated FFI import declaration and invoked passing the right argument -- the x variable from the Haskell environment. The types specified in C are automatically translated to the corresponding Haskell types, to generate the correct type signatures.

Custom anti quoters, such as vec-ptr and vec-len, handle the C and Haskell types independently. For example, when writing

[C.block| double { int i; double res; for (i = 0; i < $vec-len:xs; i++) { res += $vec-ptr:(double *xs)[i]; } return res; } |]we'll get a function of type

double some_name(int xs_len, double *xs_ptr)and on the Haskell side the variable xs will be used in conjuction with some code getting its length and the underlying pointer, both to be passed as arguments.

Building programs that use inline-cThe C code that inline-c generates is stored in a file named like the Haskell source file, but with a .c extension.

When using cabal, it is enough to specify generated C source, and eventual options for the C code:

executable foo main-is: Main.hs, Foo.hs, Bar.hs hs-source-dirs: src -- Here the corresponding C sources must be listed for every module -- that uses C code. In this example, Main.hs and Bar.hs do, but -- Foo.hs does not. c-sources: src/Main.c, src/Bar.c -- These flags will be passed to the C compiler cc-options: -Wall -O2 -- Libraries to link the code with. extra-libraries: -lm ...Note that currently cabal repl is not supported, because the C code is not compiled and linked appropriately. However, cabal repl will fail at the end, when trying to load the compiled C code, which means that we can still use it to type check our package when developing.

If we were to compile the above manually we could do

$ ghc -c Main.hs $ cc -c Main.c -o Main_c.o $ ghc Foo.hs $ ghc Bar.hs $ cc -c Bar.c -o Bar_c.o $ ghc Main.o Foo.o Bar.o Main_c.o Bar_c.o -lm -o MainExtending inline-cAs mentioned previously, inline-c can be extended by defining custom anti-quoters. Moreover, we can also tell inline-c about more C types beyond the primitive ones.

Both operations are done via the Context data type. Specifically, the Context contains a TypesTable, mapping C type specifiers to Haskell types; and a Map of AntiQuoters. A baseCtx is provided specifying mappings from all the base C types to Haskell types (int to CInt, double to CDouble, and so on). Contexts can be composed using their Monoid instance.

For example, the vecCtx contains two anti-quoters, vec-len and vec-ptr. When using inline-c with external libraries we often define a context dedicated to said library, defining a TypesTable converting common types find in the library to their Haskell counterparts. For example inline-c-nag defines a context containing information regarding the types commonly using in the NAG scientific library.

See the Language.C.Inline.Context module documentation for more.

C++ supportOur original use case for inline-c was always C oriented. However,
thanks to extensible contexts, it should be possible to build C++
support on top of inline-c, as we dabbled with in
inline-c-cpp. In this way,
one can mix C++ code into Haskell source files, while reusing the
infrastructure that inline-c provides for invoking foreign
functions. Since inline-c generates C wrapper functions for all
inline expressions, one gets a function with *bona fide* C linkage to
wrap a C++ call, for free. Dealing with C++ templates, passing C++
objects in and out and conveniently manipulating them from Haskell are
the next challenges. If C++ support is what you need, feel free to
contribute to this ongoing effort!

We meant inline-c as a simple, modular alternative to monolithic binding libraries, borrowing the core concept of FFI-less programming of foreign code from the H project and language-c-inline. But this is just the first cut! We are releasing the library to the community early in hopes that it will accelerate the Haskell community's embrace of quality foreign libraries where they exist, as an alternative to expending considerable resources reinventing such libraries for little benefit. Numerical programming, machine learning, computer vision, GUI programming and data analysis come to mind as obvious areas where we want to leverage existing quality code. In fact, FP Complete is using inline-c today to enable quick access to all of NAG, a roughly 1.6K function strong library, for a large compute-intensive codebase. We hope to see many more use cases in the future.

### making 7.10.1

### I'm reading #OutOfTheTarPit does ghc have a relational model built in for state?

### Naming convention for version branches (Packageversioning)

### text-icu (and FFI in general) on Windows 64 bits

### This is what happens to ones Javascript after having learnt Haskell (x-post from /r/node)

### CALL FOR PAPERS for IIT’15, IEEE Sponsored, Dubai (01-03 Nov 2015)

### advanced cabal configuration

### Can we write a Monoidal Either?

### Cartesian Closed Comic #27: Security

### Gabriel Gonzalez: Morte: an intermediate language for super-optimizing functional programs

The Haskell language provides the following guarantee (with caveats): if two programs are equal according to equational reasoning then they will behave the same. On the other hand, Haskell does **not** guarantee that equal programs will generate identical performance. Consequently, Haskell library writers must employ rewrite rules to ensure that their abstractions do not interfere with performance.

Now suppose there were a hypothetical language with a stronger guarantee: if two programs are equal then they generate identical executables. Such a language would be immune to abstraction: no matter how many layers of indirection you might add the binary size and runtime performance would be unaffected.

Here I will introduce such an intermediate language named Morte that obeys this stronger guarantee. I have not yet implemented a back-end code generator for Morte, but I wanted to pause to share what I have completed so far because Morte uses several tricks from computer science that I believe deserve more attention.

Morte is nothing more than a bare-bones implementation of the calculus of constructions, which is a specific type of lambda calculus. The only novelty is how I intend to use this lambda calculus: as a super-optimizer.

NormalizationThe typed lambda calculus possesses a useful property: every term in the lambda calculus has a unique normal form if you beta-reduce everything. If you're new to lambda calculus, normalizing an expression equates to indiscriminately inlining every function call.

What if we built a programming language whose intermediate language was lambda calculus? What if optimization was just normalization of lambda terms (i.e. indiscriminate inlining)? If so, then we would could abstract freely, knowing that while compile times might increase, our final executable would never change.

RecursionNormally you would not want to inline everything because infinitely recursive functions would become infinitely large expressions. Fortunately, we can often translate recursive code to non-recursive code!

I'll demonstrate this trick first in Haskell and then in Morte. Let's begin from the following recursive List type along with a recursive map function over lists:

import Prelude hiding (map, foldr)data List a = Cons a (List a) | Nil

example :: List Int

example = Cons 1 (Cons 2 (Cons 3 Nil))

map :: (a -> b) -> List a -> List b

map f Nil = Nil

map f (Cons a l) = Cons (f a) (map f l)

-- Argument order intentionally switched

foldr :: List a -> (a -> x -> x) -> x -> x

foldr Nil c n = n

foldr (Cons a l) c n = c a (foldr l c n)

result :: Int

result = foldr (map (+1) example) (+) 0

-- result = 9

Now imagine that we disable all recursion in Haskell: no more recursive types and no more recursive functions. Now we must reject the above program because:

the List data type definition recursively refers to itself

the map and foldr functions recursively refer to themselves

Can we still encode lists in a non-recursive dialect of Haskell?

Yes, we can!

-- This is a valid Haskell program{-# LANGUAGE RankNTypes #-}

import Prelude hiding (map, foldr)

type List a = forall x . (a -> x -> x) -> x -> x

example :: List Int

example = \cons nil -> cons 1 (cons 2 (cons 3 nil))

map :: (a -> b) -> List a -> List b

map f l = \cons nil -> l (\a x -> cons (f a) x) nil

foldr :: List a -> (a -> x -> x) -> x -> x

foldr l = l

result :: Int

result = foldr (map (+ 1) example) (+) 0

-- result = 9

Carefully note that:

List is no longer defined recursively in terms of itself

map and foldr are no longer defined recursively in terms of themselves

Yet, we somehow managed to build a list, map a function over the list, and fold the list, all without ever using recursion! We do this by encoding the list as a fold, which is why foldr became the identity function.

This trick works for more than just lists. You can take any recursive data type and mechanically transform the type into a fold and transform functions on the type into functions on folds. If you want to learn more about this trick, the specific name for it is "Boehm-Berarducci encoding". If you are curious, this in turn is equivalent to an even more general concept from category theory known as "F-algebras", which let you encode inductive things in a non-inductive way.

Non-recursive code greatly simplifies equational reasoning. For example, we can easily prove that we can optimize map id l to l:

map id l-- Inline: map f l = \cons nil -> l (\a x -> cons (f a) x) nil

= \cons nil -> l (\a x -> cons (id a) x) nil

-- Inline: id x = x

= \cons nil -> l (\a x -> cons a x) nil

-- Eta-reduce

= \cons nil -> l cons nil

-- Eta-reduce

= l

Note that we did not need to use induction to prove this optimization because map is no longer recursive. The optimization became downright trivial, so trivial that we can automate it!

Morte optimizes programs using this same simple scheme:

- Beta-reduce everything (equivalent to inlining)
- Eta-reduce everything

To illustrate this, I will desugar our high-level Haskell code to the calculus of constructions. This desugaring process is currently manual (and tedious), but I plan to automate this, too, by providing a front-end high-level language similar to Haskell that compiles to Morte:

-- mapid.mt( \(List : * -> *)

-> \( map

: forall (a : *)

-> forall (b : *)

-> (a -> b) -> List a -> List b

)

-> \(id : forall (a : *) -> a -> a)

-> \(a : *) -> map a a (id a)

)

-- List

(\(a : *) -> forall (x : *) -> (a -> x -> x) -> x -> x)

-- map

( \(a : *)

-> \(b : *)

-> \(f : a -> b)

-> \(l : forall (x : *) -> (a -> x -> x) -> x -> x)

-> \(x : *)

-> \(Cons : b -> x -> x)

-> \(Nil: x)

-> l x (\(va : a) -> \(vx : x) -> Cons (f va) vx) Nil

)

-- id

(\(a : *) -> \(va : a) -> va)

This line of code is the "business end" of the program:

\(a : *) -> map a a (id a)The extra 'a' business is because in any polymorphic lambda calculus you explicitly accept polymorphic types as arguments and specialize functions by applying them to types. Higher-level functional languages like Haskell or ML use type inference to automatically infer and supply type arguments when possible.

We can compile this program using the morte executable, which accepts a Morte program on stdin, outputs the program's type stderr, and outputs the optimized program on stdout:

$ morte < id.mt∀(a : *) → (∀(x : *) → (a → x → x) → x → x) → ∀(x : *) → (a

→ x → x) → x → x

λ(a : *) → λ(l : ∀(x : *) → (a → x → x) → x → x) → l

The first line is the type, which is a desugared form of:

forall a . List a -> List aThe second line is the program, which is the identity function on lists. Morte optimized away the map completely, the same way we did by hand.

Morte also optimized away the rest of the code, too. Dead-code elimination is just an emergent property of Morte's simple optimization scheme.

EqualityWe could double-check our answer by asking Morte to optimize the identity function on lists:

-- idlist.mt( \(List : * -> *)

-> \(id : forall (a : *) -> a -> a)

-> \(a : *) -> id (List a)

)

-- List

(\(a : *) -> forall (x : *) -> (a -> x -> x) -> x -> x)

-- id

(\(a : *) -> \(va : a) -> va)

Sure enough, Morte outputs an alpha-equivalent result (meaning the same up to variable renaming):

$ ~/.cabal/bin/morte < idlist.mt∀(a : *) → (∀(x : *) → (a → x → x) → x → x) → ∀(x : *) → (a

→ x → x) → x → x

λ(a : *) → λ(va : ∀(x : *) → (a → x → x) → x → x) → va

We can even use the morte library to mechanically check if two Morte expressions are alpha-, beta-, and eta- equivalent. We can parse our two Morte files into Morte's Expr type and then use the Eq instance for Expr to test for equivalence:

$ ghciPrelude> import qualified Data.Text.Lazy.IO as Text

Prelude Text> txt1 <- Text.readFile "mapid.mt"

Prelude Text> txt2 <- Text.readFile "idlist.mt"

Prelude Text> import Morte.Parser (exprFromText)

Prelude Text Morte.Parser> let e1 = exprFromText txt1

Prelude Text Morte.Parser> let e2 = exprFromText txt2

Prelude Text Morte.Parser> import Control.Applicative (liftA2)

Prelude Text Morte.Parser Control.Applicative> liftA2 (==) e1 e2

Right True

$ -- `Right` means both expressions parsed successfully

$ -- `True` means they are alpha-, beta-, and eta-equivalent

We can use this to mechanically verify that two Morte programs optimize to the same result.

Compile-time computationMorte can compute as much (or as little) at compile as you want. The more information you encode directly within lambda calculus, the more compile-time computation Morte will perform for you. For example, if we translate our Haskell List code entirely to lambda calculus, then Morte will statically compute the result at compile time.

-- nine.mt( \(Nat : *)

-> \(zero : Nat)

-> \(one : Nat)

-> \((+) : Nat -> Nat -> Nat)

-> \((*) : Nat -> Nat -> Nat)

-> \(List : * -> *)

-> \(Cons : forall (a : *) -> a -> List a -> List a)

-> \(Nil : forall (a : *) -> List a)

-> \( map

: forall (a : *) -> forall (b : *)

-> (a -> b) -> List a -> List b

)

-> \( foldr

: forall (a : *)

-> List a

-> forall (r : *)

-> (a -> r -> r) -> r -> r

)

-> ( \(two : Nat)

-> \(three : Nat)

-> ( \(example : List Nat)

-> foldr Nat (map Nat Nat ((+) one) example) Nat (+) zero

)

-- example

(Cons Nat one (Cons Nat two (Cons Nat three (Nil Nat))))

)

-- two

((+) one one)

-- three

((+) one ((+) one one))

)

-- Nat

( forall (a : *)

-> (a -> a)

-> a

-> a

)

-- zero

( \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> Zero

)

-- one

( \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> Succ Zero

)

-- (+)

( \(m : forall (a : *) -> (a -> a) -> a -> a)

-> \(n : forall (a : *) -> (a -> a) -> a -> a)

-> \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> m a Succ (n a Succ Zero)

)

-- (*)

( \(m : forall (a : *) -> (a -> a) -> a -> a)

-> \(n : forall (a : *) -> (a -> a) -> a -> a)

-> \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> m a (n a Succ) Zero

)

-- List

( \(a : *)

-> forall (x : *)

-> (a -> x -> x) -- Cons

-> x -- Nil

-> x

)

-- Cons

( \(a : *)

-> \(va : a)

-> \(vas : forall (x : *) -> (a -> x -> x) -> x -> x)

-> \(x : *)

-> \(Cons : a -> x -> x)

-> \(Nil : x)

-> Cons va (vas x Cons Nil)

)

-- Nil

( \(a : *)

-> \(x : *)

-> \(Cons : a -> x -> x)

-> \(Nil : x)

-> Nil

)

-- map

( \(a : *)

-> \(b : *)

-> \(f : a -> b)

-> \(l : forall (x : *) -> (a -> x -> x) -> x -> x)

-> \(x : *)

-> \(Cons : b -> x -> x)

-> \(Nil: x)

-> l x (\(va : a) -> \(vx : x) -> Cons (f va) vx) Nil

)

-- foldr

( \(a : *)

-> \(vas : forall (x : *) -> (a -> x -> x) -> x -> x)

-> vas

)

The relevant line is:

foldr Nat (map Nat Nat ((+) one) example) Nat (+) zeroIf you remove the type-applications to Nat, this parallels our original Haskell example. We can then evaluate this expression at compile time:

$ morte < nine.mt∀(a : *) → (a → a) → a → a

λ(a : *) → λ(Succ : a → a) → λ(Zero : a) → Succ (Succ (Succ

(Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))

Morte reduces our program to a church-encoded nine.

Run-time computationMorte does not force you to compute everything using lambda calculus at compile time. Suppose that we wanted to use machine arithmetic at run-time instead. We can do this by parametrizing our program on:

- the Int type,
- operations on Ints, and
- any integer literals we use

We accept these "foreign imports" as ordinary arguments to our program:

-- foreign.mt-- Foreign imports

\(Int : *) -- Foreign type

-> \((+) : Int -> Int -> Int) -- Foreign function

-> \((*) : Int -> Int -> Int) -- Foreign function

-> \(lit@0 : Int) -- Literal "1" -- Foreign data

-> \(lit@1 : Int) -- Literal "2" -- Foreign data

-> \(lit@2 : Int) -- Literal "3" -- Foreign data

-> \(lit@3 : Int) -- Literal "1" -- Foreign data

-> \(lit@4 : Int) -- Literal "0" -- Foreign data

-- The rest is compile-time lambda calculus

-> ( \(List : * -> *)

-> \(Cons : forall (a : *) -> a -> List a -> List a)

-> \(Nil : forall (a : *) -> List a)

-> \( map

: forall (a : *)

-> forall (b : *)

-> (a -> b) -> List a -> List b

)

-> \( foldr

: forall (a : *)

-> List a

-> forall (r : *)

-> (a -> r -> r) -> r -> r

)

-> ( \(example : List Int)

-> foldr Int (map Int Int ((+) lit@3) example) Int (+) lit@4

)

-- example

(Cons Int lit@0 (Cons Int lit@1 (Cons Int lit@2 (Nil Int))))

)

-- List

( \(a : *)

-> forall (x : *)

-> (a -> x -> x) -- Cons

-> x -- Nil

-> x

)

-- Cons

( \(a : *)

-> \(va : a)

-> \(vas : forall (x : *) -> (a -> x -> x) -> x -> x)

-> \(x : *)

-> \(Cons : a -> x -> x)

-> \(Nil : x)

-> Cons va (vas x Cons Nil)

)

-- Nil

( \(a : *)

-> \(x : *)

-> \(Cons : a -> x -> x)

-> \(Nil : x)

-> Nil

)

-- map

( \(a : *)

-> \(b : *)

-> \(f : a -> b)

-> \(l : forall (x : *) -> (a -> x -> x) -> x -> x)

-> \(x : *)

-> \(Cons : b -> x -> x)

-> \(Nil: x)

-> l x (\(va : a) -> \(vx : x) -> Cons (f va) vx) Nil

)

-- foldr

( \(a : *)

-> \(vas : forall (x : *) -> (a -> x -> x) -> x -> x)

-> vas

)

We can use Morte to optimize the above program and Morte will reduce the program to nothing but foreign types, operations, and values:

$ morte < foreign.mt∀(Int : *) → (Int → Int → Int) → (Int → Int → Int) → Int →

Int → Int → Int → Int → Int

λ(Int : *) → λ((+) : Int → Int → Int) → λ((*) : Int → Int →

Int) → λ(lit : Int) → λ(lit@1 : Int) → λ(lit@2 : Int) →

λ(lit@3 : Int) → λ(lit@4 : Int) → (+) ((+) lit@3 lit) ((+)

((+) lit@3 lit@1) ((+) ((+) lit@3 lit@2) lit@4))

If you study that closely, Morte adds lit@3 (the "1" literal) to each literal of the list and then adds them up. We can then pass this foreign syntax tree to our machine arithmetic backend to transform those foreign operations to efficient operations.

Morte lets you choose how much information you want to encode within lambda calculus. The more information you encode in lambda calculus the more Morte can optimize your program, but the slower your compile times will get, so it's a tradeoff.

CorecursionCorecursion is the dual of recursion. Where recursion works on finite data types, corecursion works on potentially infinite data types. An example would be the following infinite Stream in Haskell:

data Stream a = Cons a (Stream a)numbers :: Stream Int

numbers = go 0

where

go n = Cons n (go (n + 1))

-- numbers = Cons 0 (Cons 1 (Cons 2 (...

map :: (a -> b) -> Stream a -> Stream b

map f (Cons a l) = Cons (f a) (map f l)

example :: Stream Int

example = map (+ 1) numbers

-- example = Cons 1 (Cons 2 (Cons 3 (...

Again, pretend that we disable any function from referencing itself so that the above code becomes invalid. This time we cannot reuse the same trick from previous sections because we cannot encode numbers as a fold without referencing itself. Try this if you don't believe me.

However, we can still encode corecursive things in a non-corecursive way. This time, we encode our Stream type as an unfold instead of a fold:

-- This is also valid Haskell code{-# LANGUAGE ExistentialQuantification #-}

data Stream a = forall s . MkStream

{ seed :: s

, step :: s -> (a, s)

}

numbers :: Stream Int

numbers = MkStream 0 (\n -> (n, n + 1))

map :: (a -> b) -> Stream a -> Stream b

map f (MkStream s0 k) = MkStream s0 k'

where

k' s = (f a, s')

where (a, s') = k s

In other words, we store an initial seed of some type s and a step function of type s -> (a, s) that emits one element of our Stream. The type of our seed s can be anything and in our numbers example, the type of the internal state is Int. Another stream could use a completely different internal state of type (), like this:

-- ones = Cons 1 onesones :: Stream Int

ones = MkStream () (\_ -> (1, ()))

The general name for this trick is an "F-coalgebra" encoding of a corecursive type.

Once we encode our infinite stream non-recursively, we can safely optimize the stream by inlining and eta reduction:

map id l-- l = MkStream s0 k

= map id (MkStream s0 k)

-- Inline definition of `map`

= MkStream s0 k'

where

k' = \s -> (id a, s')

where

(a, s') = k s

-- Inline definition of `id`

= MkStream s0 k'

where

k' = \s -> (a, s')

where

(a, s') = k s

-- Inline: (a, s') = k s

= MkStream s0 k'

where

k' = \s -> k s

-- Eta reduce

= MkStream s0 k'

where

k' = k

-- Inline: k' = k

= MkStream s0 k

-- l = MkStream s0 k

= l

Now let's encode Stream and map in Morte and compile the following four expressions:

map idid

map f . map g

map (f . g)

Save the following Morte file to stream.mt and then uncomment the expression you want to test:

( \(id : forall (a : *) -> a -> a)-> \( (.)

: forall (a : *)

-> forall (b : *)

-> forall (c : *)

-> (b -> c)

-> (a -> b)

-> (a -> c)

)

-> \(Pair : * -> * -> *)

-> \(P : forall (a : *) -> forall (b : *) -> a -> b -> Pair a b)

-> \( first

: forall (a : *)

-> forall (b : *)

-> forall (c : *)

-> (a -> b)

-> Pair a c

-> Pair b c

)

-> ( \(Stream : * -> *)

-> \( map

: forall (a : *)

-> forall (b : *)

-> (a -> b)

-> Stream a

-> Stream b

)

-- example@1 = example@2

-> ( \(example@1 : forall (a : *) -> Stream a -> Stream a)

-> \(example@2 : forall (a : *) -> Stream a -> Stream a)

-- example@3 = example@4

-> \( example@3

: forall (a : *)

-> forall (b : *)

-> forall (c : *)

-> (b -> c)

-> (a -> b)

-> Stream a

-> Stream c

)

-> \( example@4

: forall (a : *)

-> forall (b : *)

-> forall (c : *)

-> (b -> c)

-> (a -> b)

-> Stream a

-> Stream c

)

-- Uncomment the example you want to test

-> example@1

-- -> example@2

-- -> example@3

-- -> example@4

)

-- example@1

(\(a : *) -> map a a (id a))

-- example@2

(\(a : *) -> id (Stream a))

-- example@3

( \(a : *)

-> \(b : *)

-> \(c : *)

-> \(f : b -> c)

-> \(g : a -> b)

-> map a c ((.) a b c f g)

)

-- example@4

( \(a : *)

-> \(b : *)

-> \(c : *)

-> \(f : b -> c)

-> \(g : a -> b)

-> (.) (Stream a) (Stream b) (Stream c) (map b c f) (map a b g)

)

)

-- Stream

( \(a : *)

-> forall (x : *)

-> (forall (s : *) -> s -> (s -> Pair a s) -> x)

-> x

)

-- map

( \(a : *)

-> \(b : *)

-> \(f : a -> b)

-> \( st

: forall (x : *)

-> (forall (s : *) -> s -> (s -> Pair a s) -> x)

-> x

)

-> \(x : *)

-> \(S : forall (s : *) -> s -> (s -> Pair b s) -> x)

-> st

x

( \(s : *)

-> \(seed : s)

-> \(step : s -> Pair a s)

-> S

s

seed

(\(seed@1 : s) -> first a b s f (step seed@1))

)

)

)

-- id

(\(a : *) -> \(va : a) -> va)

-- (.)

( \(a : *)

-> \(b : *)

-> \(c : *)

-> \(f : b -> c)

-> \(g : a -> b)

-> \(va : a)

-> f (g va)

)

-- Pair

(\(a : *) -> \(b : *) -> forall (x : *) -> (a -> b -> x) -> x)

-- P

( \(a : *)

-> \(b : *)

-> \(va : a)

-> \(vb : b)

-> \(x : *)

-> \(P : a -> b -> x)

-> P va vb

)

-- first

( \(a : *)

-> \(b : *)

-> \(c : *)

-> \(f : a -> b)

-> \(p : forall (x : *) -> (a -> c -> x) -> x)

-> \(x : *)

-> \(Pair : b -> c -> x)

-> p x (\(va : a) -> \(vc : c) -> Pair (f va) vc)

)

Both example@1 and example@2 will generate alpha-equivalent code:

$ morte < example1.mt∀(a : *) → (∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (a →

s → x) → x) → x) → x) → ∀(x : *) → (∀(s : *) → s → (s → ∀(x

: *) → (a → s → x) → x) → x) → x

λ(a : *) → λ(st : ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) →

(a → s → x) → x) → x) → x) → st

$ morte < example2.mt

∀(a : *) → (∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (a →

s → x) → x) → x) → x) → ∀(x : *) → (∀(s : *) → s → (s → ∀(x

: *) → (a → s → x) → x) → x) → x

λ(a : *) → λ(va : ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) →

(a → s → x) → x) → x) → x) → va

Similarly, example@3 and example@4 will generate alpha-equivalent code:

$ morte < example3.mt∀(a : *) → ∀(b : *) → ∀(c : *) → (b → c) → (a → b) → (∀(x :

*) → (∀(s : *) → s → (s → ∀(x : *) → (a → s → x) → x) → x) →

x) → ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (c → s → x)

→ x) → x) → x

λ(a : *) → λ(b : *) → λ(c : *) → λ(f : b → c) → λ(g : a → b)

→ λ(st : ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (a → s

→ x) → x) → x) → x) → λ(x : *) → λ(S : ∀(s : *) → s → (s → ∀

(x : *) → (c → s → x) → x) → x) → st x (λ(s : *) → λ(seed :

s) → λ(step : s → ∀(x : *) → (a → s → x) → x) → S s seed (λ(

seed@1 : s) → λ(x : *) → λ(Pair : c → s → x) → step seed@1 x

(λ(va : a) → Pair (f (g va)))))

$ morte < example4.mt

∀(a : *) → ∀(b : *) → ∀(c : *) → (b → c) → (a → b) → (∀(x :

*) → (∀(s : *) → s → (s → ∀(x : *) → (a → s → x) → x) → x) →

x) → ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (c → s → x)

→ x) → x) → x

λ(a : *) → λ(b : *) → λ(c : *) → λ(f : b → c) → λ(g : a → b)

→ λ(va : ∀(x : *) → (∀(s : *) → s → (s → ∀(x : *) → (a → s

→ x) → x) → x) → x) → λ(x : *) → λ(S : ∀(s : *) → s → (s → ∀

(x : *) → (c → s → x) → x) → x) → va x (λ(s : *) → λ(seed :

s) → λ(step : s → ∀(x : *) → (a → s → x) → x) → S s seed (λ(

seed@1 : s) → λ(x : *) → λ(Pair : c → s → x) → step seed@1 x

(λ(va : a) → Pair (f (g va))))

We inadvertently proved stream fusion for free, but we're still not done, yet! Everything we learn about recursive and corecursive sequences can be applied to model recursive and corecursive effects!

EffectsI will conclude this post by showing how to model both recursive and corecursive programs that have side effects. The recursive program will echo ninety-nine lines from stdin to stdout. The equivalent Haskell program is in the comment header:

-- recursive.mt-- The Haskell code we will translate to Morte:

--

-- import Prelude hiding (

-- (+), (*), IO, putStrLn, getLine, (>>=), (>>), return )

--

-- -- Simple prelude

--

-- data Nat = Succ Nat | Zero

--

-- zero :: Nat

-- zero = Zero

--

-- one :: Nat

-- one = Succ Zero

--

-- (+) :: Nat -> Nat -> Nat

-- Zero + n = n

-- Succ m + n = m + Succ n

--

-- (*) :: Nat -> Nat -> Nat

-- Zero * n = Zero

-- Succ m * n = n + (m * n)

--

-- foldNat :: Nat -> (a -> a) -> a -> a

-- foldNat Zero f x = x

-- foldNat (Succ m) f x = f (foldNat m f x)

--

-- data IO r

-- = PutStrLn String (IO r)

-- | GetLine (String -> IO r)

-- | Return r

--

-- putStrLn :: String -> IO U

-- putStrLn str = PutStrLn str (Return Unit)

--

-- getLine :: IO String

-- getLine = GetLine Return

--

-- return :: a -> IO a

-- return = Return

--

-- (>>=) :: IO a -> (a -> IO b) -> IO b

-- PutStrLn str io >>= f = PutStrLn str (io >>= f)

-- GetLine k >>= f = GetLine (\str -> k str >>= f)

-- Return r >>= f = f r

--

-- -- Derived functions

--

-- (>>) :: IO U -> IO U -> IO U

-- m >> n = m >>= \_ -> n

--

-- two :: Nat

-- two = one + one

--

-- three :: Nat

-- three = one + one + one

--

-- four :: Nat

-- four = one + one + one + one

--

-- five :: Nat

-- five = one + one + one + one + one

--

-- six :: Nat

-- six = one + one + one + one + one + one

--

-- seven :: Nat

-- seven = one + one + one + one + one + one + one

--

-- eight :: Nat

-- eight = one + one + one + one + one + one + one + one

--

-- nine :: Nat

-- nine = one + one + one + one + one + one + one + one + one

--

-- ten :: Nat

-- ten = one + one + one + one + one + one + one + one + one + one

--

-- replicateM_ :: Nat -> IO U -> IO U

-- replicateM_ n io = foldNat n (io >>) (return Unit)

--

-- ninetynine :: Nat

-- ninetynine = nine * ten + nine

--

-- main_ :: IO U

-- main_ = replicateM_ ninetynine (getLine >>= putStrLn)

-- "Free" variables

( \(String : * )

-> \(U : *)

-> \(Unit : U)

-- Simple prelude

-> ( \(Nat : *)

-> \(zero : Nat)

-> \(one : Nat)

-> \((+) : Nat -> Nat -> Nat)

-> \((*) : Nat -> Nat -> Nat)

-> \(foldNat : Nat -> forall (a : *) -> (a -> a) -> a -> a)

-> \(IO : * -> *)

-> \(return : forall (a : *) -> a -> IO a)

-> \((>>=)

: forall (a : *)

-> forall (b : *)

-> IO a

-> (a -> IO b)

-> IO b

)

-> \(putStrLn : String -> IO U)

-> \(getLine : IO String)

-- Derived functions

-> ( \((>>) : IO U -> IO U -> IO U)

-> \(two : Nat)

-> \(three : Nat)

-> \(four : Nat)

-> \(five : Nat)

-> \(six : Nat)

-> \(seven : Nat)

-> \(eight : Nat)

-> \(nine : Nat)

-> \(ten : Nat)

-> ( \(replicateM_ : Nat -> IO U -> IO U)

-> \(ninetynine : Nat)

-> replicateM_ ninetynine ((>>=) String U getLine putStrLn)

)

-- replicateM_

( \(n : Nat)

-> \(io : IO U)

-> foldNat n (IO U) ((>>) io) (return U Unit)

)

-- ninetynine

((+) ((*) nine ten) nine)

)

-- (>>)

( \(m : IO U)

-> \(n : IO U)

-> (>>=) U U m (\(_ : U) -> n)

)

-- two

((+) one one)

-- three

((+) one ((+) one one))

-- four

((+) one ((+) one ((+) one one)))

-- five

((+) one ((+) one ((+) one ((+) one one))))

-- six

((+) one ((+) one ((+) one ((+) one ((+) one one)))))

-- seven

((+) one ((+) one ((+) one ((+) one ((+) one ((+) one one))))))

-- eight

((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one one)))))))

-- nine

((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one one))))))))

-- ten

((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one ((+) one one)))))))))

)

-- Nat

( forall (a : *)

-> (a -> a)

-> a

-> a

)

-- zero

( \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> Zero

)

-- one

( \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> Succ Zero

)

-- (+)

( \(m : forall (a : *) -> (a -> a) -> a -> a)

-> \(n : forall (a : *) -> (a -> a) -> a -> a)

-> \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> m a Succ (n a Succ Zero)

)

-- (*)

( \(m : forall (a : *) -> (a -> a) -> a -> a)

-> \(n : forall (a : *) -> (a -> a) -> a -> a)

-> \(a : *)

-> \(Succ : a -> a)

-> \(Zero : a)

-> m a (n a Succ) Zero

)

-- foldNat

( \(n : forall (a : *) -> (a -> a) -> a -> a)

-> n

)

-- IO

( \(r : *)

-> forall (x : *)

-> (String -> x -> x)

-> ((String -> x) -> x)

-> (r -> x)

-> x

)

-- return

( \(a : *)

-> \(va : a)

-> \(x : *)

-> \(PutStrLn : String -> x -> x)

-> \(GetLine : (String -> x) -> x)

-> \(Return : a -> x)

-> Return va

)

-- (>>=)

( \(a : *)

-> \(b : *)

-> \(m : forall (x : *)

-> (String -> x -> x)

-> ((String -> x) -> x)

-> (a -> x)

-> x

)

-> \(f : a

-> forall (x : *)

-> (String -> x -> x)

-> ((String -> x) -> x)

-> (b -> x)

-> x

)

-> \(x : *)

-> \(PutStrLn : String -> x -> x)

-> \(GetLine : (String -> x) -> x)

-> \(Return : b -> x)

-> m x PutStrLn GetLine (\(va : a) -> f va x PutStrLn GetLine Return)

)

-- putStrLn

( \(str : String)

-> \(x : *)

-> \(PutStrLn : String -> x -> x )

-> \(GetLine : (String -> x) -> x)

-> \(Return : U -> x)

-> PutStrLn str (Return Unit)

)

-- getLine

( \(x : *)

-> \(PutStrLn : String -> x -> x )

-> \(GetLine : (String -> x) -> x)

-> \(Return : String -> x)

-> GetLine Return

)

)

This program will compile to a completely unrolled read-write loop, as most recursive programs will:

$ morte < recursive.mt∀(String : *) → ∀(U : *) → U → ∀(x : *) → (String → x → x) →

((String → x) → x) → (U → x) → x

λ(String : *) → λ(U : *) → λ(Unit : U) → λ(x : *) → λ(PutStr

Ln : String → x → x) → λ(GetLine : (String → x) → x) → λ(Ret

urn : U → x) → GetLine (λ(va : String) → PutStrLn va (GetLin

e (λ(va@1 : String) → PutStrLn va@1 (GetLine (λ(va@2 : Strin

g) → PutStrLn va@2 (GetLine (λ(va@3 : String) → PutStrLn ...

<snip>

... GetLine (λ(va@92 : String) → PutStrLn va@92 (GetLine (λ(

va@93 : String) → PutStrLn va@93 (GetLine (λ(va@94 : String)

→ PutStrLn va@94 (GetLine (λ(va@95 : String) → PutStrLn va@

95 (GetLine (λ(va@96 : String) → PutStrLn va@96 (GetLine (λ(

va@97 : String) → PutStrLn va@97 (GetLine (λ(va@98 : String)

→ PutStrLn va@98 (Return Unit))))))))))))))))))))))))))))))

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

))))))))))))))))))))))))))))))))))))))))))))))))

In contrast, if we encode the effects corecursively we can express a program that echoes indefinitely from stdin to stdout:

-- corecursive.mt-- data IOF r s

-- = PutStrLn String s

-- | GetLine (String -> s)

-- | Return r

--

-- data IO r = forall s . MkIO s (s -> IOF r s)

--

-- main = MkIO

-- Nothing

-- (maybe (\str -> PutStrLn str Nothing) (GetLine Just))

( \(String : *)

-> ( \(Maybe : * -> *)

-> \(Just : forall (a : *) -> a -> Maybe a)

-> \(Nothing : forall (a : *) -> Maybe a)

-> \( maybe

: forall (a : *)

-> Maybe a

-> forall (x : *)

-> (a -> x)

-> x

-> x

)

-> \(IOF : * -> * -> *)

-> \( PutStrLn

: forall (r : *)

-> forall (s : *)

-> String

-> s

-> IOF r s

)

-> \( GetLine

: forall (r : *)

-> forall (s : *)

-> (String -> s)

-> IOF r s

)

-> \( Return

: forall (r : *)

-> forall (s : *)

-> r

-> IOF r s

)

-> ( \(IO : * -> *)

-> \( MkIO

: forall (r : *)

-> forall (s : *)

-> s

-> (s -> IOF r s)

-> IO r

)

-> ( \(main : forall (r : *) -> IO r)

-> main

)

-- main

( \(r : *)

-> MkIO

r

(Maybe String)

(Nothing String)

( \(m : Maybe String)

-> maybe

String

m

(IOF r (Maybe String))

(\(str : String) ->

PutStrLn

r

(Maybe String)

str

(Nothing String)

)

(GetLine r (Maybe String) (Just String))

)

)

)

-- IO

( \(r : *)

-> forall (x : *)

-> (forall (s : *) -> s -> (s -> IOF r s) -> x)

-> x

)

-- MkIO

( \(r : *)

-> \(s : *)

-> \(seed : s)

-> \(step : s -> IOF r s)

-> \(x : *)

-> \(k : forall (s : *) -> s -> (s -> IOF r s) -> x)

-> k s seed step

)

)

-- Maybe

(\(a : *) -> forall (x : *) -> (a -> x) -> x -> x)

-- Just

( \(a : *)

-> \(va : a)

-> \(x : *)

-> \(Just : a -> x)

-> \(Nothing : x)

-> Just va

)

-- Nothing

( \(a : *)

-> \(x : *)

-> \(Just : a -> x)

-> \(Nothing : x)

-> Nothing

)

-- maybe

( \(a : *)

-> \(m : forall (x : *) -> (a -> x) -> x-> x)

-> m

)

-- IOF

( \(r : *)

-> \(s : *)

-> forall (x : *)

-> (String -> s -> x)

-> ((String -> s) -> x)

-> (r -> x)

-> x

)

-- PutStrLn

( \(r : *)

-> \(s : *)

-> \(str : String)

-> \(vs : s)

-> \(x : *)

-> \(PutStrLn : String -> s -> x)

-> \(GetLine : (String -> s) -> x)

-> \(Return : r -> x)

-> PutStrLn str vs

)

-- GetLine

( \(r : *)

-> \(s : *)

-> \(k : String -> s)

-> \(x : *)

-> \(PutStrLn : String -> s -> x)

-> \(GetLine : (String -> s) -> x)

-> \(Return : r -> x)

-> GetLine k

)

-- Return

( \(r : *)

-> \(s : *)

-> \(vr : r)

-> \(x : *)

-> \(PutStrLn : String -> s -> x)

-> \(GetLine : (String -> s) -> x)

-> \(Return : r -> x)

-> Return vr

)

)

This compiles to a state machine that we can unfold one step at a time:

$ morte < corecursive.mt∀(String : *) → ∀(r : *) → ∀(x : *) → (∀(s : *) → s → (s → ∀

(x : *) → (String → s → x) → ((String → s) → x) → (r → x) →

x) → x) → x

λ(String : *) → λ(r : *) → λ(x : *) → λ(k : ∀(s : *) → s → (

s → ∀(x : *) → (String → s → x) → ((String → s) → x) → (r →

x) → x) → x) → k (∀(x : *) → (String → x) → x → x) (λ(x : *)

→ λ(Just : String → x) → λ(Nothing : x) → Nothing) (λ(m : ∀

(x : *) → (String → x) → x → x) → m (∀(x : *) → (String → (∀

(x : *) → (String → x) → x → x) → x) → ((String → ∀(x : *) →

(String → x) → x → x) → x) → (r → x) → x) (λ(str : String)

→ λ(x : *) → λ(PutStrLn : String → (∀(x : *) → (String → x)

→ x → x) → x) → λ(GetLine : (String → ∀(x : *) → (String → x

) → x → x) → x) → λ(Return : r → x) → PutStrLn str (λ(x : *)

→ λ(Just : String → x) → λ(Nothing : x) → Nothing)) (λ(x :

*) → λ(PutStrLn : String → (∀(x : *) → (String → x) → x → x)

→ x) → λ(GetLine : (String → ∀(x : *) → (String → x) → x →

x) → x) → λ(Return : r → x) → GetLine (λ(va : String) → λ(x

: *) → λ(Just : String → x) → λ(Nothing : x) → Just va))

I don't expect you to understand that output other than to know that we can translate the output to any backend that provides functions, and primitive read/write operations.

ConclusionIf you would like to use Morte, you can find the library on both Github and Hackage. I also provide a Morte tutorial that you can use to learn more about the library.

Morte is dependently typed in theory, but in practice I have not exercised this feature so I don't understand the implications of this. If this turns out to be a mistake then I will downgrade Morte to System Fw, which has higher-kinds and polymorphism, but no dependent types.

Additionally, Morte might be usable to transmit code in a secure and typed way in distributed environment or to share code between diverse functional language by providing a common intermediate language. However, both of those scenarios require additional work, such as establishing a shared set of foreign primitives and creating Morte encoders/decoders for each target language.

Also, there are additional optimizations which Morte might implement in the future. For example, Morte could use free theorems (equalities you deduce from the types) to simplify some code fragments even further, but Morte currently does not do this.

My next goals are:

- Add a back-end to compile Morte to LLVM
- Add a front-end to desugar a medium-level Haskell-like language to Morte

Once those steps are complete then Morte will be a usable intermediate language for writing super-optimizable programs.

Also, if you're wondering, the name Morte is a tribute to a talking skull from the game Planescape: Torment, since the Morte library is a "bare-bones" calculus of constructions.

LiteratureIf this topic interests you more, you may find the following links helpful, in roughly increasing order of difficulty:

- Data and Codata - A blog post by Dan Piponi introducing the notions of data and codata
- Church encoding - A wikipedia article on church encoding (converting things to lambda expressions)
- Total Functional Programming - A paper by D. A. Turner on total programming using data and codata
- Recursive types for free! - An unpublished draft by Philip Wadler about F-algebras and F-coalgebras
- Understanding F algebras - A blog post by Bartosz Milewski
- Beyond Church encoding: Boehm-Berarducci isomorphism of algebraic data types and polymorphic lambda-terms - Oleg Kiselyov's collection of notes on Boehm-Berarducci encoding, a more complete version of Church encoding
- F-algebras and F-coalgebras - wikipedia articles that are short, sweet, and utterly impenetrable unless you already understand the subject