Literate programming using Documenter.jl and Entangled

Johannes Hidding — Sun, 04 Dec 2022 09:46:28 +0000

Here I explain my workflow for literate programming in Julia using Documenter.jl and Entangled

Literate Programming

Literate programming is a method of programming where you write all your code in a markup document (traditionally LaTeX, but these days Markdown is the obvious choice) in the form of code blocks. The technique has been popularised in a weaker form by the use of notebooks. There are some fundamental problems with the way notebooks are used. Joel Grus explains this very eloquently: I don't like notebooks.

Real literate programming works with a system of references. This form of literate programming is completely generic over languages, and much more powerful than what you can do with Literate.jl for instance. You give every code block a name. In Markdown this can be done by annotating code blocks with identifiers:

``` {.julia #pythagoras}
sqrt(x^2 + y^2)
```

We can reference this code block in other blocks as follows:

``` {.julia #hypothenuse}
hypothenuse(x, y) =
     <<pythagoras>>
```

We can build a complete program by annotating file output:

``` {.julia file=src/Geometry.jl}
module Geometry
<<hypothenuse>>
end  # module
```

This system of references was pioneered by Donald Knuth, and simplified by Norman Ramsey in Noweb.

I have developed a tool called Entangled that helps with writing literate programs. It is a daemon that watches your Markdown files for changes and keeps the tangled source code up-to-date. Even better, if you then change any of the tangled source files, these changes are automatically merged back into your markdown.

Usually I combine Entangled with Pandoc, but when the main language is Julia, Entangled also works together really well with Documenter.jl.

Howto combine with `Documenter.jl`

Traditional documentation in Julia is usualy made using the Documenter module. This has features for doc-testing and also inline code evaluation that combine well with Entangled. All it needs is a little bit extra scripting to annotate the code blocks in the generated output.

I use an Awk script to filter the Markdown source files, so that annotations are added where needed. To run this pass before the rest of Documenter.jl I have customized make.jl.

Since we are celebrating the happy Yule tide of Advent of Code, I have my Julia solutions in literate form. Enjoy!

Computing polynomials: outperforming C++

Johannes Hidding — Thu, 01 Dec 2022 14:13:37 +0000

When you want to convince people that Julia is the best language for some task, some are easily swayed by the beautiful syntax, rank polymorphism, and flirtations with functional programming. In all honesty, those people need little convincing. Others want to see hard numbers!

Here's a very small demo that shows how Julia can outperform any traditional language: computing polynomials.

Suppose we have a function described by

\sum c_i x^i,

where we have the coefficients stored in some dense vector.

struct Polynomial{T}
    c::Vector{T}
end

We can evaluate this function as follows:

function (f::Polynomial{T})(x::T) where T<:Number
    result = f.c[1]
    xpow = x
    for c in f.c[2:end-1]
        result += xpow * c
        xpow *= x
    end
    result + xpow * f.c[end]
end

This is very much how you would implement such a function in most other languages. In Julia however, we can do something much nicer: generate a function.

function expand(f::Polynomial{T}) where T<:Number
    :(function (x::$T)
        r = $(f.c[1])
        xp = x
        $((:(r += xp*$c; xp*=x) for c in f.c[2:end-1])...)
        r + xp * $(f.c[end])
    end)
end

Now, when we expand(f), say we have f = Polynomial(1.0, 0.5, 0.333, 0.25) the generated function will look as follows:

:(function (x::Float64,)
      r = 1.0
      xp = x
      begin
          r += xp * 0.5
          xp *= x
      end
      begin
          r += xp * 0.333
          xp *= x
      end
      r + xp * 0.25
  end)

To run this, we say f_unroll = eval(expand(f)). Not only does this run much faster than our previous loopy implementation, it even outperforms C++ (GCC at -O3) by more than a factor of two (depending on your machine). The reason is that we have no loop in our generated code, and more importantly, we are not accessing any memory. We have done something that a C++ programmer wouldn't dream of doing: write a code generator, compile the specialised code, and fly to the moon!

A completely literate and Documentered implementation of this demo can be found here.

Edit: Thanks to Nicos Pitsianis for point out to me that there is a more efficient method called Horner's method. This method applies to both Julia and C++ implementations, reducing the amount of multiplications needed. Using this method reduces the difference between Julia and C++ a little bit, but increasing the order of the polynomial grows it back again.

Julia Community 🟣: Johannes Hidding

Literate programming using Documenter.jl and Entangled