Solving SICP

This report is written as a post-mortem of a project that has, perhaps, been the author’s most extensive personal project: creating a complete and comprehensive solution to one of the most famous programming problem sets in the modern computer science curriculum “Structure and Interpretation of Computer Programs”, by Abelson, Sussman, and Sussman (\cite{Abelson1996}).

It measures exactly:

  • How much effort SICP requires (729 hours 19 minutes (over eight months), 292 sessions).
  • How many computer languages it involves (6).
  • How many pieces of software are required (9).
  • How much communication with peers is needed.

It suggests:

  • A practical software-supported task management procedure for solving coursework.
  • Several improvements, on the technical side, to any hard skills teaching process.
  • Several improvements, on the social side, to any kind of teaching process.

The solution is published online (the source code and pdf file):

This report (and the data in the appendix) can be applied immediately as:

  • A single-point estimate of the SICP problem set difficulty.
  • A class handout aimed at increasing students’ motivation to study.
  • A data source for a study of learning patterns among adult professionals aiming for continuing education.
  • An “almost ready” protocol for a convenient problem-set solution procedure, which produces artefacts that can be later used as a student portfolio.
  • An “almost ready”, and “almost convenient” protocol for measuring time consumption of almost any problem set expressible in a digital form.

Additionally, a time-tracking data analysis can be reproduced interactively in the org-mode version of this report. (See: Appendix: Emacs Lisp code for data analysis)

Read full paper

Let us discuss SRFI-216: SICP Prerequisites

Abstract

001-Sicp_js.png

This post is a not-so-technical introduction to the Scheme Request for Implementation 216: SICP Prerequisites, that I have written and made available for discussion. (Please, contribute!)

SICP stands for the “Structure and Interpretation of Computer Programs”, a world-famous introductory programming textbook.

It’s aim is to make the exercises and examples from the book be available for any Scheme system bothering to provide it, and not just MIT/GNU Scheme and Racket (which doesn’t even consider itself a Scheme any more). Before this SRFI an issue tracker request asking for SICP support would have been looking vaguely. Now you can just write “Could you consider providing SRFI-216 (and 203)” in your implementation.

In order to write this SRFI, I went through the whole book and solved all the exercises. However, my experience is just mine, and to make a truly good common vocabulary, community feedback is required.

For technical detail and more background, I am inviting you to read the whole article.

Read the whole story

A Mathematical Theory of Systems Engineering: The Elements by A. Wayne Wymore

The review on the book by Albert Wayne Wymore
‘A Mathematical Theory of Systems Engineering — The Elements’

wymore1967book_cover

This review must be prefaced with a quotation from the last chapter of the book, which is sort of really indicative of what you should expect from it if start reading.

“(Alan) Turing’s work is very important; there is no question about that. He illuminated many fundamental questions. In a sense, however, it is unfortunate that he chose to write in terms of ‘computability’ especially in view of development, subsequent to Turing’s work, of modern computers. As a theory of ‘computability’, Turing’s work is quite important, as a theory of ‘computations’, it is worthless.

“Wow!”, you would think. “This man has the audacity to defy Turing himself! He must be offering something really outstanding instead!”
Well, not really. What is then that he is offering instead?

To start reviewing a book about systems engineering, one would have to first, at least try to specify what systems engineering is. But even such a simple, supposedly, term would have to be met with caution. Well, obviously, it’s connected with the engineering of systems.

But if you open the definition of a system in the book, you’ll see the following:

A system is a set Z = {S, P, F, M, T, \sigma}, where 
    S is a set not empty,
    P is a set not empty,
    F is an admissible (ignore this word at the moment) set of input functions with values in P,
    M is a set of functions each defined on S with values in S,
    T is a subset of R containing 0,
    \sigma is a function defined on FxT with values in M such that \sigma is onto and 
        (1) the identity mapping \omega \in M and for every f \in F, \sigma(f,0) = \omega;
        (2) if f \in F, s, t, and s+t \in T, then \sigma(f -> s, t)\sigma(f,s) = \sigma(f, s+t);
        (3) if f and g \in F, s \in T, and f(t) = g(t) for all t \in R(s), then \sigma(f,s) = \sigma(g,s)

