Older blog entries for chalst (starting at number 116)

23 May 2004 (updated 23 May 2004 at 15:49 UTC) »
Computation weblogs
An addition to my "Computer science weblogs", whose home has moved to www.linearity.org/cas/weblog/complogs.html, and whose name has changed to "Computation Weblogs":

Andrew Birkett's blog, subtitled "Thoughts of a software engineer", has a heavy programming languages design and implementation slant, and is generally excellent:

  • Optimization asks the question "Why do programs have to get more complicated when you try to speed them up?" and why is it not possible to write code rather like *ML and XML transformers, so that one writes a simple program that is readable, maintainable and easy to reason about, and transformations on this code that make it into efficient code.
  • Yet another compiler compiler and and It's MetaTurtles, all the way down gives a nice introduction to the idea of automating the process of compiler production by starting from formal specifications of the programming language.

    Nice, but I have to quibble: Andrew asserts of denotational semantics: Unfortunately, having all these mathematical objects and theorems floating around isn't getting you much closer to having a compiler for the language, which simply isn't true: a denotational semantics provides you with the recipe for automatically generating an interpreter, which in principle can automatically transformed into a compiler by partial evaluation. The real problem with denotational semantics is that it's proven difficult to provide them for non-toy languages.

  • Of limited scope and Predicate objects talks about some issues around variables whose meaningfulness varies through their lifetime.
  • Monads by stealth motivates a C++ abstraction that turns out to be the same thing as a paradigmatic monad.

Graydon's recent thoughts on pointers
I don't share graydon's dislike of garbage collection (in particular, functional programming becomes tiresome with explicit memory management), but I do think there is a lack of languages that allow garbage collection, allow user control without any enforced runtime, and allow one flexibility in choosing mixtures of the two (Scheme48/prescheme sort of allows this, but the runtime is not optional, and the mixing is not flexible or convenient). In particular I would like to see a language where one could, without undue pain, transform code written assuming garbage collection into code with explicit memory management. There's a lot of know-how of how to do this is the scheme community

graydon wrote:

I believe there is some relationship between this approach and the "linear naming" research that chalst is doing.
There is definitely a similar way of thinking going on, although some important differences:
  • The implementation of "linear names" has always been as reversible pointers, ie. each pointer points to a back pointer; pointers are usually implemented as pairs of C pointers to data structures plus offsets to the backpointer, allowing several reversible pointers to point to the same data structure; thus names are not quite the same thing as ownership;
  • There are no weak pointers in anything written or implemented. Alan Bawden and I thought of adding them, they would have uses, but nothing was ever done. Instead sharing is done explicitly, by having special data structures that allow the data structure to be connected to arbitrarily many users by means of sharing trees. This is related to the way proof nets are handled for linear logic, hence the "linear" in linear naming.
  • We are happy with cycles, but then we are not trying to eliminate garbage collection (yet); disconnected subgraphs are garbage. There is a resource management problem since data structures may span many hosts and may move unpredictably; there's a fairly easy solution, but possibly ideas such as yours could improve on that.

A Security Kernel Based on the Lambda-Calculus
I've linked to Jonathan Rees' 1995 PhD thesis before, but am plugging it again, since it was mentioned on Lambda the Ultimate.

Advice on learning mathematics
Turns out I'm writing diary entries less often than graydon these days... I can only half-blame not having time due to the baby, since I am finding time to spend on Orkut (ncm introduced me to it almost four months ago). I just posted a reply to a query for advice on starting study of mathematics from the Orkut Mathematics forum; maybe it has wider appeal:
  • Recognise that cultivating an intuition of mathematics and knowing how to give rigorous proofs of mathematical theorems, while related, are quite different kinds of knowledge, and mathematical intuition is more fundamental;
  • Learn to judge whether mathematics is good, whether it is powerful or beautiful, and not just whether it is correct;
  • The best way you can spend time is find someone with similar tastes in mathematics and spend time regularly with them discussing problems, papers you have read, crazy ideas you have had, and so on. I didn't do this until I started my doctorate; now I regret....
  • Leverage what you know: because you are confident with programming, try coding up programs that find witnesses to existential theorems you prove. There's a close analogy between proving theorems and writing programs.
  • Don't make the mistake of just choosing computer-relevant mathematics: the core subjects of mathematics complement each other and were you to avoid analysis, say, you would finish your degree with only a skewed and incomplete grounding in mathematics.
3 May 2004 (updated 3 May 2004 at 12:46 UTC) »
The ZF inconsistency proof of the day
Brian Ford and Randall Holmes are discussing Ford's claim on the FOM list. It's still up in the air, but it looks like (i) Ford's argument is interesting, and (ii) there is an argumentative hole in it.

My own investment in the question: I'd rather like ZF to be consistent, but I wouldn't be upset if it wasn't. You can avoid worries about strong axioms by using only geometric theories in your basis theory (or metatheory, if you prefer); these can be shown by simple proof-theortic means (cut elimination) to be consistent, and IIRC they can capture all Pi^0_1 consequences of any consistent theory, or in other words, they can be quite strong but are never too strong.

BabyBlog
Carlin made her first strike against the system on May 1st, with an exercise of public nudity in the Tiergarten. She seems to have a talent for autonomiste activism. She's 15 weeks old tomorrow.

Posctscript: Ah, just read fxn's entry: he beat me to the above by two days, but there's extra information in my entry... There's actually something of a literature of correct-seeming ZF inconsistency proofs; someone should write up the history of them.

