Merry Quine-mas

open("/dev/dsp","wb"){|h|s=%q{d=["-KQW[UZbgu*HNT+]TNOOOTZ+cZTUUUUUZbagmssUZbagm
ss+wmpgja+KQW[dfnu","-KEKOINV[W*HBH+QHBCCCHN+WNHIIIIINVU[aUUINVU[aUU+YOR[^I+KEK
OXZbW","-W[acg vsc*TZ`+eaaaaa--vucavuca+eadsvs+W[dgvrtc","-K991LIL77777dIIIII--
LKKILKKI+Mad[   ^U+K991LHJK"].map{|l|l.unpack("C*").map{|c|[(c/6-4)*12/7-8,"012
35b"[c%6,1].     hex]}*4};y=32.chr;l="@"+[(m="Jnx4sn3sgd1")+"vnqkc!6sgd2Lnqc4gz
r4bnld;6/Ld       s2dzqsg6qd2@bdhud6gdq2Khmf;77/Lds2du4@dqx4gdzqs6oqd2@ozqd4ghl
4qnnl,+Amc         2gdz++2   @udm   4z        mc      2gdz      4@+u   dm   2zm
c2mz+@stqd+r     hmf",m+"E    zq    sg  !6sgd2Sz  u4@h  nt  q4qd  hfm  r;  6/Ld
s2ldm6sgdhq       2rnmfr6d  l    2  @o       knx      ;77/      Wghkd2    ehdkc
r4zmc4eknn         cr,6qnb  jr  ,2  gh  kkr,4zmc  4okz  hm  r+Rd  2@odz  s+2+,6
qd2@odzs6           +sgd2r  ntmc+@  hm        f+  inx"  ,"  Nn4l  nqd3k  ds1rhm
r6zmc2rn             4@qqnvr4fqnv,6/Nnq2sgnqmr6hm2@edrs6sgd2fqntmc;77/Hd2bnldr4
sn4lzjd               6Hhr2ak    d4@rrh   mfr4eknv+Fzq2zr+2+,6ezq2zr,6+sgd2btqr
d+hr+entmc         ","Hd4qtkdr3s  gd1   vnqkc6vhsg2sqtsg4zmc4fqzbd,6/Amc2lzjdr6
sgd2mz6@s           hnmr2oqnud77/ T   gd2fk   n4@q   hdr4    ne6Hh       r2qhfg
s4@dntr4             @mdrr,+Amc2v   nm+2+6@    cd    qr,  2v  nm6  +@cdqr2ne+Hh
r+knud"               ].map{|a|   a ,b,c,e,  *    f  =a.  sp  lit"      +";[a,c
=b+c+f                 *"2",c   ,b+  e+f*"4  "+  ".  8/        /"]*"6/"  }.join
.tr("                   a-z   /","b-    za\  n").gs  ub  (/^/  ,"       #"<<32)
;c=0;640.tim     es{|w|c<1&&(l=~/(@)?(.*?)(\d)/m;($>.<<$1?$2:y+$2).flush;l=$';c
=eval$3);c-=     1;a=[128]*z=1200;4.times{|j|t,n=d[j].pop;f=0.3456*2**(t/12.0-j
/2);(n>0?(d[     j]<<[t,n-1];z):800).times{|i|t>-3&&a[i]+=16*Math.sin(f.*w*z+i)
}};(h.<<a.pack"C*").flush};puts(s.gsub(/./){"!">$&?"#":y}+%(\nopen("/dev/dsp#{"
(c)Y.Endoh2009";'",'}"wb"){|h|s=%q{#{s}};eval(s.split*"")}))};eval(s.split*"")}

Run it under environment where /dev/dsp is available. If you are windows user, you can use cygwin. It often abends on cygwin. Please re-run it until it works.

The structure of the program:

• Lines 1-4: encoded musical score data
• Lines 4-5: score decoder
• Lines 5-17: crypted compressed lyrics data (with timing data)
• Lines 17-19: lyrics decompressor
• Lines 20-21: lyrics player
• Lines 21-23: wave synthesizer
• Lines 23-24: quine

translated from mamememo in Japanese (2009-12-24).

qng and qif: self-reproducing images

qng image

The above image is qng, a png image that prints a Ruby script that generates the image itself.

$ cat qng.rb
eval s=%q(require"zlib";include Zlib;f=Inflate.inflate(*"eNq
1VomxQyEIpAP675IOiAjqIvqS/INh3hh1dTkN0c+FOfR5j6r4Nh98cT6xSIf
Yl4WEfi92mn1Q7WCOxRijCiXWjUfjo/Y9MBLTZqkP3sh2chfDfiKSrxxUcRg
Wa6dsfMUHbSZxkAAGHFYd202KM5EerlI9uQHU4i499MPXy0yJA0/YdR1Vzp3
DbjIVe/mEhclA8rdpJU/hexb33qch/hNxK71Uh+3AJ2ZwUHw1UyNHwX6P1LI
SJTQL4yslc+qq0OleFggW1F9QlTlGLN3zmVS2ZbTXrZCezjKsy45MqoWVsmk
I+rktkSxh05qTU3O2Y4xuvppRSL6q8d185X7mUw2uJoZaonDkvCb9gajY6Yn
yiEyg5+3GOV1XWK3OIHu/Yt37eqiu4K7nIP3oe07glFr/KR4g1lQLkIdYFBW
7ShhyI+ZYMYJS7x2FBtj2jnt3zy49YrHZsp45S04Ow16yLq4p4dD0pvek8qY
3wCynAi5tWBmrVEr3vnA+2EsP2FnIOUbJV+mBV2sgF8oRX8+Q1L1Heq8Alfj
m+j2vrhKuq1DCdRVL+N29pfOMEl49lqGlY/bzpTuDv/b9cvjbcJMXSB2OYQ=
=".unpack("m"));z="\0";s="IDAT"+Deflate.deflate(z*561+%(eva\
l s=%q(#{s})).scan(/.+/).map{|l|(0..9).map{|i|[z*4,l.bytes .
map{|c|f[c*30+i*3-960,3]},z*3]}*""}*(z*187)+z*561);print ["\
\x89PNG\r\n\x1a\n","\rIHDR",372,192,4,0,4107545177,s.size-4,
s,Zlib.crc32(s),0,"IEND\xAEB\x60\x82"].pack"a11A*NNCN3A*NNA*
"############## qng.rb (c) Yusuke Endoh 2009 ##############)

$ ruby qng.rb > qng.png

qif image

The above image is qif, a gif image that prints a Ruby script that generates the image itself.

$ cat qif.rb
Y,E=%q~260|0!e0*h0($0j0($"!e0($"f0e0($0!e0*p;4f4#.q9!&8*%"1(
}+0!,e4|8,e<.%}e6#g4*};!(4*%})2!e09$"u91&(#6}f0(%+#u0)6"1(7,
v0.,*%"<8{9!(4+2}!(4*%90}<.'#<(}$"!e0($")n48$6!(0($".!e0($"$
e0w0($")k0r4*%"<8$"!9!&8*%"<0|0($"#&0()0i;f=87$};!(4+6"!e0j;
f0(',}91(4+3e0($j;!.8)2}}}}}}},4"!e0($"!2i2!i0)e0e0(#$0($"!e
0(,0}}o0(%2"1(4~,%~y;0('&!e=8}}q9!($"!"<0}}}}}}y0g4f0+2}441$
!}g;0&<}h2$11!{0!q0}h0m0|20!&8*%9s9!(7$%"<0p0!e4"g3.q9!(7&!(
(0o9!(3&!e=8o0(&>#01(t9!(2$$"<0o;0*"$$"<0o9e0($")e0o9!(4.%"<
0n4"g0*!h0(o0}}k;0{0!}}g0+."!}f0?$'!t0!($"!e0e2i0e2!e0($f4}t
0($k=!-%%!040r70&8!;}%3#,0/,"r8->#!78}z8,&s0g0($"!g~;eval$s=
%q(h=eval"0b"+(Y+"}"*39+E).bytes.map{|x|x<95?("%05b".%x-32if
32<x):"0"*(x-96)}*"";z=[2,128].pack"vC";print [71,73,70,"89\
a",372,192,736,0,0,65535,11519,0,0,372,192,768,z*372,%(Y,E=\
%q~#{Y}~,%~#{E}~;eval$s=\n%q(#$s)).scan(/.+/).map{|l|(0..9).
map{|i|[z*2,l.bytes.map{|c|[4,17&n=h>>60*c-1980+i*6,17&n>>1,
n[2]+n[3]*16,136].pack "C*"},z*2]}*""}*(z*124),z*372,"\0;"].
pack"C3a3v12"+"a*"*4 #### qif.rb (c) Yusuke Endoh 2009 ####)

$ ruby qif.rb > qif.gif

COPYRIGHTS

The two images contain Proggy Programming Fonts:

Copyright (c) 2004, 2005 Tristan Grimmer

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

translated from mamememo in Japanese (2009-07-23) and (2009-11-16).

_ : a library that allows you to write Ruby script by using only _

I published one of my darling libraries into gemcutter, named _. By using _, you can write Ruby script that consist only of _.

Getting started

$ gem install _

Source code: http://github.com/mame/_

Gem info: http://gemcutter.org/gems/_

Example

This is "Hello, world!" __script__ written in Ruby:

require "_"
____ _ _____ ____ __ ____ ____ __ ___ ____ __ __ _ ______
_____ ___ _ _ ___ _____ ______ ____ _ _ ____ _ _ ____ _
____ __ __ ___ _ ______ ___ ____ __ ______ ____ _ ____ ____
__ _ ____ _ _ ___ _____ _____ _ ______ ____ _ ______ _____

This is nothing but normal Ruby __script__. Works on Ruby 1.8 and 1.9. You can rearrenge line breaks but can not change the order of _s.

$ ruby18 -rubygems __hello__.rb
Hello, world!

$ ruby19 __hello__.rb
Hello, world!

If you mind the first `require' line, the option `-r_' can be used in Ruby 1.9.

$ ruby19 -r_ -e '____ _ _____ ____ __ ____ ____ __ ___ ____ __
__ _ ______ _____ ___ _ _ ___ _____ ______ ____ _ _ ____ _ _
____ _ ____ __ __ ___ _ ______ ___ ____ __ ______ ____ _ ____
____ __ _ ____ _ _ ___ _____ _____ _ ______ ____ _ ______ _____
'
Hello, world!

And, you can translate your own script into __script__ by __script__ method.

$ echo -n 'puts"Hello, world!"' | ruby19 -r_ -e 'puts __script__($<.read)'
require "_"
____ _ _____ ____ __ ____ ____ __ ___ ____ __ __ _ ______
_____ ___ _ _ ___ _____ ______ ____ _ _ ____ _ _ ____ _
____ __ __ ___ _ ______ ___ ____ __ ______ ____ _ ____ ____
__ _ ____ _ _ ___ _____ _____ _ ______ ____ _ ______ _____

translated from mamememo in Japanese (2009-04-02) and (2009-11-15).

enumerabler.rb: Enumerable lazy-version method library

When you want to gather first ten even numbers from an integer array, what do you do?

ary.select {|x| x.even? }.take(10)

The above program is very simple. But it may cause a lot of unnecessary checks when array is big. Also, `select' creates intermediate array.

ret = []
ary.each do |x|
  ret << x if x.even?
  break if ret.size == 10
end

This will stop the loop when enough even numbers is found, and create no unnecessary array. But, it has trouble with readability and maintainability because it is very dirty, cumbersome, tricky, too long and too primitive. We live in the age of Ruby 1.9. We need more elegance.

"We can use Enumerator and `to_enum' in Ruby 1.9!"

It's a good idea, but you are unfortunate.

(1..50).to_enum(:select) {|x| x.even? }.take(10)
  #=> [1,2,3,4,5,6,7,8,9,10]  # never selected!

Please think yourself the reason why it does not work. `to_enum' is too difficult for me, to explain in English :-p

No matter how you combine `to_enum' and `select', it will never work, I guess. You can (must) use Enumerator.new without using Enumearble#select:

module Enumerable
  def selector(&blk)
    Enumerator.new do |e|
      each do |x|
        e << x if blk[x]
      end
    end
  end
end

Also troublesome...

proposed `enumerabler.rb'

I wrote a library, named enumerabler.rb, which is a collection of the above method definitions.

require "enumerabler"

ary.selector {|x| x.even? }.take(10)

You use `selector' instead of `select.' While `select' returns an array, `selector' returns an Enumerator corresponding the array. Because of Enumerator, the evaluation is delayed. So, the above program using `selector' is not only simple but also effective, which will stop its loop as soon as ten even numbers is found. No intermediate array.

enumerabler.rb defines:

• Enumerable#grepper
• Enumerable#finder_all (alias: all_finder, selector)
• Enumerable#rejecter
• Enumerable#collector (alias: mapper)
• Enumerable#flat_mapper (alias: concat_collector)
• Enumerable#zipper
• Enumerable#taker
• Enumerable#taker_while
• Enumerable#dropper
• Enumerable#dropper_while

All of them returns corresponding Enumerator. In an aside, I cannot distinguish -er and -or without a dictionary.

"Does it use a Fiber? Isn't it slow?"

No, enumerabler.rb does neither generate nor yield a Fiber. Trust me. If you worry, please read and check the source code of Ruby!

However, it is actually slow because it calls Proc frequently. `selector' is about two or three times slower than the original `select', but it is faster than a Fiber, and actually reduces memory usage.

Examples

p ary.selector {|x| x.even? }.taker(100).take_while {|x| x >= 0 }

gathers first 100 even numbers, however terminates before the negative element, without unnecessary check and intermediate array.

require "enumerabler"

def sieve(e, &blk)
  yield n = e.first
  sieve(e.rejecter {|x| x % n == 0 }, &blk)
end

sieve(2..(1.0/0.0)) {|x| p x } #=> 2, 3, 5, 7, 11, 13, 17, 19, 23, ...

Sieve of Eratosthenes using `rejecter.'

require "enumerabler"

def fibonacci
  Enumerator.new do |e|
    e << 1
    e << 1
    fibonacci.zip(fibonacci.dropper(1)) {|x, y| e << x + y }
  end
end

fibonacci.each {|x| p x } #=> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Fibonacci numbers. `dropper' can drop an infinite sequence. Note that this is very slow because of call-by-name evaluation and because `zip' internally uses a Fiber.

how to install

$ gem install enumerabler

http://github.com/mame/enumerabler

translated from mamememo in Japanese (2009-11-11).

Piet Quine

$ ../npiet-1.1/npiet quine.gif > quine2.gif
$ diff quine.gif quine2.gif

translated (?) from mamememo in Japanese (2009-10-06).

Piet is Turing-complete

I proved Turing-completeness of the programming language Piet by defining a translation from brainfuck to Piet.

translation approach

1. Correspond brainfuck's tape and piet's stack.

• The top of the piet's stack must equal to the value that the brainfuck's pointer indicates.
• The second top must equal to current index of pointer, plus 3.
• The third top must equal to total length of the whole tape, plus 3.
• The remain part of the stack must equal to data of type except the value on the current pointer.

For example, the following brainfuck's tape:

+---+---+---+---+---+---+
| A | B | C | D | E | F |
+---+---+---+---+---+---+
              ^
           pointer

corresponds to the following piet's stack:

(top) D 6 9 A B C E F (bottom)
 where 6 is current index of pointer + 3
       9 is total length of tape + 3

2. Define auxiliary functions.

pick(n): push the n-th top value of the stack.

(top) A B C D E F (bottom)
 |
 | pick(3)
 v
(top) D A B C D E F (bottom)

deposit: insert the top value to the n-th index

(top) D 6 9 A B C E F (bottom)
 |
 | deposit
 v
(top) 6 9 A B C D E F (bottom)

withdraw: pull the n-th value to the top (inversion of deposit)

(top) 5 9 A B C D E F (bottom)
 |
 | withdraw
 v
(top) C 5 9 A B D E F (bottom)

definitions:

pick(0) = dup
pick(n) = push(n+1); push(-1); roll; dup; push(n+2); push(1); roll
deposit: pick(1); push(1); roll
withdraw: dup; push(-1); roll

3. Put initializer of the piet's stack.

initial state of the stack:

(top) 0 3 3 (bottom)

4. Put piet's instractions correspoinding to each brainfuck's instruction.

+: push(1); add
-: push(1); sub
>: deposit
   if (the second top value) > (top value)
     # extend tape
     # (top) 9 9 A B C D E F (bottom)
     # |
     # | extend
     # v
     # (top) 0 10 10 A B C D E F (bottom)
     pop; push(1); add; dup; push(0)
   else
     push(1); iadd; withdraw
   end
<: deposit; push(1); sub; withdraw
[: if (top value) * 2 <= 0
     jump the corresponding ']'
   end
]: jump the corresponding '['
,: pop; in(char)
.: dup; out(char)

Of course, branches and jumps are represented by "greater", "switch" and "pointer". Note that the piet's stack is not required to hold arbitrarily long number.

5. Put a terminator of execution.

See Piet Speficication.

full implementation

http://github.com/mame/piet-misc/blob/master/bf2piet.rb

example

An echo program written in brainfuck

,[.,]

is translated to the following Piet program:

$ ruby19 bf2piet.rb echo.bf > echo.piet.png

You can see ',', '[', '.', ',' and ']' above each corresponding sequence of instructions.

$ echo foobar | ../npiet-1.1/npiet -q echo.piet.png
foobar

You can also see hello.piet.png which is translated from brainfuck's Hello world!

$ ../npiet-1.1/npiet hello.piet.png
Hello, world!

And now, we can obtain brainfuck interpreter written in Piet, by translating Keymaker's brainfuck interpreter written in brainfuck!

$ ruby19 bf2piet.rb -c 1 kbfi.b > kbfi.piet.png
$ time ../npiet-1.1/npiet -q kbfi.b < hello.bf
Hello, world!
real    2m35.729s
user    2m35.342s
sys     0m0.128s

conclusion

Given a stack of unlimited size, Piet is Turing-complete. It does not require the stack holding arbitrarily long number.

translated from mamememo in Japanese (2009-09-25).

English blog

I write a blog in English. Main contents will be translations from some favorite entries of mamememo in Japanese.

One of the purpose of this blog is English practice. So, please point my Engrish! :-)