λιμπ
λιμπ is an esoteric programming language developped by user:Slereah. It is based on the main theoretical functional languages : λ-calculus (and combinators), µ-recursive functions and Lisp. The remaining π is for π-calculus.
Language Overview
A λιμπ program is composed of a list of functions and processes, and a final process to use those. It's also possible to use libraries by writing the files path of functions (written in the same style) at the beginning of the program.
A function has the following syntax :
f(x,y,z,...) = g(h(x,y,z,...),i(x,y,z,...),...)
You can also use a recursive function, of the form :
f(x,y,z,...,0) = g(x,y,z,...)
f(x,y,z,...,s(n)) = h(x,y,z,...,f(x,y,z,...,n))
You can do as much function composition on a function as you wish, there are no particular templates for them. All functions can also reference themselves.
Nullary functions and lambda functions require no parenthesis. For instance :
1 = s(0)
I = ^x$x
The processes require no variables either, and are just defined by P = Q, where Q has the following syntax :
Q ::= 0 | a[x].Q | a<x>.Q | (n x)Q | !Q | Q|R
Parenthesis aren't required for most expressions, but they are if using either (n x)Q or !Q on a complex expression. For instance, (n x)(Q|R|S)
Where a and x can be any name (any string that isn't ambiguous with the syntax). a and x can also be functions, denoted by f(x,y,z,...), where x, y, z are also names, evaluated as soon as they get input. To use constants instead of names (or just other functions for that matter), just define another function of the form :
f' = f(a,b,c,...)
And use nullary functions in the process using f'(). A combinator C uses (((C x) y) ...).
When evaluated, functions in processes will convert to strings if they are in the right format (ie : "abcd" = cons(a, cons(b, cons(c, d))), where a, b, c and d are the numerical values of the ASCII characters, or modulo 256 otherwise), and those strings will be used as names.
List of functions
µ-recursive functions
- 0 : A constant (or nullary function).
- s : s(x) returns x + 1
- p : A n+2-ary function, of the form : p(k,n)(x1,x2,...,xn) = xk.
- µ : Used as µy(f(y,a,b,c,...)), y being any variable of f, and returns the smallest value of y such that f = 0, if such a value exist. It would otherwise return 0, but on a practical level will not terminate. All the other variables must be defined.
Lisp
- c : c(x,y) returns the ordered pair <x,y>
- < and > : To be applied on an ordered pair, return respectively the first and last value of it.
- a : a(x) returns s(0) (or 1, on a more practical level) if x is a number. Returns 0 if it is an ordered pair.
- = : =(x,y) returns 1 if x and y are identical numbers, 0 otherwise, and cannot be fed pairs.
- ? : ?(a, b, c, d, ...)(2n-ary function) will first evaluate a, and return b if a > 0. Otherwise, it will repeat the process with c and so on. If none of the conditions evaluated are superior to zero, an error is returned.
λ-calculus
Lambda functions can be defined as : ^x^y^z... f($x,$y,$z,...). For instance, S = ^x^y^z(($x$z)($y$z))
A lot of combinators are already defined. Mostly the single letter combinators from the list of combinator birds, using capital letters.
π-calculus
- P|Q : P and Q are running in parallel.
- P.Q : Q is evaluated after P.
- a<x> : Sends x through a.
- a[y] : Awaits input from a, then will substitute this input for y.
- 0 : Inert process, used to terminate a process.
- !P : A process running an infinite amount of copy.
- P+Q : Either P or Q will run.
- (v x) P : x is a variable specific to P. For instance, (v x) x[y].P | x<z>.Q does not send y to replace z, since the channel x of x<z> isn't the same.
In the case of P+Q, it will chose the process that can actually be evaluated. For instance :
(x[y].P + a[b].M) | (x<z>.Q +c<d>.N)
becomes :
P' | Q
Where P' is P with every free occurence of y replaced by z (noted {z/y}P).
In case of non-determinism, the first choice encountered will always be chosen. P in P+Q, x<z>.P|x<t>.Q|x[y].R converts to P|{z/y}R, x<z>.P|x[t].Q|x[y].R converts to P|{z/t}Q and so on.
Instead of names, you can use functions. They will replace names in the following way : a single number is a character, in ASCII mod 256, a list will represent a string.
I/O
Apart from the processes used for computing, the outside world and optionally other processes are considered part of them. Input/Output takes the form of an unstated process that can be reached via the immutable Alice channel. Every name transmitted will find its way out, and will be processed as output on the screen. Alice[x] will await input from the keyboard.
Both input and output will either deal with the names involved (Alice<x> will output x on the screen) or by using functions to output strings or single characters.
Examples
Alice<Hello, world!>
i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)
It will work out in the following way : Processes aren't actually evaluated in parallel in the interpreter (when it will exist), neither will it make an infinite amount of copy. Any replication operator will be dealt thusly :
!P -> P|!P
And P will be evaluated. If it cannot be, it will remain that way. Otherwise, if P -> P', it will convert to :
P|!P -> P'|P|!P
And so on until no P can be evaluated in this step.
The Cat program will convert to :
i<Alice>.0|i[x].x[y].x<y>.i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)
The first name sent will be Alice via i to the first i receptor :
0|Alice[y].Alice<y>.i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)
And !(i[x].x[y].x<y>.i<Alice>.0) will again be replicated :
0|Alice[y].Alice<y>.i<Alice>.0|i[x].x[y].x<y>.i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)
Alice[y] will await input from the user, and then replace y with it (you can also drop the inert process) :
Alice<input>.i<Alice>.0|i[x].x[y].x<y>.i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)
The replicated part hasn't changed, so no more replication for now. Alice<input> will output the input, and the process will revert to its original state :
i<Alice>.0|i[x].x[y].x<y>.i<Alice>.0|!(i[x].x[y].x<y>.i<Alice>.0)