(Link) Insufficiently known POSIX shell features by apenwarr.

Do not sort the category “Other” under “O”.

For a project I'm considering, I took a few hours to see if I could write a working garbage collector.

This is a very bare-bones copying GC, written without any reference to How To Do It Properly (just my knowledge of how a copying GC works, but I believe it is mostly cleanly written other than (a) the hardcoded pointer comparisons for object layouts, and (b) support for exactly one GC root, which happens to be the object at the lowest address. (It also calls a “heap” that which I believe is conventionally called a “space”. And I suppose someone could take issue with my placements of casts and void *s.)

The test program simply allocates a structure containing the strings “Hello” and “world”, allocates a bunch of junk, and then prints the strings to show that they are still intact.

Has anything been done in logic programming (especially in languages not too far from the classic Prolog) which is analogous to monads and the IO monad in Haskell; that is, providing a means of performing IO or other side-effects which does not have the programmer depend on the evaluation/search order of the language?

In other words, what is to Prolog as Haskell is to ML?

Varychase is a graphics toy I just published. Runs in the browser; wave your mouse around and it makes curly patterns.

I originally wrote the option-less version May 29, 2010; yesterday I finally got around to adding a bunch of stuff, polishing the presentation, and publishing it.

It uses <canvas> for the optional line-drawing (I should compare the performance to using SVG instead, as well as also putting the dots in the canvas), and a few miscellaneous HTML5/CSS3 features for optional refinements. I've tested in Safari, Chrome, and Firefox on Mac.

James@Waterpoint (Xplat on Freenode) mentioned an interesting problem: write an elegant point-free expression to compute the diagonal of a list of lists (that is, from [[00, 01, 02, ...], [10, 11, 12, ...], ...] obtain [00, 11, ...]).

His version:

diag = (map head) . (foldr (flip ((flip (:)) . (map tail))) [])

My version, which needs a non-pointfree helper function (but one which others have invented before, and perhaps ought to be in the standard libraries), but has fewer flips:

import Control.Arrow ((***))
import Data.List (unfoldr)

uncons xs = case xs of (x:xs') -> Just (x,xs'); [] -> Nothing
diag = unfoldr (fmap (head *** (map tail)) . uncons)

uncons is sort of the opposite of unfoldr, in that unfoldr uncons = id.

Update: darius's version, from the comments:

diag = flip (zipWith (!!)) [0..]

I forget why I wrote this Haskell program, but it's cluttering up my do-something-with-this folder, so I’ll just publish it.

-- This program calculates all the ways to combine [1,2,3,4] using + - * / and ^
-- to produce *rational* numbers (i.e. no fractional exponents). (It could be so
-- extended given a data type for algebraic numbers (or by using floats instead
-- of exact rationals, but that would be boring).)
--
-- Written September 7, 2009.
-- Revised August 25, 2010 to show the expressions which produce the numbers.
-- Revised August 26, 2010 to use Data.List.permutations and a fold in combine.
-- 
-- In the unlikely event you actually wants to reuse this code, here's a license
-- statement:
-- Copyright 2009-2010 Kevin Reid, under the terms of the MIT X license
-- found at http://www.opensource.org/licenses/mit-license.html

I'd include the output here, but that would spam several aggregators, so I'll just show some highlights. The results are listed in increasing numerical order, and only one of the expressions giving each distinct result is shown.

(1 - (2 ^ (3 ^ 4))) = -2417851639229258349412351
(1 - (2 ^ (4 ^ 3))) = -18446744073709551615
(1 - (3 ^ (2 ^ 4))) = -43046720
(1 - (4 ^ (3 ^ 2))) = -262143
(1 - (4 ^ (2 ^ 3))) = -65535
...all integers...
((1 - (2 ^ 4)) * 3) = -45
(((1 / 2) - 4) ^ 3) = -343/8
((1 - (3 ^ 4)) / 2) = -40
(1 - ((3 ^ 4) / 2)) = -79/2
(1 - ((3 ^ 2) * 4)) = -35
...various short fractions...
(1 / (2 - (3 ^ 4))) = -1/79
(((1 + 2) - 3) * 4) = 0
(1 / (2 ^ (3 ^ 4))) = 1/2417851639229258349412352
(2 ^ (1 - (3 ^ 4))) = 1/1208925819614629174706176
(1 / (2 ^ (4 ^ 3))) = 1/18446744073709551616
(2 ^ (1 - (4 ^ 3))) = 1/9223372036854775808
(2 ^ ((1 - 4) ^ 3)) = 1/134217728
...various short fractions...
(((3 ^ 2) + 1) ^ 4) = 10000      (the longest string of zeros produced)
...all integers...
(2 ^ (3 ^ (1 + 4))) = 14134776518227074636666380005943348126619871175004951664972849610340958208
(2 ^ ((1 + 3) ^ 4)) = 115792089237316195423570985008687907853269984665640564039457584007913129639936
Tried 23090 formulas, got 554 unique results.

• A remarkable feature: “Settings → About phone → Battery use” claims to give a breakdown of energy use over the last period the phone was unplugged. It distinguishes between “Display”, “Cell standby”, “Android System”, and applications. Don't know how accurate it is.

• Bluetooth keyboard driver experiences:

  • “BlueInput” by Teksoft does not work correctly for my Palm Bluetooth Keyboard; as others have reported, some punctuation keys do not work at all (and Shift-2 generates ", making me think that it was written for a different keyboard layout and not tested with US QWERTY).
  • “BlueKeyboard JP” failed to connect to my keyboard — or rather, it immediately says “disconnected”. Also, the install permissions info says it reads GPS location, which makes no sense unless this is one of those ad-supported things, but it doesn't say that and I don’t remember whether it did show ads. Update: It works, but the keyboard must be discoverable. And it is ad-supported.

  So I still don't have a keyboard driver. Perhaps I should look into writing one.

• I need to learn about how file/application associations work so I can figure out who is at fault (file browser or viewer app) in my failing to open PDF and epub documents stashed on the SD card.

• USB connection is done right: plugging into a computer does not interrupt usage at all, and if you want to mount the SD card then that's an easily-reached option; neither mandatory nor buried. (Well, it didn't; since system updates it now pops up the do-you-want-to-mount screen immediately, which you have to exit to continue with your previous activity.)

• The force-Google-Account-to-Gmail thing became considerably less annoying once it occurred to me to find out that it let me change the From address of mail sent from the Gmail account. So my external identity is still kpreid@switchb.org, except in Google apps.

• Nice bit of polish: “A system update has been downloaded, but your battery is too low to install it. Connect to charger first.” (phrasing from memory.)

I'm considering writing up a document like the Gadget Coverage List but with an emphasis on features × how to get them on Android rather than features × gadgets — so it would be a recommended apps list, among other things.

$ cat ~/bin/maken

#!/bin/sh
# Make files and view the results.
make "$@" && open "$@"

UPDATE: Turns out I posted this previously, with further thoughts: Avoiding repeating myself (on the command line).

You may recall my post about looking for a new PDA. I have lately found additional pressure to find a solution.

• Moving about on my own in new locations, I wish for a GPS/navigation device. I am currently borrowing a standalone GPS, but that's Yet Another Gadget
• …to add to the four I already carry about (phone, PDA, watch, iPod).
• My phone is on a prepaid plan which was chosen to be cheap for low usage rates. But it quickly becomes not-cheap under higher usage than a couple minutes a day — which I have when trying to do such things as coordinate three people on an errand.

I've compiled some of the options and what features they have into this Google Docs spreadsheet: Gadget Coverage List. Note that “-” means “No”.

At the moment, I am strongly considering getting an Android phone, specifically the Nexus One. I have recently determined that Android meets all my requirements, at least given some third-party software.

Buying a phone (and a plan) is indeed a higher cost than a stand-alone PDA, but I think universal Internet access is worth it.

Costs and carriers

The phone, unsubsidized and unlocked, is $529.

Given that it is GSM, I understand there are basically two carriers to consider: T-Mobile and AT&T. I get the impression that T-Mobile is somewhat less evil than AT&T, and I hear complaints about AT&T's network. On the other hand, T-Mobile does not have coverage (even roaming) in Potsdam, NY, where I'm going to be spending the next two years.

T-Mobile offers a monthly plan for $60/mo, 500 minutes/mo plus fees and (as far as I've looked now) a $35 activation fee. (The option to buy a plan without a phone was buried: you have to choose "T-Mobile SIM card" from the phone list.) I get the impression that the obscure monthly 'taxes and fees' can be around $3-$20 depending on the particular situation. Total cost over 2 years (not including phone): $1475+fees.

AT&T is, er, changing tomorrow. But now it would apparently be $70/mo, 450 minutes/mo, for a two-year contract with a free locked phone (which could be tossed or resold). Plus taxes and fees. After the change in data plan pricing, it would be (assuming no other changes) $65 for 2GB or $55 for 200MB data. Total cost over 2 years (2GB option): $1560+fees, and the phone works in Potsdam.

In both of these cases I assume the cheapest voice plan option.

One option would be to go with T-Mobile for the 2.5 months before I arrive in Potsdam; this would minimize my initial obligation to $709, and assuming I found I liked having a smartphone around sufficiently, I could then switch to AT&T for service during my 2-year stay in Potsdam.

Comments?