Skip to content

Instantly share code, notes, and snippets.

@thealmarty

thealmarty/PatternMatchingCompilerAlgorithm.md

Last active September 22, 2020 19:58
Show Gist options
  • Save thealmarty/9c2eb443d37fafe32c7dfbfc21d9f6cc to your computer and use it in GitHub Desktop.
Save thealmarty/9c2eb443d37fafe32c7dfbfc21d9f6cc to your computer and use it in GitHub Desktop.
Download ZIP
Efficient compilation of function definitions with pattern-matching using case-expressions.
Raw
PatternMatchingCompilerAlgorithm.md

Efficient compilation of function definitions with pattern-matching

Function definitions with pattern-matching can be compiled into case-expressions for more efficient evaluation using the pattern matching compiler algorithm. The algorithm translates function definitions into case-expressions and avoids repeated examination of patterns.

I summarize the pattern matching compiler algorithm here as in chapter 5 of The implementation of functional programming languages.

The algorithm

A function definition of the form

f p1,1 ... p1,n = E1
...
f pm,1 ... pm,n = Em

can be translated into the enriched lambda calculus definition

f = λu1...λun.((λp1,1'...λp1,n'.E1') u1...un)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment