October 31, 2022 6:11 PM

The Inventor of Assembly Language

This weekend, I learned that Kathleen Booth, a British mathematician and computer scientist, invented assembly language. An October 29 obituary reported that Booth died on September 29 at the age of 100. By 1950, when she received her PhD in applied mathematics from the University of London, she had already collaborated on building at least two early digital computers. But her contributions weren't limited to hardware:

As well as building the hardware for the first machines, she wrote all the software for the ARC2 and SEC machines, in the process inventing what she called "Contracted Notation" and would later be known as assembly language.

Her 1958 book, Programming for an Automatic Digital Calculator, may have been the first one on programming written by a woman.

I love the phrase "Contracted Notation".

Thanks to several people in my Twitter feed for sharing this link. Here's hoping that Twitter doesn't become uninhabitable, or that a viable alternative arises; otherwise, I'm going to miss out on a whole lotta learning.


Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

October 30, 2022 9:32 AM

Recognize

From Robin Sloan Sloan's newsletter:

There was a book I wanted very badly to write; a book I had been making notes toward for nearly ten years. (In my database, the earliest one is dated December 13, 2013.) I had not, however, set down a single word of prose. Of course I hadn't! Many of you will recognize this feeling: your "best" ideas are the ones you are most reluctant to realize, because the instant you begin, they will drop out of the smooth hyperspace of abstraction, apparate right into the asteroid field of real work.

I can't really say that there is a book I want very badly to write. In the early 2000s I worked with several colleagues on elementary patterns, and we brainstormed writing an intro CS textbook built atop a pattern language. Posts from the early days of this blog discuss some of this work from ChiliPLoP, I think. I'm not sure that such a textbook could ever have worked in practice, but I think writing it would have been a worthwhile experience anyway, for personal growth. But writing such a book takes a level of commitment that I wasn't able to make.

That experience is one of the reasons I have so much respect for people who do write books.

While I do not have a book for which I've been making notes in recent years, I do recognize the feeling Sloan describes. It applies to blog posts and other small-scale writing. It also applies to new courses one might create, or old courses one might reorganize and teach in a very different way.

I've been fortunate to be able to create and re-create many courses over my career. I also have some ideas that sit in the back of my mind because I'm a little concerned about the commitment they will require, the time and the energy, the political wrangling. I'm also aware that the minute I begin to work on them, they will no longer be perfect abstractions in my mind; they will collide with reality and require compromises and real work.

