On this page:
Software Development
Home
7.9.0.3

Software Development

Software Development

From the first day of the semester forward we expect students (you) to visit this page once per 24 hours.

image Monday, October 26th, 2020 8:25:42am

The creation of potentially infinite (extremely large) decision trees has apparently posed more of a challenge than expected. This post explains how the use of the Fundamentals II principles gets us an “infinite chain” of natural numbers, analogous to the hints from Fundamentals I hint I posted on Piazza. The generalization to a tree shape is straightforward. The post exclusively uses class syntax; if your language supports a lambda-like construct feel free to create a mix of class-based and functional design.

Naively we may describe the infinite chain of natural numbers as follows:

    An infinite chain (IC) of natural numbers starting at n is one of:

      -- node(n,IC)

Interesting functions/methods on such a structure might be: current and next.

A student near the halfway point of Fundamentals II will understand that this description calls for both an interface and (at least) one class definition. We can formulate the interface already like this:

INaturals

// represents a stream of natural numbers starting at current

interface INaturals {

  // get the head of _this_ stream of natural numbers

  int /* >= 0 */ current();

 

  // get the rest of _this_ stream of natural numbers

  INaturals next();

}

A class that implements INaturals could construct a chain. The two methods give a client module access to the chain’s pieces.

If, however, a Fundamentals I assignment (or exam problem) confronted you with such a data definition after about four weeks, you would have immediately reacted with “this data definition is nonsense” because it is impossible to construct any examples. And constructing examples from data definitions is the first “test” of any data definition. So before we implement the interface, let’s fix the infinity problem.

The words “laziness” and “generators” in 4 — The Game Tree are critical hints here. Both delay a computation. In Fundamentals I we often say lambda delays a computation, and in Fundamentals II we say the same about methods. So this suggests that at the informal level the data definition should look like this:

    An infinite chain (IC) of natural numbers starting at n is one of:

      -- node(n, [Natural -> IC])

The notation [Natural -> IC] from Fundamentals I is short-hand for a data definition of a function (method) that takes a natural number to an IC. And it is straightforward to create examples for this in ISL+:
(define more (lambda (x) (make-node (+ x 1) more)))
(make-node 0 more)
The true intent, though, is that this function can construct the rest of chain from n and that this n is really just the current head.

This class realizes only half of the idea of “laziness.” The other half concerns caching the result of the private method.

In Fundamentals II, we can express this last idea as directly as possible with a private field and a private method:

Naturals

// a concrete data representation of natural numbers starting at n

class Naturals implements INaturals {

  private int n;

 

  public Naturals(int /* >= 0 */ n) { this.n = n; }

 

  public int current() { return this.n; }

 

  public INaturals next() { return this.create(); }

 

  private INaturals create() {

    return new Naturals(this.n+1);

  }

}

Since methods have access to the object’s fields we don’t need to hand create the current head of the chain; a chain method can retrieve the current head from the (implicit) object (argument).

If you can’t get it to run, the type setting likely introduced a typo.

Okay, let’s create a main class to run it all:

AllNaturals

class AllNaturals {

  public static void main(String argv[]) {

    INaturals all    = new Naturals(0);

    INaturals from13 = new Naturals(13);

    print10(all);

    print10(from13);

  }

 

 

  private static void print10(INaturals in) {

    for(int i = 0; i < 10; i++) {

      System.out.println(in.current());

      in = in.next();

    }

  }

}

The private method retrieves the first ten “levels” of the “decision chain.” For an actual tree, you may wish to proceed recursively to match the data definition.

image

Saturday, October 24th, 2020 7:38:41pm

Jake H. discovered an ambiguity in the test task of 5 — The Strategy. This Saturday night revision resolves the ambiguity.

image

Wednesday, October 21st, 2020 4:26:34pm

Based on observations from my TAs, I have clarified the two "functionality bullets" in 4 — The Game Tree.

image

Tuesday, October 20th, 2020 1:18:29pm

See 4 — The Game Tree for a revision of the deadline.

image

Friday, October 16th, 2020 9:22:42pm

NULLHoare’s billion dollar mistake

This problem comes up time and again. Today in the 135 pm section, a Java code walk represented "absence" once again with null, and I pointed to Fundamentals II where we insist on data-representing Aggain, also see Bloch’s Effective Java.

    A Something is one of:

     -- A ...

     -- B ...

     -- C ...

