Software Construction

A module is a group of functions that belong together and share a few rules. In this course a module is short enough to read on one screen. In a real project it might be a file, a class, or a folder with thirty files in it.

The size changes and the question does not: how much of this do I have to understand before I can change one line without breaking something I have not looked at.

A list holds many values one after another, in one box. Square brackets make one: let prices = [14, 3, 9]. Square brackets also take one back out by its position, and positions are counted from 0, so prices[0] is 14 and prices[1] is 3. prices.length is how many items there are, 3 here, which means the last position is always one less than the length. prices.push(7) adds 7 to the end and leaves the list one longer.

The order handed to each function in the lab below is a list, with one item in it per line of the order. Lists are what Steps 6 and 7 spend all their time on, because two names can end up holding the same list without either of them saying so.

An object keeps several named values together as one thing. Curly brackets make one, with a name, a colon and a value for each part: { price: 14, qty: 2 }. The names are called keys and what sits after each colon is that key's value.

The dot reaches in and names one of them. If line holds that object, then line.price is 14 and line.qty is 2, and line.qty = 3 puts a new value in that one part. So every line of the order is an object, and line.price * line.qty is what that line costs.

It runs the part in curly brackets once for every item in order, and each time round line holds the next item. Four lines in the order means the body runs four times, which is how one short loop totals up an order of any length without anybody knowing in advance how long it is.

There is a second way to write a loop, and you will need it later: for (let i = 0; i < order.length; i = i + 1). Start i at 0, keep going while it is under the length, add one to it each time round. i is short for index, meaning the position and the item at that position is order[i]. Reach for this one when you need the position itself, as you will in Step 9, where a check has to compare each item with the one before it.

In a comment above the function, in a documentation string the language pulls out into a manual, in the types of the parameters, or in the tests. Usually in several of those at once, which is fine as long as they agree.

The format matters far less than one property: somebody who wants to call the function has to be able to find out what it needs and what it promises without reading the body. A promise that only exists inside the implementation is a description of today's code, and descriptions go out of date silently.

Guessing the middle, over and over. lo and hi mark the stretch of the list the target could still be hiding in, and they start as the whole thing. mid is the position halfway between them; Math.floor just rounds down, because there is no position 2.5. If the item sitting at mid is the target, done. If it is too small, then everything from lo up to mid is too small as well, so lo jumps past the lot in one move. If it is too big, hi comes back the same way. Either way half of what was left disappears each time round, so a list of a thousand items is finished in ten guesses instead of a thousand.

while (something) { ... } is a loop with no counter in it: do the body again for as long as the condition is still true. Here it says "keep halving while there is any stretch left to search". And every bit of that depends on the list being in order: jumping past everything below mid is only safe if everything below mid really is smaller. That is precisely what the precondition is buying, and Step 9 shows you what happens to this same search when the order quietly stops holding.

=== asks whether two things are exactly the same, and the answer is true or false. So sorted[mid] === target asks "is the item at position mid the very thing we are looking for". !== is the opposite question, and < and > ask smaller and larger in the way they do in maths.

Keep all of those apart from = on its own, which asks nothing at all: lo = mid + 1 is an instruction to put a new value in the box called lo. Asking and putting are two different acts that look nearly identical on the page. Step 10 is about how much harder "exactly the same" becomes once the two things being compared are lists.

A precondition is something the function is given, rather than something it checks. "Requires: the list is sorted" means: if you hand me an unsorted list, I owe you nothing, and anything at all may happen, including a plausible wrong answer that you do not notice for a year.

That sounds harsh, and it buys something real. A function that has to cope with every possible input is bigger, slower and harder to reason about than one that is allowed to assume. The cost is that somebody has to make the precondition true. That somebody has to be told.

say(something) prints one line into the output panel under the editor, and that is the whole of what it does. It is not part of JavaScript. It is a word this site adds to the interpreter, the program that runs your code on this page, because it is shorter to read than the real one. In a browser you would write console.log(something) instead and nothing else would change.

Printing is not returning, and the difference matters from here on. say(x) puts x somewhere you can read it and the program cannot use it afterwards, while return x hands x back to whoever called the function, to store or add or test. A function that says its answer instead of returning it looks as though it works and cannot be built on, and none of the checks in Part 2 can see it. The other page word in the next two labs is check, which records one comparison and carries on; Step 3 is where it is explained.

