+TITLE: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:

• [[http://www.golfscript.com/lam/][Universal Lambda page]].

• Justine Tunney's [[https://justine.lol/lambda/][SectorLambda page]].

• Hikaru Ikuta's [[https://github.com/woodrush/lambdacraft][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~ 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

  +begin_src lisp

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

  +end_src

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

  +begin_src

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

  +end_src

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

  +begin_src

  first = compose car (0 cdr)

  +end_src

  and not

  +begin_src

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

  +end_src

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

• Acknowledgements

• Many logical combinators come from [[https://wiki.xxiivv.com/site/logic][Devine Lu Linvega logic page]].

• Lists (and ~foldr~ especially) come from the [[http://www.golfscript.com/lam/][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.