A Haskell implementation of John Backus's FP (Functional Programming) system.
FP is a programming language introduced by John Backus in his 1977 Turing Award lecture, "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs".
FP takes a radically different approach from conventional languages. Instead of building programs from statements that manipulate variables, FP builds programs entirely by composing functions. There are no variables, no assignment, and no explicit iteration — only functions applied to data and combined through a fixed set of functional forms (higher-order operators).
Key ideas:
- Programs are functions. A program takes a single input and produces a single output.
- Functional forms combine functions. Composition (
.), construction ([f, g, h]), apply-to-all (@f), insert (/f), and condition (if p -> f ; g) are the building blocks for constructing complex programs from simpler ones. - Algebra of programs. Because programs are defined purely through composition, they can be reasoned about and transformed algebraically, much like mathematical expressions.
Requires GHC >= 9.6 and Cabal >= 3.0.
cabal build
fp-exe FILE [-v|--verbose]
Write your FP program in a file and pass it as an argument. Use -v to print the parsed AST
before evaluation.
$ cabal run fp-exe -- examples/fac.fp
120
| Type | Syntax | Examples |
|---|---|---|
| Number | integer literal | 0, 1, 42 |
| Boolean | T or F |
T, F |
| Symbol | uppercase name | A, FOO, HELLO |
| Sequence | <v1, v2, ...> |
<1,2,3>, <A,B> |
Bottom (⊥) represents an undefined or error value and propagates through computation.
A function is applied to a value with the : operator:
+:<1,2> => 3
tl:<A,B,C> => <B,C>
User-defined functions are declared with Def:
Def square = *.[id, id]
square:5 => 25
Definitions must appear before the expression. Recursion is supported:
Def fac = if eq0->_1;*.[id, fac.sub1]
Def eq0 = eq.[id,_0]
Def sub1 = -.[id,_1]
fac:5 => 120
| Form | Syntax | Description |
|---|---|---|
| Composition | f . g |
Apply g first, then f to the result |
| Construction | [f, g, h] |
Apply each function to the input, collect as sequence |
| Condition | if p -> f ; g |
If p returns T, apply f; otherwise g |
| Apply-to-all | @f |
Map f over each element of a sequence |
| Insert | /f |
Reduce a sequence with f (left fold) |
| Constant | _x |
Always returns x, ignoring the input |
| Binary-to-unary | bu f x |
Fix the first argument of f to x |
| While | while p f |
Repeatedly apply f while p returns T |
Arithmetic: +, -, *, div
Selection: N (1-indexed, e.g., 1, 2, 3), Nr (from the right, e.g., 1r, 2r)
Sequence: tl (tail), tlr (tail right), reverse, rotl (rotate left), rotr (rotate right),
length, apndl (append left), apndr (append right), distl (distribute left),
distr (distribute right), trans (transpose)
Predicates: eq, atom, null, not, and, or
Identity: id
+:<1,2> => 3
@length:<<A>, <A,B>, <A,B,C>> => <1,2,3>
/+:<4,5,6> => 15
distl:<A, <1,2,3,4>> => <<A,1>,<A,2>,<A,3>,<A,4>>
trans:<<1,2,3>,<4,5,6>,<7,8,9>> => <<1,4,7>,<2,5,8>,<3,6,9>>
See the examples/ directory for more.
- Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs — John Backus, 1977 Turing Award Lecture