Universal Lambda Machine: Difference between revisions
imported>Tromp Add universal lambda machine in Python |
imported>Tromp Add universal lambda machine in JavaScript |
||
Line 119: | Line 119: | ||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|JavaScript}}== |
|||
</syntaxhighlight lang="javascript">#!/usr/local/bin/node --stack-size=8192 |
|||
let bytemode = process.argv.length <= 2; |
|||
var data; |
|||
var nchar = 0; |
|||
var nbit = 0; |
|||
var progchar; |
|||
function bit2lam(bit) { |
|||
return function(x0) { return function(x1) { return bit ? x1 : x0 } } |
|||
} |
|||
function byte2lam(bits,n) { |
|||
return n==0 ? (function(_) { return function(y) { return y } }) // nil |
|||
: (function(z) { return z (bit2lam((bits>>(n-1))&1)) |
|||
(byte2lam(bits,n-1)) }) // cons bitn bits>n |
|||
} |
|||
function input(n) { // input from n'th character onward |
|||
if (n >= data.length) |
|||
return function(z) { { return function(y) { return y } } } // nil |
|||
let c = data[n]; |
|||
return function(z) { return z (bytemode ? byte2lam(c,8) : bit2lam(c&1)) (input(n+1)) } // cons charn chars>n |
|||
} |
|||
function lam2bit(lambit) { |
|||
return lambit(function(_){return 0})(function(_){return 1})() // force suspension |
|||
} |
|||
function lam2byte(lambits, x) { |
|||
return lambits(function(lambit) { |
|||
return function(lamtail) { |
|||
return function(_) { return lam2byte(lamtail, 2*x + lam2bit(lambit)) } |
|||
} |
|||
})(Buffer.from([x])) // end of byte |
|||
} |
|||
function output(prog) { |
|||
return prog(function(c) { // more chars |
|||
process.stdout.write(bytemode ? lam2byte(c,0) : lam2bit(c) ? '1' : '0'); |
|||
return function(tail) { |
|||
return function(_) { return output(tail) } |
|||
} |
|||
})(0) // end of output |
|||
} |
|||
function getbit() { |
|||
if (nbit==0) { |
|||
progchar = data[nchar++]; |
|||
nbit = bytemode ? 8 : 1; |
|||
} |
|||
return (progchar >> --nbit) & 1; |
|||
} |
|||
function program() { |
|||
if (getbit()) { // variable |
|||
var i = 0; |
|||
while (getbit()==1) { i++ } |
|||
return function() { return arguments[i] } |
|||
} else if (getbit()) { // application |
|||
let p = program(); |
|||
let q = program(); |
|||
return function(...args) { |
|||
return p(...args)(function(arg) { return q(...args)(arg) }) // suspend argument |
|||
} |
|||
} else { |
|||
let p = program(); |
|||
return function(...args) { |
|||
return function(arg) { return p(arg, ...args) } // extend environment with one more argument |
|||
} |
|||
} |
|||
} |
|||
process.stdin.on('readable', () => { |
|||
if ((data = process.stdin.read()) != null) { |
|||
prog = program()(); |
|||
output(prog(input(nchar))) // run program with empty env on input |
|||
} |
|||
});</syntaxhighlight> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 17:32, 21 February 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
One of the foundational mathematical constructs behind computer science is the universal machine, as a machine that can emulate the behaviour of any other machine, given a description of it. Alan Turing introduced the idea of a universal Turing machine in 1936–1937.
The lambda calculus is an even older, and in many ways simpler, model of computation. That simplicity is reflected in the Binary Lambda Calculus (BLC for short), which describes lambda terms with binary tokens 00 for lambda, 01 for application, and 1^n0 for variable n (which binds to the n'th enclosing lambda).
BLC also specifies a way to represent bits and lists as lambda terms, which provides the following I/O convention:
The lambda universal machine parses the binary encoding of a lambda term from the start of its input, applies that term to the remainder of input, and outputs the result interpreted as a list of bits or bytes.
BLC as a programming language has its own entry on Rosetta Code at https://rosettacode.org/wiki/Category:Binary_Lambda_Calculus which links to more detailed descriptions of the language.
- Task
Simulate the universal lambda machine Or in other words, write a BLC interpreter. Support either bit-mode or byte-mode, or preferably both (with byte-mode as the default, and a -b command line flag for bit mode).
To test your universal lambda machine, you should execute the following BLC programs.
For bit-mode, one should reproduce the BLC Rosetta Code solutions of
- https://rosettacode.org/wiki/Quine#Binary_Lambda_Calculus
- https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Binary_Lambda_Calculus (
producing as much output as possible before running out of stack/heap space).
Also, the 342 bit program
010100011010000000011000010110011110000010010111110111100001010110000000011000011111000000101111110110010111111011001011110100111010111100010000001011100101010001101000000000010110000101011111101111100000010101111011111011111100001011000000101111111010110111000000111111000010110111101110011110100000010110000011011000100000101111000111001110
should produce output
11010
For byte-mode, one should reproduce the BLC Rosetta Code solutions of
- https://rosettacode.org/wiki/Hilbert_curve#Binary_Lambda_Calculus
- https://rosettacode.org/wiki/Execute_Brain****#Binary_Lambda_Calculus
Existing solutions may be found at https://rosettacode.org/wiki/Hello_world/Newbie#Binary_Lambda_Calculus
Binary Lambda Calculus
The following self interpreters are taken from the IOCCC entry at https://www.ioccc.org/2012/tromp/hint.html
Bit-wise:
01010001
10100000
00010101
10000000
00011110
00010111
11100111
10000101
11001111
000000111
10000101101
1011100111110
000111110000101
11101001 11010010
11001110 00011011
00001011 11100001
11110000 11100110
11110111 11001111
01110110 00011001
00011010 00011010
Byte-wise (showing https://www.ioccc.org/2012/tromp/uni8.Blc in hex):
19468
05580
05f00
bfe5f
85f3f
03c2d
b9fc3f8
5e9d65e5f
0decb f0fc3
9befe 185f7
0b7fb 00cf6
7bb03 91a1a
C
#ifndef M
#define M 50000
#endif
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
enum {I,O,V,A,L};
long n=44,i,c,T[M]={L,A,8,A,2, V,0,L,L,V,
A,30,L,A,2,V,0,L,A,5,A,7,L,V,0,O,
A,14,L,A,2,V,0,L,A,5,A,2, V,0,O,O,A},b,s;
long nc = 0, nf = 0, na = 0; // number of cells, number freed, number of allocs
typedef struct _{long t,r; struct _*e,*n;} C;C*e,*f,*l,*S[M];
void x(long l,long u){for(;l<=u;T[n++]=T[l++]);}
long g(){i--||(i=b,c=getchar());return c>>i&1;}
void d(C*l){!l||--l->r||(d(l->e),d(l->n),l->n=f,nf++,f=l);}
long p(long m){if(g()){for(T[n++]=V;g();T[n]++){}n++;}else
T[m]=n++&&g()?(T[m+1]=p(++n),A):L,p(n);return n-m;}
int main(int t,char **_){char o;
b=t>1?0:7;T[43]=p(n);i=0;
for(t=b?10:26;;)switch(T[t]){
case I: g();i++;assert(n<M-99);if(~c&&b){x(0,6);for(T[n-5]=96;i;T[n++]=!g())
x(0,9);}x(c<0?7:b,9);T[n++]=!b&&!g();break;
case O: t=b+t>42?(o=2*o|t&1,28):(putchar
(b?o:t+8),fflush(stdout),b?12:28);break;
case V: l=e;for(t=T[t+1];t--;e=e->n){}
t=e->t;(e=e->e)&&e->r++;d(l);break;
case A: t+=2;
nc++;
f||(na++,f=calloc(1,sizeof(C)));
assert(f&&s<M);S[s++]=l=f;f=l->n;
l->r=1;l->t=t+T[t-1];(l->e=e)&&e->r++;break;
case L: if(!s--){printf("\n%ld cells\n%ld freed\n%ld allocated\n", nc, nf, na);return 0;};S[s]->n=e;e=S[s];t++;break;
}
printf("%ld cells %ld allocated\n", nf, na);
return T[t+2];
}
JavaScript
</syntaxhighlight lang="javascript">#!/usr/local/bin/node --stack-size=8192 let bytemode = process.argv.length <= 2; var data; var nchar = 0; var nbit = 0; var progchar;
function bit2lam(bit) {
return function(x0) { return function(x1) { return bit ? x1 : x0 } }
} function byte2lam(bits,n) {
return n==0 ? (function(_) { return function(y) { return y } }) // nil : (function(z) { return z (bit2lam((bits>>(n-1))&1)) (byte2lam(bits,n-1)) }) // cons bitn bits>n
} function input(n) { // input from n'th character onward
if (n >= data.length) return function(z) { { return function(y) { return y } } } // nil let c = data[n]; return function(z) { return z (bytemode ? byte2lam(c,8) : bit2lam(c&1)) (input(n+1)) } // cons charn chars>n
} function lam2bit(lambit) {
return lambit(function(_){return 0})(function(_){return 1})() // force suspension
} function lam2byte(lambits, x) {
return lambits(function(lambit) { return function(lamtail) { return function(_) { return lam2byte(lamtail, 2*x + lam2bit(lambit)) } } })(Buffer.from([x])) // end of byte
} function output(prog) {
return prog(function(c) { // more chars process.stdout.write(bytemode ? lam2byte(c,0) : lam2bit(c) ? '1' : '0'); return function(tail) { return function(_) { return output(tail) } } })(0) // end of output
} function getbit() {
if (nbit==0) { progchar = data[nchar++]; nbit = bytemode ? 8 : 1; } return (progchar >> --nbit) & 1;
} function program() {
if (getbit()) { // variable var i = 0; while (getbit()==1) { i++ } return function() { return arguments[i] } } else if (getbit()) { // application let p = program(); let q = program(); return function(...args) { return p(...args)(function(arg) { return q(...args)(arg) }) // suspend argument } } else { let p = program(); return function(...args) { return function(arg) { return p(arg, ...args) } // extend environment with one more argument } }
} process.stdin.on('readable', () => {
if ((data = process.stdin.read()) != null) { prog = program()(); output(prog(input(nchar))) // run program with empty env on input }
});</syntaxhighlight>
Python
#!/usr/local/bin/python3
import os,sys
def bit2lam(bit) :
return lambda x0: lambda x1: x1 if bit else x0
def byte2lam(bits,n) :
if (n==0) :
return lambda _:lambda y: y
return lambda z: z (bit2lam((bits>>(n-1))&1)) (byte2lam(bits,n-1))
def input(n) : # input from n'th character onward
if n >= len(inp) :
c = os.read(0,1)
inp.append((lambda _: lambda y: y) if c==b''
else lambda z: z(byte2lam(c[0],8) if bytemode else bit2lam(c[0]&1))(input(n+1)))
return inp[n]
def lam2bit(lambit) :
return lambit(lambda _: 0)(lambda _: 1)(0) # force suspension
def lam2byte(lambits, x) :
return lambits(lambda lambit: lambda lamtail: lambda _: lam2byte(lamtail, 2*x+lam2bit(lambit)))(bytes([x]))
def output(prog) :
return prog(lambda c: os.write(1,lam2byte(c,0) if bytemode else (b'1' if lam2bit(c) else b'0')) and (lambda tail: lambda _ : output(tail)))(0)
def getbit() :
global nbit, progchar
if nbit==0 :
progchar = os.read(0,1)[0]
nbit = 8 if bytemode else 1
nbit -= 1
return (progchar >> nbit) & 1
def program() :
if getbit() : # variable
i = 0
while (getbit()==1) : i += 1
return lambda *args : args[i]
elif getbit() : # application
p = program()
q = program()
return lambda *args : p(*args)(lambda arg: q(*args)(arg)) # suspend argument
else :
p = program()
return lambda *args: lambda arg: p(arg, *args) # extend environment with one more argument
sys.setrecursionlimit(8192)
inp = []
nbit = progchar = 0
bytemode = len(sys.argv) <= 1
prog = program()(0)
output(prog(input(0))) # run program with empty env on input
Ruby
#!/usr/bin/ruby
def bit2lam(bit)
return lambda { |x0| lambda { |x1| bit==0 ? x0 : x1 } }
end
def byte2lam(bits,n)
return n==0 ? lambda { |_| lambda { |y| y } }
: lambda { |z| z.call(bit2lam((bits>>(n-1))&1)).call(byte2lam(bits,n-1)) }
end
def input(n) # input from n'th character onward
if n >= $inp.length()
c = STDIN.getbyte
$inp.append(c==nil ? (lambda { |_| lambda { |y| y } })
: lambda { |z| z.call($bytemode ? byte2lam(c,8) : bit2lam(c&1)).call(input(n+1)) } )
end
return $inp[n]
end
def lam2bit(lambit)
return lambit.call(lambda { |_| 0 }).call(lambda { |_| 1 }).call(0) # force suspension
end
def lam2byte(lambits, x)
return lambits.call(lambda { |lambit| lambda { |lamtail| lambda { |_| lam2byte(lamtail, 2*x+lam2bit(lambit)) } } }).call(x)
end
def output(prog)
return prog.call(lambda { |c| putc($bytemode ? lam2byte(c,0) : (lam2bit(c)==0 ? '0' : '1')) and (lambda { |tail| lambda { |_| output(tail) } }) }).call(0)
end
def getbit()
if ($nbit==0)
$progchar = STDIN.getbyte
$nbit = $bytemode ? 8 : 1
end
return ($progchar >> $nbit -= 1) & 1
end
def program()
if getbit()==1 # variable
i = 0
while (getbit()==1) do i += 1 end
return lambda { |*args| args[i] }
elsif getbit()==1 # application
p = program()
q = program()
return lambda { |*args| p.call(*args).call(lambda { |arg| q.call(*args).call(arg) }) } # suspend argument
else
p = program()
return lambda { |*args| lambda { |arg| p.call(arg, *args) } } # extend environment with one more argument
end
end
$inp = []
$nbit = $progchar = 0
$bytemode = ARGV.length <= 0
$prog = program().call(0)
output($prog.call(input(0))) # run program with empty env on input