Because tests written while looking at the body tend to test the body. You see a loop and write a case that walks the loop; you see three branches and write three cases. What that misses is the behaviour the code was supposed to have and does not, because there is nothing on screen to remind you of it.

Testing from the spec alone is called black box testing, and it is the kind that can catch a missing rule. The other kind, where you read the code and make sure every line runs at least once, is called glass box testing. It is a useful second pass rather than a replacement.

check(what you got, what it should be,"a name") records one assertion and moves on. If the two disagree, the case is marked failed and shown to you. That is the whole idea, and every testing tool in every language is a dressed-up version of it.

The spellings differ. You will meet assertEquals(want, got) in Java, assert got == want in Python, and expect(got).toBe(want) in JavaScript. Different words, same three parts: a value you computed, a value you expected, and a name so you know which one broke.

Read the spec and mark every phrase that changes the answer. In the delivery rules those are "up to 1 kg","up to 5 km","over 20 kg" and "over 100 km". Each phrase cuts one axis into bands, and the regions are every combination of bands.

Two axes with three bands each gives nine regions. It grows quickly, which is the point: nine is already more cases than most people write by instinct, and every one of the nine is somewhere the function might behave differently from all the others.

Every possible call you could make to the function, laid out as a shape. A function of one number has a line of inputs. A function of two numbers has a flat sheet, one axis each, and a particular call is a dot somewhere on it. A function taking three things has a solid, and after that the picture gives up while the idea keeps working.

The map in the lab below is that sheet: weight up the side, distance along the bottom, one dot per test case. The lines drawn across it are the places where the shop's rules change what happens.

Deliberately breaking a function and checking that your suite notices has a name: mutation testing. Tools do it automatically, changing a > to a >= or deleting a line, then reporting which mutations nobody caught. Every uncaught mutation is a behaviour with no test behind it.

You can do the cheap version by hand any time. Break the code on purpose, run the suite, and if it stays green you have just learned something about your tests rather than about your code.

Putting a list in order is something the language will do for you, and by default it does it as though everything in the list were text. Text is compared character by character, the way a dictionary orders words, so "10" comes before "2" for exactly the reason "apple" comes before "b": the first character settles it. On single digits that gives the same answer as ordering by size, every time, which is precisely why the bug can hide. The fix is to hand the sort a small function of your own that says which of two numbers should go first.

The testing lesson is the one worth keeping, though. Three cases, all passing, all drawn without thinking from the same narrow shape, and a bug sitting just outside it. Ask it of any suite you write: what do all my cases have in common that they did not have to have? Single digits. All positive. All the same length. Never empty. Every one of those is a corner you have not looked in.

Production is the copy of the software that real people are actually using, as against the copy on your own machine or the one the tests run against."It works on my machine and breaks in production" is the oldest complaint in the trade. The gap it describes is the reason a bug can be real and invisible to you at the same time. A codebase is just all of the code for one piece of software, taken together.

Three more you will meet on this page. A code review is somebody else reading your change before it is allowed in. A README is the file at the top of a codebase saying what the thing is and how to run it. A screenshot test takes a picture of the screen and complains when the next picture differs. None of those is enforced by the machine: the first two are people agreeing, which is exactly why Step 8 argues that hiding something in the code beats agreeing not to touch it.

a.slice() builds a brand new list holding the same items as a and hands it back. Two boxes now instead of one, so b.push(99) lands in b's box and a never hears about it. The name is odd because slice can also be given a start and an end, to copy part of a list. Called with nothing in the brackets it copies the lot, and that is the everyday way of saying "give me my own list".

You could write it yourself: start an empty list, loop over the original, push each item onto the new one. That is exactly what slice is doing for you. Worth knowing, because the copy is never free: copying a million-item list really does do a million pieces of work. That is the whole reason the language hands out arrows by default and makes you ask for the copy when you want one.

Because a list can be enormous. Copying one every time it is passed to a function would make passing a million-item list a million-step operation, and most of the time you did not want a copy. So the language passes the reference, which is one small number, and copying becomes something you ask for.

