29 Mar 2021
This contribution is a new feature.
This contribution adds pipe operator
|> support to the Caramel language.
Here is a summary of the different steps in a compiler:
- Lexing the source into tokens
- Parsing the token stream into an AST (abstract syntax tree)
- Validating the AST
- Translating the AST
In many functional programming languages, it is a common way to compose functions into a readable left-to-right "pipeline" of steps of computation.
The code blocks are intentionally incomplete for the sake of readability.
If you want to read the full code you'll find it in the PR link at the top.
This PR being still Open, some parts are likely to change.
I will keep the article updated if any changes are made.
The first idea was to expose the pipe operator as an external that maps to a
Here is the pipe operator signature:
Here is the pipe operator definition:
We will tell the compiler to map
|> to our caramel_runtime pipe function:
Finally given this input:
It will output:
Look how the compiler has replaced our pipes.
The problem was that we needed to first implement partial application to make it work.
Partial application involves passing less than the full number of arguments to a function.
addOne is the result of partially applying
It is a function that takes an integer
b and return
b + 1.
In our example,
Divide arr called with less arguments that they have to take.
So we went for another solution: rewrite the pipes into SSA (static single assignment).
The translation phase is broken down into 3 phases:
- The AST is lowered into an IR (intermediate representation)
- The IR is analyzed
- The IR is translated
SSA introduces a new constraint: all variables are assigned exactly once.
The idea is to go from this:
To something like this:
For now we will implement this logic in the ocaml translation side.
The goal is to go from
a |> f |> g to
let a_f = f a in let a_f_g = g a_f.
caramel/compiler/ocaml_to_erlang/fun.ml there is a match clause for the function application.
We will add a special case for the pipe operator.
The idea is to check if the
name variable is the pipe function and then do our logic to bind the result of
f x to a new variable with a unique name.
The final result allows us to compose our function pipeline in this way:
Understanding how the compiler works was the step that took me the most time.
It required me to understand a codebase I'm not used to deal with.
This contribution allowed me to review some concepts about compilers and functional programming languages.