In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
A programming language is a system of notation for writing computer programs.
I've collected here a handful of notes on the various languages that I've had the opportunity to use in the past.
Nowadays, my focus is principally on concatenative languages, namely Uxntal. In concatenative languages all expressions denote functions, and the juxtaposition of expressions denotes function composition, which I found was a way of programming that most resonated with how I think.
Point-free programming is a programming paradigm in which function definitions do not identify the arguments on which they operate. Instead the definitions merely compose other functions, among which are combinators that manipulate the arguments.
Assembly languages have a strong correspondence between the operands and the architecture.
A programming language is low level when its programs require attention to the irrelevant.
Two-dimensional languages are programming systems where programs are transformations of cells on a 2D grid.
One way to simulate a two-dimensional cellular automaton is with an infinite sheet of graph paper along with a set of rules for the cells to follow. The vast majority of cellular automata are also considered rewriting languages, but I've collected here only the graphical ones.
Expressions in a point-free language denote functions, and the juxtaposition of expressions denotes function composition.
The point-free programming paradigm is where function definitions do not identify the arguments on which they operate. Instead the definitions merely compose other functions, among which are combinators that manipulate the arguments.
- All terms denote functions.
- All functions are unary application on a stack, or queue.
- Juxtaposition denotes a composition of functions.
A stack-oriented language, in which whitespace is composition, allows programs to be interpreted and evaluated faster, since no syntax analysis is required, only lexical analysis. Lexical analysis is the process of converting a sequence of characters in a source code file into a sequence of tokens, and syntax analysis is the validation of these tokens according to the rules of the programming language.
The postfix notation is an economic way to express computations syntactically as it has no precedence rules and the stack-passing mechanism simplifies the handling of multiple return values.
Properties of Concatenative Languages
- Concatenative languages are necessarily point-free as allowing terms to denote variables would violate the rule that all terms denote functions.
- The reduction of any expression is the simplification of one function to another function; it is never necessary to deal with the application of functions to objects. This property separates them from the otherwise similar function-level languages of John Backus, which are applicative.
- Any subexpression can be replaced with a name that represents the same subexpression. This is referred to in the concatenative community as factoring.
- The syntax and semantics of concatenative languages form the algebraic structure of a monoid.
The corollary to the presence of stack operation in the code which have nothing to do with the problem domain, like pop, swap, and dup; are the let and label tokens.
Truth be told, the amount of good research into concatenative languages is nearly non-existent.
Bestiary
| Single Items | |
|---|---|
| drop/pop/zap | ( a -- ) |
| dup | ( a -- a a ) |
| nip | ( a b -- b ) |
| swap | ( a b -- b a ) |
| over/peek | ( a b -- a b a ) |
| tuck | ( a b -- b a b ) |
| rot/dig | ( a b c -- b c a ) |
| -rot/bury | ( a b c -- c a b ) |
| poke/snatch | ( a b c -- b c ) |
| flip/spin | ( a b c -- c b a ) |
| roll | ( a b c d -- b c d a ) |
| -roll | ( a b c d -- d a b c ) |
| Quoted Items | |
| unit | ( a -- [a] ) |
| identity | ( [a] -- a ) |
| rep | ( [a] -- a a ) |
| run | ( [a] -- a [a] ) |
| cons | ( a [b] -- [a b] ) |
| sons | ( a [b] -- [a b] a ) |
| dip | ( a [b] -- b a ) |
| cat/compose | ( [a] [b] -- [a b] ) |
| sap | ( [a] [b] -- b a ) |
| swat/prepose | ( [a] [b] -- [b a] ) |
| take | ( [a] [b] -- [b [a]] ) |
| tack | ( [a] [b] -- [a [b]] ) |
| sip | ( b [a] -- b a b ) |
| cake | ( a [b] -- [a b] [b a] ) |
Applicative languages are functional, and applicative is often used as a synonym for functional.
A type of programming in which the program is built from procedures and subroutines.
Rewriting languages are typically made of rules and a starting state.
These languages often have two phases; the first gives a set of rules, and the second provides an accumulator on which those rules are to be applied. For example, a program for a string rewriting system with wildcards begins with a series of rules which define strings to match, a relation(->), and the resulting transformation.
rule swap ?x ?y -> ?y ?x accumulator swap foo bar transformation bar foo
When a rule consumes a specific token during the application, we'll call this token the reagent. When a rule utilizes a specific token that survives the rewrite, we'll call it the catalyst.
dup a -> a a dup is a reagent sub a b -> sub sub is a catalyst
Bestiary
| Reducers | |
|---|---|
| erase | a -> |
| subtract | a b -> |
| join | b c -> a |
| halve | a a -> a |
| Movers | |
| move | a -> b |
| ring(blink) | a -> b b -> a |
| ring | a -> b b -> c c -> a |
| Growers | |
| duplicate | a -> a a |
| double | a -> b b |
| fork | a -> b c |
- Pocket Rewriting, a multiset rewriting zine.
- Horadric, a rewriting mailing list.