ChapterZero

Regarding MT text formatting engines: it is obvious that there is no way to accomodate the full richness of XHTML [cf. Appnel]– not to mention the various other web technologies– into a single _simple_ textual markup scheme. At the point where it equals the expressive power of XHTML, the markup would necessarily surpass XHTML in its complexity, because of the textual gymnastics which allow it to be embedded in XHTML. So, equally as obvious, there can be no one textual formatting engine to rule them all. Instead, a user may want to take advantage of the (complementary?) features of several text formatting engine, mixing and merging the markup schemes with an eventual level of complexity that they control. MT has been designed to allow the user to choose the particular text formatting engine that will be used for each post, which is nice, but I propose that it be taken to the next logical level. Instead of choosing just one engine, the user could choose a tower of formatting engines– that is, a set of formatting engines, and an order in which to apply them. Of course, the question then arises of how to handle the interaction of the markup schemes of the separate engines. One way to do so would be to standardize the markup schemes used by all engines, but that is the first step down the path towards the creation of a markup language– not a good idea, as languages tend towards generality (and therefore complexity) over time. Another, more free-spirited approach, is not to handle the interaction of the engines, to leave that responsibility to the user. And why not?– after all, the user ostensibly knows the syntaxes of the engines he is using.

Even if this paradigm is never officially supported by Six Apart, there is a way to implement it using the current plugin system: Create an ‘OverEngine’ text formatting engine, which when applied to a particular entry, scans that entry for an ordered list of text formatting engines to apply. It can strip this command, locate the appropiate procedures using the MT plugin architecture, and apply them.

I discovered this summation identity naturally– meaning, motivated by my own investigation, and without anticipation of the final result, even though I am sure I’ve seen it before:

It seems to work for any complex number, including zero. I have a proof for real x in [0,1], but that is based on probability theory, so I don’t have a handle yet on the general case. I’ve submitted it to the UHME mailing list, but I don’t think anyone will really work at it.

Update: I just realized where I’ve seen that identity before– it’s just an expansion of using the binomial theorem. Silly me…

The Bracketing Problem (cf. MathWorld) can be stated as such:

Let be a non-associative, non-commutative binary operation. Given an ordered n-tuple of operands, , indicate using parentheses all possible -products that can be found by varying the sequence in which the operands are combined.

For example, a 4-tuple yields five unique bracketings:

(x(x(xx))), (x((xx)x)), ((xx)(xx)), (((xx)x)x), ((x(xx))x)

It can be shown (not yet by me ) that there are bracketings for an -tuple, where is the -th Catalan number: .

The question of how to write a ‘Catalan generator’– a program that generates all bracketings for a given number– came up on sci.math. Here’s an algorithm that is straightforward to implement:

To find the bracketings for , form all pairs where and . For each of these pairs, find = the set of bracketings and = the set of bracketings, then find = the cartesian product of and . The base case is , where is just a generic variable as above. Then , the set of bracketings for , is the union of over all the pairs.

This is a scheme program from SICP that demonstrates the elegance of Scheme; it is the definition of a procedure that finds the roots of equations using the half-interval method:

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                    (search f neg-point midpoint))
                   ((negative? test-value)
                    (search f midpoint pos-point))
                   (else midpoint))))))

(define (close-enough? l r)
 (< (abs (- l r)) 0.0001))

(define (average l r)
  (/ (+ l r) 2))

;This is the entry point to the program
(define (half-interval-method f a b)
  (let ((a-value (f a))
         (b-value (f b))
    (cond ((and (negative? a-value) (positive? b-value))
              (search f a b))
             ((and (negative? b-value) (positive? a-value))
              (search f b a))
             (else
               (error "Values are not of opposite sign" a b)))))

I’ve been working on a geometry (triangle) problem for a day now; Zach posted it to the UH Math club mailing list. It’s one of those problems that looks ridiculously easy, like all you have to do is identify some similar triangles, but it’s turning out not to be so easy.

This morning I spent about 3 hours working with Eukleides and LaTeX to produce a nicely typset version of the problem, to which I can hopefully append a solution some time soon. It took me so long because: i) I’m not familiar with Eukleides, ii) while Eukleides has better than average documentation, it is not a tome of comprehensiveness, and iii) getting the illustration to fit unto a double-column page (with the problem on the other side) was tough. I ended up having to use \raisebox and \makebox to trick LaTeX into ‘thinking’ the illustration was skinnier than it actually is.

In the process, I conceived of a more powerful Eukleides, one based on/ interleaved with Scheme. The current one is ok, and very useful, but it could have more features. And as is, it doesn’t support looping.

I said I was taking a break to study the material I need to know to implement a CAS, and I’ve been doing so. But.. that’s not so interesting yet; I’m going very slow, as I don’t feel there is much point to rushing– I’m in this for the long haul anyway.

I’ve been reading Crytonomicon by Stephen Nealson; Alan Turing plays a role in that book, so today when I visited the library, I picked up a biography of him. Actually, there’s more to it– I see that book so often, yet this is the first time I’ve checked it out– I picked it up today because of the Cryptonomicon, and I started to read the introduction, which gave me the impression that it was a book that Douglas Hofstadter would read. Then it turned out that Douglas Hostadter wrote the introduction! That marvelous stroke of serendipity made me decide to read the book.

On the math side: I love this book I’m currently reading on algebra: “Advanced Modern Algebra” by Joseph Rotman. And I have two excellent CA specific reference books, and one for polynomials: “Algorithms for Computer Algebra” by Geddes, Czapor and Labahn, and “Modern Computer Algebra” by von zur Gathen and Gerhard, and “Polynomials: an Algorithmic Approach” by Mignotte and Stefanescu, respectively. So once I finally finish learning ‘ordinary’ algebra, I can start tackling the applied, algorithmic side.

I’ve also been fooling around with Scheme. Nothing major, just implementing some simple number theoretic algorithms (gcd, lcm, factoring, totient function). This is helping me get familiar with Scheme– even in implementing these unremarkable procedures, I’m seeing how divergent the different Scheme implementations all are.