<p>In my book &quot;Jezici za gimnazijalce&quot; (not available online) and in my Bachelor thesis (which will be online in about a month) I was claiming that assembly languages are like the <a href="https://en.wikipedia.org/wiki/Pirah%C3%A3_language" rel="nofollow noreferrer">Piraha language</a> in that both of them don't support linguistic recursion.</p>
<p>However, I can't help but notice that some assembly languages do indeed support linguistic recursion. WebAssembly Text Format is usually considered an assembly language, but it is written in S-expressions. If it's written in S-expressions, it obviously supports linguistic recursion. However, one can easily argue that WebAssembly Text Format is not a real assembly language.</p>
<p>PicoBlaze assembly language doesn't support linguistic recursion, I can be certain of that because I made <a href="https://picoblaze-simulator.sourceforge.io" rel="nofollow noreferrer">an assembler for PicoBlaze</a> for my Bachelor thesis. I added the support for arithmetic expressions in constants and some other things, but that's still not real linguistic recursion because arithmetic expressions in constants don't allow one to embed one directive into another (<code>load (load s0, s1), s2</code> is invalid assembly directive, and so is any similar one).</p>
<p>However, I am not sure about x86 assembly. Does it have some directive that expect another directive as an operand? My <a href="https://flatassembler.github.io/compiler.html" rel="nofollow noreferrer">Arithmetic Expression Compiler</a>, which outputs x86 assembly, doesn't output any such directive, but that doesn't mean there aren't such directives in x86 assembly.</p>

<recursion><assembly>
Does x86 assembly support linguistic recursion?
CC BY-SA 4.0
2023-10-19T15:46:30.677Z
By "linguistic recursion," do you mean terms that have non-trivial subterms? That terms can be (non-trivially) nested?
David Young
CC BY-SA 4.0
2023-10-19T15:46:33.377Z
There is no one x86 assembly/assembler — there are a dozen different assemblers each with their own syntax and directives.  MASM has macros, though, which might be considered capable of recursion, since one macro can invoke another.
Erik Eidt
CC BY-SA 4.0
2023-10-19T15:49:46.750Z
I'm asking because I am not familiar with the phrase "linguistic recursion." Looking it up, it seems to be a phrase that describes something in natural language. It's not immediately, completely clear to me how it should apply to programming languages.
David Young
CC BY-SA 4.0
2023-10-19T15:50:02.043Z
As far as machine code instructions, x86 family has a wide range of prefix instructions/opcodes that modify the operations/interpretation of next instruction in a variety of ways.  See here, and look for "prefix" https://en.wikipedia.org/wiki/X86_instruction_listings  Further, prefixes can be combined.
Erik Eidt
CC BY-SA 4.0
2023-10-19T22:30:18.257Z
At the risk of stating the obvious, most assemblers support constant expressions.
Pseudonym
CC BY-SA 4.0
2023-10-20T14:11:25.867Z
Does x86 (or any other) machine code support "linguistic recursion"? Perhaps that's the relevant question. Assemblers might support many features, climbing the continuum to compilers, making answering difficult.
Pablo H
CC BY-SA 4.0
2023-10-26T23:46:28.630Z
It should be noted that the idea that the Piraha language does not support recursion is controversial. There has been a *tiny* amount of research primarily done by one author, and while it supported Piraha lacking linguistic recursion, it also suffered from serious methodological flaws and has been widely critiqued.
apropos
<p>There's no standardized assembly language for most popular CPU architectures. X86 has masm, nasm and gas for starters, each with its own mutually incompatible directives and macro system.</p>
<p>In nasm you can write, e.g.</p>
<pre><code>%macro  foo 2
    %1
    %2
%endmacro

%macro  bar 2
    %1
    %2
%endmacro

    foo { bar push eax, push ebx }, { bar push ecx, push edx }
</code></pre>
<p>and that extends in principle to an arbitrary nesting depth, so nasm assembly isn't a regular language even if you ignore arithmetic expressions. But that's just nasm; nasm doesn't define x86 assembly language. By the same token, the fact that you wrote a PicoBlaze assembler that doesn't support embedded clauses doesn't mean that PicoBlaze assembly language inherently lacks embedded clauses.</p>

CC BY-SA 4.0
2023-10-19T21:10:28.487Z
2023-10-19T21:10:28.487Z
benrg
<p>It's not immediately clear how we should even define linguistic recursion as a property of a formal language.</p>
<p>We can certainly define it as a property of a grammar. For example, supposing <code>Instruction</code> is some non-recursive term such as a traditional assembly language instruction, then this grammar is plainly recursive since <code>program</code> appears in its own derivation:</p>
<pre><code>program ::= ε
         |  Instruction program
</code></pre>
<p>And this grammar plainly isn't recursive:</p>
<pre><code>program ::= Instruction*
</code></pre>
<p>But these two grammars both define the same language, i.e. any sequence of zero or more instructions. So this language ─ which could be any traditional assembly language, including x86 assembly ─ has grammars which are recursive and grammars which aren't.</p>
<p>On the other hand, there are formal languages such as the <a href="https://en.wikipedia.org/wiki/Balanced_parentheses" rel="noreferrer">language of balanced parentheses</a> for which every grammar must be recursive (i.e. have some term which appears directly or indirectly in its own derivation). So we could say that a formal language exhibits linguistic recursion if every grammar for that language is recursive.</p>
<p>By that definition, x86 assembly is not linguistically recursive, since it has a non-recursive grammar of the form above. Note that for that to be the case, we have to define instructions in a way which allows for <a href="https://stackoverflow.com/q/35379820/12299000">instruction prefixes</a>; but we can do that without recursion:</p>
<pre><code>program ::= instruction*

