# LambdaLang

This is still a work in progress. It may be changed in the future.

LambdaLang is a language based around Lambda calculus but with jumping and control flow.

The Logo of LambdaLang

## The Syntax

`(var name):=(lambda calculus expression)` denotes an assignment.
`\` is the lambda symbol.
`lbl:` denotes a label.
`=>lbl` denotes jumping to label 'lbl'.
`(var name)=(lambda calculus expression)` skip next instruction if two expressions are equal.

## Builtin functions

They are just subsitutions to lambda calculus. What follows is a list of subsitutions:

Builtin functions
Name Expression Function
`IDENTITY` `\a.a` <WIP>
`IF` `IDENTITY` <WIP>
`TRUE` `\a.\b.a` <WIP>
`FALSE` `\a.\b.b` <WIP>
`OR` `\a.\b.a(TRUE)(b)` <WIP>
`AND` `\a.\b.a(b)(FALSE)` <WIP>
`NOT` `\a.a(FALSE)(TRUE)` <WIP>
`XOR` `\a.\b.a(b(FALSE)(TRUE))(b(TRUE)(FALSE))` <WIP>
`XNOR` `\a.\b.NOT(XOR(a)(b))` <WIP>
`I` `IDENTITY` <WIP>
`K` `TRUE` <WIP>
`S` `\a.\b.\c.a(c)(b(c))` <WIP>
`Y` `\f.((\x.f(\y.x(x)(y)))(\x.f(\y.x(x)(y))))` <WIP>
`LIST` `CONS(TRUE)(TRUE)` <WIP>
`PREPEND` `\xs.\x.CONS(FALSE)(CONS(x)(xs))` <WIP>
`EMPTY` `\xs.CAR(xs)` <WIP>
`HEAD` `\xs.CAR(CDR(xs))` <WIP>
`TAIL` `\xs.CDR(CDR(xs))` <WIP>
`APPEND` `Y(\f.\xs.\x.EMPTY(xs)(\h.PREPEND(xs)(x))(\h.CONS(FALSE)(CONS(HEAD(xs))(f(TAIL(xs))(x))))(TRUE))` <WIP>
`REVERSE` `Y(\f.\xs.EMPTY(xs)(\h.LIST)(\h.APPEND(f(TAIL(xs)))(HEAD(xs)))(TRUE))` <WIP>
`MAP` `Y(\f.\a.\xs.EMPTY(xs)(\h.LIST)(\h.PREPEND(f(a)(TAIL(xs)))(a(HEAD(xs))))(TRUE))` <WIP>
`RANGE` `Y(\f.\a.\b.GTE(a)(b)(\h.LIST)(\h.PREPEND(f(INC(a))(b))(a))(TRUE))` <WIP>
`REDUCE` `FOLD` <WIP>
`FILTER` `\f.\l.(REDUCE(\x.\xs.f(x)(APPEND(xs)(x))(xs))(l)(LIST))` <WIP>
`DROP` `\n.\l.n(TAIL)(l)` <WIP>
`TAKE` `Y(\f.\n.\l.(OR(EMPTY(l))(ISZERO(n))(\h.LIST)(\h.(PREPEND(f(DEC(n))(TAIL(l)))(HEAD(l))))(TRUE)))` <WIP>
`LENGTH` `\l.REDUCE(\x.\n.INC(n))(l)(ZERO)` <WIP>
`INDEX` `Y(\f.\n.\l.(ISZERO(n)(\h.HEAD(l))(\h.f(DEC(n))(TAIL(l)))(TRUE)))` <WIP>
`ANY` `Y(\f.\l.(EMPTY(l)(\h.FALSE)(\h.HEAD(l)(TRUE)(f(TAIL(l))))(TRUE)))` <WIP>
`ALL` `Y(\f.\l.(EMPTY(l)(\h.TRUE)(\h.NOT(HEAD(l))(FALSE)(f(TAIL(l))))(TRUE)))` <WIP>
`INC` `\n.\a.\b.a(n(a)(b))` <WIP>
`ADD` `\a.\b.a(INC)(b)` <WIP>
`MUL` `\a.\b.\c.a(b(c))` <WIP>
`DEC` `\n.\f.\x.n(\g.\h.h(g(f)))(\h.x)(IDENTITY)` <WIP>
`SUB` `\a.\b.b(DEC)(a)` <WIP>
`POW` `\a.\b.b(a)` <WIP>
`DIFF` `\a.\b.ADD(SUB(a)(b))(SUB(b)(a))` <WIP>
`ZERO` `FALSE` <WIP>
`ONE` `IDENTITY` <WIP>
`TWO` `\a.\b.a(a(b))` <WIP>
`THREE` `\a.\b.a(a(a(b)))` <WIP>
`FOUR` `INC(THREE)` <WIP>
`FIVE` `ADD(TWO)(THREE)` <WIP>
`SIX` `MUL(TWO)(THREE)` <WIP>
`SEVEN` `INC(SIX)` <WIP>
`EIGHT` `MUL(FOUR)(TWO)` <WIP>
`NINE` `POW(THREE)(TWO)` <WIP>
`TEN` `MUL(FIVE)(TWO)` <WIP>
`ISZERO` `\a.a(\h.FALSE)(TRUE)` <WIP>
`GTE` `\a.\b.ISZERO(SUB(b)(a))` <WIP>
`LTE` `\a.\b.ISZERO(SUB(a)(b))` <WIP>
`GT` `\a.\b.ISZERO(SUB(INC(b))(a))` <WIP>
`LT` `\a.\b.ISZERO(SUB(INC(a))(b))` <WIP>
`EQ` `\a.\b.AND(GTE(a)(b))(LTE(a)(b))` <WIP>
`MIN` `\a.\b.LTE(a)(b)(a)(b)` <WIP>
`MAX` `\a.\b.GTE(a)(b)(a)(b)` <WIP>
`CONS` `\a.\b.\c.c(a)(b)` <WIP>
`CAR` `\p.p(TRUE)` <WIP>
`CDR` `\p.p(FALSE)` <WIP>
`NULL` `\h.TRUE` <WIP>
`ISNULL` `\h.\h.FALSE` <WIP>
`FAC` `Y(\f.\n.ISZERO(n)(\h.ONE)(\h.MUL(n)(f(DEC(n))))(ZERO))` <WIP>
`FIB` `Y(\f.\n.LTE(n)(TWO)(\h.ONE)(\h.ADD(f(DEC(n)))(f(DEC(DEC(n)))))(ZERO))` <WIP>
`DIV` `Y(\f.\a.\b.LT(a)(b)(\h.ZERO)(\h.INC(f(SUB(a)(b))(b)))(ZERO))` <WIP>
`MOD` `Y(\f.\a.\b.LT(a)(b)(\h.a)(\h.f(SUB(a)(b))(b))(ZERO))` <WIP>
`EVEN` `\a.ISZERO(MOD(a)(TWO))` <WIP>
`ODD` `\a.NOT(EVEN(a))` <WIP>
`SIGN` `\n.CONS(TRUE)(n)` <WIP>
`NEG` `\p.CONS(NOT(CAR(p)))(CDR(p))` <WIP>
`ISPOS` `\p.CAR(p)` <WIP>
`ISNEG` `\p.NOT(CAR(p))` <WIP>
`UNSIGN` `\p.CDR(p)` <WIP>
`SADD` `\a.\b.(XNOR(CAR(a))(CAR(b))(CONS(CAR(a))(ADD(CDR(a))(CDR(b))))(CONS(XOR(CAR(a))(LTE(CDR(a))(CDR(b))))(DIFF(CDR(a))(CDR(b)))))` <WIP>
`SSUB` `\a.\b.SADD(a)(CONS(NOT(CAR(b)))(CDR(b)))` <WIP>
`SMUL` `\a.\b.CONS(XNOR(CAR(a))(CAR(b)))(MUL(CDR(a))(CDR(b)))` <WIP>