Worksheet Lox 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

abstract class Pastry {
  public void printMe (); 
}
class Beignet extends Pastry {
  @Override
  public void printMe() {
    System.out.println ("It's a beignet");
  }
}
class Cruller extends Pastry {
  @Override
  public void printMe() {
    System.out.println ("It's a cruller");
  }
}

class PastryTest {
  public static void main (String[] args) {
    var ps = new Pastry[] {new Beignet(), new Cruller()};
    for (var p : ps) {
      p.printMe();
    }
  }
}

$ javac PastryTest.java 
$ java PastryTest 
It's a beignet
It's a cruller

enum Pastry:
  case Beignet
  case Cruller
import Pastry.*

def printPastry (p: Pastry) =
  p match
    case Beignet => println("It's a Beignet")
    case Cruller => println("It's a Cruller")

def main(args:Array[String]) = 
  var ps = List(Beignet,  Cruller)
  for (p <- ps) do printPastry(p)

$ scala Pastry.scala 
It's a Beignet
It's a Cruller

interface PastryVisitor {
  public void visitBeignet(Beignet beignet); 
  public void visitCruller(Cruller cruller);
}
abstract class Pastry {
  public abstract void accept(PastryVisitor visitor);
}
class Beignet extends Pastry {
  @Override
  public void accept(PastryVisitor visitor) {
    visitor.visitBeignet(this);
  }
}
class Cruller extends Pastry {
  @Override
  public void accept(PastryVisitor visitor) {
    visitor.visitCruller(this);
  }
}

class PastryPrinter implements PastryVisitor {
  public void visitBeignet(Beignet beignet) {
    System.out.println ("It's a beignet");
  }
  public void visitCruller(Cruller cruller) {
    System.out.println ("It's a cruller");
  }
}
public class PastryTest {
  public static void main (String[] args) {
    var printer = new PastryPrinter ();
    var ps = new Pastry[] {new Beignet(), new Cruller()};
    for (var p : ps) {
      p.accept(printer);
    }
  }
}

$ javac PastryTest.java 
$ java PastryTest 
It's a beignet
It's a cruller

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.

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

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 

#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.