TFLite

TFLite, short for "Tiny Functional Language (lite)" is a tiny functional language. It was designed by User:RocketRace in 2022 as part of the inaugural round of the Esolang Buffet challenge. The language features first-class functions, non-polymorphic algebraic data types (ADTs), pattern matching, and a terse syntax. The language is structurally similar to Haskell, and "many qualities" of its implementation were allegedly "inspired by V." https://eb.esolangs.gay/1/tflite.py
== Feature set ==
Being a declarative language, TFLite programs consist of a set of declarations. Each declaration may either be an ADT declaration or a function declaration. Declarations are delimited by either line feeds or semicolons. Every declaration begins with a one-character naming tag. ADTs are tagged with capital ASCII letters, functions are tagged with lowercase ASCII letters, and the special entry point function is tagged with a caret (^). In general, names in TFLite are limited to a single character in length, with capitals reserved for ADT names and constructors and the caret reserved for the entry point.
Extraneous whitespace, as well as empty declarations, are ignored in source code. Be wary that there is no notion of a "comment" in the original specification of the language.
=== ADTs ===
ADTs in TFLite are defined as sums of products. Their variants are separated via a bar (|), whereas their fields are simply juxtaposed. Fields, if present, must reference another ADT — there are no generic ADTs in TFLite. Declarations may also be recursive.
 BT|F
 NZ|SN
The first declaration here defines B with two named variants: T and F. This is the standard definition of a boolean type. The second declaration is a definition of Peano numerals with Z as 0 and SN as the successor of a number.
 UU
 TLU|BTT
There are two declarations here: A unit type U, and a binary tree T with units U at its leaves L. Notice that the tree branches B are recursive, referring to T twice.
=== Function declarations ===
Function declarations consist of a one-character tag and a one-character numeric arity (from 0 to 9), followed by a sequence of function arms. A function arm is a pattern followed by an expression, such that the function (when called) evaluates to that expression iff its arguments match the given pattern. Patterns are attempted sequentially, so the first matching pattern determines the output of the function. Pattern matching through function arms is the primary mechanism used for conditional evaluation.
A function pattern may consist of the following:
* A variable pattern (e.g. x), which matches any arguments and binds a name for the scope of the function
* A wildcard pattern _, which matches and promptly ignores any argument
* An ADT pattern (e.g. U, Blr or SSS_), beginning with an ADT variant name and followed by further (possibly recursive) patterns. The number of following patterns is determined by the number of fields in the given ADT variant.
 k2xyx
This function implements the K combinator. It is a projection taking in two arguments x and y, and returning x.
 BT|F
 a2TTT|Txx|F_F
The a function is a slightly roundabout definition of the binary AND operation on booleans. It has three branches (for the sake of demonstration). The first matches if both of the 2 arguments are T, the second matches T and any boolean x, and the third matches F and any boolean _.
=== Function application & anonymous functions ===
Functions are called using juxtaposition. Multiple parameters may be passed to a function via currying. Function application is left-associative, but parentheses () may be used to group applications together as needed. Like ADTs, functions may also be recursive.
Anonymous functions can be used wherever an expression is expected. They are identical to regular function definitions, except they lack a tag and are enclosed in square brackets [].
 BT|F
 LN|CBN
 m2_NN|fCxyC(fx)(mfy)
 n1xm[1TF|FT]x
This snippet begins with the definition for booleans, as well as linked lists of booleans. The m function implements a map over a list, inputting two arguments: a function and a list. If the argument list is empty, the function short-circuits and returns N. Otherwise, it applies the given function to the head of the list and conses the result to a recursive call mfy to the tail of the list. Lastly, the n function maps an anonymous function (an inline definition of boolean NOT) over its argument list, consequently negating each of its elements.
== I/O ==
A TFLite program takes input and returns output using the specially named ^ function. It is the entry point to TFLite programs.
There is no rigorously defined I/O format. The original specification suggests using ADT expressions (e.g. S(S(S(S(SN))))) as a standard string-based format for input and output, but the accompanying implementation only supports it partially. Furthermore, due to the lack of a standard library, the variant names used as input & output are arbitrary and depend on their definition inside the program itself.
== Computational complexity ==
TFLite can trivially implement the SKI combinator calculus:
SKI	TFLite
I 	[1xx]
K 	[2x_x]
S 	[3xyzxz(yz)]
== Examples ==
Below is the first official program written in TFLite. It is an implementation of insertion sort.
 BF|T;NZ|SN;LE|CNL
 g2SxSygxy|S_ZT|__F
 i2xECxE|xCyz[1TCy(ixz)|_Cx(Cyz)](gxy)
 ^1Cxyix(^y)|_E
Here is another implementation of a sorting algorithm. It was written by a different user as part of the Esolang Buffet challenge. Its details are left as an exercise for the reader.
 NZ|SN
 LE|CNL
 g2Z_Z|_ZZ|SySzS(gyz)
 m2Zxx|xZx|SxSyS(mxy)
 b2xCylC(gxy)(b(mxy)l)|xyCxy
 ^1EE|Cxlbx(^l)
And finally a program that returns a list of digits of an input number, using some cursed definitons of subtraction, division and modulo.
 NZ|SN
 MN|JN
 LE|CNE
 t0S(S(S(S(S(S(S(S(S(SZ)))))))))
 a2Zyy|Sxyax(Sy)
 s2xZJx|ZSxN|SxSysxy
 q1Jxx|NZ
 d3_Zzz|JZ_zz|Jxyzd(sxy)y(Sz)|N_zq(sz(SZ))
 m3N_zz|_Zzz|JZ__Z|Jxy_m(sxy)yx
 e2Zyy|xye(d(Jx)tZ)(C(m(Jx)tZ)y)
 ^1xexE
== References ==
Category:Languages
Category:2022
Category:Functional paradigm
Category:Declarative paradigm
Category:Implemented