The cost of that speed is that sharing is the default and it is invisible in the code. Nothing at the call site says whether the function you are handing your list to intends to change it. Only the spec can tell you, which is why specs say things like "modifies: nothing".

A shallow copy duplicates one level: a new outer list holding the same references. A deep copy walks the whole structure and duplicates everything it finds. Deep is what people usually mean when they say "copy", and it is also the one that can be slow, can loop forever on a structure that points back at itself, and can duplicate things that were meant to be shared.

Most languages give you shallow by default and make you write the deep one, because shallow is cheap and predictable. Knowing which one you have is enough to avoid nearly all of the trouble.

A function is a value, the same way 7 and "hat" are values, so it can be kept under a key like anything else. { push: function (x) { items.push(x) } } is an object with one key, called push, whose value happens to be a function. Reading it back with s.push hands you the function itself; writing s.push(4) hands you the function and then calls it with 4.

The other half is that makeStack runs its body afresh every time it is called. Each call builds its own items list and its own three functions, which is why two stacks made from the same makeStack know nothing about each other. If you moved let items = [] up above the word function, there would be one list in the whole program and every stack would share it. The lab checks for exactly that.

list.push(x) puts x on the end, which you have met. list.pop() is its exact opposite: it takes the last item off and hands it back, so let last = list.pop() both shortens the list by one and tells you what was removed. Called on an empty list it removes nothing and hands back undefined.

Those two operations are all a stack needs, and that is not a coincidence. A list with things pushed on and popped off at the same end already behaves the way a stack promises to behave. Which is the point of the step: a stack is not the list, it is the promise and a list is one convenient way of keeping it.

Some languages have a keyword: private in Java, an underscore convention in Python, module-level visibility in Go. JavaScript's oldest and strongest answer is the closure. Variables declared inside the factory function are reachable by the operations defined inside it and by nothing else, because there is no name for them outside.

It is not a rule that somebody chooses to respect. There is no expression a client can write that reaches those variables, which is a different and much stronger kind of hidden.

The representation is the actual stuff a data type keeps inside to do its job: the list behind the stack, the two whole numbers behind a fraction, the table behind a set. Step 8 called it the inside. This is the proper name for it.

An invariant is something that stays true the whole time, no matter which operations get called or in what order. Put together, a representation invariant is a sentence about the inside that every operation promises to leave true: the list is sorted, the count matches the length, the bottom of the fraction is never zero.

Often yes. A check that costs a few comparisons next to work that costs far more is not worth removing, and in a running system a loud failure at the right place beats a quiet wrong answer everywhere else. Some languages let you switch assertions off at build time so you can keep them in the source and pay nothing in production.

The one to think about is a check that walks the whole structure inside an operation that is supposed to be quick. Checking that a thousand-item list is sorted, on every insert, turns cheap inserts into expensive ones. The usual answer is to keep it on in testing and in development, and to sample it rather than delete it in production.

typeof x hands you back a word describing what kind of value x is. typeof 7 is "number", typeof"7" is "string" (string is the usual word for text), and typeof true is "boolean". So typeof xs[i] !=="number" is how you ask "is this item something other than a number".

Why the invariant bothers to say it: a list will hold anything you put in it, and the text "2" sits quietly between 1 and 3 when you compare it with <. A check that only compares neighbours waves it straight through. Then some later operation does arithmetic on it and gets "21" where it wanted 3. An invariant is the place to say what the inside is allowed to contain, not only what order it has to be in.

Two machines stand side by side. You can put coins in and press buttons, and that is all you can do, because the panels are welded shut. If every sequence of coins and buttons gets the same thing out of both, then as far as anybody using them is concerned they are the same machine. One might hold its cans in a spiral and the other in a stack, and no customer can ever find out.

A data type is the same arrangement. The operations are the buttons. Two values are observationally equal when no sequence of operations tells them apart. Take a set, which Step 11 builds twice. It is a type that holds a collection of different things. You can put something in, ask whether something is in it, and ask how many different things it holds. Those three are the whole interface. Notice what is not on the list: nothing asks which order they went in. Which is why a set holding 1 and 2 equals a set holding 2 and 1: there is no button you can press that tells them apart.

