Tail recursive subroutine

[pepijndevos]

NBC doesn't have a stack or pointers, except for the return "pointer" of a subcall. And then, isn't the whole point of tail recursion that it doesn't consume stack space?

The plan:

• do a subcall with return pointer next
• recur using temp for a pointer
• exit using next

Code: Select all

myseg segment
  next word
  temp word

  counter word
myseg ends

subroutine tailrecursive
  add counter counter 1
  NumOut(0, LCD_LINE1, counter)
  // doesn't work, counter is set to one and app quits
  // subcall tailrecursive temp
  // does work, but we lost our exit now
  subcall tailrecursive next
  
  subret next
ends


thread main
  subcall tailrecursive next
  wait 5000
endt

Why doesn't this work? Is it a bug, or does the firmware "manage" that variable in a way that prohibits this?

[afanofosc]

I'm not sure I can explain the behavior you are seeing. However, it looks like maybe you could use exitto in order to do what you are trying to do.

Code: Select all

myseg segment
  next byte
  temp byte

  counter word
myseg ends

subroutine tailrecursive
  brcmp GT, LBL_GT3000, counter, 3000
  add counter, counter, 1
  NumOut(0, LCD_LINE1, counter)
  exitto tailrecursive
LBL_GT3000:
  subret next
ends

thread main
  subcall tailrecursive, next
  TextOut(0, LCD_LINE7, 'done')
  wait 5000
endt

Maybe this is a useful technique. I don't know. Please share whatever cool things you wind up doing with this.

John Hansen

[pepijndevos]

Interesting, it'd work for this case. I can't find exitto in the firmware guide, so I assume it's implemented as a few other primitives. It'd be interesting to know which ones. Likewise for call. Is there a readable C file in the enhanced firmware NBC compiler that defines these?

What I'm really after is full recursive functions. You see, if the return pointer is really a normal variable, I can implement a stack and push it on there.

Code: Select all

dseg segment

  TStack struct
    data word[]
    offset word
  TStack ends

dseg ends

#define push(stack, val) \
  replace stack.data stack.data stack.offset val \
  add stack.offset stack.offset 1

#define pop(stack, val) \
  sub stack.offset stack.offset 1 \
  index val stack.data stack.offset

So every subroutine would start with push(returnstack, next) and end with pop(returnstack, next); subret next.

[pepijndevos]

While just going ahead and implementing a mutual recursive odd/even subroutine, I encountered even more weirdness.

I defined a macro to pop the stack and return, but then NBC gave an error that a subroutine needs to end with a return statement.

The odd/even code seems to break out of the loop midway, for no obvious reason. The code blow prints 4 on the screen. It could be just a bug in my code, but I doubt it.

Code: Select all

dseg segment

  TStack struct
    data word[]
    offset word
  TStack ends

  returnstack TStack
  nextword word

  datastack TStack
  val word

dseg ends

#define push(stack, val) \
  replace stack.data stack.data stack.offset val \
  add stack.offset stack.offset 1

#define pop(stack, val) \
  sub stack.offset stack.offset 1 \
  index val stack.data stack.offset

#define callword(theword) \
  subcall theword nextword

myseg segment
  number word
myseg ends

subroutine odd
  push(returnstack, nextword)

  pop(datastack, number)
  brtst EQ NotOdd number

  sub number number 1
  push(datastack, number)
  callword(even)

  jmp RetOdd
  
NotOdd:
  push(datastack, 0)

RetOdd:
  pop(returnstack, nextword)
  subret nextword
ends

subroutine even
  push(returnstack, nextword)

  pop(datastack, number)
  brtst EQ Even number

  sub number number 1
  push(datastack, number)
  callword(odd)

  jmp RetEven
  
Even:
  push(datastack, 1)

RetEven:
  pop(returnstack, nextword)
  subret nextword
ends

thread main
  arrinit datastack.data 0 32
  arrinit returnstack.data 0 32

  push(datastack, 1)
  push(datastack, 2)
  push(datastack, 9)
  push(datastack, 7)
  callword(even)

  pop(datastack, number)
  NumOut(0,0,number)

  wait 5000
endt

[HaWe]

my advice: forget about recursions using NXC.

But if you won't give up: try to implement a useful code, e.g. generating Fibonacci Numbers:

Code: Select all

