Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #60580 > unrolled thread

Re: primitive instruction for programming

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 14:27 -0700
    Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 15:12 -0700
      Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 00:17 +0100
        Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-22 11:07 -0700
    Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 09:04 +0200
      Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-21 03:02 -0500
      Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-21 01:34 -0700
        Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 11:34 +0200
          Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-21 11:48 +0100
            Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 13:10 +0200
        Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 10:53 +0100

#60580 — Re: primitive instruction for programming

Em segunda-feira, 13 de abril de 2015 09:11:05 UTC-3, David Brown  escreveu:
>...
> Function call/return /is/ a control structure.  You can use your G macro
> to eliminate control structures other than call/return, but not to
> eliminate call/return itself.

What about:

...func(a,b,c)...

to

ret = _next
p1= a, p2= b, p3= c
goto _func;
_next: ...

_func: ...use params p1, p2, p3
   .....(of course, each nested call here should use a different ret)
   .....at end of function:
   goto ret;


Emiliano.

[toc] | [next] | [standalone]

#60584

> ret = _next
> p1= a, p2= b, p3= c
> goto _func;
> _next: ...
> 
> _func: ...use params p1, p2, p3
>    .....(of course, each nested call here should use a different ret)
>    .....at end of function:
>    goto ret;
> 
> 
> Emiliano.

Complementing, that'll be a powerful NewBasic. And ultra-simple, too,
thus EVERYONE shall be able to program then.

Emiliano.

[toc] | [prev] | [next] | [standalone]

#60590

On 20/04/2015 23:12, Emiliano Gomes Padilha wrote:
>
>> ret = _next
>> p1= a, p2= b, p3= c
>> goto _func;
>> _next: ...
>>
>> _func: ...use params p1, p2, p3
>>     .....(of course, each nested call here should use a different ret)
>>     .....at end of function:
>>     goto ret;
>>
>>
>> Emiliano.
>
> Complementing, that'll be a powerful NewBasic. And ultra-simple, too,
> thus EVERYONE shall be able to program then.

Your example won't work in standard C (as you can't take addresses of 
labels). Also you've omitted the considerable work needed to implement 
recursive calls and to handle results. (And all formal parameter names 
would either all need to exist simultaneously in the same name-space, or 
even more work is needed to call a function.)

This might work for auto-generated code which no-one has to look at *if* 
there is no proper way of implement function calls, but not for normal 
programming. Certainly not 'everyone'.

I don't see how 'ultra-simple' can be applied to it considering how much 
effort is needed to implement x=f(a,b,c) instead of just writing 
x=f(a,b,c). Ultra-primitive perhaps...

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#60768

Em segunda-feira, 20 de abril de 2015 20:17:50 UTC-3, Bart  escreveu:
> On 20/04/2015 23:12, Emiliano Gomes Padilha wrote:
> >
> >> ret = _next
> >> p1= a, p2= b, p3= c
> >> goto _func;
> >> _next: ...
> >>
> >> _func: ...use params p1, p2, p3
> >>     .....(of course, each nested call here should use a different ret)
> >>     .....at end of function:
> >>     goto ret;
> >>
> >>
> >> Emiliano.
> >
> > Complementing, that'll be a powerful NewBasic. And ultra-simple, too,
> > thus EVERYONE shall be able to program then.
> 
> Your example won't work in standard C (as you can't take addresses of 
> labels). Also you've omitted the considerable work needed to implement 
> recursive calls and to handle results. (And all formal parameter names 
> would either all need to exist simultaneously in the same name-space, or 
> even more work is needed to call a function.)
> 
> This might work for auto-generated code which no-one has to look at *if* 
> there is no proper way of implement function calls, but not for normal 
> programming. Certainly not 'everyone'.
> 
> I don't see how 'ultra-simple' can be applied to it considering how much 
> effort is needed to implement x=f(a,b,c) instead of just writing 
> x=f(a,b,c). Ultra-primitive perhaps...
> 
> -- 
> Bartc


Yeah, for the record, I was just sarcastically going to reductio ad
absurdium; I thought the whole thread was about that...:)

