Sheep

Sheep

Paradigm(s)	Functional
Designed by	Ashli Katt
Appeared in	2023
Computational class	Turing Complete
Reference implementation	Unimplemented
File extension(s)	.sheep

About

Sheep is a functional esolang where the only datatype is lambda functions. It was invented by constantly simplifying and reducing another language idea, however it essentially became lambda calculus with prefix notation.

Overview

A Sheep program is a list of constant definitions written in the form name value;. The name of an identifier is any number of non-whitespace characters except for /, ., and ;.

A value is one of three things:

• A named constant/variable reference. name.
• A lambda declaration. \ name value.
• A lambda call. . lambda value. (lambda is another value here)

All lambdas take exactly one parameter, but you may use currying to simulate multiple.

Small Notes

• Comments begin with //.
• Whitespace only matters to separate identifiers when needed, it is otherwise ignored.
• The constant main will be called with the program input, and its return value is the output.
• A variable reference will always use the innermost scope. (ie: Variable Shadowing)

IO Format

The main constant will be called with the program's input, ie: . code input is the initial call. The program input and output are both strings that are converted into nested lambdas.

Suppose our program input is abc, we first convert it into a UTF-8 bitstring: 011000010110001001100011. We then place a 1 before each bit, and pad it with infinite zeroes: 1011111010101011101111101010111010111110101011110000...

To continue, it will be helpful to define two functions:

1 \x \y x; // Takes two args, returns the first.
0 \x \y y; // Takes two args, returns the second.

Our format will resemble a LinkedList where passing 1 into it will return its bit, and 0 will return the rest of the bits. (ie: head and tail). We can write a single node using the following template expression: \bool . . bool if1 if0.

Applying the expression to the format, we get the following: \bool . . bool 1 (rest). Where (rest) would be another copy of this expression, but returning 0 instead (see above bitstring).

Suppose we have the bitstring 101 (This is impossible in practice), we can write it like so:

\b ..b 1
\b ..b 0
\b ..b 1
(infinite zeroes)

Note that these aren't separate statements, they're chained together via the first . on each line.

Finally, (infinite zeroes) can be defined as: infiniteZeroes \b ..b 0 infiniteZeroes. (Note: This can be written with a raw expression, it does not internally use a constant, but it improves readability)

So, in total, 101 becomes: \b..b 1 \b..b 0 \b..b 1 infiniteZeroes, or written without any constants: \i..i\1\0 1\i..i\1\0 1\i..i\1\0 1\i..i\1\0 0.\x\b..b\1\0 0.x x\x\b..b\1\0 0.x x;

The opposite process is done to parse an output back into a string.

Examples

SKI Combinators, proving Turing-Completeness

S\x\y\z . . x z . x y;
K\x\y y;
I\x x;

Cat program.

main \x x;

Church numeral encoding.

0c \x x;
++ \n \x . n . x x;