Numbers are stored in binary, as a sum of halves, quarters, eighths and so on. A tenth is not a sum of those, in the same way that a third is not a finite decimal: 0.3333 never quite gets there. So 0.1 is stored as the nearest number that binary can hold, 0.2 likewise, and the sum of those two nearest numbers is not the nearest number to 0.3.

No better computer fixes this. The way out is to stop comparing decimals for exact equality: ask whether the difference is smaller than some tolerance, or hold money as a whole number of pennies and never divide it.

It is, and it is the only sensible way to compare two things when you do not know how deep they go. Asking whether [1, [2, [3]]] equals [1, [2, [3]]] means comparing the outer lists position by position, which means asking whether [2, [3]] equals [2, [3]], which means asking whether [3] equals [3]. It is the same question three times over, on smaller and smaller pieces. So write the question once, and let it ask itself.

What stops it going on forever is that each call is handed something strictly smaller than what it was given. Eventually you reach a piece with no parts inside it: a number, some text, true, null. There the answer is just ===, and the function answers without asking again. That case, the one that does not call itself, is the one to write first. A recursive function with no such case runs until the interpreter stops it. This page's interpreter will stop it and say so.

Three helpers you will want. typeof x hands back a word saying what kind of thing x is: "number", "string", "boolean", "object". Lists and objects both answer "object", which is why Array.isArray(x) exists to tell those two apart. And Object.keys(obj) hands back a list of the object's key names, so Object.keys({ x: 1, y: 2 }) is ["x","y"], which you can loop over with for ... of and count with .length.

Java writes interface Set and the compiler refuses to build anything that claims to be a Set without every operation. Go infers it from the operations a type has. Python leans on the operations existing at the moment you call them. Here it is an object holding three functions, which is the same idea with no ceremony.

What none of those languages check is the promises. Nothing in a type system says "adding the same thing twice changes nothing". That part is the spec, and the only thing that enforces it is the test suite you run against every implementation.

The list version starts at the front and compares its way along, so asking whether something is in a set of two hundred can cost two hundred comparisons. The table version does something else entirely: it turns the item into a place. It runs the item through a fixed piece of arithmetic that always gives the same answer for the same item, and puts it in the slot that arithmetic names. Later, to find out whether the item is there, it runs the same arithmetic, goes to that one slot and looks. One look, and it does not get slower as the set fills up.

You have used a table already without calling it one. An object with keys is exactly this. counts["apple"] does not walk the object's keys one at a time looking for "apple"; it works out where "apple" is kept and goes straight there. The table-backed set in this step is an object being used that way. That is the whole of why its cost per operation barely moves, while the list version's cost grows with every item you add.

Refactoring means changing the shape of code without changing what it does. Splitting a long function into named pieces, giving a number a name, moving a decision to one place. The behaviour before and after is identical, which is what makes it safe to do in small steps.

Here you are doing two jobs at once, because the module also has a bug in it, and separating those is the professional habit: refactor with the tests green, then fix the bug as its own change, so that when something breaks you know which of the two did it.

Declare it once, above all of them: let freeAt = 30. Every function written underneath can read freeAt, because a function can see the names that surround it as well as its own parameters. And one of them can change it, like this: function setFreeDeliveryAt(mark) { freeAt = mark }. After that, every function that reads freeAt sees the new value, without being told and without being edited. That is what Step 1's tidy module was doing, and it is what "the rule that changes most often can be changed in one move" looks like written down.

It is also the thing to be careful with, and you already know why. A value that anybody can reach and anybody can change is the trouble from Step 6 one floor up. It is tolerable here because there is exactly one of them, it is changed through one named function rather than from wherever and the module owns it. A module with nine of them, changed from everywhere, is the mess somebody calls you in to fix.

It is useful when it states an independent requirement and would catch a plausible wrong implementation. Run it against the old code, the proposed change and a deliberately broken variant. A test that passes every version supplies no evidence.

Keep hidden or independently written evaluation cases for work where the generator also writes the implementation. Otherwise the same misunderstanding can appear in both code and test, producing a green but incorrect pair.

It has no errors covered by the type rules and declarations that passed. An unsafe cast, incorrect library declaration or unvalidated runtime value can still make a declaration disagree with reality.

Types also do not prove business rules such as “the end date follows the start date.” Enforce those with constructors, runtime checks and tests.

