It is currently Tue Oct 17, 2017 2:47 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 39 posts ]  Go to page Previous  1, 2, 3
Author Message
PostPosted: Sun Mar 19, 2017 8:27 pm 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 284
tepples wrote:
Could you show an example of C-style C and the corresponding Forth-style C?

I don't actually write much C-style C, but here's some Forth-style C (or at least what I call Forth-style C):
Code:
int f = 0;

for(size_t i = 0; i < instructions; i++)
{
   int op  = in[i].op;
   int var = in[i].var;

   if(op == FUNCTION)
   {
      f = var;
   }
   else if(op == JSR)
   {
      int t = function[var].stack + function[var].locals;

      if(t > function[f].stack)
      {
         function[f].stack = t;
      }
   }
}

This routine allocates local variables to zero page based on a call graph, as part of a 6502-targeted compiler (the one used to build Wrecking Balls, in fact; this is from an actual working program). in[] is the program, in tokenized assembler format, one instruction/directive per entry. FUNCTION is a directive inserted by the frontend at the start of each function, with a parameter indicating the function index. function[].locals is the input, the number of bytes of stack space each function needs. function[].stack is the output, the address of the first byte of each function's stack frame, which is initialized to zero.

My language forbids forward references in order to prevent accidental recursion (which is impossible with static allocation); to allow those, simply repeat the above routine until function[f].stack = t; stops being executed. (Note that it will never stop executing in the case of recursion.)

I call this code "Forth-style" because it solves a hard problem (building a call graph and allocating stack frames such that their addresses ranges overlap only if they are never active at the same time) with a trivial algorithm (iterating over an assembly listing). It uses zero space (other than space already allocated and used outside the routine), executes in time linear in the size of the program (assuming no forward references, trivially true for my application), and produces an optimal result (RAM usage of any branch of the call graph is exactly equal to the sum of the stack usage of all functions along that branch), in 21 lines of code (including 3 blanks and 8 braces).

The equivalent "C-style" code would build the call graph as an explicit data structure, then apply some form of graph-colouring algorithm to perform the allocation, and would probably total several thousand lines of code. I know that sounds like I'm deliberately bashing on C programmers, but that's only because I picked something I happen know a simple solution to, for maximum contrast.

EDIT

rainwarrior wrote:
I thought "stack juggling" was an assembly language concern, not a C concern?

Stack juggling is the #1 most common complaint about Forth (not C) due to its rigidly RPN syntax. I'm refering to "pure" Forth, without named local variables, which were added for ease of use by non-Forth programmers, and result in "C-style Forth" code. (I had a link to a perfect example of what I mean by "C-style Forth", but the page seems to have vanished.)


Top
 Profile  
 
PostPosted: Sun Mar 19, 2017 8:40 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5709
Location: Canada
Rahsennor wrote:
The equivalent "C-style" code would build the call graph as an explicit data structure, then apply some form of graph-colouring algorithm to perform the allocation, and would probably total several thousand lines of code. I know that sounds like I'm deliberately bashing on C programmers, but that's only because I picked something I happen know a simple solution to, for maximum contrast.

I'm having difficulty understanding what "C-style" means here, because you didn't provide an example. How would you implement this "C-style" instead and why would it take several thousands of lines of code?


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 12:13 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7224
Location: Chexbres, VD, Switzerland
Quote:
fnctions in C are basically backwards-RPN with some (,)

"Backwards RPN" means simply PN - the original polish notation which uses operation symbol before the operators.

Quote:
There are as many dialects of Forth as there are Forth programmers. Writing your own compiler is pretty much a rite of passage, and the language's entire shtick is domain-specific customization. Portability is unheard of.

Honnestly this makes FORTH sound as a terrible language, perhaps even worse than assembly.


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 3:13 am 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 284
rainwarrior wrote:
I'm having difficulty understanding what "C-style" means here, because you didn't provide an example. How would you implement this "C-style" instead and why would it take several thousands of lines of code?

The "C-style" version of my example would, as I said, build an explicit call graph and run an allocation algorithm on it. I would take thousands of lines to do that, and probably spend months getting it to work. I imagine you could do better.

