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

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

MISRA C (was: buckle-up ....)

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

  MISRA C (was: buckle-up ....) Alan Mackenzie <acm@muc.de> - 2026-09-25 10:01 +0000
    Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 14:52 +0200
      Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 13:48 +0000
        Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 16:39 +0200
          Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 15:10 +0000
            Re: MISRA C bart <bc@freeuk.com> - 2026-09-25 16:57 +0100
            Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 11:42 -0700
              Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 20:21 +0000
                Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 14:05 -0700
                  Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-26 08:43 +0200
                    Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-26 17:55 +0000
                    Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-03 23:55 +0100
                      Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-04 16:10 +0200
                        Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 01:22 +0100
                          Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-05 07:59 +0200
                      Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:23 -0700
                      Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:24 -0700
                      Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 09:02 +0000
                        Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-05 12:07 +0200
                        Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 15:29 +0100
                          Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 20:29 +0000
                        Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:13 -0700
                      Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:14 -0700
            Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-09-27 10:52 -0700
            Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 13:08 +0200
              Re: MISRA C bart <bc@freeuk.com> - 2026-09-28 13:07 +0100
              Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-28 14:08 +0200
                Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:28 +0200
              Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-28 12:17 +0000
                Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:40 +0200
            Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 10:21 -0700
              Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-30 19:57 +0000
                Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 13:09 -0700
                  Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-01 08:47 +0200
                    Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-01 15:18 -0700
        Re: MISRA C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-27 04:58 +0800
    Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-25 17:02 +0200
    Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-26 15:37 -0700

Page 1 of 2  [1] 2  Next page →

#402383 — MISRA C (was: buckle-up ....)

[ Followup-To: set ]

In comp.theory Dude <punditster@gmail.com> wrote:

[ .... ]

> You can use restricted programming languages or subsets (such as MISRA 
> C, SPARK, or Rocq) that are not fully Turing-complete.

MISRA C is turing-complete, just as C is.  I don't know about the
others, but it is likely they are turing-complete too.

MISRA C is a subset of C which supposedly reduces error possibilities,
at the expense of bloat.  As far as I'm aware, no studies have been done
which show that MISRA C is in fact better than full C, for any value of
"better".  It is a religion in programming for automotive applications,
no more to be questioned than the Lord's Prayer in a Christian church.

> By banning unbounded loops and wild recursion, you ensure that every 
> valid program in the language is guaranteed to finish

No.  Besides, unbounded loops (such as event loops) are necessary.
Recursion is, too, if you want to program things like tree structures.

-- 
Alan Mackenzie (Nuremberg, Germany).

[toc] | [next] | [standalone]

#402388 — Re: MISRA C

On 2026-09-25 12:01, Alan Mackenzie wrote:
> In comp.theory Dude <punditster@gmail.com> wrote:
> 
>> By banning unbounded loops and wild recursion, you ensure that every
>> valid program in the language is guaranteed to finish
> 
> No.  Besides, unbounded loops (such as event loops) are necessary.
> Recursion is, too, if you want to program things like tree structures.

Note that recursion isn't "necessary" to program [operations on]
tree structures. It just makes the algorithms appear simpler and
clearer, thus recursion is a sensible technique to implement
application cases like those. WRT Dude's statement it should be
mentioned that a recursive algorithm can be transformed to an
iterative one, so if iterative algorithms would have the property
to be _decidable_ to finish - actually, they are not - we could
also say the same for a recursive one.

Janis

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

#402389 — Re: MISRA C

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 2026-09-25 12:01, Alan Mackenzie wrote:
> > In comp.theory Dude <punditster@gmail.com> wrote:

> >> By banning unbounded loops and wild recursion, you ensure that every
> >> valid program in the language is guaranteed to finish

> > No.  Besides, unbounded loops (such as event loops) are necessary.
> > Recursion is, too, if you want to program things like tree structures.

> Note that recursion isn't "necessary" to program [operations on]
> tree structures. It just makes the algorithms appear simpler and
> clearer, thus recursion is a sensible technique to implement
> application cases like those.

Some things you need to do on trees need either explicit recursion, or
"simulated recursion", where static arrays are used to hold intermediate
values of variables.  This approach limits the depth of a tree, possibly
more so than the size of the stack when using explicit recursion.  We
might just be arguing about the meaning of words here.  

> WRT Dude's statement it should be mentioned that a recursive algorithm
> can be transformed to an iterative one, so if iterative algorithms
> would have the property to be _decidable_ to finish - actually, they
> are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice.  In theory,
there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without recursion.

