Follow up on kanji coding method: Wuji

Turns out there is a character input method like the one I described in my previous post.
Sounds like it turns out to be kind of awkward to use. Ah well...

Ban the dangling else!

I was just reading through Niklaus Wirth's paper, "Good Ideas, Through the Looking Glass" (found through Lambda the Ultimate, of course!) where he talks about the Dangling Else problem.

Some programming languages have statements of the form:

if X then Y

and

if X then Y else Z

with no end keyword or bracket, leading to the problem of how to interpret:

if it's Saturday then if it's sunny then have a picnic else see a movie

Do we see a movie if it's not Saturday, or if it is Saturday, but it's cloudy?

Natural languages have exactly the same sort of problem (example from the AP Press Guide to News Writing, quoted in Language Log):

We spent most of our time sitting on the back porch watching the cows playing Scrabble and reading.

It reads funny in English, but we resolve it easily because we know the context. Obviously context is not as helpful for a compiler.

How does Language Log suggest fixing that problem in English? They give two suggestions:

We spent most of our time sitting on the back porch watching the cows, playing Scrabble and reading.

or

Playing Scrabble and reading, we spent most of our time sitting on the back porch watching the cows.

The first suggestion corresponds approximately to Wirth's preference for an end keyword; the comma signals a break of some kind, and the obvious interpretation is that the cows and the scrabble shouldn't be too closely associated. It's not nearly so rigorous as end, of course.

The other suggestion is a bit more interesting; they rework the entire ordering of the sentence. Although the two examples aren't really parallel, it does suggest another way to rework our if-then-if-then-else, if we intend the final else to correspond to the first if-then:

if it's not Saturday then see a movie else if it's sunny then have a picnic.

In other words, we're punting -- not solving the original ambiguity but wording around to avoid the issue.

I think that's actually a better strategy from a human reader's standpoint. We do not have much in the way of "closing braces" in natural language: they tend to lead to center embedding issues which our brains just aren't equipped to deal with. So maybe a good policy would be for a compiler to simply disallow the "if-then-if-then-else" construction with either interpretation, and force the user to rework their logic a little. Such a restriction looks like an ugly hack to a computer scientist, but I think its necessary if we take seriously the idea that programs should be human languages as well as computer languages.

Tags: language, Programming Languages, HCI, dangling modifiers

Metalanguage for Software Development

Every software developer uses a variety of languages to develop a program. It may seem like you're developing something purely in Perl or Java or VB or whatever, in fact you're using a lot of mini-languages to manage the development process:

• Shell: if you're using a command line, you have to know shell commands for managing files and directories, invoking the compiler, etc.
• IDE: On the other hand if you're using an IDE, you could kind of consider it language-like; you invoke series of drop down menus and click options on and off
• source control: whether it's IDE-based or command-line based, you're describing and querying a specialized model encompassing time, files, directories, versions, and maybe different user identities
• deployment: you use FTP commands, or something equivalent, to put files on a server, configure the server to run your programs at the appropriate time, etc.
• building and linking: Like makefiles or visual studio "projects"
  
• profiling: turning a profiler on or off, configuring it, and interpreting its output, is a language-like interaction
• debugging: another model of the program, where you communicate with the debugger about variable values and code structures
• SQL: typically any interaction with a database within your program, is done from within a walled-off sublanguage; maybe SQL built into strings, or maybe a specialized, but usually somewhat awkward, object or function call model.
• Database configuration: setting up tables and so forth is often done with a combination of SQL or database management configuration IDE manipulation

When programmers think about the development process, we have an integrated mental model of all these aspects of the process, and from that figure out how to use them all together to do what needs to be done. It would be interesting to have a single, consistent meta-language for software development that encompassed all these tasks.

The closest thing we have to that, I think, is the command-line shell. The simpler "languages", such as the compiler settings language, are encapuslated as command-line arguments, so technically from the same prompt you are doing diverse tasks like compiling your program or renaming files. But useful as it is, it's kind of a gimmick. You can't easily pull together information from, say, the profiler, the debugger, and some unit test results, and ask questions that cut across these different domains.