It was a poor example and I regret posting it. Forget I said anything.

How about this:

"Forth-style" code does the minimum possible work to get the job done and breaks up functionality into small, re-usable pieces.

"C-style" code solves problems in a methodical fashion and has a tendency toward monolithic, generalized solutions.

The former 'wastes' programmer time on minimizing the codebase, under the expectation that doing so will reduce future work. The latter trades larger code and more duplication for less time spent rewriting.


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 10:08 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5709
Location: Canada
Rahsennor wrote:
rainwarrior wrote:
why would it take several thousands of lines of code?

The "C-style" version of my example would, as I said, build an explicit call graph and run an allocation algorithm on it. I would take thousands of lines to do that, and probably spend months getting it to work. I imagine you could do better.

I don't know what "building an explicit call graph" looks like in this context, nor do I know what "an allocation algorithm" would be in this case. You wrote a simple piece of C code that looks fine (?) and doesn't really look like it's not "C-style", so I don't have a clue how that might translate into your idea of what "C-style" means, and I really can't even fathom what a thousand-lines version of this is supposed to be.

Rahsennor wrote:
"Forth-style" code does the minimum possible work to get the job done and breaks up functionality into small, re-usable pieces.

"C-style" code solves problems in a methodical fashion and has a tendency toward monolithic, generalized solutions.

I've seen many C coding guidelines that recommend breaking tasks into small functions and re-using them as much as is practical. The idea of "small, re-usable pieces" is kind of just a programming platitude, though; I don't think it has much to do with the language at all. I don't know what your experience with C is, but there's small specialized code and there is monolithic libraries too, but I really don't get why you think that "C-style" has to mean some gargantuan overwrought library. ?

What do you think of, say, DOOM's C source code? Does this look like "C-style" to you?

Your statements almost seem like a distortion of the definition of a "functional" programming language vs an "imperative", though I've been looking at Forth again since you mentioned it, and I don't think Forth fits the definition of "functional programming" either, though these things don't actually have to be a language feature-- they can apply to tendencies of style too. More pure functional languages tend to impose that you work certain ways, e.g. in Haskell it tends to be very impractical to debug large complicated functions, so if you don't break things into small pieces your program will probably just die. So... language design can often strongly guide you to write in a certain way.

I don't understand from your description how this relates to Forth and C, though.

Bregalad wrote:
Rahsennor wrote:
There are as many dialects of Forth as there are Forth programmers. Writing your own compiler is pretty much a rite of passage, and the language's entire shtick is domain-specific customization. Portability is unheard of.

Honnestly this makes FORTH sound as a terrible language, perhaps even worse than assembly.

From what I can tell, Forth's strongest point is that it's exceedingly simple and easy to write an interpreter/compiler for. I don't really see how this aids the task of programming itself, but it does seem to make it very portable/implementable and customizable, which is a practical advantage in some situations.

It seems specifically designed to produce small binary bytecode, by having very little language features. I can see how it could produce smaller binaries than native assembly or C (and the interpreter implementation itself would be small too), but none of this seems to be an aid to the programmer. Coding Forth you have to "think" in RPN because the language does every operation it can through the stack. You get smaller code the more things you can cascade through the stack. (I did mention earlier, though, that I think translating ideas into RPN is a burden that has been shifted to the programmer here that can easily be done by a compiler.)

I'm reminded a little of SWEET16 where Woz wrote a bytecode interpreter for doing 16-bit stuff on the 6502 but with small code.

It's pretty common to write small bytecode interpreters in C or assembly, though, enabling you to use both a compact bytecode and efficient native code in tandem. "Small" code isn't the exclusive domain of Forth; Forth is just a language that seems to get a lot of functionality out of relatively few moving parts.


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 2:09 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7224
Location: Chexbres, VD, Switzerland
Quote:
I've seen many C coding guidelines that recommend breaking tasks into small functions and re-using them as much as is practical. The idea of "small, re-usable pieces" is kind of just a programming platitude, though; I don't think it has much to do with the language at all.