22 Mar 2004 (updated 22 Mar 2004 at 12:59 UTC) »
graydon wrote:
I think the idea of a "software component" is a wrong and damaging distraction from a fundamental fact: program text is the ultimate component technology.
I almost completely agree, but actually I think there's nothing wrong with a properly thought through VM model of exchangeable code. No doubt, though, improper application of the component mindset has very widespread and farreaching consequences, almost all malignant.

BTW, I completely agree with what you said about language wars, though if we were forced (at gunpoint, naturally) to choose between C# and Java, I think Java has to be the choice. Mono, I think, is a very, very, dangerous thing for GNOME.

1 Mar 2004 (updated 1 Mar 2004 at 11:07 UTC) »
BabyBlog
Carlin will be six tomorrow. Six weeks, that is.

Recentlog
First time I've read recentlog from beginning to end in, well it would be since about six weeks ago...

ncm: Thanks three times for your congratulations messages, and it is excellent to see such finely calculated mischief as the "I Hate Java" community at Orkut. I almost wish I was a Java hater myself...

And re monotone: indeed, and not only is it well coded, the design is deeply revolutionary. Hackers of the world unite, you have nothing to lose but your beauty sleep! Join the revolution now, while you can be one of its heroes...

fxn: Thanks and congratulations yourself. BETA around 120 days? That should be in an easy patch IIRC :>

27 Jan 2004 (updated 27 Jan 2004 at 21:46 UTC) »
badvogato: Quite so, but I posted on the 25th and was wishing my readers a happy new chinese year. Carlin indeed falls under the sign of black sheep/goat, and since she is also a Capricorn, astrologers might get a bit excited about her goaty spiritual influences.
25 Jan 2004 (updated 27 Jan 2004 at 21:40 UTC) »
Carlin Stewart-Wiese
Our baby daughter was born late on Tuesday night (20th January), at 10:55 pm (Berlin time), weighing 3.38kg (7lbs 7oz), and 51 cm long. You can see a photo of her.

The birth was very tough on my wife, but she's recovering well, and Carlin is healthy, happy and hungry.

And happy year of the monkey, everyone...

7 Jan 2004 (updated 7 Jan 2004 at 16:14 UTC) »
Tutorial on Graph Transformation
Since using graph based representations for all kinds of data is becoming more and more popular, I think it is a good time to remind the wider world that sleepy academia has come up with some nice machinery for performing transformations on graphs, especially the so-called single- and double- pushout approaches. There's a bit of category theory needed to understand what is going on, but only a little bit; much, much less than is needed to understand what is going on with monads in functional programming, for instance.

The best introduction I know is Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts by Hartmut Ehrig (a former employer of mine), and two coauthors.

Unfortunately it is not online; in its place I can suggest Practical Use of Graph Rewriting. I'd be delighted to know of any other recommendations.

Countdown
BETA=15 days.

5 Jan 2004 (updated 5 Jan 2004 at 19:55 UTC) »
What's Wrong with Romanticism?
Gian-Carlo Rota wrote:
The idea of genius, elaborated by German romantics, is destructive; it is a night into fantasy. There is reason to believe we've killed classical music because of that idea. People think that they will be either geniuses like Beethoven or nothing. But look at the Baroque Age--there were hundreds of little Italians who wrote good music and didn't give a hoot about being creative.

Random Remarks
tk and mslicker are behaving like idiots in lkcl's very timely and constructive article's comment thread...

I see that Paul Graham has a book coming in May.

dyork: Don't leave us, please! Belonging to the free software community is a vocational sort of thing, not associated with this or that project. Your diary entries enrich advogato even when they are not filled with LPI, DocBook, etc.

1 Jan 2004 (updated 1 Jan 2004 at 22:29 UTC) »
Happy New Year, advogato!
I had a wonderful New Year celebration with my wife, in the mists of the gunpowdery fog that is Kreuzberg, Berlin at this time of year, at our favourite pub, Max und Moritz. Now just 3 weeks to go before our daughter is born.

Computer science weblogs
Probably the academic discipline that gets best value out of the weblog phenomenon is law, with a good number of excellent weblogs devoted to both general and specialist subjects. Computer science is pretty disappointing by comparison, but here's a selection of some weblogs that are battling the odds. (There are also some weblogs here by non-computer scientists, which I tend to count as one of us if there is a heavy language design focus).

Lambda the Ultimate This is just clearly the best computer science weblog out there; it has no close competitors. Here's a selection of excellent posts, taken almost at random:

Pinku Surana's Green Hat Journal: probably my favourite individual blog by a computer scientist. Some of his best past posts:

Matt Jadud's weblog How do you compile?, who also runs the Cool Stuff in Computer Science weblog. Focus on didactics of computer science; some sample posts:

Bill Clementson's Blog, a Common LISPer. Some samples:

  1. Continuation-based web frameworks
  2. Kenny Tilton's Cells
  3. A CLer learns scheme

Ian Wehermann's the maine paige. Sample posts:

  1. Generalized logic and proof
  2. on the web's first semantic application

John D. Mitchell's blog (he also keeps an artima.com blog. Java programmer. Samples:

Bjorn Borud's Random Scribblings; samples:

Gordon Weakliem's 80/20; samples:

Will Benton's Free Variable. Sample post: Thinking like a computer scientist

Cay Horstmann's rather sparse artima.com blog; sample post: Some objects are more equal than others

Jim Coplien's Artima.com artima.com blog has just this single entry, which makes it more an essay than a weblog: Teaching OO: Putting the Object back into OOD.

Katz's Web; sample on Inference Web: Explanations on the Semantic Web

More to follow: I'll keep this post updated. Recommendations sought; you can email me at cas@janeway.inf.tu-dresden.de.

107 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!