Skip to content

Instantly share code, notes, and snippets.

@milmazz

milmazz/func_geo.livemd

Created March 7, 2022 14:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save milmazz/b771f8e27d6a7b21c035eaa983e089c3 to your computer and use it in GitHub Desktop.
Save milmazz/b771f8e27d6a7b21c035eaa983e089c3 to your computer and use it in GitHub Desktop.
Download ZIP
Functional Geometry
Raw
func_geo.livemd

Functional Geometry

Installation

Mix.install([
  {:func_geo, github: "milmazz/func_geo"},
  {:kino, "~> 0.5.0"}
])

Introduction

Some years ago I saw the [keynote presentation][whyfp-video] given by [John Hughes][john-hughes] at the [Erlang Factory SF Bay 2016][sfbay2016] conference. J. Hughes is the author of the very well-known paper [Why Functional Programming Matters][whyfp90] (1990), at the end of that talk, J. Hughes mentioned some other papers that he liked and their importance, one paper that caught my attention was Functional Geometry by [Peter Henderson][ph], the idea of this article is to explain how I implemented these concepts with Elixir.

Peter Henderson's paper ([revisited version][funcgeo2], [original version][funcgeo]) deconstructs the [M.C. Escher][m-c-escher]'s woodcut [Square Limit][square-limit] using an algebra of pictures. The author also mentions that these ideas are applied to many more complex domains such as music or animation.

A picture is an example of a complex object that can be described in terms of its parts. Yet a picture needs to be rendered on a printer or a screen by a device that expects to be given a sequence of commands. Programming that sequence of commands directly is much harder than having an application generate the commands automatically from the simpler, denotational description.

Basic operations

  • rot(picture) :: picture
  • flip(picture) :: picture
  • rot45(picture) :: picture
  • above(picture, picture) :: picture
  • beside(picture, picture) :: picture
  • over(picture, picture) :: picture

$$over(p, q)(a, b, c) = p(a, b, c) \cup q(a, b, c)$$

$$blank(a, b, c) = \text{{}}$$

$$beside(p, q)(a, b, c) = p(a, \frac{b}{2}, c) \cup q(a + \frac{b}{2}, \frac{b}{2}, c)$$

$$above(p, q)(a, b, c) = p(a, b, \frac{c}{2}) \cup q (a + \frac{c}{2}, b, \frac{c}{2})$$

$$rot(p)(a, b, c) = p(a + b, c, -b)$$

$$flip(p)(a, b, c) = p(a + b, -b, c)$$

$$rot45(p)(a, b, c) = p(a + \frac{b + c}{2}, \frac{b + c}{2}, \frac{c - b}{2})$$

For completeness, they mention this two operations:

$$beside(m, n, p, q)(a, b, c) = p(a, b * m/(m + n), c) \cup q(a + b * m/(m + n), b * n/(m + n), c)$$

$$above(m, n, p, q)(a, b, c) = p(a + c * n/(m + n), b, c * m/(m + n)) \cup q(a, b, c * n/(m + n))$$

Some tests that they recommend in the paper are the following:

$$rot(rot(rot(rot(p)))) = p$$

$$rot(above(p, q)) = beside(rot(p), rot(q))$$

$$rot(beside(p, q)) = above(rot(q), rot(p))$$

$$flip(beside(p, q)) = beside(flip(q), flip(p))$$

Unit tests

Let's try to convert the previous laws into tests in Elixir. But first, let's define a helper to wrap some images.

