Worksheet Scala and Prerequisites (Java and C)

Open a console / terminal on your computer.

• For Windows, use the builtin "Command Prompt" (cmd.exe). The more adventurous might try any of the following:
  • Windows Terminal
  • git-bash
  • Windows PowerShell
  • Windows Subsystem for Linux
• For Linux, open whichever terminal program came with your system. That terminal program will probably run the bash shell, unless you have configured it to use a different shell program.
• For OS X, use the builtin "Terminal", found in /Applications/Utilities. It will run the zsh shell by default.

Verify that you can change directories (with cd), create directories (with mkdir), list directories (with ls or dir), etc.

Terminology: Windows uses the term "console". Linux, OS X, and others more typically use "terminal"; moreover, a shell program such as zsh reads commands from the terminal, so we might say "open a shell" rather than "open a terminal".

On Linux and OS X, your home directory probably has the form /home/bob or /Users/bob; this is stored in the HOME environmental variable. The home directory has some special support:

• You can change to your home directory quickly by just running cd with no directory specified.
• You can refer to your home directory by ~. For example, mkdir -p ~/doc/mynotes creates a doc/mynotes hierarchy of directories in your home directory.

In the Command Prompt and terminal, you can often press the TAB key to autocomplete.

There are different behaviors when autocompletion is used with multiple entries, e.g., multiple files/directories with the same prefix

• Autocompletion in Command Prompt (Windows) cycles through the entries.
• Autocompletion in zsh (Linux and OS X) does a partial completion; if you press TAB a second time, it will show you the possible completions and allow you to select one with the arrow keys. You can also cycle through the options by hitting TAB repeatedly.

Using TAB liberally will make your command-line interactions significantly faster.

The terminal keeps track of all the commands you've typed in. This is known as the command history. You can move backwards and forwards through the history using the arrow keys. Try it!

