Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => TI Z80 => Topic started by: Ashbad on June 20, 2011, 11:52:34 pm
-
TCPS embedded/independent scripting language
NOTE: this is not a full project of mine, but rather a 2-3 day distraction to free my mind from my real projects for a bit so I can think better ;)
It is too late to post a working program, but during my swim meet I had tonight, I decided to make an interpreter for a scripting language that is based on ProceduralBrainF*ck (Pbrain) and Toadskin, which works as a standalone interpreter and an embedded parser for dynamic Axe or Hybrid BASIC scripting. TCPS stands for Turing Complete, Procedural, Stacked scripting language. It works either by accepting arguments from a program in a (char*)array form starting in *L4, or by accepting user input asking for a program to run from at the start of the program run if no valid parameters are given in L4.
Here is an overview on how TCPS works. The scripting language starts at either the specified pointer to program data or user input program names. If in embedded mode, it creates a turing tape of specified length at a given start position, a specified number of stacks of given lengths at given locations, and starts running normally. If in input mode, all of these values are scanned for at the AT header portion of the given program. TCPS supports brainf*ck-like commands with support for math, running internal interlaced compiled assembly code, procedural declarations and runs, and stack operating. The operators:
+ - add operand to cell
- - subtract operand from cell
> - move forward one cell
< - move back one cell
[ - move to ] if current cell is 0
] - if reached with no call trace, goto matching [
( - delimit start of procedure
) - end procedure delimiting
/ - call procedure by name of following letter (if no letter follow //)
// - call procedure of index determined by value of current cell
^ - pop from current stack to current cell
* - push from current cell to current stack
= - set current stack to index determined by following letter (if none, follow ==)
== - set current stack to index determined by current cell value
{ } - delimits interlaced assembly code (compiled to .bin format), can be at most 256 bytes large per block and must end with a RETI instruction
" " - delimits inline ASCII data in the current cell
' ' - delimits inline numerical hex data inserted in the current cell
! - end script execution and prompt interpreter to clean up mess
? - if current cell is zero, end script execution and prompt interpreter to clean up mess
. - display value of current cell in ASCII
, - display value of current cell as a numerical value
Pi OP Pi - Pi symbol delimits math operand (Axe's +,-,*,/,^) taking current cell and the next cell, doing the operation, and storing to current cell
Example program (hello world), in .8xp format and started in execution by user input (non-embedded) mode:
AT
1000,L1
1,64,L2
/AT
>"Hello World!"<
+++++++++++
[>.<-]!
Another example of me making a procedure that will push all of the ASCII data onto the stack, and pick out every other letter and print it. It even includes error handling! :) :
AT
1000,L1
2,64,L2
/AT
>"gboaodd ddaayy"<
(P >*.< -) =A
(D ++++++++)
:D ^
=B [>^> =A* - =B]
:D [:P] ?
"Err: WTF?" :D
[.>] !
(prints "good day"' or "Err: WTF?" if somehow the cells wouldn't initiate correctly (memory error))
As you can see, it is glorified BF, but it can do a lot for a fast processing speed. Programs are highly polymorphic and interlaced assembly can even change program contents during execution; you have decent math capabilities; you have powerful stacks and procedure workings; hard things like error handling are simple is TCPS; it can be used from Axe code easily (you can even compile the source into part of the program, for easy access) or do it externally with hybrid BASIC (support for straight up BASIC on the way); and loads more.
Interpreter, source, example programs and program loader data, and screenies will most likely come tomorrow ;) until then, have fun processing this wall of smarts in your head! Questions, Comments, Questions, Comments, or even Questions are welcome below!
Happy scripting,
Ashbad
-
Didn't you have Vixen/Emerald and another language, though? ???
This seems a bit interesting, though. I hope this doesn't distract you from other projects too much, though. <_<
-
Yeah, I actually worked on verdant today :D but this is like the only thing I could have possibly done with my calc and no computer during the swim meet, so this happened :). It wont distract me at all, I'm already 80% done with it.
-
Oh wait it was Verdant. Also wow I totally wasn't realize this new language was coded on calc lol
-
Let us assume that each instruction can be mapped to a finite set of integers from 0 to some number X. Let the number of possible states of the interpreter be similarly mapped some potentially infinite set of integers from 0 to m. Before continuing further, it must also be mentioned that any Turing complete language can store an infinite amount of data. Since TCPS has finite memory (due to the underlying hardware constraints), it is not truly Turing complete. However, it is common to ignore such constraints and assume that the language has access to an infinite amount of memory if it chooses to utilize it. I will assume that here as well. Also, the simplest way to prove TCPS Turing complete is just to recognize that since brainf*ck is Turing complete and Assembly can implement a brainf*ck interpreter while TCPS allows inline Assembly, TCPS is Turing complete by extension. However, the command list given does not have a command for arbitrary input [like brainf*ck's ',' command]*, TCPS cannot perfectly emulate brainf*ck. While this is really quite a significant oversight, excluding emulation of this command does not necessarily make TCPS Turing-incomplete (as a cursory examination of the properties of Rule 110 will demonstrate).
Now, in order for a language to be Turing-Complete, it must be able to emulate any possible Turing machine. In other words, there must be a 1-to-1 mapping of TCPS programs to Turing Machines. The data requirements of a Turing machine are 1) A Turing tape, which is essentially an infinitely large array of numbers, B) A number representing the memory location on the tape currently being accessed by the head, and C) a number representing the state of the machine. Let the memory space accessibly by the interpreter suffice as a representation of the tape. Let the memory location (PC) currently accessed by stored in some place either on the tape or internal to the interpreter while the state of the interpreter consists of the values of all other data contained within the program.
From the above requirements for Turing-completeness, it can be seen that any system which implements the following program is thus Turing-Complete:
Label: Beginning
If {PC}=0 Then
Change State to Q₀
Change {PC} to R₀
Change PC to PC₀ '
Goto Beginning
End
If {PC}=1 Then
Change State to Q₁
Change {PC} to R₁
Change PC to PC₁'
Goto Beginning
End
…
If {PC}=[i]x[/i] Then
Change State to Qₓ
Change {PC} to Rₓ
Change PC to PCₓ '
Goto Beginning
End
If (State Or {PC}) = (Halting_Condition) Then
Halt
End
While one could conceivably generating many other Turing-Complete programs, this is I think the most intuitive one. Since all Turing-Complete systems are Turing-Equivalent, any Turing-Complete system can implement that program and every non-Turing-Complete systems are missing one of the abilities. Therefore, a system is Turing-Complete if and only if the program can be implemented.
Label <string>:
Labels are primarily a human construct and need not actually appear in the tape. Assume Labels to refer to particular memory locations in a manner similar to pointers.
If {PC}=x Then:
This routine can be accomplished in much the same manner as in brainf*ck. Subtract 1 from{PC} x times and then use the '[' and ']' looping commands to test the conditional.
Change State to Qₓ :
Again, this can be accomplished in much the same way as brainf*ck. Use the '+' and '-' operators to change the value of {PC} and the '<' and '>' operators respectively to
access other memory locations (see the part on Goto for a description of the difficulties associated with this).
Change {PC} to Rₓ:
'+' or '-' will suffice.
Change PC to PCₓ ':
Precisely the same idea as “Change State to Qₓ “
Goto <Label>
Okay, I'll be honest; TCPS can't actually do an arbitrary Goto <Label>. Neither can Brainf*ck. To actually do so in either language is equivalent to solving the Halting Problem, which has been proven to be generally undecidable. This does not mean that TCPS isn't Turing-Complete though, as the provided example program can be rewritten such that the conditionals are located at one point on the tape and Goto <Label> is equivalent to a finite (and known!) number of '<' or '>' operators. I'll leave implementing as an exercise, as the general case is one of those things that makes babies cry and milk go sour.
End:
This is another primarily human construct that need not necessarily exist on the tape. It's essentially just the ']' command.
Halt:
This is the '!' command.
Since the program can indeed be implemented, TCPS is therefore Turing-Complete and this informal proof is thus concluded.
*The ability to input filenames, while technically "arbitrary input," just doesn't seem like a reasonable substitute since you'd basically have to write programs for each case of a computable problem. You could theoretically use this in a BF interpreter written in TCPS, but come on. Getkey is so simple that even BF has it >_>
PS: If you'd like my opinion, I don't think TCPS is really in the spirit of Brainf*ck, which was designed to be a Turing-Tarpit. Adding extra commands is kind of like putting more legs on a Kangaroo IMHO. It might make it easier for the Kangaroo to jump, but it's now it's a mutant Kangaroo. But it's your project, so good luck finishing it :)
EDIT: Sorry for the weird spacing. I typed this up in a word processor and the forum doesn't use the same typesetting.
-
- you don't need all of brainfuck's commands to be turing complete. All you need is:
- >
- +
- [
- ] (even this is optional depending on rules)
- BF doesn't have get key ??? Having a built in get key with this would be stupid. It could be done interlaced with assembly, and I think its already bad that it supports output to screen as characters.
- the reason it's so simple is due to limited speed and size of the z80, which interpretation of this bodes well for since it is extremely minimal and can be easily extended
Half of above doesn't even relate to this directly at all :P I know what turing completednesss is and that this is a TCL.
-
- BF doesn't have get key ??? Having a built in get key with this would be stupid. It could be done interlaced with assembly, and I think its already bad that it supports output to screen as characters.
...
Half of above doesn't even relate to this directly at all :P I know what turing completednesss is and that this is a TCL.
BF uses the ',' command as a "getkey" of sorts. It takes a byte of input from the user and places it in the cell at the data pointer. TCPS doesn't appear to have anything like that aside from the filename thing, which is... annoying. Also, not having I/O takes away from the ability of the language to replicate programs in "real" languages. Sure, they aren't necessary for Turing completeness, but they make brainf*ck a theoretically useful language by not forcing everything to be hardcoded and perfectly deterministic.
As for how the proof relates to the language, you can't just say "This language is Turing complete" and have it be so. The creator of Malbolge stated that it was Turing complete in his presentation of the language, while the language actually isn't. What I provided was an informal proof (which would serve as a nice outline to a formal proof) of the language's Turing completeness.
-
Wow, you're bored and think: Let's create a new language! LOL
How did you make it on-calc?
-
- BF doesn't have get key ??? Having a built in get key with this would be stupid. It could be done interlaced with assembly, and I think its already bad that it supports output to screen as characters.
...
Half of above doesn't even relate to this directly at all :P I know what turing completednesss is and that this is a TCL.
BF uses the ',' command as a "getkey" of sorts. It takes a byte of input from the user and places it in the cell at the data pointer. TCPS doesn't appear to have anything like that aside from the filename thing, which is... annoying. Also, not having I/O takes away from the ability of the language to replicate programs in "real" languages. Sure, they aren't necessary for Turing completeness, but they make brainf*ck a theoretically useful language by not forcing everything to be hardcoded and perfectly deterministic.
As for how the proof relates to the language, you can't just say "This language is Turing complete" and have it be so. The creator of Malbolge stated that it was Turing complete in his presentation of the language, while the language actually isn't. What I provided was an informal proof (which would serve as a nice outline to a formal proof) of the language's Turing completeness.
Well, I don't know if I even need one -- I can literally sap from common BF's proof and call it a day :P because it includes everything found in BF, plus many more things.
The reason I don't have input and only limited output is because all of that is to be mostly taken care of with inline assembly, and I'm going to make copy-paste libraries that you can copy and paste .bin code from into a interlaced block. I plan on using TCPS as the external scripting language for all of my future Axe games, including UCTI.
-
Hmm you know only Axe and ASM is allowed for the contest right, though? ???
-
Well, I don't know if I even need one -- I can literally sap from common BF's proof and call it a day :P because it includes everything found in BF, plus many more things.
You may also notice that I pointed that out in my proof as the simplest way to demonstrate Turing-Completeness...
-
Hmm you know only Axe and ASM is allowed for the contest right, though? ???
What if someone makes a really awesome 4D puzzle platformer in Brainf? D:
-
But why do I even have to know? I already do. Proofs are stupid, and a waste of time with something I know the answ for.r
-
But why do I even have to know? I already do. Proofs are stupid, and a waste of time with something I know the answ for.r
They show others what you know and make sure your right