defmodule ImageHelper do
  import FuncGeo

  def man do
    grid(
      14,
      20,
      polygon([
        {6, 10},
        {0, 10},
        {0, 12},
        {6, 12},
        {6, 14},
        {4, 16},
        {4, 18},
        {6, 20},
        {8, 20},
        {10, 18},
        {10, 16},
        {8, 14},
        {8, 12},
        {10, 12},
        {10, 14},
        {12, 14},
        {12, 10},
        {8, 10},
        {8, 8},
        {10, 0},
        {8, 0},
        {7, 4},
        {6, 0},
        {4, 0},
        {6, 8}
      ])
    )
  end

  def f do
    grid(
      7,
      7,
      polygon([{2, 1}, {2, 6}, {5, 6}, {5, 5}, {3, 5}, {3, 4}, {4, 4}, {4, 3}, {3, 3}, {3, 1}])
    )
  end

  def p do
    grid(16, 16, [
      {{4, 4}, {6, 0}},
      {{0, 3}, {3, 4}},
      {{3, 4}, {0, 8}},
      {{0, 8}, {0, 3}},
      {{4, 5}, {7, 6}},
      {{7, 6}, {4, 10}},
      {{4, 10}, {4, 5}},
      {{11, 0}, {10, 4}},
      {{10, 4}, {8, 8}},
      {{8, 8}, {4, 13}},
      {{4, 13}, {0, 16}},
      {{11, 0}, {14, 2}},
      {{14, 2}, {16, 2}},
      {{10, 4}, {13, 5}},
      {{13, 5}, {16, 4}},
      {{9, 6}, {12, 7}},
      {{12, 7}, {16, 6}},
      {{8, 8}, {12, 9}},
      {{12, 9}, {16, 8}},
      {{8, 12}, {16, 10}},
      {{0, 16}, {6, 15}},
      {{6, 15}, {8, 16}},
      {{8, 16}, {12, 12}},
      {{12, 12}, {16, 12}},
      {{10, 16}, {12, 14}},
      {{12, 14}, {16, 13}},
      {{12, 16}, {13, 15}},
      {{13, 15}, {16, 14}},
      {{14, 16}, {16, 15}}
    ])
  end

  def q do
    grid(16, 16, [
      {{2, 0}, {4, 5}},
      {{4, 5}, {4, 7}},
      {{4, 0}, {6, 5}},
      {{6, 5}, {6, 7}},
      {{6, 0}, {8, 5}},
      {{8, 5}, {8, 8}},
      {{8, 0}, {10, 6}},
      {{10, 6}, {10, 9}},
      {{10, 0}, {14, 11}},
      {{12, 0}, {13, 4}},
      {{13, 4}, {16, 8}},
      {{16, 8}, {15, 10}},
      {{15, 10}, {16, 16}},
      {{16, 16}, {12, 10}},
      {{12, 10}, {6, 7}},
      {{6, 7}, {4, 7}},
      {{4, 7}, {0, 8}},
      {{13, 0}, {16, 6}},
      {{14, 0}, {16, 4}},
      {{15, 0}, {16, 2}},
      {{0, 10}, {7, 11}},
      {{9, 12}, {10, 10}},
      {{10, 10}, {12, 12}},
      {{12, 12}, {9, 12}},
      {{8, 15}, {9, 13}},
      {{9, 13}, {11, 15}},
      {{11, 15}, {8, 15}},
      {{0, 12}, {3, 13}},
      {{3, 13}, {7, 15}},
      {{7, 15}, {8, 16}},
      {{2, 16}, {3, 13}},
      {{4, 16}, {5, 14}},
      {{6, 16}, {7, 15}}
    ])
  end

  def r do
    grid(16, 16, [
      {{0, 12}, {1, 14}},
      {{0, 8}, {2, 12}},
      {{0, 4}, {5, 10}},
      {{0, 0}, {8, 8}},
      {{1, 1}, {4, 0}},
      {{2, 2}, {8, 0}},
      {{3, 3}, {8, 2}},
      {{8, 2}, {12, 0}},
      {{5, 5}, {12, 3}},
      {{12, 3}, {16, 0}},
      {{0, 16}, {2, 12}},
      {{2, 12}, {8, 8}},
      {{8, 8}, {14, 6}},
      {{14, 6}, {16, 4}},
      {{6, 16}, {11, 10}},
      {{11, 10}, {16, 6}},
      {{11, 16}, {12, 12}},
      {{12, 12}, {16, 8}},
      {{12, 12}, {16, 16}},
      {{13, 13}, {16, 10}},
      {{14, 14}, {16, 12}},
      {{15, 15}, {16, 14}}
    ])
  end

  def s do
    grid(16, 16, [
      {{0, 0}, {4, 2}},
      {{4, 2}, {8, 2}},
      {{8, 2}, {16, 0}},
      {{0, 4}, {2, 1}},
      {{0, 6}, {7, 4}},
      {{0, 8}, {8, 6}},
      {{0, 10}, {7, 8}},
      {{0, 12}, {7, 10}},
      {{0, 14}, {7, 13}},
      {{8, 16}, {7, 13}},
      {{7, 13}, {7, 8}},
      {{7, 8}, {8, 6}},
      {{8, 6}, {10, 4}},
      {{10, 4}, {16, 0}},
      {{10, 16}, {11, 10}},
      {{10, 6}, {12, 4}},
      {{12, 4}, {12, 7}},
      {{12, 7}, {10, 6}},
      {{13, 7}, {15, 5}},
      {{15, 5}, {15, 8}},
      {{15, 8}, {13, 7}},
      {{12, 16}, {13, 13}},
      {{13, 13}, {15, 9}},
      {{15, 9}, {16, 8}},
      {{13, 13}, {16, 14}},
      {{14, 11}, {16, 12}},
      {{15, 9}, {16, 10}}
    ])
  end
