And another computer science great leaves us

John McCarthy, creator of Lisp died recently. Those that wrote chess programs, like William Bader (one of SCS’s senior programmers), and me, knew his work well.

http://linkd.in/svpqAC

We’ve used things we learned from chess programming to create SCS/ClassPag™ for (newspaper classified pagination).

Chess programming provided a rich environment for computer science research. Debugging chess programs was quite difficult. The complexity of the algorithms meant that hand simulation of the program’s logic was often nearly impossible. Chess programmers quickly realized that writing such programs depended on having the best tool for thinking through the programs’ designs.

McCarthy developed Lisp for his AI projects. It replaced OPS5 when he found he could no longer improve his chess program because he could no longer understand it!

Remember that in the early days of chess programming, the development environment wasn’t interactive. Batch compilations and test runs were the norm. Programmers like Ed Kozdrowicki and Dennis Cooper, authors of the CoKo, wrote in FORTRAN. They invented indenting code to show the nesting levels of loops, etc. CoKo was well over 50,000 lines of code. (A single spaced printout of the code was six inches thick.) Like most chess programs in those days, it was tested using all the computer time the authors could beg, borrow or steal. In CoKo’s case just 12 executions! Imagine doing a live show-and-tell of such minimally tested software at a convention (many of these programs were shown at the Association for Computing Machinery annual meetings) before nearly a thousand of your most respected colleagues!

Ken Thompson developed C and Unix as a platform for his chess programming efforts. He and his chess program/machine, Belle, designed at AT&T’s Bell Laboratories, won the North American Computer Chess Championship in 1978. In 1983, Belle became the first chess program to reach the U.S. master level of playing ability.

Ken basically stole the computer on which he did this skunk works development. When asked what he was up to, he replied that he was developing a text processor that the lab (i.e., Bell Labs) could use in document preparation. When asked for a demo, he had to quickly put together what later was called nroff. To compose type for a phototypesetter he then developed troff.

Thompson and McCarthy were both Turing Award winners, which most regard as the Nobel prize for computer science.

Barbara Huberman Liskov, a graduate student of McCarthy’s, wrote a Lisp based chess playing system for her doctorate. She then developed a new paradigm for programming which she embodied in a programming language of her own design called CLU.  CLU was the first programming language that supported all of the concepts that are fundamental to object oriented programming. For this contribution she received the Turing Award. I suspect the design of CLU was influenced by her chess programming experience.

