OSDev.org

Posted: **Thu Sep 02, 2004 6:39 pm**

..and before anyone starts about how C gets the job done, I'll add that I am writing this from purely scholarly interest, with my intention to expand the way we thing ok programming. My intention is NOT to explain how C would be bad (as it's not).

It finally hit me. The problem is that Dijkstra and friends "banned" goto. I claim that it's not really goto that was really wrong. Sure, you can get rid of goto with while and if, and make those neater with break/continue, add exceptions and functions and what not to get around the limitation of banning goto, but I claim that goto's not a problem per se, the problem is that goto passes no arguments...

And now, most of us will realize that functions are what pass arguments. Sure. But functions do another things besides that: they accumulate stack. At least C function do that. Scheme functions ofcourse don't do that (if they are written in a tail-recursive manner) but even then, the functionality is there.

Pure goto on the other hand (in the form it's found in BASIC or assemblers JMP) does not touch the stack. But even BASIC has GOSUB, which obviously needs a stack. Why needing stack is bad? Well, if function passing takes stack, you are forced to use stack only within one function. You lose the most basic data-structure found in every system, and need to implement your own heap-allocated stack if you need anything more flexible than the function return stack.

There are two languages that each solve part of this (one elegantly, and one practically). These languages are Scheme and Forth. Scheme requires full tail-recursion. If there's no reason to leave anything from a function call into the stack, then the stack needs to be cleaned, even if the function hasn't logically returned. Futher, any return path can be used as many times as desired, by using one of the weirdest CS concepts ever: continuations.

Forth on the other hand, solves the inter-procedure stack "problem" by using separate stacks for data and return path. But if one understand continuations, one understands that we only need one stack. The return stack is strictly unnecessary. One can always pass "go here with return data" addresses as data instead.

What if goto had parameters? To calculate maximum of two absolute values (that is max(abs(a),abs(b))) with something like:
(convention is to pass the return address as the first argument)

Code: Select all

  goto abs(abs_a_return, a)
abs_a_return(abs_a):
  goto abs(abs_b_return, b)
abs_b_return(abs_b):
  goto max(max_return, abs_a, abs_b)
max_return(bigger):
  goto print(exit, bigger)

Ofcourse, in real life we'd have to specify scoping somehow. But anyway, there's nothing strange about what's done.. just continuation passing style programming.. for example, in Scheme this would look like:

Code: Select all

(lambda (cont a b)
  (cps_abs
    (lambda (aa)
      (cps_abs
        (lambda (ab)
          (cps_max
            (lambda (bigger)
              (print exit bigger))
            aa
            ab))
        b))
    a))

Notice how (either of the code versions) can directly express that we never return from "exit".. there's simply no continuation passed to it..

Obviously, reading (especially the Scheme version of) this kind of code is rather painful. So my question is: does there exist a better way to express this kind of code (which never returns from anywhere, simply calls another functions, even if that function was given to it simply to be called with it's return value).

If one thinks a minute about it, it's not too far from how unix-pipes operate (although there the "functions" run concurrently, also adding lazy evaluation into the mix).
There are "monads" in languages like Haskell, which basicly encapsulate CPS into a nicer syntax (and add some safety) but monads are not exactly easy to understand..

I have nothing agaist normal "structured programming", I'm just trying to find new ways to express things. No-one can deny that one sometimes needs to work around this limitation (exceptions are a good example of possible workarounds developed). I especially that if such a syntax is possible, it might make some tasks of kernel development much easier..

Ofcourse, since I don't know such a syntax (and I've tried various diffent ways to express pure CPS programs) I can't really tell whether it'd make life any easier. But my hopes are high.

Posted: **Thu Sep 02, 2004 7:05 pm**

The best syntax I've been able to come up with, is basicly an extension from an extension to Lisp syntax:
let [args: code] stand for (lambda (args) code)
where either args and code can contain several things.

Then, add a continuation operator >> (kinda like Unix pipe) so one can rewrite the previous example as:

Code: Select all

[a b: (abs a) >>
  [aa: (abs b) >>
    [ab: (max aa ab) >>
      [bigger: (print bigger) >> exit]]]]

Or, omitting extra bracets and switching to more common function calling:

Code: Select all

[a b: abs(a) >>
  aa: abs(b) >>
  ab: max(aa,ab) >>
  bigger: print(bigger) >> exit]

Now the only set of bracets are used for delimiting scope.
Obviously, this is not too different from:

Code: Select all

def somefunction(a, b):
  aa = abs(a)
  ab = abs(b)
  bigger = max(aa, ab)
  print(bigger)
  exit()

We just don't need to care about saving the return address, since we can express that we don't need it.. and we can pass multiple values nice (which Python and other 4G programming languages support anyway).

(Pardon me for not speaking about Haskell, for most people probably can't comprehend it, at least not with the current documentation, which is "bad")

It seems with modern languages we are going down this road, but no language seems to take a path which is both elegant and practical, combining the full power of true CPS with ease of use and code which is possible to read by a mortal.

To exploit our multiple return values, we could obviously have written our little imaginary program as:

Code: Select all

[a b: abs(a, b) >>
  aa ab: max(aa, ab) >>
  bigger: print(bigger) >> exit]

or maybe even:

Code: Select all

[a b: abs(a, b) >> max >> print >> exit]

That is, pass return values of abs are parameters to max and so on, until the end of the list is reached. Or how about defining a function with:

Code: Select all

def absmax(ret, args..):
  abs(args..) >> max >> print >> ret

Not really that bad, is it?

Posted: **Thu Sep 02, 2004 8:23 pm**

Finally, we could also use an "implicit" variable such as $ for the return value (to get even closer to normal syntax):

Code: Select all

def absmax(args..):
  abs(args..) >> max >> print >> $

Now, if we want to catch $ into an "explicit" variable instead,
we can always use:

Code: Select all

def id(var): $(var)

def somefunction():
  id($) >>
  ret: ..some..other..code..

and we can also write Scheme call/cc as:

Code: Select all

def callcc(fun):
  fun($) >> $

Posted: **Sat Sep 04, 2004 7:39 pm**

Are you familiar with SNOBOL at all, Mystran? It is a very peculiar language from the early 1960s that was designed for string processing. Two of the interesting qualities of it are that a) every statement generates a completion value, of either 'success' or 'failure'; and b) any statement can have a multiple-branch clause which could be based on the completion value. Not exactly relevant, but still it might be of some interest as a curiosity if nothing else...

Posted: **Sun Sep 05, 2004 9:36 am**

In fact, I have heard the name SNOBOL, but never bothered to investigate futher.. got the check that..

That said, I'm not completely happy with what I wrote here... I mean.. I had a point I think, but I lost it at some point..

Should pre-write essays and post them only when completed. Well.. life's a learning experience..

OSDev.org

What's wrong with C..

What's wrong with C..

Re:What's wrong with C..

Re:What's wrong with C..

Re:What's wrong with C..

Re:What's wrong with C..