<p>I'm wondering whether its possible to construct a group where the elements are all possible valid programs, with a small or simple generator set. That way you could have a series of operations you can apply to a program to move it from one valid state to another valid state without going through an invalid state (since we are using these operations).</p>
<p>I know this <em>should</em> be possible if syntax is how validity is defined, but I'm more interested in what happens when types get involved, especially when you can make abstractions with them (structs/classes/enums).</p>
<p>I say simple/small, since a set of simple generators that are infinitely or very large should be ok, as long as they are fairly comprehensible to a programmer and follow a pattern. On the other hand, a few complex generators may also be ok, as the programmer could just learn them.</p>
<p>I also think Scratch or other block based languages could be a simple example, because the operation could be adding a block and the generator set could be the set of all blocks (maybe). However, I'm not sure how types (especially compound ones) would fit in here.</p>
<p>Which programming languages have the best generator sets, and what characteristics do they have?</p>
<p>If I've made any mistakes in my assumptions or research (or maybe my question is flawed), please feel free to correct me :).</p>
<p><strong>Clarification</strong>
As for which binary operation, I'm not completely sure. I was thinking of defining it based on the generators themselves. An example of this kind of construction is with  the Rubik’s Cube group, which uses composition of its underlying generators. In this sense, the group operation kind of depends on the generator set, which makes this harder.</p>

