0

I am trying to understand how a computer works from transistors to the C programming language. I know that C can run on most x86 architectures. My question is what is the list of the most basic assembly language commands needed to run C (without making a second language to translate between C and the assembly language). I have tried looking this up on Google, but I haven't found anything.

Example of Command: Add A, B, C (adds the values in register A and B and outputs it to register C).

Help is much appreciated.

MaddNich
  • 27
  • 2
  • C can be compiled to run on ISAs *far* simpler than x86. However, the question is really *very* broad so is probably unsuitable for SO. If an answer requires a ten-part web series to answer it, it's probably not a good fit :-) – paxdiablo Feb 15 '18 at 04:46
  • 1
    This question makes no sense, especially since C can be compiled to just about *any* processor. And actually, it's not uncommon to have an *intermediate* language between C and the final assembler or machine instructions (though to learn about that you need to learn compiler theory and practice). – Some programmer dude Feb 15 '18 at 04:46
  • "(without making a second language to translate between C and the assembly language)" - what does this have to do with anything, why would you need a second language? – user253751 Feb 15 '18 at 04:46
  • 2
    Probably the way to find this out for yourself is to design your own assembly language (for a made-up CPU, it doesn't have to be a real one) and write a C compiler for it. And see which instructions you missed and which ones you didn't need. – user253751 Feb 15 '18 at 04:47
  • And to answer you much to broad question: A C target processor needs to be able to read from memory, write to memory, compare values, and conditional and unconditional jumps. That's about it. The rest is just fluff and "good to have". – Some programmer dude Feb 15 '18 at 04:49
  • Oh and if you're trying to understand computer architecture from transistors up, why not make yourself a CPU? I suggest using logic gates in the Logisim simulator if you don't want to actually build it; Logisim has transistors but don't bother with them as they don't behave accurately. (If you *do* want to build it out of transistors, be prepared to buy a few hundred dollars of transistors and resistors) – user253751 Feb 15 '18 at 04:50
  • 5
    [All you need is “subtract and branch if less than or equal to”.](https://en.wikipedia.org/wiki/One_instruction_set_computer) – Eric Postpischil Feb 15 '18 at 04:52
  • As you may have gathered from the comments, you have asked a question with no single answer. Theories of computation tell us that a universal computer can be built out of almost anything. So, for practical purpose, the question of what instructions we need is purely a matter of practical considerations. We design instruction sets for efficiency, expressiveness, convenience, and other purposes. For theoretical purposes, we need very little to provide the basics. Learning what is needed in practice requires a good deal of learning about computers in general. – Eric Postpischil Feb 15 '18 at 04:58
  • 3
    Since you mentioned x86, I recently [read an article](https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf) that the `mov` instruction (with all its addressing modes) is turing complete.In theory all you need is the x86 `mov` instruction to implement any arbitrary program including running _C_ code. – Michael Petch Feb 15 '18 at 05:04
  • @MichaelPetch: There already is [a working compiler that targets `mov`-only x86](https://github.com/xoreaxeaxeax/movfuscator). See discussion on https://news.ycombinator.com/item?id=9751312 for some funny quotes from the paper that first showed that x86 `mov` is turing-complete thanks to doing calculations with addressing modes. It avoids `jmp` by using faulting `mov` instructions or something, which is kinda cheating (see discussion on https://stackoverflow.com/questions/44795134/is-it-possible-to-perform-some-computations-within-the-ram#comment76602377_44799928) – Peter Cordes Feb 15 '18 at 05:17
  • 1
    The converse of this question: [If a computer can be Turing complete with one instruction what is the purpose of having many instructions?](https://stackoverflow.com/questions/46614200/if-a-computer-can-be-turing-complete-with-one-instruction-what-is-the-purpose-of): TL:DR: performance! – Peter Cordes Feb 15 '18 at 05:20
  • You could make an instruction set where there is just one instruction which does a lot of things depending on arguments. What is the point of the question? – Ajay Brahmakshatriya Feb 15 '18 at 08:37

1 Answers1

9

BitBitJump is turing complete, meaning you could definitely write a C compiler in it. It has only one instruction, so I guess there's an answer for you :) The instruction copies one bit in memory and passes the execution unconditionally to the address specified by one of the operands of the instruction.

Whilom Chime
  • 366
  • 1
  • 9
  • 2
    Note the transport triggered architecture described on that same page is both simple *and* practical to actually build and write a compiler for! – user253751 Feb 15 '18 at 04:53
  • ByteByteJump runs at ~3.93 MIPS, so it's practical. Transport-triggered is a "dirty" hack having nothing to do with computers. I mean, it _does_ compute indeed, but you have to put all those predefined circuits around. It's definitely not minimalistic, neither _canonical_. – Brian Cannard May 16 '21 at 22:51