In some shells, you can also search backwards through the history by holding the control key and pressing the key for r. This key combination is often abbreviated Ctrl-R (although it's lowercase). Once you've typed what you are searching for, you can press Ctrl-R again to search further backwards. If you go to far back, you can press Ctrl-S to search forward.

The shell is a Read-Eval-Print loop (REPL). Many other REPLs also have a command history. Try the arrow keys in Scala. 😊. Try them in Lox. 🙁.

On Unix systems (Linux, Mac) you can get command history by installing rlwrap. On a mac the install command is brew install rlwrap.

You can precede any shell command with rlwrap in order to get a command history. For example, try running lox this way:

mvn -q clean compile && rlwrap java -cp target/classes com.craftinginterpreters.lox.Lox x.lox

Write a hello world program in Java. Your program should print "Hello world!" to the console / terminal, and then exit.

Solution: Hello World in Java

Modify the following fractal function.

public class Fractal {
  public static void fractal (int x) {
    if (x > 0) {
      System.out.print (x + " ");
    }
  }

  public static void main (String[] args) {
    if (args.length != 1) {
      System.out.println ("usage: java Fractal <number>");
      System.exit (1);
    }
    int num = Integer.parseInt (args[0]);
    fractal (num);
    System.out.println ();
  }
}

Your function should print numbers as follows

input |  output
------|--------
1     | 1
2     | 1 2 1
3     | 1 2 1 3 1 2 1
4     | 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
etc...

Solution: Recursion in Java

Write a singly-linked list class in Java.

Include a sensible toString method.

Include functions to add and remove elements from the front of the list.

Write a main program that creates a list with 5 elements, prints the list, then deletes the first 2 elements and prints the list again.

Solution: Linked List in Java

You can run code online using repl.it. You can see the assembly code produced by a compiler using godbolt.org.

Mac and linux will come with gcc or clang preinstalled.

On windows, you could try any of the following:

• mingw-w64
• Visual Studio Community
• Windows Subsystem for Linux

Write a hello world program in C. Your program should print "Hello world!" to the console / terminal, and then exit.

Compile your program with a C compiler, then run it from the console / terminal.

Solution: Hello World in C

Consider the following C program. Replace the comments with code, so that the value of x is 10 when it is printed.

#include <stdio.h>
#include <stdlib.h>

void update (int* p) {
  /* TODO */
}

int main () {
  int x = 5;
  update (/* TODO */);
  printf ("%d\n", x);
}

Solution: Pointers

Consider the following C program.

#include <stdio.h>
#include <stdlib.h>

int x = 5;

int main () {
  int y = 10;
  int* p = (int*) malloc (sizeof (int));
}

Answer the following questions:

1. Where in memory is x allocated?
2. Where in memory is y allocated?
3. Where in memory is p allocated?
4. Where in memory is p pointing to?

Solution: Allocation Location

Consider the following C program.

#include <stdio.h>
#include <stdlib.h>

void countdown (int n) {
  if (n <= 0) {
    printf ("done\n");
  } else {
    printf ("counting down\n");
    countdown (n - 1);
  }
}

int main () {
  countdown (5);
}

When it is executed:

1. What will be printed?
2. What is the maximum number of activation records (also known as stack frames) on the call stack at one point during execution?

Solution: Call-Stack Allocation

Consider the following two C programs. Which one of these programs is problematic and why?

#include <stdio.h>
#include <stdlib.h>

int foo (int n) {
  int result = 2 * n;
  return result;
}

int main () {
  int x = foo (5);
  int y = foo (7);
  printf ("%d\n", x);
  printf ("%d\n", y);
}

#include <stdio.h>
#include <stdlib.h>

int* foo (int n) {
  int result = 2 * n;
  return &result;
}

int main () {
  int* p = foo (5);
  int* q = foo (7);
  printf ("%p %d\n", p, *p);
  printf ("%p %d\n", q, *q);  
}

Solution: Dangling Pointer

Unzip scala-hw.zip.

You will not be able to verify that your code compiles and passes tests without the tests contained in this zip file.

Browse the instructions in the README.html file in the top-level directory of the code you unzipped from D2L. You will need to refer to these instructions when you complete the assignment later.

Each week you will complete one file from this zip file. In the first week it will be fp1.scala. You hand the homework in on D2L.

Open a command prompt or terminal, then change directory to the top-level directory of your unzipped code.

Verify that you have the file build.sbt in the current working directory. On a Linux or OS X system, it should look like this when you run ls and tree.

$ ls
README.html  build.sbt    src/
$ tree
.
├── README.html
├── build.sbt
└── src
    ├── main
    │   └── scala
    │       └── fp1.scala
    └── test
        └── scala
            ├── UnitSpec.scala
            └── fp1tests.scala

Use dir for a command prompt on Windows; you should see the same files and directories.

The file build.sbt contains instructions about how to build a project and other configuration information. When you start SBT, it uses the build.sbt file in the current working directory. This is very common for command-line build tools, but differs from GUI development systems.

When you first run SBT, it will attempt to download the version of the Scala compiler specified in build.sbt and various other libraries. For this reason, you will need a network connection on the first run.

Now run SBT by entering sbt at the command / shell prompt. You should see something like the following (the /tmp/assignments directory will be different for you).

$ sbt
[info] Loading project definition from /tmp/assignments/project
...lots of output from downloading files...
[info] Set current project to CSC447 Assignments (in build file:/tmp/assignments/)
>

The SBT prompt is >. You can enter SBT commands there, e.g., compile. See README.md for more examples.

The only SBT command that we need at present is console. Enter the console command at the SBT prompt to start the Scala REPL. You should see something like the following.

> console
[info] Updating {file:/tmp/assignments/}assignments...
[info] Resolving jline#jline;2.12 ...
[info] Done updating.
[info] Compiling 4 Scala sources to /tmp/assignments/target/scala-2.11/classes...
[info] Starting scala interpreter...
[info] 
Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_60).
Type in expressions to have them evaluated.
Type :help for more information.

scala> 

The Scala REPL prompt is scala>. You can enter Scala expressions and definitions at the Scala REPL prompt. Try this out by entering 1 + 2. You should see something like the following.

scala> 1 + 2
res0: Int = 3

Write some Scala expressions for Boolean, integer, character, and String literals. Write some Scala expressions involving arithmetic. Try them in the Scala REPL.