<language-design><math><ide>
Can you represent a language with a group with a small/simple generator set?
CC BY-SA 4.0
2023-08-30T22:24:54.687Z
What group operation are you thinking of, to combine two programs to get another program? The obvious binary operator on programs is concatenation, but that doesn't have inverses, and the concatenation of two valid programs may not be valid (e.g. it could declare the same name twice, or have code in an unreachable position). Likewise I do not see how your proposed operation on Scratch programs would define a group.
kaya3
CC BY-SA 4.0
2023-08-30T22:33:28.323Z
I added a clarification.
debater-coder
CC BY-SA 4.0
2023-08-30T22:42:41.060Z
The group operation does not depend on the generator set. You need to have a group, which means a set and a binary operation, before it makes sense to talk about a generating set. For your example of a Rubik's cube, the group elements are the different possible configurations of the Rubik's cube, and the group operation is composition of permutations (i.e. given two configurations A and B, to compose them perform a sequence of actions which transforms the initial configuration into A, and then from there perform a sequence of actions which would transform the initial configuration into B).
kaya3
CC BY-SA 4.0
2023-08-30T22:48:21.170Z
I could see this being interesting, but you might need to be a bit more specific. Not exactly sure how. For example, the additive group of integers is generated by the set containing only the number `1`. You could interpret each integer as the ASCII encoding of a source file with the sign corresponding to the least significant bit (for example). More in the spirit, I think, is bidirectional programming.
David Young
CC BY-SA 4.0
2023-08-30T22:49:11.520Z
I do not see any sensible way to make a group out of the valid programs in any typical programming language ─ it is probably possible to design a special language where the valid programs *modulo behavioural equivalence* form a group under concatenation, but I don't see how one would expect to do this for programming languages in general. But until there is a way to define a group structure on valid programs in some language, there is no way to talk about the size of a generating set.
kaya3
CC BY-SA 4.0
2023-08-30T22:57:28.353Z
Could you represent a group with operations on the AST? I've heard of [Structure editor](https://en.wikipedia.org/wiki/Structure_editor)s for programming languages, where it essentially forces you to perform actions where both the start and end state are syntactically correct. This may be harder to do with having it with correct types. Also, maybe groups are the wrong abstraction for this, but I'm not sure what else you'd use.
debater-coder
CC BY-SA 4.0
2023-08-30T23:00:07.297Z
My first thought is that we could take the group operation to be function composition. Then we might ask if there is a finite set of invertible, computable functions that gives a Turing-complete language under function composition. This seems doable to me. [This](https://cs.stackexchange.com/a/50120/20578) addresses one possible concern someone might have.
David Young
CC BY-SA 4.0
2023-08-30T23:17:52.657Z
The problem with function composition as a group operation on programs, is that in order to be a group, every valid program must correspond with some invertible function. That is, it must be impossible to write a non-invertible function in the language. That's a massive restriction which isn't true for any useful language. *Maybe* it could be a thing in quantum computing, since quantum logic gates are necessarily reversible, but I don't think quantum computing is on-topic here (it's a very different subject and there's not much overlap in expertise).
kaya3
CC BY-SA 4.0
2023-08-30T23:19:19.967Z
Sorry, this may be a silly question, but what is an example of a non-invertible program you can write in a traditional programming language?
debater-coder
CC BY-SA 4.0
2023-08-30T23:21:38.183Z
For example, a program which reads a number from the input, and then outputs the square of that number. It produces the output 4 for the input 2 and also for the input -2, so it is not invertible.
kaya3
CC BY-SA 4.0
2023-08-30T23:27:29.273Z
As I've mentioned earlier, maybe my question is fundamentally flawed as I jumped at the opportunity to try to make it into a group, but all I'm really interested in is a representation where there is a small set of "operations" you can apply to a program to get another valid program. I don't know of any looser structures than a group that does this. Does anyone know of any way to do this?
debater-coder
CC BY-SA 4.0
2023-08-31T00:48:20.713Z
@debater-coder Is [this](https://cstheory.stackexchange.com/a/48222) an example of what you're looking for? If so, I can post it as an answer.
user76284
CC BY-SA 4.0
2023-08-31T02:15:24.947Z
Thanks. It looks like it, but I'll need a proof that it is a group. If you have one, you can post it, if not I'll attempt it myself when I have time.
debater-coder
CC BY-SA 4.0
2023-08-31T12:49:19.420Z
Fixating on the concept of a "group" is a mistake. Your instinct that you can study languages algebraically is entirely correct ("a representation where there is a small set of "operations" you can apply to a program to get another valid program"), but it is being confounded by the fact that maybe the only kind of algebraic structures that you happen to be closely familiar with are groups. Instead, you should look into universal algebra (https://en.wikipedia.org/wiki/Universal_algebra) and the notion of an algebraic structure. In particular, you should look into "Kleene algebras with tests".
Adam Přenosil
CC BY-SA 4.0
2023-08-31T14:13:45.757Z
Since inverses are the problem, perhaps you just want it to be a [monoid](https://en.wikipedia.org/wiki/Monoid).  Then the set of programs is rather trivially a monoid under composition, which you can think of like the pipeline operator `|` in a shell.  The identity element is `cat`.
Nate Eldredge
<h2>Zot</h2>
<p>Based on the comments, I'm assuming you don't really want groups, but any set that could be &quot;generated&quot; in some way. A minimal example is the esolang <a href="http://web.archive.org/web/20200414141014/http://www.nyu.edu/projects/barker/Iota/zot.html" rel="nofollow noreferrer">Zot</a>.</p>
<p>Zot is based on <a href="https://en.wikipedia.org/wiki/SKI_combinator_calculus" rel="nofollow noreferrer">SKI combinator calculus</a>. In SKI combinator calculus, all programs are constructed by the three symbols S, K, I, and function application, where:</p>
<p>S = λa.λb.λc.ac(bc)<br />
K = λa.λb.a<br />
I = λa.a</p>
<p>I is redundant, as it is equivalent to SK* where * could be anything. Function application could mean parentheses, but <a href="http://www.madore.org/%7Edavid/programs/unlambda/" rel="nofollow noreferrer">Unlambda</a> chooses a prefix operator <code>`</code>, so that <code>``ab`cd</code> means <code>((ab)(cd))</code>.</p>
<p>Then someone found out it could be simplified to a single symbol, confusingly named i, and created <a href="http://web.archive.org/web/20201112014512/http://www.nyu.edu/projects/barker/Iota/" rel="nofollow noreferrer">Iota</a>, where:</p>
<p>i = λf.fSK</p>
<p>and</p>
<p><code>`ii</code> = I<br />
<code>`i`ii</code> = KI (aka SK or 0)<br />
<code>`i`i`ii</code> = K<br />
<code>`i`i`i`ii</code> = S<br />
<code>`i`i`i`i`ii</code> = SSK<br />
<code>`i`i`i`i`i`ii</code> = I<br />
...</p>
<p>But the number of <code>`</code> (actually <code>*</code> in Iota) must be one less than <code>i</code>, and there must be less <code>`</code> than <code>i</code> in each suffix. So there is Zot, which removed this restriction, by redefining <code>`</code> as a function, and function applications are done from left to right, starting from the empty program:</p>
<p>&lt;empty program&gt; = λf. f(λret. ret)<br />
` = λcont. λl. l(λlret. λr. r(λrret. cont(lret rret)))<br />
i' = λcont. cont i</p>
<p>Here cont means return the control to the parent node, and is consist of code passed from the parent node, effectively a part of the parent node. The result would be returned as ret, lret or rret to the code in the parent node.</p>
<p>There is also Jot removing the restriction in another way, but I think Zot is constructed better. In a hypothetical new language, you could change <code>`</code> to <code>(</code> and make it scan for the symbols only until a <code>)</code> is reached, to support parentheses like in most practical languages. It effectively provided a way to define any brackets, and even half brackets, just like any other elements in the language. Code with unpaired brackets would be made meaningful. And the special syntaxes such as in the class definitions could just work like started with an alternative bracket.</p>
<h2>Group</h2>
<p>If you really want to make the language mathematically a group, it may have to be concatenative and reversible.</p>
<p>Most concatenative languages don't support unpaired brackets, or may change the meaning when two programs with unpaired brackets are concatenated. But supporting unpaired brackets seems easy. We just make the stack for parsing expressions a part of the input and output if it is not empty. Zot itself is not concatenative, but ideas in it might be used to cover cases that are otherwise errors.</p>
<p>Making something reversible is also easy if you know exactly what you are doing. Just make multiple versions of the memory, initialize all versions to zero, and use xor instead of assignment to write new versions. There is just not much reason to use the inverse operations in such a model in practical programs.</p>

CC BY-SA 4.0
2023-08-31T06:05:11.387Z
2023-08-31T06:05:11.387Z
user23013
CC BY-SA 4.0
2023-08-31T07:45:24.937Z
I was hoping for something with a type system, but I realized that that is unlikely to be possible.
debater-coder
CC BY-SA 4.0
2023-08-31T11:23:12.977Z
The problem with splitting unpaired brackets across multiple group elements is that if `(x` and `y)` are both legal programs then `y)` has to be a legal program. What you could do is have `(x y)` expressed as `(x) (y) join`, where `join` is an operator in the language which concatenates two quotes. Then you don't need unmatched parentheses in any valid programs, and you can have a finite set of "generators" while using `join` to build arbitrary quotes.
kaya3
<p>There is a notion studied in computability theory and category theory. A <strong>partial combinatory algebra</strong> (PCA) is a set <span class="math-container">$A$</span> equipped with a binary partial operation <span class="math-container">$A \times A \rightharpoonup A$</span>, written as left associative multiplication, such that</p>
<ul>
<li>There exists an element <span class="math-container">$k$</span> with <span class="math-container">$kxy = x$</span>.</li>
<li>There exists an element <span class="math-container">$s$</span> with <span class="math-container">$sxyz = (xz)(yz)$</span> and <span class="math-container">$sxy$</span> is always defined.</li>
</ul>
<p>Of course, you can require the operation to be total, getting the definition of <em>total</em> combinatory algebras. But since we usually want programs to be able to fail, panic, diverge or raise exceptions, partial combinatory algebras are more useful.</p>
<p>For example, the syntax of untyped lambda calculus or untyped SKI combinators <em>quotiented under <span class="math-container">$\beta\eta$</span>-equivalence</em> form a <strong>total</strong> combinatory algebra. The normal forms of untyped lambda calculus or untyped SKI calculus form a partial combinatory algebra. There are typed versions too: simply make ill-typed combinations undefined. You can similarly turn your favourite programming language into a partial combinatory algebra.</p>
<p>PCAs are extremely useful because we can use them to build categorical models of computation (including hypercomputation). You can build a topos <span class="math-container">$\textsf{Rz}(A)$</span> out of every PCA. A topos is a mathematical &quot;universe&quot; in which you can do essentially any math, except each topos has its distinct features. In <span class="math-container">$\textsf{Rz}(A)$</span>, every function is computable (in a suitable sense determined by <span class="math-container">$A$</span>), and thus we automatically get algorithms from mathematical proofs!</p>

CC BY-SA 4.0
2023-08-31T07:52:52.157Z
2023-08-31T07:52:52.157Z
Trebor
# Can you represent a language with a group with a small/simple generator set?
Posted by: username_0 on 2023-08-30
I'm wondering whether its possible to construct a group where the elements are all possible valid programs, with a small or simple generator set. That way you could have a series of operations you can apply to a program to move it from one valid state to another valid state without going through an invalid state (since we are using these operations).

I know this *should* be possible if syntax is how validity is defined, but I'm more interested in what happens when types get involved, especially when you can make abstractions with them (structs/classes/enums).

I say simple/small, since a set of simple generators that are infinitely or very large should be ok, as long as they are fairly comprehensible to a programmer and follow a pattern. On the other hand, a few complex generators may also be ok, as the programmer could just learn them.

I also think Scratch or other block based languages could be a simple example, because the operation could be adding a block and the generator set could be the set of all blocks (maybe). However, I'm not sure how types (especially compound ones) would fit in here.

Which programming languages have the best generator sets, and what characteristics do they have?

If I've made any mistakes in my assumptions or research (or maybe my question is flawed), please feel free to correct me :).

**Clarification**
As for which binary operation, I'm not completely sure. I was thinking of defining it based on the generators themselves. An example of this kind of construction is with the Rubik’s Cube group, which uses composition of its underlying generators. In this sense, the group operation kind of depends on the generator set, which makes this harder.
**Tags:** language-design math ide
> **Comments:**
> **username_1**: What group operation are you thinking of, to combine two programs to get another program? The obvious binary operator on programs is concatenation, but that doesn't have inverses, and the concatenation of two valid programs may not be valid (e.g. it could declare the same name twice, or have code in an unreachable position). Likewise I do not see how your proposed operation on Scratch programs would define a group.  
> **username_0**: I added a clarification.  
> **username_1**: The group operation does not depend on the generator set. You need to have a group, which means a set and a binary operation, before it makes sense to talk about a generating set. For your example of a Rubik's cube, the group elements are the different possible configurations of the Rubik's cube, and the group operation is composition of permutations (i.e. given two configurations A and B, to compose them perform a sequence of actions which transforms the initial configuration into A, and then from there perform a sequence of actions which would transform the initial configuration into B).  
> **username_2**: I could see this being interesting, but you might need to be a bit more specific. Not exactly sure how. For example, the additive group of integers is generated by the set containing only the number `1`. You could interpret each integer as the ASCII encoding of a source file with the sign corresponding to the least significant bit (for example). More in the spirit, I think, is bidirectional programming.  
> **username_1**: I do not see any sensible way to make a group out of the valid programs in any typical programming language ─ it is probably possible to design a special language where the valid programs *modulo behavioural equivalence* form a group under concatenation, but I don't see how one would expect to do this for programming languages in general. But until there is a way to define a group structure on valid programs in some language, there is no way to talk about the size of a generating set.  
> **username_0**: Could you represent a group with operations on the AST? I've heard of [Structure editor](https://en.wikipedia.org/wiki/Structure_editor)s for programming languages, where it essentially forces you to perform actions where both the start and end state are syntactically correct. This may be harder to do with having it with correct types. Also, maybe groups are the wrong abstraction for this, but I'm not sure what else you'd use.  
> **username_2**: My first thought is that we could take the group operation to be function composition. Then we might ask if there is a finite set of invertible, computable functions that gives a Turing-complete language under function composition. This seems doable to me. [This](https://cs.stackexchange.com/a/50120/20578) addresses one possible concern someone might have.  
> **username_1**: The problem with function composition as a group operation on programs, is that in order to be a group, every valid program must correspond with some invertible function. That is, it must be impossible to write a non-invertible function in the language. That's a massive restriction which isn't true for any useful language. *Maybe* it could be a thing in quantum computing, since quantum logic gates are necessarily reversible, but I don't think quantum computing is on-topic here (it's a very different subject and there's not much overlap in expertise).  
> **username_0**: Sorry, this may be a silly question, but what is an example of a non-invertible program you can write in a traditional programming language?  
> **username_1**: For example, a program which reads a number from the input, and then outputs the square of that number. It produces the output 4 for the input 2 and also for the input -2, so it is not invertible.  
> **username_0**: As I've mentioned earlier, maybe my question is fundamentally flawed as I jumped at the opportunity to try to make it into a group, but all I'm really interested in is a representation where there is a small set of "operations" you can apply to a program to get another valid program. I don't know of any looser structures than a group that does this. Does anyone know of any way to do this?  
> **username_3**: @debater-coder Is [this](https://cstheory.stackexchange.com/a/48222) an example of what you're looking for? If so, I can post it as an answer.  
> **username_0**: Thanks. It looks like it, but I'll need a proof that it is a group. If you have one, you can post it, if not I'll attempt it myself when I have time.  
> **username_4**: Fixating on the concept of a "group" is a mistake. Your instinct that you can study languages algebraically is entirely correct ("a representation where there is a small set of "operations" you can apply to a program to get another valid program"), but it is being confounded by the fact that maybe the only kind of algebraic structures that you happen to be closely familiar with are groups. Instead, you should look into universal algebra (https://en.wikipedia.org/wiki/Universal_algebra) and the notion of an algebraic structure. In particular, you should look into "Kleene algebras with tests".  
> **username_5**: Since inverses are the problem, perhaps you just want it to be a [monoid](https://en.wikipedia.org/wiki/Monoid).  Then the set of programs is rather trivially a monoid under composition, which you can think of like the pipeline operator `|` in a shell.  The identity element is `cat`.  
---
## 2 answers
### Answer by username_7 on 2023-08-31. Score: 5 | Accepted answer
There is a notion studied in computability theory and category theory. A **partial combinatory algebra** (PCA) is a set $A$ equipped with a binary partial operation $A \times A \rightharpoonup A$, written as left associative multiplication, such that

* There exists an element $k$ with $kxy = x$.
* There exists an element $s$ with $sxyz = (xz)(yz)$ and $sxy$ is always defined.

Of course, you can require the operation to be total, getting the definition of *total* combinatory algebras. But since we usually want programs to be able to fail, panic, diverge or raise exceptions, partial combinatory algebras are more useful.

For example, the syntax of untyped lambda calculus or untyped SKI combinators *quotiented under $\beta\eta$-equivalence* form a **total** combinatory algebra. The normal forms of untyped lambda calculus or untyped SKI calculus form a partial combinatory algebra. There are typed versions too: simply make ill-typed combinations undefined. You can similarly turn your favourite programming language into a partial combinatory algebra.

PCAs are extremely useful because we can use them to build categorical models of computation (including hypercomputation). You can build a topos $\textsf{Rz}(A)$ out of every PCA. A topos is a mathematical "universe" in which you can do essentially any math, except each topos has its distinct features. In $\textsf{Rz}(A)$, every function is computable (in a suitable sense determined by $A$), and thus we automatically get algorithms from mathematical proofs!
---
### Answer by username_6 on 2023-08-31. Score: 3
## Zot

Based on the comments, I'm assuming you don't really want groups, but any set that could be "generated" in some way. A minimal example is the esolang [Zot](http://web.archive.org/web/20200414141014/http://www.nyu.edu/projects/barker/Iota/zot.html).

Zot is based on [SKI combinator calculus](https://en.wikipedia.org/wiki/SKI_combinator_calculus). In SKI combinator calculus, all programs are constructed by the three symbols S, K, I, and function application, where:

S = λa.λb.λc.ac(bc)  
K = λa.λb.a  
I = λa.a

I is redundant, as it is equivalent to SK\* where \* could be anything. Function application could mean parentheses, but [Unlambda](http://www.madore.org/%7Edavid/programs/unlambda/) chooses a prefix operator ```, so that ```ab`cd` means `((ab)(cd))`.

Then someone found out it could be simplified to a single symbol, confusingly named i, and created [Iota](http://web.archive.org/web/20201112014512/http://www.nyu.edu/projects/barker/Iota/), where:

i = λf.fSK

and

``ii` = I  
``i`ii` = KI (aka SK or 0)  
``i`i`ii` = K  
``i`i`i`ii` = S  
``i`i`i`i`ii` = SSK  
``i`i`i`i`i`ii` = I  
...

But the number of ``` (actually `*` in Iota) must be one less than `i`, and there must be less ``` than `i` in each suffix. So there is Zot, which removed this restriction, by redefining ``` as a function, and function applications are done from left to right, starting from the empty program:

= λf. f(λret. ret)  
` = λcont. λl. l(λlret. λr. r(λrret. cont(lret rret)))  
i' = λcont. cont i

Here cont means return the control to the parent node, and is consist of code passed from the parent node, effectively a part of the parent node. The result would be returned as ret, lret or rret to the code in the parent node.

There is also Jot removing the restriction in another way, but I think Zot is constructed better. In a hypothetical new language, you could change ``` to `(` and make it scan for the symbols only until a `)` is reached, to support parentheses like in most practical languages. It effectively provided a way to define any brackets, and even half brackets, just like any other elements in the language. Code with unpaired brackets would be made meaningful. And the special syntaxes such as in the class definitions could just work like started with an alternative bracket.

## Group

If you really want to make the language mathematically a group, it may have to be concatenative and reversible.

Most concatenative languages don't support unpaired brackets, or may change the meaning when two programs with unpaired brackets are concatenated. But supporting unpaired brackets seems easy. We just make the stack for parsing expressions a part of the input and output if it is not empty. Zot itself is not concatenative, but ideas in it might be used to cover cases that are otherwise errors.

Making something reversible is also easy if you know exactly what you are doing. Just make multiple versions of the memory, initialize all versions to zero, and use xor instead of assignment to write new versions. There is just not much reason to use the inverse operations in such a model in practical programs.
> **Comments:**
> **username_0** (2023-08-31): I was hoping for something with a type system, but I realized that that is unlikely to be possible.  
> **username_1** (2023-08-31): The problem with splitting unpaired brackets across multiple group elements is that if `(x` and `y)` are both legal programs then `y)` has to be a legal program. What you could do is have `(x y)` expressed as `(x) (y) join`, where `join` is an operator in the language which concatenates two quotes. Then you don't need unmatched parentheses in any valid programs, and you can have a finite set of "generators" while using `join` to build arbitrary quotes.  
---
