10
$\begingroup$

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.

$\endgroup$
15
  • 1
    $\begingroup$ 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. $\endgroup$
    – kaya3
    Aug 30, 2023 at 22:24
  • 1
    $\begingroup$ 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). $\endgroup$
    – kaya3
    Aug 30, 2023 at 22:42
  • 1
    $\begingroup$ 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 addresses one possible concern someone might have. $\endgroup$ Aug 30, 2023 at 23:00
  • 1
    $\begingroup$ 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). $\endgroup$
    – kaya3
    Aug 30, 2023 at 23:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – kaya3
    Aug 30, 2023 at 23:21

2 Answers 2

5
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

Zot is based on 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 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, 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:

<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.

$\endgroup$
2
  • $\begingroup$ I was hoping for something with a type system, but I realized that that is unlikely to be possible. $\endgroup$ Aug 31, 2023 at 7:45
  • $\begingroup$ 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. $\endgroup$
    – kaya3
    Aug 31, 2023 at 11:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .