Skip to content

Standard library for Lambda Calculus, finally making LC a practical programming language.

License

Notifications You must be signed in to change notification settings

aartaka/stdlambda

Repository files navigation

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.

Sources of inspiration and code:

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 and combinators.lambda.
    alist.lambda
    Associative (key-value) lists. Depends on cons.lambda and combinators.lambda.
    stack.lambda
    Operations/combinators from stack languages.
    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

About

Standard library for Lambda Calculus, finally making LC a practical programming language.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published