int fib(int n){
  return (n<2?1:(fib(n-1) + fib(n-2));}

task main() {
  printf("%d", fib(20));
  while(1);
}

[afanofosc]

I would encourage you to look at how the firmware implements the subcall and subret opcodes and clump queuing/scheduling in general.

Code: Select all

    case OP_SUBCALL:
    {
      NXT_ASSERT(cCmdIsClumpIDSane((CLUMP_ID)Arg1));
      NXT_ASSERT(!cCmdIsClumpOnQ(&(VarsCmd.RunQ), (CLUMP_ID)Arg1));

      NXT_ASSERT(cCmdIsDSElementIDSane(Arg2));
      
      CLUMP_ID clump = VarsCmd.RunQ.Head;
      CLUMP_REC* pClumpRec = &(VarsCmd.pAllClumps[clump]);
      pClumpRec->CalledClump = (CLUMP_ID)Arg1;

      *((CLUMP_ID *)(cCmdDSScalarPtr(Arg2, 0))) = clump;

      cCmdDeQClump(&(VarsCmd.RunQ), clump); //Take caller off RunQ
      cCmdEnQClump(&(VarsCmd.RunQ), (CLUMP_ID)Arg1);  //Add callee to RunQ

      Status = CLUMP_SUSPEND;
    }
    break;

Code: Select all

    case OP_SUBRET:
    {
      NXT_ASSERT(cCmdIsDSElementIDSane(Arg1));
      CLUMP_ID clump = *((CLUMP_ID *)cCmdDSScalarPtr(Arg1, 0));
      
      //Take Subroutine off RunQ
      //Add Subroutine's caller to RunQ
      cCmdDeQClump(&(VarsCmd.RunQ), VarsCmd.RunQ.Head);
      cCmdEnQClump(&(VarsCmd.RunQ), clump);

      CLUMP_REC* pClumpRec = &(VarsCmd.pAllClumps[clump]);
      pClumpRec->CalledClump = NOT_A_CLUMP;
      
      Status = CLUMP_DONE;
    }
    break;

I suspect that the EnQ and DeQ routines, and possibly the design of the run queue, is causing the odd behavior that you are seeing. BTW, the return address variable is just a byte (storing a clump ID from 0 to 255). It could be something to do with the clump firecount as well.

The exitto opcode is called FINCLUMPIMMED in the NXT Executable File Specification PDF. You can find information about it and all the other NBC opcodes in the NBC Programmer's Guide and the online NBC Help files.

http://bricxcc.sourceforge.net/nbc/doc/ ... hedst.html
http://bricxcc.sourceforge.net/nbc/doc/NBC_Guide.pdf

The code for exitto is here:

Code: Select all

    case OP_FINCLUMPIMMED:
    {
        CLUMP_ID Clump= VarsCmd.RunQ.Head; // DeQ changes Head, use local val
        cCmdDeQClump(&(VarsCmd.RunQ), Clump); //Dequeue finalized clump
        cCmdSchedDependent(Clump, (CLUMP_ID)Arg1);  // Use immediate form

        Status = CLUMP_DONE;
    }
    break;

John Hansen

[afanofosc]

Is there a readable C file in the NBC compiler that defines these?

NBC is written in Pascal so it is extremely readable. Look at uNXTClasses.pas and uNXTConstants.pas here: https://bricxcc.svn.sourceforge.net/svn ... icxcc/NXT/

John Hansen

[pepijndevos]

Ok, so that explains call and exitto. I'll look at the pimped exit later.

I can't say I immediately understand how these opcodes work. However, the fact that the return code is just the clump ID raises some new questions.

If I call from clump A to clump B and B returns, is clump A merely 'resumed''? In other words, how does it get back to the correct location in clump A?

With recursion, we refer to the same clump that was just suspended, does that mean this clump is just resumed, or restarted? Now, what happens when we return to the clump we already resumed or restarted?

In either case, there is no way we could get back to the exact point we left the routine, and the routine we just left(which is also the one we're returning to) is marked 'done'.

I think that might be what I was seeing, that returning caused a clump to be marked done to early, or execution resumed in another place than I expected.

On related note, what is the difference between a subroutine and a thread, because both seem to be compiled to clumps?

[pepijndevos]

FINCLUMP_PIMMED also takes a direct value. So that is basically equal to just jumping to the start. It'll work nonetheless.

So basically I can do tail recursion using exito(but not normal or mutual recursion), and then normal function calls using subret with my stack.

[spillerrec]

Shouldn't you be able to do tail recursion with a simple jmp/goto? It would be nice to see this in NXC, even though I not so sure how many would use it (or even know that it is possible)...