Questions and Completion

To receive credit for completing the worksheet, you must complete the corresponding quiz (it is just a checkbox) on D2L when you have finished the worksheet.

If you have questions as you go through this worksheet, please feel free to post them on the discussion forum.

Java

Java Type Checking 1

Does the Java compiler javac type checker allow assigning an int variable to a char variable?

Write a small program to test.

Java Type Checking 2

Does the Java compiler javac type checker allow assigning an int variable to a String variable?

Write a small program to test.

Java Upcasting

Does the Java compiler javac type checker allow /upcasting/, e.g., allowing a reference of type B to be used as a reference of type A (given the class declarations below)?

class A           { int x; }
class B extends A { int y; }

Write a small program to test.

Solution: Java Upcasting

Java Upcasting Disassembly

Look at the Java Virtual Machine (JVM) bytecode for your program from the previous upcasting subsection.

Do this by running javap (see javap manual page) with the -c option and the name of your class (you must have run javac to compile the Java source and produce the .class file already).

For example, for the code from Solution: Java Upcasting:

$ javap -c Upcast
Compiled from "Upcast.java"
public class Upcast {
  public Upcast();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  void f(Upcast$B);
    Code:
       0: aload_1
       1: astore_2
       2: return
}

Note: the code for method f does not show any dynamic checks (aload and astore are like the mov instructions in Intel assembly language).

Java Downcasting

Does the Java compiler javac type checker allow /downcasting/, e.g., allowing a reference of type A to be used as a reference of type B (given the class declarations below)?

class A           { int x; }
class B extends A { int y; }

Write a small program to test.

Solution: Java Downcasting

Java Downcasting Disassembly

Look at the Java Virtual Machine (JVM) bytecode for your program from the previous downcasting subsection.

Do this by running javap (see javap manual page) with the -c option and the name of your class (you must have run javac to compile the Java source and produce the .class file already).

For example, for the code from Solution: Java Downcasting:

$ javap -c Downcast
Compiled from "Downcast.java"
public class Downcast {
  public Downcast();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  void g(Downcast$A);
    Code:
       0: aload_1
       1: checkcast     #2                  // class Downcast$B
       4: astore_2
       5: return
}

Note: the code for method g does show a dynamic check this time!

The checkcast instruction is the one that dynamically checks whether the argument is an instance of B or not. It is generated by the compiler when we use the cast (B).

Scala

Install SBT

• SBT compiles and invokes tests on Java/Scala code
• On windows, install the msi installer for sbt from here Do not attempt to use sbt inside of the linux subsystem for windows. As of March 2017, it does not work.
• Alternatively, on windows you can also use a package manager such as scoop. See here.

$ scoop install sbt

• On Mac or Linux, use a package manager to do the install. On a mac, use homebrew. On Ubuntu, use apt-get.
  

$ brew install sbt

• Change directory to your repository
  • Use dir or ls to check build.sbt is in current directory
• Run: sbt
• The first time you do this, you will need to be connected to the internet

Optional: Install VSCode

• You can use any editor you like for scala. A simple text editor is fine. Just open a terminal window and run sbt on the command line.
• If you want an editor with a little smarts, I recommend VSCode.
• After installing, you need to get extensions for scala and sbt, then sbt will run in the terminal window within VSCode.

Get the homework code

Download the homework code for the first assignment from the Course Schedule For the first assignment, you are only going to complete hw1-gameoflife.scala.

Read Repository Instructions

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. In the first assignment it will be hw1-gameoflife.scala. You hand the homework in on D2L.

Run SBT / Start Scala REPL

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
    │   └── java
    |       └── gameoflife.java
    |   └── scala
    │       └── hw1-gameoflife.scala
    └── test
        └── scala
            ├── UnitSpec.scala
            └── gameoflifetests.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 Concepts of Programming Languages (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] compiling 2 Scala sources and 1 Java source to ...
