Conti
| Paradigm(s) | CPS |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2026 |
| Computational class | Turing complete |
| Major implementations | Implemented |
| File extension(s) | .txt |
Conti is an esolang invented by User:Hakerh400 in 2026.
Syntax
The syntax is (roughly) defined as:
<program> ::= <def>+
<def> ::= <ident> "=" <expr>
<ident> ::= [a-zA-Z0-9_\-']+
<expr> ::= <ident> | <group> | <lambda> | <app>
<group> ::= "(" <expr> ")"
<lambda> ::= "\" <ident>+ "," <expr>
<app> ::= <expr> <expr>+
There are some additional contraints though. For instance, in the syntax for application app, the left expr is called target, while the right expr+ is called arguments. One of the constraints is that none of the arguments can be an application (not even directly inside a group). For example, x (y z) is not a valid syntax, because y z is an application, so it cannot be an argument of x.
Another constraint is that all definitions must start with lambda expression. For instance, x = y or x = y z is a syntax error.
Semantics
When the program starts, find the global definition main (if there is no such definition, it is an error). Then call the main function (construct an application) with arguments <inp> and \a, a (\_, <out_1>) (\_, <out_0>). So, the main expression at the start of a program will be:
main <inp> (\a, a (\_, <out_1>) (\_, <out_0>))
Here, <inp> is a special term that cannot be constructed in the source code directly. It is for reading from stdin. Similarly, <out_0> and <out_1> are for writing bits (0 and 1, resp.) to the stdout. Those expressions cannot be constructed from basic terms, but they are passed to the main function when the program starts. Also note that when a lambda expression is the last argument of an application, parentheses can be removed. So the main expression is:
main <inp> \a, a (\_, <out_1>) \_, <out_0>
Then the interpreter reduces the main expression until the program halts.
I/O format
Both input and output are lists of bits. Each input bit is prepended with bit 1. Reading bits after EOF returns 0. Similarly, when an output bit is produced, only bits at odd positions are considered (0-indexed), while bits at even position are control bits: the first time 0 appears on an even position terminates the program.
Reduction
Iteratively reduce the main expression:
- If it is a lambda expression → Error (or terminate with warning; similar applies to other errors below)
- If it is an identifier → Replace with the corresponding definition
- If it is
<inp>,<out_0>, or<out_1>→ Error - If it is an application:
- If the target is a lambda expression → Beta reduction
- If the target is
<inp>:- If the next input bit is 0 → Replace target with
\a, a \a b, b \a, a - If the next input bit is 1 → Replace target with
\a, a \a b, a \a, a
- If the next input bit is 0 → Replace target with
- If the target is
<out_0>→ Output bit 0 and replace target with\a, a \a, a - If the target is
<out_1>→ Output bit 1 and replace target with\a, a \a, a
Example
This program reverses and inverts the input bits.
id = \a cb, cb a 0 = \a b, b id 1 = \a b, a id ite = \b x y cb, b (\_, cb x) (\_, cb y) not = \b cb, ite b 0 1 cb pair = \a b cb, cb \c, c a b nil = \c, c 0 id cons = \a b cb, pair a b \p, pair 1 p cb caseList = \xs cbNil cbCons, xs \k d, k (\_, d cbCons) \_, cbNil id foldl = \z f xs cb, caseList xs (\_, cb z) \x xs, f z x \z, foldl z f xs cb foldr = \z f xs cb, caseList xs (\_, cb z) \x xs, foldr z f xs \z, f x z cb reverse = \xs cb, foldl nil (\xs x cb, cons x xs cb) xs cb map = \f xs cb, foldr nil (\x xs cb, f x \x, cons x xs cb) xs cb invert = \bs cb, map not bs cb readBits = \inp cb, inp \neof, not neof \eof, eof (\_, cb nil) \_, inp \b, readBits inp \bs, cons b bs cb writeBits = \out bs cb, foldl id (\_ b cb, out 1 \_, out b cb) bs cb ioRun = \f inp out, readBits inp \bs, f bs \bs, writeBits out bs \_, out 0 id main = \inp out, ioRun main1 inp out main1 = \bs cb, reverse bs \bs, invert bs cb