LambdaLang
Jump to navigation
Jump to search
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
- 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 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:
| 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>
|