Wakatta!

Like Eureka!, only cooler

Seven Languages in Seven Weeks Scala Day 1

The language for this week is Scala, which attempts (among other things) to brings functional programming and a new concurrency model to the JVM.

This was a language I was really keen to know more about. I am using Java a lot, professionally, so I am always looking for options in this ecosystem. I am pretty sure the next book after this one will be a Scala book.

Scala Types

The first thing we learn about Scala is that it is “strongly typed.” This is not a very helpful description, as the definition is fairly loose. And the proof offered by the author that the language is strongly typed is strange:

Scala is strongly typed? 
1
2
3
4
5
6
7
8
9
10
11
12

scala> 4 * "abc"
<console>:8: error: overloaded method value * with alternatives:
  (x: Double)Double <and>
  (x: Float)Float <and>
  (x: Long)Long <and>
  (x: Int)Int <and>
  (x: Char)Int <and>
  (x: Short)Int <and>
  (x: Byte)Int
 cannot be applied to (java.lang.String)
              4 * "abc"
                ^

So a string cannot be multiplied by a number? By this standard, C is strongly typed as well:

What about C? 
1
2
3
4
5
6
7
8
9

#include <stdio.h>

int main() {
  char *str = "abc";

  printf("%s\n", (4*str));

  return 0;
}

1
2
3

$ gcc -o typed typed.c 
typed.c: In function ‘main’:
typed.c:6: error: invalid operands to binary * (have ‘int’ and ‘char *’)

As Scala has a theoretical background, perhaps it is useful to move to the language of Type Theory.

A more useful definition than strong typing, is whether a type system is expressive: what do types of expressions tell about how the expressions can be combined, and what to expect when these expressions are evaluated. From this perspective, C types are unexpressive (barely above assembly language), Java’s much better, OCaml, and Haskell better still, and Coq and other dependently-typed languages are perhaps the most expressive of all.

A type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.

From this perspective, type expressivity is a static (i.e. compile time) feature only. The dynamic equivalent is a type is a tag, i.e. the runtime information about what operations a value supports, so it is impossible to prove any behaviour as impossible before running the program.

Another scale to judge a type system is how verbose it is. In C, as in Java, the type of everything has to be declared. In dynamic languages, no type is needed (or even possible). OCaml and Haskell can figure out the type of most expressions with no need for declarations (which are still useful for documentation). Scala falls somewhere between Java and OCaml. It has type inference over portions of a program.

So when it comes to Scala types (or any type system, really), I have two criteria: whether it is expressive enough to be used to enforce specific properties over portions of a program, and whether it is concise enough that using it does not become a major effort.

Scala syntax

Scala reminds me of OCaml, vaguely. The syntax is fairly concise (especially compared to Java). Scala has list comprehension (as in Python or Haskell), ranges, singletons (object), and mixins (trait).

The syntax for the definition of functions (that is, methods that return a value) is somewhat strange, as it requires an equal sign:

Function definition 
1
2
3

def my_fun(i: Int): Int = {
  return i+1
}

Procedures (methods that return nothing) only need one when they are defined as returning Unit (which is void for Scala):

Function definition 
1
2
3
4
5
6
7

def my_proc(str: String) {
  println(str)
}

def my_proc2(str: String): Unit = {
  println(str)
}

Nothing overly complex, and if I believe the error message (“warning: Detected apparent refinement of Unit; are you missing an ‘=’ sign?”), the reason for this syntax is to support other constructs. Still, I had this error a few times as I wrote my code, before I finally internalized the rule.

The rest of the syntax (as introduced today) is straightforward, and easy to get used to (at least for me).

Exercises

For a first day, the exercise was rather demanding.

Tic-Tac-Toe

My first version is, admittedly, ugly. I build a list of the possible lines (i.e. rows, columns or diagonals) in the board (as a list of pairs of indices) in lines, then in the function winner I iterate over this list and check if the positions for each pair have the same content, and if this content belong to a player or not.

For the bonus part, I use print_board, which displays a board with numbers on unused locations, and play, which asks players in turn for their move, checks whether the move is valid, whether it is a winning move, and switches between players when needed.

The play function relies on variables more than I would like, but on the other hand it is harder to model a board with no update at all.

Tic-Tac-Toe (tictactoe.scala) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

val board = Array.ofDim(3,3):Array[Array[Char]]
val lines = List(((0,0),(1,1),(2,2)), ((0,2),(1,1),(2,0))) ++ (0 to 2).flatMap((i:Int) => List(((0,i), (1,i), (2,i)), ((i,0),(i,1),(i,2))))

def get(b: Array[Array[Char]], i: (Int,Int)): Char = b(i._1)(i._2)


def winner(b: Array[Array[Char]]): Boolean = {
  lines.foreach {
    case(i1,i2,i3) =>
     if (get(b,i1) == get(b, i2) && get(b, i2) == get(b, i3)) {
       if (get(b, i1) == 'X') {
         println("Player X is the winner");
         return true
       } else if (get(b, i1) == 'O') {
         println("Player Y is the winner");
         return true
       }
     }
  }
  return false
}

def print_board(b: Array[Array[Char]]) {
  println("-----")
  for(i <- 0 to 2) {
    print('|')
    for (j <- 0 to 2) {
      val c = get(b, (i,j))
      if (c == ' ')
        print(i*3+j+1)
      else
        print(c)
    }
    println('|')
  }
  println("-----")
}


def print_board_clear(b: Array[Array[Char]]) {
  println("-----")
  b.foreach {
    line =>
      print('|')
      line.foreach {
      c => print(c)
    }
    println('|')
  }
  println("-----")
}

def init_board(b: Array[Array[Char]]) {
  for(i <- 0 to 2) {
    for(j <- 0 to 2) {
      b(i)(j) = ' '
    }
  }
}

