3 ms·
Concatenative languages [1] have the property that every token sequence is a valid program. For languages using single bits as tokens, every bit sequence is a
by tromp 3y ago
Concatenative languages [1] have the property that every token sequence is a valid program.
For languages using single bits as tokens, every bit sequence is a valid program. One such language is Chris Barker's zot [2].
Inspired by zot, I defined a concatenative version of Binary Lambda Calculus that shares the same property [3].
[1] https://en.wikipedia.org/wiki/Concatenative_programming_language https://en.wikipedia.org/wiki/Concatenative_programming_lang...
[2] https://en.wikipedia.org/wiki/Iota_and_Jot#Zot https://en.wikipedia.org/wiki/Iota_and_Jot#Zot
[3] https://cstheory.stackexchange.com/questions/32309/concatenative-binary-lambda-calculus-combinatory-logic https://cstheory.stackexchange.com/questions/32309/concatena...
- deathanatos 3y ago> Concatenative languages [1] have the property that every token sequence is a valid program. I don't think this is correct? Concatenative languages have the property that if a and b are both valid programs, that the program a || b is valid (where || means "concatenate"). But that property doesn't imply that every sequence of tokens is valid. For example, in Cat, [1 2 is not grammatically valid.
- tromp 3y agoYou're right. I should have qualified it as "some concatenative languages".
- joshmarlow 3y agoIs there a particular term for concatenative languages with this property?
- contravariant 3y agoTrivially it's all concatenative languages where each single token is valid. Not sure if they have a name but I would be tempted to call it a free language.
- YeGoblynQueenne 3y agoSo does Prolog count as a concatenative language given the standard definition of concatenative languages? For context, a Prolog program is a set of definite clauses so the union of two Prolog programs is a Prolog program. In fact, this property forms the basis of the concept of (syntactic) generality in Prolog: if P1, P2, P3 are three Prolog programs such that P1 is the union of P2 and P3, then we say that P1 generalises each of P2 and P3. Does this concept of generality also exist for concatenative languages?
- dheera 3y agoThey used an OCR program though, which probably has a bias toward attempting to close parentheses.
- kqr 3y ago> making Jot a natural Gödel numbering of all algorithms. This sounds very cool. I wish I understood both Jot and that sentence.
- tromp 3y agoA Gödel numbering is simply a mapping to integers (that is easily decoded). If your programs are arbitrary binary strings, then you're basically already done, since bitstrings are in 1-1 correspondence with integers: empty 0 1 00 01 10 11 000 001 ... 0 1 2 3 4 5 6 7 8 ...
- Dylan16807 3y ago> A Gödel numbering is simply a mapping to integers (that is easily decoded). "easily" is arguable. Sure, I could multiply/factor an enormous number and count how many copies of each prime it has, but I'd much rather concatenate/split some digits.
- thaumasiotes 3y agoFactoring numbers is difficult. Manipulating digits is easy, or it looks that way, but this is partially an illusion resulting from the number being given to you with the digits already known. If you have a quantity in mind but you're not sure what its digits are, it can be a lot of work to learn.
- Dylan16807 3y agoI don't know what you mean by "not sure what its digits are". If you mean what base to represent the number in, that's no more arbitrary than knowing the exact way Gödel numbers use primes.
- pmontra 3y agoMaybe it's an unfair example but: the number of people on Earth. We know the quantity more or less, the leftmost digit in base ten, then it's a lot of work to figure out the other digits.