You can bind the expressions to variables:

val x = true

or just type them in directly:

true

Solution: Scala Literals and Arithmetic

Tips to improve REPL interaction:

1. Try referring to one of the previous values in a new expression for the Scala REPL. E.g.,

   1 + (res0 * 2)
   

2. Use command-line editing to pull up previous expressions and edit them in the REPL. Support varies between systems. Press the Up/Down arrow keys to scroll through REPL history. Press the Left/Right arrow keys to move through current expression (to edit).
3. If you write Scala code in a text editor and then paste it into the REPL, you may end up with parsing ending too early. Either add curly braces to prevent parsing ending too early, or enter :paste into the REPL, paste, then press Control D to end pasting mode.

1. In the REPL, define a variable x using val and try to assign to it. What happens and why?
2. In the REPL, define a variable x using var and try to assign to it. What happens and why?
3. In the REPL, define a variable x using val without an initializing expression. Why does the REPL reject that?
4. In the REPL, define a variable x using val. Then define another variable x using val with a different value. Why does the REPL accept that? Which value is returned when you enter x into the REPL now?

Write some Scala expressions for tuples. Try them in the Scala REPL.

Solution: Tuples

Write some Scala expressions to build lists (the builtin Scala List type). Use the :: (cons) operator for some, and the List (...) form for others. Try your expressions in the Scala REPL.

Solution: Lists

Warning: Scala equality testing syntax conflicts with Java:

1. Use == in Scala where you would use the equals method in Java, e.g., to test if two String instances contain the same characters.
2. Use eq in Scala where you would use the == operator in Java, i.e., to test reference equality (that two references are pointing to the same instance).

Run Scala expressions in the REPL to convince yourself that this is correct.

Solution: Equality Testing

Write the factorial function in Scala and try it in the REPL.

Then change your factorial function so that it prints out information about each recursive call as it happens.

Solution: Factorial

Try the following expression in the Scala REPL.

(10 to 20).toList

Write a Scala function upto that takes start and an end parameters (both of type Int), then returns a List[Int] of all Int between start and end (inclusive). That is, upto (start, end) should have the same result as (start to end).toList.

Solution: Upto

Write a Scala function that takes an element and repeats it a given number of times.

It should work as follows:

scala> repeat ("hello", 5)
res0: List[String] = List(hello, hello, hello, hello, hello)

scala> repeat (13, 5)
res1: List[Int] = List(13, 13, 13, 13, 13)

Solution: Repeat

Define a Scala function printCounter that prints out each element of a list on its own line with a counter. The function must be written using recursion. You can create additional auxiliary functions if you like.

The output should resemble:

scala> printCounter (List ("the", "rain", "in", "spain"))
[001] the
[002] rain
[003] in
[004] spain

Recursive List Traversal

Consider the following Scala code:

def f [X] (xs:List[X]) : List[X] =
  xs match
    case Nil => Nil
    case y::ys => y::(y::(f (ys)))

Our goal is to describe the effect of this function in words.

Develop some intuition for its effect by working out on paper:

• the result of running f on a list of length 0 (there are not many!)
• the result of running f on a list of length 1
• the result of running f on a list of length 2
• the result of running f on a list of length 3

Confirm your results using the Scala REPL.

Notice that if your choice of a list of length 1 is List (5) (say), then you can use that result when working out the result of running f on List (4, 5), because it recursively calls to f (List (5)). This breaks your analysis into smaller, simpler pieces.

With these results, and the intuition you have developed, what do you think the function does? Look at the code again to confirm your intuition.

Analyzing Functions

public class Hello {
  public static void main (String[] args) {
    System.out.println ("Hello world");
  }
}

$ javac Hello.java
$ java Hello
Hello world

public class Fractal {
  public static void fractal (int x) {
    if (x > 0) {
      fractal (x-1);
      System.out.print (x + " ");
      fractal (x-1);      
    }
  }

  public static void main (String[] args) {
    if (args.length != 1) {
      System.out.println ("usage: java Fractal <number>");
      System.exit (1);
    }
    int num = Integer.parseInt (args[0]);
    fractal (num);
    System.out.println ();
  }
}