init_board(board)

println("Test on empty board")
winner(board)

print_board(board)
board(1)(1)='X'
print_board(board)
board(0)(0)='O'
print_board(board)
board(0)(2)='X'
print_board(board)
board(0)(1)='O'
print_board(board)
board(2)(0)='X'
print_board(board)

println("After game:")
winner(board)

println("And now play:")
init_board(board)

def play(b: Array[Array[Char]]) {
  init_board(b)
  var playerX = true
  (1 to 9).foreach { i =>
    print_board(b)
    print(i + " ")
    var valid_pos = false
    while(!valid_pos) {
      if (playerX)
        print("Player X")
      else
        print("Player O")
      println(" move:")
      val ln = readLine().toInt
      val i = (ln -1 ) / 3
      val j = (ln - 1) % 3
      if (b(i)(j) != ' ')
        println("Invalid position. Try again")
      else {
        if (playerX)
          b(i)(j) = 'X'
        else
          b(i)(j) = 'O'

        valid_pos = true
      }
    }

    playerX = !playerX

    if(winner(b))
      return

  }

  println("Draw!")
}

play(board)

When running it, it will first test the code by playing a predefined game. Then the bonus code is run, and an interactive game can be tried:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

$ scala tictactoe.scala 
Test on empty board
-----
|123|
|456|
|789|
-----
-----
|123|
|4X6|
|789|
-----
-----
|O23|
|4X6|
|789|
-----
-----
|O2X|
|4X6|
|789|
-----
-----
|OOX|
|4X6|
|789|
-----
-----
|OOX|
|4X6|
|X89|
-----
After game:
Player X is the winner
And now play:
-----
|123|
|456|
|789|
-----
1 Player X move:
5
-----
|123|
|4X6|
|789|
-----
2 Player O move:
1
-----
|O23|
|4X6|
|789|
-----
3 Player X move:
2
-----
|OX3|
|4X6|
|789|
-----
4 Player O move:
4
-----
|OX3|
|OX6|
|789|
-----
5 Player X move:
8
Player X is the winner

The interactive code is not great (see below for an improvement); especially a draw

Tic-Tac-Toe with class

A second version, slightly cleaned up (but presumably still ugly), this time in a class. Only one variable remains (the board); everything else is immutable.

Tic-Tac-Toe with class (tictactoe_class.scala) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

class TicTacToe() {
  val players = List("O", "X")
  val lines = List(((0,0),(1,1),(2,2)), ((0,2),(1,1),(2,0))) ++ (0 to 2).flatMap((i:Int) => List(((0,i), (1,i), (2,i)), ((i,0),(i,1),(i,2))))

  val board = Array.ofDim(3,3):Array[Array[Char]]
  init_board()

  def get(i: (Int,Int)): Char = board(i._1)(i._2)

  def init_board() {
    for(i <- 0 to 2) {
      for(j <- 0 to 2) {
        board(i)(j) = ' '
      }
    }
  }

  def isWinner(): Boolean = {
    lines.foreach {
      case(i1,i2,i3) =>
        if (get(i1) == get(i2) && get(i2) == get(i3)) {
          if (get(i1) != ' ') {
            return true
          }
        }
    }
    return false
  }

  def print_board_with_num() {
    println("-----")
    for(i <- 0 to 2) {
      print('|')
      for (j <- 0 to 2) {
        val c = get((i,j))
        if (c == ' ')
          print(i*3+j+1)
        else
          print(c)
      }
      println('|')
    }
    println("-----")
  }

  def play() {
    (1 to 9).foreach { move =>
      if (play_one_move(players(move % 2)))
        return
    }

    println("Draw!")
  }

  def play_one_move(player: String): Boolean = {
    print_board_with_num()
    val (i, j) = get_move(player)
    board(i)(j) = player(0)
    if (isWinner) {
      println("Player " + player + " won!")
      return true
    }

    return false
  }

  def get_move(player: String): (Int, Int) = {
    while(true) {
      print("Player " + player)
      print(" move: ")
      val ln = readLine().toInt
      val i = (ln -1 ) / 3
      val j = (ln - 1) % 3
      if (board(i)(j) != ' ')
        println("Invalid position. Try again")
      else
        return (i,j)
    }
    return (-1,-1)                      // actually, can't happen but compiler doesn't know
  }
}

val game = new TicTacToe
game.play()

It still handles normal victory:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

$ scala  tictactoe_class.scala 
-----
|123|
|456|
|789|
-----
Player X move: 5
-----
|123|
|4X6|
|789|
-----
Player O move: 1
-----
|O23|
|4X6|
|789|
-----
Player X move: 2
-----
|OX3|
|4X6|
|789|
-----
Player O move: 4
-----
|OX3|
|OX6|
|789|
-----
Player X move: 8
Player X won!

as well as the more common case of draw:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

$ scala  tictactoe_class.scala 
-----
|123|
|456|
|789|
-----
Player X move: 5
-----
|123|
|4X6|
|789|
-----
Player O move: 1
-----
|O23|
|4X6|
|789|
-----
Player X move: 2
-----
|OX3|
|4X6|
|789|
-----
Player O move: 8
-----
|OX3|
|4X6|
|7O9|
-----
Player X move: 3
-----
|OXX|
|4X6|
|7O9|
-----
Player O move: 7
-----
|OXX|
|4X6|
|OO9|
-----
Player X move: 4
-----
|OXX|
|XX6|
|OO9|
-----
Player O move: 6
-----
|OXX|
|XXO|
|OO9|
-----
Player X move: 9
Draw!

Wrapping Up Day 1

Scala seems easy enough to get started with. The syntax is readable; the semantic close enough to Java’s (and other mainstream languages) that there is little surprise.

Comments