Tarski
| Paradigm(s) | Functional |
|---|---|
| Designed by | Chase Roycroft |
| Appeared in | 2021 |
| Computational class | Turing complete |
| Major implementations | Python |
| Influenced by | Underload |
| File extension(s) | .tarski |
Tarski is a stack-based esoteric programming language inspired by the theory of concatenative combinators, and by Underload specifically. It's named after Alfred Tarski, the famous mathematician and philosopher, and its name is intentionally suggestive of a Turing Tarpit and of the SKI calculus, although it is more closely related to the BCKW calculus. It is purely functional, lends itself to tacit (aka pointfree) programming, and is homoiconic by virtue of its quotation feature. It was created by Chase Roycroft and has a reference implementation in Python.
Commands
Tarski has six basic operations, plus an optional one. All other characters are Nops.
- * : [A] [B] — [A B]
- Concatenate the top element of the stack to the end of the second element of the stack.
- ~ : [A] [B] — [B] [A]
- Swap the top two elements of the stack.
- ? : [A] —
- Drop/Discard the top element of the stack.
- ! : [A] — [A] [A]
- Copy/Duplicate the top element of the stack.
- ' : [A] — [ [A] ]
- Quote the top element of the stack.
- ` : [A] — A
- Call/Unquote the top element of the stack.
- [A] : — [A]
- Push everything enclosed in brackets onto the stack.
Notational Choices
The names are pretty standard. The question mark for Drop and exclamation point for Dup are meant to evoke the exponential modalities in linear logic, which allow propositions to be arbitrarily discarded and duplicated, respectively. These modalities are related to the topological operations of interior and closure. Unfortunately, this is the reverse of how ! is used in Underload. Naturally, quotation is represented as a single quote / tick, and dequotation is represented as a backtick, like Unlambda's apply operator. The bracket notation is optional because it is convenient, but not purely concatenative.
Examples
Hello, world!
[Hello, world!]
Factorial
(produces the factorial of however many exclamation points are in the first set of parentheses)
[!!!!!!!]![![[`![]~[[!]*~`]'~*`??[]~`]]~*[]~``]~[`'[*~`]*'~*[]~`?[]~`]'~**`??`
Quine
[!'~*]!'~*
Slight modification that recursively calls itself.
[!'~*`]!'~*`
Truth Machine
(Produces one element based on the Boolean in the first set of parentheses)
[~?][[1][~!*~!`]!`]~0~``
Additional Examples
Additional examples, including 99 bottles of beer and FizzBuzz are forthcoming.
Programming Tips
Unlike most programming languages, including Underload, Tarski has no way to output data. Instead, it is suggested to transform the program itself into its output. Comments can usefully be included as quotations followed by Drop.
Booleans
Tarski uses Church Booleans. True takes two arguments, and Drops the second. False takes two arguments and Drops the first.
| Boolean | Expression |
|---|---|
| True | ~? |
| False | ? |
Numbers
In Tarski, a natural number 'n' is represented as a program which takes the top element of the stack, and replaces it by n concatenated copies of itself. This is related to the idea of Church numerals. For example, the numbers 0-9 can be written in the following short forms. For a longer list, see Numbers.
| Number | Expression |
|---|---|
| 0 | ?[] |
| 1 | [empty]? |
| 2 | !* |
| 3 | !!** |
| 4 | !*!* |
| 5 | !!*!** |
| 6 | !!**!* |
| 7 | !!!**!** |
| 8 | !*!*!* |
| 9 | !!**!!** |
The basic operations are closely related to arithmetic operations on these numbers. Drop, for example, is related to zero, while Dup is related to two, and Cat and Call are related to multiplication and exponentiation respectively. There's no basic operation corresponding to addition, but it can be formed as follows:
| Operation | Expression |
|---|---|
| + | [~]~**[!]~*[*]* |
| * | * |
| ^ | ` |
Curiously, the arithmetical combinators are functionally complete, and the fragment without addition corresponds to linear lambda calculus. The author welcomes suggestions for extending numbers to include negative numbers and rational numbers. This could be done with pairs of numbers using the Grothendieck Construction. It would be cool to use the Stern-Brocot tree somehow.
Lists and tuples
Quotation provides a straightforward way of implementing lists.
Characters and Strings
I'm not sure how best to represent characters. Maybe as lists/quotations of Booleans interpreted as ASCII. Strings, presumably, would be lists/quotations of characters.