9 ms·
Radiation-hardened quine
- tomp 13y agoThis would be much easier to understand if GitHub had proper ruby syntax highlighting. Just yesterday I was testing this, it appears they use very simplistic algorithm for parsing Ruby string interpolation - probably just regexes, which cannot handle nesting. https://gist.github.com/tomprimozic/9113077 https://gist.github.com/tomprimozic/9113077
- samatman 13y agoIronically, Linguist+Pygments, the detection and highlighting engine, is a Ruby tool.
- halostatue 13y agoPygments is a Python tool, accessed through RubyPython* (for which I should really make sure it still works with Ruby 2.1 and maybe start trying to figure out how to make it work with Py3.) We have a few crashes that I can't figure out (but am putting in the test suite). * https://bitbucket.org/raineszm/rubypython/src https://bitbucket.org/raineszm/rubypython/src
- deleted 13y ago[deleted]
- dllthomas 13y agoFascinating exercise. "Deleting one character" seems a phenomenally unlikely outcome of radiation, though.
- ygra 13y agoA harder task might be "Randomly delete, add or mutate a single character". We had a few similar tasks on CGSE, e.g. • http://codegolf.stackexchange.com/q/4486/15 http://codegolf.stackexchange.com/q/4486/15 • http://codegolf.stackexchange.com/q/18087/15 http://codegolf.stackexchange.com/q/18087/15
- dllthomas 13y agoAddition and deletion anywhere but the end seems overwhelmingly unlikely.
- ygra 13y agoDepends on how the code is stored in memory ... with ropes addition or deletion anywhere could happen.
- dllthomas 13y agoTrue! But: 1) it's still less likely - most of the data is almost certainly characters of content, not sizes; 2) it's unlikely to be robust against flipped bits in pointers in the rope structures (even if implemented as indexes); and 3) there is no reason to expect it to be limited to one byte (if an addition or deletion happens, "more than one byte" is far more likely than "one byte").
- fnordfnordfnord 13y agoGranted it's not "deleting" a character but here, if you haven't seen it: https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1 https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_...
- dllthomas 13y agoThat seems to be a flipped bit, by far the most likely kind of problem due to radiation.
- foobarqux 13y agoCorrupting one bit is likely but if the rest of your system is not radiation hardened it isn't very helpful.
- dllthomas 13y agoYes, my objection wasn't that this failed to be a practical complete solution to radiation, but that there wasn't really a tie to radiation at all.
- TrainedMonkey 13y agoI agree, flipping random bit is more likely. I.E. mutating random character into some other random character (does not have to be printable one). This also has a pretty strong assumption that Ruby itself is not corrupted.
- throwaway_yy2Di 13y agoHard mode: flip bits in the interpreter's process memory as it's running.
- spoiler 13y agoExtreme mode: Run this code on an abacus.
- pavel_lishin 13y agoOlympic mode: while drunk.
- foobarqux 13y agoOr in the program counter or ALU, etc.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- Cthulhu_ 13y agoI can't read this code at all, but, does this code basically contain the same code twice, so if something from the first half is removed the second half saves it?
- joi_degn 13y agoI didnt look at the code and am not knowledgeable in this kind of coding but unless I am wrong, if the program simply would contain the same code twice each of these 2 codes would have to contain the same code twice ad infinitum.
- notimetorelax 13y agoIf we follow your reasoning than quine itself is not possible.
- hrjet 13y agoYes, Line 15: /#{eval eval if eval==instance_eval}}/.i rescue##/ They are checking the two instances and rescuing the corrupted one. But how exactly it works is beyond me.
- jonmrodriguez 13y agoAlso, in line 17, I think it's running whichever of the two codes is longer (since the longer one is the one that didn't have a byte deleted) eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##" See the max_by ... size part
- Schwolop 13y agoYes, and I was thoroughly disappointed by this result. So - new challenge: a radiation hardened quine in less than two times the characters of the equivalent non-radiation hardened version.
- hyborg787 13y agoExercise for the reader, make a quine that still works even if any one character is mutated (by 1 bit or 8?), rather than deleted.
- jxf 13y agoThat definitely wouldn't work with this strategy (two copies), because you wouldn't be able to tell which copy was the mutated one. Error-correcting codes to the rescue. :)
- ojii 13y agocouldn't one make 3 copies and take the two that are equal as non-modified?
- eklavya 13y agoSo like above said, error correction for at most one error.
- Guillaume86 13y ago2 copy + one hash could do the same job?
- th0ma5 13y agoI recommend reading specs for low power digital radio protocols like WSPR for ideas around basic error correction. Just something I did recently and was fun.
- jheriko 13y agoi wonder how far this can be taken... e.g. flipping or setting a random string of bits that would be physically contiguous in hardware as if a real neutron came smashing into the memory... if doing it during run can be achieved etc. how about a real native app with instructions? i'd never expect something as high level and wooly as ruby in systems that will be exposed to radiation. that's just asking for failure imo... how robust is the interpreter for instance?
- iliis 13y agoA friend of mine writes firmware for embedded devices like automatic door controls. Besides having very well designed and redundant hardware (multiple PSUs etc.) the software does a lot of things to keep itself running robustly. For example, the microcontroller regularly tests its own memory for bad blocks and compensates accordingly - similiar to what flash memory controllers do. So yeah, even if you don't go into space or inside a nuclear reactor software can be written to tolerate a lot of harware failures.
- jheriko 13y agothats interesting to know... i think you misunderstand me though. neutrons rain down on your hardware right now from deep space with significant energies... nuclear reactors aside. this is the primary reason afaik for things like ecc and encasing your hardware in boro-silicate glass...
- zefhous 13y agoHere's the google translate link to his blog post about it. My favorite part: "Ruby I terrible." http://translate.google.com/translate?sl=auto&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&u=http%3A%2F%2Fd.hatena.ne.jp%2Fku-ma-me%2F20140219 http://translate.google.com/translate?sl=auto&tl=en&js=n&pre...
- audunw 13y agoJapanese is Subject-Object-Verb order, so it was probably "My Ruby (is) terrible". But I don't know Japanese so I can't tell you for sure. Chinese would also drop the verb in this case, so I'm assuming they might do that in Japanese as well.
- ojii 13y agoRuby is the subject in that sentence, not sure why gtranslate injects an "I". I'd translate it as "Ruby is scary, isn't it?"
- iterion1 13y agoCould also be 'surprising'. With the context of the sentence before it is basically, "I thought this would be hard to write. Ruby is surprising." Also, the author is a contributor to ruby on github, so I doubt he is negative towards the language. http://jisho.org/words?jap=%E6%81%90%E3%82%8D%E3%81%97%E3%81%84&eng=&dict=edict http://jisho.org/words?jap=%E6%81%90%E3%82%8D%E3%81%97%E3%81...
- ojii 13y agoYes it's one of those "funny" words in Japanese that is highly context sensitive, so you're probably right.
- minikomi 13y agoYeah.. 恐ろしい is kind of a "Wondrous and terrifying" blend
- trapezoid 13y ago
- michaelmior 13y agoDepends on how you define "works." The program continues to output the original source code after the deletion, and ceases to be a quine. Still a very cool trick though :)
- lmkg 13y agoBut reverting to the original source gives the program a stability property that will maintain functionality through multiple generations. Outputting the modified source would cause the program to accrue errors over time, meaning eventually entropy would win.
- michaelmior 13y agoGood point :)
- zackmorris 13y agoInteresting! Does anyone know of a language or operating system that uses Reed–Solomon error correction on every file? https://en.wikipedia.org/wiki/Reed–Solomon_error_correction https://en.wikipedia.org/wiki/Reed–Solomon_error_correction Or to top that, imagine a computer where the entire memory space, perhaps shared with persistent flash memory, was encoded in this manner, so that even the filesystem was protected against bit flips. When I was doing Mac repair a few years back, the majority of the PowerMac G5s that came through the doors died premature deaths for two reasons: the ram was in a bad spot which caused the board to bend and crack on insertion, and the ram was non-ECC so it was notoriously difficult to isolate a bad ram chip. It was the most unreliable Mac I ever diagnosed, by perhaps an order of magnitude. Contrast that with the Mac Pro, which used ECC and was so much more reliable that I don't remember seeing a single Mac Pro fail in the 3 years I was there. Imagine how stable a Reed–Solomon computer would be..
- CraigJPerry 13y agoZFS (the file system) goes to some fairly extreme lengths to validate data. It effectively doesn't trust anything past the south bridge.
- usefulcat 13y ago> Does anyone know of a language or operating system that uses Reed–Solomon error correction on every file? A while back, after losing some personal photographs to bit rot, I became curious about this and did some experimentation with RS. The biggest drawback I found was that even with a relatively fast processor it is slow compared to typical disk read/write speeds. I concluded that the ZFS approach of RAID + checksums would be preferable.
- MaysonL 13y agoIn the early 1970's I implemented the driver for, and programs using, a digital videotape drive (IIRC, it incorporated an Ampex 2 inch reel-to-reel recorder, and used the sound track for positioning information). It used hardware Reed-Solomon error correction (IIRC, it was capable of correcting up to 11-bit errors). It stored a massive (for the time) database of scanned drawings for a number of aircraft maintenance manuals.
- NAFV_P 13y ago$ git clone the_quine $ cd the_quine $ ruby the_quine The program 'ruby' can be found in the following packages: * ruby1.8 * ruby1.9.1 # shit I don't have ruby $ sudo apt-get install ruby1.9.1 # 200 bytes/s, terrible # ... what's going on? Ah finally. $ touch output $ ruby rbquine.rb > output $ diff rbquine.rb output # nowt
- danslimmon 13y agoI was curious how well this quine would withstand having more than one character removed, so I performed a test. I did 1000 iterations removing 2 characters each time, then 1000 more removing 3 characters each time, and so on. Here are the results up to 23 removals: http://i.imgur.com/PwWN7Z7.png http://i.imgur.com/PwWN7Z7.png
- mdisraeli 13y agoNice, Love it when people actually perform experiments! :D In how many cases was the wrong output still functional?
- gojomo 13y agoNeat! Was each test of n random 1-character removals, or 1 removal of an n-character run?
- danslimmon 13y agoThe first one.
- p4bl0 13y agoNice! This reminds me of a work I did as an undergrad which landed in a paper called "Can a Program Reverse-Engineer Itself?". The idea is to take any program/function and make it a quine so you can retrieve its original code even if it has been obfuscated. You can find the paper here: http://pablo.rauzy.name/research.html#imacc11 http://pablo.rauzy.name/research.html#imacc11.
- heydenberk 13y agoIf you had asked me I might've said this was impossible.
- mey 13y agoWouldn't radiation flip a bit, rather than remove a character?
- yincrash 13y agosame author wrote a 50 language quine: https://github.com/mame/quine-relay https://github.com/mame/quine-relay
- NAFV_P 13y agoI looked at his git profile, I recognised the name: Yusuke Endoh - multiple IOCCC winner. Here is one of my favourites: http://www.ioccc.org/2012/endoh1/hint.html http://www.ioccc.org/2012/endoh1/hint.html