But, granted, I didn't put sufficient signals to that end: I thought
the whole thing about "oh, look how SO MUCH easier and powerful it is!"
would be enough. I presumed someone would eventually point out that THAT
was why goto has become 'forbidden': so that NOT EVERYONE could program...;)


I was aware that recursion would be a problem (any nested call), but
that got me thinking: what about the following (assuming you CAN put
'labels' in variables). Simple tail-recursions like factorial can be
done in a VERY specialized way (transforming it to a loop in fact).
Maybe even Ackermann's could, with LOTS of different variabkles...
(and of course it's a mess! Like machine code):

factorial(0,1): return 1              /* mathematical pseudo-code */
factorial(n): return n * factorail(n-1)


_fac: if (p1<=1) goto ret;
      if (p1 >1) { retv*= p1;  p1-= 1;  goto _fac; }


   p1= 20;   ret= _next;   /* calling factorial(20) */
   retv= 1;  goto _fac;
_next: ...use result in retv



Em segunda-feira, 20 de abril de 2015 20:17:50 UTC-3, asetof...@gmail.com escreveu:

> int s[10000]; 
> int *r=s+9999; *Lim=r, z; 
> 
> #define G(a,b)  if(a)goto b 
> #define push(a) r>=s?*r=a,--r:0 
> #define pop(a)  r<Lim?++r, a=*r:0 
> #define ret     pop(z); G(1,z); 
> #define ca(a,m) z=m; push(z); G(1,a) 
> 
> f(a,b,c) 
> 
> Should traslate to 
> push(c); push(b); push(a); 
> ca(f,label); 
> label: 
> pop(z);pop(z);pop(z);

That's roughly what any high-level language automatically do
for you: it's called subroutine prologue, to prepare and unwind
the stack frame.

Emiliano.

[toc] | [prev] | [next] | [standalone]

#60609

On 20/04/15 23:27, Emiliano Gomes Padilha wrote:
> Em segunda-feira, 13 de abril de 2015 09:11:05 UTC-3, David Brown  escreveu:
>> ...
>> Function call/return /is/ a control structure.  You can use your G macro
>> to eliminate control structures other than call/return, but not to
>> eliminate call/return itself.
> 
> What about:
> 
> ...func(a,b,c)...
> 
> to
> 
> ret = _next
> p1= a, p2= b, p3= c
> goto _func;
> _next: ...
> 
> _func: ...use params p1, p2, p3
>    .....(of course, each nested call here should use a different ret)
>    .....at end of function:
>    goto ret;
> 
> 

You can certainly make something like.  The details might be fuzzy here,
especially for dealing with multiple function calls and recursive calls
- you need to make a stack of some sort for recursive calls.  Eventually
it boils down to implementing roughly the assembly code generated by the
C compiler, but writing it in sort-of C.

The point, however, is that it can't be done by the "G" macro - it needs
some way to keep track of function local data and return stack data.


You might be curious to learn that the earliest subroutines were
implemented without any sort of stack at all.  They didn't support
recursion, however, but it was an elegant solution.  In a mix of
pseudo-C and pseudo-assembler, they were done like this:

main:
	...
	// call function foo
	*((void*) foo) = next1
	goto foo+1	// i.e., foocode
next1:
	// continue main

foo:
	.data 0		// Storage for return address
foocode:
	// Actual foo code
	...
	goto *foo

[toc] | [prev] | [next] | [standalone]

#60613

On Tue, 21 Apr 2015 09:04:49 +0200, David Brown
<david.brown@hesbynett.no> wrote:

>On 20/04/15 23:27, Emiliano Gomes Padilha wrote:
>> Em segunda-feira, 13 de abril de 2015 09:11:05 UTC-3, David Brown  escreveu:
>>> ...
>>> Function call/return /is/ a control structure.  You can use your G macro
>>> to eliminate control structures other than call/return, but not to
>>> eliminate call/return itself.
>> 
>> What about:
>> 
>> ...func(a,b,c)...
>> 
>> to
>> 
>> ret = _next
>> p1= a, p2= b, p3= c
>> goto _func;
>> _next: ...
>> 
>> _func: ...use params p1, p2, p3
>>    .....(of course, each nested call here should use a different ret)
>>    .....at end of function:
>>    goto ret;
>> 
>> 
>
>You can certainly make something like.  The details might be fuzzy here,
>especially for dealing with multiple function calls and recursive calls
>- you need to make a stack of some sort for recursive calls.  Eventually
>it boils down to implementing roughly the assembly code generated by the
>C compiler, but writing it in sort-of C.
>
>The point, however, is that it can't be done by the "G" macro - it needs
>some way to keep track of function local data and return stack data.
>
>
>You might be curious to learn that the earliest subroutines were
>implemented without any sort of stack at all.  They didn't support
>recursion, however, but it was an elegant solution.  In a mix of
>pseudo-C and pseudo-assembler, they were done like this:
>
>main:
>	...
>	// call function foo
>	*((void*) foo) = next1
>	goto foo+1	// i.e., foocode
>next1:
>	// continue main
>
>foo:
>	.data 0		// Storage for return address
>foocode:
>	// Actual foo code
>	...
>	goto *foo
>
>

While that particular approach was fairly popular (CDC 6600, PDP-8, to
pick a couple of particularly famous examples), several other schemes
were used as well.  There were real stacks as well (originally
envisioned by Turing for ACE, but not actually implemented), although
they weren't that common at first.

AFAIK, the first computer with what we'd recognize as modern
subroutines was EDSAC, on which the (somewhat simplified) linkage
convention loaded the current address plus a jump opcode into the
accumulator, branched to the subroutine, which added two or three
(memory fails me) to the accumulator, and then stored it in the
location of the return.  So when the subroutine ended, the now updated
"return" instruction would branch back to the caller.  Obviously this
is somewhat similar to the first scheme in that the return address is
stored in the body of the subroutine, although the subroutine would
end with a simple branch, rather than an indirect one.  Univac I used
a similar scheme in which the "return instruction" was modified,
although there was more hardware support.

Other systems used fixed memory locations to hold return addresses,
but those locations were not in the bodies of the subroutines
themselves.

Obviously this was dependent on both the hardware and the software
convention.  A system like the 704 used a somewhat RISC-like scheme
where the return address would be saved in a (fixed) (index) register,
and the subroutine would be required to save that if it in turn called
another subroutine.  Obviously any scheme would do, but on the 704 it
was back to using a fixed location most of the time, although a real
stack was implemented on occasion as well.  (To confuse things
further, that index register was used to access the parameters as
well, which would be stored after the call instruction).

[toc] | [prev] | [next] | [standalone]

#60614

int s[10000];
int *r=s+9999; *Lim=r, z;

#define G(a,b)  if(a)goto b
#define push(a) r>=s?*r=a,--r:0
#define pop(a)  r<Lim?++r, a=*r:0
#define ret     pop(z); G(1,z);
#define ca(a,m) z=m; push(z); G(1,a)

f(a,b,c)

Should traslate to
push(c); push(b); push(a);
ca(f,label);
label:
pop(z);pop(z);pop(z);

[toc] | [prev] | [next] | [standalone]

#60619

On 21/04/15 10:34, asetofsymbols@gmail.com wrote:
> int s[10000];
> int *r=s+9999; *Lim=r, z;
> 
> #define G(a,b)  if(a)goto b
> #define push(a) r>=s?*r=a,--r:0
> #define pop(a)  r<Lim?++r, a=*r:0
> #define ret     pop(z); G(1,z);
> #define ca(a,m) z=m; push(z); G(1,a)
> 
> f(a,b,c)
> 
> Should traslate to
> push(c); push(b); push(a);
> ca(f,label);
> label:
> pop(z);pop(z);pop(z);
> 

You have /completely/ missed the point.

The original claim was that G /alone/ could replace any control
structure in C.  It can't - it is unable to replace the call/return
mechanism needed for recursion, which is /required/ for some types of
functions (like the Ackerman function given).  You can add extra data,
such as a stack, and use that along with G to implement recursion - but
you cannot do it with just G.

[toc] | [prev] | [next] | [standalone]

#60628

David Brown <david.brown@hesbynett.no> writes:

> On 21/04/15 10:34, asetofsymbols@gmail.com wrote:
>> int s[10000];
>> int *r=s+9999; *Lim=r, z;
>> 
>> #define G(a,b)  if(a)goto b
>> #define push(a) r>=s?*r=a,--r:0
>> #define pop(a)  r<Lim?++r, a=*r:0
>> #define ret     pop(z); G(1,z);
>> #define ca(a,m) z=m; push(z); G(1,a)
>> 
>> f(a,b,c)
>> 
>> Should traslate to
>> push(c); push(b); push(a);
>> ca(f,label);
>> label:
>> pop(z);pop(z);pop(z);
>> 
>
> You have /completely/ missed the point.
>
> The original claim was that G /alone/ could replace any control
> structure in C.  It can't - it is unable to replace the call/return
> mechanism needed for recursion, which is /required/ for some types of
> functions (like the Ackerman function given).  You can add extra data,
> such as a stack, and use that along with G to implement recursion - but
> you cannot do it with just G.

That's not how this problem is usually set up; adding data is not
usually considered a problem -- after all, much of the data is there in
the recursive function version anyway.  The rules of the "what makes a
minimal computational system" usually permit any finite amount of extra
data that might be required (though in some more restrictive cases one
might object to quantities that grow exponentially with the problem
size).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#60631

On 21/04/15 12:48, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 21/04/15 10:34, asetofsymbols@gmail.com wrote:
>>> int s[10000];
>>> int *r=s+9999; *Lim=r, z;
>>>
>>> #define G(a,b)  if(a)goto b
>>> #define push(a) r>=s?*r=a,--r:0
>>> #define pop(a)  r<Lim?++r, a=*r:0
>>> #define ret     pop(z); G(1,z);
>>> #define ca(a,m) z=m; push(z); G(1,a)
>>>
>>> f(a,b,c)
>>>
>>> Should traslate to
>>> push(c); push(b); push(a);
>>> ca(f,label);
>>> label:
>>> pop(z);pop(z);pop(z);
>>>
>>
>> You have /completely/ missed the point.
>>
>> The original claim was that G /alone/ could replace any control
>> structure in C.  It can't - it is unable to replace the call/return
>> mechanism needed for recursion, which is /required/ for some types of
>> functions (like the Ackerman function given).  You can add extra data,
>> such as a stack, and use that along with G to implement recursion - but
>> you cannot do it with just G.
> 
> That's not how this problem is usually set up; adding data is not
> usually considered a problem -- after all, much of the data is there in
> the recursive function version anyway.  The rules of the "what makes a
> minimal computational system" usually permit any finite amount of extra
> data that might be required (though in some more restrictive cases one
> might object to quantities that grow exponentially with the problem
> size).
> 

That's fair enough, when that's the rules.  But I understood the
original claim to be that G is entirely sufficient to replace all the
control structures in C - which it cannot do.  When you are free to add
data, then of course you can do much more, as these examples show.

[toc] | [prev] | [next] | [standalone]

#60622

On 21/04/2015 09:34, asetofsymbols@gmail.com wrote:
> int s[10000];
> int *r=s+9999; *Lim=r, z;
>
> #define G(a,b)  if(a)goto b
> #define push(a) r>=s?*r=a,--r:0
> #define pop(a)  r<Lim?++r, a=*r:0
> #define ret     pop(z); G(1,z);
> #define ca(a,m) z=m; push(z); G(1,a)
>
> f(a,b,c)
>
> Should traslate to
> push(c); push(b); push(a);
> ca(f,label);
> label:
> pop(z);pop(z);pop(z);
>

I've tried to run this but there are far too many compilation errors and 
I've given up.

Please post a working version, and include the body of the function 'f' 
(which just prints out its parameters or something).

Note that manipulating pointers to labels, that will only work with gcc 
or Clang.

-- 
Bartc

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web