into

    interface ISomeThing {}

    

    class A implements ISomeThing {}

    class B implements ISomeThing {}

    class C implements ISomeThing {}

which of course applies to binary enumerations, too.

K. asked about Java’s optional type (in one of the more recent versions of the language). The idea is absolutely the correct one, and it has been around for approximately forever. The realization in the standard took a long time, and the interface is clumsy. Functional languages such as Haskell and Maybe and SML and option have done significantly better. Sadly, Java is often a compromise between what "old" people think programming should be and the designers and specifiers of the language who understand the language design research quite well.

image

Thursday, October 15th, 2020 5:43:36pm

The following is a script that an experienced Racketeer would write with the principles of Fundamentals I in mind without writing down all pieces.

xcheck

#! /usr/bin/env racket -tm

#lang racket/base

 

;; Usage: run

;;   ./xcheck PathToSpecification

;; at the top-level of a repo. It checks whether the repo is organized

;; according to the Spec found in PathToSpecification.

 

#; {type Spec = Symbol u .* u [** Symbol] u [Cons Symbol [Listof Spec]]}

;; Symbol is a name, .* means "any file", [** Symbol] means optional;

;; (S . Spec) is the specification for sub-directory S

 

(provide main #;{PathString to Specification of required file/dir org})

 

(require racket/match racket/set racket/format)

 

(define (main lvl) (check-spec (with-input-from-file lvl read)))

 

#; {Spec -> Void}

(define (check-spec sp [path "."])

  (define-values (must may) (level->set sp))

  (check-1-level (member '|.*| sp) must may path)

  (define dirs

    (for/list ([l sp] #:when (and (pair? l) (set-member? must (~n (car l)))))

      l))

  (for* ([m dirs][dir (in-value (~n (car m)))])

    (when (directory-exists? dir)

      (parameterize ((current-directory dir))

        (check-spec (cdr m) (~a path "/" dir))))))

 

#; {Boolean [Setof String] [Setof String] PathString -> Void}

(define (check-1-level any must may P)

  (define all (map path->string (directory-list)))

  (for ([m must] #:unless (matched? m all)) (displayln `[,m missing at ,P]))

  (unless any (extras all (set-union must may) P)))

 

#; {[Listof String] [Listof String] PathString -> Void}

(define (extras F Pats Path)

  (define (match-one f) (for/or ([p Pats]) (matched? p (list f))))

  (define xtra (for/list ([f F] #:unless (match-one f)) f))

  (when (pair? xtra) (displayln `[,xtra should not exist at ,Path])))

 

#;{Spec -> (values [Setof String] [Setof String])}

(define (level->set lvl)

  (define-values (man opt)

    (for/fold ([man '()][opt '()]) ([l lvl])

      (match l

        [`[** ,k]     (values man (cons (~n k) opt))]

        [`[,d ,_ ...] (values (cons (~n d) man) opt)]

        [_            (values (cons (~n l) man) opt)])))

  (values (apply set man) (apply set opt)))

 

#; {String [Listof String] -> Boolean}

(define (matched? p all) (for/or ([a all]) (regexp-match p a)))

 

#; {Symbol -> String}

(define (~n s) (cond [(regexp-match "(.*)/" (~a s)) => cadr] [else (~a s)]))

The following is a sample spec for the current milestone. It is located in 3/Other/3.rktl for my solution.

state of repo for milestone 3

[(** B/)

 (** C/)

 (** D/)

 (** E/)

 (Fish/

   README.*

   [** Makefile]

   xtest

   (Common/

     state.*

     .*)

   [** Other/]

   (Planning/

     system.pdf

     milestones.pdf

     game-state.md

     games.md))

 (3/

   [** Makefile]

   xboard

   (Tests/

     1-in.json 1-out.json

     2-in.json 2-out.json

     3-in.json 3-out.json)

   [** Other/])]

Neither the script nor the spec are the ones we use for checking whether you can follow basic instructions.

image

Wednesday, October 14th, 2020 3:55:35pm

Below is a simple ASCII diagram that explains the organization of your repository:

    Your_Repository/

     |  Fish/

     |   | README...

     |   | Makefile **

     |   | xtest

     |   | Common/

     |   |   | board.PP

     |   |   | state.PP

     |   |   otherwise the organization of this directory is left to you

     ....... you will have to add more directories and files here ......

     |   | Other/   **

     |   | Planning/

     |   |   | system.pdf

     |   |   | milestones.pdf

     |   |   | game-state.md

     |   |   | games.md

     |  3/

     |   | Makefile **

     |   | xboard

     |   | Tests/

     |   | Other/   **

     ...... for future assignments you will create additional integration tests

     |  10/

     |   | Makefile **

     |   | x...tbd...

     |   | Tests/

     |   | Other/   **

The directories and files marked with ** are optional.

If the above diagram conflicts with the prose in the tabs on the left, the prose overrides the diagram.

image

Friday, October 16th, 2020 9:39:55am

Please take a look at a sample game state specification. Yours may differe and get full credit, but this one provodes full guidance and later explanation of the design rationale.

[My implementation deviates from this plan.]

image

Wednesday, October 14th, 2020 11:20:04am

Test Me is in effect as of milestone 3.

image

Tuesday, October 13th, 2020 7:56:04pm

3 — The Game State has been updated to include a restriction on the size of test cases you may submit. You may consider this a validity constraint.

image

Sunday, October 11th, 2020 1:14:09pm

Important

The testing task for 3 — The Game State exposed a gap in the "common ontology" between our software components, specifically whether straight lines stop at holes in the board. The answer is yes.

I have clarified the testing task and Fish accordingly.

[ Since we are dealing with the board only, there really is no need to figure out where penguins are, which is only a part of the game state. ]

image

Saturday, October 10th, 2020 11:36:29am

The following piece of advice collects in one place a Piazza post from Friday 09 October.

Your task was to model 3 distinct pieces of "information". In terms of Fundamentals I, II, and III, this implies at least three distinct structs/classes together with appropriate functionality:
  • Once constructed, nobody changes game tiles. A well-chosen data representation makes them immutable. Those of you who have code before and/or have encountered mentally old coders during co-op have questioned and perhaps will continue to question the attribute "immutable" that shows up so often in F I, II, III and here. Ordinarily I give an ad hoc lecture during this week on the person who designed the JAVA API and his book Effective Java by Josh Bloch. If anyone understands JAVA and the intention on how to program with it, it is Josh. His book (the first edition is the most concise and clearly written one) states in indisputable terms: Favor Immutability. While F II was designed independently and before Josh wrote his book, I consider it affirmation of a basic idea that has been overlooked for way too long. (In essence Josh’s book is an apology for making so many parts of the JAVA API mutable.) At this point you may wish to reflect on your attitudes and thinking about F I, II, and III.

  • Once constructed, nobody changes game avatars (penguins). A well-chosen data representation makes them immutable.

  • A board consists of a bunch of tiles arranged in a "natural" way (see images). It changes over time. Weigh the advantages of functional updates vs imperative updates.

Two additional ideas must govern your design choices this time:
  • For this particular game board, planning steps from a tile to neighboring tiles is a key operation. This implies the use of an "direct indexed" data structure choice or a representation that hard-bakes connectivity in a graph-like fashion. The latter choice makes alternative paths across the board (zigzags instead of straight lines) a bit more difficult but may make straight-line calculations easier.

  • Functionality such as "find a straight line to all positions to which the avatar can move" needs either a data representation for "position" and possibly "straight line" and/or a purpose statement that implicitly introduces and interprets them.

No matter what you do, you need an explanation of representation and interpretation meaning answers to the questions "how do I represent an actual game board (information) in my chosen data representation" and "how do I construct a board from an instance of my chosen data representation."

If you can answer both of these questions, you have a data representation.

If you don’t do this you have "stuff", not accessible pieces of software.

image

Saturday, October 10th, 2020 8:01:17am

Remember to complete your self evaluation by tonight.

image

Friday, October 9th, 2020 5:29:45pm

image

Tuesday, October 6th, 2020 9:04:18am

I have made some adjustments to 2 — The Game Pieces. See the strike-out and purple words. In particular, the “rendering” task could have been misunderstood as “render just one tile” [of the board] but it really meant render all all tiles [of the board].

image

Friday, October 2nd, 2020 5:27:18pm

Sometime in the next hour or so, a file named self-1.md will appear in your code repository in directory 1/. This is your first self-evaluation probe of the project. See Code Grades for details.

image

Thursday, October 1st, 2020 9:18:28am

Industrial people are slowly recognizing the downside of ticket-driven software development. Considering reading the Jon Evans’s blog post to get a sense of what these people are getting at. As I said in class on Tuesday, tools are no panecea, but people tend to think of them as such. The effectiveness of tools depends on the users, and in the case of JIRA the project management people: some know how to use it properly and many act like sheep.

Academia cannot and must not teach tools. Our goal has to be to teach thinking instead and create reflective people and software developers.

image

Wednesday, September 30th, 2020 1:39:49pm

We have added a Online Reviews subsection to In-Class Reviews. Please take a look before Friday.

image

Thursday, September 24th, 2020 9:09:35pm

Send your lab books to the section TA now.

Use the following subject line:

    lab book for sw dev

image

Saturday, September 19th, 2020 4:52:03pm

See Lectures for the videos for next week.

Also re-visit D — GUI if you had difficulties interacting with your GUI program on the Linux servers.

image

Friday, September 18th, 2020 4:07:23pm

On the lighter side After describing the circular sociology of “there can be only one JSON thing in a json file” or the imminent death of Fortran (see Psychology of Programming), JH in the 09:50am section sent me to

https://xkcd.com/978/

Enjoy. And don’t forget to read the ALT text.

image

Wednesday, September 16th, 2020 3:44:07pm

As of next Tuesday, we will test-run code walks. We will start with a a set of panelists code walking my solution to one of our assignments, then some of us will play panelists for code walking a pair from the class. Following those two, we will conduct a couple of more trial runs with both presenters and panelists drawn from the class.

If you would like to volunteer, it comes with an upside and a downside:
  • the upside is that you get to practice

  • the downside is that you get feedback in public

Keep in mind that the instructor gets to know you and that this is usually a good thing.

image

Wednesday, September 16th, 2020 8:21:29am

As you know, the grades for your first homework have been released. Here are two critical comments:
  • our test harness does not run make unless there is a Makefile

  • an executable shell script must start with a #! because it won't run as a subprocess otherwise.

image

Tuesday, September 15th, 2020 4:55:07pm

See Lectures for the next batch of videos.

The transformation of textual information into internal data is known as parsing, a technical problem that spawned an entire research area. Parsing is so complex, it should never be used in an introductory course but to this day, many such courses assign programs that read text, analyze it, and react to it—without proper support. Proper coverage is offered in Compilers and Theory, and these two course will help you design parsing programs properly.

At first glance, JSON is a simple notation for writing down information in terms of Booleans, Strings, Numbers, arrays of JSON expressions, and objects of JSON expressions. But, as it turns out, turning JSON information into internal data is a minefield; indeed, no two JSON parsers seem to accept the same JSON inputs.

You should keep this fact in mind for your upcoming co-op and future employment.

Finally, if you are interested in recent studies of negative feedback to workers, you may wish to read The Rare Worker Who Thrives on Negative Feedback [PDF].

image

Sunday, September 13th, 2020 3:34:05pm

Lectures lists the videos for lectures past and the next one (or two) coming up. Please take a look at the videos for 09/15.

image

Saturday, September 12th, 2020 12:20:43pm

Contrary to rumors, B — Command Line is a pair-programming assignment. Indeed, as you can imagine from the brief explanation in class, the actual effort is negligible. Any single person can probably finish the code in less than 15 minutes.

The actual purpose is two-fold: (1) to get to know your partner with a tiny on-line assignment, and (2) to learn to live up very rudimentary specifications.

Note You were provided with email contacts, and some people may not read their emails on a daily basis, especially not over weekends. So, give your partner until Monday noon to get in touch with you, that is, reply to your first message. This deadline leaves you with 12 hours to finish something that ought to take 30 mins max in total.

If your partner does not reply to your emails by Monday noon, let your instructor know.

image

Wednesday, August 5th, 2020 9:46:03am

Welcome to the Fall 2020 issue of Software Development. As always, we aim to deliver a course that teaches you a lot, not in terms of industrial tools and techniques but for your life as a reflective software developer.

Please familiarize yourself with this web site, its organization and its content. The site will continue to grow:
  • this front page serves as a universal announcement scroll,

  • the Assignments, Actual page serves as your “task list,” and

  • a few other pages come online as needed.

The College’s web services company caches pages on a too-permanent basis, injecting the occasional miscommunication. The backup site for the course can be found at the personal web page of the lead instructor.

image