5
$\begingroup$

I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.

There is only one data type in it (integer, since that's the only data type brainfuck supports). It supports functions and subroutines (to which you can pass integers by value, but not arrays, though you can access an array in the global scope from within a function/subroutine) but it does not support recursion (all function and subroutine calls are inlined). It supports statically allocated arrays (size known at compile time) and has just one unbounded stack. You can store as many items as you like in the stack, unlike with arrays, but you only have one stack for your entire program.

I have these limitations to achieve a balance between ease of use, and fast generated code.

However, I never studied any of this stuff and I actually started this project to learn about compilers (by making one), therefore my question is:

From the above description, is this language turing complete?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Are you describing your language or brainfuck? And, why? $\endgroup$ – Dave Clarke Apr 18 '13 at 13:25
  • $\begingroup$ I am describing my language. Brainfuck is a very simple language with only 8 commands operating on a "tape" of cells. Shouldn't take more than 2 minutes to learn the entirety of the language off of wikipedia. I would like to know whether the language I am creating is turing complete with that weird set of available tools. $\endgroup$ – Cedric Mamo Apr 18 '13 at 13:30
4
$\begingroup$

If your language supports an arbitrarily large array of integers (even of numbers in $\{0,1\}$), then you can simulate the tape of a TM. Then, clearly your language is Turing complete.

EDIT: based on your comment, you don't have an arbitrary array.

In this case, you can do the following: If you can keep two counters (integers), and increase or decrease them, and check whether they are 0, then you can simulate a two counter machine (Minsky Machine), which is Turing complete (with a caveat).

If you also bound the maximal value that an integer can take, then I believe that your machine is no more powerful than a PDA.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I asked the question simply because of the weird combination of arrays and stack. Array sizes have to be declared at compile time, meaning you can't create an array of arbitrary size at runtime, but you have one stack which is unbounded. $\endgroup$ – Cedric Mamo Apr 18 '13 at 13:28
  • $\begingroup$ Edited the answer. $\endgroup$ – Shaull Apr 18 '13 at 13:54
  • $\begingroup$ Thanks for your answer. The range of the values depends on the interpreter running the code generated by my compiler so it's not really my problem :D. $\endgroup$ – Cedric Mamo Apr 18 '13 at 14:37
  • 1
    $\begingroup$ By the way, if you are really talking about a practical machine, then it is a finite model, and is therefore no more expressive than a DFA. $\endgroup$ – Shaull Apr 18 '13 at 16:02
1
$\begingroup$

If you want to build a compiler, brainfuck is near the worst language to start with... it was designed to be a total mess.

A practical way to understand a compiler is Fraser and Hanson's "A Retargetable C Compiler: Design and Implementation", the book contains the full source code for a simple (but complete) ANSI C compiler. From the link you can get the source code for the (much improved) last version. But note that real compilers are much more complex, LCC has carefully selected schemas for conditionals and loops, does careful instruction selection, and a bit of on-the-fly expression simplification; but little else in terms of "code optimization". If you'd like to mess with a real compiler, take a peek at LLVM, the official compiler for MacOS. It is nicely structured from the ground up, thus much more understandable than the organically grown GCC. Perhaps tcc, the Tiny C Compiler (outgrowth of an International Obfuscated C Code Contest entry for 2002, where they asked for the smallest C compiler able to compile itself) might be of amusement value...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ those compilers output mwchine code at the end, mine outputs bf. doesn't really matter to me as I still learned about the parsing, some optimizations etc. and that was kind of the whole point $\endgroup$ – Cedric Mamo Apr 19 '13 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.