1337

From Esolang
Jump to navigation Jump to search
Not to be confused with l33t.

1337 is a language by User:Olsner based on single-combinator combinatory logic and a simple precedence parser, with the set of integers (or, really, any ordered set of items) as its input alphabet. The language has a single operator, function application, that can be used with any precedence specified by the input integer. The single combinator used is Fokker's X combinator, X = λf.fS(λxyz.x), with the standard S combinator S = λfgx.fx(gx).

The language name also makes a very good excuse for calling things relating to this language "1337", as demonstrated by the contents of this page.

For example, the program [1,0] represents the expression X(XX). Since all non-operator parts of the input program would be the symbol representing the X combinator, those symbols are elided from the source and implicitly inserted by the parser. In order to understand the example, we insert the X's again, at the end and the beginning and between every operator. The program can now be seen as X <1> X <0> X, where <n> stands for function application with precedence n - the function application with the lower number binding harder. Reapplying parantheses and rewriting to more familiar syntax, we get X <1> X <0> X = X <1> (XX) = X(XX).

Example

This program calculates and prints all prime numbers. This is translated from the prime number sample program from the Lazy K home page. 

[1,32,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,31,1,0,30,1,29,1,0,28,1,0,27,1,26
,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,25,1,0,24,1,0,3,1,2,1,0,23,1,0,5,1,4,1
,0,3,1,2,1,0,22,1,0,9,1,8,1,0,7,1,0,3,1,2,1,0,6,1,0,2,1,0,5,1,0,4,1,0,3
,1,2,1,0,3,1,5,1,2,1,21,1,0,20,1,0,3,1,2,1,0,19,1,0,3,1,2,1,18,1,0,3,1,
2,1,0,17,1,0,10,1,0,3,1,2,1,0,9,1,0,3,1,2,1,8,1,0,3,1,2,1,0,7,1,0,6,1,0
,3,1,2,1,0,5,1,0,3,1,2,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,6,1,4,1,0,3,
1,0,2,1,2,1,3,1,2,1,16,1,15,1,0,14,1,13,1,0,12,1,0,3,1,2,1,0,11,1,0,5,1
,4,1,0,3,1,0,2,1,2,1,10,1,0,3,1,2,1,9,1,0,8,1,7,1,0,4,1,0,3,1,2,1,0,3,1
,5,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,2,1,6,1,0,4,1,0,3,1,0,2,1,2,1,3,1,
0,2,1,2,1,4,1,0,2,1,2,1,5,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,2,1,5,1,0,4
,1,0,3,1,2,1,0,3,1,8,1,0,3,1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,14,1,0,3,1
,2,1,3,1,20,1,19,1,0,3,1,2,1,18,1,0,17,1,0,3,1,0,2,1,2,1,16,1,15,1,0,14
,1,0,13,1,0,12,1,0,7,1,0,2,1,0,2,1,6,1,0,3,1,0,2,1,2,1,5,1,4,1,3,1,0,2,
1,2,1,11,1,10,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,2,1,6,1,0,4,1,0,3,1,2,1
,0,3,1,5,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,2,1,9,1,0,8,1,7,1,0,6,1,0,3,
1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,8,1,9,1,2,1,12,1,2,1,13,1,0,10,1,0,3,
1,2,1,0,9,1,0,5,1,4,1,0,3,1,0,2,1,2,1,8,1,0,3,1,2,1,7,1,0,6,1,5,1,0,4,1
,0,3,1,2,1,0,3,1,6,1,0,3,1,0,2,1,2,1,3,1,2,1,10,1,5,1,4,1,3,1,0,2,1,2,1
,14,1,0,7,1,0,3,1,2,1,0,6,1,0,5,1,4,1,0,3,1,0,2,1,2,1,5,1,0,2,1,0,4,1,0
,3,1,0,2,1,2,1,4,1,2,1,8,1,0,3,1,2,1,7,1,0,6,1,5,1,0,4,1,0,3,1,2,1,0,3,
1,6,1,0,3,1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,17,1,5,1,4,1,3,1,0,2,1,2,1,
24,1,4,1,3,1,0,2,1,2,1,27,1,0,3,1,0,2,1,2,1,3,1,2,1,30,1,0,15,1,14,1,0,
13,1,12,1,0,11,1,10,1,0,9,1,0,3,1,0,2,1,2,1,8,1,7,1,0,6,1,5,1,0,4,1,0,3
,1,2,1,0,3,1,4,1,0,2,1,2,1,6,1,0,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,4,1,
0,2,1,2,1,5,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,2,1,11,1,15,1,0,6,1,0,3,1
,2,1,0,5,1,0,3,1,2,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,7,1,6,1,0,3,1,0,
2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,31,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,28,1,0
,15,1,14,1,0,13,1,0,3,1,2,1,0,12,1,0,7,1,6,1,0,5,1,0,4,1,0,3,1,0,2,1,2,
1,3,1,2,1,4,1,3,1,0,2,1,2,1,11,1,0,2,1,0,10,1,0,9,1,0,3,1,2,1,0,8,1,0,3
,1,2,1,7,1,0,3,1,2,1,0,6,1,0,5,1,4,1,0,3,1,0,2,1,2,1,5,1,10,1,2,1,27,1,
0,10,1,0,3,1,2,1,0,9,1,0,5,1,4,1,0,3,1,2,1,0,8,1,0,5,1,4,1,0,3,1,2,1,7,
1,0,6,1,0,3,1,2,1,0,5,1,0,3,1,2,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,6,1
,5,1,0,4,1,0,3,1,2,1,0,3,1,26,1,25,1,0,24,1,0,3,1,2,1,0,23,1,0,7,1,6,1,
0,5,1,0,4,1,0,3,1,0,2,1,2,1,3,1,2,1,4,1,3,1,0,2,1,2,1,22,1,0,3,1,2,1,21
,1,0,20,1,19,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,18,1,0,17,1,16,1,0,15,1,0,
3,1,2,1,0,14,1,0,13,1,12,1,0,11,1,10,1,0,9,1,0,3,1,2,1,0,8,1,0,3,1,2,1,
7,1,0,3,1,2,1,0,6,1,0,5,1,4,1,0,3,1,0,2,1,2,1,5,1,9,1,2,1,13,1,0,8,1,0,
3,1,2,1,0,7,1,0,3,1,2,1,6,1,0,5,1,4,1,0,3,1,0,2,1,2,1,3,1,2,1,5,1,0,3,1
,0,2,1,2,1,3,1,2,1,8,1,4,1,0,3,1,0,2,1,2,1,3,1,2,1,17,1,0,11,1,0,3,1,2,
1,0,10,1,0,5,1,4,1,0,3,1,2,1,0,9,1,0,5,1,4,1,0,3,1,2,1,8,1,0,6,1,0,3,1,
2,1,0,5,1,0,3,1,2,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,7,1,6,1,0,3,1,0,2
,1,2,1,5,1,4,1,3,1,0,2,1,2,1,11,1,7,1,6,1,0,3,1,0,2,1,2,1,5,1,4,1,3,1,0
,2,1,2,1,20,1,0,5,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,15,1,0,9,1,8,1,0,
7,1,6,1,0,3,1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,14,1,0,13,1,0,3,1,2,1,0,
12,1,0,3,1,2,1,11,1,0,3,1,0,2,1,2,1,10,1,9,1,0,8,1,7,1,0,6,1,0,3,1,0,2,
1,2,1,5,1,4,1,3,1,0,2,1,2,1,8,1,13,1,7,1,0,6,1,5,1,0,4,1,0,3,1,0,2,1,2,
1,3,1,2,1,6,1,0,3,1,2,1,4,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,24,1,6,1,0,3,
1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,28,1,0,4,1,0,3,1,2,1,0,3,1,4,1,0,2,1,
2,1,28,1,0,3,1,0,2,1,2,1,3,1,0,2,1,2,1,11,1,0,10,1,9,1,0,8,1,7,1,0,6,1,
0,3,1,0,2,1,2,1,5,1,4,1,3,1,0,2,1,2,1,8,1,10,1,0,3,1,0,2,1,2,1,3,1,0,2,
1,2,1]