...
Welcome to Scala 3.5.0 (21.0.1, Java Java HotSpot(TM) 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.

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

Literals and Arithmetic

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

REPL Tips

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.

Val And Var

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?

Tuples

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

Solution: Tuples

Lists

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

Equality Testing

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

Factorial

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

Upto

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

Repeat

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

Recursive List Traversal

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

Analyzing Functions

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

Solutions

Solution: Java Upcasting

public class Upcast {
  static class A           { int x; }
  static class B extends A { int y; }

  void f (B p) {
    A q = p;
  }
}

Solution: Java Downcasting

public class Downcast {
  static class A           { int x; }
  static class B extends A { int y; }

  static B convert (A p) {
    B result = (B) p;
    return result;
  }

  public static void main (String[] args) {
    A r = new A ();
    r.x = 5;
    B s = convert (r);
    System.out.println (s);
  }
}

Solution: Scala Literals and Arithmetic

  val b1 = true
  val b2 = false

  val b3 = !b2
  val b4 = b1 && b2 
  val b5 = b1 || b2 

  val n1 = 2
  val n2 = 3

  val n3 = n1 + n2
  val n4 = n1 - n2
  val n5 = n1 * n2
  val n6 = n1 / n2

  /* Character literals are delimited by an apostrophe. */
  val c1 = 'h'
  val c2 = 'e'
  val c3 = 'e'

  /* String literals are delimited by double quotes. */
  val s1 = "hello"
  val s2 = "world"

  /* The string concatenation function is written infix as "+". */
  val s3 = s1 + " " + s2

Solution: Tuples

  /* Pairs are created using parentheses. */

  /* They may have the same type. */
  val pair1 = (3, 5)
  val pair2 = ("hello", "world")

  /* Or different types. */
  val pair3 = (3, "hello")
  val pair4 = ("hello", 3)

  /* More generally, we can create tuples using the same syntax. */
  val tuple1 = pair1
  val tuple2 = (3, 5, 3, "hello")

  /* Tuples can nest. */
  val nested1 = ((3, 5), ("hello", "world"))
  val nested2 = (pair1, pair2)

  /* Now test equality of nested1 and nested2. */
  val equal12 = nested1 == nested2

  /* The nesting is significant.  tuple2 has a different type to nested1
   * and nested2.  Try running "tuple2 == nested1" at the 
   * command line to see that they are distinct values.
   */

Solution: Lists

  val emptylist = Nil
  /* The following yields the same result as emptylist. */
  val emptylist2 = List ()  

  val singletonlist1 = List (5)
  val singletonlist2 = List ('a')
  val singletonlist3 = List ("hello")
  val singletonlist4 = 5 :: Nil

  /* Every object in a list must have the same type. */
  val list1 = List (5, 4, 3, 2, 1)
  val list1a = 5 :: (4 :: (3 :: (2 :: (1 :: Nil))))
  val list2 = List (1, 2, 3, 4, 5)

  /* Creates a List[Char] from a String */
  val characters = "hello".toList

  /* Functions/methods such as "reverse", concatenation/append ":::", and cons "::" can operate on
   * lists.
   */
  val list3 = list2.reverse
  val list4 = list1 ::: list2 /* ::: - joins two lists */
  val list5 = 29 :: list2     /* ::  - joins a list element and a list */
  val list6 = 1 :: 2 :: 3 :: 4 :: 5 :: Nil

  /* Lists can be compared for equality, and equality is based upon
   * having the same elements.  It is not possible to create
   * (observably) distinct lists with the same elements.
   */

  val equal12a = list1 == list2
  val equal12b = list1 == list3

  val equal = list2 == (1 to 5).toList

  /* SUMMARY:
   * * TUPLES: the type specifies the length, and individual components
   *   may have different types.
   *
   * * LISTS: the length is unbounded (and may even be infinite!), and
   *   individual components must have the same type.
   *
   * Tuples, lists, strings, etc., are all immutable.  You cannot
   * change them at all.
   */

Solution: Scala Equality Testing

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

Solution: Scala Factorial

def fact (n:Int) : Int = if (n <= 1) 1 else n * fact (n - 1)

def fact (n:Int) : Int = {
  println ("called with n = %d".format (n))
  if (n <= 1) {
    println ("no recursive call")
    1 
  } else {
    println ("making recursive call")
    n * fact (n - 1)
  }
}

Solution: Scala Upto

  def upto (start:Int, end:Int) : List[Int] = {
    if (start > end) 
      Nil
    else 
      start :: upto (start + 1, end)
  }

Solution: Scala Repeat

  def repeat [X] (element:X, repetitions:Int) : List[X] = {
    if (repetitions == 0)
      Nil
    else 
      element :: repeat (element, repetitions - 1)
  }

Solution: Scala List Traversal

// Unit is the equivalent of the C/Java void type
// The dummy value of type Unit is ().
def printCounterAux [X] (xs:List[X], count:Int) : Unit =
  xs match
    case Nil   => ()
    case y::ys => 
      println ("[%03d] %s".format (count, y))
      printCounterAux (ys, count + 1)

def printCounter [X] (xs:List[X]) : Unit =
  printCounterAux (xs, 1)

def main(args: Array[String]): Unit =
  printCounter (List ("the", "rain", "in", "spain"))

Solution: Scala Analyzing Functions

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.