> Janis

-- 
Alan Mackenzie (Nuremberg, Germany).

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

#402390 — Re: MISRA C

On 2026-09-25 15:48, Alan Mackenzie wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>> On 2026-09-25 12:01, Alan Mackenzie wrote:
>>> In comp.theory Dude <punditster@gmail.com> wrote:
> 
>>>> By banning unbounded loops and wild recursion, you ensure that every
>>>> valid program in the language is guaranteed to finish
> 
>>> No.  Besides, unbounded loops (such as event loops) are necessary.
>>> Recursion is, too, if you want to program things like tree structures.
> 
>> Note that recursion isn't "necessary" to program [operations on]
>> tree structures. It just makes the algorithms appear simpler and
>> clearer, thus recursion is a sensible technique to implement
>> application cases like those.
> 
> Some things you need to do on trees need either explicit recursion, or
> "simulated recursion", where static arrays are used to hold intermediate
> values of variables.  This approach limits the depth of a tree, possibly
> more so than the size of the stack when using explicit recursion.  We
> might just be arguing about the meaning of words here.

The difference is an explicitly programmed stack vs. an implicitly
used stack. Any practical size limitations apply to both, recursion
and iterative replacements.

(I don't know whether we are arguing about meaning of words; I was
just pointing out the non-"necessity", i.e. on the word you used.)

> 
>> WRT Dude's statement it should be mentioned that a recursive algorithm
>> can be transformed to an iterative one, so if iterative algorithms
>> would have the property to be _decidable_ to finish - actually, they
>> are not - we could also say the same for a recursive one.
> 
> Recursion can often be programmed iteratively in practice.  In theory,
> there are recursively defined functions which grow too quickly with
> increasing argument to be definable (or programmable) without recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Janis

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

#402392 — Re: MISRA C

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 2026-09-25 15:48, Alan Mackenzie wrote:
> > Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

> >> WRT Dude's statement it should be mentioned that a recursive algorithm
> >> can be transformed to an iterative one, so if iterative algorithms
> >> would have the property to be _decidable_ to finish - actually, they
> >> are not - we could also say the same for a recursive one.

> > Recursion can often be programmed iteratively in practice.  In theory,
> > there are recursively defined functions which grow too quickly with
> > increasing argument to be definable (or programmable) without recursion.

> Have you functions like fib() in mind? - Despite they are cascaded
> recursion you can create iterative ones. - But it's simpler; just
> recognize that a recursion is using an implicit stack, so you can
> write it in iterative form with an explicit stack. Even an extreme
> function like Ackermann (which is more demanding) is not exempt to
> that principle. - Or do you disagree? (Then please explain - best
> with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name).  It's a function of two natural number arguments.  Simply
making both arguments the same gives a function of one argument.