For example, suppose you made a change to a procedure last week, and now you think it may be running too slow on a particular dataset. A test of that is easy to express in English: run the current version of the procedure X against dataset Y and note how long it takes; also run X against Y using the version of X that was current last Thursday. Implementing it would take a little work; we'd have to check out two versions, compile them in separate directories, run them both under a profiler, and know how to interpret the profiler results. Speaking for myself, I'd probably make a mistake the first time through -- I'd check out the wrong version of the code, or run the compiler with different optimization flags or something.

There oughtta be a language that has standard terminology for all these sorts of tools, and some easy way to build little modules onto the front end of a tool, that translates this language into the tool's configuration settings, and translates its results or error messages back into the language.

The trick is you'd have to have a pretty smart front end that could pull apart commands or queries that involved multiple tools and figure out what commands to pass along to the individual tools; then integrate the results it gets back. This would not be a trivial problem, but it would be a good start just to make this kind of task *expressible*, and require a lot of user guidance at first.

Tag: ProgrammingLanguages

Buddhism and Category Theory

In my previous post today I mused about using standard ontologies in programs as a way of grounding the web of connections between your objects in a framework of common terminology.

There is a concept in Buddhist metaphysics called Dependent Origination, which states that nothing exists on its own, but only manifests itself through its connections with everything else in its environment. One illustration of the concept is Indra's Net, an infinite spider web with little silver balls at all the junctions, each reflecting all the others in a way that would gum up any ray tracer.

A program that doesn't refer to much of anything external to itself is like that -- you can define data structures and pointers and files that all point to each other, but it's all meaningless without the interpretation that a programmer or user gives to it in the data they feed to it and their interpretation of its output.

I'd say that Category Theory is a mathematical restatement of Dependent Origination.

Tags: CategoryTheory, DependentOrigination

Organizing programs by their invariants

It seems to me that natural langauge program specifications tend to consist of a lot of statements which are all independently true, and only dependent on context for deictic references (i.e. pronouns and pronoun-like references to concepts in surrounding sentences). In other words, I'd claim, you could make sense of a good proportion of a scrambled specification if:

• Sentences remained intact
• Deictic references were replaced by full references to global names of entities or processes

Now obviously, not everything in such a document will behave that way; for example an ordered list of steps will have their ordering and context lost. But I think my claim is more true of an English-language spec, then, say, a large FORTRAN program. If you have a spec you're working with closely, you might have sticky notes on different pages, and individual sentences highlighted, which you can turn to and refer to instantly without necessarily reading for context. An old-skool not-very-modular FORTRAN program, on the other hand, is meant to be executed in one fell swoop. A programmer might turn to a particular page of a printout and look for some information, but will require a lot more scanning around and reasoning to come up with an answer to their question about what's going on in the program.

A Java program might fall somewhere in between English and Fortran in that regard -- Java tends to be written with lots of smallish functions, each of which might be comprehended on its own.

Another reason a natural-language spec is easier to read in a random order, is that the words in an English sentence are more likely to be standard vocabulary not defined in the spec; and the ones that are defined in the spec are likely to be motivated* narrowings or metaphors of standard terminology. In all the programming languages I'm familiar with, almost all the entities defined in a particular system can be freely named: a there may be conventions telling a programmer what sort of thing a WidgetWindowHandlerFactory is, but the compiler doesn't care; it could be a synonym for Integer.

So this habit of natural language helps make randomly-chosen sentences more comprehensible on their own. That in turn makes it easier for us short-attention-span programmers to digest the piles of paper our managers and user groups churn out.

This suggests a couple interesting features for programming languages:

1. Structurally organize programs around a series of declared invariants, with the compiler (when possible) or the programmer (the rest of the time) filling in associated code to ensure the invariant remains true. This could be done in a lot of different ways depending on the need -- type systems, aspects, agents.
2. Create a large and varied, but standard and fixed, ontology of types that the user should almost always derive from. Give them all short names and require user-defined types and variables to end with those type names. This would have to be done carefully to avoid javaStyleWordiness(), and it would also be a larger learning curve/burden on the programmer. I'm picturing something vaguer and more flexible than a standard library; rather than providing a bunch of standard implementations, the ontology would provide standard invariants.
   

* "motivated" -- I got this term from George Lakoff's book "Women, Fire, and Dangerous Things" where he talks about how new uses for old words are motivated by metaphorical relations with older meanings, but not predictable from those meanings.

