teaching machines

CS 330 Lecture 38 – Monkey patching, Meta-programming, Blocks, and Mixins

May 8, 2013 by Chris Johnson. Filed under cs330, lectures, spring 2013.

Agenda

• what ?s
• monkey patching
• why monkey patch? a custom malloc
• reflection and meta-programming
• why meta-program? a testing framework
• adding blocks to TestTest
• mixins
• making things Orderable (IRL, use Comparable)

?s

• Are there non-English languages?
  • http://en.wikipedia.org/wiki/Non-English-based_programming_languages
  • http://www.codinghorror.com/blog/2009/03/the-ugly-american-programmer.html
• What’s the point of symbols?
  • http://www.troubleshooters.com/codecorn/ruby/symbols.htm
  • http://glu.ttono.us/articles/2005/08/19/understanding-ruby-symbols
  • http://www.robertsosinski.com/2009/01/11/the-difference-between-ruby-symbols-and-strings
• Is there something like tryruby.org for Haskell?
  • http://tryhaskell.org
• Is there something like tryruby.org for C?
  • http://tryc.org
• “What would be the point of doing 0…5 to represent nums 1-4 when you can just do 1..4?”

TODO

• Write a question that could appear on the final exam. Derive your question from the topics posted under the previous lecture. Post in the comments for a participation point, using a name by which I can identity you. (First name and last initial is fine.) Post a second for extra credit. Do not turn in a piece of paper.

Code

monkey.rb

#!/usr/bin/env ruby

class Fixnum
  def [] i
    i + self
  end
end

puts 6[3]

mymalloc.cpp

#include <iostream>

const int NWORDS = 2048;
int heap[NWORDS];

char *malloc(int nwords) {
  int *block_start = (int *) heap;

  // Load up the metadata for the first block.
  int nwords_in_block = block_start[0];
  int is_free = block_start[1];

  // If the block is free and large enough, then we can give some portion
  // of it back to the caller. Otherwise, we check the next block to see
  // if it can satisfy the request.
  while (!is_free || nwords > nwords_in_block) {
    block_start += nwords_in_block + 2;
    nwords_in_block = block_start[0];
    is_free = block_start[1];
  }

  // Invariant: block_start points to a block that can hold the requested
  // number of bytes. (Or we're out of memory, a case I don't handle.)

  // This block holds has room for the requested number of words and is no
  // longer free.
  block_start[0] = nwords;
  block_start[1] = 0;

  // If the requested number of words is less than the actual capacity of
  // the block, then we split the block in two. The unused portion gets
  // marked free.
  if (nwords < nwords_in_block) {
    block_start[2 + nwords] = nwords_in_block - nwords - 2;
    block_start[2 + nwords + 1] = 1;
  }

  // The metadata exists in the first two words of this block. The actual
  // caller data starts two words later, so it's that address we give
  // back.
  return (char *) (block_start + 2);
};

void free(void *pointer) {
  // The caller will have sent us an address two words into the block that
  // was previously allocated with malloc. The block is marked free, but
  // it retains its size. A future malloc call can make use of it if it
  // provides enough words.
  int *block_start = ((int *) pointer) - 2;
  block_start[1] = 1;

  // A smarter implementation would coalesce adjacent free blocks to avoid
  // fragmentation.
}

void leak_check();

int main(int argc, char **argv) {
  // I've got to initialize the free list that is used to manage the heap.
  // I'm sure there's a better way to do this.
  ((int *) heap)[0] = NWORDS - 2;
  ((int *) heap)[1] = 1;

  int *a = (int *) malloc(4);
  free(a);
  a = (int *) malloc(8);
  free(a);

  // Are there any blocks still marked free?
  leak_check();

  return 0;
}






















void leak_check() {
  int *block_start = (int *) heap;

  while (block_start - heap < NWORDS) {
    int nwords_in_block = block_start[0];
    int is_free = block_start[1];

    if (!is_free) {
      std::cout << "a leak!" << std::endl;
    }

    block_start += nwords_in_block + 2;
  }
}

TestTest.rb

#!/usr/bin/env ruby

class TestTest
  # def TestTest.assert_equals(msg, expected, actual) 
    # if expected != actual 
      # puts "#{caller[0]} #{msg}" 
      # puts "Expected: #{expected}" 
      # puts "  Actual: #{actual}" 
    # end 
  # end 

  def TestTest.assert_equals(*args)
    msg = args[0]
    expected = args[1]
    actual = args.length == 3 ? args[2] : yield

    if expected != actual
      puts "#{caller[0]} #{msg}"
      puts "Expected: #{expected}"
      puts "  Actual: #{actual}"
    end
  end

  def TestTest.run(clazz)
    instance = clazz.new
    # puts instance.methods.sort.join(" ") 
    cases = instance.methods.grep(/^test/)
    for c in cases do
      # puts c.inspect 
      # instance.c 
      instance.send(c)
    end
  end
end

class UnitTests
  def testStringLength
    TestTest.assert_equals("String.length failed", 3, "abc".length)
  end

  def testStringSubscript
    TestTest.assert_equals("String[] failed", 'c', "abc"[2])
  end

  def testStringFailed
    TestTest.assert_equals("String[] failed", 'f', "abc"[2])
  end

  def testStringConcatenation
    TestTest.assert_equals("String concatenation failed", 'blarp') do
      s = 'b'
      s += 'l'
      s += 'ar'
      s += 'p'
    end
  end
end

TestTest.run UnitTests

# tests = UnitTests.new 
# tests.testStringLength 
# tests.testStringSubscript 
# tests.testStringFailed 

Haiku