If memory serves me correctly (which it probably doesn't),
A(0, 0) = 0.
A(1, 1) = 1.
A(2, 2) = 5.
A(3, 3) = 63.
A(4, 4) = 2^2^2^2^2^2^2 + 3
A(5, 5) is much bigger still.

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be.  Or something like that.

But I'll accept that for typical practical programming, a recursive
algorithm can be recast iteratively, with explicitly maintained stacks.
A few years back the Emacs Lisp reader was optimised for speed this way.

> Janis

-- 
Alan Mackenzie (Nuremberg, Germany).

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

#402393 — Re: MISRA C

On 25/09/2026 16:10, Alan Mackenzie wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>> On 2026-09-25 15:48, Alan Mackenzie wrote:
>>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> 
> [ .... ]
> 
>>>> WRT Dude's statement it should be mentioned that a recursive algorithm
>>>> can be transformed to an iterative one, so if iterative algorithms
>>>> would have the property to be _decidable_ to finish - actually, they
>>>> are not - we could also say the same for a recursive one.
> 
>>> Recursion can often be programmed iteratively in practice.  In theory,
>>> there are recursively defined functions which grow too quickly with
>>> increasing argument to be definable (or programmable) without recursion.
> 
>> Have you functions like fib() in mind? - Despite they are cascaded
>> recursion you can create iterative ones. - But it's simpler; just
>> recognize that a recursion is using an implicit stack, so you can
>> write it in iterative form with an explicit stack. Even an extreme
>> function like Ackermann (which is more demanding) is not exempt to
>> that principle. - Or do you disagree? (Then please explain - best
>> with an example you may have in mind.)
> 
> Yes, it was the Ackermann function I had in mind (though I'd forgotten
> its name).  It's a function of two natural number arguments.  Simply
> making both arguments the same gives a function of one argument.
> 
> If memory serves me correctly (which it probably doesn't),
> A(0, 0) = 0.
> A(1, 1) = 1.
> A(2, 2) = 5.
> A(3, 3) = 63.

I think those last two should be 7 and 61.

> A(4, 4) = 2^2^2^2^2^2^2 + 3

If correct, that value would be:

   (2 ** 2 ** 2003...6736) + 3

That third number has over 19000 digits. I think it is equivalent to this:

   (2 ** X)

where X has about 2**2003...6736/3 digits.

The size of the stack might then be the smaller issue! But then, the 
stack needs to be tens of thousands deep just to do A(3, 10) where the 
numbers involved are small.

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

#402395 — Re: MISRA C

Alan Mackenzie <acm@muc.de> writes:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
[...]
>> Have you functions like fib() in mind? - Despite they are cascaded
>> recursion you can create iterative ones. - But it's simpler; just
>> recognize that a recursion is using an implicit stack, so you can
>> write it in iterative form with an explicit stack. Even an extreme
>> function like Ackermann (which is more demanding) is not exempt to
>> that principle. - Or do you disagree? (Then please explain - best
>> with an example you may have in mind.)
>
> Yes, it was the Ackermann function I had in mind (though I'd forgotten
> its name).  It's a function of two natural number arguments.  Simply
> making both arguments the same gives a function of one argument.
>
> If memory serves me correctly (which it probably doesn't),
> A(0, 0) = 0.
> A(1, 1) = 1.
> A(2, 2) = 5.
> A(3, 3) = 63.
> A(4, 4) = 2^2^2^2^2^2^2 + 3
> A(5, 5) is much bigger still.
>
> This function can't be calculated iteratively, since there's no
> non-recursive way of calculating how big the requisite static arrays
> would have to be.  Or something like that.

Who says the arrays have to be static?  You could allocate an
array using malloc() and expand it as needed using realloc().
Or you could use a linked list.

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

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

#402396 — Re: MISRA C

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> Alan Mackenzie <acm@muc.de> writes:

[ .... ]

> > Yes, it was the Ackermann function I had in mind (though I'd forgotten
> > its name).  It's a function of two natural number arguments.  Simply
> > making both arguments the same gives a function of one argument.

[ .... ]

> > This function can't be calculated iteratively, since there's no
> > non-recursive way of calculating how big the requisite static arrays
> > would have to be.  Or something like that.

> Who says the arrays have to be static?  You could allocate an
> array using malloc() and expand it as needed using realloc().
> Or you could use a linked list.

You mean, implement a stack of unbounded size?  If you do that, you are
implementing a recursive algorithm, surely?  The point under discussion
is whether or not Ackermann's function can be implemented without using
recursion.

> [...]

> -- 
> Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
> void Void(void) { Void(); } /* The recursive call of the void */

-- 
Alan Mackenzie (Nuremberg, Germany).

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

#402398 — Re: MISRA C

Alan Mackenzie <acm@muc.de> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> Alan Mackenzie <acm@muc.de> writes:
> [ .... ]
>> > Yes, it was the Ackermann function I had in mind (though I'd forgotten
>> > its name).  It's a function of two natural number arguments.  Simply
>> > making both arguments the same gives a function of one argument.
> [ .... ]
>> > This function can't be calculated iteratively, since there's no
>> > non-recursive way of calculating how big the requisite static arrays
>> > would have to be.  Or something like that.
>
>> Who says the arrays have to be static?  You could allocate an
>> array using malloc() and expand it as needed using realloc().
>> Or you could use a linked list.
>
> You mean, implement a stack of unbounded size?  If you do that, you are
> implementing a recursive algorithm, surely?  The point under discussion
> is whether or not Ackermann's function can be implemented without using
> recursion.

Yes, I mean implementing a stack of unbounded size.

It depends on what you mean by "recursive algorithm".  Using an
explicit stack that can grow as needed is a way to implement
something like Ackermann's function without functions that call
themselves, directly or indirectly.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

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

#402403 — Re: MISRA C

On 25/09/2026 23:05, Keith Thompson wrote:
> Alan Mackenzie <acm@muc.de> writes:
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>>> Alan Mackenzie <acm@muc.de> writes:
>> [ .... ]
>>>> Yes, it was the Ackermann function I had in mind (though I'd forgotten
>>>> its name).  It's a function of two natural number arguments.  Simply
>>>> making both arguments the same gives a function of one argument.
>> [ .... ]
>>>> This function can't be calculated iteratively, since there's no
>>>> non-recursive way of calculating how big the requisite static arrays
>>>> would have to be.  Or something like that.
>>
>>> Who says the arrays have to be static?  You could allocate an
>>> array using malloc() and expand it as needed using realloc().
>>> Or you could use a linked list.
>>
>> You mean, implement a stack of unbounded size?  If you do that, you are
>> implementing a recursive algorithm, surely?  The point under discussion
>> is whether or not Ackermann's function can be implemented without using
>> recursion.
> 
> Yes, I mean implementing a stack of unbounded size.
> 
> It depends on what you mean by "recursive algorithm".  Using an
> explicit stack that can grow as needed is a way to implement
> something like Ackermann's function without functions that call
> themselves, directly or indirectly.
> 

In computation theory (and the Ackermann function is only of theoretical 
interest - it has no practical use!), there is no difference between 
loops and functions that call themselves - it is all recursion.  And it 
doesn't matter if your "stack" is a call stack, a static array, a 
heap-based linked list, or whatever.

The thing that is special about the Ackermann function is that it is not 
"primitive recursive".  That does not mean you can't implement it with a 
loop and an array to hold your stack.  Basically, it means that you 
don't know an upper bound on your stack size in advance.

If you take something like the quicksort algorithm for comparison.  That 
is most clearly implemented in most languages with recursive functions, 
but you can certainly handle it with loops and heap-allocated (or even 
alloca allocated) stacks.  You can also use a single allocation for 
this, because you can find an upper bound - if your input data is length 
"n", a stack of size n^2 will definitely be big enough.

You can implement the Ackermann function without explicit recursion, 
just using a single loop and with allocated stacks or lists to hold the 
progress.  But you /cannot/ do so with a single allocation at the start. 
  If you are asked to calculate A(m, n), you cannot calculate an upper 
bound on the stack size you need without calculating the function.

But with malloc() and realloc(), you are good to go!

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

#402407 — Re: MISRA C

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

[ .... ]

> In computation theory (and the Ackermann function is only of theoretical 
> interest - it has no practical use!), there is no difference between 
> loops and functions that call themselves - it is all recursion.  And it 
> doesn't matter if your "stack" is a call stack, a static array, a 
> heap-based linked list, or whatever.

> The thing that is special about the Ackermann function is that it is not 
> "primitive recursive".  That does not mean you can't implement it with a 
> loop and an array to hold your stack.  Basically, it means that you 
> don't know an upper bound on your stack size in advance.

> If you take something like the quicksort algorithm for comparison.  That 
> is most clearly implemented in most languages with recursive functions, 
> but you can certainly handle it with loops and heap-allocated (or even 
> alloca allocated) stacks.  You can also use a single allocation for 
> this, because you can find an upper bound - if your input data is length 
> "n", a stack of size n^2 will definitely be big enough.

> You can implement the Ackermann function without explicit recursion, 
> just using a single loop and with allocated stacks or lists to hold the 
> progress.  But you /cannot/ do so with a single allocation at the start. 
>  If you are asked to calculate A(m, n), you cannot calculate an upper 
> bound on the stack size you need without calculating the function.

Thanks, David, for the clarification.

> But with malloc() and realloc(), you are good to go!

-- 
Alan Mackenzie (Nuremberg, Germany).

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

#402664 — Re: MISRA C

Sorry I'm jumping in here.  I don't read Usenet much these days but this
got me going.

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

> You can implement the Ackermann function without explicit recursion, just
> using a single loop and with allocated stacks or lists to hold the progress.
> But you /cannot/ do so with a single allocation at the start.   If you are
> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
> size you need without calculating the function.

Hmm...  This is likely to confuse people.  You can calculate A(m, n)
using O(m) extra space.  You can pre-allocate the space you need before
starting the calculation.  (Aside: this disregards the space needed to
store the numbers.  A(m, n) grows so large that you need extra space
just to store the integers, but that complicates the discussion and I
think everyone has been ignoring it in this thread anyway.)

A carefully written recursive version will also use only O(m) stack, but
here we get into problems of definition.  Given that there is an
iterative version that needs only O(m) extra storage there is obviously
a trivial recursive version of that function that, say, just pointlessly
calls itself once!

> But with malloc() and realloc(), you are good to go!

In an imaginary C with unbounded integers, you can do it with a couple
of VLAs at the top of the function.

-- 
Ben.

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

#402670 — Re: MISRA C

On 04/10/2026 00:55, Ben Bacarisse wrote:
> Sorry I'm jumping in here.  I don't read Usenet much these days but this
> got me going.
> 

It is always good to hear from you - c.l.c. was richer when you posted 
more often.

> David Brown <david.brown@hesbynett.no> writes:
> 
>> You can implement the Ackermann function without explicit recursion, just
>> using a single loop and with allocated stacks or lists to hold the progress.
>> But you /cannot/ do so with a single allocation at the start.   If you are
>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>> size you need without calculating the function.
> 
> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
> using O(m) extra space.  

That surprises me.  (The rest of your post follows quite logically from 
this one point.)  Maybe I need to brush up on my computation theory here 
- it's been a while sine I studied it.

A(m, n) can be calculated as (2 arrow[m-2] (n+3)) - 3, or using H(k, a, 
b) to mean (a arrow[k - 2] b), A(m, n) = H(m, 2, n + 3) - 3.

Hyperoperations H are also defined recursively, where

H(0, a, b) = b + 1	// The successor function
H(1, a, b) = a + b	// Addition
H(2, a, b) = a * b	// Multiplication
H(3, a, b) = a ^ b	// Exponentiation
H(4, a, b) = a ^ (a ^ (a ^ (a ^ ...))) with b copies
H(5, a, b) = H(4, a, H(5, a, b - 1))
H(n, a, b) = H(n - 1, a, H(n, a, b - 1))


At each level, I think I can see how H(k, a, b) could be done with a 
number of nested loops where that number can be calculated from k, a and 
b, and that number gives you a size you can allocate for the loop index 
stack.  But inside the inner loop will be a call to H(k - 1, a2, b2), 
and each of these will similarly need nested loops and its own extra 
stack - the size of which will depend on k-1, a2 and b2.  (When k is 
small enough, you don't need that - it gets down to calculations that 
can be done directly.)  I don't see how you can know an upper bound for 
all these at the start of the H(k, a, b) calculation - even simplifying 
with the knowledge that a is 2 here.


I also think disregarding the space for the numbers is perhaps 
"cheating" here.  It does not really make things more complicated either 
- in fact, it simplifies one aspect of it.  It means you are going to 
need at least O(log(A(n, m))) space to calculate A(n, m), so you are 
going to need to know A(n, m) (or an upper bound for it) before 
allocating space.


> You can pre-allocate the space you need before
> starting the calculation.  (Aside: this disregards the space needed to
> store the numbers.  A(m, n) grows so large that you need extra space
> just to store the integers, but that complicates the discussion and I
> think everyone has been ignoring it in this thread anyway.)
> 
> A carefully written recursive version will also use only O(m) stack, but
> here we get into problems of definition.  Given that there is an
> iterative version that needs only O(m) extra storage there is obviously
> a trivial recursive version of that function that, say, just pointlessly
> calls itself once!
> 
>> But with malloc() and realloc(), you are good to go!
> 
> In an imaginary C with unbounded integers, you can do it with a couple
> of VLAs at the top of the function.
> 

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

#402688 — Re: MISRA C

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

> On 04/10/2026 00:55, Ben Bacarisse wrote:
...
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> You can implement the Ackermann function without explicit recursion, just
>>> using a single loop and with allocated stacks or lists to hold the progress.
>>> But you /cannot/ do so with a single allocation at the start.   If you are
>>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>>> size you need without calculating the function.
>> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
>> using O(m) extra space.  
>
> That surprises me.  (The rest of your post follows quite logically from this
> one point.)  Maybe I need to brush up on my computation theory here - it's
> been a while sine I studied it.

Maybe my post was not clear.  I can see why it might have been as was
assuming a model I only put at the end of my post:

> In an imaginary C with unbounded integers, you can do it with a couple
> of VLAs at the top of the function.

I should have said you need only O(m) extra numbers.  As you go on to
say, the storage for the actual numbers is significant for the actual
space complexity, but I don't think that is what people were talking
about when the were referring to "stack depth".  For one thing formal
space complexity is always relative to some model of computation --
usually Turing machines which have no stacks.

> A(m, n) can be calculated as (2 arrow[m-2] (n+3)) - 3, or using H(k, a, b)
> to mean (a arrow[k - 2] b), A(m, n) = H(m, 2, n + 3) - 3.
>
> Hyperoperations H are also defined recursively, where
>
> H(0, a, b) = b + 1	// The successor function
> H(1, a, b) = a + b	// Addition
> H(2, a, b) = a * b	// Multiplication
> H(3, a, b) = a ^ b	// Exponentiation
> H(4, a, b) = a ^ (a ^ (a ^ (a ^ ...))) with b copies
> H(5, a, b) = H(4, a, H(5, a, b - 1))
> H(n, a, b) = H(n - 1, a, H(n, a, b - 1))
>
>
> At each level, I think I can see how H(k, a, b) could be done with a number
> of nested loops where that number can be calculated from k, a and b, and
> that number gives you a size you can allocate for the loop index stack.  But
> inside the inner loop will be a call to H(k - 1, a2, b2), and each of these
> will similarly need nested loops and its own extra stack - the size of which
> will depend on k-1, a2 and b2.  (When k is small enough, you don't need that
> - it gets down to calculations that can be done directly.)  I don't see how
> you can know an upper bound for all these at the start of the H(k, a, b)
> calculation - even simplifying with the knowledge that a is 2 here.

I'm not sure this helps. H is defined in quite a similar way to A, to
you have just moved the goal posts.

> I also think disregarding the space for the numbers is perhaps "cheating"
> here.  It does not really make things more complicated either - in fact, it
> simplifies one aspect of it.  It means you are going to need at least
> O(log(A(n, m))) space to calculate A(n, m), so you are going to need to know
> A(n, m) (or an upper bound for it) before allocating space.

Sure.  I meant O(m) extra numbers.  I should have been clearer up front.

-- 
Ben.

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

#402698 — Re: MISRA C

On 05/10/2026 02:22, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 04/10/2026 00:55, Ben Bacarisse wrote:
> ...
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> You can implement the Ackermann function without explicit recursion, just
>>>> using a single loop and with allocated stacks or lists to hold the progress.
>>>> But you /cannot/ do so with a single allocation at the start.   If you are
>>>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>>>> size you need without calculating the function.
>>> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
>>> using O(m) extra space.
>>
>> That surprises me.  (The rest of your post follows quite logically from this
>> one point.)  Maybe I need to brush up on my computation theory here - it's
>> been a while sine I studied it.
> 
> Maybe my post was not clear.  I can see why it might have been as was
> assuming a model I only put at the end of my post:
> 
>> In an imaginary C with unbounded integers, you can do it with a couple
>> of VLAs at the top of the function.
> 
> I should have said you need only O(m) extra numbers.  As you go on to
> say, the storage for the actual numbers is significant for the actual
> space complexity, but I don't think that is what people were talking
> about when the were referring to "stack depth".  For one thing formal
> space complexity is always relative to some model of computation --
> usually Turing machines which have no stacks.
> 
I guess I'm going to have to think about this a good deal more.  I do 
understand you mean O(m) numbers of unbounded size, but it still does 
not feel right to me.  However, you've studied this field in a lot more 
depth than mean, and far more recently.  So while you can make mistakes 
just like anyone else, the safe bet is that you are right and I was 
wrong.  Now I need to figure out why you are right, and why I was wrong!

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

#402699 — Re: MISRA C

Ben Bacarisse <ben@bsb.me.uk> writes:

> Sorry I'm jumping in here.  I don't read Usenet much these days but this
> got me going.
>
> David Brown <david.brown@hesbynett.no> writes:
>
>> You can implement the Ackermann function without explicit
>> recursion, just using a single loop and with allocated stacks or
>> lists to hold the progress.  But you /cannot/ do so with a single
>> allocation at the start.  If you are asked to calculate A(m, n),
>> you cannot calculate an upper bound on the stack size you need
>> without calculating the function.
>
> Hmm...  This is likely to confuse people.  You can calculate A(m,n)
> using O(m) extra space.  You can pre-allocate the space you need
> before starting the calculation.  (Aside: this disregards the space
> needed to store the numbers.  A(m, n) grows so large that you need
> extra space just to store the integers, but that complicates the
> discussion and I think everyone has been ignoring it in this thread
> anyway.)
>
> A carefully written recursive version will also use only O(m)
> stack, but here we get into problems of definition.  Given that
> there is an iterative version that needs only O(m) extra storage
> there is obviously a trivial recursive version of that function
> that, say, just pointlessly calls itself once!

I don't see what you're getting at here.  The idea that A(m,n)
can be computed with only O(m) space, for any n, goes against
both my intuition and what I remember from my recursive function
theory course (quite a long time in the past now).  At the very
least it seems to require a radically different formulation of
how the Ackermann function is defined.  Can you elaborate how,
for example, A(m,n) can be computed by a recursive function with
O(1) local variables but a call depth that never exceeds O(m)?

By the way, I think I know what you're getting at with extra
storage needed to store the numbers, but we need to be careful
here.  If we are allowed variables that hold arbitrary precision
integers then surely any computable function can be calculated
using only O(1) such variables.

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

#402700 — Re: MISRA C

Ben Bacarisse <ben@bsb.me.uk> writes:

P.S. It's nice to see you posting here again.

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

#402701 — Re: MISRA C

Ben Bacarisse <ben@bsb.me.uk> wrote:
> Sorry I'm jumping in here.  I don't read Usenet much these days but this
> got me going.
> 
> David Brown <david.brown@hesbynett.no> writes:
> 
>> You can implement the Ackermann function without explicit recursion, just
>> using a single loop and with allocated stacks or lists to hold the progress.
>> But you /cannot/ do so with a single allocation at the start.   If you are
>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>> size you need without calculating the function.
> 
> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
> using O(m) extra space.  You can pre-allocate the space you need before
> starting the calculation.  (Aside: this disregards the space needed to
> store the numbers.  A(m, n) grows so large that you need extra space
> just to store the integers, but that complicates the discussion and I
> think everyone has been ignoring it in this thread anyway.)

Not everone.  C does not have unbounded integers, so in C using
signed numbers computation will very quickly lead to overflow.
On can handle non-overflowing cases by very simple iterative code.
Even in language with unbounded integers in practice Ackermann
very quickly will overflow.  So in practice Ackermann is easily
computable, you either get overflow or comptational cost is
related to size of the answer.

In theory, as long as you have two unbounded numeric variables and
a reasonable fixed number of bounded variables you can emultate
single tape Turing machine, so you can compute anything computable.

Function like Ackermann appeard in complexity hierarchies precisely
because of size of numbers that one needs to handle (and possibly store)
during computation.  Note that non-looping program with N-bit state
can make at most 2^N steps, so space complexity also gives you
(possibly poor) bound on time complexity.  OTOH to really use
memory one need to touch it, so in reasonable step-by-step models
actually using N-bit state also gives lower bound proportional to
N for execution time.  In high complexity classes numbers grow
absurdly fast and "mere" exponential on the top does not change
qualitative behaviour.

Practially, theory says that power of your computaional class
is equivalent to your willingnes to throw resources at the
computation.

> A carefully written recursive version will also use only O(m) stack, but
> here we get into problems of definition.  Given that there is an
> iterative version that needs only O(m) extra storage there is obviously
> a trivial recursive version of that function that, say, just pointlessly
> calls itself once!

AFAIK when you allocate memory at the start some functional folks
will still call it iterative.  After all you can just use one
vector valued variables plus possibly a fixed number of temporaries.
Only when you really do allocation on the stack and access the
allocated values in stack-like manner it is considerd trurly
recursive.  AFAICS the following has recursion depth of m and
uses fixed number of variables per recursion level:

bigint A(bigint m, bigint n) {
    if (m == 0) {
        return n + 1;
    }
    bigint res = 1;
    for(bigint l = 0; l <= n; l++) {
        tmp = A(m - 1, tmp);
    }
    return res;
}

where bigint is appropriate type for unbounded integers.  There
are various definition of Ackermanm function, the above corresponds
to following purely recursive definition:

A(0, n) = n + 1
A(m, 0) = A(m - 1, 1);
A(m, n) = A(m - 1, A(m, n - 1))

-- 
                              Waldek Hebisch

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

#402702 — Re: MISRA C

On 2026-10-05 11:02, Waldek Hebisch wrote:
> Ben Bacarisse <ben@bsb.me.uk> wrote:
>> Sorry I'm jumping in here.  I don't read Usenet much these days but this
>> got me going.
>>
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> You can implement the Ackermann function without explicit recursion, just
>>> using a single loop and with allocated stacks or lists to hold the progress.
>>> But you /cannot/ do so with a single allocation at the start.   If you are
>>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>>> size you need without calculating the function.
>>
>> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
>> using O(m) extra space.  You can pre-allocate the space you need before
>> starting the calculation.  (Aside: this disregards the space needed to
>> store the numbers.  A(m, n) grows so large that you need extra space
>> just to store the integers, but that complicates the discussion and I
>> think everyone has been ignoring it in this thread anyway.)
> 
> Not everone.  C does not have unbounded integers, so in C using
> signed numbers computation will very quickly lead to overflow.
> On can handle non-overflowing cases by very simple iterative code.
> Even in language with unbounded integers in practice Ackermann
> very quickly will overflow.  So in practice Ackermann is easily
> computable, you either get overflow or comptational cost is
> related to size of the answer.

I don't think the question here was about a "universal Ackermann"
function, neither concerning the representation of integers with
its extreme growth, nor with any need to going as fundamental as
to Turing machines. The previously posted "iterative Ackermann"
C-function showed the same range of numerically representable
arguments and results as the respective recursive function, and
its space demands appear to not be larger than the recursive one
(with its internal stack hidden by the programming language's
implicit mechanisms).

I'd like to also remind that Alan's original example was not as
extreme as Ackermann function (which is of rare practical use),
but rather he mentioned the common recursive tree-algorithms.
Their "non-linearity" would make iterative versions also have to
introduce some stack-"memory" (so is in that respect not different).
The point is that you can formulate these recursive algorithms in
a much more obvious (simple) way than with introducing explicit
stacks.

Janis

> [...]

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

#402705 — Re: MISRA C

antispam@fricas.org (Waldek Hebisch) writes:

> Ben Bacarisse <ben@bsb.me.uk> wrote:
>> Sorry I'm jumping in here.  I don't read Usenet much these days but this
>> got me going.
>> 
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> You can implement the Ackermann function without explicit recursion, just
>>> using a single loop and with allocated stacks or lists to hold the progress.
>>> But you /cannot/ do so with a single allocation at the start.   If you are
>>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>>> size you need without calculating the function.
>> 
>> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
>> using O(m) extra space.  You can pre-allocate the space you need before
>> starting the calculation.  (Aside: this disregards the space needed to
>> store the numbers.  A(m, n) grows so large that you need extra space
>> just to store the integers, but that complicates the discussion and I
>> think everyone has been ignoring it in this thread anyway.)
>
> Not everone.  C does not have unbounded integers, so in C using
> signed numbers computation will very quickly lead to overflow.
> On can handle non-overflowing cases by very simple iterative code.
> Even in language with unbounded integers in practice Ackermann
> very quickly will overflow.  So in practice Ackermann is easily
> computable, you either get overflow or comptational cost is
> related to size of the answer.
>
> In theory, as long as you have two unbounded numeric variables and
> a reasonable fixed number of bounded variables you can emultate
> single tape Turing machine, so you can compute anything computable.

Sure.  I have made a mess of what I was saying as it's not really about
formal complexity at all but about an analysis of possible algorithms as
your example makes explicit.

Maybe no misconception need to be corrected in the thread.  I just got
the idea that some people thought there was no way to know how deep a
stack (or how large a temporary array of [big]numbers) would be needed
before computing A(m, n).

...
>> A carefully written recursive version will also use only O(m) stack, but
>> here we get into problems of definition.  Given that there is an
>> iterative version that needs only O(m) extra storage there is obviously
>> a trivial recursive version of that function that, say, just pointlessly
>> calls itself once!
>
> AFAIK when you allocate memory at the start some functional folks
> will still call it iterative.  After all you can just use one
> vector valued variables plus possibly a fixed number of temporaries.
> Only when you really do allocation on the stack and access the
> allocated values in stack-like manner it is considerd trurly
> recursive.  AFAICS the following has recursion depth of m and
> uses fixed number of variables per recursion level:
>
> bigint A(bigint m, bigint n) {
>     if (m == 0) {
>         return n + 1;
>     }
>     bigint res = 1;
>     for(bigint l = 0; l <= n; l++) {
>         tmp = A(m - 1, tmp);

Surely s/tmp/res/g?

>     }
>     return res;
> }
>
> where bigint is appropriate type for unbounded integers.

-- 
Ben.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web