Category Archives: computer science

Models of forms explicated, a little bit

Some miscellaneous notes about the concept of form, which I sketched (ahem) in  a series of posts TDMO1TDMO2TDMO3TDMO4,TDMO5TDMO6, TDMO7, TDMO8, and TDMO9. This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.  I am now embarking on a series of posts with further explanations and comments.

More about a model of a form

For any constructor space \text{C} (which will be the sketch for a kind of category, a special case of a doctrine), take any object F in the FL Cattheory of \text{C}   and adjoin a new arrow f:1\to F where 1 is the terminal object.  f is what we call a C-form and the enhanced category is denoted by \text{C}_f.  In TDMO9 I described the node \text{rfs} for reflexive function spaces in a cartesian closed category; it is an example of a CCC-form.

A model of a \text{C}-form f  “in a C-category \text{K}” means that \text{K} is a model of \text{C}_f . In particular, in  \text{K}, M(F) is nonempty.

The connection with sketches is this:  If you have a sketch in some doctrine \text{C}, the sketch consists of a graph with some diagrams, cones and cocones.  There is a node F in the FL Cattheory of \text{C} each of whose elements in a model of \text{C} (in other words in a \text{C}-category) will be such a sketch.

Example: The FP sketch for magmas

A magma is a set with a binary operation defined on it (Note 1).  It does not have to be associative or commutative or anything.  In the FP doctrine its sketch consists of one diagram

(Diagram1)

and one cone

(Cone1)

and nothing else.  The FP-Cattheory for this sketch is (equivalent to) the Lawvere theory of magmas.

The FL-Cattheory \text{FP} for FP categories, described in some detail in TDMO8, contains a node whose inhabitants in any model of \text{FP} (in other words in any FP-category) are all such sketches (the diagram and the cone).   This means that the FP sketch for magmas corresponds to an FP-form.  In this way you can see that all sketches in Ehresmann’s sense are forms in my sense.

This node can be constructed as the limit F of a cone over a diagram in \text{FP} as was done in previous posts.  You have to make the diagram become a description of the diagram and cone above, using the arrows in the constructor space \text{FP}, for example \text{ob}, \text{ar}, \text{prod}:\text{ob}\times\text{ob}\rightarrow\text{cone} and others, and including formally commutative diagrams that say for example that Cone1’s projections go to the same object (using \text{lproj} and \text{rproj}).   Maybe someday I will produce this diagram in a post but right now I have a cold.  (Excuses, excuses…)

Adjoining a global element to this limit node will result in an FL-sketch \text{FP}_fwhich contains the FL-Cattheory for \text{FP} along with that global element.

So a model of the form for magmas in an FP category \cal{B} is a model of \text{FP}_f for which the model of the underlying cattheory \text{FP} is \cal{B}; in other words it is the category \cal{B} with a distinguished element f of the node F.  That distinguished element is a particular diagram and cone like the ones shown above for a particular object A (because the projections onto F include a particular projection to \text{ob}).  That object A with the arrows corresponding to m, p_1 and p_2 is a particular magma, a model of the sketch for magmas given above.

Notes

Note 1  “Magma” was the term used by Bourbaki for this structure.  As far as I know, very few people ever used the word until it was published in [1].  When I was a grad student in 1962-65 it was called a “groupoid”, which means something else now (something much more important than a magma in my opinion).  Now the name occurs in examples all over Wikipedia.

References

[1] M. Hazewinkel (2001), “Magma“, in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104

Send to Kindle

Addenda to the 1993 Sketches paper

I have uploaded here a version of my 1993 sketches paper with an addendum listing a few relevant papers written since then.  I have not kept up with the field well enough to contemplate a complete revision of the 1993 paper.

I recommend that more people update their papers this way.  I did it by making a new PDF file with the added references and then using Acrobat to combine it with the old paper into one file.  That way I didn’t have to re-TeX the old paper, which is a good thing, since I don’t know where some of the .sty files are.

Send to Kindle

Reticulating Splines?

My backup program (Mozy) went awry.  I followed their instructions for repairing it (delete certain files) and it started up.  It took a long time to get going (but it finally did), and during that time it emitted several messages.  One of them was “Reticulating splines”.

This causes me considerable Cognitive Dissonance (sometimes known as CD).  In fact, this causes me Dismaying Virtual Disturbance (otherwise known as DVD).  Reticulating splines is all about continuous  (indeed differentiable) things.  Backing up digital files is all about discrete things.  How can you apply splines to a discrete process?

No doubt some reader will tell me.

POSTSCRIPT:  I just found out, from here. Now I have Egg On My Face (EOMF) because I wrote a blog about something without looking it up on Google. Sigh.

Send to Kindle

Bluetooth

A friend of mine said she didn’t know what Bluetooth is. This is a brief explanation. Bluetooth has aspects that might interest liberal-artsy people.

Bluetooth is a method for transmitting data over short distances, so you don’t need cables. It is transmitted over a frequency that changes rapidly within a narrow band so it doesn’t interfere with other devices using the same method. This method is called frequency hopping.

One method to implement frequency hopping was patented in 1942 by Hedy Lamarr (the actress) and George Antheil (the composer), who wanted to use it to send radio guidance to torpedoes that could not be interfered with. The idea was to use a piano roll to change the frequency rapidly. As you might expect, their method used 88 different frequencies. They never benefited from their patent because clocks in those days weren’t accurate enough.

Hedy Lamarr lived in prewar Germany and was mathematically talented. She married an arms manufacturer who took her to meetings where she learned about military technology. She was disgusted with his fascist tendencies (they were both Jewish) and one day in 1937 arranged to go to a party wearing all her expensive jewelry. She and her maid drugged the husband and she escaped to England with the jewelry. She met Louis B. Mayer and wound up starring in a number of films.

George Antheil grew up in Trenton, New Jersey, and acquired the founder of the Curtis Institute of Music as a patron. His most famous work is Ballet Mécanique, which featured (among other things) several player pianos and three airplane propellers with leather strips flapping in them. At an early concert they blew off toupees and hats from members of the audience. Later concerts had them pointing at the ceiling. I heard a recording of it many years ago and was fascinated by it. In spite of what the description suggests, it is real music.

Bluetooth is named after Haraldr Blátönn, who was King of Denmark in the tenth century. Runestones he erected still exist, in Jelling in Denmark. They have been standing outside for a thousand years but soon they will be moved indoors. If your computer or music player has Bluetooth, you will see its logo on the instrument. The logo is a “bind-rune” composed of the runes for H and B.

Send to Kindle

Structured programming

Adam Barr mentioned recently in his blog that Edsger Dijkstra said, “It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.”

I have some personal history relevant to this. I started programming in Microsoft Basic in 1979 (I think) when I bought an Apple II Plus. During the next few years I found myself teaching various courses in theoretical computer science at CWRU and in the process learned about many of the early ideas called structured programming. (This was before object-oriented programming came along.) One main point was that you could do everything with assignment statements, if-then-else and while.

My experience was that once I absorbed these ideas and had done some programming in Algol and Pascal I found that I had achieved more clarity and efficiency in programming in Basic on my home computer. What I was doing was implementing the if-then-else and while structures using Basic’s IF and GOTO. Doing this achieved some modularity by separating out the subroutines as separate blocks of code and avoiding GOTOing to the middle of a subroutine.

For what it is worth, this is evidence that Basic didn’t necessarily permanently ruin people. But I have to say that I had programmed in Basic for only two or three years before I started being Structured, so maybe it takes longer to ruin people.

Send to Kindle