Chip: composable vector operations in Ruby.

.gitignore

/.yardoc
/.yardopts
/coverage
/doc

.ruby-version

2.0.0-p353

chip.shard.rb

require 'singleton'

#
# Composable function which takes any number of inputs and produces any number
# of outputs.
#
# Chips can be composed with {#&} or modified with {#shift}. Once composed, a
# chip can be invoked any number of times by using `#call`. `#call` takes one
# argument, an {::Array} containing the inputs, and returns an {::Enumerable} of
# the outputs.
#
#     chip         = Chip::Identity.instance.shift(2, true)
#     result       = chip.call([false, true, false]).to_enum
#
#     result.next  #=> true
#     result.next  #=> true
#     result.next  #=> false
#     result.next  #=> true
#     result.next  #=> false
#
# @abstract Subclasses must implement `#call(inputs)`.
#
class Chip

  class ResultBase
    include Enumerable
  end

  #
  # Chip that performs a bitwise AND on each of the corresponding outputs of two
  # other chips.
  #
  #     output[n] = input_1[n] && input_2[n]
  #
  class And < Chip
    class Result < ResultBase
      def each
        @a.zip(@b) { |input_a, input_b| yield input_a && input_b }
      end

      def initialize(chip, inputs)
        @a = chip.a.call inputs
        @b = chip.b.call inputs
      end
    end

    private_constant :Result
    attr_reader :a, :b

    #
    # Filters the inputs through both chips, returning the bitwise AND of the
    # results.
    #
    # @param inputs [Enumerable<Boolean>]
    # @return [Enumerable<Boolean>]
    #
    def call(inputs)
      Result.new self, inputs
    end

    def initialize(a, b)
      @a = a
      @b = b
    end
  end

  #
  # Chip that copies its inputs to its outputs unchanged.
  #
  #     output[n] = input[n]
  #
  class Identity < Chip
    include Singleton

    #
    # Returns `inputs` unchanged.
    #
    # @param inputs [Enumerable<Boolean>]
    # @return [Enumerable<Boolean>]
    #
    def call(inputs)
      inputs
    end
  end

  #
  # Chip that returns true for an output only if the corresponding input, and
  # all lower-numbered inputs, are false.
  #
  #     output[n] = !input[n] && !input[n - 1] && ... && !input[0]
  #
  class None < Chip
    include Singleton

    class Result < ResultBase
      def each
        none = true
        @inputs.each { |input| yield (none &&= !input) }
      end

      def initialize(inputs)
        @inputs = inputs
      end
    end

    private_constant :Result

    #
    # Returns a result where each output is true only if the corresponding
    # input, and all lower-numbered inputs, are false.
    #
    # @param inputs [Enumerable<Boolean>]
    # @return [Enumerable<Boolean>]
    #
    def call(inputs)
      Result.new inputs
    end
  end

  #
  # Chip that performs a left shift on its inputs. Outputs are copied from the
  # _nth_ previous input; the first _n_ outputs all return the `fill` value.
  #
  #     output[n] = input[n - count]  # n >= count
  #     output[n] = fill              # n < count
  #
  class Shift < Chip
    class Result < ResultBase
      def each
        i = @count
        while i > 0
          yield @fill
          i -= 1
        end
        @inputs.each { |input| yield input }
      end

      def initialize(chip, inputs)
        @count = chip.count
        @fill = chip.fill
        @inputs = chip.inner.call inputs
      end
    end

    private_constant :Result
    attr_reader :count, :fill, :inner

    #
    # Returns `inputs` shifted left by `count` places.
    #
    # @param inputs [Enumerable<Boolean>]
    # @return [Enumerable<Boolean>]
    #
    def call(inputs)
      Result.new self, inputs
    end

    def initialize(inner, count, fill)
      @count = count
      @fill = fill
      @inner = inner
    end
  end

  #
  # Build a chip representing the bitwise AND of this chip's outputs with the
  # `other` chip's outputs.
  #
  # @param other [Chip]
  # @return [And]
  #
  def &(other)
    And.new self, other
  end

  #
  # Build a chip representing the left shift of this chip's outputs by `count`
  # bits. The first `count` outputs will always equal `fill`.
  #
  # @param count [Fixnum]
  # @param fill [Boolean]
  # @return [Shift]
  #
  def shift(count, fill)
    Shift.new self, count, fill
  end

  #
  # Chip that returns true on only the output corresponding to the
  # lowest-numbered true input. For instance, if input 0 is false and input 1 is
  # true, output 0 will be false, output 1 will be true, and all higher-numbered
  # outputs will be false regardless of the value of their corresponding inputs.
  #
  Priority = None.instance.shift(1, true) & Identity.instance
end

chip_profile.rb

#!/usr/bin/env ruby -w

require_relative 'chip.shard'
require 'ruby-prof'

n_inputs = ARGV.fetch(0, 10).to_i - 1

inputs = [false, true]
samples = inputs.product(*([inputs] * (n_inputs)))
chip = Chip::Priority
results = nil

puts <<TXT
#########
#       #
# Setup #
#       #
#########

TXT

profile = RubyProf.profile do
  results = samples.map { |sample| chip.call sample }
end

RubyProf::FlatPrinter.new(profile).print(STDOUT, sort_method: :total_time)

puts <<TXT


##############
#            #
# Evaluation #
#            #
##############

