User:Slereah/Limp
Here's a draft of Limp :
λιμπ 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.
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 basic functions are the following :
- 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 (and if any value can be computed with only this variable defined). All the other variables must
be defined.
- 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, ...) will first evaluate a, and return b if a > 0. Otherwise, it will repeat the process with c
and so on.
- Most combinators from Lazy Bird, using upper case for letters.
Lambda functions can be defined as : ^x^y^z... f($x,$y,$z,...). For instance, S = ^x^y^z(($x$z)($y$z))
The syntax and primitives of processes are :
- 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] | x<z>.P 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 awaits input from the keyboard.
Both input and output will either be dealt 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. First, it will evaluate any function present (only with actual input. It won't take the name for a string. Use f() in processes for nullary functions). 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)