Finishing the jack-compiler

[Murray Steele]

Hi all,

As mentioned in my last post to the list about Meeting 12[1], I’ve been working on finishing the jack-compiler.  I’ve just managed to get it to successfully compile all the example jack programs in nand2tetris/projects/11/ so I’m calling it done.  Well, functionally complete at least.

I’ve raised a PR[2] with all my effort.  My approach has been to compile the jack code from nand2tetris/projects/11/ with the provided tool and create a spec for the compilation engine that tests our vm code is the same as what it produced.  It took me a few evenings to get this done.  I think we might have needed an 11d and 11e if we were to do it as a group, mostly because there were some discrepancies between what the book suggested and what the provided tool did.

Anyway, feel free to have a look.

Cheers,

Murray

[1]: https://groups.google.com/d/msg/london-computation-club/OVGKdDgO-aA/8bej-w9agVEJ

[2]: https://github.com/computationclub/jack-compiler/pull/2

[Tom Stuart]

On 17 Jul 2015, at 12:20, Murray Steele <murray...@gmail.com> wrote:
> I’ve been working on finishing the jack-compiler. I’ve just managed to get it to successfully compile all the example jack programs in nand2tetris/projects/11/ so I’m calling it done.

I finally had a chance to look through this PR. It’s excellent — probably the best outcome imaginable from where we got to in the meetings. The testing stuff in particular is really nice, and I found your exposition of the mismatches between the book and the reference compiler implementation really interesting too.

Congratulations Murray, and thanks for the heroic effort.

Unless someone else wants to surprise us with their complete reimplementation of a Jack compiler in Treetop/XSLT/INTERCAL/Jack/whatever, I definitely think we should merge this on Tuesday and use it to compile our Jack programs for chapter 12.

Oh, also, reminder for everyone: it’s our next meeting on Tuesday! Maybe we’ll finish the book‽ http://lanyrd.com/2015/london-computation-club-nand2tetris-meeting-12/

Cheers,
-Tom

[Paul Mucur]

In a frustrating calendar fail on my part, I'm afraid I'm going to have to miss tonight but I'm very keen to see the end to our Jack compiling adventures.

I look forward the write-up and good luck with the operating system!

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.
To post to this group, send an email to london-comp...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/A4BB1449-5D5E-4685-906B-5D8F0859CF81%40codon.com.
For more options, visit https://groups.google.com/d/optout.

[Tom Stuart]

Quick sanity check: are there sufficient attendees to make tonight's meeting viable? Lanyrd says 3 attendees (Chris P, Leo, me); I know James M, Murray and Paul can't make it. Any other takers?

[Kevin Butler]

I forgot to Lanyrd, but count me in unless we're postponing!

[Tom Stuart]

On 21 Jul 2015, at 16:41, Kevin Butler <haq...@gmail.com> wrote:
> I forgot to Lanyrd, but count me in unless we're postponing!

Thanks, Kevin — I reckon four people is a minimum viable meeting.

[Leo Cassarani]

We have way more crisps and beer than four people's worth, but I'm not complaining!

Leo

> --
> You received this message because you are subscribed to the Google Groups "London Computation Club" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.
> To post to this group, send an email to london-comp...@googlegroups.com.

> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/51DB2FFA-7E59-4046-93E5-A55A69EDDBFC%40codon.com.

[Chris Patuzzo]

I'll likely be a few minutes late. The good news is - I've drunk lots of coffee and I'm raring to go.

> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/3E7465E8-CFD2-4BDE-B71A-3BDEED27E9C5%40geckoboard.com.

[Paul Mucur]

How did it go? Are we in danger of becoming the London Jack User Group?

To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/D5018988-B439-4D1D-A3EF-E0103461FA30%40patuzzo.co.uk.

[Tom Stuart]

On 22 Jul 2015, at 09:49, Paul Mucur <mu...@mudge.name> wrote:
> How did it go? Are we in danger of becoming the London Jack User Group?

I think it went well! We certainly made a bit of progress on Jack OS. I’m writing it up now.

[Chris Patuzzo]

Hi Paul,

The meeting went well. We spent some time looking through Murray's commit messages then moved on to complete the Memory.jack and Array.jack implementations in the Operating System chapter. We chose to implement the basic memory allocation strategy as that was all that was required to pass the test. We looked at the free list approach and discussed how a memory defragmentation process might work.

Some of the meeting was spent setting up a Makefile which we used to leverage the Main.jack test harness for each of the operating system classes. I think we'd be better placed to start the LMUG meetup after yesterday's collective enthusiasm for Makefiles.

When we implemented the Array class, we learnt some interesting things about how objects work in the Jack language. The Array.new function returns a pointer to some memory, but the test harness subsequently calls an instance method of Array on this pointer which seemed quite odd to us. I don't remember all of the detail around this as some of it went over my head, but I'm sure the others could elaborate.