Tags: ontology, language, Programming Languages

Saponomancy

This week I was asked to write some code to mimic a SOAP service. How hard could that be? It was a very simple service, just a couple remote procedure calls, one of which could return a large binary file.

Of course, the original one was implemented in Delphi, to run under IIS, and the new one needed to run on a UNIX-like system, but SOAP is intended on making all this easy, right? How much did I need to know?

Well, a lot, it turns out. I played with a couple different toolkits for creating SOAP services, and they kept coming up with slight variations, none of which seemed to interoperate out of the box. Little things would be different in the XML message, like whether namespaces were mentioned in the tags, or how the attachment was referenced and sent. It was easy to see and understand the problem by looking at the dumps of the XML and MIME stuff going over the wire, but much harder to plow through the documentation of the various API's to see what flags needed to be set in their object model, or what objects needed to be created, or who was responsible for allocating and freeing memory, etc.

In the end, I realized that since this was an internal service, and I controlled both endpoints, I could easily make a case to management for just using the raw HTTP protocol, and in fact as I played with that solution, it turned out to be cleaner, lighter, more maintainable, and easier to document. I'm changing my party affiliation to REST, even though it's too late to vote in the primaries.

Well, that's fine; I'm sure there must be cases where SOAP is a better solution, but it got me to thinking about why it is that the raw XML is so much easier to debug than the supposedly labor-saving frameworks built on top of it. I guess it's just that what goes across a line is easier to capture and pin down -- I can run two services, capture their input and output, and just compare the logs of them. But I can't compare the operations of their object models, because they're different.

What would be very cool, is if there were a formal way to specify a relationship between all the possible operations of an object model, and the grammar of its input and output streams. Then I could point to a rule in the grammar that I wanted to come out a certain way, and ask "what sequences of user-accessible object operations can cause this". The closest thing I've seen to this is the Whyline from project Marmelade at CMU. The Whyline is a thingy that looks like it's geared towards helping a programmer find bugs in their code, by tracing out why a particular condition was arrived at in code execution. Seems like it could be just as useful for prying apart the mysteries of someone else's prepackaged API, especially if it was closed-source, if somehow the Whyline could still operate without showing you precious vendor secrets.

Unfortunately the Whyline is still a research project built into a research language called Alice, not a handy button on my Visual Studio menubar.

Abstracting Bubblesort

In my August 4th entry I conjectured that monads might be a good way to abstract away the question of whether a bubblesort was done over time or laid out across memory as a sequence of permutations.

I thought that was a good exercise for me to brush up on Haskell monads, so here's the program I wrote. It's "literate haskell", so you can take this whole posting, save it as an whatever.lhs, and it should compile.

I especially relied on a monad tutorial at A Neighborhood of Infinity, that Sigfpe happened to post just as I was in need of it. Thanks, Sigfpe!

I'll be using the State, List, and IO monads.  Eek, trial by fire.
To start with, State has to be imported:

>import Control.Monad.State

So here's my generic bubblesort to start out with.  It sets everything
up without actually having the list available yet; all it needs is the
length for now.

The cf and swap parameters are functions that compare and swap elements,
respectively.  Actually, they just take the indexes of the element(s)
and return a function which will be responsible for testing and permuting
anything the caller wants, however they want.  cf x y should compare elements
x and y (whatever that may mean), and swap x should swap the xth and (x+1)th
elements.

So this function cycles through pairs of adjacent indices in bubblesorty
fashion, and builds a list of functions, each of which is responsible
for testing, and maybe swapping, a pair of elements, with those 
user-supplied comparison and swapping functions.

>bubblesort cf swap theLen = do
>                       i <- reverse [0..theLen]
>                       j <- [0..(i-2)]
>                       [do
>                            i <- cf j (j+1)
>                            if i
>                                 then swap j 
>                                 else return ()]

Now here's a simple comparison function: it assumes that the 
list will be just an ordinary list, with elements instances of
Ord (so that > works).  What it returns is (State [a] Bool),
which is actually another function, taking one list [a]
and returning the same unchanged list [a] and a Boolean.

>cf1 :: Ord a => Int -> Int -> (State [a] Bool)
>cf1 i j = do
>            ls <- get
>            return $ (ls!!i) > (ls!!j)

And here's the corresponding swap function.  It returns a
function which takes a list, and returns a list with the
jth and (j+1)th elements swapped.

>swap1 :: Int -> (State [a] ())
>swap1 j = do
>            theList <- get
>            put $ (take j theList) ++ 
>                 [theList!!(j+1)] ++ [theList!!j] ++ drop (j+2) theList

Let's look at another pair of swapping/comparison functions,
before putting everything together:

This set has a more complicated state -- it's an ordered pair,
of the current permutation [a], and a list of strings [[Char]]
representing the Plinko toy that 
would produce the sort so far.

>cf2 :: Ord a => Int -> Int -> (State ([a],[[Char]]) Bool)
>cf2 i j = do
>            (theList, history) <- get
>            return $ (theList!!i) > (theList!!j)

And here's the corresponding swap function:

>swap2 j = do
>            (theList, history) <- get
>            let newList = (take j theList) 
>                          ++ [theList!!(j+1)] 
>                          ++ [theList!!j] 
>                          ++ drop (j+2) theList in
>                let newHistory = (( (replicate j '|') 
>                              ++ "><" 
>                              ++ (replicate ((length theList)-j-1) '|')) 
>                                  : history) in
>                    put (newList, newHistory)

In this second example, the state is more than just the
list, so we need a function to create the original ([a], [[Char]])
structure:

>buildstate2 :: [a] -> ([a], [[a]])
>buildstate2 a = (a, [[]])

And one to get our plinko toy out after we're done sorting:

>getresult2 :: (Show a) => ([a], [[a]]) -> [Char]
>getresult2 (_, b) = foldl (++) "" $ map (\b -> "\n" ++ show(b) ) b

I skipped the equivalent functions before for the straightforward
sorting example because they are straightforward:

>buildstate1 :: [a] -> [a]
>buildstate1 a = a
 
>getresult1 :: (Show a) => [a] -> [Char]
>getresult1 a = show a

So now we're ready to call this contraption.  dosort takes
the four functions that relate to our state: buildstate, getresult,
swap, and cf; along with the string to be sorted (I call it string,
but it could have been a list of anything in Ord, really).

The "sequence" function links up that list of functions that
bubblesort created, and execState is what runs them, when supplied
with the output of buildstate.

>dosort buildstate cf swap getresult string = 
>           let sorter = bubblesort cf swap $ length string in
>               getresult $ execState (sequence sorter) (buildstate string)

Here are some test functions which call both suites on the same string:

>test1 = dosort buildstate1 cf1 swap1 getresult1 "sambangu!"
>test2 = dosort buildstate2 cf2 swap2 getresult2 "sambangu!"
>
>main = do
>        putStrLn test1
>        putStrLn test2

I'm certain I'm not doing this in a very elegant way. It appears that those four characteristic functions belong together in a class declaration, and somehow different execution types would be instances of that class, but I was unable to get it to compile that way. Could be my syntax was wrong, or more likely, fuzzy thinking, which Haskell seems to be pretty (justifiably) intolerant of.

Keystroke coding system for Kanji

I was thinking about ways of entering Chinese characters, and wishing there were a more intuitive way to do it. So here's a scheme I came up with. Obviously a lot of people have been thinking about how to type kanji for a long time, so it's probably been thought of and (implemented | dismissed) before, but anyway, it seems to me like it could work:

In this system each character is represented by a sequence of the letters b, n, m, and k. Each letter represents a stroke or part of a stroke:

b = diagonal downwards to left
n = downwards
m = diagonal downwards to right
k = horizontal

So for every stroke you type a letter, and if the stroke changes directions, you type the new letter, making no distinction between strokes and parts of strokes. I wonder how many ambiguities there would be? Are there any kanji with disputed stroke orders, or is it totally standardized?

Here are the numbers 1 - 10:

一 k
二 kk
三 kkk
四 nknknbnk
五 knknk
六 nkbm
七 knk
八 bkm
九 bknk
十 kn

There would have to be some standard rules about how to represent the little hooks (like the last strokes of 四 and 九) and the ones that kind of curve from one heading to another (like the first stroke of 九).

It seems like a person adept at writing kanji might be able to kind of mentally translate their mechanical skill of writing into these keystrokes.