I was going to say the same, but you worded it better than I'd have done. Good and bad programming can be done with any language - so you just seem to implicitly say "good programming style = FORTH style", "bad programming style = C style" but I'm pretty sure it's not related to either of those languages.

Quote:
I'm reminded a little of SWEET16 where Woz wrote a bytecode interpreter for doing 16-bit stuff on the 6502 but with small code.

To be honnest the original SWEET16 is very lacking. I wrote my own "SWEET16" which is largeley supperior to Steeve Wożniak's, it supports operations such as AND, OR and do not need status flags. It also supports much sweeter intermerging with native asm 6502. It is also somewhat easier to code for it rather than 6502 assembly, at least for some tasks, for others it's worse but then why bother.


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 6:19 pm 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 284
Bregalad wrote:
so you just seem to implicitly say "good programming style = FORTH style", "bad programming style = C style"

If you'd bothered to actually read my posts, you'd have seen me repeatedly say that the things I'm talking about are not unique to Forth, or even hard in other languages, and that the entire point of me suggesting people learn Forth is to promote this kind of coding in other languages.

I also repeatedly said that I learned this kind of programming from Forth, but as this discussion proves, I am a complete retard and incapable of learning anything that isn't shoved down my throat. People like you and rainwarrior, who have an IQ above 50, clearly don't need to learn Forth to acquire what is apparently common sense for the rest of the world, so I have wasted the time of all parties involved. I apologise for opening my big mouth.

I don't know why I bother talking to people - in fact, I'm pretty sure expecting any degree of success in doing so meets the definition of insanity. Autism sucks.


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 8:42 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5709
Location: Canada
Hey, I'm sorry to have upset you. I was genuinely confused by what you were trying to express with the term "c-style". Clearly you don't want to defend that term, and that's fine. That's unimportant to me. What I really wanted to know what the kind of bad code that Forth helped you with looked like.

I've been looking at Forth since you mentioned it, and have been considering what kind of project I might try it out on in the future. I ran across this interesting example of a 6502 assembler written in a very succinct Forth program:
6502 forum thread (the author's comments about it are a little bit hilarious, though)

As a contrasting parallel of someone going out of their way to write very compactly in C++, here's Bisquit's NES emulator written in about 1000 lines of C++11:
video part 1 / video part 2 (the opcode matrix / instruction emulation is particularly bizarre and interesting)

I'm not personally of the belief that short code is necessarily better, but it often better to have less code rather than more. I also don't think code has to be "pretty"; I'm tolerant of ugly conventions and styles as long as I think I can read them well and maintain them, and of course I hope most of all that the code really solves the problem I have, and not some simplified problem that would make the code more elegant instead (which I find is a common temptation).

That's why I linked the DOOM source code above, too. I think it's a good example example of well written, practical C code in a large real-world project:
DOOM on github


Top
 Profile  
 
PostPosted: Mon Mar 20, 2017 9:55 pm 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 197
When I think of "FORTH-style" C code, I think of code with very linear data flow and data structures that are flat.

For example, here's how the main loop of a video game written "FORTH-style" would look:
Code:
while(true)
{
    apply_gravity(&actors);
    move_actors(&actors);
    check_collisions(&actors);
    handle_collision_events(&actors);
    prepare_render(&actors, &render_data);
    render(&render_data);
}

Each step would be as self-contained as possible and would pass everything down (including events, messages, etc) as data. The call stack would remain little as possible; function calls are not deeply nested.

Compare this to a more "object oriented" design written in C++:
Code:
int main()
{
    for(int i = 0; i < num_actors; ++i)
    {
        actors[i].step();
    }
}

// And the "class" member functions:
void actor::step()
{
    this->move();
    this->render();
}

void actor::move()
{
    this->apply_gravity();
    while(actor* a = this->find_collision(&actors))
    {
        this->collided_with(a);
        a->collided_with(this);
    }
}

The call graph here is a longer and tree-like, and will continue to get worse as the program grows in complexity. This makes it harder to follow the data flow and refactor.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 39 posts ]  Go to page Previous  1, 2, 3

All times are UTC - 7 hours


Who is online

Users browsing this forum: Bing [Bot], Google [Bot], Pokun and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group