instruction ::= PrefixInstruction* LeafInstruction
</code></pre>

CC BY-SA 4.0
2023-10-19T18:40:42.533Z
2023-10-19T18:40:42.533Z
kaya3
CC BY-SA 4.0
2023-10-20T18:23:47.047Z
Well said. More formally, linguistic recursion (or any grammatical recurrence) is a property of trees, but assembly languages usually admit a monoid due to an underlying associative property. This is contravariant and thus perhaps unintuitive: a free magma yields trees, but a free monoid yields lists; the extra algebraic law of monoids leads to simpler free structures.
Corbin
# Does x86 assembly support linguistic recursion?
Posted by: username_0 on 2023-10-19
In my book "Jezici za gimnazijalce" (not available online) and in my Bachelor thesis (which will be online in about a month) I was claiming that assembly languages are like the [Piraha language](https://en.wikipedia.org/wiki/Pirah%C3%A3_language) in that both of them don't support linguistic recursion.

However, I can't help but notice that some assembly languages do indeed support linguistic recursion. WebAssembly Text Format is usually considered an assembly language, but it is written in S-expressions. If it's written in S-expressions, it obviously supports linguistic recursion. However, one can easily argue that WebAssembly Text Format is not a real assembly language.

PicoBlaze assembly language doesn't support linguistic recursion, I can be certain of that because I made [an assembler for PicoBlaze](https://picoblaze-simulator.sourceforge.io) for my Bachelor thesis. I added the support for arithmetic expressions in constants and some other things, but that's still not real linguistic recursion because arithmetic expressions in constants don't allow one to embed one directive into another (`load (load s0, s1), s2` is invalid assembly directive, and so is any similar one).

However, I am not sure about x86 assembly. Does it have some directive that expect another directive as an operand? My [Arithmetic Expression Compiler](https://flatassembler.github.io/compiler.html), which outputs x86 assembly, doesn't output any such directive, but that doesn't mean there aren't such directives in x86 assembly.
**Tags:** recursion assembly
> **Comments:**
> **username_1**: By "linguistic recursion," do you mean terms that have non-trivial subterms? That terms can be (non-trivially) nested?  
> **username_2**: There is no one x86 assembly/assembler — there are a dozen different assemblers each with their own syntax and directives.  MASM has macros, though, which might be considered capable of recursion, since one macro can invoke another.  
> **username_1**: I'm asking because I am not familiar with the phrase "linguistic recursion." Looking it up, it seems to be a phrase that describes something in natural language. It's not immediately, completely clear to me how it should apply to programming languages.  
> **username_2**: As far as machine code instructions, x86 family has a wide range of prefix instructions/opcodes that modify the operations/interpretation of next instruction in a variety of ways.  See here, and look for "prefix" https://en.wikipedia.org/wiki/X86_instruction_listings  Further, prefixes can be combined.  
> **username_3**: At the risk of stating the obvious, most assemblers support constant expressions.  
> **username_4**: Does x86 (or any other) machine code support "linguistic recursion"? Perhaps that's the relevant question. Assemblers might support many features, climbing the continuum to compilers, making answering difficult.  
> **username_5**: It should be noted that the idea that the Piraha language does not support recursion is controversial. There has been a *tiny* amount of research primarily done by one author, and while it supported Piraha lacking linguistic recursion, it also suffered from serious methodological flaws and has been widely critiqued.  
---
## 2 answers
### Answer by username_7 on 2023-10-19. Score: 6
It's not immediately clear how we should even define linguistic recursion as a property of a formal language.
We can certainly define it as a property of a grammar. For example, supposing Instruction is some non-recursive term such as a traditional assembly language instruction, then this grammar is plainly recursive since program appears in its own derivation:
program ::= ε
         |  Instruction program

And this grammar plainly isn't recursive:
program ::= Instruction*

But these two grammars both define the same language, i.e. any sequence of zero or more instructions. So this language ─ which could be any traditional assembly language, including x86 assembly ─ has grammars which are recursive and grammars which aren't.
On the other hand, there are formal languages such as the language of balanced parentheses for which every grammar must be recursive (i.e. have some term which appears directly or indirectly in its own derivation). So we could say that a formal language exhibits linguistic recursion if every grammar for that language is recursive.
By that definition, x86 assembly is not linguistically recursive, since it has a non-recursive grammar of the form above. Note that for that to be the case, we have to define instructions in a way which allows for instruction prefixes; but we can do that without recursion:
program ::= instruction*

instruction ::= PrefixInstruction* LeafInstruction
> **Comments:**
> **username_8** (2023-10-20): Well said. More formally, linguistic recursion (or any grammatical recurrence) is a property of trees, but assembly languages usually admit a monoid due to an underlying associative property. This is contravariant and thus perhaps unintuitive: a free magma yields trees, but a free monoid yields lists; the extra algebraic law of monoids leads to simpler free structures.  
---
### Answer by username_6 on 2023-10-19. Score: 3
There's no standardized assembly language for most popular CPU architectures. X86 has masm, nasm and gas for starters, each with its own mutually incompatible directives and macro system.
In nasm you can write, e.g.
%macro  foo 2
    %1
    %2
%endmacro

%macro  bar 2
    %1
    %2
%endmacro

    foo { bar push eax, push ebx }, { bar push ecx, push edx }

and that extends in principle to an arbitrary nesting depth, so nasm assembly isn't a regular language even if you ignore arithmetic expressions. But that's just nasm; nasm doesn't define x86 assembly language. By the same token, the fact that you wrote a PicoBlaze assembler that doesn't support embedded clauses doesn't mean that PicoBlaze assembly language inherently lacks embedded clauses.
---