Wow. Looks really cryptic, doesn’t it?

Factually, if you open almost any other book on the subject, you’ll most probably see a completely different definition, likely dealing with loosely defined terms, such as ‘components’, ‘interfaces’, ‘actors’ and similar things from project management jargon.

For example, this is the definition of a system from the INCOSE’s Systems Engineer’s Handbook.

“… an integrated set of elements, subsystems, or assemblies that accomplish a defined objective. These elements include products (hardware, software, firmware), processes, people, information, techniques, facilities, services, and other support elements. (INCOSE)”

“Well”, you may tell me, “perhaps this Dr. Wymore is meaning something completely different?” Are they even speaking about the same field of knowledge?

Let’s check:

‘A. Wayne Wymore founded the first academic department of Systems Engineering in the world at the University of Arizona in 1960. He pioneered Mathematical-based Systems Engineering and later led Model-based Systems Engineering. He was an early and ardent supporter of the fomenting of INCOSE. He has led self-evaluation of Systems Engineering education, and continues to be one of the most prominent theoreticians of the Systems Engineering community. In addition to his teaching, writing, and consulting, he has participated in pro bono projects to bring a Systems Engineering approach to social service organisations.

INCOSE (2003) “INCOSE’s Pioneer Award” text; cited in: Wayne Wymore biography at incose.org, last updated: 19 Nov 2007.’

Wow, that’s impressive. So Dr. Wymore actually founded the whole Systems Engineering way of thinking. How come the definitions are so different?