end

With the previous helper, we can add some unit tests.

ExUnit.start(autorun: false)
defmodule FuncGeoTest do
  use ExUnit.Case, async: true

  import FuncGeo

  @point [{0, 0}, {1, 0}, {0, 1}]

  setup_all do
    %{man: ImageHelper.man()}
  end

  test "p is equal after four continuos rotations", %{man: man} do
    man_rotated = man |> rot() |> rot() |> rot() |> rot()

    assert apply(man_rotated, @point) == apply(man, @point)
  end

  test "rot(above(p, q)) must be equal to beside(rot(p), rot(q))", %{man: man} do
    man_rotated = rot(above(man, man))
    man_beside = beside(rot(man), rot(man))

    assert apply(man_rotated, @point) == apply(man_beside, @point)
  end

  test "rot(beside(p, q)) must be equal to above(rot(q), rot(p))", %{man: man} do
    man_rotated = rot(beside(man, man))
    man_above = above(rot(man), rot(man))

    assert apply(man_rotated, @point) == apply(man_above, @point)
  end

  test "flip(beside(p, q)) must be equal to beside(flip(q), flip(p))", %{man: man} do
    flipped = flip(beside(man, man))
    man_beside = beside(flip(man), flip(man))

    assert apply(flipped, @point) == apply(man_beside, @point)
  end

  test "over(man, man) must be equal to over(man, blank())", %{man: man} do
    o = over(man, man)
    b = over(man, blank())

    assert apply(o, @point) == apply(b, @point)
  end
end

Now, that we have a few unit tests in place, let's run those and check if the implementation satisfies the previous laws.

ExUnit.run()

Square Limit

import FuncGeo

points = [{0, 0}, {1, 0}, {0, 1}]

draw = fn image -> image |> apply(points) |> as_svg() |> Kino.Image.new(:svg) end

p = ImageHelper.p()

draw.(p)
q = ImageHelper.q()

draw.(q)
r = ImageHelper.r()
draw.(r)
s = ImageHelper.s()
draw.(s)
# Build the drawing of the fish out of the parts defined above
t = quartet(p, q, r, s)

draw.(t)
side1 = quartet(blank(), blank(), rot(t), t)

draw.(side1)
side2 = quartet(side1, side1, rot(t), t)

draw.(side2)
u = q |> rot() |> cycle()

draw.(u)
corner1 = quartet(blank(), blank(), blank(), u)

draw.(corner1)
corner2 = quartet(corner1, side1, rot(side1), u)

draw.(corner2)
corner = nonet(corner2, side2, side2, rot(side2), u, rot(t), rot(side2), rot(t), rot(q))

draw.(corner)
corner
|> cycle()
|> apply(points)
|> as_svg()
|> Kino.Image.new(:svg)

Other implementations

  • [Lisp][lisp] by Frank Buß
  • [F#][fsharp] by Satnam Singh
  • [Python][python] and [Haskell][haskell] by Will McCutchen
  • [Julia][julia] by Shashi Gowda
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment