Older blog entries for ajk (starting at number 22)

I've been specing and implementing Winters network protocol. It's going slowly. I managed to write my own Blowfish implementation which seems to be correct (passes a simple encryption/decryption test where I know the correct ciphertext). I noted, however, that the online description of Blowfish is ambiguous in many occasions, most notably it omits information on endianness issues on many occasions. Apparently my guess "big-endian über alles" was correct. My Blowfish implementation is not one of the fastest, but it is the only one that I know that does not require separate source configuration (either manually or with Autoconf) and is written in C.

Did you know that GCC means "Graphic Character Combination"? I didn't, until I ran across the ECMA-48 standard.

I should've known. I presented the session management part of the Winters protocol to a security newsgroup. It was pretty much shot down. They even asked why I was designing my own protocol instead of using SSL or SSH or some other well-established protocol. The answer is that they don't take advantage of one unique aspect of the application I'm designing the protocol for: all legitimate sessions are necessarily derived from a root session. My protocol thus can do without all long-term keys, symmetric or asymmetric. Oh well, back to the drawing board (and I'm getting a copy of Schneier).

I decided to rebuild my home system, which naturally runs Debian, from scratch to do away with all its cruft. Of course I forgot that I need the drivers diskette even in the NFS install, and of course I noticed that after wiping out my previous install. I had no access to the network anymore. I had several past versions of Debian on CD's but alas, my CD drive is broken. I even had some old boot disks for Debian 1.3, Debian 0.93r6, and Slackware 3.0. Unfortunately, none of them would build my system into a shape where it could reach out to the net to grab the stuff I needed. Ended up calling a nearby friend and using his machine for creating that much needed drivers diskette.

Today my network connection suddenly dropped. Turned out my network card was loose and had disconnected.

I've been drafting the Winters network protocol. I found uses to such 32-bit quantities as 4037931181 ("emergency hangup") and 4026658817 ("permission denied") [thanks dhd!]. The protocol is simple and expresses what it needs to express. I realized I can set up a separate auth server to provide new sessions for arbitrary clients if necessary, which simplifies the problem. You see, the protocol creates new sessions by negotiating their cipher and encryption key on an existing session; this avoids me having to deal with public-key cryptography in the protocol itself.

Anybody see any obvious security problems with assuming that if the client can send a known plaintext (published as part of the protocol specification) encrypted with the correct key (which is prenegotiated using channels we assume to be secure) then the client can be considered authenticated?

The next step is to implement the protocol. This should not take more than two days (famous last words!).

Advertised Advogato to Tuomas Lukka. Seems he likes it.

In the spirit of the recent article on project naming, I decided to rename TeWiS into Winters. Sounds much better that way.

schoen, you can find a list of recommended compiler technology books in the comp.compilers FAQ. The book is the dragon book, Compilers: Principles, Techniques, and Tools by Aho, Sethi and Ullman (Addison-Wesley, 1986). I've also found Wirth's books on the topic instructional (he has a book that, IIRC, builds a complete Pascal compiler as it goes, and I believe his Data Structures + Algorithms has a section on recursive descent). Stroustrup builds an expression calculator using recursive descent in his C++ bible (as do many other authors in various books using various languages).

schoen

It is pretty straightforward to write a recursive descent parser based on a BNF grammar by hand: make every nonterminal a procedure that parses that nonterminal, and have it recursively invoke other procedures whenever the BNF grammar refers to other nonterminals. Parse terminal symbols any way you see fit (a separate lexer that tokenizes the input is easy to write ad hoc or by using regular expressions). See any language/automata theory book or compiler technology book for more info.

In other news

I have taken over the TeXmalli document from liw. It is a sample LaTeX document written in Finnish.

I have been so involved in real life since Friday that I haven't had a chance to post any diaries. Most of that was because I was moving (new real-life contact information on my home page) and thus have acquired a permanent net connection, so I hope I am excused :-)

For the same reason, I have not been able to do any development work in the last few days.

Responses to Ankh

• A transclusion - from what I remember from Ted Nelson's lecture series he held here some time ago - has the important (and good!) property that it refers always to the same version of the document, but if you went and checked the other end of the transclusion, you could see that that part of the text had been seriously modified (and you could see the diff between the transcluded version and the current version, too). And you can transclude only a part of the text, if you like. So, claiming that the XML entity reference is anything like transclusion is not really fair. But yeah, it does have some similarities (the ability to fetch from the network, for example, XML entities do that don't they).

• It is important to realize that literate programming is not just a fancy method for commenting your code. The ability to rearrange the program text and thus for example ignore required nitty-gritty you are not interested to write just now (and put off its code to another section) is in some senses at least as important as the documentation-code dichotomy. For example, the design method of stepwise refinement becomes an actual possibility only after you start doing it the literate way: this allows you to incorporate the refinement steps of the design in the actual code that will be compiled and then executed. In other words, literate programming makes pseudocode executable.

• I agree that the module problem is a real one with literate tools. Do you know Knuth's solution, as seen in for example Stanford GraphBase and the MMIX simulator? He composes the modules as separate literate works, which no doubt become chapters in the book. I don't personally find that style appealing, but it is a solution. I have personally decided to try out the include file mechanism: I split the program into include files which are then put together by CWEB as a single source for either CC or TeX.

• GZigZag is not just "a simple data structure to avoid having to understand more complex one". Rather, it is a metastructure: you can define the usual lists, trees and whatnot inside the ZigZag structure quite easily. ZigZag the data structure gives you automatic memory management, persistent storage, distributed data structures et cetera, once it's fully implemented. GZigZag is actually a system in its own right: it has its own way of looking at data, everything is a cell (compare to everything is a file in Unix), and it provides you with means of data storage (persistent cells) and networking (distributed cells). I don't understand much of it yet - its way of looking at the world is sufficiently different from the conventional view that it needs adjusting to - but I can say (having seen demos of it and discussed it with Ted Nelson and Tuomas Lukka, the main architects) that it looks cool.

Today

Wrote more TeWiS and figured out some of litprog.

Question

Does anybody know a Plain TeX (not LaTeX or Texinfo) rendering of the GNU General Public License, version 2?

What is Zangelding?

It's been windy here today.

Ankh, I thought that transclusions were supposed to be bidirectional. Or am I mixing them with Ted's link concept? In any case, you can't do the full transclusion thing in XML, as the entity reference does not understand document versioning.

Anyway, if you like Ted Nelson's work, check out GZigZag, which is an implementation of his ZigZag structure. It really blows your mind out.

Ankh, I've read the literate programming column (it is reprinted in Knuth's Literate Programming book), and I believe that the part of MacIlroy's criticism that was based on the Unix pipeline was unfounded. He did not consider the context where the program was written: it was an exercise demonstrating a programming methodology, and it is common for such exercises to assume that certain solution types are forbidden (especially those that make the exercise trivial). And in any case, the original WEB system was Pascal only, so it was limited in what you could do with it (no Unix pipelines, for example); but this concern is no longer relevant, as there are language independent LP tools (like Noweb, which I mentioned yesterday), and you could actually write the pipeline in literate style - but since it's so short there is no point in doing that.

Literate programming is hard. I regard myself as an excellent writer of fact prose (fiction is harder by an order of magnitude) and as a decent programmer, but combining these two skills seems very difficult. Maybe it's the tools. I use Knuth's CWEB system to write TeWiS, and one of its problems is that it does not really encourage modular style (and I am a modular programmer!). Norman Ramsey's Noweb looks more interesting but its build-time dependencies are horrible (install Icon to install a program you need for compiling my C program... horror) and it still hasn't been ported to all Debian's architectures.

Apart from battling with CWEB and TeWiS my day has not contained any productive activity. I've been lazy, and reading up sfnet.keskustelu.ihmissuhteet (the Finnish newsgroup about human relationships), and rereading Childhood's End.

Bathroom has been usable since Friday, after I solved the "closed cold water valve" problem.

No work before Friday. University Easter is fun!

Hacked on TeWiS.

Played guitar, sang.

Processed Incoming.