(TIL I learned the word "apparate". I'm not sure how I feel about it yet.)


Posted by Eugene Wallingford | Permalink | Categories: Patterns, Personal, Teaching and Learning

October 23, 2022 9:54 AM

Here I Go Again: Carmichael Numbers in Graphene

I've been meaning to write a post about my fall compilers course since the beginning of the semester but never managed to set aside time to do anything more than jot down a few notes. Now we are at the end of Week 9 and I just must write. Long-time readers know what motivates me most: a fun program to write in my student's source language!

TFW you run across a puzzle and all you want to do now is write a program to solve it. And teach your students about the process.
-- https://twitter.com/wallingf/status/1583841233536884737

Yesterday, it wasn't a puzzle so much as discovering a new kind of number, Carmichael numbers. Of course, I didn't discover them (neither did Carmichael, though); I learned of them from a Quanta article about a recent proof about these numbers that masquerade as primes. One way of defining this set comes from Korselt:

A positive composite integer n is a Carmichael number if and only if it has multiple prime divisors, no prime divisor repeats, and for each prime divisor p, p-1 divides n-1.

This definition is relatively straightforward, and I quickly imagined am imperative solution with a loop and a list. The challenge of writing a program to verify a number is a Carmichael number in my compiler course's source language is that it has neither of these things. It has no data structures or even local variables; only basic integer and boolean arithmetic, if expressions, and function calls.

Challenge accepted. I've written many times over the years about the languages I ask my students to write compilers for and about my adventures programming in them, from Twine last year through Flair a few years ago to a recurring favorite, Klein, which features prominently in popular posts about Farey sequences and excellent numbers.

This year, I created a new language, Graphene, for my students. It is essentially a small functional subset of Google's new language Carbon. But like it's predecessors, it is something of an integer assembly language, fully capable of working with statements about integers and primes. Korselt's description of Carmichael numbers is right in Graphene's sweet spot.

As I wrote in the post about Klein and excellent numbers, my standard procedure in cases like this is to first write a reference program in Python using only features available in Graphene. I must do this if I hope to debug and test my algorithm, because we do not have a working Graphene compiler yet! (I'm writing my compiler in parallel with my students, which is one of the key subjects in my phantom unwritten post.) I was proud this time to write my reference program in a Graphene-like subset of Python from scratch. Usually I write a Pythonic solution, using loops and variables, as a way to think through the problem, and then massage that code down to a program using a limited set of concepts. This time, I started with short procedural outline:

    # walk up the primes to n
    #   - find a prime divisor p:
    #     - test if a repeat         (yes: fail)
    #     - test if p-1 divides n-1  (no : fail)
    # return # prime divisors > 1
and then implemented it in a single recursive function. The first few tests were promising. My algorithm rejected many small numbers not in the set, and it correctly found 561, the smallest Carmichael number. But when I tested all the numbers up to 561, I saw many false positives. A little print-driven debugging found the main bug: I was stopping too soon in my search for prime divisors, at sqrt(n), due to some careless thinking about factors. Once I fixed that, boom, the program correctly handled all n up to 3000. I don't have a proof of correctness, but I'm confident the code is correct. (Famous last words, I know.)

As I tested the code, it occurred to me that my students have a chance to one-up standard Python. Its rather short standard stack depth prevented my program from reaching even n=1000. When I set sys.setrecursionlimit(5000), my program found the first five Carmichael numbers: 561, 1105, 1729, 2465, and 2821. Next come 6601 and 8911; I'll need a lot more stack frames to get there.

All those stack frames are unnecessary, though. My main "looping" function is beautifully tail recursive: two failure cases, the final answer case checking the number of prime divisors, and two tail-recursive calls that move either to the next prime as potential factor or to the next quotient when we find one. If my students implement proper tail calls -- an optimization that is optional in the course but encouraged by their instructor with gusto -- then their compiler will enable us to solve for values up to the maximum integer in the language, 231-1. We'll be limited only by the speed of the target language's VM, and the speed of the target code the compiler generates. I'm pretty excited.

Now I have to resist the urge to regale my students with this entire story, and with more details about how I approach programming in a language like Graphene. I love to talk shop with students about design and programming, but our time is limited... My students are already plenty busy writing the compiler that I need to run my program!

This lark resulted in an hour or so writing code in Python, a few more minutes porting to Graphene, and an enjoyable hour writing this blog post. As the song says, it was a good day.


Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development, Teaching and Learning

October 02, 2022 9:13 AM

Twitter Replies That No One Asked For

I've been pretty quiet on Twitter lately. One reason is that my daily schedule has been so different for the last six or eight weeksr: I've been going for bike rides with my wife at the end of the work day, which means I'm most likely to be reading Twitter late in the day. By then, many of the threads I see have played themselves out. Maybe I should jump in anyway? Even after more than a decade, I'm not sure I know how to Twitter properly.

Here are a few Twitter replies that no one asked for and that I chose not to send at the time.

• When people say, "That's the wrong question to ask", what they often seem to mean -- and should almost always say -- is, "That's not the question I would have asked."

• No, I will not send you a Google Calendar invite. I don't use Google Calendar. I don't even put every event into the calendaring system I *do* use.

• Yes, I will send you a Zoom link.

• COVID did not break me for working from home. Before the pandemic, I almost never worked at home during the regular work day. As a result, doing so felt strange when the pandemic hit us all so quickly. But I came first to appreciate and then to enjoy it, for many of the same reasons others enjoy it. (And I don't even have a long or onerous commute to campus!) Now, I try to work from home one day a week when schedules allow.

• COVID also did not break me for appreciating a quiet and relatively empty campus. Summer is still a great time to work on campus, when the pace is relaxed and most of the students who are on campus are doing research. Then again, so is fall, when students return to the university, and spring, when the sun returns to the world. The takeaway: It's usually a great time to be on campus.

I realize that some of these replies in absentia are effectively subtweets at a distance. All the more reason to post them here, where everyone who reads them has chosen to visit my blog, rather in a Twitter thread filled with folks who wouldn't know me from Adam. They didn't ask for my snark.

I do stand by the first bullet as a general observation. Most of us -- me included! -- would do better to read everyone else's tweets and blog posts as generously as possible.


Posted by Eugene Wallingford | Permalink | Categories: General, Personal