Before the lab

Before every lab in this course, you will be given tasks to complete. These will generally be easy tasks like watching videos, but you need to complete them in order to keep up with the class.

Command Line Familiarity Check

1. In an FCS linux lab (remote or locally) log in, and open a terminal.

2. Make a directory *

3. Create a file in that directory using one of the available text editors

4. Now clean up, removing the file and the directory.

If any of this was new to you, then please take the time to go through parts 1 to 5 of the Learning the Shell Tutorial.

Read the course syllabus.

The Course Syllabus is available on line. Please read it, and bring any questions you have about it to the first lab.

Background Reading

For every lab there will be some related reading. I'll point these out as we go through the lab, but I'll also collect them at the start of the lab in case you want to get a head start (or refer back to them later).

• The Frog manual
• Git Basics from Pro Git
• Basic Shell Background

About the course

1. What's similar to other CS courses you've taken?

2. What's different?

3. Key point, how are labs evaluated?

Software Setup

1. Open a terminal.

2. Install frog and the other tools we need via the following command (throughout the course, $ at the beginning of a line will indicate a shell prompt, you don't need to type it.):

     $ raco pkg install --auto unb-cs2613
   

3. Install the python library pygments, used by frog for syntax highlighting

    $ python -m ensurepip --upgrade
    $ python -m pip install pygments
   

There are an unfortunate number of warnings here, but we can ignore them for now.

Getting Started with Frog

We'll be using frog frog to keep a journal of what we learn in this course.

1. Open a terminal.

2. Make a directory called cs2613 that will keep all of your work (note that case and spaces matter in Linux and this is not the same as CS2613 or CS 2613. For the rest of this course we will assume it is directly under your home directory. The shortcut ~/cs2613 will refer to this directory in the lab texts and in the shell.

3. Make a directory journal inside ~/cs2613. Inside ~/cs2613/journal, run

    $ raco frog --init
   

4. Try viewing the newly created blog with

    $ raco frog -bp
   

5. Start a new blog page for today's lab, and delete the fake entry created by the frog setup command. Note that you may have to refresh the browser after running raco frog -bp.

Setting up a git repo

1. Change to ~/cs2613. This directory should have one subdirectory called journal, which has the results of your experiments above with frog.

2. Create the git repository

    $ git init -b main
   

   Git will reply with something like

    Initialized empty Git repository in /home1/ugrads/$username/cs2613/.git/
   

   You’ve now initialized the working directory — you may notice a new directory created, named ".git". You should mentally replace "$username" with whatever the login name is that you use to log into the FCS linux machines.

3. Read the git-quickref page, and follow the initial configuration steps there.

   • note that the "--wait" option for gedit is important here.

4. Next, tell Git to take a snapshot of the contents of all files under the journal, with git add:

   $ git add journal
   

This snapshot is now stored in a temporary staging area which Git calls the "index". You can permanently store the contents of the index in the repository with git commit:

   $ git commit

This will open and editor and prompt you for a commit message. Enter one and exit the editor. You’ve now stored the first version of your project in Git. See §5.2 of Pro Git for some hints about writing good commit messages. As mentioned in the class git policy, you will be marked on your commit messages, so you may as well get started with good habits.

Pushing to a central repo

Since we are using the FCS git repositories there is an existing repository for all students who registered early enough. If it turns out there is no repository for you, you may need to do the last step later.

• First add the remote. This something like a nickname for the URL where the repo will be stored.

    $ git remote add origin https://$username@vcs.cs.unb.ca/git/cs2613-$username
  

  origin is the default name for a remote, but we could have used a different name here. Replace $username with your FCS Linux account name.

• Now upload your local copy of the repo.

    $ git push --all origin
  

  you should see something like

            Counting objects: 388, done.
            Delta compression using up to 8 threads.
            Compressing objects: 100% (350/350), done.
            Writing objects: 100% (388/388), 71.63 KiB | 0 bytes/s, done.
            Total 388 (delta 223), reused 59 (delta 33)
            To https://$username@vcs.cs.unb.ca/git/cs2613-$username
               e7e5311..f1ae959  main -> main
  

• If you have extra time, start L02

Before next lab

Before the lab

Background

• This lab completes our discussion git, and starts our first programming language, namely Racket.

• For learning racket, we will mainly follow Functional Introduction to computer science

• You may also find the BSL reference helpful.

Git Tutorial Continued

Making Changes in git

Having at look at our test post from Lab 1, we can observe the post template adds a bunch of stuff related to social media. Let's suppose that for our cs2613 journal we want a more minimal look.

Start by finding the right files to edit with

$ git grep disqus

git grep is a very useful (and fast!) tool to find occurrences of strings in your git repository. Notice in the output there are some files created by frog; we will clean those up later. Find the template file (under _src) and edit it to remove the undesired social media links. Check the results with

$ raco frog -bp

You might notice one more link to twitter in a different template file. Feel free to remove that one as well.

Use git add to stage your changes:

$ git add file1 file2 file3

(where file1, file2 and file3 are actual files you modified). You are now ready to commit. You can see what is about to be committed using git diff with the --cached option:

$ git diff --cached

(Without --cached, git diff will show you any changes that you’ve made but not yet added to the index.) You can also get a brief summary of the situation with git status:

$ git status
# On branch master
# Changes to be committed:
#   (use "git reset HEAD <file>..." to unstage)
#
#       modified:   file1
#       modified:   file2
#       modified:   file3
#

If you need to make any further adjustments, do so now, and then add any newly modified content to the index. Finally, commit your changes with:

$ git commit

This will again prompt you for a message describing the change, and then record a new version of the project.

Alternatively, instead of running git add beforehand, you can use

$ git commit -a

which will automatically notice any modified (but not new) files, add them to the index, and commit, all in one step. Keep in mind that you will be marked on the logical structure of your git commits, so you are better off using git add to explicitely choose what changes to commit.

Cleaning up generated files

A common phenomenon in software development is the existence of generated files. These files are created by some tool, typically based on some source files. In general it is a bad idea to track generated files in version control because they introduce spurious changes into history. We'll look at this more later, but for now let's try to clean up. We can find out what files are generated .e.g. by consulting the frog docs. Let's first try a shortcut. Run

$ cd ~/cs2613/journal
$ raco frog --clean

To find out what changed, run

$ git diff --stat

All going well, you will see a bunch of deletions. We can tell git to make those deletions permanent in several ways. It turns out that there is a handy option to git add that tells git to stage all of the changes in the working tree. Try to figure out which option it is.

• to see the effect of a git add command, run git diff --cached --stat
• to undo the effect of a git add command, run git reset.

When you are satisfied with the changes, run git commit.

It will turn out that this is not all of the generated files; we can use git rm to clean up further as we find more.

Make sure you run

$ raco frog -bp

To make sure the the blog still works after your deletions.

Viewing project history

1. At any point you can view the history of your changes using

    $ git log
   

   Use this command to verify that all the changes you expected to be pushed to the server really were.

   If you also want to see complete diffs at each step, use

    $ git log -p
   

   Often the overview of the changes is useful to get a feel for each step

    $ git log --stat --summary
   

2. In most projects, you have to share commit messages to (at least) the same people who view your source code. Share your "best commit" message with one or more of your neighbours.

3. Find something positive to say about the other commit messages you are reading.

4. Find a constructive improvement with one of the other messages. Don't be mean, people have varying levels of experience with this.

Getting started with racket

Hello Racket World

• Open a terminal

• Make a directory ~/cs2613/labs/L02 (if it does not already exist) and change there with cd

• Save the following code to ~/cs2613/labs/L02/hello.rkt

#lang htdp/bsl
"hello world"
(* 6 7)

Command Line

• run the program with

    $ racket hello.rkt
  

• What is the difference between the first and second line of output?

DrRacket: A Racket Specific IDE

• Start DrRacket from the activities menu

• Referring to the DrRacket documentation as needed, open and run the hello.rkt program from the previous part.

• What is the meaning of the first line of the file?

Racket Expressions.

• Form groups of 2 or 3.

• Work through Exercise 0: for each of the following lines of code, someone from the group should guess what is wrong before trying it in the Interactions window of DrRacket.

    (* (5) 3)
    (+ (* 2 4)
    (5 * 14)
    (* + 3 5 2)
    (/ 25 0)
  

• Work through Exercise 1. In general where the text asks you to predict the value of an expression, you can also enter into the definitions window something like

    (check-expect (* 6 9) 42)
  

  When you run (e.g. F5), then you will find out if your prediction is correct.

• Work through Exercise 2. You can test your answers by applying the following functions to appropriate arguments. Notice that the value of y does not matter.

#lang htdp/bsl
(define y 18)
(define (t1 x)
  (or (= x 0) (< 0 (/ y x))))
(define (t2 x)
  (or (< 0 (/ y x)) (= x 0)))
(define (t3 x)
  (and (= x 0) (< 0 (/ y x))))
(define (t4 x)
  (or (< 0 (/ y x)) (not (= x 0))))

Racket functions

• Do this part on your own.

• Do Exercise 4

  Here are some tests to help you check your function

(check-expect (middle-of-three 1 2 3) 2)
(check-expect (middle-of-three 2 1 3) 2)
(check-expect (middle-of-three 1 3 2) 2)

• Do these tests suffice? Why or why not?

Before Next Lab

Before the lab

Git Questions

Some questions from before:

• What is a remote?
• What is merging?
• What is a conflict?

Setup

• make a directory labs/L03 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

The DrRacket stepper

• copy arith.rkt, save it as ~/cs2613/labs/L03/arith.rkt and commit it.

• run your arith.rkt in DrRacket; observe that the test fails

• run your arith.rkt in the DrRacket Stepper. Notice that after about 7 steps, we have reduced the test case to multiplication by zero which looks wrong. That means that the problem is with the recursive (reduction) step.

• Fix the a > 0 case of my-* to match the following formula a * b = (a - 1) * b + b, while still using my-+

• DrRacket should report "The test passed!" when you have it working. Commit this version of your code. Remember that git commit message quality counts in this course, so work on making commit messages.

Semantics

As you read in FICS unit 3, we can understand evaluation ("running") of Racket programs as a sequence of "reductions" or "substitutions". These rules are similar to the reduction steps in the DrRacket stepper.

The stepper uses the following rules for and and or (notice that these rules enforce short circuit evaluation)

(and true exp2 ...) => (and exp2 ...)
(and false exp2 ...) => false
(or true exp2 ...) => true
(or false exp2 ...) => (or exp2 ...)
(and) => true
(or) => false

Following Exercise 7, write a new set of rules that requires at least two arguments for and and or. The rules are for human consumption; you can write them as comments in DrRacket. You can write "exp1 exp2 ..." to mean at least 2 expressions.

Discuss your answers with a your group, and try a couple evaluation small examples by hand using your rules.

Test Coverage

Unit testing is an important part of programming, and has inspired something called test driven development.

• This activity continues arith.rkt from the first half of the lab.

• Under

  Language -> Choose Language -> Show Details -> Dynamic Properties
  

  enable

  ⊙ Syntactic test suite coverage
  

• comment out the given test

• run your code in DrRacket again

• most likely you will have some code highlighted with orange text and black foreground. This means that code is not covered by your test suite. Uncomment the given test, and if needed add tests to cover each piece of uncovered code.

• When you have complete test coverage, commit your code.

  In this course, for all racket assignments you will lose marks if you don't have complete test coverage.

• Push your repo to coursegit.

If you have extra time

• Run the tests on the command line with raco test arith.rkt
• Read the first assignment A1
• Update your journal.

Before Next Lab

Before the lab

Questions from last time

• The programming languages we will study this term are all dynamically typed. This means that not only the value but also the type of variables can change at runtime. Why does this make testing even more important?

• What kind of software problems is testing not well suited to find?

• Why might mutable state (e.g. instance variables in Java) make writing unit tests harder?

Setup

• make a directory labs/L04 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Simulating Natural Numbers I

Write the times function from Exercise 11 in FICS. You can (and should) use the following code from the linked discussion

#lang htdp/bsl
(define-struct Z ())
(define-struct S (pred))
(define (pred nat)
  (cond
    [(Z? nat) (error "can't apply pred to Z")]
    [(S? nat) (S-pred nat)]))

(define (plus nat1 nat2)
  (cond
    [(Z? nat1) nat2]
    [(S? nat1) (make-S (plus (S-pred nat1) nat2))]))

Here is the template for structural recursion on (simulated) natural numbers. See the linked text (or the plus function just above) for how to add a second "carried-along" parameter.

(define (my-nat-fn nat)
  (cond
    [(Z? nat) ...]
    [(S? nat) ... (my-nat-fn (S-pred nat)) ...]))

Here are some tests to get you started. As always, try to have as complete test coverage as possible. Depending on how you choose the language in DrRacket, the line (define-struct S (pred)) may show partial coverage; you can ignore this for this lab.

;; 0 * 0 = 0
(check-expect (times (make-Z) (make-Z)) (make-Z))
;; 0 * 1 = 0
(check-expect (times (make-Z) (make-S (make-Z))) (make-Z))
;; 2 * 1 = 2
(check-expect (times (make-S (make-S (make-Z)))
                       (make-S (make-Z)))
              (make-S (make-S (make-Z))))

You may find it helpful to refer back to your solution from L03.

Simulating Natural Numbers II

Write the compare function from Exercise 11 in FICS. Your function compare should use the struct definitions Z and S, and pass the following tests

;; 0 = 0
(check-expect (compare (make-Z) (make-Z)) 'equal)
;; 0 < 1
(check-expect (compare (make-Z) (make-S (make-Z))) 'less)
;; 1 > 0
(check-expect (compare (make-S (make-Z)) (make-Z)) 'greater)
;; 2 > 1
(check-expect (compare (make-S (make-S (make-Z)))
                       (make-S (make-Z))) 'greater)

Structural recursion, on numbers

Use structural (note that structural here is only indirectly related to Racket structs) recursion on natural numbers (not the simulated ones from above, but regular Racket numbers like 1, 42, and 1337) to define a function (sum-factors n max-factor) that sums all factors of n (including 1) no larger than max-factor

Recall the template for structural recursion on natural numbers:

(define (my-nat-fn n)
  (cond
    [(zero? n) ...]
    [(positive? n) ... (my-nat-fn (sub1 n)) ...]))

Try to use only one recursive call to sum-factors like in the template. Keep in mind that the n in the template might be a different parameter of your function. You can use the builtin function remainder to test for divisibility.

The following tests should pass

;; 1+2+3 = 6
(check-expect (sum-factors 6 5) 6)
;; 1+2+4+7+14 = 28
(check-expect (sum-factors 28 27) 28)

Before Next Lab

Before the lab

Setup

• make a directory labs/L05 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Substitute in a list

Complete FICS Exercise 13.

Note the template for structural recursion.

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...]))

Here is a test case based on the linked test

(check-expect
 (substitute 3 "three" (list "four" 3 4 "three" 3))
 (list "four" "three" 4 "three" "three"))

Uniquifying lists

Complete FICS Exercise 15. Although probably not intended by the original question, use the built-in BSL function member? to simplify your solution. Otherwise use only the constructs specified in Exercise 14, and structural recursion. Here is one test case derived from the linked text.

(check-expect
 (unique-right
  (list 1 4 2 1 5 4))
 (list 2 1 5 4))

Add an element to all lists

Recall the template for structural recursion on lists

(define (my-list-fn lst)
  (cond
    [(empty? lst) ...]
    [(cons? lst) ... (first lst) ...
                 ... (my-list-fn (rest lst)) ...])

Use this template to write a function cons-all that adds a given element to the front of each given sublist. This is related to FICS Exercises 23-25 (but you only need to write cons-all, not do those exercises).

The following test case illustrates the use of cons-all. You will need to use the language #lang htdp/bsl+ or "Beginning Student with List Abbreviations" or replace the use of ' in the following.

(check-expect (cons-all 3 '((2 4) () (5)))
              '((3 2 4) (3) (3 5)))

Before next lab

Before the lab

Questions

• Questions about Assignment 1?
• Questions about Quiz 1?

Setup

• make a directory labs/L06 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Structural recursion on two parameters

• Form a group of 2 or 3.

• Work together to design the template in FICS Exercise 17

• Individually implement the function keep-first which follows this template.

• Compare your functions. Are there any interesting differences?

• Here is a test case

    (check-expect (keep-first (list 1 2 3 4) 3) (list 1 2 3))
  

• If that isn't enough for complete coverage for your solutions, add additional test cases.

Intersection of two ordered lists

The template for structural recursion on two lists is

(define (my-list-fn lst1 lst2)
  (cond
    [(empty? lst1) ... lst2 ...]
    [(empty? lst2) ... lst1 ...]
    [(cons? lst1)
        ... (first lst1) ... (first lst2) ...
        ... (my-list-fn (rest lst1) lst2) ...
        ... (my-list-fn lst1 (rest lst2)) ...
        ... (my-list-fn (rest lst1) (rest lst2)) ...]))

Use this template to complete FICS Exercise 20 You may find it helpful to refer to the function o-union defined in Section 5.4. Note that the fact that the lists are sorted is key an efficient solution here; you do not have to check that property.

Here are some test cases for the function intersection

(check-expect (intersection (list 1 2 3 4 5) (list 2 4 6 7))
              (list 2 4))

(check-expect (intersection (list 2 4 11) (list 1 2 3 4 5))
              (list 2 4))

Generating all subsets of fixed size

Start with the template from the first exercise and complete FICS Exercise 24. If your template needs updating, compare with cases in the two list template.

Use the built-in function append and the function cons-all you wrote in Lab 5.

Here are some test cases to illustrate the use of the function comb

(check-expect (comb '(a) 1) '((a)))
(check-expect (comb '(1 2) 1) '((1) (2)))
(check-expect (comb '(1 2 3) 2) '((1 2) (1 3) (2 3)))

Before next lab

Before the lab

Questions

• Questions about Assignment 2?
• Questions about Quiz 1?

Setup

• make a directory labs/L07 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Introducing foldr

• Form a group of 2 or 3.

• Work together to solve FICS Exercise 27

• Contracts were introduced in The Design Recipe

• Optionally write your contract in the form of a signature

• Here is an implementation of foldr, with the name changed so as not to conflict with the builtin. It is often easier to infer a type from a (simple) implementation.

(define (Foldr combine base lst)
  (cond
    [(empty? lst) base]
    [else (combine
            (first lst)
            (Foldr combine base (rest lst)))]))

Guess the function

This part of the lab is based on FICS Exercise 29

Fill in the two instances of ... in the following template with a builtin function so that the tests pass. Try some other values for mylist, mylist1, mylist2 to help you guess.

#lang htdp/isl+
(define mylist '(1 2 buckle my shoe))
(check-expect (foldr cons empty mylist) (... mylist))
(define mylist1 '(3 4 5))
(define mylist2 '(1 2))
(check-expect (foldr cons mylist1 mylist2) (... mylist2 mylist1))

• Do these uses of foldr fit your contract above? If not, how can you fix your contract.

Filter in terms of foldr

On your own, complete FICS Exercise 28

• You will have to rename the function to Filter to avoid colliding with the builtin filter.

• You will need to use the language htdp/isl+ or "Intermediate Student with Lambda"

• Your solution should pass the following test cases. odd? is a builtin function.

• The previous part (Ex. 29) may give you some ideas about how to do this part.

(check-expect (Filter (lambda (x) #f) '(1 2 3)) '())

(check-expect (Filter odd? '(0 1 2 3 4 5 6 7 8 9))
              (list 1 3 5 7 9))

Before next lab

Before the Lab

Background

• Node.js REPL
• JavaScript functions
• NodeJS test runner

Getting started

• make a directory labs/L08 inside your ~/cs2613 git repository
• All of your work from today should be committed in that directory (and pushed before you leave).

Questions

• Questions about Quiz 1?
• Questions about Assignment 2?
• Questions about Programming Contest

Running JavaScript

In a file

• Create a new file ~/cs2613/labs/L08/hello-world.js
• Add some JavaScript code, save

    console.log("Hello world");

Running a script

• open a terminal, find the right directory

  $ node hello-world.js

• commit your file

In a Browser

• Start Firefox

• Open the "Web Console" with Ctrl-Shift-K (or navigate via the "hamburger menu" to "Web Developer -> Web Console" ).

• Select the tab "Console"

• Copy-paste the code in.

In the REPL

• Start up a node repl

  $ node

• Load your code into the repl

    > .load hello-world.js
  

• Evaluate some expressions

    > 1 + 1
    > "Hello " + "world!"
  

JavaScript equality and type coercion

From Eloquent JavaScript Chapter 1, and the WAT talk by Gary Bernhardt, we know that type coercion is an important part of evaluating JS expressions. This is sometimes useful

> 42 + 'is a big number'

But just as often a source of errors and confusion.

> "" + 1
> x=""
> x++

One operator where type coercion can be particularly surprising is the standard equality test ==. Not only does type coercion apply:

> "" == 0
> false == 0
> "" == 0

but special rules apply to "undefined" and "null"

> false == undefined
> undefined == null
> undefined == undefined

even though they would normally be considered falsy (considered false in boolean contexts).

   > if (undefined) { console.log("truthy") } else { console.log("falsey") }

NaN is another falsy value not == to the other falsy values, not even itself:

   > NaN == undefined
   > NaN == NaN

To avoid this twisty maze of "helpful" type coercion, you can use the "strict equality" checker ===

   > "" === 0
   > false === 0
   > "" === 0
   > false === undefined
   > undefined === null
   > undefined === undefined

Javascript functions

Reference for this section is JavaScript functions Like Racket, JavaScript has two different ways of defining functions. The first way is by assigning an anonymous function to a variable.

    (define square (lambda (x) (* x x)))

    let square = x => x*x;
    let square2 = function (x) {return x*x};

• Answer the following questions in your journal:

  • How is assignment (=) in javascript different from binding (let, define) in Racket?

  • return is mandatory. What does it mean?

  • what is the difference between the two kinds of anonymous functions in JavaScript? Hint: the first example is an arrow function.

The more compact way of defining functions in both Racket and JavaScript combines the binding and creation of a function/lambda

    (define (square x) (* x x))

    function square(x) { return x*x }

• Start a new file ~/cs2613/labs/L08/loop-arith.js, and fill in the following definition for mult using plus and for.

const plus = (a,b) => {
    for (let i=0; i < a; i++){
        b++;
    }
    return b;
}

const mult = function (a,b) {
    sum=0;



    return sum;
}

• Test your file manually, using e.g. the node REPL.

Node test runner

In order to provide similar functionality to check-expect in racket, we will use the nodejs test framework.

In order to use the test runner, we need to add two lines to the beginning of our javascript files.

const test=require("node:test");
const assert=require("assert");

We'll talk more about both const and require later.

A test is considered to pass if it does not throw an exception. assert provides several functions useful for this kind of test. We will concentrate on assert.strictEqual for now, which corresponds to the === test discussed above.

Here is a complete example with one passing test and one failing one

const test=require("node:test");
const assert=require("assert");

function add1(n) {
    return n+1;
}

test('one plus one is two', (t)=>assert.strictEqual(add1(1),2));
test('one plus one is three', (t)=>assert.strictEqual(add1(1),3));

Test coverage

We will use an experimental feature of node v20 in order to make sure we have test coverage (analogous to how we set up DrRacket for visual test coverage).

Getting a coverage report

• Run our sample program from above with arguments to node to see a test coverage report.

   $ node --test --experimental-test-coverage sample.js
  

• All going well, your output should contain something like

ℹ start of coverage report
ℹ ---------------------------------------------------------
ℹ file      | line % | branch % | funcs % | uncovered lin…
ℹ ---------------------------------------------------------
ℹ sample.js | 100.00 |   100.00 |  100.00 |
ℹ ---------------------------------------------------------
ℹ all files | 100.00 |   100.00 |  100.00 |
ℹ ---------------------------------------------------------
ℹ end of coverage report

Writing tests

• Add tests to your loop-arith.js solution until you have complete coverage.

• Check your work for test coverage.

• Make sure your tests pass as well as having coverage.

• Remember that test coverage is a necessary, but not sufficient condition for a good test suite. What things should you test beyond complete coverage?

Before the next lab

Before the lab

Questions

• About Quiz 1?
• About Assignment 2?
• About the programming contest?
• About JavaScript functions?
• About the node test framework?

Deep Comparison

Follow the Deep Comparison Exercise to write a function deepEqual that passes the following tests. assert uses something very similar for the deepStrictEqual test used below. Your function should pass the following tests.

let obj = {here: {is: "an"}, object: 2};
test("self", (t)=> assert.strictEqual(deepEqual(obj,obj),true));
test("null", (t)=> assert.strictEqual(deepEqual(null,null),true));
test("!null", (t)=> assert.strictEqual(deepEqual(null,obj),false));
test("different", (t)=>
    assert.strictEqual(deepEqual(obj, {here: 1, object: 2}),false));
test("equivalent", (t)=>
    assert.strictEqual(deepEqual(obj, {here: {is: "an"}, object: 2}),true));

Remember from L08 that you need the following lines to use the test framework

const test=require("node:test");
const assert=require("assert");

It can be frustrating trying to achieve full branch coverage (with our current tools). One useful trick is to turn one sided ifs into two sided ones, so the missing branch is turned into a missing line.

JavaScript Arrays

JavaScript supports arrays. They are actually implemented as objects, which leads to some slightly surprising behaviour:

> x=[]
> x[10]=1
> x
> x["bob"] = 2
> x

Generating arrays

Follow the (first part of the) Sum of a Range Exercise to write a range function that passes the following tests.

test("empty", (t)=>assert.deepStrictEqual(range(2,1),[]));
test("single", (t)=> assert.deepStrictEqual(range(2,2),[2]));
test("multiple", (t)=>
    assert.deepStrictEqual(range(42,50),[42,43,44,45,46,47,48,49,50]));

Arrays Continued

Follow the (second part of the) Sum of a Range Exercise to write a sum function that passes the following tests.

test("empty", (t)=> assert.strictEqual(sum([]),0));
test("single", (t)=> assert.strictEqual(sum([2]),2));
test("multiple", (t)=> assert.strictEqual(sum(range(1,10)),55));

Adding step argument to range.

Add an optional step argument to the range function so that the following tests pass. The original tests should keep passsing, that's a big part of the point of having unit tests.

test("step 2", (t)=> assert.deepStrictEqual(range(1,10,2),[1,3,5,7,9]));
test("step -1", (t)=> assert.deepStrictEqual(range(5,2,-1),[5,4,3,2]));

Before next lab

Before the lab

Questions

• Questions about Racket Quiz?
• About JavaScript objects and arrays?

Flattening

Solve the Flatten Exercise using reduce and concat methods. Your solution should pass the following test suite.

test("base case", ()=> assert.deepStrictEqual(flatten([]),[]))
test("single element",
     function () {
     assert.deepStrictEqual(flatten([1]),[1]);
     assert.deepStrictEqual(flatten(["foo"]),["foo"]);
     assert.deepStrictEqual(flatten([{foo: 1}]),[{foo: 1}]);
     });
test("longer list", ()=>
    assert.deepStrictEqual(flatten([[1],2,[3],4,[5,6]]),[1,2,3,4,5,6]));

Does the following test pass with your implementation? If not, why not?

test("deeper nesting", (t)=>
    assert.deepStrictEqual(flatten([[[1],2,[3]],4,[5,6]]),[1,2,3,4,5,6]));

Referring back to L07, answer the following in your journal.

• is reduce more like Racket's foldl or foldr?

Every

Solve the Every Exercise

Call the version using a loop every_loop

test("all true", (t)=>
    assert.strictEqual(every_loop([1, 3, 5], n => n < 10), true));
test("last false", (t)=>
    assert.strictEqual(every_loop([2, 4, 16], n => n < 10), false));
test("last middle false", (t)=>
    assert.strictEqual(every_loop([2, 16, 3], n => n < 10), false));
test("empty list", (t)=>
    assert.strictEqual(every_loop([], n => n < 10),true));

Call the version using the some method every_some. The tricky part here is to construct a function that is the negation of the given function.

test("all true", (t)=>
    assert.strictEqual(every_some([1, 3, 5], n => n < 10), true));
test("last false", (t)=>
    assert.strictEqual(every_some([2, 4, 16], n => n < 10), false));
test("last middle false", (t)=>
    assert.strictEqual(every_some([2, 16, 3], n => n < 10), false));
test("empty list", (t)=>
    assert.strictEqual(every_some([], n => n < 10),true));

Timing functions

We are presented with two different implementations of the Fibonacci function, and we want to see which one is faster ¹.

const test=require("node:test");
const assert=require("assert");

function fib(n) {
    if (n<=2)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

let cache = {};
function memfib(n) {
    if (cache[n] !== undefined)
        return cache[n];

    if (n<=2)
        cache[n] = 1;
    else
        cache[n] = memfib(n-1)+memfib(n-2);

    return cache[n];
}

test("fib(35)=9227465",(t)=>assert.strictEqual(fib(35),9227465));
test("memfib(35)=9227465",(t)=>assert.strictEqual(memfib(35),9227465));

Using the function noisy as a template, write the higher order function timed that uses the builtins console.time and console.timeEnd to output timing information. The wrapped function produced by timed should produce the same values as the original function, as shown by the following tests.

test("timed(fib)(35)=9227465", (t)=>assert.strictEqual(timed(fib)(35),9227465));
test("timed(memfib)(35)=9227465",(t)=>assert.strictEqual(timed(memfib)(35),9227465));

let out=timed(fib)(42);
let out2=timed(memfib)(42);

test("fib(42)≈memfib(42)",assert.ok(Math.abs(out-out2)<0.000001))

It turns out that memfib is much faster. On my computer, the output from the last two timed calls is

fib(42): 970.887ms
memfib(42): 0.034ms

Notice how I have included the name of the function and the parameter in the output. Try to do the same.

Answer the following in your journal:

• Why do you think the last test does not use assert.strictEqual?
• The order of the timing output is a bit surprising. How can you explain it?

Before Next Lab

Before the lab

A Vector class

Do the Vector Type exercise.

test("addition", (t) =>
    assert.deepStrictEqual(new Vec(1, 2).plus(new Vec(2, 3)),
                           new Vec(3,5)));
test("subtraction", (t)=>
    assert.deepStrictEqual(new Vec(1, 2).minus(new Vec(2, 3)),
                           new Vec(-1,-1)));
test("length", (t) =>
    assert.strictEqual(new Vec(3, 4).length,5));

A Set ("Group") class

Do the Group exercise. Instead of the suggested array, use an object to store the elements of the "Group". The simplest way to implement from is to loop over the iterable argument and repeatedly call add.

const test=require("node:test");
const assert=require("assert");
class Group {
    constructor() {
        this.elements={}
    }
    add(element) {
        this.elements[element]=true;
    }
    has(element) {
    }
    delete(element) {
    }
    static from(iterable) {
    }
}
let group = Group.from([10, 20]);
test("has yes",(t)=>assert.strictEqual(group.has(10),true));
test("has no",(t)=>assert.strictEqual(group.has(30),false));
test("add existing is not error", (t)=>group.add(10));
test("delete existing", (t) => {
    group.delete(10);
    assert.strictEqual(group.has(10),false);
});

Racket Quiz

Before next lab

Before the lab

Before the lab

Background

• node.js filesystem API
• Promises API
• Async Functions

Callback Chaining

The recommended way to get maximimum performance from the node.js filesystem API is to use callbacks, i.e. functions to call when the I/O operation completes.

Replace the ALL-CAPITALS words in the following code sample with defined identifiers to make this callback chaining example work.

const fs=require("node:fs");

function log(string, next) {
    let date = new Date();
    function finish(err) {
        if (err) throw err;
        console.timeEnd("write");
        CALLBACK();
    }
    function write(err, fd) {
        if (err) throw err;
        fs.write(VALUE, date.toISOString() + ": " + string, CALLBACK);
    }
    console.time("write");
    fs.open("log.txt", "a", CALLBACK)
}

console.time("log");
log("first\n",
    () => {
        log("second\n",
            () => console.log("done"));
    });
console.timeEnd("log");

When you get the code working, the file log.txt should contain lines like the following (the exact date and time may differ):

2024-10-25T17:31:56.626Z: first
2024-10-25T17:31:56.629Z: second

Questions for your journal:

• Why are the functions write and finish defined inside log?
• What can you tell about the execution order from the printed output?
• Based on the printed timings, does it make sense to use asynchronous I/O to write a single string to a file?

Promises

In the Promises API file system methods return a Promise object that automates the chaining of callbacks. These Promise objects can be chained together using then. Fill in the appropriate API calls (they should be very similar to the first part, without the explicit callbacks).

const fs=require("node:fs/promises");

function log(string) {
    let date = new Date();
    return new Promise(next=> {
        console.time("write");
        API_CALL
            .then(fd=>API_CALL)
            .then(()=>console.timeEnd("write"))
            .then(CALLBACK)
            .catch((err) => console.log(err));
    });
}

console.time("log");
log("first\n")
    .then(()=>log("second\n"))
    .catch((err) => console.log(err));
console.timeEnd("log");

Questions for your journal:

• According to the NodeJS Documentation, what is one disadvantage of the Promises API?

• What does the Promise.catch method do?

Async Functions

Async Functions provide some nice features for programming with Promises, essentially eliminating some of the boilerplate from our previous example. They also introduce one very important keyword.

Replace the ALL-CAPITALS parts of the following program to duplicate the functionality of the previous versions.

const fs=require("node:fs/promises");

async function log(string) {
    console.time("write")
    const fd = MAGIC_KEYWORD API_CALL()
    let date = new Date();

    const promise=API_CALL();
    console.timeEnd("write");
    return promise;
}

console.time("log");
log("first\n")
    .then(()=>log("second\n"))
    .catch((err) => console.log(err));
console.timeEnd("log");

• What is the keyword used as MAGIC_KEYWORD above, and what does it do?

Before Next Lab