The answer can be found, interestingly, in the auto-biography of Dr. Wymore, written by himself (http://sysengr.engr.arizona.edu/wymore/WWAutobiography.htm):

“Now (1987) I had a chance to finish the book on which I had been working for 11 years, since the publication of Systems Engineering Methodology for Interdisciplinary Teams in 1976. This was to be the book that I write for myself, for pleasure, with little regard for the existence of a market. It would be mathematically as rigorous as I was able to make it and it was intended to include every aspect of system science that would be necessary for successful systems engineering.  The rigor doubtless would be tedious for the present day systems engineer.  It might take a generation or two, perhaps more, before the profession would see fit to train systems engineers at a sufficiently high level of mathematical sophistication to qualify themselves to take on the design of a really vast and complex system such as the national health care system.”

Please, note the *the rigor doubtless would be tedious for the present day systems engineer*.

Has those two generations passed already? Or perhaps just one? 1987-2017 = 30 yeas.

So, basically, Wymore had seen the power of mathematics in describing all possibly thinkable systems, back then, in 1967. But even today, in 2019, we still don’t have sufficient enough computing systems to implement all the prerequisites for a self-supporting, computable Systems Engineering ecosystem.

Well, I have said ‘Systems Engineering’ so many times, and still hasn’t properly explained what it is.

The problem, it IS a bit hard to explain what it is. The informal definition of ‘assembling systems from pieces’ leaves more questions than answers anything.

Actually, Dr. Wymore actually had the same feeling, so he decided to give the same subject a more fundamental, mathematical base.

So, from a mathematical point of view, systems engineering is sort of a mathematics, and a skill of solving equations in a special functional space, which Wymore calls an ‘admissible input functions’ space. Without getting into too much detail, it is a somehow queer space of functions, which can have quite a lot of discontinuities, and are not obliged to be in any sense smooth, but are required to be sort of scale and shift independent, representing time and space isotropy.

Wymore claims that almost all imaginable systems (hardware or software, or even human organisations) can be represented as formulae on top of the ‘admissible functions’. And he builds a relatively comprehensive theory, describing how to relate various mathematical descriptions of systems requirements (input, output, state) with his definition of what is a system.

systems_image

Interestingly, the most ‘meaty’ thing, that is how to actually describe a system mathematically, is given very little attention in the book. Because that is, supposedly, heavily dependent on the nature of the system built. But if the system IS already described, Wymore’s theory is ready to give some insight on how to predict the system’s behaviour, and how to use the power of mathematics to partition the system into parts. (Which IS, in some sense, the main thing expected from a systems engineer in practice.)

Remember, this book comes from 1967. There is, however, the second book in the series, written in 1993 (*model-based* systems engineering), which puts more emphasis exactly on those two missing aspects of the theory. On modelling and on simulating. (I haven’t yet read it, but it’s on my plans.)

You would ask me: how does it actually work in practice? Is Wymore’s mathematics actually used somewhere?

The answer is a bit disappointing. I haven’t seen any applications of the theory, and more modern books on systems engineering seem to be full of marketing bullshit, not of consistent mathematics.

Why? Well, so far, the world is still ruled by people more focused on intuitive thinking, rather than mathematical thinking. And I don’t see much of it changing in the foreseeable future. And Wymore’s theory seems to be in the worst possible location for a mathematical theory. It requires the users to be BOTH mathematics-savvy, AND having good intuition in those places where no good mathematical theory exists.

But how is Systems Engineering working nowadays then? Well ,the actual answer is ‘difficultly’. In the situation when you can’t force people to not just know mathematics, but even learn programming, you’re left with an only option of ‘programming people’ by writing documents. And to some extent, the systems engineering of now, is a science of writing instructions for people, and drawing diagrams (rather than writing code), because generally, unprepared people are easier at understanding graphics, not text.

I guess, you’re starting to feel where I’m going to. I am going to SysML.

sysml-diagram-taxonomy

SysML (and UML) is an attempt to make programming ‘imprecise’. That is, actually, a software program is always a model of behaviour of some system. But too often we cannot formulate the system precisely enough to actually write a robot to satisfy the system specification.

Nevertheless, we often can at least sketch the system’s definition in UML/SysML. (And frankly, it was a very bad idea to make the canonical representation of the language graphical, not text-based, but thanks to PlantUML, the situation is now much-much less cumbersome for people like me, who like precision.) Who knows, maybe at some point we will actually have better tools for the interaction between graphics and logic (code). Maybe the second tome (1993) will give me more insight into how this works. Especially since Wymore seems to be providing a more computer-friendly language called T3SD, a domain-specific textual language for describing systems. Maybe it will serve as a good bridge between the mathematical and the visual parts of systems design.

So, getting back to the Mathematical Theory of Systems Engineering: The Elements.

This book is definitely a must-read for a systems engineer. If you don’t understand the mathematics behind what you are doing, you’re not doing it right in any respect.

Is it well written? Well, in almost every aspect — yes. I feel some influence of the social nature of the systems engineering job — the book has a rich vocabulary, and with an exception of several rather confounding theorems, is clearly and consistently written.

Is this book of immediate practical applicability? I wouldn’t be so sure about this, but maybe the second book will change my mind.

Is this book enough as a first introduction into the subject? Still, no. Systems engineering in practice is much more than just mathematics behind the system specifications. Some practical information on how to do *informal* descriptions of systems is seriusly needed.

And, I guess, for every subject I’m reading about, I should be asking myself a little bit weird question: “should such thing be taught in middle school?”.
And in some sense, I would rather answer “yes” than “no” to such a question.
I still remember studying physics at school, and I do remember than one of the biggest complaints I had about it was that physics was presented to us as just a set of disconnected, scattered facts, each of them having a different structure.
Having then not interconnected was already bad enough, but it was the inconsistency of internal structures than was really driving me crazy. (I still don’t know physics, even though I am working (!) as physicist now.)

And in some sense, the MTOSE book is making a small step towards providing a unified base under various physical models and phenomena, and also can be seen as providing links to the other modellable subjects, such as biological phenomena, for example.

Should you read the book? I don’t know. I guess, we need a simpler book on systems engineering for ordinary people, which would still keep at least a trace of mathematical rigour. But this one… perhaps not, unless you are a working engineer or a mathematician. Then — yes. And of course, if you are a systems engineer, it is must.