Universal Lambda Machine: Difference between revisions
m
Move Haskell before JavaScript
m (Move Haskell before JavaScript) |
|||
| (7 intermediate revisions by 3 users not shown) | |||
Line 25:
Also, the 342 bit program
<
should produce output
<
For byte-mode, one should reproduce the
Line 35:
When run on the 186-byte binary file https://www.ioccc.org/2012/tromp/tromp/symbolic.Blc followed by input 010000011100111001110100000011100111010, it should output
<
\a (\b \c b (b c)) ((\b \c b (b c)) ((\b \c b (b c)) a))
\a \b (\c \d c (c d)) ((\c \d c (c d)) a) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
Line 49:
\a \b a (a (a (a (a (a ((\c \d c (c d)) a b))))))
\a \b a (a (a (a (a (a ((\c a (a c)) b))))))
\a \b a (a (a (a (a (a (a (a b)))))))</
=={{header|Binary Lambda Calculus}}==
Line 57:
Bit-wise (the whitespace is actually not part of the program and should be removed before feeding it into the universal machine) :
<
10100000
00010101
Line 77:
01110110 00011001
00011010 00011010
</pre>
Byte-wise (showing https://www.ioccc.org/2012/tromp/uni8.Blc in hex, again with whitespace for decorational purposes only):
<
05580
05f00
Line 93:
0b7fb 00cf6
7bb03 91a1a
</pre>
=={{header|Bruijn}}==
Line 180:
}
</syntaxhighlight>
=={{header|Haskell}}==
A bit-wise only ULM:
<syntaxhighlight lang="haskell">
import System.IO
import Data.List
import Text.Parsec
import Control.Applicative hiding ((<|>), many)
data WHNF = SYM !Char | FUN (WHNF -> WHNF)
fun :: WHNF -> WHNF -> WHNF
fun (SYM c) _ = error $ "Cannot apply symbol " ++ [c]
fun (FUN f) w = f w
expr :: Monad m => ParsecT String u m ([WHNF] -> WHNF)
expr = char '0' *> (buildLambda <$ char '0' <*> expr
<|> buildApply <$ char '1' <*> expr <*> expr)
<|> buildVar <$> pred.length <$> many (char '1') <* char '0' where
buildLambda e env = FUN $ \arg -> e (arg:env)
buildApply e1 e2 env = e1 env `fun` e2 env
buildVar n env = env !! n
buildIO prog = whnfToString . (prog [] `fun` ) . stringToWhnf where
stringToWhnf :: [Char] -> WHNF
stringToWhnf = foldr (whnfCons . bitToWhnf . fromEnum) whnfFalse where
bitToWhnf :: Integral a => a -> WHNF
bitToWhnf n = if even n then whnfTrue else whnfFalse
whnfCons :: WHNF -> WHNF -> WHNF
whnfCons fw gw = FUN $ \hw -> hw `fun` fw `fun` gw
whnfToString = map whnfToChar . whnfToList where
cons2sym :: WHNF
cons2sym = whnfConst . whnfConst $ SYM ':'
whnfToList :: WHNF -> [WHNF]
whnfToList l = case (l `fun` cons2sym) of
SYM ':' -> l `fun` whnfTrue : whnfToList (l `fun` whnfFalse)
FUN _ -> []
whnfToChar :: WHNF -> Char
whnfToChar iw = c where (SYM c) = iw `fun` SYM '0' `fun` SYM '1'
whnfConst :: WHNF -> WHNF
whnfConst = FUN . const
whnfTrue :: WHNF
whnfTrue = FUN whnfConst
whnfFalse :: WHNF
whnfFalse = whnfConst $ FUN id
main = do
hSetBuffering stdout NoBuffering
interact $ either (error . show) id . parse (buildIO <$> expr <*> getInput) ""
</syntaxhighlight>
Feel free to replace this by a solution for both bit-wise and byte-wise.
=={{header|JavaScript}}==
Line 253 ⟶ 311:
}
});</syntaxhighlight>
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
sub bit2lam {
my $bit = pop;
sub { my $x0 = pop; sub { my $x1 = pop; $bit ? $x1 : $x0 } }
}
sub byte2lam {
my ($bits,$n) = @_;
$n == 0 ? sub { sub { pop } } # nil
: sub { pop->(bit2lam(vec$bits,$n-1,1))->(byte2lam($bits,$n-1)) }
}
sub input {
my $n = pop; # input from n'th character onward
if ($n >= @B) {
my $c = getc;
push @B, !defined($c) ? sub {sub { pop } } # nil
: sub { pop->($bytemode ? byte2lam($c,8) : bit2lam($c))->(input($n+1)) }
}
$B[$n];
}
sub lam2bit {
pop->(sub{0})->(sub{1})->() # force suspension
}
sub lam2byte {
my ($lambits, $x) = @_; # 2nd argument is partial byte
$lambits->(sub { my $lambit = pop; sub { my $tail = pop; sub { lam2byte($tail, 2*$x + lam2bit($lambit)) }
}})->(chr $x) # end of byte
}
sub output {
pop->(sub { my $c = pop; print($bytemode ? lam2byte($c,0) : lam2bit($c));
sub { my $tail = pop; sub { output($tail) } } })->(0) # end of output
}
sub getbit {
$n ||= ($c = getc, $bytemode ? 8 : 1);
vec $c,--$n,1;
}
sub program {
if (getbit()) { # variable
my $i;
$i++ while getbit();
sub { $_[$i] }
} elsif (getbit()) { # application
my $p=program();
my $q=program();
sub { my @env = @_; $p->(@env)->(sub { $q->(@env)->(pop) }) } # suspend argument
} else {
my $p = program();
sub { my @env = @_; sub { $p->(pop,@env) } } # extend environment with one more argument
}
}
$bytemode = !pop; # any argument sets bitmode instead
$| = 1; # non zero value sets autoflush
$prog = program()->();
output $prog->(input(0)) # run program with empty env on input</syntaxhighlight>
=={{header|Phix}}==
Line 476 ⟶ 590:
"0000001000101000101000100000000000001000100000101000000000101000001000001000100000100000101"&
"0000000001010001010000000000010000000000010001010001000001010000000001000001000001000001010"&
"0000100010100000000010000000000000100010100010000000000000100000100000000010100010000010000"&
"0001000001000001000100000100000001000100000001000000000101000000000101000001000100000100000"&
"0010001010001000000000001000000010001000000010001000001000000000001010000000000000000010000"&
"0100000000010000010000010100000100000000010000010000010100000100000100010100000000000100000"&
"0000101000100000100000101000000000001000100000100000001000000000100000001000000000100000001"&
"0000010000010001000000010000010001000000010001000000000000010000000001000000000001010000000"&
"0010100010100000000010000000000000100010100010000000000000100010100010000000000000000000100"&
"0100000001000000000100000001000100000100000100000000000001000100000100000100000001000001000"&
"00000000100010000010100."},
{"100 doors",
"00010001000101010001101000000101100000110011101100101000110100000000001011111110000001"&
Line 540 ⟶ 662:
Sieve of Eratosthenes:
00110101000101000101000100000101000001000101000100000100000101000001000101000001000100000100000001000101000101000100000000000001000100000101000000000101000001000001000100000100000101000000000101000101000000000001000000000001000101000100000101000000000100000100000100000101000001000101000000000100000000000001000101000100000000000001000001000000000101000100000100000001000001000001000100000100000001000100000001000000000101000000000101000001000100000100000001000101000100000000000100000001000100000001000100000100000000000101000000000000000001000001000000000100000100000101000001000000000100000100000101000001000001000101000000000001000000000101000100000100000101000000000001000100000100000001000000000100000001000000000100000001000001000001000100000001000001000100000001000100000000000001000000000100000000000101000000000101000101000000000100000000000001000101000100000000000001000101000100000000000000000001000100000001000000000100000001000100000100000100000000000001000100000100000100000001000001000000000001000100000101000
100 doors:
Line 554 ⟶ 676:
Hello, world!
</pre>
=={{header|Python}}==
Line 826 ⟶ 892:
Output:
1001000010000001000000001000000000010000000000001000000000000001000000000000000010000000000000000001
</pre>
Sieve of Eratosthenes example (output manually terminated after first 1024 bits printed):
<pre>
Input:
00010001100110010100011010000000010110000010010001010111110111101001000110100001110011010000000000101101110011100111111101111000000001111100110111000000101100000110110
Output:
0011010100010100010100010000010100000100010100010000010000010100000100010100000100010000010000000100010100010100010000000000000100010000010100000000010100000100000100010000010000010100000000010100010100000000000100000000000100010100010000010100000000010000010000010000010100000100010100000000010000000000000100010100010000000000000100000100000000010100010000010000000100000100000100010000010000000100010000000100000000010100000000010100000100010000010000000100010100010000000000010000000100010000000100010000010000000000010100000000000000000100000100000000010000010000010100000100000000010000010000010100000100000100010100000000000100000000010100010000010000010100000000000100010000010000000100000000010000000100000000010000000100000100000100010000000100000100010000000100010000000000000100000000010000000000010100000000010100010100000000010000000000000100010100010000000000000100010100010000000000000000000100010000000100000000010000000100010000010000010000000000000100010000010000010000000100000100000000000100010000010100^C
</pre>
| |||