TXT
profile = RubyProf.profile do
  results.each { |result| result.each { } }
end

RubyProf::FlatPrinter.new(profile).print(STDOUT, sort_method: :total_time)

chip_spec.rb

begin
  require 'simplecov'
rescue LoadError
else
  SimpleCov.start
end

require 'minitest/autorun'
require 'minitest/spec'

require_relative 'chip.shard'

describe Chip do
  let(:identity) { Chip::Identity.instance }
  let(:none)     { Chip::None.instance }

  describe Chip::And do
    subject    { chip.call([false, true, true, false]).to_a }
    let(:chip) { identity & identity.shift(1, false) }

    it 'false AND false is false' do
      subject[0].must_equal false
    end

    it 'false AND true is false' do
      subject[1].must_equal false
    end

    it 'true AND true is true' do
      subject[2].must_equal true
    end

    it 'true AND false is false' do
      subject[3].must_equal false
    end
  end

  describe Chip::Identity do
    subject    { chip.call([false, true]).to_a }
    let(:chip) { identity }

    it 'passes through false' do
      subject[0].must_equal false
    end

    it 'passes through true' do
      subject[1].must_equal true
    end
  end

  describe Chip::None do
    let(:chip) { none }

    describe 'with inputs [false, true, false, false]' do
      subject { chip.call([false, true, false, false]).to_a }

      it 'output 0 is true if input 0 is false' do
        subject[0].must_equal true
      end

      it 'output 1 is false if output 1 is true' do
        subject[1].must_equal false
      end

      it 'output 2 is false if output 1 is true' do
        subject[2].must_equal false
      end

      it 'output 3 is false if output 1 is true' do
        subject[3].must_equal false
      end
    end

    describe 'with inputs [true, false, false]' do
      subject { chip.call([true, false, false]).to_a }

      it 'output 0 is false if input 0 is true' do
        subject[0].must_equal false
      end

      it 'output 1 is false if input 0 is true' do
        subject[1].must_equal false
      end

      it 'output 2 is false if input 0 is true' do
        subject[2].must_equal false
      end
    end
  end

  describe Chip::Priority do
    let(:chip) { Chip::Priority }

    describe 'with inputs [false, true]' do
      subject { chip.call([false, true]).to_a }

      it 'output 0 is false if input 1 is false' do
        subject[0].must_equal false
      end

      it 'output 1 is true if input 1 is true' do
        subject[1].must_equal true
      end
    end

    describe 'with inputs [true, true]' do
      subject { chip.call([true, true]).to_a }

      it 'output 0 is true if input 0 is true' do
        subject[0].must_equal true
      end

      it 'output 1 is false if input 0 is true' do
        subject[1].must_equal false
      end
    end
  end

  describe Chip::Shift do
    subject    { chip.call([false, true]).to_a }
    let(:chip) { identity.shift(1, true) }

    it 'extends the result' do
      subject[0].must_equal true
    end

    it 'shifts the first input' do
      subject[1].must_equal false
    end

    it 'shifts subsequent inputs' do
      subject[2].must_equal true
    end
  end
end

All 1,048,576 possible combinations of 20 inputs to a Priority, processed in 1m20s. Each invocation of Chip::Priority.call results in 15 method calls: 10 to set up the result and intermediate Enumerables, and 3 to evaluate the expression. This gives a grand total of 15,728,640 method calls, excluding the test harness.

$ ruby chip_profile.rb 20
#########
#       #
# Setup #
#       #
#########

Thread ID: 70160665151200
Fiber ID: 70160402150740
Total: 20.477856
Sort by: total_time

 %self      total      self      wait     child     calls  name
  0.00     20.478     0.000     0.000    20.478        1   Global#[No method] 
  7.44     20.478     1.524     0.000    18.954        1   Array#map 
  9.48     18.954     1.941     0.000    17.013  1048576   Chip::And#call 
  7.94     17.013     1.626     0.000    15.388  3145728  *Class#new 
 15.24     15.388     3.121     0.000    12.266  1048576   Chip::And::Result#initialize 
  8.54     11.059     1.748     0.000     9.311  1048576   Chip::Shift#call 
 15.32      7.649     3.137     0.000     4.513  1048576   Chip::Shift::Result#initialize 
  8.62      4.513     1.765     0.000     2.748  1048576   Chip::None#call 
  6.24      1.278     1.278     0.000     0.000  1048576   Chip::None::Result#initialize 
  5.89      1.207     1.207     0.000     0.000  1048576   Chip::Identity#call 

* indicates recursively called methods


##############
#            #
# Evaluation #
#            #
##############

Thread ID: 70160665151200
Fiber ID: 70160402150740
Total: 58.657315
Sort by: total_time

 %self      total      self      wait     child     calls  name
  0.00     58.657     0.000     0.000    58.657        1   Global#[No method] 
  2.27     58.657     1.333     0.000    57.324  1048577  *Array#each 
  3.14     57.324     1.840     0.000    55.484  1048576   Chip::And::Result#each 
  2.79     55.484     1.636     0.000    53.848  1048576   Enumerable#zip 
  9.08     53.848     5.327     0.000    48.521  1048576   Chip::Shift::Result#each 
  4.05     48.521     2.377     0.000    46.144  1048576   Chip::None::Result#each 

* indicates recursively called methods