ULEX
Paradigm(s)  Functional Stringrewriting 

Designed by  ULEXdev 
Appeared in  2024 
Memory system  Cellbased 
Computational class  Turing complete 
Major implementations  Original 
Influenced by  Brainfuck λcalculus 
File extension(s)  .txt 
ULEX is a minimalist programming language based on a variation of λcalculus envisioned in the 80s by Nicolaas Govert de Bruijn.
Language overview
The whole language boils down to a set of valid expressions represented by strings and a function capable of doing reductions on them, following both the string rewriting and functional paradigms.
Etymology
ULEX is both an acronym meaning (U)nnamed (L)ambda (Ex)pressions and a homage to the uppercase "LISP", a family of programming languages based on the functional paradigm. Large programs written in the language may contain many asterisk characters which can resemble the needles of the plant Ulex europaeus, trivia that gave the language its six pointed star symbol.
Author's note:
I admit that FLUX ([F]unctional [L]anguage of [U]nnamed e[X]pressions) would've been a better name choice if it wasn't already picked before I created it. Since ULEX is also a valid english word we'll roll with it!
Specifications
The following EBNF notation explains how to form valid *expressions:
expression = redex  function  placeholder; redex = '(', expression, '', expression, ')'; function = expression, '<'; placeholder = '*'*;
Once an expression is valid, each character can be interpreted according to the table below:
Character  Name  Use 

<

Less than sign  Ending functions 
(

Left parenthesis  Starting redexes 


Vertical bar  Separating redex functions and arguments 
)

Right parenthesis  Ending redexes 
*

Asterisk  Starting and ending placeholders 
The main difference between ULEX and λcalculus is the way variables are handled. With λexpressions a finite length name must be assigned to each variable, but if De Bruijn indices are used then each variable is assigned a natural number according to its scope inside function expressions, excluding the need for names altogether. In this sense, ULEX uses a metavariable scheme which disposes the use of types beyond the valid expressions defined previously.
Combinator  λexpression  *expression 

I  λx.x

*<

K  λxy.x

**<<

S  λxyz.xz(yz)

((****)(***))<<<

Y  λf.(λx.f (x x)) (λx.f (x x))

((**(**))<(**(**))<)<

Execution
Executing a piece of ULEX code is not as straight forward as in imperative languages: a reduction might not give the result straight away, instead relying in a sequence of steps much like with instruction registers in modern CPUs. With arbitrary memory to store a copy of the string containing the valid *expression, successive reductions take place until the result is invariant with relation to the source expression, that is, a reduction no longer changes the string.
Reductions
Redex expressions are defined by an ordered pair of two other expressions, respectively called the redex function and redex argument. Placeholders are strings of asterisks interpreted as natural numbers. An interpreter for ULEX models the reduction function β, which takes an input string s containing a redex expression and yields the reduced string s'. An example of reduction is presented below:
// redex function = *< // redex argument = *** s = (*<***) β(s) = ***
In *expressions every placeholder corresponds to a numbered function scope that indicates which metavariable belongs to each function expression. Placeholders not belonging to the outermost function scope will not be replaced by the redex argument during a βreduction:
s = (*<<***) β(s) = *<
Additionally, all placeholders members of redex functions and arguments which are free get rebound to their new scope, property demonstrated by the examples below.
// rebinding a redex function with scope 6 to 5: s = (******<*) β(s) = *****
// rebinding a redex argument from scope 2 to 4: s = (***<<<**) β(s) = ****<<
Generally, βreductions act as function applications using placeholders as variables, with special cases for scope rebinding. In this fashion, halting can be achieved by stopping computations if s = β(s)
.
Examples
By using a preprocessor and a *expression catalog it's possible to write and read humanreadable code that can be expanded directly into ULEX with the help of extra formatting by placing parentheses in operators which must take precedence, like in the following example:
// FALSE = *<< // TRUE = **<< // AND = ((***)**)<< AND TRUE FALSE // original string ((***)**)<< **<< *<< // expanded macros ((((***)**)<<**<<)*<<) // inserted parentheses (((**<<*)**<<)<*<<) // reduction 1 ((**<<*<<)**<<) // reduction 2 (*<<<**<<) // reduction 3 *<< // reduction 4 FALSE // translated macro
Edge cases
Minification
Metalanguage
Conventions
Following the normal order of application (leftmost innermost redexes are reduced first)