$ javac Fractal.java
$ java Fractal 4
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 

public class LinkedListDemo {
  private Node first;
  static class Node { 
    public int item; 
    public Node next; 
    public Node (int item, Node next) { 
      this.item = item; 
      this.next = next; 
    }
  }

  public boolean isEmpty () {
    return first == null;
  }

  public void push (int item) {
    first = new Node(item, first);    
  }

  public int pop () {
    if (isEmpty()) throw new java.util.NoSuchElementException ();
    int result = first.item;
    first = first.next;
    return result;
  }

  public String toString () { 
    StringBuilder result = new StringBuilder ("[ ");
    for (Node x = first; x != null; x = x.next) {
      result.append (Integer.toString(x.item));
      result.append (" ");
    }
    result.append ("]");
    return result.toString ();
  }

  public static LinkedListDemo of(int... items) {
    LinkedListDemo result = new LinkedListDemo();
    for (int i = items.length - 1; i >= 0; i--) {
      result.push(items[i]);
    }
    return result;
  }

  public static void main (String[] args) {
    LinkedListDemo list = LinkedListDemo.of (24, 35, 67, 83, 22);
    System.out.println(list);
    list.pop();
    list.pop();
    System.out.println(list);
  }

}

$ javac LinkedListDemo.java
$ java LinkedListDemo      
[ 24 35 67 83 22 ]
[ 67 83 22 ]

#include <stdio.h>
#include <stdlib.h>

int main () {
  printf ("Hello world!\n");
  return 0;
}

$ gcc -o hello hello.c
$ ./hello 
Hello world!

#include <stdio.h>
#include <stdlib.h>

void update (int* p) {
  *p = 10;
}

int main () {
  int x = 5;
  update (&x);
  printf ("%d\n", x);
}

$ gcc -o pointers-01-solution pointers-01-solution.c
$ ./pointers-01-solution 
10

1. Global memory.
2. In an activation record for main (also known as stack frame) stored on the call stack.
3. In an activation record for main (also known as stack frame) stored on the call stack.
4. On the heap.

1. This is printed.

   counting down
   counting down
   counting down
   counting down
   counting down
   done
   

2. There are at least 8 activation records on the call stack when done is printed by printf. There may be more since we do not know the implementation of printf.
   • main
   • count with n = 5
   • count with n = 4
   • count with n = 3
   • count with n = 2
   • count with n = 1
   • count with n = 0
   • printf

The first program is fine.

The second program is problematic because p is a dangling pointer after foo returns. That is, p contains a pointer to an area of memory that is not defined, and when it is dereferenced (using *p) the behavior is not guaranteed: it might be 10, some other value, or crash the program. This happens because the result variable is allocated in the activation record for foo, and the address of result is returned from foo, but the activation record for foo is deallocated (hence the memory storing result is also deallocated) when foo returns.

These are straightforward:

scala> List (1, 2, 3) == List (1, 2, 3)
res1: Boolean = true

scala> List (1, 2, 3) eq List (1, 2, 3)
res2: Boolean = false

These are more tricky. The REPL happens to return the same String instance for hello so eq does not return false as we expect.

scala> "hello" == "hello"
res3: Boolean = true

scala> "hello" eq "hello"
res4: Boolean = true

But we can use a different expression to create a fresh instance of a hello String. This works as expected (returns false for eq).

scala> "hello" == "olleh".reverse
res5: Boolean = true

scala> "hello" eq "olleh".reverse
res6: Boolean = false

f (Nil)
--> Nil

f (5::Nil)
--> 5::(5::(f (Nil)))
--> 5::(5::(Nil))

f (4::(5::Nil))
--> 4::(4::(f (5::Nil)))
--> 4::(4::(5::(5::(Nil))))

f (3::(4::(5::Nil)))
--> 3::(3::(f (4::(5::Nil))))
--> 3::(3::(4::(4::(5::(5::(Nil))))))

The function doubles each occurrence of elements in a list. The resulting list is twice as long as the input list.