Construction of 1337 programs

A simple haskell function to convert SK-programs to 1337 programs: 

data SkExp = CombS | CombK | SkApp SkExp SkExp


skToNum CombS = [1,0] -- (x x) x

skToNum CombK = [0] -- (x x)
skToNum (SkApp x y) = xs++[n]++ys
	where
		xs = skToNum x
		ys = skToNum y
		n = max (maximum xs) (maximum ys + 1)

Parser

The basis of the interpreter is a simple lambda calculus, based on the following data type, which is produced directly by the parser. 

data LambdaExp =
	Lambda Id LambdaExp
	| App LambdaExp LambdaExp
	| Var Id
	deriving (Eq,Show)

type Id = Int

Here is the X combinator used, (\f -> f s (\x _ _ -> x)), expressed as a LambdaExp. 

sComb =
   Lambda 0 $ Lambda 1 $ Lambda 2 $
      App (App (Var 0) (Var 2)) (App (Var 1) (Var 2))

xComb = Lambda 0 $
   App
      (App (Var 0) sComb)
      (Lambda 0 $ Lambda 1 $ Lambda 2 $ Var 0)

And here is the parser, using the *** operator from the Control.Arrow module and otherwise only functions from the standard Prelude. 

parse :: Ord a => [a] -> LambdaExp
parse xs =
	head . snd . reduceUntil (const False) . foldl shiftReduce ([],[xComb]) $ xs
	where
		shiftReduce s x = (x:) *** (xComb:) $ reduceUntil (x <) s
		
		reduce (op:ops,v1:v2:vs) = (ops,App v2 v1:vs)
		reduce ([],[val]) = ([],[val])
		
		reduceUntil p = until (all p . take 1 . fst) reduce

Runtime system

The runtime system is borrowed from Lazy K (and this could very well be implemented as an additional input language for Lazy K). The list of numbers is parsed into a lambda expression, which is evaluated by a lazy interpreter, with input represented as an infinite list of church-encoded ascii values, and the program treated as an infinte list of output characters.

Implementation

There is a reference implementation in Haskell at http://darcs.olsner.se/1337/ (using darcs get is recommended). This implementation is rather slow, and can in its current incarnation only calculate the first few primes in one second (a long way from the 80 claimed for Lazy K). This is probably caused by program pessimisation in the SKI-to-SK-to-X conversion process - as an example, for the simplest SKI program possible, I, the above skToNum function produces a seven line lambda expression when parsed: I -> SKK -> X(XX)(XX)(XX) -> etc.

Retrieved from "https://esolangs.org/w/index.php?title=1337&oldid=81297"