# 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;