1
$\begingroup$

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 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 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, which outputs x86 assembly, doesn't output any such directive, but that doesn't mean there aren't such directives in x86 assembly.

$\endgroup$
8
  • 3
    $\begingroup$ By "linguistic recursion," do you mean terms that have non-trivial subterms? That terms can be (non-trivially) nested? $\endgroup$ Commented Oct 19, 2023 at 15:46
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Oct 19, 2023 at 15:46
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Oct 19, 2023 at 15:49
  • 4
    $\begingroup$ 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" en.wikipedia.org/wiki/X86_instruction_listings Further, prefixes can be combined. $\endgroup$ Commented Oct 19, 2023 at 15:50
  • 1
    $\begingroup$ x86 has prefixes, but not arbitrary sequences of prefixes. $\endgroup$ Commented Oct 19, 2023 at 16:03

2 Answers 2

Reset to default
6
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Oct 20, 2023 at 18:23
3
$\begingroup$

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.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.