In a biography of Liskov, John V. Guttag, Head of the MIT Electrical Engineering and Computer Science Departmen,t wrote, “CLU was a truly audacious language. It tastefully combined the then novel ideas of 1) data abstraction, 2) iteration abstraction, 3) exception handling, and 4) polymorphic types. CLU was not a “paper”
programming language. Barbara and her students produced a high quality implementation on a variety of platforms. Along the way, they pioneered a number of implementation techniques, e.g., for raising and catching exceptions, that are still used today. Every important programming language since 1975 has borrowed ideas from CLU. Java, for example, owes its notion of inheritance to Simula and Smalltalk, but almost everything else of interest in it was pioneered in CLU.” [

Here is some correspondence between me and Dr. Liskov:

“Dear Dr. Liskov,

Congratulations on winning the Turing award.

I note that your winning of the Turing award is particularly appropriate since Turing himself and John McCarthy, your adviser, were both students of computer chess.

I remember sitting in the lunch room at the Bank of Delaware in 1972 with my fresh BSCS degree from the U of Delaware reading your PhD dissertation. (Chess programs in LISP! Wow!) You were Barbara Huberman then. I was working in data processing operations because I wasn’t trained to program in 1401 Autocoder or 360 COBOL. There was a recession on (RCA had just let 2,000 data processing staff go) so I was glad for the job.

Anyway the VP of data processing (called the IBM Department) (who didn’t have a degree) picked up what I was reading and shrugged when I tried to explain what it was about. I suspect that he thought my interests were at best unusual. He must have had some inkling that I was special because after that he kept giving me little projects that resulted in challenges to the status quo. I started having fun at the BoD job. To this day I say this was thanks to you.

As you know writing chess programs confers on their authors special insights. Unless you are able to use an algorithmic language that supports clear thinking, your hopes for getting working chess programs are slim.

For our work with newspapers we build numerous domain specific
languages. Not surprisingly much of the software we supply to
newspapers solves their NP-hard problems.

I was thinking of you the other day. While scanning several articles on the web I found myself saying “Oh, this one sounds like Barbara.” I checked the authors and there you were. You have a clarity of thought and expression that makes whatever you write an outstanding pleasure to read.

Once again I am delighted to offer you my personal congratulations on your award.

Thanks,
Richard”

Barbara Liskov wrote on 3/27/09:

“thanks so much for your note. I really appreciate it. It’s great
to learn about your story and I’m glad I was able to help (if in
fact I did)!

Best regards,

Barbara Liskov”

Thoughts about Steve Jobs and SCS

SCS became an official Apple developer in 1977. SCS bought an Apple II+
from the just-opened Lehigh Valley Computerland. (I believe SCS was
their first Apple sale, or very nearly so.)

SCS had a contract with American Express to make personal computer
programs for business executives. I think we agreed to write the suite
of programs (called Epics) for $6,000. It included an appointment
scheduler, project planner using the critical path planning method (we
got the algorithm from friends at DuPont which first developed it on a
mainframe), contact manager and several others. The AmEX VP who
contracted with us thought all his executives should have computers of
their own.

The programs were developed in Pascal (UCSD version) with the help of
interns. They worked in an office I outfitted in the lower level of our
home. William started there.

Martha applied to get an AmEX credit card but she was at first refused.
She contacted the VP and said something like, “We are giving you credit
on this project, surely you can return the favor.” SCS got its card
shortly thereafter.

SCS also developed (mostly my code) an information retrieval system
for scientific article citations under contract with Connaught
Laboratories. Their Apple had a 5mb hard disk with a VCR-based backup
tape drive. Complex queries were evaluated in parallel to save disk
accesses because they were very slow. The development machine had 48kb
and three 360kb floppies.

There might not be an SCS today were it not for Steve Jobs and Apple
Computer, the company he co-founded.

Jobs has earned an exalted place in history. He will be missed.

Please enjoy what’s linked to below. There are lessons for SCS today in
what he says.

Steve Jobs: ‘Computer Science Is A Liberal Art’

http://www.npr.org/player/v2/mediaPlayer.html?action=1&t=1&islist=false&id=141118621&m=141128513

Jobs Stanford commencement speech.

Steve Jobs Interview extract.

2. What is perhaps the most valuable thing you learned in college?

“Because I had dropped out and didn’t have to take the normal classes, I
decided to take a calligraphy class. I learned about serif and sans
serif typefaces, about varying the amount of space between different
letter combinations, about what makes great typography great. It was
beautiful, historical, artistically subtle in a way that science can’t
capture, and I found it fascinating.”

3. How was this useful to you?

“Ten years later, when we were designing the first Macintosh computer,
it all came back to me. And we designed it all into the Mac. It was the
first computer with beautiful typography. If I had never dropped in on
that single course in college, the Mac would have never had multiple
typefaces or proportionally spaced fonts.”

4. What lesson did you take from this?

“You can’t connect the dots looking forward. You can only connect them
looking backwards. So you have to trust that the dots will somehow
connect in your future.”

5. What maxim has guided your life?

“You have to trust in something — your gut, destiny, life, karma,
whatever. This approach has never let me down, and it has made all the
difference in my life.”

Computing color positions during ad dummying – some history.

SCS’s ColorAdBoss™ works in conjunction with Layout-8000™ to compute press impositions as color ads are placed during edition design. At least for initial placement, this can be done independently of pressroom help.

The politics of allowing advertising departments to control color ad placement is interesting to say the least. We found this out in the late 80’s when we released, sold and installed ColorAdBoss’s predecessor called WebPresser™.

WebPresser was unique technology for the newspaper business. It was (and except for ColorAdBoss, still is) the only successfully marketed computer program which actually computes press layouts while the edition is being designed and therefore while more color positions can still be sold.

This sounds like something every advertising department would love to use – and perhaps they would. But it challenges the traditional role of the pressroom foreman and his relationship with the layout staff.

By the end of 1993 we had sold nearly $100K of WebPresser technology to 59 sites, but the importance of WebPresser went far beyond the minimal amount of our revenue that this represented. Its importance was more closely tied to how it distinguished us from competitors who might also market ad dummying software. WebPresser had tactical and strategic importance which helped us protect our market share with Layout-8000. Here is what it looked like in 2002.

Read my memo of March 7, 1989 about the back-story including how we used it tactically to defeat a challenge from Composition Systems Inc. (CSI) that threatened our dominance in the automated dummying business. The memo also contains a good description of the potentially adversarial battle between the advertising department and the pressroom foreman about how much color can be run in the paper and the edge that WebPresser could give the advertising staff.
Here is a summary of some additional details from other folks who were around and involved in the story for those who remember the era.

Creative And Innovative Ads – Good Idea or a Distraction?

Follow SCS on Facebook and on Twitter Let’s say your marketing department comes up with a product that they claim is “new and brilliant.”  After being impressed, you go to the production and technology departments and say, “Look at this … Continue reading →

Tools to assess newspaper readability – are they still important?

I recently read a grant request for research that planned to use the Gunning-Fog index to assess newspaper readability. One PhD thesis I reviewed years ago for the University of Texas suggested that when newspapers began hiring college graduates (and the readability score of newspaper copy they wrote got higher – i.e., written for a higher education level), the audience for the newspaper’s content declined in proportion. The thesis asserted that this was the primary cause for the circulation declines in the 60′s and 70′s.

Robert Gunning helped make the WSJ more readable. Barney Kilgore was the transformative journalist who hired Gunning. This lead to the
Journal becoming one of the most readable newspapers in the country.
Its circulation rapidly grew from 250,000 to over a million as Gunning’s suggestions for clear writing were adopted. (He said you don’t need complex language to explain complex topics. In fact, complex language works against understanding.)

The Audit Bureau of Circulation recently reported that the WSJ was the only newspaper that increased its daily circulation (to over 2 million) between October, 2009 and March, 2010. Is there still a message here about clear writing?

At the American Newspapers Publishers Association Research Institute
(ANPA/RI) in the mid-70s, I was responsible for creating and testing an advanced fog index calculator. The Society of Newspaper Editors
campaigned against this and several other applications we developed,
including one that did relatively intelligent story cutting and fitting. They were opposed to almost any machine analysis of editorial
content. They made quite a stink and the RI backed off.

Later nearly everyone liked my spelling checker. Word processors of the day checked 60 words a minute. My patented device checked 15,000 per second. The software version was pretty fast and allowed the mini-computer based newsroom systems of the day to provide spelling checking. (In our current systems we test words at over 125,000 per second. The tester can work on any set membership task.)

The grant request I read also addressed the idea of measuring quality and/or political bias in metro newspapers. I’m much more curious about local content in local newspapers than in metros. The large national newspapers seem to offer few surprises regarding quality (usually good) and political bias (predictable). I’d like to see some thought put into assessing the quality and depth of local coverage by community newspapers.

There seem to still be plenty of areas where computer science could help newspapers improve. Are they willing to listen?

Writing good code: opinions of the Theorist, the Implementer and the Pragmatist

A conversation with a Girl who Writes Code

Sharon: Dad, why would you use a macro instead of a procedure or function?

Dad:  Good question, Sharon.  I have some opinionated experts here to
help answer this important question.  What are your thoughts on the subject?

Sharon: I write a lot of code.   I want it to be reliable, maintainable,
efficient and easily produced.

Pragmatist: Joel (as in “Joel on Software”) says “Don’t repeat yourself.”

Sharon:  Well, if code is to be easily maintainable, it will have to be
readable.   I’ll want terse but easily understood code.

Dad:  Wouldn’t it be nice if programming could be more automated?

Sharon:  You mean like David Parnas wanted to see.  An engineering
discipline of software development, where tested components were
manufactured and then combined into reliable sub-assemblies and from
there into systems?

Dad: Yes, exactly.   Parnas thought doing software needed to be a more
systematic endeavor.

Sharon:  What became of his work?

Dad: The Japanese claimed to have built such a culture and the West
thought it would take over the world.  That was 20 years ago, and it
hasn’t happened yet.

Sharon: Back to the question of macros vs. procedures and functions, please!

Implementer:  My compiler includes a pre-processor that expands macros.
You get inline code on macro invocation.  For procedures and functions
you get reusable code blocks that can be invoked via procedure calls
over and over.  The macros execute faster because they are inline while
they make bigger code images because they are replicated whenever
invoked.   Procedures and functions usually save space but have the
overhead of the procedure or function call and eventual return.

Theorist:  Actually thinking of the implementation doesn’t much help
with understanding the real differences.  You want to write clearer yet
more terse and reliable programs.  This starts with the  notion of type.
Types are the names of sets of values. Variables hold values. The
beauty of types is that with types, programs written in imperative
programming languages offer a way to declare consistency requirements
for operands.  When operands of the same type can be treated the same,
appropriate operators can be defined.  If variables (operands) have
known, that is, static types, then compilers can check for consistent
usage.  This protects the programmer from making many intractable errors
and even allows more optimized code generation.

Declare a type and a set of procedures and functions that work with it
and you have the making of a library of components.  Step one in
engineering software.

Better yet, combine these two ideas and make classes.  You
can make things doubly secure.

Pragmatist:   I’m not so sure.  Making classes helps me encapsulate
abstract types and operators, but how does it work in practice?  Let’s
say I need to process things last in, first out, that is, in stack-like
fashion.   So I know the logic for handling stacks.  Where do I go from
there?   I’d like to have many stacks, each differing by the type of
elements the stack holds and yet having the same operators. It’s
complicated. I’m confused.

Theorist:  No confusion necessary.   You just encapsulate the notion of
stack and apply operators with the same name.  It’s called polymorphism.
It looks the same, but works differently.

Pragmatist:  You mean it looks like a duck, walks like a duck, quacks
like a duck, but isn’t a duck?  What if some stacks are slightly
different from others?

Theorist: No problem.  Just include the parts that are the same and
differentiate that which is different.  It’s called inheritance.

Pragmatist: We have gotten a long way from abbreviating code for clarity
and efficiency.  Is this really going to solve the problem Parnas lays out?

Dad: Hasn’t yet.

Implementer:  You would not believe how complex compilers are getting
these days.

Dad: And then there is the structure clash.  Database management systems
make data access available externally to and independently of
application code.   Encapsulated data certainly cannot be externally
available.  That’s why there are relational to object-oriented mapping
technologies.  It might just be that one notion or another is incompatible.

Sharon:  So what’s wrong with class libraries?

Dad:  Not much.  However the bigger and more versatile they get, the
more complex and less transparent they get. (Even Julian Assange knows
lack of transparency is bad.) If a programmer runs into a situation
where the library routine is almost, but not quite, what he or she
needs, what happens?  If the library is a set of binaries, then a new
module is written.  If there is source available, then the source might
be edited forking the module or increasing its complexity and
potentially introducing instability.

BTW – When Parnas wrote about the software engineering crisis, Fortran
was being promoted as a tool for automated programming.  How times have
changed and how much they have stayed the same.

Sometimes it is better to just make a new language, one that has a
notation that very precisely fits the application domain – a domain
specific language, (DSL).

Sharon:  Where do macros come in?

Dad:  Early on elaborate macro processing was built into assemblers and
text processors (composition systems).

For typography you could name a visual effect and apply it to any type
(i.e., copy) you wished.  Properly done you could extend a macro
processor-based composition language, like RNF, troff or TeX, to many
application areas.  They allowed you to define your own domain specific
languages.

For assemblers, macro facilities made generating appropriate tedious
code sequences easier.  Eventually, macro processors built for
assemblers became so general purpose that the code a programmer wrote
appeared to be written in a high-level structured language.   Macro
processors could even be used to re-target code to different machine
architectures.

Powerful macro processing facilities were built into some compilers.
These allowed programmers to code extensions to the base language that
looked as if they were there from the start.

Theorist:  Yes, but the generality of macro processing must be weighed
against the lack of verification that comes with that power.  You
should have seen the macro processor that was first used to translate
C++ into C.

Pragmatist:  All this theory sounds good, but I still want to make
applications that work and to do so quickly.   I like to use module
builders.   What do you think of them?

Dad: I love module builders.   They are the perfect anti-theoretical
technology.  They work extremely well in practice but offer virtually no
theoretical underpinning.  You couldn’t get a PhD studying them, ever,
but you could build SugarCRM and dozens of other powerful and useful
applications.

If it were not for module builders, the web would be a much less
interesting place.

What we have made and are continuing to develop is technology which
includes generalized module building technology as a component.

Much of this relates back to macros.  Where they started and left off
was as tools for manipulating code.   Code – not objects, abstract data
types, stacks, queues, etc., just code.  Code is what you wanted to make
in the first place, after all.

Only by manipulating code can you deal with non-local issues globally,
as in the case of security technology.  It needs to operate everywhere
but appear nowhere.

Much of what gives theorists heartburn can be dealt with by targeting a
very strongly typed domain specific language.  Its compiler can pick up
type conflicts.

Still, one has to ask about our approach at SCS.  What is it?  Will it work?

Our tools development proceeds both top down and bottom up.   There are
three basic parts – the DSL, called the spice formula language; the Spice
Pattern Language and the Spice Macro Pre-processor.   They function
together to both become and to generate applications.  Bassett frames,
macros, patterns and most other concepts that support automatic program
generation are part of their feature set.   That’s the top down part.

The bottom up part is that as the tools are enhanced they are put to
almost immediate use.  Many features are incorporated based on day-to-day programming experience.   Programmer desire drives feature
development.  The tools are used to build very large mission-critical
applications in which new versions are deployed agilely nearly every
four weeks.  Every iteration includes multiple enhancements (often major
ones) and significant code re-factoring to take advantage of tool
enhancements.

Best of all it works at major companies every day.

Richard J. Cichelli (aka Dad)
President, SCS

 

What you will find here

Richard J. Cichelli, the President and co-owner of SCS, has been involved in the development of newspaper software almost since newspapers began using computers.  Before joining me (Martha) at SCS, he was the Research Manager of Computer Applications at the ANPA/RI (predecessor of the NAA – Newspaper Association of America).  From that era came Layout-80 (later transformed into Layout-8000), the first and preeminent page dummying software as well as ReQueSt-DB (an apparatus and software for providing searchable classified ads on cable TV) which has matured and spawned some pretty impressive search algorithms.

Richard is more than an IT expert or a technologist.  What drives him (in addition to his passion about newspapers) is the desire to push the limits of computer science to implement the best algorithms with the best tools he can design. He’s committed to creating software that is fast, efficient, machine and operating system independent and that solves “tough problems.”

That’s what you’ll read about here – the research, the thinking, the design philosophy and the creation of development tools that continues to make this possible.

Martha J. Cichelli