A union says a value is one of several named shapes. Checking a field such as state tells the checker which other fields are available.

A generic describes one relationship for many types. Result<T, E> holds either a value of type T or an error of type E without losing which one is present.

Files, locks, transactions and temporary resources need release on success, failure and cancellation. A finally block or resource scope runs cleanup whichever path leaves the operation.

Cleanup can fail too. Record that without hiding the original fault, and make repeated cleanup safe where possible.

A timeout is a policy that cancels work after a deadline. Cancellation is the signal sent through the operation. Code must stop new work, release resources and decide what partial effects remain.

A write may have committed before cancellation arrived, so the outcome can still be uncertain.

If A imports B, B imports C and C imports A, none can be understood or replaced independently. Draw the arrows and move a shared rule behind an interface owned by the more stable layer.

Cycles at package or service level affect builds, ownership and deployment more than local recursion does.

The core describes operations it needs, such as QuestStore.save. A database, in-memory test store or remote API can sit behind that port.

Architecture tests can inspect imports and fail when a framework detail points into the wrong layer.

A property can compare two routes, check an invariant or use a slow reference. If the test copies the production algorithm, both may share one mistake. Choose an independent oracle.

Generators should deliberately include empty, maximum, duplicate, Unicode and deeply nested cases.

The changed behavior may be uncovered, the assertion weak, or the code equivalent or unreachable. Inspect the mutant before adding a test. A mutation score is evidence, not a reason to add meaningless assertions.

Use mutation selectively on important logic because running many altered versions costs time.

A lock protects code that uses the same lock. Several locks can deadlock when tasks acquire them in different orders. Keep critical sections small and use a fixed order.

Immutability and message passing reduce shared writable state, but ownership and message order still need rules.

Pause each task at named yield points, choose a known interleaving and assert the final state. Save the schedule that exposes the failure.

Continue with Concurrent Data Structures for atomics, memory order and safe reclamation.

An instant coordinated change is difficult to retry or roll back. Mobile clients may remain old for months. Prefer tolerant readers, additive fields and explicit deprecation windows.

When a semantic break is necessary, version the contract and give callers a tested migration path.

Process bounded batches, record progress and make repeating a batch safe. Verify counts and invariants before and after. Avoid one transaction across the entire dataset.

Rolling code back does not automatically reverse data already changed by the new version.

Configuration selects behavior for an environment. Secrets are credentials and keys. Keep secrets out of source, logs, generated artifacts and browser code. Supply them at runtime through a controlled secret store.

Grant each workload only the secret and permission it needs. Rotation must replace both stored credentials and running consumers without an unsafe gap.

Pinning makes a build repeatable, but old code can contain known flaws. Update deliberately: inspect the change, run compatibility and security tests, stage the release and keep a recovery route.

A package with no maintenance plan becomes risk even if it has no current advisory.

Check the requirement, diff, tests, data and security effects, compatibility, operations and deletion plan. Style automation should handle mechanical details so people can examine behavior.

Large mixed changes hide risk. Separate formatting, generated files, dependency updates and behavior when that makes each part independently verifiable.

Name an owner, intended lifetime, default and removal condition. Test both states while both exist. After rollout is complete, remove the old branch and flag rather than adding permanent combinations.

Flags help separate deployment from release, but they also create runtime states that need monitoring.

Build a timeline from evidence, describe impact and contributing technical or organizational conditions, then assign specific prevention, detection and recovery improvements.

Stopping at the person who made the last edit hides the system conditions that allowed one action to cause broad harm. Track actions to completion and verify that they change the failure mode.

It can restore old code. It may not reverse database writes, messages, emails or external effects already produced. Test rollback and forward-repair plans against stateful changes.

Gradual rollout, health checks and automatic stopping reduce the amount affected before recovery begins.

No. Similar code can change for different reasons. Wait until the shared rule is clear, then give that rule one name. A premature abstraction couples cases that only happen to look alike today.

Duplication of a safety rule or protocol may deserve earlier attention than repeated presentation markup.

Performance Engineering measures time and resource costs. Reliable Systems develops failure boundaries, retries and operations. Fault Tolerance tests recovery.

Build a Language shows how types, interfaces and invariants support parsers, interpreters and compilers.