Up to Main Index                            Up to Journal for August, 2023

                    JOURNAL FOR TUESDAY 15TH AUGUST, 2023
______________________________________________________________________________

SUBJECT: A misbehaving factorial rabbit hole
   DATE: Tue 15 Aug 20:20:21 BST 2023

I’d just finished the work on if-elif-else-fi blocks and was updating the Mere
ICE documentation when I had, what I thought at the time, was a splendid idea:

  “Why not modernise all of the example Mere code to use for/next loops,
    functions and if-elif-else-fi?”

One of the changes I made was to update the factorial example from:


  N = 4
  p = f = x = 1

  if 0<N && N<=20; goto next
    println "N must be between 1 and 20."
    exit

  next:
    p  = f
    f *= x
    printf "%d × %d = %d\\n" x p f
  if x++ <= N; goto next

  printf "\\n%d! = %d" N f


To a more traditional example of recursion:


  for x = 1; x <= 20; x++
    printf "%2d! = %d\\n" x, call factorial(x)
  next
  exit

  // factorial is a recursive function to calculate: n! = n*(n-1)*(n-2)…*1
  factorial: func N
    is N == 0; return 1
    return N * call factorial(N-1)
  endfunc


Only it didn’t work :( Well it did, if I changed the function to:


  factorial: func N
    is N == 0; return 1
    return int(N) * call factorial(N-1)
  endfunc


See that “int(N)” hiding in there? A very ugly hack to force N to the stack.
But… it should work without the hack… but didn’t… but why? Hrmmm…

I then spent several days tearing my hair out digging into the problem. What I
ended up with was a hack in the way Mere deals with variables during function
calls. I wasn’t happy. It worked, but was butt ugly and seriously effected the
performance of function calls…

I spent nearly a week messing about fixing the fixes, improving the situation
little by little. I hated the final result, but it worked…

Then yesterday evening I’d had enough. I hate poor code, and I’m damned if I’m
the one who writes it! I bit the bullet. I knew what the answer was and how to
fix the problem — I had to gut and totally rewrite how Mere handles variable
storage internally. In total it took about five or six hours to rip out the
offending code and replace it all with a new implementation, and have all of
the tests passing :)

The End?

Not quite…

Function calls are fast with very little accounting required. A few nasty
scoping rule surprises have been fixed. Overall Mere is a little slower — by
about 10%[1], but better for it. I knew before I bit the bullet that the
changes would cause a performance hit, I just didn’t know how big a hit. Is
10% a little too much? There is still some cleaning-up needed. A refactoring
at some point will help as well. A side effect is that I should be able to
implement proper closures… maybe…

With the problem solved properly, the Mere ICE documentation done and Mere ICE
updated for Go 1.21.0 I just have some final testing to do[2]. I think it will
then be time for a Mere v0.0.5 release :)

--
Diddymus

  [1] Based on running the counter.mr benchmark against v0.0.4 and HEAD.

  [2] I need to build Go 1.21.0 on my dev boxes, including the Raspberry Pi
      Zero W. Then test across all of the platforms…


  Up to Main Index                            Up to Journal for August, 2023