stdlambda—Standard Library for Lamdba Calculus

Lambda Calculus is an inspiring idea, but most of the resources about it list just a couple of utilities and ways to encode data, without getting deep enough into building a practical set of primitives. stdlambda tries to do just that: provide a more or less practical set of primitives for programming in Lambda Calculus. Included are:

• Frequent combinators like S, K, I, and Y.
• Church Booleans and all the possible logical operations on them.
• Church Numerals and arithmetics on them.
  • List-encoded numerals might be provided in the future.
• Church Pairs (with an opinionated nil = false) and Haskell/Lisp-inspired utilities on them.
  • nil = λx.true pairs might be provided in the future.

Note that stdlambda is mostly deprecated by Lamber and its extensive standard library. Also note that the code is slightly more readable there, having multi-letter variables &c.

Sources of inspiration and code:

• Universal Lambda page.
• Justine Tunney’s SectorLambda page.
• Hikaru Ikuta’s Lambdacraft

Getting Started

• Feed the definitions from provided files into your Lambda Calculus interpreter. The files (and their interdependencies) are:

  combinators.lambda

  Logical/stack combinators, no deps.

  bool.lambda

  Boolean ops, no deps.

  numbers.lambda

  Numeric, arithmetics. Depends on combinators.lambda and bool.lambda.

  cons.lambda

  Conses. Depends on bool.lambda.

  list.lambda

  Linked lists and utils for them. Mostly fold operations. Depends on cons.lambda, numbers.lambda, combinators.lambda, bool.lambda.

  set.lambda

  Operations on lists-as-sets. Depends on list.lambda and its transitive dependencies.

  alist.lambda

  Associative (key-value) lists. Depends on cons.lambda and combinators.lambda.

  alias.lambda

  Aliases for all of the above.

• Run the code using these primitives. Say

fac = Y λr.λn.(if (=0 n) 1 (× n (r (1- n))))
(fac 5)

Format

The format is the single-letter single-argument lambdas. The approximate regex would be:

.* = (λ[a-z]\.)*.*

Not all function applications are enclosed into parentheses and not all applications are single-argument. Example:

first = compose car (0 cdr)

and not

first = ((compose car) (0 cdr))

It’s too much work to maintain such a code. I might reconsider that in the future, though.

Acknowledgements

• Many logical combinators come from Devine Lu Linvega logic page.
• Lists (and foldr especially) come from the Golfscript Universal Lambda page.
• Many list primitives and names for things come from Common Lisp and Scheme.
  • Things like conjoin and compose especially come from Alexandria library.