tag:blogger.com,1999:blog-127531022024-03-28T15:41:38.468-04:00Ben's JournalA random collection of thoughts, comments and photos from Ben Simon.Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.comBlogger130125tag:blogger.com,1999:blog-12753102.post-49553123306670454132019-07-17T16:45:00.000-04:002019-07-17T16:45:01.943-04:00Don't Fear the x, and other lessons from Shamir Secret Sharing<p>
Consider these facts about this 3rd degree polynomial:</p>
<pre>
f(x) = 1822 + 3x + 19x<sup>2</sup> + 2x<sup>3</sup>
</pre>
<p>
<b>Fact 1.</b> This is considered a 3rd degree polynomial because <A href='https://www.mathsisfun.com/algebra/degree-expression.html'>the largest exponent value is 3</a>. While looking at this equation gives me a burst of High School Math PTSD, it need not. Upon further reflection, it's just a bit of terse code. I could program the above as:</p>
<pre>
(define f (lambda (x)
(+ 1822
(* 3 x)
(* 19 (expt x 2))
(* 2 (expt x 3)))))
</pre>
<p>
Because all polynomials have the same shape, it's easy to make a function that generates polynomials:</p>
<pre>
(define (make-poly coeffs)
(lambda (x)
(let loop ((coeffs coeffs)
(i 0)
(sum 0))
(cond ((null? coeffs) sum)
(else
(loop (cdr coeffs)
(+ i 1)
(+ sum (* (car coeffs) (^ x i)))))))))
</pre>
<p>
With this 'make' function, I can replace the above code with the following:</p>
<pre>
(define f (make-poly '(1822 3 19 2)))
</pre>
<p>
I can call <tt>f</tt> with as many values of <tt>x</tt> as I wish:</p>
<pre>
> (for-each (lambda (x) (show (cons x (f x)))) (range 0 10))
((0 . 1822))
((1 . 1846))
((2 . 1920))
((3 . 2056))
((4 . 2266))
((5 . 2562))
((6 . 2956))
((7 . 3460))
((8 . 4086))
((9 . 4846))
((10 . 5752))
</pre>
<p>
<b>Fact 2.</b> Evaluating a polynomial at <tt>x = 0</tt> always returns the value of the first constant term. We see this above, as 0 maps to 1822. This will continue to hold true no matter how ugly and complex the polynomial is.</p>
<p><b>Fact 3.</b> Using <a href='https://en.m.wikipedia.org/wiki/Lagrange_polynomial'>Lagrange Interpolating polynomials</a> we can use <tt><i>degree</i> + 1</tt> values of a polynomial to construct a function which will return values equivalent to the original polynomial. That is, if we feed any four values above into <tt>make-lagr-poly</tt> we end up with a new function <tt>fg</tt> which computes the same values as <tt>f</tt>.</p>
<pre>
(define fg (make-lagr-poly '((3 . 2056)
(6 . 2956)
(7 . 3460)
(10 . 5752))))
> (for-each (lambda (x) (show (cons x (fg x)))) (range 0 10))
((0 . 1822))
((1 . 1846))
((2 . 1920))
((3 . 2056))
((4 . 2266))
((5 . 2562))
((6 . 2956))
((7 . 3460))
((8 . 4086))
((9 . 4846))
((10 . 5752))
</pre>
<p>
The how and why of <a href='http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html'>Lagrange polynomials</a> will have to wait for another blog post. But for now, trust me that this bit of math-magic works.</p>
<p>
Cryptographer <a href='https://en.wikipedia.org/wiki/Adi_Shamir'>Adi Shamir</a> combined the above facts to create something quite useful: a way to securely share a secret among a group.</p>
<p>
Consider this problem:</p>
<blockquote>
You need to distribute a vault code to bank executives, however you'd like to avoid a number of pitfalls. For one, you want to make sure that a single lost or stolen code doesn't allow an attacker into the vault. You'd also like to insure that at least 4 executives need to agree on the requirement of opening the vault before it can be accessed. This reduces the chances that a small number of executives will coordinate to steal from the vault.
</blockquote>
<p>
Shamir used the above math to create <a href='https://en.m.wikipedia.org/wiki/Shamir%27s_Secret_Sharing'>Shamir Secret Sharing</a>. Here's how it works. First, note your secret, which in this case is the vault code. We'll use <a href='https://www.youtube.com/watch?v=a6iW-8xPw3k'>12345</a> as our code. Then decide on your threshold, that is the number of executives that are required before the secret can be revealed. We'll use 4 as suggested above. Finally, decide on how many shares you want to give out. Let's assume there are 10 executives, so we'll generate 10 shares.</p>
<p>
Step one is to form a polynomial of <tt>threshold - 1</tt> degree, where the first term is the secret:</p>
<pre>
;; values 4, 19 and 103 are random numbers, and should be
;; generated in a secure and truly random way.
(define secret (make-poly '(12345 4 19 103)))
</pre>
<p>
Step two is to generate the 10 shares, one for each executive:</p>
<pre>
> (for-each (lambda (x) (show (cons x (secret x)))) (range 1 10))
((1 . 12471))
((2 . 13253))
((3 . 15309))
((4 . 19257))
((5 . 25715))
((6 . 35301))
((7 . 48633))
((8 . 66329))
((9 . 89007))
((10 . 117285))
</pre>
<p>Note how we start <tt>x</tt> at 1 and not 0. Calling this function with 0 reveals our secret.</p>
<p>
We give each pair of numbers to an executive and instruct them to keep the pair private. If an attacker obtains less than 4 shares, then the secret remains safe and no clues about the it are revealed.</p>
<p>
When the vault needs to be opened, 4 executives pool their shares to calculate a function equivalent to the original polynomial:</p>
<pre>
(define soln (make-lagr-poly '((1 . 12471)
(5 . 25715)
(9 . 89007)
(10 . 117285))))
</pre>
<p>
Finally, to derive the secret we pass 0 to the solution function:</p>
<pre>
> (soln 0)
12345
</pre>
<p>
While the above implementation captures the essence of Shamir Secret Sharing, it's missing an important step to make it truly secure. I may cover that in a future post.</p>
<p>
I had two takeaways from my experience implementing Shamir Secret Sharing. First, it's fascinating to see how mathematical properties can be combined to solve everyday problems</p>
<p>And Second, I found the math behind this scheme to be initially quite overwhelming. I struggled to both understand the mathematical notation, as well as how to convert it to code. And then it hit me: I've got a programming language that let's me directly implement polynomial and Lagrange interpolations functions; I don't need to think of them as purely symbolic expressions like so many of the examples on the web do. Putting this in terms of code and not math made all the difference for me.</p>
<p>What a joy it was to untangle what initially appeared to be so complex.</p>
<p>
Find my implementation of Shamir Secret Sharing <a href='https://github.com/benjisimon/code/blob/master/sss/main.ss'>here</a>. Find the original paper by Adi Shamir <a href='https://www.cs.tau.ac.il/~bchor/Shamir.html'>here</a>. Enjoy!</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com2tag:blogger.com,1999:blog-12753102.post-49838953004390033122018-04-27T17:30:00.000-04:002018-04-27T17:30:09.600-04:00Elise Four - Strong, Human Powered, Encryption<p>
<i>If you want to understand a subject, teach it to someone. If you want to truly and completely understand a subject, teach it to a computer. That is, program it.</i></p>
<p>
This idea of coding to reach understanding is a lesson I've learned countless times. Most recently, I experienced this adage while tackling the <A href='https://programmingpraxis.com/2018/03/27/elsie-four/'>Elise Four exercise</a> from Programming Praxis. The task was to implement the <A href='https://eprint.iacr.org/2017/339.pdf'>EliseFour (aka, LC4) Encryption Algorithm</a>. This approach to encryption is especially interesting because of its competing goals. First, it attempts to provide for strong encryption. Secondly, it's designed to be run offline by human power alone. (Not unlike <A href='http://www.blogbyben.com/2014/12/trigraphs-diana-pads-and-zombies.html'>this solution</a>)</p>
<p>
See the contradiction there? All the tools one thinks of when considering strong encryption, such as terrifically hard calculations and massively large numbers, are off the table. LC4 therefor has to choose clever conventions over raw processing power. The author solves this challenge by constructing a grid of Scrabble-like tiles and re-arranging them using a simple set of rules. While I'm interesting in implementing an offline version of the algorithm, for now, I've coded the algorithm in Scheme.</p>
<p>
Here's the algorithm at work:</p>
<pre>
;; Example 1
Key: xv7ydq #opaj_ 39rzut 8b45wc sgehmi knf26l
Nonce: solwbf
Text: im_about_to_put_the_hammer_down
Encrypted: i2zqpilr2yqgptltrzx2_9fzlmbo3y8_9pyssx8nf2
Decrypted: im_about_to_put_the_hammer_down#rubberduck
;; Example 2
Key: xv7ydq #opaj_ 39rzut 8b45wc sgehmi knf26l
Nonce: argvpx
Text: hurrrraaaaaaaaaaaaaaaaaaaaaay
Encrypted: 3bcxnt57hus6accn97v4iie__hjbml8wr
Decrypted: hurrrraaaaaaaaaaaaaaaaaaaaaay#ben
</pre>
<p>
The source code for my solution can be found <A href='https://github.com/benjisimon/code/blob/master/programming-praxis/lc4.scm'>in the usual spot</a>.</p>
<p>
Example 1 comes directly from the <a href='https://eprint.iacr.org/2017/339.pdf'>paper describing the algorithm</a> and was my lifeline for implementing and verifying the algorithm. You can see that to communicate with the LC4 algorithm, both users need to know the key value ahead of time. The key will always be an arrangement of the 36 different characters in the alphabet.</p>
<p>
Encryption and decryption also depend on a nonce value, which is used to add additional noise into the system. The nonce value is to be shared with the recipient, and no harm comes from it being exposed to an attacker.</p>
<p>
Example 2 emphasizes that even text with a telling shape comes out as random gibberish when encrypted; a sign that his is indeed a secure algorithm.</p>
<p>
LC4 is an elegant solution to an unusual encryption challenge. On one level, I knew this by browsing the <A href='https://eprint.iacr.org/2017/339.pdf'>source paper</a> on the topic. But now that I've struggled through an implementation, I know this on a completely different level. And when I say struggle, I mean it. Encryption algorithms are tricky to implement because the goal is to take text and turn it into garbage, but very specific garbage. So when I had variable <tt>c</tt> where <tt>y</tt> belonged, or neglected to reset <tt>r</tt> and <tt>y</tt> the algorithm still produced jumbled text, but it was the wrong jumbled text.</p>
<p>
At least four times I was absolutely sure I had coded the encryption and decryption algorithm exactly as described, yet my code was failing. I did what any smart programmer does in these situations: I stepped away and re-attacked the problem after some rest. With some time away from the code, the bugs were obvious and easy to address.</p>
<p>
When I finished coding the algorithm I had far more than just working code. I had an intimate appreciation for key generation, nonce usage, dictionary selection, authentication operation and a half dozen other subtle details that work together to make LC4 function. Oh, and the dopamine rush from seeing my text get encrypted and then decrypted was nice too.</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-27940480362134666922018-04-24T14:16:00.002-04:002018-04-24T14:16:29.566-04:00Lightweight, R7RS Compliant and in palm of my hand - Compiling chibi-scheme on Android <p>
I'm eyeing <A href='https://programmingpraxis.com/2018/03/27/elsie-four/'>this Programming Praxis exercise</a> as one to tackle next but there's a catch before I can start programming. <A href='http://www.blogbyben.com/2018/04/a-little-scheme-setup-and-development.html'>TinyScheme</a>, my current Scheme Interpreter of choice, doesn't have support for generating random numbers, and the exercise requires this.</p>
<p>
I could hack something together using TinyScheme (and probably the <a href='https://programmingpraxis.com/contents/standard-prelude/'>Programming Praxis Standard Prelude)</a>. Or, I could do as <A href='https://www.blogger.com/profile/11452247999156925669'>John Cowen</a> suggested, and try out a different implementation. He suggested <a href='https://github.com/ashinn/chibi-scheme'>Chibi-Scheme</a>. Chibi Scheme is lightweight, but unlike TinyScheme, it's also quite modern. This means, among other things, it should give me easy access to the <A href='https://srfi.schemers.org/srfi-27/srfi-27.html'>SRFI-27: Sources of Random Bits</a> library. Longer term, it would be ideal to have access to R7RS features and other modern niceties.
</p>
<p>
I busted out my cell phone and hardware keyboard. I opened up Termux and went to work. Here's my attempt at getting chibi-scheme running on Android:</p>
<pre><span style='color: #009d0b; font-weight: bold'>Let's be clever and build this on the SD card.</span>
<span style='color: #333; font-weight: bold'>[localhost]{~}(1)$ cd storage/external-1/src</span>
<span style='color: #333; font-weight: bold'>[localhost]{src}(1)$ git clone https://github.com/ashinn/chibi-scheme.git</span>
Cloning into 'chibi-scheme'...
remote: Counting objects: 18101, done.
remote: Compressing objects: ....
Receiving objects: 100%
Resolving deltas: 0%
<span style='color: #333; font-weight: bold'>[localhost]{src}(1)$ cd chibi-scheme</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ ./configure</span>
bash: ./configure: /bin/sh: bad interpreter: Permission denied
<span style='color: #009d0b; font-weight: bold'>D'oh. OK, don't panic.</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ sh configure</span>
Autoconf is an evil piece bloatware encouraging cargo-cult programming.
Make, on the other hand, is a beautiful little prolog for the filesystem.
Just run 'make'.
<span style='color: #009d0b; font-weight: bold'>Oooh, sassy software. I like it.</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ make</span>
The program 'make' is not installed. Install it by executing:
pkg install make
<span style='color: #009d0b; font-weight: bold'>No problem, I'll just do what Termux tells me to do...</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ pkg install make</span>
Building dependency tree...
Reading state information...
All packages are up to date.
The following packages were automatically installed and are no longer required:
binutils libandroid-support-dev libffi libllvm ndk-stl ndk-sysroot
Use 'apt autoremove' to remove them.
The following NEW packages will be installed:
make
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 76.5 kB of archives.
After this operation, 246 kB of additional disk space will be used.
Get:1 https://termux.net stable/main aarch64 make aarch64 4.2.1 [76.5 kB]
Preparing to unpack .../make_4.2.1_aarch64.deb ...
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ make</span>
echo '#define sexp_so_extension "'.so'"' > include/chibi/install.h
echo '#define sexp_default_module_path "'/data/data/com.termux/files/usr/share/chibi:/data/data/com.termux/files/usr/lib/chibi'"' >> include/chibi/install.h
echo '#define sexp_platform "'android'"' >> include/chibi/install.h
echo '#define sexp_version "'0.8.0'"' >> include/chibi/install.h
echo '#define sexp_release_name "'`cat RELEASE`'"' >> include/chibi/install.h
cc -c -Iinclude -Wall -g -g3 -O3 -o main.o main.c
make: cc: Command not found
make: *** [Makefile:149: main.o] Error 127
<span style='color: #009d0b; font-weight: bold'>Whoops. No compiler. After attempts to install 'gcc' and search for a compiler</span>
<span style='color: #009d0b; font-weight: bold'>package in general I finally tripped over 'clang.' That will apparently install</span>
<span style='color: #009d0b; font-weight: bold'>a C compiler.</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ pkg install clang</span>
The following NEW packages will be installed:
clang
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 12.9 MB of archives.
After this operation, 61.2 MB of additional disk space will be used.
Get:1 https://termux.net stable/main aarch64 clang aarch64 6.0.0-1 [12.9 MB]
Preparing to unpack .../clang_6.0.0-1_aarch64.deb ...
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ make</span>
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o main.o main.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o gc.o gc.c
<span style='color: #009d0b; font-weight: bold'>It's working! It's really working!</span>
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o sexp.o sexp.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o bignum.o bignum.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o gc_heap.o gc_heap.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o opcodes.o opcodes.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o vm.o vm.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o eval.o eval.c
cc -c -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -fPIC -o simplify.o simplify.c
cc -fPIC -shared -Wl,-soname,libchibi-scheme.so.0 -o libchibi-scheme.so.0.8.0 gc.o sexp.o bignum.o gc_heap.o opcodes.o vm.o eval.o simplify.o -ldl -lm
ln -sf libchibi-scheme.so.0.8.0 libchibi-scheme.so.0
ln: libchibi-scheme.so.0: Operation not permitted
make: *** [Makefile:162: libchibi-scheme.so.0] Error 1
<span style='color: #009d0b; font-weight: bold'>And it broke. Ugh. After a much debugging I realized that my issue</span>
<span style='color: #009d0b; font-weight: bold'>was permission based. Apparently Android doesn't allow you to perform</span>
<span style='color: #009d0b; font-weight: bold'>certain operations on your SD card. I moved the source tree to internal </span>
<span style='color: #009d0b; font-weight: bold'>storage and tried again.</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ cd ..</span>
<span style='color: #333; font-weight: bold'>[localhost]{src}(1)$ mv chibi-scheme ~/</span>
<span style='color: #333; font-weight: bold'>[localhost]{src}(1)$ cd</span>
<span style='color: #333; font-weight: bold'>[localhost]{~}(1)$ cd chibi-scheme</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ make</span>
ln -sf libchibi-scheme.so.0.8.0 libchibi-scheme.so.0
ln -sf libchibi-scheme.so.0 libchibi-scheme.so
<span style='color: #009d0b; font-weight: bold'>It's working again. Whooo!</span>
cc -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o chibi-scheme main.o -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/filesystem.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/filesystem.so lib/chibi/filesystem.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/weak.so lib/chibi/weak.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/heap-stats.so lib/chibi/heap-stats.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/disasm.so lib/chibi/disasm.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/ast.so lib/chibi/ast.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/emscripten.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/emscripten.so lib/chibi/emscripten.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/process.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/process.so lib/chibi/process.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/time.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/time.so lib/chibi/time.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/system.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/system.so lib/chibi/system.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/stty.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/stty.so lib/chibi/stty.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/net.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/net.so lib/chibi/net.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/io/io.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/io/io.so lib/chibi/io/io.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/optimize/rest.so lib/chibi/optimize/rest.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/optimize/profile.so lib/chibi/optimize/profile.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/chibi/crypto/crypto.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/chibi/crypto/crypto.so lib/chibi/crypto/crypto.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/27/rand.so lib/srfi/27/rand.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/151/bit.so lib/srfi/151/bit.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/39/param.so lib/srfi/39/param.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/69/hash.so lib/srfi/69/hash.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/95/qsort.so lib/srfi/95/qsort.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/98/env.so lib/srfi/98/env.c -L. -lchibi-scheme
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme -q tools/chibi-ffi lib/srfi/144/math.stub
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/144/math.so lib/srfi/144/math.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/scheme/time.so lib/scheme/time.c -L. -lchibi-scheme
cc -fPIC -shared -DSEXP_USE_INTTYPES -Iinclude -Wall -g -g3 -O3 -o lib/srfi/18/threads.so lib/srfi/18/threads.c -L. -lchibi-scheme
echo "# pkg-config" > chibi-scheme.pc
echo "prefix=/data/data/com.termux/files/usr" >> chibi-scheme.pc
echo "exec_prefix=\${prefix}" >> chibi-scheme.pc
echo "libdir=/data/data/com.termux/files/usr/lib" >> chibi-scheme.pc
echo "includedir=\${prefix}/include" >> chibi-scheme.pc
echo "version=0.8.0" >> chibi-scheme.pc
echo "" >> chibi-scheme.pc
cat chibi-scheme.pc.in >> chibi-scheme.pc
find lib/chibi/ -name \*.sld | \
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme tools/generate-install-meta.scm 0.8.0 > lib/.chibi.meta
find lib/srfi/ -name \*.sld | \
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme tools/generate-install-meta.scm 0.8.0 > lib/.srfi.meta
find lib/scheme/ -name \*.sld | \
LD_LIBRARY_PATH=".:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH=".:" CHIBI_MODULE_PATH=lib ./chibi-scheme tools/generate-install-meta.scm 0.8.0 > lib/.scheme.meta
<span style='color: #009d0b; font-weight: bold'>Amazing - it built without issue. How about installing, will that work?</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ make install</span>
install -d /data/data/com.termux/files/usr/bin
install -m0755 chibi-scheme /data/data/com.termux/files/usr/bin/
install -m0755 tools/chibi-ffi /data/data/com.termux/files/usr/bin/
install -m0755 tools/chibi-doc /data/data/com.termux/files/usr/bin/
install -m0755 tools/snow-chibi /data/data/com.termux/files/usr/bin/
install -m0755 tools/snow-chibi.scm /data/data/com.termux/files/usr/bin/
<span style='color: #009d0b; font-weight: bold'>many boring 'install' lines removed. You're welcome.</span>
if type ldconfig >/dev/null 2>/dev/null; then ldconfig; fi
echo "Generating images"
Generating images
cd / && LD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:" /data/data/com.termux/files/usr/bin/chibi-scheme -d /data/data/com.termux/files/usr/share/chibi/chibi.img
cd / && LD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:" /data/data/com.termux/files/usr/bin/chibi-scheme -xscheme.red -d /data/data/com.termux/files/usr/share/chibi/red.img
cd / && LD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:/data/data/com.termux/files/usr/lib" DYLD_LIBRARY_PATH="/data/data/com.termux/files/usr/lib:" /data/data/com.termux/files/usr/bin/chibi-scheme -mchibi.snow.commands -mchibi.snow.interface -mchibi.snow.package -mchibi.snow.utils -d /data/data/com.termux/files/usr/share/chibi/snow.img
<span style='color: #009d0b; font-weight: bold'>Holy smokes, it's done. Let's see if it really worked.</span>
<span style='color: #333; font-weight: bold'>[localhost]{chibi-scheme}(1)$ cd</span>
<span style='color: #333; font-weight: bold'>[localhost]{~}(1)$ chibi-scheme</span>
> (+ 1 2 3)
6
<span style='color: #009d0b; font-weight: bold'>We have scheme! Let's try something a bit more advanced</span>
> (import (srfi 27) (srfi 1))
> (random-integer 100)
56
>
<span style='color: #009d0b; font-weight: bold'>The R7RS library functionality is working and </span>
<span style='color: #009d0b; font-weight: bold'>srfi's are installed by default. We have success!</span>
</pre>
<p>
And here are some screenshots to show this really was all executed on my Galaxy S9 Plus:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjA5hoqsmIiNmCBmzb0B3Jhab6ODIBXfQ6jbUVUGuq2M57RT8C1DZHoT4yXLnnzcpyi-W3HkeVeCyGTz8WURmu7VbcQjYcTBfmDBzLKQFAMSlsa2HgNF3umfsxeijNPtshFevbA/s1600/Screenshot_20180424-114432_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjA5hoqsmIiNmCBmzb0B3Jhab6ODIBXfQ6jbUVUGuq2M57RT8C1DZHoT4yXLnnzcpyi-W3HkeVeCyGTz8WURmu7VbcQjYcTBfmDBzLKQFAMSlsa2HgNF3umfsxeijNPtshFevbA/s200/Screenshot_20180424-114432_Termux.jpg" width="200" height="97" data-original-width="1600" data-original-height="779" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsspwEjRud-Q7vnAJGTcz1FiyKYByoZQxuKjS2FB0j07IrxP8qc6TjCw7LZslzpUM-58Ysjn41sT-m36jVTEha0G2RAAxdQWMrJ8wPMeqd8lxhMKSuwWKbraO7m4S-uYTHFjTh/s1600/Screenshot_20180424-114523_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsspwEjRud-Q7vnAJGTcz1FiyKYByoZQxuKjS2FB0j07IrxP8qc6TjCw7LZslzpUM-58Ysjn41sT-m36jVTEha0G2RAAxdQWMrJ8wPMeqd8lxhMKSuwWKbraO7m4S-uYTHFjTh/s200/Screenshot_20180424-114523_Termux.jpg" width="200" height="97" data-original-width="1600" data-original-height="779" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnrzi2F-jbvPqKZ7OK2IhpC4NKi2AW5Q0GnjWWdMVzwQX6Xe17pz9x76V8d_ZK2ZTx-b0chqauA2GK_mqcAbMUqaylGYDUMb-1USojvgWlG8_NqmCGxnh8MqSrZ8pDlO_9ob0i/s1600/Screenshot_20180424-114615_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnrzi2F-jbvPqKZ7OK2IhpC4NKi2AW5Q0GnjWWdMVzwQX6Xe17pz9x76V8d_ZK2ZTx-b0chqauA2GK_mqcAbMUqaylGYDUMb-1USojvgWlG8_NqmCGxnh8MqSrZ8pDlO_9ob0i/s200/Screenshot_20180424-114615_Termux.jpg" width="200" height="97" data-original-width="1600" data-original-height="779" /></a>Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com2tag:blogger.com,1999:blog-12753102.post-35134451980075236252018-04-23T23:11:00.000-04:002018-04-23T23:11:33.508-04:00A Little Scheme Setup and Development on the Galaxy S9 Plus<p>
Today's goal was to setup a Scheme programming environment on my new Galaxy S9 Plus phone. I planned to use the same tools I'd used on my LG G6:</p>
<ul>
<li><a href='https://play.google.com/store/apps/details?id=com.termux'>Termux</a> - provides a Unixy environment, doesn't require root and is just plain awesome</li>
<li><a href='http://tinyscheme.sourceforge.net/'>tinyscheme</a> - provides a lightweight, yet powerful, scheme environment. For bonus points, it's trivial to install within Termux. Just type: <tt>pkg install tinyscheme</tt></li>
<li><tt>emacs, vim, git</tt> - these tools run well under Termux and are installed using the <Tt>pkg install</tt> command. I use the same <tt>emacs</tt> config on my phone as I do my desktop.</li>
<li><a href='https://play.google.com/store/apps/details?id=com.apedroid.hwkeyboardhelper'>External Keyboard Helper</a> - remaps keys on my hardware keyboard. Specifically, I use it to map <tt>Caps Lock</tt> to <tt>Escape</tt>. I've found that this keybinding is essential to making <tt>bash</tt>, <tt>emacs</tt> and <tt>vim</tt> work in a sane way.</li>
</ul>
<p>
With the tools installed, I was able to open up a new <tt>.scm</tt> file in <tt>emacs</tt>, type <tt>C-u M-x run-scheme tinyscheme</tt> and I was off and running with an interactive Scheme development environment.</p>
<p>
While the tools installed without issue, I couldn't consider the environment setup until I wrote some code. So off I went to <a href='https://programmingpraxis.com/'>ProgrammingPraxis.com</a> to find an interesting exercise to tackle.</p>
<p>
Sticking with the theme of <A href='http://www.blogbyben.com/2018/03/hidden-in-plain-sight-using-unicode.html'>rendering text in unique ways</a>, I decided to complete the <A href='https://programmingpraxis.com/2018/02/27/seven-segment-devices/'>Seven-Segment Devices exercise</a>. A <i>Seven-Segment Device</i> is a primitive display that renders numbers and text using seven different lit up bars. Think old school calculators. Here are the seven different segments you have to work with:</p>
<pre>
--2--
| |
3 4
| |
--1--
| |
5 6
| |
--0--
</pre>
<p>
Below you'll find my solution that turns any integer into text that's rendered using this seven-segment style. The exercise called for storing the data as a bit-array. I took an alternative approach, and mapped every digit in the number to a list of enabled segments. For example, 0 maps to <tt>(2 4 6 0 5 3)</tt>. This is more verbose than packing the data into bits, but I was more interested in rendering the text than storing a compact representation of it.</p>
<p>
Here are some screenshots of the code running, and the code itself is below. It felt good to be coding on my new phone, and it sure is remarkable how well all these tools Just Work.</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCfH3pl_dW-mB9hhcBqCmKllqb1y4o09ly1dFIV6DCPgnVk8N0WeNSqnYQkZJFbuflU7FFpi9IXNoSz6BoKu1BZgbIS5SMu6ikhqP-7R5qWAGZq1960XsW0J8b08d1ldm7fPhy/s1600/Screenshot_20180423-144842_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCfH3pl_dW-mB9hhcBqCmKllqb1y4o09ly1dFIV6DCPgnVk8N0WeNSqnYQkZJFbuflU7FFpi9IXNoSz6BoKu1BZgbIS5SMu6ikhqP-7R5qWAGZq1960XsW0J8b08d1ldm7fPhy/s320/Screenshot_20180423-144842_Termux.jpg" width="320" height="156" data-original-width="1600" data-original-height="779" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8xKuRUOLRNAyT9HeYWRqbvD_U0w1jPS9MK0WJOrljgDYRVxsw81ffUoPLZ14A-5k0Pwu5feiM4rBRanzJ2_KHtaNMIETS-TOsBXyHxnMYyjqLFhwAu4sBxK0pdLWESjdC-3Dq/s1600/Screenshot_20180423-144824_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8xKuRUOLRNAyT9HeYWRqbvD_U0w1jPS9MK0WJOrljgDYRVxsw81ffUoPLZ14A-5k0Pwu5feiM4rBRanzJ2_KHtaNMIETS-TOsBXyHxnMYyjqLFhwAu4sBxK0pdLWESjdC-3Dq/s320/Screenshot_20180423-144824_Termux.jpg" width="320" height="156" data-original-width="1600" data-original-height="779" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9q3nQ-SqR56-vBw1-07BuWA4C-C5oCxb6bpdVg9MAxADWJ8zobwF2mUQ0webiFrwpaeJXJMFJiDQBU5c0ePesNp09lU1ShACxFLlvU2ZZhm7YLdQx6e_McfvVE61pFz-SWqlR/s1600/Screenshot_20180423-144959_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9q3nQ-SqR56-vBw1-07BuWA4C-C5oCxb6bpdVg9MAxADWJ8zobwF2mUQ0webiFrwpaeJXJMFJiDQBU5c0ePesNp09lU1ShACxFLlvU2ZZhm7YLdQx6e_McfvVE61pFz-SWqlR/s320/Screenshot_20180423-144959_Termux.jpg" width="320" height="156" data-original-width="1600" data-original-height="779" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKWnpgdQupJibisLvRR0mq9zn7pmEauwd3aChy3QbaLku0B2b-QlNjnOLRXVWRmuOTK246AjRSEBnPvwOqcbnq0kvAmn7zqm55Iykvkh2Gm-xDRU7S52h06V2yqd_lWtYAncwD/s1600/Screenshot_20180423-145340_Termux.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKWnpgdQupJibisLvRR0mq9zn7pmEauwd3aChy3QbaLku0B2b-QlNjnOLRXVWRmuOTK246AjRSEBnPvwOqcbnq0kvAmn7zqm55Iykvkh2Gm-xDRU7S52h06V2yqd_lWtYAncwD/s320/Screenshot_20180423-145340_Termux.jpg" width="320" height="156" data-original-width="1600" data-original-height="779" /></a>
<pre>
;; https://programmingpraxis.com/2018/02/27/seven-segment-devices/
(define (show . args)
(display args)
(newline))
(define (range lower upper)
(if (< lower upper)
(cons lower (range (+ 1 lower) upper))
'()))
(define *digit-width* 10)
(define *digit-height* 11)
(define *digit-sep* 4)
(define *digit-map*
'((0 . (2 4 6 0 5 3))
(1 . (4 6))
(2 . (2 4 1 5 0))
(3 . (2 4 1 6 0))
(4 . (3 1 4 6))
(5 . (2 3 1 6 0))
(6 . (3 5 0 6 1))
(7 . (2 4 6))
(8 . (0 1 2 3 4 5 6))
(9 . (2 4 1 3 6))))
(define (integer->bars val)
(if (= val 0)
(cdr (assoc 0 *digit-map*))
(let loop ((val val) (bars '()))
(cond ((<= val 0)
bars)
(else
(let ((d (modulo val 10)))
(loop
(inexact->exact (floor (/ val 10)))
(cons (cdr (assoc d *digit-map*)) bars))))))))
(define (draw-sep)
(for-each (lambda (i)
(display " "))
(range 0 *digit-sep*)))
(define (draw first mid last)
(display first)
(for-each (lambda (i)
(display mid))
(range 0 (- *digit-width* 2)))
(display last))
(define (draw-row digits row)
(define mid (/ (- *digit-height* 1) 2))
(define top? (= row 0))
(define bottom? (= row (- *digit-height* 1)))
(define mid? (= row mid))
(define upper? (and (not top?) (< row mid)))
(define lower? (and (not bottom?) (> row mid)))
(for-each (lambda (bars)
(define (has? x) (member x bars))
(cond ((and top? (has? 2))
(draw "+" "-" "+"))
((and bottom? (has? 0))
(draw "+" "-" "+"))
((and mid? (has? 1))
(draw "+" "-" "+"))
((and upper? (has? 3) (has? 4))
(draw "|" " " "|"))
((and upper? (has? 3))
(draw "|" " " " "))
((and upper? (has? 4))
(draw " " " " "|"))
((and lower? (has? 5) (has? 6))
(draw "|" " " "|"))
((and lower? (has? 5))
(draw "|" " " " "))
((and lower? (has? 6))
(draw " " " " "|"))
(else
(draw " " " " " ")))
(draw-sep))
digits)
(newline))
(define (draw-integer x)
(define s (integer->bars x))
(newline)
(for-each (lambda (row)
(draw-row s row))
(range 0 *digit-height*))
x)
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-83993560056980269092017-12-20T15:44:00.000-05:002017-12-20T15:44:32.453-05:00Helping bash and tinyscheme get along | Friendlier command line execution of scheme code<p>
I was looking for a cleaner way to manage <a href='http://www.blogbyben.com/2017/08/using-google-sheets-to-manage-sdr-touch.html'>SDR Touch radio frequencies</a> and I thought I'd give Scheme <a href='https://www.computerhope.com/jargon/s/s-expression.htm'>S-expressions</a> a go.</p>
<p>
I quickly arrived at this 'format':
</p>
<pre>
(("Arl,VA"
(166.9 "DC Police?")
(166.7 "Dc Police?"))
("OnABoat"
(462 "FRS Low")
(467 "FRS High")
(457.5 "Marine1")
(467.5 "Marine2")
(467.7 "Marine3"))
("NCL"
(457.5250 "Bridge Ops")
(457.5500 "Engineering")
(457.5750 "???"))
</pre>
<p>
Because I programmed the solution in Scheme, turning this basic set of S-expressions into the required mess of XML was straightforward. You can find the solution <a href='https://github.com/benjisimon/code/blob/master/sdr_touch/mkpresets.scm'>here</a>. I have to say, it was a real delight using S-Expressions to solve this one. XML, JSON and raw text all jumped out at me as options, but in this case, S-Expressions were the clear way to go.</p>
<p>
I coded this solution on my Android device using <A href='http://www.blogbyben.com/2017/11/hop-to-it-counting-jumps-using-cell.html'>Termux, emacs and Tinyscheme</a>.</p>
<p>
While the solution worked great under emacs' interactive scheme mode, I decided I wanted the ability to run the conversion command from a bash prompt. While tinyscheme has some basic command line handling, it was lacking a few details, such as the ability to get the script's working directory. This may seem like an obscure requirement, but with this value I'm able to reliably <tt>(load ...)</tt> files without worrying about running the script from a specific directory.</p>
<p>
To make tinyscheme more command line friendly, I created <Tt>tsexec</tt>, a small script below that kicks off tinyscheme with a number of helpful functions predefined. These include:</p>
<p><tt>(cmd-arg0)</tt> - returns the name of scheme script that is currently executing.</p>
<p><tt>(cmd-args)</tT> - returns the list of command line arguments passed to the currently executing script.</p>
<p><tt>(cmd-dir . path)</tt> - when invoked with no arguments, returns the directory the currently executing script lives in. When an argument is provided, the value is prefixed with the source script's directory.</p>
<p>
Using these functions I'm was able to write a command line friendly version of my scheme code to generate XML.
<pre>
(load (cmd-dir "utils.scm")) ;; utils.scm is now imported in a location independent way
(define (make-presets frequency-file xml-file)
(with-output-to-file xml-file
(lambda ()
(with-data-from-file frequency-file
(lambda (data)
(show "<?xml version='1.0' encoding='UTF-8'?>")
(show "<sdr_presets version='1'>")
(for-each (lambda (category)
(show "<category id='" (gen-id) "' name='" (car category) "'>")
(for-each (lambda (preset)
(show "<preset id='" (gen-id) "' ")
(show " name='" (cadr preset) "' ")
(show " freq='" (freqval (car preset)) "' ")
(show " centfreq='" (freqval (car preset)) "' ")
(show " offset='0'")
(show " order='" (gen-id) "' ")
(show " filter='10508' ")
(show " dem='1' ")
(show "/>"))
(cdr category))
(show "</category>"))
data)
(show "</sdr_presets>"))))))
;; Simple argument handling below
(cond
((= 1 (length (cmd-args)))
(make-presets (car (cmd-args)) "SDRTouchPresets.xml"))
((= 2 (length (cmd-args)))
(make-presets (car (cmd-args)) (cadr (cmd-args))))
(else
(show "Need to provide frequency and output file to continue.")))
</pre>
<p>
Here's a few screenshots of me running this code:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPXYZU5Z_pqoGCRoish3bhdbAxza80XCGHLtQkjauFyu8Z1BAI0Uklm4E7upN-8ACQn0IT5mitH8yYl1xRQMHqoxOXhMe2Wh1iO6bzszqFOBAkL7urfRvE8fOOR6gWh07deIRR/s1600/Screenshot_2017-12-20-15-01-00.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPXYZU5Z_pqoGCRoish3bhdbAxza80XCGHLtQkjauFyu8Z1BAI0Uklm4E7upN-8ACQn0IT5mitH8yYl1xRQMHqoxOXhMe2Wh1iO6bzszqFOBAkL7urfRvE8fOOR6gWh07deIRR/s320/Screenshot_2017-12-20-15-01-00.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcu-UYyGTb7E_jODANZjvyB0EuDPAJXXlNyx7oSI5_Wj3aUwAhuNzcB8P8QYXEJ8NZkf-pTaPtKIaO6_0-qFMd8ue6AS9vQQI7eWd2hqPQyxfzoo5F_69EinYR4DBEdTYVPF52/s1600/Screenshot_2017-12-20-15-01-35.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjcu-UYyGTb7E_jODANZjvyB0EuDPAJXXlNyx7oSI5_Wj3aUwAhuNzcB8P8QYXEJ8NZkf-pTaPtKIaO6_0-qFMd8ue6AS9vQQI7eWd2hqPQyxfzoo5F_69EinYR4DBEdTYVPF52/s320/Screenshot_2017-12-20-15-01-35.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEika1IPiRh1U0PJEqyXR15iA3J9u89ZBkkG3EcJXUtia0tYq5Nn9kOQzjbbfX0GMuOQTgk82lVG3bhtUH1hLzaedtokYHBPsKn07LsQmnCFg4CmRfb9doIqrtsMb4pfl1PnR25J/s1600/Screenshot_2017-12-20-15-01-27.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEika1IPiRh1U0PJEqyXR15iA3J9u89ZBkkG3EcJXUtia0tYq5Nn9kOQzjbbfX0GMuOQTgk82lVG3bhtUH1hLzaedtokYHBPsKn07LsQmnCFg4CmRfb9doIqrtsMb4pfl1PnR25J/s320/Screenshot_2017-12-20-15-01-27.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0MIK5wiAc6FnTTpDugQRVzVtGv0Nqp0vFEemzDz9kqk1GIUcAt5SP0NT2OwnKNyaLVHpqVe_Z2NVmI9HwVcj3sfMDlX5JyoL0Deg0Pqs_IuhW0pXQ-YPJ6_uDminJv8vcIdCa/s1600/Screenshot_2017-12-20-15-01-16.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0MIK5wiAc6FnTTpDugQRVzVtGv0Nqp0vFEemzDz9kqk1GIUcAt5SP0NT2OwnKNyaLVHpqVe_Z2NVmI9HwVcj3sfMDlX5JyoL0Deg0Pqs_IuhW0pXQ-YPJ6_uDminJv8vcIdCa/s320/Screenshot_2017-12-20-15-01-16.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a>
<p>
Termux has a handy <A href='https://play.google.com/store/apps/details?id=com.termux.widget'>add-on</a> that allows you to invoke shell scripts from your phone's home screen. I'm thinking <tt>tsexec</tt> may be an ideal way to connect up this short-cut ability to tinyscheme.
</p>
<p>
Finally, here's the source code for <Tt>tsexec</tt>. Enjoy!</p>
<pre>
#!/data/data/com.termux/files/usr/bin/bash
##
## Execute a tinyscheme script. Setup various functions that can
## be used to access command line args and such
##
if [ ! -f "$1" ] ; then
echo "Refusing to run non-existant script [$1]"
exit 1
fi
CMD_DIR=$(pwd)/$(dirname $1)
CMD_ARG0=$(basename $1)
CMD_MAIN="$CMD_DIR/$CMD_ARG0"
shift
CMD_ARGS=""
for arg in "$@" ; do
CMD_ARGS="$CMD_ARGS \"$arg\""
done
if [ ! -f "$CMD_MAIN" ] ; then
echo "Failed to derive CMD_DIR, guessed: $CMD_DIR"
exit 2
fi
wrapper() {
cat <<EOF
;; Autogenerated scheme wrapper script
(define (cmd-arg0)
"$CMD_ARG0")
(define (cmd-dir . path)
(if (null? path)
"$CMD_DIR"
(string-append "$CMD_DIR/" (car path))))
(define (cmd-args)
(list $CMD_ARGS))
(load "$CMD_MAIN")
EOF
}
wrapper > $HOME/.ts.$$
tinyscheme $HOME/.ts.$$
rm $HOME/.ts.$$
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com4tag:blogger.com,1999:blog-12753102.post-17788715759984824482017-11-13T14:21:00.001-05:002017-11-13T14:21:09.092-05:00Hop to it - Counting Jumps using a cell phone accelerometer<p>
Last week I was harshly schooled in the difference between <a href='http://www.blogbyben.com/2017/11/calculating-distance-from-cell-phones.html'>theoretical physics and the reality of cell phone hardware</a>. While it may be true that you can calculate distance from acceleration, the hardware on the LG G6 isn't precise enough to do so. But I remain undeterred!</p>
<p>
I return instead, to my original and simpler problem: can I use my phone's sensors to determine many jumps have I done in a jump rope session? The accelerometer is clearly one way to approximate this. Just check out the graph below. It shows three bursts of me jumping, with each set of jumps followed by a pause:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihGEaL8cwvZiIg5QlmjW_zxCyLGD6NcF5-8Gh-R5ydGEl0rOKWH3Di4dntL8jp9vGjE1hZP3Iueb5aqHIaIwPJ_rk_rDh0ue5tum1VDpSbEqYSV3cH3Gf6MmEz-v7is9oqkRZ8/s1600/Screenshot_2017-11-13-13-46-21.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihGEaL8cwvZiIg5QlmjW_zxCyLGD6NcF5-8Gh-R5ydGEl0rOKWH3Di4dntL8jp9vGjE1hZP3Iueb5aqHIaIwPJ_rk_rDh0ue5tum1VDpSbEqYSV3cH3Gf6MmEz-v7is9oqkRZ8/s640/Screenshot_2017-11-13-13-46-21.png" width="640" height="320" data-original-width="1600" data-original-height="800" /></a>
<p>
The simplest strategy here is to count the peaks of the graph. Swapping out the code to calculate distance with code to do this counting was simple enough. All the code can be found <A href='https://github.com/benjisimon/code/blob/master/android-accelerometer-playtime/main.scm'>here</a>, but the relevant lines as follows:</p>
<pre>
;; Counting the peaks in a given accelerometer stream. This should
;; give us a rough approximation of jumps
(define (count-peaks accum data)
(let ((lower 0)
(upper 10)
(verbose? #t)
(a-now (+ (data 1) (data 2) (data 3)))
(rising? (accum 0))
(num-peaks (accum 1)))
(cond ((and rising? (>= a-now upper))
(if verbose?
(show "peak discovered: " a-now))
(list #f (+ 1 num-peaks)))
((and (not rising?) (<= a-now lower))
(list #t num-peaks))
(else
(list rising? num-peaks)))))
</pre>
<p>
For now, a peak is defined as having total acceleration over 10m/s<sup>2</sup>. I arrived at this number the way all important mathematical constants are: I stood in my living room and jumped up and down. Set the peak height too low, and simple movements are marked as jump. Set it too high, and not all the jumps are counted.</p>
<p>
A smarter approach would be to make this number adaptive, making it somehow dependent on the data set itself. But for now, a constant of 10 seems to work OK.</p>
<p>
With this code change, I was able to record a 10 jump data file and run it through tinyscheme:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhveSODzJzv6iRH9q_5XWRfjectTJNSQMeIyCXzjhjSdRABJBy9ga7eFt93GainKrcMiYgjEwEwHJdh0XjOnBzMpPqp5-Mq26Mp59D3QaSo44Dyp6oOwV4enHr8zCXr4iQIIrOu/s1600/Screenshot_2017-11-13-07-59-23.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhveSODzJzv6iRH9q_5XWRfjectTJNSQMeIyCXzjhjSdRABJBy9ga7eFt93GainKrcMiYgjEwEwHJdh0XjOnBzMpPqp5-Mq26Mp59D3QaSo44Dyp6oOwV4enHr8zCXr4iQIIrOu/s640/Screenshot_2017-11-13-07-59-23.png" width="640" height="320" data-original-width="1600" data-original-height="800" /></a>
<p>
While this was functional, I was curious if I could streamline running this script. Switching to <a href='https://play.google.com/store/apps/details?id=com.termux'>Termux</a>, then entering the right filename in emacs, and then evaluating the code in the <tt>*scheme*</tT> buffer was all a bit much.</p>
<p>
Fortunately, Termux has the answer: <tt>Termux:Task</tt>. This is an add on for Tasker that allows you to kick off shell scripts under Termux. The first order of business was to wrap up the scheme code as a shell script. That wasn't hard:</p>
<pre>
#!/data/data/com.termux/files/usr/bin/sh
SRC_DIR=$HOME/dt/i2x/code/android-accelerometer-playtime/
MAIN_SCM=$SRC_DIR/main.scm
usage () {
echo "Usage: `basename $0` /path/to/data.csv"
exit
}
if [ -f "$1" ] ; then
exec tinyscheme -c "(define *src-dir* \"$SRC_DIR\") (load \"$MAIN_SCM\") (show (count-jumps \"$1\"))"
else
usage
fi
</pre>
<p>
<Tt>tinyscheme</tt> can be invoked with <tt>-c</tt> which allows for running arbitrary scheme expressions. I'm using this to initialize and run parameterized code.</p>
<p>
From there, I soft linked this script under <tt>$HOME/.termux/tasker</tt>. This allowed the script to be visible inside of Tasker:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMeUC0ArsruGdb-xgS8woYEpgXXqd0O0aiVLzqbG6DCdlM_H-EtjCYSKHdL9xDtAUfZ2TTuGQ6yc6XW-o-_WYycrW49rnjpHhWS3dEKJKYJTdLZpyUfWCU4iHt3wE5fXxEw8OB/s1600/Screenshot_2017-11-13-13-36-17.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMeUC0ArsruGdb-xgS8woYEpgXXqd0O0aiVLzqbG6DCdlM_H-EtjCYSKHdL9xDtAUfZ2TTuGQ6yc6XW-o-_WYycrW49rnjpHhWS3dEKJKYJTdLZpyUfWCU4iHt3wE5fXxEw8OB/s320/Screenshot_2017-11-13-13-36-17.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEif5J0HzLLPPyMWG9fpBrR7Cv0iHAxULhwOWkF9W3y_HJ8LO_JMmYq5AZKeiY3eEGJmxWD9bLEZmEOWDO0yUy2QbC_89D8TvQWAaEeJ-LSWoZLUM5pftZ2IsPu3inkPUzsYLXnP/s1600/Screenshot_2017-11-13-13-36-34.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEif5J0HzLLPPyMWG9fpBrR7Cv0iHAxULhwOWkF9W3y_HJ8LO_JMmYq5AZKeiY3eEGJmxWD9bLEZmEOWDO0yUy2QbC_89D8TvQWAaEeJ-LSWoZLUM5pftZ2IsPu3inkPUzsYLXnP/s320/Screenshot_2017-11-13-13-36-34.png" width="320" height="160" data-original-width="1600" data-original-height="800" /></a>
<p>
Note the use of <tt>%asfile1</tt>. This variable is set by <a href='https://play.google.com/store/apps/details?id=com.joaomgcd.autoshare&hl=en'>AutoShare</a>, a Tasker plugin that lets you kick off actions based on the system sharing menu.
</p>
<p>
With the Tasker code in place, I can record data in the <A href='https://play.google.com/store/apps/details?id=net.vieyrasoftware.physicstoolboxsuitepro&hl=en'>Physics Toolbox Sensor Suite</a> app, then share that data with the <tt>Count Jumps</tt> AutoShare command. This kicks off the <Tt>count_jumps</tt> shell script, which invokes <Tt>tinyscheme</tt> and runs my code above. Simple, right? It may be a virtual Rube Goldberg, but it does work, and successfully demonstrates how you can get from an Android App to scheme code with very little effort.</p>
<p>As a final test, here's me knocking out 30 test jumps:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtcnrcHXa0boSVsnHl6QPz847ewvTNCJnswCp9QwnLtAI-6LrCM4b4n04KZ_CTvZcuWJDd7jBsV1GyqafKmWRnoSIcApXo5-r0G6OpUeA5deb1EPZfBk_Dy9vOusJbjGFzlQCr/s1600/Screenshot_2017-11-13-14-03-16.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtcnrcHXa0boSVsnHl6QPz847ewvTNCJnswCp9QwnLtAI-6LrCM4b4n04KZ_CTvZcuWJDd7jBsV1GyqafKmWRnoSIcApXo5-r0G6OpUeA5deb1EPZfBk_Dy9vOusJbjGFzlQCr/s400/Screenshot_2017-11-13-14-03-16.png" width="200" height="400" data-original-width="800" data-original-height="1600" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJR1PQb9b8v0poQTTWLiwyxiDcDQKbvSY_vt2-9kB1_Qf9GH_7cnffS-oi6lb2HLS48M8VS0syTFpLu6lTxskuQJPFZrtgW37cXUmh26dXW-KwMBZ-YhjxkcNCDBwLnAuNKo_S/s1600/Screenshot_2017-11-13-14-03-36.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJR1PQb9b8v0poQTTWLiwyxiDcDQKbvSY_vt2-9kB1_Qf9GH_7cnffS-oi6lb2HLS48M8VS0syTFpLu6lTxskuQJPFZrtgW37cXUmh26dXW-KwMBZ-YhjxkcNCDBwLnAuNKo_S/s400/Screenshot_2017-11-13-14-03-36.png" width="200" height="400" data-original-width="800" data-original-height="1600" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLw7An97L9FlEaixyuEaytS1etzOrnh1Ohdt_qJIv2DsSPk3t_4nNWGZjE1OGSI9tmDFC9N23DATlFqgx5lnONKqjpxLrsu_VWNkpUEwlUlb-glDteWVvHFkqQe29jU7iMVm-D/s1600/Screenshot_2017-11-13-14-03-41.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLw7An97L9FlEaixyuEaytS1etzOrnh1Ohdt_qJIv2DsSPk3t_4nNWGZjE1OGSI9tmDFC9N23DATlFqgx5lnONKqjpxLrsu_VWNkpUEwlUlb-glDteWVvHFkqQe29jU7iMVm-D/s400/Screenshot_2017-11-13-14-03-41.png" width="200" height="400" data-original-width="800" data-original-height="1600" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh42BzDQ5a7D8Cr9pmVlqxl1uIf9KyTQTYMAFr1jLI8yrTm4kIfId7sTRUDiiuUYiVi3AbZdrgmSlVZMy0OHl4-HksvO5m0vfiQ0z-LDyaXYV4FplAyHAm8abNs_wDeUvywVcUY/s1600/Screenshot_2017-11-13-14-04-07.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh42BzDQ5a7D8Cr9pmVlqxl1uIf9KyTQTYMAFr1jLI8yrTm4kIfId7sTRUDiiuUYiVi3AbZdrgmSlVZMy0OHl4-HksvO5m0vfiQ0z-LDyaXYV4FplAyHAm8abNs_wDeUvywVcUY/s400/Screenshot_2017-11-13-14-04-07.png" width="200" height="400" data-original-width="800" data-original-height="1600" /></a>
<p>
And there you have it, 31 jumps. As approximations go, I'll take it.
</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-12426418796504766722016-06-16T12:35:00.001-04:002016-06-16T12:35:33.546-04:00Got Data? Adventures in Virtual Crystal Ball Creation<p>
There's two ways to look at <A href='https://programmingpraxis.com/2016/06/10/linear-regression/'>this recent</a> Programming Praxis exercise: implementing a beginner level statistics function or <i>creating a magical crystal ball that can predict past, present and future</i>! I chose to approach this problem with the mindset of the latter. Let's make some magic!</p>
<p>
The algorithm we're tackling is <a href='https://programmingpraxis.com/2016/06/10/linear-regression/'>linear regression</a>. I managed to skip statistics in college (what a shame!), so I don't recall ever being formally taught this technique. Very roughly, if you have the right set of data, you can plot a line through it. You can then use this line to predict values not in the data set.</p>
<p>
The exercise gave us this tiny, manufactured, data set:
</p>
<pre>
x y
60 3.1
61 3.6
62 3.8
63 4.0
65 4.1
</pre>
<p>
With linear regression you can answer questions like: what will be the associated value for say, <tt>64</tt>, <tt>66</tt> or <tt>1024</tt> be? Here's my implementation in action:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFSTHHLgsOpQaWZkssbcPOyVaM5sDFJGn74hcJ6yGwzO6imVcnPF9Mmule469841MYSuz8NWZcxm4VqVAzWFGs0hWyxm-QlRyBCl35O9cOCFBbOVMJLQBbL1qyLPqqBVBV9Vq4/s1600/Screenshot_20160616-115610.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFSTHHLgsOpQaWZkssbcPOyVaM5sDFJGn74hcJ6yGwzO6imVcnPF9Mmule469841MYSuz8NWZcxm4VqVAzWFGs0hWyxm-QlRyBCl35O9cOCFBbOVMJLQBbL1qyLPqqBVBV9Vq4/s640/Screenshot_20160616-115610.png" /></a>
<p>
A few words about the screenshot above. You'll notice that I'm converting my data from a simple list to a generator. A generator in this case is a function that will return a single element in the data set, and returns <tt>'()</tt> when all the data has been exhausted. I chose to use a generator over a simple list because I wanted to allow this solution to scale to large data sets.</p>
<p>
Below you'll see a data set that's stored in a file and leverages a file based generator to access its contents. So far, I haven't throw a large data set at this program, but I believe it should scale without issue.</p>
<p>The call to <tt>make-crystal-ball</tt> performs the linear-regression and returns back a function that when provided <tt>x</tt> returns a <s>guess</s> prediction for <tt>y</tt>. What? I'm trying to have a bit of fun here.</p>
<p>
Looking around on web I found <A href='http://onlinestatbook.com/2/regression/intro.html'>this example</a> that uses a small, but real data set. In this case, it compares <a href='http://onlinestatbook.com/2/case_studies/sat.html'>High School and College GPA</a>. Using linear-regression we're able to predict how a High School student with a 2.7, 3.0 or 3.5 GPA is going to do in college. Here's the code:</p>
<pre>
;; http://onlinestatbook.com/2/regression/intro.html
;; http://onlinestatbook.com/2/case_studies/sat.html
(define (gpa-sat-test)
(define data (file->generator "gpa-sat-data.scm"
(lambda (high-gpa math-sat verb-sat comp-gpa univ-gpa)
(list high-gpa univ-gpa))))
(let ((ball (make-crystal-ball data)))
(show "2.7 => " (ball 2.7))
(show "3.0 => " (ball 3))
(show "3.5 => " (ball 3.5))))
</pre>
<p>
And the answer is: 2.91, 3.12 and 3.45 respectively. So yeah, that's good news if you were dragging in High School, you're GPA should climb a bit. But High School overachievers should beware, your GPA is most likely to dip. D'oh.</p>
<p>
Below is my implementation of this solution. You can also find it on <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/linear-regression.scm'>github</a>. As usual I find myself preaching the benefits of Scheme. The code below was written on my Galaxy Note 5 using <A href='https://termux.com/'>Termux</a>, <a href='http://endlessparentheses.com/running-emacs-on-android.html'>emacs</a> and <a href='http://tinyscheme.sourceforge.net/download.html'>Tinyscheme</a>. With relative ease I was able to implement a generator framework that works for both lists and data files. I'm also able to leverage the Scheme reader so that the data file format is trivial to operate on. Finally, I wrote a generic <tt>sigma</tt> function that walks through my data set once, but performs all the various summations I'll need to calculate the necessary values. In other words, I feel like I've got an elegant solution using little more than lists, lambda functions and sexprs. It's beautiful and should be memory efficient.</p>
<p>
Here's the code:</p>
<pre>
;; https://programmingpraxis.com/2016/06/10/linear-regression/
(define (show . args)
(for-each (lambda (arg)
(display arg)
(display " "))
args)
(newline))
(define (as-list x)
(if (list? x) x (list x)))
(define (g list index)
(list-ref list index))
(define (make-list n seed)
(if (= n 0) '()
(cons seed (make-list (- n 1) seed))))
(define (list->generator lst)
(let ((remaining lst))
(lambda ()
(cond ((null? remaining) '())
(else
(let ((x (car remaining)))
(set! remaining (cdr remaining))
x))))))
(define (file->generator path scrubber)
(let ((port (open-input-file path)))
(lambda ()
(let ((next (read port)))
(if (eof-object? next) '() (apply scrubber next))))))
(define (sigma generator . fns)
(define (update fns sums data)
(let loop ((fns fns)
(sums sums)
(results '()))
(cond ((null? fns) (reverse results))
(else
(let ((fn (car fns))
(a (car sums)))
(loop (cdr fns)
(cdr sums)
(cons (+ a (apply fn (as-list data)))
results)))))))
(let loop ((data (generator))
(sums (make-list (length fns) 0)))
(if (null? data) sums
(loop (generator)
(update fns sums data)))))
;; Magic happens here:
;; m = (n × Σxy − Σx × Σy) ÷ (n × Σx2 − (Σx)2)
;; b = (Σy − m × Σx) ÷ n
(define (linear-regression data)
(let ((sums (sigma data
(lambda (x y) (* x y))
(lambda (x y) x)
(lambda (x y) y)
(lambda (x y) (* x x))
(lambda (x y) 1))))
(let* ((Sxy (g sums 0))
(Sx (g sums 1))
(Sy (g sums 2))
(Sxx (g sums 3))
(n (g sums 4)))
(let* ((m (/ (- (* n Sxy) (* Sx Sy))
(- (* n Sxx) (* Sx Sx))))
(b (/ (- Sy (* m Sx)) n)))
(cons m b)))))
(define (make-crystal-ball data)
(let* ((lr (linear-regression data))
(m (car lr))
(b (cdr lr)))
(lambda (x)
(+ (* m x) b))))
;; Playtime
(define (test)
(define data (list->generator '((60 3.1)
(61 3.6)
(62 3.8)
(63 4.0)
(65 4.1))))
(let ((ball (make-crystal-ball data)))
(show (ball 64))
(show (ball 66))
(show (ball 1024))))
;; From:
;; http://onlinestatbook.com/2/regression/intro.html
;; http://onlinestatbook.com/2/case_studies/sat.html
(define (gpa-sat-test)
(define data (file->generator "gpa-sat-data.scm"
(lambda (high-gpa math-sat verb-sat comp-gpa univ-gpa)
(list high-gpa univ-gpa))))
(let ((ball (make-crystal-ball data)))
(show "2.7 => " (ball 2.7))
(show "3.0 => " (ball 3))
(show "3.5 => " (ball 3.5))))
(gpa-sat-test)
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com2tag:blogger.com,1999:blog-12753102.post-61644241278095964412016-03-15T09:10:00.001-04:002016-03-15T09:10:47.361-04:00The technology that powered geeks from Newton to Aldrin<p>
Pop Quiz: <i>What do Issac Newton, Buzz Aldrin and My Dad all have in common?</i> They all solved math problems, at one time or another, using the same device: the mighty <A href='http://www.npr.org/sections/ed/2014/10/22/356937347/the-slide-rule-a-computing-device-that-put-a-man-on-the-moon'>slide rule</a>. After watching <a href='http://thekidshouldseethis.com/post/the-iphone-of-slide-rules-halden-calculex-numberphile'>this video</a> I realized I've never done a post on the slide rule, and as an aficionado of all things simultaneously basic and techy, I needed to correct that.</p>
<p>
The technology really does go back hundreds of years, with Issac Newton clearly <a href='http://web.mat.bham.ac.uk/C.J.Sangwin/Sliderules/newton.html'>describing</a> a device which anyone doing math in the 1960's or before would appreciate:</p>
<blockquote>
Mr. Newton, with the help of logarithms graduated upon scales by placing them parallel at equal distances or with the help of concentric circles graduated in the same way, finds the roots of equations. Three rules suffice for cubics, four for biquadratics. In the arrangement of these rulers, all the respective coefficients lie in the same straight line. From a point of which line, as far removed from the first rule as the graduated scales are from one another, in turn, a straight line is drawn over them, so as to agree with the conditions conforming with the nature of the equations; in one of
</blockquote>
<p>
And here's an actual shot of <A href='http://sliderulemuseum.com/Ephemera/Buzz_Aldrin_Apollo11_with_slide_rule.jpg'>Buzz Aldrin</a> in space with a slide ruler floating in the background:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhw1rmkj0ldsfsFWTqkMwes3tbYkCGii2e0Cisj0T2LsIlIdvvJJ-wF7C6_4f3EYdtLmr2kOIx6SDRWOCGR7EpyrHkr4NbNUcaABRk8KF7Vlo76o1CpuST5F1s7J76g_8BP7Nvo/s1600/Buzz_Aldrin_Apollo11_with_slide_rule.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhw1rmkj0ldsfsFWTqkMwes3tbYkCGii2e0Cisj0T2LsIlIdvvJJ-wF7C6_4f3EYdtLmr2kOIx6SDRWOCGR7EpyrHkr4NbNUcaABRk8KF7Vlo76o1CpuST5F1s7J76g_8BP7Nvo/s580/Buzz_Aldrin_Apollo11_with_slide_rule.jpg" /></a>
<p>
One can imagine that nearly every major undertaking involving complex math utilized the slide rule in one way or another. Consider this description of the <A href='http://www.pbs.org/wgbh/amex/legacy/goldengate/sfeature/sf_forces_pop_04a.html'>building of the Golden Gate Bridge</a>:
<blockquote>
Charles Ellis and Leon Moisseiff calculated forces for the Golden Gate Bridge with only a circular slide rule and a manual adding machine. They worked for months -- by hand -- sometimes solving equations with more than thirty unknowns.
</blockquote>
<p>
Those guys weren't messing around.</p>
<p>
My favorite slide rule store does happen to come from the space program, specifically from the <a href='http://modernnotion.com/slide-rules-helped-put-man-moon/'>Apollo 13 mission</a>:
<blockquote>
Perhaps the most impressive use of the slide rule was during the Apollo 13 crisis. Engineers had to recalculate data to guide the crew safely back to Earth—and they had to do it quickly. Richard Ogle describes how it went down:<br/>
<br/>
""NASA had at its disposal whole banks of sophisticated computers, of course, but these were not programmed to do the basic calculations [Commander Jim Lovell] needed. So the engineers reverted to that most mundane pre-pocket calculator workhorse, the slide rule. Had the engineers at Mission Control been forced to do the necessary calculations on paper, Apollo 13 might well have missed the trajectory needed to bring it back to earth altogether. Instead the slide rule, designed specifically to exploit human beings’ highly developed visual acuity, allowed them to perform a set of complicated calculations in seconds.""
</blockquote>
<p>
OK, we all get that the slide rule is an amazing device. But how do you truly grok it? You could pick one up on <A href='http://www.ebay.com/sch/i.html?_from=R40&_trksid=p2050601.m570.l1313.TR0.TRC2.A0.H0.Xslide+rule.TRS1&_nkw=slide+rule&_sacat=0'>eBay</a> for under $10 or so and work towards mastering it. Or, you could install the <a href='https://play.google.com/store/apps/details?id=com.timscott.sliderule'>App</a> on your phone for free, and start playing with it right now. But, as they say, if you truly want to understand something, <i>teach it</i>. And I know of no more recalcitrant a student than the computer. So I decided to program a slide rule.
</p>
<p>
Here's <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/slide-rule.scm'>my solution</a>:</p>
<pre>
(struct scale (symbol location abs-fn scale-fn) #:prefab)
(define C (scale 'C 'slide
(lambda (s)
(log s))
(lambda (a)
(exp a))))
(define D (scale 'D 'body
(lambda (s)
(log s))
(lambda (a)
(exp a))))
(define CI (scale 'CI 'slide
(lambda (s)
(log (/ s (/ 1 s))))
(lambda (a)
(/ 1 (exp a)))))
(define DI (scale 'CI 'body
(lambda (s)
(log (/ s (/ 1 s))))
(lambda (a)
(/ 1 (exp a)))))
(define A (scale 'A 'body
(lambda (s)
(log (expt s (/ 1 2))))
(lambda (a)
(expt (exp a) 2))))
(define B (scale 'B 'slide
(lambda (s)
(log (expt s (/ 1 2))))
(lambda (a)
(expt (exp a) 2))))
(define R (scale 'R 'slide
(lambda (s)
(log (expt s 2)))
(lambda (a)
(sqrt (exp a)))))
(define K (scale 'K 'body
(lambda (s)
(log (expt s (/ 1 3))))
(lambda (a)
(expt (exp a) 3))))
(define (make-slide-rule)
(let ((offset 0))
(lambda (action . args)
(define (align s1 v1 s2 v2)
(cond ((and (eq? (scale-location s1) 'body)
(eq? (scale-location s2) 'slide))
(set! offset
(- ((scale-abs-fn s1) v1)
((scale-abs-fn s2) v2)))
offset)
((and (eq? (scale-location s1) 'slide)
(eq? (scale-location s2) 'body))
(align s2 v2 s1 v1))
(else
(error (format "Must align body to slide, not ~a to ~a"
(scale-location s1) (scale-location s2))))))
(define (read s1 v1 s2)
(cond ((and (eq? (scale-location s1) 'body)
(eq? (scale-location s2) 'slide))
((scale-scale-fn s2) (- ((scale-abs-fn s1) v1) offset)))
((and (eq? (scale-location s1) 'slide)
(eq? (scale-location s2) 'body))
((scale-scale-fn s2) (+ ((scale-abs-fn s1) v1) offset)))
(else
(error (format "Must read from slide to body, or body to slide. Not ~a to ~a"
(scale-location s1) (scale-location s2))))))
(case action
((align)
(apply align args))
((offset) offset)
((read)
(apply read args))
(else
(error (format "Unknown slide rule command: ~a" action)))))))
</pre>
<p>
I found <A href='http://www.math.utah.edu/~pa/sliderules/'>this page</a> especially useful in developing my implementation.
</p>
<p>
What I learned from this little coding exercise was that there's really only two operations that you can perform with a slide rule: <i>slide it</i> and <i>read it</i>. So I implemented those two operations: <tt>align</tt> and <tt>read</tt>. For example, to perform basic multiplication, you align the <tt>C</tt> and <tt>D</tt> scales, and then read the value off the <tt>D</tt> scale relative to the <tt>C</tt> scale. Or, in code:</p>
<pre>
(define sr (make-slide-rule))
(sr 'align C 1 D 5)
(sr 'read C 3 D) ;; => 15
</pre>
<p>
And here's an example of computing <tt>X<sup>3</sup></tt> using the <tt>K</tt> scale:
</p>
<pre>
(define sr (make-slide-rule))
(sr 'align C 1 D 1)
(sr 'read C 3 K) ;; => 9
</pre>
<p>
I definitely appreciate that by implementing more advanced scales, you could knock out some pretty hairy math with relative ease.
</p>
<p>
Don't get me wrong, I love me a calculator (even with its <A href='http://www.blogbyben.com/2016/03/the-problem-with-and-solution-to.html'>flaws</a>) and gladly perform even the most basic mathematics on it. But from a design and hacking perspective, you really can't beat the mighty slide rule. It's definitely worth taking the time to understand how it works and why it was such an effective tool for so long.
</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-23357504579329237302016-01-13T07:21:00.000-05:002016-01-13T10:44:19.331-05:00Mystery Solved: One Approach to Spot-It Game Card Generation<p>
<a href='http://www.amazon.com/Asmodee-00411-Spot-It/dp/B0039S7NO6/ref=sr_1_1?s=toys-and-games&ie=UTF8&qid=1452661702&sr=1-1&keywords=spot+it'>Spot-It</a> is one of my go-to quick games for kids and adults alike. Many a wait at the pediatrician's office has been made that much more bearable thanks to this handy little game. While there are a few variations for playing it, they all involve the same basic strategy: the faster you can spot the match between any two Spot-It cards, the better. Which brings me to the cards:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgjgoQk_YF0-RT3K7fPcGDh9gh1mz16Fvu4YZiRrcm_LqN9_kHcAFKGKg5qfkfpQ_kPRS3NiJNEXJZmgz9io5O2ARoqRUfyDCcYhOMM0xvabxZsVxgRvQ1INKP2EFxMAaX3XLRzw/s1600/spot-it.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgjgoQk_YF0-RT3K7fPcGDh9gh1mz16Fvu4YZiRrcm_LqN9_kHcAFKGKg5qfkfpQ_kPRS3NiJNEXJZmgz9io5O2ARoqRUfyDCcYhOMM0xvabxZsVxgRvQ1INKP2EFxMAaX3XLRzw/s580/spot-it.jpg" /></a>
<p>
The magic of the game is this: every card matches every other card exactly once. Take a moment and confirm this by looking at the cards above.</p>
<p>
Every time I play Spot-It I think to myself: <i>how the heck did that do that?</i> And so after a rousing game a few weeks ago I decided I'd have to find out. And what better way to do so than to write some code to generate my own deck of cards?</p>
<p>
And so began a multi-week saga in puzzling out a solution. I have to admit, the problem pretty much kicked my butt. If you look at the <a href='https://github.com/benjisimon/code/commits/master/programming-praxis/spot-it.scm'>history</a> of my code, you'll see all sorts of wrong headed attempts. From a random statistical solution, to mutating vectors full of vectors, I tried in vain to crack the problem. For the last few weeks our table has been covered in little scraps of paper, like so:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjkPyu6wgkrWMOWPA_r4aLu3zjQSaplzZpjlZTkl_G2c3UnRjzmMTLdR91LycKHn3-DCjfP8PLHdc2C2j9Qie-lOBDuIT3aPf7EbeFA9MaDpXLczCq_YbqI9aj-o4Dev0_AQvq0XQ/s1600/scraps.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjkPyu6wgkrWMOWPA_r4aLu3zjQSaplzZpjlZTkl_G2c3UnRjzmMTLdR91LycKHn3-DCjfP8PLHdc2C2j9Qie-lOBDuIT3aPf7EbeFA9MaDpXLczCq_YbqI9aj-o4Dev0_AQvq0XQ/s580/scraps.jpg" /></a>
<p>
But I lived with the problem, and during last week's dentist cleaning, I had a bit of breakthrough. Luckily, I had to wait for Shira to finish up, and so that gave me some time in the waiting room to work on a solution. I can't imagine what the receptionist thought as I tore apart pages from my pocket notepad to create prototype cards. From there, I busted out my <a href='http://www.blogbyben.com/2015/10/more-linux-on-android-success-emacs.html'>keyboard</a> and coded up my new insights. Alas, that solution had flaws, but it took me in the right direction.</p>
<p>
Finally, I realized I needed a solution that had a component of backtracking to it. Luckily, before I jumped in and implemented <a href='http://c2.com/cgi/wiki?AmbSpecialForm'>amb</a>, and I discovered I could get this backtracking by using simple recursion. I finally figured out the the last iteration of a solution on a jog a few days ago, and then last night I typed it in. And voila!, I give you a generated set of Spot-It cards:
</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVjMF5vmb8DlOsv56HKcy_7-vRjNj4HgdmEy6FTr1Zp68pY0dpY17ZKFLCWCwZfNbigr-EhXrOTlbfMB-kqbJDyNXsFL4UVHHT4c_8_immsXz1ekLM0Sfzl3Sky0izOdgUIYhslw/s1600/Screenshot_2016-01-12-17-12-49.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVjMF5vmb8DlOsv56HKcy_7-vRjNj4HgdmEy6FTr1Zp68pY0dpY17ZKFLCWCwZfNbigr-EhXrOTlbfMB-kqbJDyNXsFL4UVHHT4c_8_immsXz1ekLM0Sfzl3Sky0izOdgUIYhslw/s580/Screenshot_2016-01-12-17-12-49.jpg" /></a>
<p>
OK, the above uses numbers instead of funky symbols. But the core principle holds: each card (implemented as a list of numbers) matches each other card exactly once. The prettification of the output is left as an exercise to the reader.</p>
<p>
I'm sure there's a much more elegant solution to this problem than mine. However, for now, I'm just enjoying that feeling that comes from living with, and ultimately conquering, a problem. Whoo!</p>
<p>
And here's the code. The mystery to Spot-It card generation (or at least, one version) is revealed below:
</p>
<pre>
;;
;; Not an actual programming praxis exercise, but it should be.
;; Implement the spot-it game card sequence
;;
;; Every card matches every other card in exactly one way
;;
#lang scheme
(define (inc x)
(+ x 1))
(define (dec x)
(- x 1))
(define (make-symbol-generator)
(let ([x 0])
(lambda ()
(set! x (inc x))
x)))
(define (card-match? c1 c2)
(cond ([null? c1] #f)
([null? c2] #f)
([member (car c1) c2] #t)
(else (card-match? (cdr c1) c2))))
(define (make-deck n sym-gen)
(if (exact? (sqrt n))
(apply append
(for/list ([i (sqrt n)])
(let ([sym (sym-gen)])
(for/list ([j (sqrt n)])
(list sym)))))
(error "Deck size must a perfect square")))
(define (can-add-to-pile? card pile)
(cond ([null? pile] #t)
((not [card-match? (car pile) card])
(can-add-to-pile? card (cdr pile)))
(else #f)))
(define (grow-pile pile size deck)
(cond ([= size 0] pile)
([null? deck] #f)
(else
(let ([card (car deck)])
(if (and (can-add-to-pile? card pile)
(grow-pile (cons card pile) (dec size) (cdr deck)))
(grow-pile (cons card pile) (dec size) (cdr deck))
(grow-pile pile size (cdr deck)))))))
(define (remove-pile-from-deck pile deck)
(filter (lambda (card)
(not (memq card pile)))
deck))
(define (match-pile pile sym-gen)
(let ([sym (sym-gen)])
(map (lambda (card)
(cons sym card))
pile)))
(define (done? deck)
(let loop ([cards deck])
(cond ([null? cards] #t)
(else
(if (andmap (lambda (c)
(card-match? c (car cards)))
deck)
(loop (cdr cards))
#f)))))
(define (tick deck sym-gen)
(let ([psize (sqrt (length deck))])
(let loop ([i 0] [deck deck] [piles '()])
(cond ([= i psize]
(apply append (map (lambda (p)
(match-pile p sym-gen))
piles)))
(else
(let ([pile (grow-pile '() psize deck)])
(loop (inc i)
(remove-pile-from-deck pile deck)
(cons pile piles))))))))
(define (go size)
(let ([sym-gen (make-symbol-generator)])
(let loop ([deck (make-deck size sym-gen)])
(cond ([done? deck] deck)
(else
(loop
(tick deck sym-gen)))))))
(go 9)
(go 16)
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-12308427140020827632015-11-23T06:53:00.002-05:002015-11-23T06:53:30.188-05:00Reading Racket Documentation on Android, No Internet Needed<p>
I've got <A href='http://www.blogbyben.com/2015/10/more-linux-on-android-success-emacs.html'>emacs and racket</a> running nicely on my Android phone (thanks to the awesome <A href='http://www.blogbyben.com/2015/09/linux-on-your-android-phone-easier-and.html'>Gnuroot</a>). But that left me with a new wrinkle: what's the best way to access Racket Documentation while programming on my phone? Obviously, I can open up a browser to <A href='http://docs.racket-lang.org/'>doc.racket-lang.org</a> but what if I'm a context where I don't have access to the Net?</p>
<p>
By default, <tt>apt-get</tt> appears to install racket documentation in <tt>/usr/share/doc/racket</tt>, which means that my phone had the documentation, I just needed a way of viewing it.</p>
<p>
<b>Method 1: w3m</b>. A quick and easy way to view the documentation is to run <tt>apt-get install w3m</tt>, and install <A href='http://w3m.sourceforge.net/'>w3m</a>. <Tt>w3m</tt> is an extremely handy tool as it lets you view <tt>html</tt> files from the command line. For example:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSghyphenhyphenHZ9ParRtVFfKoQbI8H2hlT1QLVNeZvUUGLIcrfx70CZavUaoFHLAWZkLxcT2chrfns8hJHFlYKm89wHxi8jIWZtQQ3b_6KVRzvPXbRgGXwPU-EgPMfj-3zjDmM1PehlKBMQ/s1600/Screenshot_2015-11-23-06-40-29.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSghyphenhyphenHZ9ParRtVFfKoQbI8H2hlT1QLVNeZvUUGLIcrfx70CZavUaoFHLAWZkLxcT2chrfns8hJHFlYKm89wHxi8jIWZtQQ3b_6KVRzvPXbRgGXwPU-EgPMfj-3zjDmM1PehlKBMQ/s580/Screenshot_2015-11-23-06-40-29.png" /></a>
<p>
<b>Method 2: launch a local web server</b>. While <tt>w3m</tt> is a fast and functional solution, I wanted to be able to view the documentation in a standard browser, too. I figured I could accomplish this if I kicked off a local webserver. I could then point my regular Android browser to this server and I'd be all set. While I'm sure I could have installed <tt>apache</tt> or another full featured server, I found an easier and lighter weight solution: <a href='http://www.hping.org/wbox/'>wbox</a>. <tt>wbox</tt> is a testing tool that happens to offer the capability of being a stand alone, zero configuration, web server. Installing <tt>wbox</tt> is as easy as running <tt>apt-get install wbox</tt>. And here it is in action:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiX1lWYvjP0vAvV5BqQta3decn78yGQ5YaP12u5s4M2P0x3_3biFZVbCK4wDsfM6AtkKETdGYWtvOXqc24dJbxRXAGLPHw7k7xyRuhZIrP5mWaLWx9ZrZBQ81Hcobn3m0vTcGG-Zw/s1600/Screenshot_2015-11-23-06-03-29.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiX1lWYvjP0vAvV5BqQta3decn78yGQ5YaP12u5s4M2P0x3_3biFZVbCK4wDsfM6AtkKETdGYWtvOXqc24dJbxRXAGLPHw7k7xyRuhZIrP5mWaLWx9ZrZBQ81Hcobn3m0vTcGG-Zw/s580/Screenshot_2015-11-23-06-03-29.png" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKQhYG3URidoYg2B5yGgewi9BIWbFy__cxcp0rixsD7nyqvPSmNRZAkeNNQiH3TF9SeB8SoA0e-qD_m7z3D-TigDGGYUNU2FRP4KS_tfwjInXM5qpkb5wBIX0m9Ix_W6JWr9V1vg/s1600/Screenshot_2015-11-23-06-03-45.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKQhYG3URidoYg2B5yGgewi9BIWbFy__cxcp0rixsD7nyqvPSmNRZAkeNNQiH3TF9SeB8SoA0e-qD_m7z3D-TigDGGYUNU2FRP4KS_tfwjInXM5qpkb5wBIX0m9Ix_W6JWr9V1vg/s580/Screenshot_2015-11-23-06-03-45.png" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoPEpmVVmpDBSD4J7mf8kQBBAf_9-VTb6aOdfzx2HfbV6r7EvbLA-lvCRLTPpKED4XL8PFfP_SFWzUboCAtkPMbL3hrVmLbW9QwufjyVZhzC00yFIpGkveBs3aVCHge8OwJyhpLA/s1600/Screenshot_2015-11-23-06-05-39.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoPEpmVVmpDBSD4J7mf8kQBBAf_9-VTb6aOdfzx2HfbV6r7EvbLA-lvCRLTPpKED4XL8PFfP_SFWzUboCAtkPMbL3hrVmLbW9QwufjyVZhzC00yFIpGkveBs3aVCHge8OwJyhpLA/s580/Screenshot_2015-11-23-06-05-39.png" /></a>
<p>
(Note the URL is: <tt>http://localhost:8081</tt>)
</p>
<p>
<tt>wbox</tt> worked perfectly, and I should be able to leverage this same approach to hosting any local documentation.</p>
<p>
Combine this local web browser approach with <A href='http://www.blogbyben.com/2015/10/its-so-beautiful-emacs-and-chrome-side.html'>Android Multi Window</a>, and you've got a remarkably functional environment.</p>
<p>
I'm one step closer to a full self contained, no-Internet-needed, development environment.</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com3tag:blogger.com,1999:blog-12753102.post-65304939974865806492015-11-19T12:21:00.001-05:002015-11-19T12:21:43.969-05:00Thermaroid: Android + a Thermal Printer = Super Cheap, Super Low Quality Photos on the Fly<p>
<A href='https://github.com/benjisimon/thermaroid'>Thermaroid</a> lives! Today I finished smooshing together my <A href='http://www.blogbyben.com/2015/11/doing-battle-with-and-losing-to-android.html'>Camera API progress</a> with my past success printing to a <a href='http://www.blogbyben.com/2015/02/thermal-nuclear-bluetooth-printing-on.html'>Bluetooth Thermal Printer</a>. The result is a drop dead simple app. The app starts up with absolutely no UI, it's just a live camera preview. Short press on the screen and the camera focuses. Long press the image is captured and sent to the Bluetooth printer. Here's an action shot:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4u2RFrfsN5NbPrdarjyi5wITRY2XGY7w4eo-Z-bRUR6e97nRWxIOaUw5aH3TTvNfRQaD2sOTwkw_e_4M0VVyKqwA6bftJns0xQdX4vi3be9qKE4qnHo2fA9Dhps9LcH8uBiyiGQ/s1600/thermaroid.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4u2RFrfsN5NbPrdarjyi5wITRY2XGY7w4eo-Z-bRUR6e97nRWxIOaUw5aH3TTvNfRQaD2sOTwkw_e_4M0VVyKqwA6bftJns0xQdX4vi3be9qKE4qnHo2fA9Dhps9LcH8uBiyiGQ/s580/thermaroid.png" /></a>
<p>
(Yes, that's a screenshot of me using Thermaroid to take a picture of a picture that I just printed out with Thermaroid. Got that?)
<p>
<p>
The app needs quite a bit of polishing before it's ready for prime time, including: some indication that your photo is being printed and proper code for backgrouding the printing process. But functionality wise, it works.</p>
<p>
I think I'm finally getting the hang of using Kawa Scheme to build apps. Apparently I needed to let go of this notion that I could somehow write Java code using Scheme's terse conventions. Kawa lets you do this a bit, but at the end of the day, things seem to work better (or compile with fewer complaints) when you annotate your code with types. I'm definitely interested in seeing if I can do some refactoring to eek out a bit more elegance than purely translating Java to Scheme. We'll see.</p>
<p>
Check out the code <A href='https://github.com/benjisimon/thermaroid'>here</a>. And happy photo'ing!
</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-83177775309187056522015-11-18T11:30:00.003-05:002015-11-18T11:30:38.640-05:00Doing Battle With, and Losing To, the Android Camera2 API<p>
I'm back to fiddling with with my <a href='http://www.blogbyben.com/2015/02/thermal-nuclear-bluetooth-printing-on.html'>Android Bluetooth Thermal Printer</a>. Specifically, I'm building a small camera app that outputs to the printer directly, rather than saving files on your phone. </p>
<p>Looking at the <a href='http://developer.android.com/reference/android/hardware/Camera.html'>Camera API</a>, I realized that it was now deprecated, so I started building the app using <a href='http://developer.android.com/reference/android/hardware/camera2/package-summary.html'>Camera2</a>. I'm not proud to admit it, but Camera2 beat me. I give up. That's one complete and crazy API to use. That's not a bad thing, it's just not ideal for quick little apps.</p>
<p>
Oh, and all of this is written in <A href='http://www.gnu.org/software/kawa/'>Kawa Scheme</a>. So if you're looking for Scheme Android examples, or how you might invoke the camera from a Scheme app, check out my project's <A href='https://github.com/benjisimon/thermaroid'>repository</a>, hopefully it'll be of some use.</p>
<p>
For now, the app does little more than open up the camera, switch into preview mode and focus when you press the screen. But hopefully with the Camera functionality in place, hooking in my existing <A href='https://github.com/benjisimon/drop-print'>Thermal Printer Code</a> shouldn't be too painful.</p>
<p>
Two gotchas that I overcame:</p>
<p>
<b>1.</b> I was getting the message: <tt>A TextureView or a subclass can only be used with hardware acceleration enabled</tt>, and of course the camera didn't work. I tried <a href='http://stackoverflow.com/questions/9966228/android-textureview-hardware-acceleration-with-lockcanvas'>turning on Hardware Acceleration</a> in the <tt>AndroidManifest.xml</tt>. That made no difference. Ultimately, it was <a href='http://developer.android.com/guide/topics/manifest/application-element.html#hwaccel'>this note</a> that solved the issue:</p>
<blockquote>
The default value is "true" if you've set either minSdkVersion or targetSdkVersion to "14" or higher; otherwise, it's "false".
</blockquote>
<p>
Turns out, I wasn't setting <tt>minSdkVersion</tt> at all. I did so (setting it to 22), and that fixed the issue.</p>
<p>
<b>2.</b> I fired up the camera preview but the screen remained black. There were no messages in the Android monitor so I was baffled. Then it hit me: the camera is lying down on its lens, of course the screen is black. I picked it up, and the camera view showed the correct image. What the heck was I thinking?</p>
<p>
Here's the project if you want to follow along: <A href='https://github.com/benjisimon/thermaroid'>Thermaroid</a>
</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-67753657691195535352015-04-07T14:46:00.003-04:002015-04-07T14:46:52.432-04:00A Little Multi-Radix Programming Fun<p>
I was sucked in by today's Programming Praxis Challenge: <a href='http://programmingpraxis.com/2015/04/07/pounds-shillings-pence/'>Pounds, Shillings, Pence</a>. The goal was to create a couple math functions that worked with mixed radix values (for example, time which is specified in weeks, days, hours, minutes and seconds). Developing the API turned out to be some good fun. The exercise definitely reminded me of my very early days of programming, where you'd be given an assignment to make proper change (damn you pesky quarters, nickles and dimes!) and would have to <tt>div</tt> and <tt>mod</tt> your way to a solution. I recall being thoroughly stumped by these sort of tasks, so perhaps this was my way of slaying a very old dragon?</p>
<p>
I ended up taking a page from Unix, and built my 'system' on the notion of converting multi-radix values to a single integer value. In the time example above, I convert all values to seconds (just like <a href='http://en.wikipedia.org/wiki/Unix_time'>Unix does</a>) to allow for easy math.</p>
<p>
You could hardly call what I put together elegant, but I'm pleased with the results. It almost lets you think about the values you'd like to (in the case below, miles, yards, feet and inches) versus what the computer ideally works in.
<pre>
(define dist '(1760 3 12)); read: (yards-per-mile feet-per-yard inches-per-foot)
(define short (make-mr dist '(5)) ; 5 inches
(define football (make-mr dist '(100 0 0)) ; 100 yards
(define marathon (make-mr dist '(26 385 0 0)) ; 1 marathon
(show (mr-add football marathon))
(show (mr-sub marathon football))
...
</pre>
<p>
And here's the <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/multi-radix.scm'>complete code</a>:
</p>
<pre>
;; Mixed Radix Math --
;; http://programmingpraxis.com/2015/04/07/pounds-shillings-pence/
;;
(define time-spec '(7 24 60 60))
(define dist-spec '(1760 3 12))
(define hms-spec '(60 60))
(define (mr-factors spec)
(let loop ((spec (reverse spec)) (current 1) (result '(1)))
(cond ((null? spec) result)
(else
(let ((x (* (car spec) current)))
(loop (cdr spec) x (cons x result)))))))
(define (mr-normalize spec value)
(cond ((= (length value) (+ (length spec) 1)) value)
((> (length value) (+ (length spec) 1))
(error "Invalid value: " value spec))
(else
(mr-normalize spec (append (list 0) value)))))
(define (mr->int spec value)
(let ((factors (mr-factors spec))
(cleaned (mr-normalize spec value)))
(apply + (map * factors cleaned))))
(define (int->mr spec value)
(let loop ((value value) (factors (mr-factors spec)) (mr '()))
(cond ((null? factors) (reverse mr))
(else
(let* ((f (car factors))
(q (quotient value f))
(r (remainder value f)))
(loop r (cdr factors) (cons q mr)))))))
(define (show . x)
(for-each display x)
(newline))
;;
;; Slightly higher level API
;;
(define (make-mr spec value)
(cons spec value))
(define (mr-spec x) (car x))
(define (mr-value x) (cdr x))
(define (mr-op op)
(lambda (x y)
(let ((xv (mr->int (mr-spec x) (mr-value x)))
(yv (mr->int (mr-spec y) (mr-value y))))
(make-mr (mr-spec x) (int->mr (mr-spec x) (op xv yv))))))
(define mr-add (mr-op +))
(define mr-sub (mr-op -))
(define x (make-mr hms-spec '(3 19 45)))
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-52517547182449939722015-03-19T11:09:00.001-04:002015-03-19T11:09:58.334-04:00The "Funny, It Doesn't Look Like a Linux Server", Server<p>
Check out the cutest edition to our Linux family:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTFAY12AlPCrONp_APZ4rbVa8W9x7UIUeyG1gsCMVKDwIcGymCKS8vDgt5_pCoEWAO6zoXImgdQYkj3xJ4KYN5VC5sN8cWju1MWxHxh8BDnKZfpeb35baK2fvo5e8lyIA3jf0ltw/s1600/tp.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiTFAY12AlPCrONp_APZ4rbVa8W9x7UIUeyG1gsCMVKDwIcGymCKS8vDgt5_pCoEWAO6zoXImgdQYkj3xJ4KYN5VC5sN8cWju1MWxHxh8BDnKZfpeb35baK2fvo5e8lyIA3jf0ltw/s580/tp.jpg" /></a>
<p>
What you're looking at is a <a href='http://www.amazon.com/TP-LINK-TL-WA850RE-Universal-Wireless-Indicator/dp/B00E98O7GC/ref=sr_1_2?s=pc&ie=UTF8&qid=1426772418&sr=1-2&keywords=wifi+extender'>TP-Link TL-WA850RE</a> WiFi range extender. A while back, I was having <A href='http://www.blogbyben.com/2015/01/the-joy-of-wires.html'>WiFi woes</a>, so I picked up this $30 WiFi extender from <a href='http://www.amazon.com/TP-LINK-TL-WA850RE-Universal-Wireless-Indicator/dp/B00E98O7GC/ref=sr_1_2?s=pc&ie=UTF8&qid=1426772418&sr=1-2&keywords=wifi+extender'>Amazon</a>. Turns out, the extender didn't help matters much, so I decided to put it to use in another way.</p>
<p>
I installed <a href='http://openwrt.com/'>OpenWRT</a> on the device. OpenWRT is a Linux distribution designed for routers and the like, and it caught my eye because it had <a href='http://wiki.openwrt.org/toh/tp-link/tl-wa850re'>confirmed support</a> for this particular device. Installing OpenWRT was almost too easy. I grabbed the <a href='http://downloads.openwrt.org/barrier_breaker/14.07/ar71xx/generic/openwrt-ar71xx-generic-tl-wa850re-v1-squashfs-factory.bin'>.bin file</a> (it was in the <tt>ar71xx » generic</tt> subdirectory) and used the <a href='http://ecx.images-amazon.com/images/I/A1dnoE9DPcS.pdf'>upload firmware option</a> that was available in the built in web based UI.</p>
<p>
In just a few minutes I turned this hunk of white plastic into a Linux box, which, well did nothing. Through some small miracle, I was able to hook it up to a cable and telnet to it.</p>
<p>
The first order of business was to configure this device as a WiFi client (or station) rather than the default configuration of being an access point. My hope that was once the device was in client mode, I could plug it into the wall in a random spot in our house, it would then boot up and I'd be able to telnet/ssh to it.</p>
<p>
I found <A href='http://h-wrt.com/en/mini-how-to/wifi_openwrt'>this</a> and <A href='http://wiki.openwrt.org/doc/recipes/routedclient#uschemeingmasquerade'>this</a> article handy is setting up client mode on the device. However, it was ultimately <a href='wiki.openwrt.org/doc/recipes/routedclient#usingmasquerade '>this bit of advice</a> that made all the difference:</p>
<blockquote>
If the target network uses the 192.168.1.0/24 subnet, you must change the default LAN IP address to a different subnet, e.g. 192.168.2.1 .
You can determine the assigned WAN address with the following command: ...
</blockquote>
<p>
I had wanted to setup the <tt>lan</tt> (wired side) of the device to have a static IP and the <tt>wan</tt> (WiFi side) to have a DHCP picked up IP. It wasn't obvious, but attempting to have both the static IP and dynamic IP be on the same network caused it to fail. The static IP would be set, but the WiFi side wouldn't ever be properly configured. Here's the configuration that ended up working for me:</p>
<pre>
# /etc/config/wireless
config wifi-device 'radio0'
option type 'mac80211'
option channel 'auto'
option hwmode '11g'
option path 'platform/ar934x_wmac'
option htmode 'HT20'
option disable '0'
config wifi-iface
option device 'radio0'
option network 'wan'
option mode 'sta'
option ssid 'SSID_TO_CONNECT_TO_GOES_HERE' # [1]
option encryption 'wep'
option key 'PASSWORD_GOES_HERE_SEE_BELOW' # [2]
# /etc/config/network
config interface 'loopback'
option ifname 'lo'
option proto 'static'
option ipaddr '127.0.0.1'
option netmask '255.0.0.0'
config interface 'lan'
option ifname 'eth0'
option force_link '1'
option proto 'static'
option ipaddr '192.168.2.75' # [3]
option netmask '255.255.255.0'
# /etc/config/firewall
# ... trimmed ...
config zone
option name wan
list network 'wan'
list network 'wan6'
option input ACCEPT # [4]
option output ACCEPT
option forward REJECT
# ... trimmed ...
</pre>
<p>
Some notes from above:</p>
<p>
[1] - This is where you specify your router's SSID to connect up with<br/>
[2] - For WEP encryption I entered a hex value here, versus text. I used <a href='http://www.einhorn-net.de/jstools/wepkey.html'>this site</a> to do the conversion.<br/>
[3] - This was key: my router will give a 192.168.1.x IP, so this needs to be off that network.<br/>
[4] - Once I got everything set up, I was getting a <tt>connection refused</tt> message when trying to telnet to the server. The <tt>wan</tt> firewall needed to be changed to allow access
</p>
<p>
Once this all got hashed out, I was able plug the device into a random spot on the wall and telnet to it. Success! And yet, where do I go from here?
<p>
Obviously this is useful for educational purposes. I've already had to brush up on my basic networking skills to get this far, and there's plenty more to learn. Heck, you could use this $30.00 router to learn about life on the command line and generally how to be a Unix geek.</p>
<p>OpenWRT, however, is more than just a learning platform. There's a large number of <a href='http://downloads.openwrt.org/barrier_breaker/14.07/ar71xx/generic/packages/packages/'>software packages</a> available, and they can be installed using <a href='http://wiki.openwrt.org/doc/techref/opkg'>opkg</a> with ease. Turning this bad boy into a web server or the like should be easy enough. I was even able to install a version of <A href='https://code.google.com/p/sigscheme/'>scheme</a>, by grabbing an older <tt>sigscheme</tt> package:</p>
<pre>
root@pipsqueak:/# opkg install http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk
Downloading http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk.
Installing sigscheme (0.8.3-2) to root...
Configuring sigscheme.
root@pipsqueak:/# sscm
sscm> (map (lambda (x) (* x 9)) '( 1 2 3 4 5 6))
(9 18 27 36 45 54)
sscm> (exit)
</pre>
<p>
Ultimately, what will make this useful is if I can find an application for the device that leverages its near invisible profile and dirt cheap price. If I was in the <a href='http://en.wikipedia.org/wiki/Red_team'>security business</a>, or a nerd-action-novel writer, then the uses would be pretty obvious. Walk in, plug in device, walk out. And bam! you've got a server that can try to worm it's way onto the network. But for myself, I'm going to have to think a little more on this. Perhaps the device should live in my car? Or maybe it'll be useful in a hotel room? Not sure, but the technology is just too cool to ignore.
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-17065353674422492352015-02-25T08:41:00.002-05:002015-02-25T08:41:13.339-05:00Adventures in Dithering: Making some gray in a sea of black and white<p>
Yesterday I implemented support for <a href='http://www.blogbyben.com/2015/02/dropprint-20-image-and-qr-code-support.html'>printing images</a> in my <a href='https://github.com/benjisimon/drop-print/'>DropPrint Android app</a>. One issue with the printer is the range of values it prints: mainly it has none. As they say: <a href='http://en.wikiquote.org/wiki/Henry_Ford'>you can have any color you want, as long as it's black</a>. So a typical photo, which is filled with all sorts of grays, gets turned in a photo filled only with black and white. Like this one:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDnm6UVem-XzYlMzFLtxFrLByAVcjXThqu_FTOJqN-7fDXEJtWVfks-8Y4WI0fRiRwUXsn6qBocbmZsPZSjC05dF0IeJX1E7yXrVyIjrDpkR-pKmv-57_tdsrWKQLqqF-SnNwzsQ/s1600/20150225_075448.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDnm6UVem-XzYlMzFLtxFrLByAVcjXThqu_FTOJqN-7fDXEJtWVfks-8Y4WI0fRiRwUXsn6qBocbmZsPZSjC05dF0IeJX1E7yXrVyIjrDpkR-pKmv-57_tdsrWKQLqqF-SnNwzsQ/s320/20150225_075448.jpg" /></a>
<p>
In some cases this effect may be desirable, but I was curious if I could leverage the <a href='http://en.wikipedia.org/wiki/Halftone'>halftone</a> effect to simulate shades of gray. With a halftone you trick the eye into seeing gray by by varying the mixture of white and black dots. One Google search told me that while halftoning may get the job done, <a href='http://stackoverflow.com/questions/1258047/algorithm-to-make-halftone-images'>there's another important option to consider</a>:</p>
<blockquote>
If you are doing this because you like the effect, that's cool. But if you just want to dither down to a black and white image consider using a "Floyd-Steinberg" dither. It provides high quality results and distributes the error across the image. <a href='http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering'>http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering</a>
</blockquote>
<p>
The <a href='http://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering'>Floyd–Steinberg dithering</a> looked exactly like what I wanted, and the Wikipedia page even gave me an algorithm I could translate to scheme code:</p>
<pre>
(for-each-coord src-w src-h
(lambda (x y)
(let* ((old-pixel (rgb->gray (pixels (idx x y))))
(new-pixel (if (> old-pixel 128) 255 0))
(quant-error (- old-pixel new-pixel)))
(store! x y new-pixel)
(update! (inc x) y (* quant-error (/ 7 16)))
(update! (dec x) (inc y) (* quant-error (/ 3 16)))
(update! x (inc y) (* quant-error (/ 5 16)))
(update! (inc x) (inc y) (* quant-error (/ 1 16))))))
</pre>
<p>
After fixing <tt>update!</tt> so it wouldn't try to update pixels outside of the image (I'm looking at you <tt>(-1, 1)</tt>), I was surprised at the quality of the image generated. Here's the same image as above, but with dithering in place:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4hivcV-S7fEmNqd6oGms7kmJHNVImAECBT0dBWkZlZB5enrPaREzxd32Y8gbAy3V_4EAPqfctmJmTCio_-XRWImA3Km7NHViT3BSJCruJAg7cHO9F-gqDiRYwyV-kpD3epgzHfg/s1600/20150225_075455.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4hivcV-S7fEmNqd6oGms7kmJHNVImAECBT0dBWkZlZB5enrPaREzxd32Y8gbAy3V_4EAPqfctmJmTCio_-XRWImA3Km7NHViT3BSJCruJAg7cHO9F-gqDiRYwyV-kpD3epgzHfg/s320/20150225_075455.jpg" /></a>
<p>
Look at that, there's now some "gray" in the image!</p>
<p>
I'm not sure what to make of the white vertical bars. They are almost certainly a defect in code as I've printed other images that don't have them.</p>
<p>
The main issue I have with this algorithm is that it's terribly slow. Dithering a 384x447 pixel image takes almost 30 seconds, with the vast majority of that time spent looping over every pixel in the image. I'm sure I'm doing something inefficient, though it's possible that I'm running into a performance issue with Kawa Scheme. At some point, I'll probably debug it further and see why it's so slow.
</p>
<p>
Next up: I've got to see if I can get rid of those annoying white bars and then I need to make the Bluetooth connectivity far more bullet proof. When that's done,I should have a pretty dang functional app.</p>
<p>
As usual, the DropPrint source code can be found <A href='https://github.com/benjisimon/drop-print/'>here</a>.
</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com2tag:blogger.com,1999:blog-12753102.post-42289014634853911772015-02-24T08:37:00.000-05:002015-02-24T08:37:47.000-05:00DropPrint 2.0: Image and QR Code Support<p>
This morning I finished up the next iteration of <a href='https://github.com/benjisimon/drop-print/'>DropPrint</a>, a tiny Android app that drives a <a href='http://www.blogbyben.com/2015/02/thermal-nuclear-bluetooth-printing-on.html'>thermal bluetooth printer</a>. The big improvements: DropPrint now supports images as well as bar codes.</p>
<p>
Check it out:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOBku0XEozL3HrQZdzaqFescAYhtN5BxhlbTeyo0Od3xgpa_oNbT6YYzUPZ5OiEQJI-dtnqKCEFRgOPiqfY-OShl1cyB99miRr2ZnLHWn2hSdyboYTTO-yN7hfaZkPTt7zXhsRIg/s1600/20150224_065136.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhOBku0XEozL3HrQZdzaqFescAYhtN5BxhlbTeyo0Od3xgpa_oNbT6YYzUPZ5OiEQJI-dtnqKCEFRgOPiqfY-OShl1cyB99miRr2ZnLHWn2hSdyboYTTO-yN7hfaZkPTt7zXhsRIg/s320/20150224_065136.jpg" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAcNPQwuOAiOOtEeFRJ7BEMHkDeTHL5-o3iskRBt2M-mzDft8Kfle3eakJ1e6KLfr0IkMWNTs_PJ7nMuwpJYCWfEm3gEaQRl2T8fbIlXYIVYjIU3kRJWSZDvExQkVrZcuskzspZw/s1600/20150224_080317.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAcNPQwuOAiOOtEeFRJ7BEMHkDeTHL5-o3iskRBt2M-mzDft8Kfle3eakJ1e6KLfr0IkMWNTs_PJ7nMuwpJYCWfEm3gEaQRl2T8fbIlXYIVYjIU3kRJWSZDvExQkVrZcuskzspZw/s320/20150224_080317.jpg" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1N1USYILWrh4rb8vBJ9OLu6jztKoppYHrAyOUsyAAjubKYGFbmro5XbZ9UXsh9NcVzHUTFbDlbL8O_28l89oEOsBoGeZUV2_-H2aXk1DlTjZUBxNg7XRmN76UR6pVfoog5_GONw/s1600/20150224_080759.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1N1USYILWrh4rb8vBJ9OLu6jztKoppYHrAyOUsyAAjubKYGFbmro5XbZ9UXsh9NcVzHUTFbDlbL8O_28l89oEOsBoGeZUV2_-H2aXk1DlTjZUBxNg7XRmN76UR6pVfoog5_GONw/s320/20150224_080759.jpg" /></a>
<p>
The image printing protocol for the printer I'm using, a DL58, is pretty dang simple. It consists of little more than sending each row of an image with the following format:</p>
<pre>
0x1F 0x10 NN 0x00 B1 B2 B3 ...
</pre>
<p>
Where <tt>NN</tt> is the number of bytes being sent to represent the line of the image. <tt>B1</tt>, <tt>B2</tt>, etc. are bytes containing the relevant bits (0 black, 1 white) for each pixel. In other words, if my image was 1 pixel high and 8 pixels wide (I know, not a particularly interesting image):</p>
<pre>
Black Black Black White White White Black White
</pre>
<p>
I'd send this as:</p>
<pre>
0x1F 0x10 0x01 0x0 [00011101]
</pre>
<p>
It through me off at first, but that binary header (<tt>0X1F 0x10 ...</tt>) is sent at the start of each row, not just at the start of the image.</p>
<p>
This whole mapping of image pixels to individual bits, followed by compressing the bits into bytes, was an interesting exercise to say the least. Not being much of a hardware interface guy, these are usually details I'm not worrying about. An interesting side effect of printer's binary protocol is that the height of the image is effectively irrelevant. All the printer knows about are the individual rows of the image. I'm using this to my advantage in DropPrint by rotating images that are taller than they are wider. The result is that especially narrow or wide images, like a panoramic shot, actually do well on the printer.</p>
<p>
One obvious issue with the printer is that it only prints black and white, there's no ability to send any sort of gray pixels. The result is that your typical photograph, filled with not-quite-black-not-quite-white areas, looks awful when printed. Still, there's hope. The notion of the <a href='http://en.wikipedia.org/wiki/Halftone'>halftone</a> was invented to solve exactly this problem. Invented back in the 1830's, it's hardly new tech. The idea is to simulate gray by interspersing black and white dots. Just like our brains can be fooled into seeing fluid movement using the principles of animation, we can also be fooled into seeing gray when only black and white is present. Anyway, this is an area I'll be coming back to.</p>
<p>
With the basic image printing ability out of the way adding <a href='http://www.blogbyben.com/2009/04/qr-code-coolness.html'>QRCode</a> support was quite easy. I grabbed the <A href='https://github.com/zxing/zxing'>zxing library</a> and put it it to work. Now when DropPrint discovers a <tt>.qrc</tt> file, it encodes the text found within as a QR Code and prints that.</p>
<p>
Next up: I'll work on improving the image printing quality as well as improving how the app handles being put in the background and losing connection to the printer. Still lots to do, but it's amazing when this guy prints out an image I've sent to it.</p>
<p>
Check out the source code <a href='https://github.com/benjisimon/drop-print/'>here</a>.
</p>Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-30676382270498711502015-02-23T08:01:00.000-05:002015-02-23T08:01:09.325-05:00Just a Little Impossible: Morris Counting<p>
I'll often advise <a href='http://www.ideas2executables.com'>entrepreneurs I talk with</a> that it's ideal if their Software Idea is just a <i>little impossible</i>. <a href='http://programmingpraxis.com/2015/02/20/morris-counting/'>ProgrammingPraxis</a> recently published a challenge / solution that fits this description well. It's quirky, but still instructive. Here's my own word-problem based description of the <A href='http://programmingpraxis.com/2015/02/20/morris-counting/'>challenge</a>:</p>
<blockquote>
Imagine you're given the task at counting entrants to the state fair (<a href='http://www.travelwisconsin.com/blog/fairs-festivals/wisconsin-state-fair-favorite-food-on-a-stick'>yum!</a>). Your boss hands you one of those <a href='http://www.webclicshoppingmall.com/products_pictures/TL123P.JPG'>crowd counter</a> devices and walks away. As you examine the counter you realize that it only counts up to 255. Once the 256th person walks in, your screwed. The counter won't work anymore.</p>
</blockquote>
<p>
What do you do? Pray that the state fair has 254 attendees? Flee for your life? If you're <A href='http://en.wikipedia.org/wiki/Approximate_counting_algorithm'>Robert Morris</a>, you get creative and devise a new way of counting, one that solves this seemingly impossible problem.</p>
<p>
Here's what you do: you borrow a coin from your fellow fair employees and you stand by the gate. The first time someone walks in, you click the counter. Now it reads one. The next time someone walks you, you look down at the counter and flip the coin however many times is shown on its face. If your coin comes up heads every time, then you click the button to increment the counter. And repeat.</p>
<p>
So if the counter says 8, then you have to flip the coin 8 times in a row. And if you get heads 8 times (unlikely, but do it enough, and it'll happen), you increment the counter to 9.</p>
<p>
When your boss comes by and asks how many people visited the fair you bust out your pocket calculator compute <tt>2<sup>x</sup>-1</tt>, where <tt>x</tt> is the number shown on the counter.</p>
<p>
Of course, this won't be the exact number of people who visited the fair, but it will be in the ballpark. It'll certainly tell you if there were 10's, 100's or 1000's of visitors that day. And that's far better data than having nothing.</p>
<p>
Here's some random executions of the this algorithm:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJEg4ylOe0zcKBGYCEKe8-cLBgWH5XBOqV-rgdbDgo7LODDGCcs0S_vIfJ1DevykWq8ooL5hDOpfZU-5VeBNxmL8PcCOqO5D-fyB4saAmD_p-sQBeD_-M50YvtBuirhYoIexrVGQ/s1600/Screenshot_2015-02-23-06-12-58.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJEg4ylOe0zcKBGYCEKe8-cLBgWH5XBOqV-rgdbDgo7LODDGCcs0S_vIfJ1DevykWq8ooL5hDOpfZU-5VeBNxmL8PcCOqO5D-fyB4saAmD_p-sQBeD_-M50YvtBuirhYoIexrVGQ/s580/Screenshot_2015-02-23-06-12-58.png" /></a>
<p>
In some cases, the number is pretty accurate (524 was estimated at 511, 242 was estimated at 255). In other cases, it's pretty out there (2956 vs. 4095). But still, considering that you're making use of nothing more than a very limited counter and a single coin, the results are quite impressive.</p>
<p>
The bigger lesson though is the recipe at play here: find a problem which others think is impossible, solve it, and you're on your way to changing the world. That's not too much to ask, is it?</p>
<p>
Here's the code that implements the above algorithm:</p>
<pre>
;;
;; http://programmingpraxis.com/2015/02/20/morris-counting/
;;
(define (show . words)
(for-each display words)
(newline))
(define (heads? n)
(let ((flip (= 1 (random-integer 2))))
(cond ((not flip) #f)
((and flip (= n 1)) #t)
(else (heads? (- n 1))))))
(define (int-count n)
(+ 1 n))
(define (morris-count c)
(cond ((= c 0) 1)
((heads? c) (int-count c))
(else c)))
(define (morris-value c)
(- (expt 2 c) 1))
(define (trial upper)
(let loop ((n (random-integer upper))
(i 0)
(c 0))
(cond ((= n 0)
(show "actual=" i ", morris=" (morris-value c)))
(else
(loop (- n 1)
(int-count i)
(morris-count c))))))
(define (test)
(for-each trial '(10 50 100 200 500 800 1000
1500 2000 5000 7000 10000)))
</pre> Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com7tag:blogger.com,1999:blog-12753102.post-23311448559588650812015-02-12T08:56:00.000-05:002015-02-12T08:56:24.928-05:00Thermal Nuclear Bluetooth Printing on Android (minus the nuclear part)<p>
Inspired by this <a href='http://www.blogbyben.com/2015/01/instant-photos-on-very-cheap.html'>photography idea</a>, I picked up a thermal Bluetooth printer from eBay. Specifically, a model <a href='http://www.ebay.com/itm/281517589767?_trksid=p2057872.m2749.l2649&ssPageName=STRK%3AMEBIDX%3AIT'>DL58</a>. I was impressed with the Chinese company that sold it to me; my request for access to the SDK was immediately and fully met. While I've got big plans for the printer, the first order of business was to get it printing basic text.</p>
<p>
I don't really have any experiencing developing with Bluetooth devices, so I wasn't quite sure what I was in for. Thankfully, the device was discovered and paired with my phone without a hitch (pairing PIN: <a href='https://www.youtube.com/watch?v=a6iW-8xPw3k'>1234</a>). The first version of the SDK the eBay seller provided had the printing code wrapped up behind a shared native library. When I couldn't get this to work, the eBay seller provided an updated version of the code. This time, I could see that all the system was doing was making a Bluetooth socket connection to the device and sending text over the socket. Well that's easy enough. The printer does handle images too, and those are sent using some sort special binary header. That's something I'll be figuring out soon enough.</p>
<p>
I then went to work taking my new found lessons in Bluetooth printing and turning them into a super simple app. I give you: <A href='https://github.com/benjisimon/drop-print'>DropPrint</a>. DropPrint watches the directory <tt>/sdcard/DropPrint</tt> and when new files are discovered it prints them. Right now, DropPrint only understands two types of file: <tt>txt</tt> and <tt>scm</tt> files. I plan to also have it support image files, as well as bar code files (store "foo" in foo.qrc, and a qrcode with the contents "foo" get printed).</p>
<p>
There's not much to DropPrint, but here's the requisite screenshot:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNwP37sB5RhbiCsRhC6q2kdVE2VIrPONp2uo88KUy9Cd2YLxJ3utTTpFaZuEyG4KVXrjrqiaaECPHdk-xbmgiXbXfeCrjflOxtum3cyaDJsOclVvUbipu22pyi_e-48K1yV8TVUQ/s1600/Screenshot_2015-02-11-11-39-50%5B1%5D.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNwP37sB5RhbiCsRhC6q2kdVE2VIrPONp2uo88KUy9Cd2YLxJ3utTTpFaZuEyG4KVXrjrqiaaECPHdk-xbmgiXbXfeCrjflOxtum3cyaDJsOclVvUbipu22pyi_e-48K1yV8TVUQ/s580/Screenshot_2015-02-11-11-39-50%5B1%5D.png" /></a>
<p>
DropPrint's handling of <tt>txt</tt> files is obvious enough. But surely you're wondering what a <tt>scm</tt> file are all about. Well, it is what you think it is: Scheme file handling.</p>
<p>
See, I implemented <a href='https://github.com/benjisimon/drop-print'>DropPrint</a> in <a href='https://www.gnu.org/software/kawa/Android-view-construction.html'>Kawa Scheme</a>. That makes it trivial to <tt>read</tt>, <tt>eval</tt> and literally print <tt>scm</tt> files. For example, I can drop the following code in <tt>DropPrint/fib.scm</tt>: </p>
<pre>
(begin
(define (dec x) (- x 1))
(define (fib x)
(cond ((= x 0) 1)
((= x 1) 1)
(else
(+ (fib (dec x)) (fib (dec x))))))
(let loop ((i 0))
(cond ((= i 10) 'done)
(else
(display i)
(display " = ")
(display (fib i))
(newline)
(loop (+ i 1))))))
</pre>
<p>
A few moments later, the printer spits out the following:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgb1Cou8n7hz2mwNOjWiUhzqxI6KaqVUHk2MlzKo1QQgMDyCvtNNv8Ja7kMb7OaKEpcy_pzGevV6z4af7Kz7F1Rpe3pzRarPJsxu_1Im0jSEyNGTz_SgPGX-2Mq_Dd14bplXPqivg/s1600/20150211_101033.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgb1Cou8n7hz2mwNOjWiUhzqxI6KaqVUHk2MlzKo1QQgMDyCvtNNv8Ja7kMb7OaKEpcy_pzGevV6z4af7Kz7F1Rpe3pzRarPJsxu_1Im0jSEyNGTz_SgPGX-2Mq_Dd14bplXPqivg/s580/20150211_101033.jpg" /></a>
<p>
(Beware: it intentionally deletes the files after printing them)
</p>
<p>
In the bits-and-bytes world I live in, to actually have something physical generated is amazingly cool.</p>
<p>
As implementation languages go, I'm very much warming up to Kawa. It's certainly far more satisfying to use for this sort of project than say <a href='http://phonegap.com/'>PhoneGap</a>, which has a huge number of layers to get to (HTML, JavaScript, PhoneGap code and core Java Code to name a few) before you can work with core Android APIs. I'm not yet sure I can make the case that Kawa is generally better for app development then Java itself, though, with time I'm sure I'll get there. I'm certainly finding it a heck of a lot of fun to program in.</p>
<p>
Now that I've got basic printing working, it's time to turn my attention to images. Stay tuned...</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com2tag:blogger.com,1999:blog-12753102.post-72186122580110014002015-02-05T22:05:00.000-05:002015-02-06T03:13:25.288-05:00Sounds awful, but it's all mine - Adventures in programmatic music generation<p>
A few years ago I discovered the <a href='http://www.blogbyben.com/2011/11/rtttl-simplest-and-most-hackable-sound.html'>RTTTL</a> "music format." RTTTL, as a quick refresher, was a language used to exchange ring tones. Essentially it's a <A href='http://en.wikipedia.org/wiki/Ring_Tone_Transfer_Language'>text file that lists out which notes to play</a>; couldn't be simpler. The textual nature of it means that it's trivial to generate songs using any programming language.</p>
<p>
Yesterday evening I had about 3 hours on the train to kill. I had planned to work on my Laptop but the "free" WiFi was apparently maxed out by passengers who had the same idea. So I put the laptop away, busted out the Bluetooth Keyboard and started to brainstorm as to how I could use Scheme to generate sweet, sweet music.</p>
<p>
I can tell you that I fully missed the mark on the "sweet, sweet" part. But I did manage to use Scheme to generate RTTTL files, which in turn played on my mobile device. I ended up implementing a series of functions to generate Morse Code from arbitrary text, as well as a function to generate a random song. Here, give a listen to some samples:</p>
<iframe width="100%" height="200" scrolling="no" frameborder="no" src="https://w.soundcloud.com/player/?url=https%3A//api.soundcloud.com/playlists/78535968&auto_play=false&hide_related=false&show_comments=true&show_user=true&show_reposts=false&visual=true"></iframe>
<p>
The Morse Code needs tuning to be truly accurate, and the "random songs" my program generates are more like random noise. But this is hardly a loss. I've always been curious what an algorithm might be that would generate at least a passable tune, and now I've got the toolkit to experiment with this.</p>
<p>
I've included my source code below, and you can grab it from github <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/rtttl.scm'>here</a>.
</p>
<p>
One feature of RTTTL is that your phone, for historic reasons, probably plays it without needing a special application. The flip side of this, though, is that finding a way to play the RTTTL files outside of your phone is non-trivial. I looked all over Google Play for an app that would convert my RTTTL file to a .wav or .mp3 file, but had no luck. Your typical music player and music publication site (I'm looking at you, <a href='http://soundcloud.com'>soundcloud</a>) is going to be clueless as to what an RTTTL file is. Luckily, I was able to find a recipe that works for converting from RTTTL to .wav. Here it is:</p>
<ul>
<li>Install the <a href='http://search.cpan.org/dist/SMS-Ringtone-RTTTL-MIDI/'>SMS-Ringtone-RTTTL-MIDI</a> perl module</li>
<li>Grab this script I <A href='https://github.com/benjisimon/code/blob/master/rtttltomidi'>prepared</a> to leverages this module to create a MIDI file</li>
<li>Install some MIDI related tools, including <tt>timidity++</tt> and <tt>fluidsynth</tt></li>
</ul>
<p>
Once the above steps are taken care of, you can convert <tt>foo.rtttl</tt> to <tt>foo.wav</tt> by using the following sequence:</p>
<pre>
rtttltomidi < foo.rttl > foo.midi
timidity foo.midi # listen to your creation
fluidsynth -F foo.wav /usr/share/sounds/sf2/default.sf2 foo.mid
</pre>
<p>
That last step was inspired by this <A href='http://wootangent.net/2010/11/converting-midi-to-wav-or-mp3-the-easy-way/'>post</a>, which also goes on to explain how to convert the <tt>.wav</tt> to <tt>.mp3</tt>.
</p>
<p>
Getting these libraries together sounds tricky, but on my new Linux box the whole process was surprisingly painless.</p>
<p>
OK, so now it's your turn. Go off and write some code which in turn writes some amazing music!
</p>
<hr/>
<pre>
;;
;; RTTTL - let's generate some sounds. Below we generate both
;; Morse Code and a random "song"
;;
(define (&& . any)
(apply string-append
(map (lambda (x)
(cond ((number? x) (number->string x))
((symbol? x) (symbol->string x))
(else x)))
any)))
(define (implode sep parts)
(let loop ((parts parts) (accum '()))
(cond ((null? parts) (apply && accum))
(else
(loop (cdr parts)
(if (null? accum)
(list (car parts))
(append accum (list sep (car parts)))))))))
(define (string-head text)
(substring text 0 1))
(define (string-tail text)
(substring text 1 (string-length text)))
(define (explode sep text)
(let loop ((text text) (current "") (accum '()))
(cond ((equal? text "")
(if (equal? current "")
(reverse accum)
(reverse (cons current accum))))
((equal? (string-head text) sep)
(loop (string-tail text)
""
(cons current accum)))
(else
(loop (string-tail text)
(string-append current (string-head text))
accum)))))
(define (rtttl title notes)
(string-append title ":d=4,o=5,b=160:" notes "\n"))
(define (save filename contents)
(call-with-output-file (string-append "/sdcard/Documents/" filename)
(lambda (out)
(display contents out))))
(define morse-map
'((a ".-") (b "-...") (c "-.-.") (d "-..") (e ".")
(f "..-.") (g "--.") (h "....") (i "..") (j ".---")
(k ".-.-") (l ".-..") (m "--") (n "-.") (o "---")
(p ".-.-") (q "--*-") (r ".-.") (s "...")
(t "-") (u "..-") (v "...-") (w ".-") (x "-..-")
(y "-.--") (z "--..")))
(define (morse-char c)
(let ((needle (string->symbol (string (char-downcase c)))))
(cond ((eq? c #\space) " ")
((assoc needle morse-map) => cadr)
(else (morse-char #\x)))))
(define (morse-word text)
(let ((chars (map morse-char (string->list text))))
(implode "|" chars)))
(define (morse-string text)
(let ((words (explode " " text)))
(implode "_" (map morse-word words))))
(define (morse-notes encoded)
(let loop ((chars (string->list encoded)) (accum '()))
(cond ((null? chars)
(implode "," (reverse accum)))
(else
(loop
(cdr chars)
(cons
(case (car chars)
((#\.) "c5")
((#\-) "a7")
((#\|) "p")
((#\_) "p,p,p"))
accum))))))
(define (morse-rtttl message)
(rtttl message (morse-notes (morse-string message))))
(define (string-reverse text)
(apply string
(reverse (string->list text))))
(define (range low high)
(if (> low high) '() (cons low (range (+ 1 low) high))))
(define (random-elt items)
(list-ref items (random-integer (length items))))
(define (random-between low high)
(+ low (random-integer (- high low))))
(define (random-note)
(let ((note (random-elt '(c c c c d d e f g a p)))
(len (random-elt '(1 2 4 8 16)))
(oct (random-elt '(5 6))))
(if (eq? note 'p)
(&& len note)
(&& len note oct))))
(define (random-name)
(&& (random-note) (random-note) (random-note) (random-note)))
(define (random-notes)
(implode
","
(map (lambda (i)
(random-note))
(range 0 (random-integer 100)))))
(define (make-buffer)
(let ((buffer '()))
(lambda (x)
(if (equal? x 'get)
(implode "," (reverse buffer))
(set! buffer (cons x buffer))))))
(define (random-song)
(let ((chorus (random-notes))
(buffer (make-buffer)))
(for-each (lambda (i)
(buffer (random-notes))
(buffer chorus))
(range 1 (random-between 5 10)))
(buffer (random-notes))
(rtttl "Music By Scheme" (buffer 'get))))
(save "hw.rtttl" (morse-rtttl "Hello World"))
(save "sos.rtttl" (morse-rtttl "SOS"))
(save "random.rtttl" (random-song))
</pre>Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-11918403189426910242015-01-12T15:13:00.003-05:002015-01-12T20:24:35.619-05:00The Most Powerful Computer You'll Never Own<p>
Inspired by the movie the <a href='http://www.blogbyben.com/2015/01/review-imitation-game.html'>Imitation Game</a>, I just had build my own <a href='http://en.wikipedia.org/wiki/Turing_machine'>Turing Machine</a> (I know, I should have built <A href='http://www.lysator.liu.se/~koma/turingbombe/bombe.html'>one of these</a>! Some day). While folks have built actual <a href='http://aturingmachine.com/'>physical machines</a>, I took the programmer's way out and made mine strictly virtual.</p>
<p>
A Turing Machine is the <a href='https://martinugarte.com/static/pdf/what_is_a_turing_machine.pdf'>theortical device</a> Alan Turing devised in his <a href='http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf'>1936 paper</a> on computability. To this day, Computer Science students are made to <a href='http://www.cse.buffalo.edu/courses/cse396/content/turing.pdf'>do battle with this machine</a> and the theories that stem from it.</p>
<p>
While it's been years since I've done any CS homework that involved Turing Machines, I can't recall actually ever implementing one. What a shame.</p>
<p>
The web is filled with such simulators including: <a href='http://morphett.info/turing/turing.html'>here</a>, <a href='http://www.turing.org.uk/turing/scrapbook/tmjava.html'>here</a> and <a href='https://martinugarte.com/turingmachine/'>here</a>. These were invaluable for refreshing my memory as to how a Turing Machine operates.</p>
<p>
Implementing a <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/turing-machine.scm'>Turing Machine</a> was oddly satisfying. One has to contend with the fact that a program handed to a Turing Machine may never complete. I dealt with this by allowing the user to execute the machine in terms of blocks of cycles. So you create the machine, run it for 100 cycles, and if you want, run it 100 more.</p>
<p>
Here's the code to create a machine. The program is actually <a href='http://en.wikipedia.org/wiki/Turing_machine_examples#Turing.27s_very_first_example'>Alan Turing's first example</a>:</p>
<pre>
(define r1 '(((b _) (c 0 >))
((c _) (e _ >))
((e _) (f 1 >))
((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))
</pre>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhf1unZShd8UGYDLxeaDRYj0baOd-wEOSKrHYV8XOjuBEe7w-9SRacjXheQuffKJHJFXMOqpGWruADUzkzfynm3OWFnrJaPy_34yIVsJmSQMZ26boZoCEqZRgUoUBimTG_LDng0SA/s1600/Screenshot_2015-01-12-10-00-33.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhf1unZShd8UGYDLxeaDRYj0baOd-wEOSKrHYV8XOjuBEe7w-9SRacjXheQuffKJHJFXMOqpGWruADUzkzfynm3OWFnrJaPy_34yIVsJmSQMZ26boZoCEqZRgUoUBimTG_LDng0SA/s580/Screenshot_2015-01-12-10-00-33.png" /></a>
<p>
The rules specified by <tt>r1</tt> are in the format: </p>
<pre>
(((current-state current-symbol) (new-state new-symbol new-direction))
...)
</pre>
<p>
Invoking <tt>make-tm</tt> creates the new Turing Machine. You provide as arguments the initial state, initial tape-contents, list of halting states and the transition rules.</p>
<p>
Once you've got the machine (<tt>tm1</tt>, above), you can invoke it with an integer to say how many cycles of the machine should execute (e.g., <tt>(tm1 10)</tt>).</p>
<p>
Scheme truly shined as a host language: I was trivially able to make the machine operate on arbitrary states and tape contents. Also sexpr's were ideal for defining the state transition rules.</p>
<p>
All of this may seem fairly unimpressive until you ponder <a href='http://ironphoenix.org/tm/help/basics.shtml'>this thought</a>:</p>
<blockquote>
However odd it may sound for so simple a machine, the Turing Machine is the most powerful computing model known to computer scientists. In this context, "powerful" refers only to what it is capable of doing, not to how fast or efficiently it does it. It has been proven that a TM is capable of performing any computation that a modern computer can, given enough time. Infact, it is technically MORE powerful than modern computers, since it has no storage limitations.
</blockquote>
<p>
Here's the <A href='https://github.com/benjisimon/code/blob/master/programming-praxis/turing-machine.scm'>complete source code</a> for my simulator.</p>
<p>
<font color='red'>Update:</font> <a href='http://programmingpraxis.com/2009/04/03/programming-the-turing-machine/'>Programming Praxis</a> tackled the Turing Machine almost 5 years ago. I've updated my code below with their <A href='http://programmingpraxis.com/2009/04/03/programming-the-turing-machine/'>example</a>.
</p>
<pre>
; A Turing Machine Impl
(define (range lower upper)
(if (>= lower upper) '()
(cons lower (range (+ 1 lower) upper))))
(define (show . words)
(for-each display words))
(define tape-cell '#(_))
(define tape-padding '#(_ _ _ _ _))
(define (make-tape contents)
(cons 0 (vector-append (list->vector contents) tape-padding)))
(define (tape-head t)
(car t))
(define (tape-items t)
(cdr t))
(define (tape-read t)
(vector-ref (tape-items t) (tape-head t)))
(define (tape-write t x)
(vector-set! (tape-items t) (tape-head t) x)
t)
(define (tape-move t direction)
(let ((index (+ (tape-head t)
(case direction
((< L) -1)
((> R) 1)
((- N) 0)
(else (error "Unknown tape movement: " direction))))))
(cond ((= index -1)
(set-cdr! t (vector-append tape-cell (tape-items t)))
(set! index 0))
((= index (vector-length (tape-items t)))
(set-cdr! t (vector-append (tape-items t) tape-padding))))
(set-car! t index)
t))
(define (display-tape t)
(for-each (lambda (i)
(let ((v (vector-ref (tape-items t) i)))
(cond ((= i (tape-head t))
(show "[" v "]"))
(else (show v)))
(show " ")))
(range 0 (vector-length (tape-items t)))))
(define (tm-find state tape rules)
(let ((needle (list state (tape-read tape))))
(let loop ((rules rules))
(cond ((null? rules) #f)
((equal? needle (caar rules)) (cadar rules))
(else
(loop (cdr rules)))))))
(define (make-tm initial-state initial-tape halting-states rules)
(let ((state initial-state)
(tape (make-tape initial-tape)))
(lambda (cycles)
(let loop ((cycle 0))
(show state ": ")
(display-tape tape)
(newline)
(cond ((= cycle cycles) #t)
((member state halting-states) state)
((tm-find state tape rules) =>
(lambda (dest)
(let* ((new-state (car dest))
(new-symbol (cadr dest))
(new-direction (caddr dest)))
(set! state new-state)
(tape-write tape new-symbol)
(tape-move tape new-direction)
(loop (+ 1 cycle)))))
(else 'no-matching-rules))))))
; Binary Counting - http://aturingmachine.com/examples.php
(define r0 '(((walk 0) (walk 0 >))
((walk 1) (walk 1 >))
((walk _) (count _ <))
((count 0) (walk 1 >))
((count 1) (count 0 <))
((count _) (walk 1 >))))
(define tm0 (make-tm 'walk '(0) '() r0))
; Turing's First Example
; http://en.m.wikipedia.org/wiki/Turing_machine_examples
(define r1 '(((b _) (c 0 >))
((c _) (e _ >))
((e _) (f 1 >))
((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))
; http://programmingpraxis.com/2009/3/27/a-turing-machine-simulator/
(define r2 '(((0 1) (0 1 R))
((0 +) (1 1 R))
((1 1) (1 1 R))
((1 _) (2 _ L))
((2 1) (H 1 N))))
(define tm2
(make-tm 0
'(1 1 1 + 1 1 1 1)
'(H)
r2))
</pre>Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-52938948995525149642014-12-08T08:07:00.000-05:002014-12-08T08:07:13.557-05:00Trigraphs, Diana Pads and Zombies<p>
I'm browsing this guy's <a href='https://www.zombiehunters.org/forum/viewtopic.php?f=14&t=72858'>zombie response kit</a> when I noticed this item here:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiy9oSljK7nSiHj0c2-mJSs48I8GZiOX0r5Hyz0lE7_EbP_zDYuHskYcRXDsDx3F61Ed9cu0yDgXEjzTIMbIYjVl7rT7dRXsJ3GRJ0A0CoF_MYhx3vSi5NKaRYsns0iAlKFue6pFQ/s1600/tri-graph.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiy9oSljK7nSiHj0c2-mJSs48I8GZiOX0r5Hyz0lE7_EbP_zDYuHskYcRXDsDx3F61Ed9cu0yDgXEjzTIMbIYjVl7rT7dRXsJ3GRJ0A0CoF_MYhx3vSi5NKaRYsns0iAlKFue6pFQ/s580/tri-graph.png" /></a>
<p>
This naturally raises the questions: (a) what's a tri-graph and (b) how does it help with "clandestine" communications?</p>
<p>
Of course, the Internet explains: a <a href='http://danmorgan76.wordpress.com/2013/09/30/encryption-via-a-one-time-pad/'>tri-graph</a> (or is it trigraph?) is a lookup table used in One Time Pad (OTP) encryption. One example of an OTP are pages and pages of random text. If you and I have copies of the same one time pad, then we can use a tri-graph as <a href='http://get-urban-survival-skills.blogspot.com/2011/03/urban-survival-planning-basic-message.html'>follows</a>:</p>
<p>
1. Pick a line in the OTP (known as our key text). Say:
</p>
<pre>
<b>VAXPM IPIXU QUXIP MAXIU</b>
</pre>
<p>
2. Write the clear text below it:
</p>
<pre>
VAXPM IPIXU QUXIP MAXIU
<b>MEETA TTENT ONIGH TXXXX</b>
</pre>
<p>
(that's: <i>meet at 10 tonight</i>)
</p>
<p>
3. For each letter, look up the key text and plain text character in
the trigraph and find the resulting encrypted text.</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6_wIOuVbsg-swKCYmZFjhJoUyDgwogqVgrIzJVO_afnK8nEPVm3n_pPwp_yftf3pZ5UbDc-hGZHOvusEyZaFseN8VduiwvIS0i-MatsgnHjLMa0uouEe4C5IG30BYhmWjqewiww/s1600/trigraph.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6_wIOuVbsg-swKCYmZFjhJoUyDgwogqVgrIzJVO_afnK8nEPVm3n_pPwp_yftf3pZ5UbDc-hGZHOvusEyZaFseN8VduiwvIS0i-MatsgnHjLMa0uouEe4C5IG30BYhmWjqewiww/s580/trigraph.jpg" /></a>
<pre>
VAXPM IPIXU QUXIP MAXIU
MEETA TTENT ONIGH TXXXX
<b>SVYRN YRNPM VSULD UCFUI</b>
</pre>
<p>
Because of the symmetric nature of the tri-graph, I can decode the text using the same procedure. That is, if I look up a key and encrypted letter, I will arrive and the decoded letter.</p>
<p>
That may seem like a neat parlor trick, but the fact is, the above encryption is actually quite strong. In fact, assuming that the pads are truly randomly generated, never reused and never compromised the system is <a href='http://militaryradio.com/spyradio/otp.html'>unbreakable</a>.</p>
<p>
One use case for the above system was during the <a href='http://www.vietnamgear.com/Article.aspx?Art=47'>Vietnam War</a>:</p>
<blockquote>
Special Forces were one of (if not the only) units in Vietnam to utilize Morse code on a regular basis. We used a method of encryption called the Diana Cryptosystem.<br/>
<br/>
The basis of these "One-Time Pads", is that there were only two matching pads in existence, and they would only be used one time. They were booklets that contained randomly generated groups of 5-letter "words;” 30 words to a page. The person sending a message would first write the letters to the message, over these random groups of words. Included in the front of each one-time pad was a one-page encryption table. If I wanted to send the letter "P", and the letter under the "P" was an "A", then I would send a "K". The person listening on the frequency at the other end, would have the other matching pad. They would write the letter they received (a "K") over the letter in their one-time pad (an "A"), and decipher it based on the table, yielding the original letter "P".<br/>
<br/>
Each communication site in Vietnam (we had over 100 A-Camps along the Cambodian / Laotian border, and some 20 B-detachment sites spread over the country) had a different pad, depending on the location they were having the commo-check with. It obviously was very important that both people were using the appropriate matching pads, or the deciphered messages would not make any sense.<br/>
<br/>
After a while, most of us became so proficient with the system, that we actually learned the deciphering matrix by heart. No matter what pads anyone had, the combinations always were the same. i.e. Any 3 letters always went together, regardless of the order; "BKO"/"KOB"/"OBK"/"BOK". After listening to thousands and thousands of transmissions, it really got quite simple. If I was listening to code, and a letter "B" was sent (now remember, we usually sent around 20-25 "words" (5 letters per word) a minute, hence the importance of the "speed" keys!), and the letter it was associated with was an "O", most of us would decipher as we heard it, and just write the "K". That may sound like quite a yarn, but it is absolutely true.
</blockquote>
<p>
That's my kind of solution: simple enough that a a soldier can manually execute the encryption and send it over Morse Code, yet sophisticated enough that the code was effectively unbreakable. </p>
<p>
Naturally, I had to experiment with this encryption, and of course, write some code to make it easier to play with. You can find the code <A href='https://github.com/benjisimon/code/blob/master/programming-praxis/diana-pad-encryption.scm'>here</a>, or copied below. The code provides two top level function: <tt>make-pad</tt> which generates characters for a one time pad and <tt>tri-lookup</tt> which does the tri-graph lookup:</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3cv7oYNC3Ykc9pBvU4A_67dteb1fK54KjxmznZctsE33pcRo9g4gWAZ_o76_IbGJmGV0vrnsZnj-9JvYIZU_xJ7KV_01Ps6kg798l_Qm1NKCrqfcfiRrXD3VdyG10tWqJ2qKKzA/s1600/Screenshot_2014-12-08-07-37-47%5B1%5D.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3cv7oYNC3Ykc9pBvU4A_67dteb1fK54KjxmznZctsE33pcRo9g4gWAZ_o76_IbGJmGV0vrnsZnj-9JvYIZU_xJ7KV_01Ps6kg798l_Qm1NKCrqfcfiRrXD3VdyG10tWqJ2qKKzA/s580/Screenshot_2014-12-08-07-37-47%5B1%5D.png" /></a>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjUItAArB2h_TQU9XQO9Ruop0SbEA0GiTY5R5HJ4-QYEG03zw-Gc8jIWz4L8jgl63e7HqvPgJPdcNXpjnlazGFXdZMLZp5Jm2HFktzRUQoEd7-W4i0uVE-rqwkJpH2xxjWEmJk8zw/s1600/Screenshot_2014-12-08-07-38-52%5B1%5D.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjUItAArB2h_TQU9XQO9Ruop0SbEA0GiTY5R5HJ4-QYEG03zw-Gc8jIWz4L8jgl63e7HqvPgJPdcNXpjnlazGFXdZMLZp5Jm2HFktzRUQoEd7-W4i0uVE-rqwkJpH2xxjWEmJk8zw/s580/Screenshot_2014-12-08-07-38-52%5B1%5D.png" /></a>
<p>
(In the session above, <tt>k</tt> is the key text and <tt>p</tt> is the plain text)
</p>
<p>
Thinking more about this form of encryption, it's remarkable how practical it could be. For example, if both my wife and I had a business card sized piece of paper packed with random characters, we could send dozens of short messages to each other using the above technique. Furthermore, any stream of text that we agree upon could be used as a key. While random text would be ideal, technically any string of characters would work. We could use song lyrics, the 5th paragraph from the 2nd story on the 3rd page of the New York Times, street names from a map, ingredients on a shampoo bottle, etc. Heck, you could even incorporate the clue to the key in the messages. For example:</p>
<pre>
K541 8151 Z781 0742 AI06 PU72 EBXBH HGOXU
</pre>
<p>
Where <tt>K541 8151 Z781 0742 AI06 PU72</tt> corresponds to <A href='https://twitter.com/velolassie/status/541815178107420672'>tweet 541815178107420672</a> (the spaces and letters are meant to throw off attackers).</p>
<p>
Of course, straying from randomized text definitely weakens the setup. I wouldn't want to protect state secrets or call in an air strike using these short-cuts. But, this would work for leaving a romantic note to my wife or other less than sensitive message.</p>
<p>
At the end of the day, I suppose the most important question is: does a tri-graph belong in your zombie fighting kit? Heck yeah! It also belongs in your kids play fort setup, and teenager's clandestine communication kit.</p>
<hr/>
<pre>
;;
;; Implement a version of One Time Pad encryption.
;; Use a trigraph / diana pad method
;; http://danmorgan76.wordpress.com/2013/09/30/encryption-via-a-one-time-pad/
;; http://home.earthlink.net/~specforces/spdiana.htm
;;
(define (a->i letter)
(- (char->integer letter) 65))
(define (i->a index)
(integer->char (+ 65 index)))
(define (rand-char)
(i->a (random-integer 26)))
(define (range low high)
(if (> low high) '() (cons low (range (+ 1 low) high))))
(define (head items)
(let loop ((i 0) (items items) (accum '()))
(cond ((or (null? items) (= i 5)) (reverse accum))
(else
(loop (+ i 1) (cdr items) (cons (car items) accum))))))
(define (tail items)
(reverse (head (reverse items))))
(define (make-pad rows cols)
(define (make-block)
(apply string (map (lambda (i) (rand-char)) (range 1 5))))
(define (make-row)
(for-each (lambda (i)
(if (> i 1) (display " "))
(display (make-block)))
(range 1 cols)))
(for-each (lambda (i)
(make-row) (newline))
(range 1 rows)))
(define (tri-row i)
(reverse (map (lambda (pos)
(i->a (modulo (- pos i) 26)))
(range 0 25))))
(define (tri-lookup key plain)
(let loop ((key (string->list key))
(plain (string->list plain))
(coded '()))
(cond ((null? plain) (apply string (reverse coded)))
((equal? #\space (car plain))
(loop (cdr key) (cdr plain)
(cons #\space coded)))
(else
(let ((row (a->i (car plain)))
(col (a->i (car key))))
(loop (cdr key) (cdr plain)
(cons (list-ref (tri-row row) col) coded)))))))
(define k "ASDFA POUYK")
(define p "HELLO WORLD")
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com3tag:blogger.com,1999:blog-12753102.post-10148392678981831072014-11-18T06:34:00.001-05:002014-11-18T06:34:43.494-05:00Cramming Darwin into My Cell Phone<p>
My father, a Professor of Biology, is fond of telling his students (and children): <a href='http://www.blogbyben.com/2011/06/how-to-watch-my-dads-brain-melt.html'>Darwin is always in the room</a>. The idea, as he's explained to me, is that the basic elements of evolution (competition, mutation, adaptation, selection, etc.) are present in all biological processes, no matter how big or small. So if Darwin can be in the room, why not in my computer?</p>
<p>
I give you the latest exercise from Programming Praxis: <a href='http://programmingpraxis.com/2014/11/14/dawkins-weasel/'>Dawkin's Weasel</a>. This exercise requires that you implement the basic constructs of evolution in code:
<blockquote>
I don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?<br/>
...</br>
We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.
</blockquote>
<p>
Writing the prescribed algorithm was easy enough. You can find the complete source code <a href='https://github.com/benjisimon/code/blob/master/programming-praxis/dawkins-weasle.scm'>here</a> and the highlights below. Writing the code efficiently, on the other hand, turned out to be more elusive. My version creeps along, taking about 25 minutes to produce an answer. Why the sluggishness? I could blame it on the fact that I'm running it on an <a href='http://www.blogbyben.com/2014/09/are-we-there-yet-writing-and-running.html'>interpreter on my phone</a>, but really, it's slow because I haven't take the time to make it fast. Still, after exactly 333 successive generations the system went from pure randomness to the target phrase (on run #2, it only took 211 generations to produce the right match). Slow and steady, that seems appropriate for the topic anyway.</p>
<p>
As a programmer, I can't help but marvel at how simple and effective this algorithm is. By providing two key elements: (a) a way to introduce change and (b) a way to score the results, I'm able to write code that finds a solution even though I have no idea what the ideal path to producing that solution is. It's no surprise that there's a whole area of programming dedicated <a href='http://www.geneticprogramming.com/Tutorial/'>to this approach</a>.</p>
<p>
While I think this exercise nicely demonstrates some key aspects of evolution, my favorite experiment on the topic is still <a href='https://www.youtube.com/watch?v=8Bd3Ch8ME50'>this one</a>. In this case, the power of mutation (a key ingredient for evolution) is shown using the act of tracing a single vertical line. Spoiler alert: all those tiny errors introduce when a person tries and fails to copy the line exactly turn into significant changes. The results are pretty staggering. If you want to skip all the chit chat, and just see the effect in action, check out <a href='http://vimeo.com/18998570'>this video</a>.</p>
<p>
And here's the code for our computer monkeys:</p>
<pre>
; http://programmingpraxis.com/2014/11/14/dawkins-weasel/
;
; requires sort from:
; https://raw.githubusercontent.com/benjisimon/code/master/programming-praxis/dawkins-weasle.scm
(define goal (string->list "METHINKS IT IS LIKE A WEASEL"))
(define (range low high)
(if (> low high) '()
(cons low (range (+ 1 low) high))))
(define (rand-char)
(let ((offset (random-integer 27)))
(if (= offset 26) #\space
(integer->char (+ 65 offset)))))
(define (mutate input)
(map (lambda (x)
(let ((rand (random-integer 100)))
(if (< rand 5) (rand-char) x)))
input))
(define (score input)
(let loop ((value 0) (input input) (goal goal))
(cond ((null? input) value)
(else
(loop (if (equal? (car input) (car goal))
(+ 1 value) 0)
(cdr input) (cdr goal))))))
(define (bang)
(map (lambda (c) (rand-char)) goal))
(define (tick input)
(let ((attempts
(sort (map (lambda (i) (mutate input)) (range 1 100))
(lambda (x y)
(> (score x) (score y))))))
(car attempts)))
(define (solve)
(let loop ((generation 0) (input (bang)))
(cond ((equal? goal input) generation)
(else
(display (list generation (score input))) (newline)
(loop (+ 1 generation)
(tick input))))))
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-4952406459540073762014-10-29T09:19:00.001-04:002014-10-29T09:25:30.397-04:00Praise for Siri and a quick (and surprisingly satisfying) mobile version of Eliza<p>
My friend (and <A href='http://www.amazon.com/Christian-Cantrell/e/B0040Y98T6'>famous author!</a>) <A href='http://www.livingdigitally.net/'>Christian Cantrell</a> posted a touching story on <A href='https://plus.google.com/+ChristianCantrell/posts/Bx7stgatSba'>Google Plus</a>: <a href='http://www.nytimes.com/2014/10/19/fashion/how-apples-siri-became-one-autistic-boys-bff.html?_r=0'>To Siri, With Love: How One Boy With Autism Became BFF With Apple’s Siri</a>. It's more than worth your time to read. However, a quick take on it is it that Siri has a number of attributes that make it an excellent companion for the author's Autistic Son(for example: Siri doesn't mind talking minutia for hours, and her gentle corrections help teach important social skills).</p>
<p>
Besides this being another <i>see, technology can be a force for good in people's lives!</i> article, it got me thinking about chat bots in general. And no discussion of chat bots is complete without a mention of <a href='http://www.alicebot.org/articles/wallace/eliza.html'>Eliza</a>, Siri's great-great-great-great-great grandmother. Eliza was a "doctor" who could psychoanalyze you using little more than a set of text matching rules. Still, it managed to give the impression of <a href='http://www.alicebot.org/articles/wallace/eliza.html'>true intelligence</a>.</p>
<p>
With Eliza on the brain, I started wondering how tricky it would be to implement an Eliza clone for my phone. Turns out, not tricky at all. Here's what I did.</p>
<p>
First, I cheated and grabbed <a href='http://dave-reed.com/csc533.S10/Code/eliza.scm'>this implementation of Eliza</a> in Scheme. Yes, I should have written my own. Heck one day, I probably will.</p>
<p>
Next, I wrote some wrapper functions around that code to make it accept arbitrary string input:</p>
<pre>
(define random random-integer)
(define (eliza-scrub text)
(define (valid-char? c)
(let ((v (char->integer c)))
(or (equal? c #\space)
(and (>= v 97) (<= v 122)))))
(let* ((chars (string->list text))
(lower (map char-downcase chars))
(valid (filter valid-char? lower)))
(apply string valid)))
(define (eliza-it text)
(let ((input (map string->symbol (explode " " (eliza-scrub text)))))
(implode " "
(apply-rule ELIZA-RULES input))))
</pre>
<p>
I then busted out my <a href='http://www.blogbyben.com/2014/10/web-apply-turn-your-android-phone-into.html'>web-apply</a> framework, and attached this function to the local URL: <tt>http://localhost:9000/doc</tt>:</p>
<pre>
(tcp-service-register!
(list server-address: "*"
port-number: 9000
eol-encoding: 'cr-lf)
(web-fn-dispatcher `(("/doc" . (,eliza-it #t)))))
</pre>
<p>
At this point, I could visit the URL in my browser and have a crude discussion with Eliza. But it's hardly the feel I was after. Next up, I turned to <A href='http://www.blogbyben.com/search/label/tasker'>Tasker</a> and created this quick Task:</p>
<pre>
Eliza (40)
A1: Get Voice [ Title:Talk to the Doctor Language ]
A2: If [ %VOICE eq bye ]
A3: Say [ Text:Good bye ]
A4: Else
A5: HTTP Get [ Server:Port:http://localhost:9000
Path:/doc
Attributes:p0=%VOICE output=display ]
A6: Say [ Text:%HTTPD ]
A7: Goto [ Type:Action Number Number:1 ]
</pre>
<p>
The magic is in the Tasker action <tt>Get Voice</tt>. This prompts a user to say something which is then turned into text and stored in <Tt>%VOICE</tt>. The action <tt>Say</tt> does the reverse, taking arbitrary text and speaking it aloud. Finally, there's the web invocation of <tt>http://localhost:9000/doc</tt> which actually executes the above Eliza code.</p>
<p>
While the above code is more fragile than I'd like (you need to explicitly bind the the <tt>eliza-it</tt> function to a port and path), it's also surprisingly effective. The whole experience is voice driven and feels remarkably powerful. It definitely brings back the magic of Eliza that had secretaries and staff confiding in it so long ago.</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com1tag:blogger.com,1999:blog-12753102.post-64435801348790543682014-10-28T11:17:00.000-04:002014-10-28T11:17:25.003-04:00web-apply - Turn your Android Phone into an itty bitty Scheme app server<p>
Checkout screenshots of my latest "web app" :</p>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgW1Pld0aJLHgArbxFS-M4iI28LBwqwIHfN2x71c4Sapqk52pvr2PphQ6edAvEhPjbWCJRGRT3TRzZ-jQ417C1vzsBh7Tqz048BhNlGKRFz8ZyC19ANhHUE0zLnOeS9hUxshtEmCA/s1600/Screenshot_2014-10-24-10-09-16.png.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgW1Pld0aJLHgArbxFS-M4iI28LBwqwIHfN2x71c4Sapqk52pvr2PphQ6edAvEhPjbWCJRGRT3TRzZ-jQ417C1vzsBh7Tqz048BhNlGKRFz8ZyC19ANhHUE0zLnOeS9hUxshtEmCA/s580/Screenshot_2014-10-24-10-09-16.png.jpg" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIhW4Qz8ELxE16EQgKEHmX3a-FUo1IdvXQZOlnXMonQEAZ47VEX7jmbAD35oU3lSF95cYo-CcinBbRdr13vYQOhuLmgdbxzCMqPHk_0ZfvzTyKSRHcIjp31NAJBN7pBESwk6Y-0A/s1600/Screenshot_2014-10-24-10-10-00.png.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIhW4Qz8ELxE16EQgKEHmX3a-FUo1IdvXQZOlnXMonQEAZ47VEX7jmbAD35oU3lSF95cYo-CcinBbRdr13vYQOhuLmgdbxzCMqPHk_0ZfvzTyKSRHcIjp31NAJBN7pBESwk6Y-0A/s580/Screenshot_2014-10-24-10-10-00.png.jpg" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdDVQTSb0NGjwjW481FNF-yNRa5nZFVyyGCafv2NSBNefXAlcW6GnsISXfEiY0xOWTe01bU7f5ko7402Z4TBhcpyp39wBDWbdvY83ixMzPIKYe1TfHQejzgZ3vJgBTLATOhTlPNg/s1600/Screenshot_2014-10-24-10-10-51.png.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdDVQTSb0NGjwjW481FNF-yNRa5nZFVyyGCafv2NSBNefXAlcW6GnsISXfEiY0xOWTe01bU7f5ko7402Z4TBhcpyp39wBDWbdvY83ixMzPIKYe1TfHQejzgZ3vJgBTLATOhTlPNg/s580/Screenshot_2014-10-24-10-10-51.png.jpg" /></a>
<p>
Pretty lame, right? Perhaps not, allow to me to explain.</p>
<p>
What you're looking at are some interactions with <A href='https://github.com/benjisimon/code/tree/master/web-apply'>web-apply</a>, a crude framework for binding arbitrary Scheme functions to a web page. Here's how it works. First, you start with any old functions. Here's three toy ones:</p>
<pre>
(define (string-reverse x)
(apply string
(reverse (string->list x))))
(define (tip-calc amt)
(map (lambda (percent)
(cons percent (exact->inexact (+ amt (* (/ percent 100) amt)))))
'(10 15 20)))
(define (random-within x y)
(+ x (random-integer (- y x))))
</pre>
<p>
Then you bind these functions to a particular port and path:</p>
<pre>
(tcp-service-register!
(list server-address: "*"
port-number: 9000
eol-encoding: 'cr-lf)
(web-fn-dispatcher `(("/rev" . (,string-reverse #t))
("/tip" . (,tip-calc number))
("/rand" . (,random-within number number)))))
</pre>
<p>
<tt>tcp-service-register!</tt> is built into <a href='http://www.iro.umontreal.ca/~gambit/doc/gambit-c.html#Network-devices'>Gambit Scheme</a> and takes care of accepting TCP connections. <tt>web-fn-dispatcher</tt> implements trivial HTTP handling and allows for interaction with a browser. The framework has one more trick up it's sleeve: you can pass an <tt>output</tt> parameter to declare how you want the output rendered. By default, a basic HTML page is generated, though you can pass in <tt>display</tt> or <tt>write</tt> to output the content using the aptly named Scheme function.</p>
<p>
And here's the cool part: this framework was built in, and explicitly runs on <A href='http://www.blogbyben.com/2014/09/are-we-there-yet-writing-and-running.html'>Gambit Scheme on Android</a>. So the above bindings effectively turn my cell phone into a resource an arbitrary user can browse to and interact with.</p>
<p>
So why bother writing <tt>web-apply</tt>? I'm glad you asked. Here are three reasons:</p>
<ol>
<li><tt>web-apply</tt> demonstrates just how powerful Gambit Scheme is on Android. Threads and sockets <i>Just Work</i>, including the ability to <a href='http://www.iro.umontreal.ca/~gambit/doc/gambit-c.html#Debugging-example'>debug</a> at the REPL. Combined with <A href='http://www.blogbyben.com/2014/09/are-we-there-yet-writing-and-running.html'>Droid Edit</a>, you can really get creative and program dang near anything.</li>
<li>If I try hard enough, I can imagine a circumstance where a team of individuals would want quick and dirty access to interact with some code, and <tt>web-apply</tt> gives you exactly this.</li>
<li><tt>web-apply</tt> should play nice with <a href='http://www.blogbyben.com/search/label/tasker'>Tasker</a>, as Tasker allows for easy execution of HTTP requests. This should allow you to code a task mainly using Tasker's standard environment, but jump into the Scheme world when it's convenient.</li>
</ol>
<p>
Of course, this should be considered alpha level code. But it's fun alpha level code, so feel free to <A href='https://github.com/benjisimon/code/tree/master/web-apply'>play around</a> with it.</p>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0tag:blogger.com,1999:blog-12753102.post-28162520413254213902014-10-21T07:45:00.001-04:002014-10-22T20:48:18.578-04:00Ancient Laptops and being a Heroic Boyfriend - Text Formatting inspired Stories<p>
You might think a topic like <A href='http://programmingpraxis.com/2014/10/07/text-formatting/'>text formatting</a> would be pretty bland. Not so! I have not one, but two stories inspired by the topic. Allow me to share.</p>
<p>
I can remember it vividly: I'm 13 years old and working away on my very own laptop. Specifically, a <a href='http://www.obsoletecomputermuseum.org/nec8500/'>NEC PC-8500</a>, with a whopping 64K (yes kilobytes!) of RAM. I'm typing up an essay for school in the <a href='http://www.slate.com/blogs/future_tense/2014/05/14/george_r_r_martin_writes_on_dos_based_wordstar_4_0_software_from_the_1980s.html'>WordStar</a> word processor and having a heck of a time. Specifically, the paragraphs are all askew, with some lines being shorter than others. In the end, I'm left fighting with the computer trying to get the different lines to have somewhat equal length. What a pain.</p>
<p>
Looking back, I was running into a fairly classic text formatting problem. Either WordStar had automatic word wrap and I was defeating it by hitting enter at the end of some lines, or it had a manual function to refill paragraphs that I didn't know how to operate. All I know is, this is one of my earliest memories of software appearing to be buggy, but actually performing as designed. Little did I know that I'd pretty much make this fight my life's work by becoming a programmer. Now, on a nearly daily basis I look at software and think "hmmm, it can't possibly be behaving that way...." And yet, it almost always is. And usually it's my fault!</p>
<p>
Fast forward from middle school to college for the second story. I'm on <a href='http://en.wikipedia.org/wiki/Talk_%28software%29'>Unix Talk</a> with my long-distance girlfriend, and she starts telling me about the arduous task in front of her. She's manually re-formating a massive final lab report. It's taking her forever to adjust each line to the right length. I finally convince her to send me a copy. A minute or two later she receives it back, perfectly formatted. How'd I work this bit magic? Why thanks to the <a href='http://linux.about.com/library/cmd/blcmdl_fmt.htm'>Unix fmt command</a>.</p>
<p>
You may be thinking, big deal, you formatted some text. Turns out, it was a big deal. That girlfriend is now my wife of almost <s>16</s> 17 years. And when I started describing the story a few days ago, she immediately started mentioning details I'd forgotten. That little bit of unix-manship, is probably in the top 10 list of amazing things I've done for my wife. Never underestimate the power of the command line.</p>
<p>
In honor of both those stories, I give you a <A href='https://github.com/benjisimon/code/blob/master/programming-praxis/text-formatting.scm'>Scheme implementation</a> of <tt>fmt</tt>. Incidentally, this answers the first part of the <A href='http://programmingpraxis.com/2014/10/07/text-formatting/'>Programming-Praxis Challenge</a>, I've still got the <a href='http://programmingpraxis.com/2014/10/10/formatting-text-again/'>second part</a> to complete.</p>
<pre>
; http://programmingpraxis.com/2014/10/07/text-formatting/
(define (empty? str)
(= (string-length str) 0))
(define (++ . args)
(apply string-append
(map
(lambda (any)
(cond ((string? any) any)
((number? any) (number->string any))
((char? any) (string any))))
args)))
(define (g options key . default)
(cond ((assoc key options) => cdr)
(else (if (null? default)
(error "Missing default: " key options)
(car default)))))
(define (read-token port)
(let loop ((buffer ""))
(let ((c (peek-char port)))
(cond ((eof-object? c)
(if (empty? buffer)
(cons 'eof (read-char port))
(cons 'word buffer)))
((equal? c #\newline)
(if (empty? buffer)
(cons 'newline (read-char port))
(cons 'word buffer)))
((equal? c #\space)
(if (empty? buffer)
(begin (read-char port) (loop buffer))
(begin (read-char port) (cons 'word buffer))))
(else
(loop (++ buffer (read-char port))))))))
(define (output line port opts)
(let* ((width (g opts 'width 60))
(align (g opts 'align 'left))
(delta (- width (string-length line))))
(case align
((left) (display line port))
((right)
(display (make-string delta #\space) port)
(display line port))
((center)
(display (make-string (floor (/ delta 2)) #\space) port)
(display line port)))
(newline port)))
(define (handle-word word buffer out width loop opts)
(let ((line (if (empty? buffer) "" (++ buffer " "))))
(if (> (string-length (++ line word)) width)
(begin
(output buffer out opts)
(loop word))
(begin
(loop (++ line word))))))
(define (fmt in out opts)
(call-with-input-file in
(lambda (pin)
(call-with-output-file out
(lambda (pout)
(format pin pout opts))))))
(define (format in out opts)
(let ((width (g opts 'width 60)))
(let loop ((buffer ""))
(let ((next (read-token in)))
(case (car next)
((eof) (output buffer out opts))
((word)
(handle-word (cdr next) buffer out width loop opts))
((newline)
(let ((peek (read-token in)))
(case (car peek)
((newline)
(output buffer out opts)
(newline out)
(loop ""))
((eof) (output buffer out opts))
((word)
(handle-word (cdr peek) buffer out width loop opts))
(else (error "Unknown peek token:" peek)))))
(else (error "Unknown token:" next)))))))
(define in "/sdcard/Documents/input.txt")
(define out "/sdcard/Documents/output.txt")
(define opts '((width . 30)))
(define (range low high)
(let loop ((i low) (result '()))
(if (> i high) (reverse result)
(loop (+ 1 i) (cons i result)))))
(define-macro (repeat qty . body)
`(for-each
(lambda (i) ,@body) (range 1 ,qty)))
</pre>
Ben Simonhttp://www.blogger.com/profile/09833753747177544979noreply@blogger.com0