We didn't implement any of the Math operations, but we did work through the algorithm for division on the whiteboard. At first, this seemed incredibly cryptic and we had to look for patterns to understand how it worked. There was a statement in the book towards the end of that section (I don't have the book handy at the moment), which none of us initially understood about reusing an intermediate value between levels of recursion. Once we'd figured this out, we looked at how the pseudocode presented in the book could be altered to reuse this intermediate value.

We didn't agree on when the next meeting should take place yet. I think Leo mentioned it's his birthday in a couple of weeks.

If you're interested, all of the recordings so far are captured here: fortress.patuzzo.co.uk/public/computation_club

Chris

[Tom Stuart]

On 22 Jul 2015, at 11:03, Chris Patuzzo <ch...@patuzzo.co.uk> wrote:
> The meeting went well. […]

Ah, thanks Chris, this saves me some effort!

[Tom Stuart]

On 22 Jul 2015, at 11:03, Tom Stuart <t...@codon.com> wrote:
> I’m writing it up now.

I’m doubtful how much it adds to what Chris has already said, but this is now live: https://github.com/computationclub/computationclub.github.io/wiki/Elements-of-Computing-Systems-Chapter-12

Cheers,
-Tom

[Tom Stuart]

On Wednesday, July 22, 2015 at 4:54:47 PM UTC+1, Tom Stuart wrote:

I’m doubtful how much it adds to what Chris has already said, but this is now live: https://github.com/computationclub/computationclub.github.io/wiki/Elements-of-Computing-Systems-Chapter-12

 

Hey, division fans: why doesn’t this work?

>> def divide(x, y)

     return [0, 0] if y > x

     y_next = 2 * y

     q, qy2_next = divide(x, y_next)

     qy2 = y_next + qy2_next

     if (x - qy2) < y

       return [2 * q, qy2]

     else

       return [2 * q + 1, qy2]

     end

   end

=> :divide

>> divide(95, 3)

=> [0, 186]

Cheers,

-Tom

[Kevin Butler]

If returned `q` is zero then the multiplication would zero out `2qy` but the addition doesn't check for this! Oops!

So our line 4 of divide should actually have had a check similar to: `qy2 = if q == 0 then 0 else y_next + qy2_next end`.

[Tom Stuart]

On 23 Jul 2015, at 20:09, Kevin Butler <haq...@gmail.com> wrote:
> If returned `q` is zero then the multiplication would zero out `2qy` but the addition doesn't check for this! Oops!
> So our line 4 of divide should actually have had a check similar to: `qy2 = if q == 0 then 0 else y_next + qy2_next end`.

Ah, well spotted, thank you!

So this works pretty well now:

>> divide(95, 3).first
=> 31
>> divide(42, 6).first
=> 7

But in other cases it gives the wrong answer:

>> divide(40, 4).first
=> 8
>> divide(37, 7).first
=> 4

What’s gone wrong?

[Kevin Butler]

Looks like we were overzealous with declaring our algorithm from only 3-4 traces!

I dumped the code and original algorithm into a script and traced them for the values you provided, top is the algorithm from the book, bottom is ours:

y=32 q=0, qy2=0
y=16 q=1, qy2=32
y=8 q=2, qy2=32
y=4 q=5, qy2=40
Original Answer= 10

y=32 q=0, qy2=0
y=16 q=1, qy2=32
y=8 q=2, qy2=48
y=4 q=4, qy2=56
Answer= 8


In the original algorithm, `qy2` doesn't change whenever the returned `q` value is just doubled, e.g. on the second frame where x-qy2 < y is true ((40 - 32) < 16). I found that having `qy2-y` as the return value for the first branch made things work out, which cancels out the addition at the next level (our y_next + qy2_next).  This leads to a better algorithm (I think) where we can make the decision at the lower level and not have to cache `y_next` or make decisions on `q`:

def divide(x, y)
  return [0, 0] if y > x

  q, qy2 = divide(x,  y + y)
  puts "y=#{y} q=#{q}, qy2=#{qy2}" if $debug

  if (x - qy2) < y
    return [2 * q, qy2]
  else

    return [2 * q + 1, qy2 + y]
   end
 end

From how I understand this, `qy2` is the amount currently accounted for in the division, and the check is testing to see if the 'current level' fits within the remaining space. When there is space we return the quotient incremented an extra time, then to match this we bump up the cumulative value `qy2` by the current `y` (which at the higher level is `2 * y` in the old multiplication algorithm).

Here's a gist with the updated code which includes testing against a decent sample of values (0..999)/(1..2000): https://gist.github.com/Ryman/23825937647c1127aaba

[Tom Stuart]

On 24 Jul 2015, at 13:06, Kevin Butler <haq...@gmail.com> wrote:
> From how I understand this, `qy2` is the amount currently accounted for in the division, and the check is testing to see if the 'current level' fits within the remaining space. When there is space we return the quotient incremented an extra time, then to match this we bump up the cumulative value `qy2` by the current `y` (which at the higher level is `2 * y` in the old multiplication algorithm).

This is great, Kevin — thanks for getting to the bottom of it! Your code certainly looks like it works.

