Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Efficient compilation of function definitions with pattern-matching using case-expressions.

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