I wonder if this is really what they meant, i.e. returning multiple values from the recursive call? It seems slightly counterproductive to have to allocate/deallocate memory every time. Is that really more efficient than just doing the flippin multiplication? Is there some other way we’re missing?

Cheers,
-Tom

[Kevin Butler]

It should be possible to pass down `qy2` and mutate a single reference during the entire computation. i.e. we return from `divide` the result of `divide_inner(0, 0, &mut 0)`.

[Leo Cassarani]

That does sound feasible, even in Jack. Alternatively, am I right in thinking that the initial method call could allocate a single array, and pass it down through the recursive call stack? The method would effectively return void, and deliver both results via the two-element array.

Leo

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.

To post to this group, send email to london-comp...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/2d4deeb6-3573-4842-b726-0a061ca88e38%40googlegroups.com.

[Tom Stuart]

On 28 Jul 2015, at 10:22, Leo Cassarani <l...@geckoboard.com> wrote:
> am I right in thinking that the initial method call could allocate a single array, and pass it down through the recursive call stack? The method would effectively return void, and deliver both results via the two-element array.

We could do this, but at that point it seems perverse to define the function recursively. Maybe it makes more sense to convert it to an iterative function so that we can just use local variables and plain assignment rather than mutating an array?

[Leo Cassarani]

Yes, I'd be curious to see the non-recursive version of this algorithm. Does Jack have while loops?

> --
> You received this message because you are subscribed to the Google Groups "London Computation Club" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.

> To post to this group, send an email to london-comp...@googlegroups.com.
> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/E6277CCF-6854-485C-BC62-89E97FA1BC56%40codon.com.

[Chris Patuzzo]

They don't claim in the book that there's a more efficient way to implement division in jack specifically, they just state that the pseudocode algorithm they provide is suboptimal. I'd imagine it is possible through the techniques Kevin and Leo describe.

The reason it's suboptimal is because a multiplication takes O(n) operations where n is the number of bits in the numerator. Division can be achieved in O(n) as well but the pseudocode uses multiplication in each step which is itself an O(n) operation. (I guess this makes their algorithm O(n^2)?)

The other multiplications are 2 * y and 2 * q, which can be achieved with a simple bit-shift.

Is this correct, or have I misunderstood?

Chris

To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/B623013F-FE0E-4CE3-BE6E-6D1E325403D6%40geckoboard.com.

[Kevin Butler]

Yes Chris, that matches my understanding of the book's conundrum from memory.

Regarding the other multiplications, I'm unsure if we have bit shifting on our CPU, but luckily those two can be done with a single addition each (y + y = 2y) if not.

On Tuesday, 4 August 2015 12:57:49 UTC+1, Chris Patuzzo wrote:

They don't claim in the book that there's a more efficient way to implement division in jack specifically, they just state that the pseudocode algorithm they provide is suboptimal. I'd imagine it is possible through the techniques Kevin and Leo describe.

The reason it's suboptimal is because a multiplication takes O(n) operations where n is the number of bits in the numerator. Division can be achieved in O(n) as well but the pseudocode uses multiplication in each step which is itself an O(n) operation. (I guess this makes their algorithm O(n^2)?)

The other multiplications are 2 * y and 2 * q, which can be achieved with a simple bit-shift.

Is this correct, or have I misunderstood?

Chris

On 28 Jul 2015, at 10:22 am, Leo Cassarani <l...@geckoboard.com> wrote:

That does sound feasible, even in Jack. Alternatively, am I right in thinking that the initial method call could allocate a single array, and pass it down through the recursive call stack? The method would effectively return void, and deliver both results via the two-element array.

Leo

On 27 Jul 2015, at 16:44, Kevin Butler <haq...@gmail.com> wrote:

It should be possible to pass down `qy2` and mutate a single reference during the entire computation. i.e. we return from `divide` the result of `divide_inner(0, 0, &mut 0)`.

On Monday, 27 July 2015 14:56:51 UTC+1, Tom Stuart wrote:

On 24 Jul 2015, at 13:06, Kevin Butler <haq...@gmail.com> wrote:
> From how I understand this, `qy2` is the amount currently accounted for in the division, and the check is testing to see if the 'current level' fits within the remaining space. When there is space we return the quotient incremented an extra time, then to match this we bump up the cumulative value `qy2` by the current `y` (which at the higher level is `2 * y` in the old multiplication algorithm).

This is great, Kevin — thanks for getting to the bottom of it! Your code certainly looks like it works.

I wonder if this is really what they meant, i.e. returning multiple values from the recursive call? It seems slightly counterproductive to have to allocate/deallocate memory every time. Is that really more efficient than just doing the flippin multiplication? Is there some other way we’re missing?

Cheers,
-Tom

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.

To unsubscribe from this group and stop receiving emails from it, send an email to london-computation-club+unsub...@googlegroups.com.

To post to this group, send email to london-comp...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/2d4deeb6-3573-4842-b726-0a061ca88e38%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.

To unsubscribe from this group and stop receiving emails from it, send an email to london-computation-club+unsub...@googlegroups.com.