Setting up Raspberry Pi with iRobot Create3

I recently decided to change my robotics course to use the iRobot Create3 educational robot. There are a number of reasons for this decision:

• The excellent Lego Mindstorms EV3 robot has reached its product end-of-life.
• The Lego Mindstorms Robot Inventor, in my experience, was a largely inferior robot in comparison.
• Even the Robot Inventor has been canceled - Lego seems to be getting out of the educational robot business entirely.
• The iRobot Create3 is comparably priced to the Mindstorms robots.
• The iRobot Create3 has a good path to student professional development due to the ability to control it using ROS2.
• I was able to obtain sufficient internal funding for this purpose.

The robots work pretty well using the Python Playground. The playground is a web-based Python IDE that connects to a robot via Bluetooth. It works really well as long as one is using the built-in Create3 sensors. 

Particularly exciting with the Create3 is the ability to control it using ROS2. This enables the integration of other sensors, including computer vision, as well as access to a large number of ROS2 modules that incorporate a variety of robot control algorithms. 

The best-supported operating system for ROS2 is Ubuntu Linux. A Raspberry Pi running Ubuntu Linux riding aboard the Create3 can be both powered by the Create3 as well as control it via ROS2 using a single USB-C cable. 

Setting up the Raspberry Pi for this purpose is a little tricky. The instructions provided by iRobot are very helpful, but there are a few missing details that I will supply here:

• In their instructions, they suggest installing Ubuntu Server. I personally am using Ubuntu Desktop - for experimenting with computer vision algorithms, being able to open desktop windows is essential, and with Remote Desktop it has never been easier.
• There are three system files to modify to get the wired USB-C connection to work mentioned in Steps 6-8: 
• The file to modify in Step 6 is /boot/firmware/config.txt. 
• The file to modify in Step 7 is /boot/firmware/cmdline.txt.
• The file to modify in Step 8 is /etc/netplan/01-network-manager-all.yaml. In addition to the file contents provided, you'll need to add the ethernets and usb0 headers, as I learned from this very helpful forum thread.
• In Step 12, right before running sudo apt install -y ros-humble-desktop, run sudo apt upgrade. This is suggested on the ROS2 installation page.
• To access the Raspberry Pi remotely, I use ssh. To set up ssh, use sudo apt install openssh-server. 
• Be sure to reboot the Raspberry Pi after setting up everything. 
• Also make sure to set the USB/Bluetooth toggle to USB (on the left).
• If ros2 topic list doesn't show anything beyond /parameter_events and /rosout after a few attempts, use ping 192.168.186.2 to see if there is a live wired connection to the robot. If there is, you'll need to reboot the robot. 
• Press the two small buttons simultaneously until the blue ring appears to set up the robot's access point. 
• Then navigate to 192.168.10.1. 
• From Applications, select Reboot Robot. It will take a few minutes.
• Once it chimes, try ros2 daemon stop && ros2 topic list && ros2 topic list. You should see your robot's topics at this point.

To set up OpenCV for use with a webcam:

• sudo apt install python3-pip
• pip3 install opencv-python
• sudo chmod 666 /dev/video0
• Without adding read/write permission to the camera, it will be necessary to run all OpenCV scripts using sudo. 

To view OpenCV windows, follow the instructions at the link to enable Remote Desktop. 

Running Rust and Flutter on a Kindle Fire 7

 Due to my strong interest in both Rust and mobile apps, I've been learning to use the flutter_rust_bridge package to build mobile apps using Rust and Flutter. They have a pretty clever example in their user guide in which the Rust code generates a Mandelbrot set which is rendered in the Flutter app. I wanted to try it out on an Android device. For development purposes, I'm using a Kindle Fire 7.

Unfortunately, their instructions are a bit cryptic, and in some places not entirely correct for the Kindle Fire 7 or for building on Windows. Here is what I had to do to get it working:

• I cloned their GitHub repo as instructed. If you use an IDE, I suggest opening it up in Android Studio.
• In the CI Workflow, I examined the flutter_android_test section. The bullets below described what I used or had to adapt.
• I had installed NDK some time ago. The instructions there are for a Unix platform. For Windows, Android provides a useful guide. I think this is what I did, but I honestly don't remember for sure.
• I already had Rust and Flutter installed. 
• I next installed the cargo-ndk program: cargo install cargo-ndk
• Here is where it was necessary to diverge from their instructions. The Kindle Fire 7 uses an ARM Cortex A7 CPU. So to target that CPU, I typed: rustup target add armv7-linux-androideabi in the rust subdirectory. This downloads the necessary files for rustc to cross-compile to that specific Android architecture.
• Note that, other than disk space, there is no particular drawback to including as many distinct Android targets as you'd like. Each one you compile will be included in the APK, and at runtime it will try to select the correct .so file for the architecture on which it is running. 
• At this point, I was ready to compile: cargo ndk -t armv7-linux-androideabi -o ..\android\app\src\main\jniLibs build
• Having completed the above setup, flutter run built the APK, uploaded it to my device, and executed it perfectly.

I realized what the problem was after finding this answer on StackOverflow. I added my own answer as well, then wrote this blog post to add a few more details for any other Android Rust enthusiasts out there!

Socket Programming in Dart and Flutter

Much of the utility of mobile device apps comes from their ability to connect to other devices over a computer network. All modern operating systems for all network-enabled computing devices provide an important abstraction for making these connections: the TCP Socket. Each language, in turn, provides its own mechanisms for creating and using sockets to communicate.

Future, Async, Await

One of the trickiest issues involving sockets is timing. That is, the app probably has other things it can be doing while waiting for a message over a socket. In Flutter, there are three interrelated language constructs we use to manage timing:

• Future objects
• The async keyword
• The await keyword

Any function in Dart can be labeled async. Every function labeled async returns a Future object immediately. The function then executes asynchronously with respect to the calling code. 

There are several ways in which the caller can interact with the returned Future object. The .then() method sets up a callback function to execute once the async function has completed successfully. The .catchError() method sets up a callback function to execute in the event that the async function throws an exception. And the .whenComplete() method's callback executes whenever the async function completes, error or not. These three methods can be thought of as analogous to try, catch, and finally, respectively.

Within an async function itself, it is pretty common to call another async function. In that case, the most common way to interact with the Future returned by the called function is to use the await keyword to pause the caller until the callee's Future completes. 

What works really well with this arrangement is that we can handle blocking communication without any explicit multithreading. Any networking code that blocks goes into an async function. 

Listening for Incoming Connections

The following examples come from a peer-to-peer text messenger app I wrote. Here is a code segment for setting up a server socket:

const int ourPort = 8888;

Future<void> _setupServer() async {
  try {
    ServerSocket server =
      await ServerSocket.bind(InternetAddress.anyIPv4, ourPort);
    server.listen(_listenToSocket); // StreamSubscription<Socket>
  } on SocketException catch (e) {
    _sendController.text = e.message;
  }
}

As _setupServer() is an async method, it needs to return a Future. Since it does not return any concrete values, it returns a Future<void>. It uses await to pause until it has acquired a ServerSocket instance. It then instructs the ServerSocket object to use _listenToSocket() as its callback by using the .listen() method. That method makes _listenToSocket()a subscriber to the ServerSocket. 

void _listenToSocket(Socket socket) {
  socket.listen((data) {
    setState(() {
      _handleIncomingMessage(socket.remoteAddress.address, data);
    });
  });
}

Within _listenToSocket(), there is no need for asynchronous code. Every time the ServerSocket receives an incoming connection, it executes _listenToSocket() and passes in the Socket it creates to communicate with the incoming connection. The _listenToSocket() method, in turn, listens for an incoming message from that socket. Once it arrives, it places the message on the user interface for the user to read. 

Because async is implemented behind-the-scenes with concurrent multithreading, data race conditions are a risk. In this program, the data that is shared between the implicit threads is all part of the user interface, represented by the _MyHomePageState class, of which _listenToSocket() is a method. As _MyHomePageState inherits from the State class, it inherits the .setState() method for updating the user interface. Each call to .setState() places the code passed to it in the UI event queue. The code passed through .setState() is thus effectively protected from data races on the UI state.

Sending Outgoing Messages

The app maintains a "friend" list of devices with whom the user can communicate. It retains the IP address, a nickname, and a message history with each friend. This data is encapsulated in the Friend class:

import 'package:mutex/mutex.dart';
final m = Mutex();

class Friend {
  String _ipAddr;
  String _name;
  List<Message> _messages;

  Friend(this._ipAddr, this._name) {
    _messages = [];
  }

  Future<void> send(String message) async {
    Socket socket = await Socket.connect(_ipAddr, ourPort);
    socket.write(message);
    socket.close();
    await _add_message("Me", message);
  }

  Future<void> receive(String message) async {
    return _add_message(_name, message);
  }

  Future<void> _add_message(String name, String message) async {
    await m.protect(() async => _messages.add(Message(name, message)));
  }
}

When the user sends a message to the specified Friend, the .send() method pauses via await while awaiting the acknowledgement of the connection and the creation of a Socket. The message history is stored in the _messages instance variable. Because messages can be appended to that list both when sent and received, concurrent data races are possible. To avert this issue, we use the mutex package. The .protect() method treats its code parameter as an atomic critical section. By using await, we can block until the mutex is free to allow the critical section to enter.

Review of Key Ideas

To write a TCP socket app using Flutter, it is important to understand the following key ideas:

• Concurrency via Future, async, and await.
• Subscribing callback code using .listen().

Serialization with JSON in Dart

Whenever one needs to package up an object and send it over a network or save it to a file, one needs serialization. This post is a brief overview and example of how do to so using the Dart language. 

A de facto standard serialization language that has emerged in recent years is JSON, the JavaScript Object Notation. The Dart language has adapted it as its own serialization standard, and it is the approach that we will employ here. 

The appeal and utility of JSON comes in how it nicely mirrors the structure of an object definition. Basic values (e.g. strings, numbers) are represented as strings. Sequences of values are also representable. Most pertinent to representing objects, each object is represented by a dictionary. The keys in the dictionary are the names of the object's instance variables, and the values associated with each key are in turn represented in JSON. Constructing a JSON representation of an object, then, is a recursive process in which one creates a dictionary by creating an entry for each instance variable. 

Here is a simple Dart class representing a User with two strings: a name and title. It creates a JSON object by returning a Dart Map containing those variables and their values. It rebuilds a User object from a JSON object by looking up the instance variable values from the JSON map and assigning them accordingly.

class User {
  String _name;
  String _title;

  User(this._name, this._title);

  bool operator==(Object other) =>
      other is User && other.name == name && other.title == title;

  String get name => _name;
  String get title => _title;

  Map<String,dynamic> toJson() => {
    'name': _name,
    'title': _title,
  };

  User.fromJson(Map<String, dynamic> json)
    : _name = json['name'], _title = json['title'];
}

The Map object containing the JSON representation has a value type of dynamic to avoid overdetermining the data types of the instance variables.

This next class contains a User object, and helps illustrate how JSON can be built recursively:

class UserStampedMessage {
  String _message;
  User _user;

  UserStampedMessage(this._message, this._user);

  bool operator==(Object other) =>
      other is UserStampedMessage && other.message == message && other.user == user;

  String get message => _message;
  User get user => _user;

  Map<String, dynamic> toJson() => {
    'message': _message,
    'user': _user.toJson()
  };

  UserStampedMessage.fromJson(Map<String, dynamic> json)
    : _message = json['message'], _user = User.fromJson(json['user']);
}

A UserStampedMessage contains a message and an associated user. When converting to JSON, the value for the User object in the returned map is itself another JSON object. When rebuilding the object from JSON, the fromJson method for the User class is invoked to rebuild the instance variable's value.

To send a UserStampedMessage over a network, then, involves the following steps:

• Convert the object to JSON.
• Convert the JSON to a string (use the jsonEncode() function from the dart:convert package).
• Send the string into a socket.

Retrieving a UserStampedMessage from a socket requires the following complementary steps:

• The value coming from the socket will be a Uint8List (i.e., a byte sequence). Use String.fromCharCodes() to convert it to a string.
• Convert the string into a JSON map using the jsonDecode() function from the dart:convert package.
• Rebuild the object from the JSON map using the fromJson method.

The following code fragment shows the encoding process:

    UserStampedMessage msg = UserStampedMessage("This is a test", User("Gabriel Ferrer", "Professor"));
    Map<String, dynamic> msgJson = msg.toJson();
    String msgStr = jsonEncode(msgJson);
    // Send over a socket, save to a file, or whatever else you have in mind...

Here are the pieces assembled for the decoding process:

    String msgStr = /* retrieve from socket, file, or wherever... */;
    Map<String, dynamic> decodedMap = jsonDecode(msgStr);
    UserStampedMessage recovered = UserStampedMessage.fromJson(decodedMap);

Happy coding!

Getting Started with Dart and Flutter

 I find the Flutter framework for mobile app development to be appealing and exciting for several reasons:

• A common source code base can be used to build both an Android and iPhone app.
• While an app is running, you can change the source code, and the app's behavior will change while it is still running, even retaining the state of its objects.
• The layout of widgets is straightforward, with a strong flavor of "trust the platform". It rewards figuring out the right relative arrangements of the widgets without trying to micromanage them.
• Related to this, Flutter builds its widgets in a lightweight manner. All it uses from the underlying platform is the ability to draw pixels. This, in turn, helps avoid the Android nightmare of having to use old versions of the platform on older devices.

The Dart language that is used in the Flutter framework is a straightforward object-oriented language that should pose no difficulties for anyone with experience with languages such as Java and C#.

Hello, World!

I have been using Android Studio to build Flutter apps. When you create a new Flutter project, the "Hello World" app it generates is a simple counter, defining one function and three classes as shown below:

import 'package:flutter/material.dart';

void main() {
  runApp(MyApp());
}

This program starts executing in the main() function. It calls runApp() with a newly created object of the MyApp class:

class MyApp extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'Flutter Demo',
      theme: ThemeData(
        primarySwatch: Colors.blue,
        visualDensity: VisualDensity.adaptivePlatformDensity,
      ),
      home: MyHomePage(title: 'Flutter Demo Home Page'),
    );
  }
}

The architecture of a Flutter app has a StatelessWidget at its root, to organize the basic layout. Its stateless nature is implemented by the fact that, under typical circumstances, its build() method is only called when it is created, and it really doesn't do anything other than answer calls to its build() method. 

The actual layout, then, is determined by the Widget returned by the build() method. In this program, that Widget is a MaterialApp widget, which is easily configured as shown by specifying a title, a theme, and a home. The title is simply a short string used as the name of the app. The theme describes the app's look and feel. The primary swatch is the default color used for app components. The visual density describes how densely components should be laid out. Specifying adaptive platform density basically says, "let the platform that this is running on make the decision." Finally, the home has a constructor for an object that will be the app's "home page" or starting point. In this case, it is an object of the MyHomePage class:

class MyHomePage extends StatefulWidget {
  MyHomePage({Key key, this.title}) : super(key: key);

  final String title;

  @override
  _MyHomePageState createState() => _MyHomePageState();
}

Just as StatelessWidget.build() is called when a StatelessWidget is created, StatefulWidget.createState() is called when a StatefulWidget is created. The resulting State object will mutate as needed in response to the pertinent system inputs. Much as with the StatelessWidget, there really isn't much to a StatefulWidgetother than the createState() method. The real action is in the State object, as we see next:

class _MyHomePageState extends State<MyHomePage> {
  int _counter = 0;

  void _incrementCounter() {
    setState(() {
      _counter++;
    });
  }

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: Text(widget.title),
      ),
      body: Center(
        child: Column(
          mainAxisAlignment: MainAxisAlignment.center,
          children: <Widget>[
            Text(
              'You have pushed the button this many times:',
            ),
            Text(
              '$_counter',
              style: Theme.of(context).textTheme.headline4,
            ),
          ],
        ),
      ),
      floatingActionButton: FloatingActionButton(
        onPressed: _incrementCounter,
        tooltip: 'Increment',
        child: Icon(Icons.add),
      ), 
    );
  }
}

There are a number of important observations to make about the _MyHomePageState class:

• Dart does not include public or private keywords; instead, any class or instance variable name that starts with an underscore ("_") is private. So the _MyHomePageState class, its _counter instance variable and its _incrementCounter() method are all private.
• Calling State.setState() places a call to this State object's build() method on the scheduler's agenda. The build() method returns a Widget that should reflect the new state of the object. It follows that since build() is called for every state update, it is important to make sure the widget doesn't take too long to generate.
• In this specific case, the build() method creates a Scaffold widget containing a couple of Text widgets in its body as well as a FloatingActionButton. When the latter button is pressed, the _incrementCounter() method is called, which in turn calls setState() and regenerates the widget once again. 
• What is nice about the Scaffold widget is that it provides the app with an aesthetically appealing default appearance. The "main action" so to speak goes into the body. In this case, the body is a Center widget, which centers its contents. In turn, it contains a Column widget, instantiated with an array of widgets that are contained in the column.

Math Quizzer

Having examined this app in some detail, we will now use it as the basis for creating an app with slightly richer behavior. This app will generate randomized addition problems, the user will input answers using a text field, and the app will then display the total number of correct and incorrect answers received. 

Adding this new functionality only requires changing the _MyHomePageState class. The new version is as follows:

class _MyHomePageState extends State<MyHomePage> {
  int _correct = 0;
  int _incorrect = 0;
  int _x = 0;
  int _y = 0;
  Random _rng = new Random();
  TextEditingController _controller;

  void initState() {
    super.initState();
    _controller = TextEditingController();
    _reset_nums();
  }

  void dispose() {
    _controller.dispose();
    super.dispose();
  }

  void _reset_nums() {
    _x = _rng.nextInt(12) + 1;
    _y = _rng.nextInt(12) + 1;
  }

  void _check(String answer) {
    try {
      var target = int.parse(answer);
      setState(() {
        int total = _x + _y;
        if (total == target) {
          _correct += 1;
        } else {
          _incorrect += 1;
        }
        _reset_nums();
      });
    } on FormatException {

    }
  }

  @override
  Widget build(BuildContext context) {
    TextStyle _ts = Theme.of(context).textTheme.headline4;

    return Scaffold(
      appBar: AppBar(
        title: Text(widget.title),
      ),
      body: Center(
        child: Column (
          mainAxisAlignment: MainAxisAlignment.center,
          children: <Widget>[
            Row (
              mainAxisAlignment: MainAxisAlignment.center,
              children: <Widget>[
                Text('$_x + $_y = ', style: _ts),
                SizedBox(width: 100, child: TextField(controller: _controller,style: _ts,
                    onSubmitted: (String value) {_check(value); _controller.clear();})),
              ],),
            Text(
              'Correct: $_correct',style: _ts,
            ),
            Text(
              'Incorrect: $_incorrect',style: _ts,
            )
            ],
        ),
      ),
    );
  }
}

Instead of tracking a single counter value, the app now tracks four different values: the two addends, the number of incorrect answers, and the number of correct answers. It also has a random-number generating object as part of its state. (Be sure to import 'dart:math'; to use it.) 

A More Sophisticated Math Quizzer

This is either at or past the limit of application complexity that ought to be embedded in the user interface code. I have further refined the program to better demonstrate this separation. The full implementation is available on GitHub. 

Data Structures

Enumerations are relatively primitive in Dart. Unlike in Java, one cannot attach methods or data to them. I decided to handle this by using a Map (a Dart dictionary) and a custom object containing the state I desired:

enum Op {
  plus,
  minus,
  times,
  divide
}

class OpData {
  int Function(int,int) _op;
  Op _inverse;
  String _symbol;

  OpData(this._op, this._inverse, this._symbol);

  int Function(int,int) get op => _op;
  Op get inverse => _inverse;
  String get symbol => _symbol;
}

Map<Op,OpData> opData = {
  Op.plus: OpData((a, b) => a + b, Op.minus, "+"),
  Op.minus: OpData((a, b) => a - b, Op.plus, "-"),
  Op.times: OpData((a, b) => a * b, Op.divide, "x"),
  Op.divide: OpData((a, b) => a ~/ b, Op.times, "/")
};

This enum, Op, represents the four different arithmetic operators employed in a math quiz. (It is the custom in Dart to use lower-case letters for enum values.) The OpData class contains the three elements that we need to represent each Op: the calculation it makes, its inverse, and a symbol to represent it textually. The calculation is represented using a Function object. The data type of a function object is its return type, the keyword Function, and the types of its parameters. Class members whose names start with an underscore are private. The paramaters of a constructor can be designated with this.member to auto-initialize the specified member with the specified parameter. The get keyword denotes a getter method. It is invoked without parentheses or parameters to yield a non-mutable attribute.

Next we examine an ArithmeticProblem, which combines an Op with two operands to represent a problem for a student to solve:

class ArithmeticProblem {
  int _x;
  Op _op;
  int _y;
  int _result;
  int _hash;
  bool _valid = true;

  ArithmeticProblem(this._x, this._op, this._y) {
    _valid = _y != 0 || _op != Op.divide;
    if (_valid) {
      _result = opData[_op].op(_x, _y);
    }
    _hash = toString().hashCode;
  }

  ArithmeticProblem inverse() => ArithmeticProblem(_result, opData[_op].inverse, _y);

  int get answer => _result;

  bool get valid => _valid;

  bool operator ==(o) => o is ArithmeticProblem && _x == o._x && _y == o._y && _op == o._op;

  int get hashCode => _hash;

  String toString() {
    return "$_x ${opData[_op].symbol} $_y";
  }
}

The opData Map defined earlier is employed throughout the implementation of the ArithmeticProblem class. Aside from the operands and operator, each instance also includes its result, its hash code, and whether or not it is a valid problem. (A problem is invalid if there is a division by zero.) The constructor directly initializes the operands and operator, and calculates the validity, the result, and the hash code, which are then employed by the other methods as needed.

A Quiz contains a bunch of ArithmeticProblem objects as well as a random number generator. Each Quiz contains all possible problems for the given operator and the given range of operands. These problems are randomly permuted. Any incorrectly answered problems are cycled back into the problem rotation. Once all problems have been answered correctly, the Quiz is considered complete.

enum Outcome {
  correct,
  incorrect
}

class Quiz {
  List<ArithmeticProblem> _problems = List();
  List<ArithmeticProblem> _incorrect = List();
  Random _random;

  Quiz(Op op, int max, this._random) {
      for (int x = 0; x <= max; x++) {
        for (int y = 0; y <= max; y++) {
          _addValidProblem(_makeFrom(x, y, op));
        }
      }
      _problems.shuffle(_random);
  }

  void _addValidProblem(ArithmeticProblem p) {
    if (p.valid) {
      _problems.add(p);
    }
  }

  ArithmeticProblem _makeFrom(int x, int y, Op op) {
    if (op == Op.minus || op == Op.divide) {
      return ArithmeticProblem(x, opData[op].inverse, y).inverse();
    } else {
      return ArithmeticProblem(x, op, y);
    }
  }

  bool finished() => _problems.isEmpty && _incorrect.isEmpty;

  ArithmeticProblem current() {
    if (_problems.isEmpty) {
      _problems = _incorrect;
      _incorrect = List();
      _problems.shuffle(_random);
    }
    return _problems.last;
  }

  Outcome enterResponse(int response) {
    ArithmeticProblem p = _problems.removeLast();
    if (p.answer == response) {
      return Outcome.correct;
    } else {
      _incorrect.add(p);
      return Outcome.incorrect;
    }
  }

  String toString() => 'Problems:${_problems.toString()}; Incorrect:${_incorrect.toString()}';
}

The enum Outcome is introduced to enable a Quiz to report whether a given answer is correct. If it is not, the problem is added to the incorrect problems list. Once all problems have been asked, remaining incorrect problems are shuffled back into the list. Subtraction and division problems are generated by inverting addition and multiplication problems. This avoids issues of subtraction problems with negative answers and division problems with non-integer answers, both of which were beyond the scope of what was envisioned for this app.

Unit Testing

I wrote the unit tests below for these data structures. They are straightforward. The basicTest ensures that the specified operator is evaluated and inverted correctly. The testQuiz runs a scenario of quiz problems. It verifies whether the answers given in a list of answers are classified correctly as correct or incorrect. It runs the quiz through to completion.

import 'dart:math';

import 'package:flutter_test/flutter_test.dart';
import 'package:simple_math/problems.dart';

void main() {
  test('2 + 3', () {
    basicTest(Op.plus, 2, 3, 5);
  });

  test('2 * 3', () {
    basicTest(Op.times, 2, 3, 6);
  });

  test('Problems, addition', () {
    testQuiz(Op.plus, [1, 1, 2, 2, 2, 4, 4, 3, 0, 3],
        [Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.incorrect, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct]);
  });

  test('Problems, subtraction', () {
    testQuiz(Op.minus, [1, 0, 2, 0, 2, 1, 2, 2, 0, 1],
        [Outcome.correct, Outcome.correct, Outcome.incorrect, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct]);
  });

  test('Problems, multiplication', () {
    testQuiz(Op.times, [0, 0, 1, 0, 0, 2, 4, 2, 0], [Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct]);
  });

  test('Problems, division', () {
    testQuiz(Op.divide, [1, 2, 0, 1, 2, 0], [Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct, Outcome.correct]);
  });
}

void basicTest(Op op, int operand1, int operand2, int expectedValue) {
  ArithmeticProblem p1 = ArithmeticProblem(operand1, op, operand2);
  expect(p1.answer, expectedValue);
  expect(ArithmeticProblem(expectedValue, opData[op].inverse, operand2), p1.inverse());
  expect(p1.inverse().answer, operand1);
  expect(p1.inverse().inverse(), p1);
}

void testQuiz(Op op, List<int> answers, List<Outcome> expected) {
  Quiz probs = Quiz(op, 2, new Random(2));
  print("$probs");
  for (var i = 0; i < answers.length; i++) {
    expect(probs.enterResponse(answers[i]), expected[i]);
  }
  expect(probs.finished(), true);
}

Dart's unit testing infrastructure is straightforward, albeit a bit different in layout than the various xUnit frameworks. A single main() function calls all the tests. Each test is run by a call to the test function, which supplies the test code in a Function object. Within the test code, each assertion is tested using an expect function call. The expression being evaluated is the first expect parameter, and the target value is the second parameter.

User Interface Code

Flutter UI code can easily get out of hand if it is not properly decomposed into functions. I sought to do so for this app to keep the code intelligible. I will begin by describing the state data for the _MyHomePageState class.

  Widget Function() _screen;
  Quiz _problems;
  Random _rng = new Random();
  TextEditingController _controller;
  TextStyle _ts;
  Op _selected = Op.plus;
  bool _lastCorrect = true;
  int _lastMax = 12;

  void initState() {
    super.initState();
    _resetController();
    _screen = setup;
  }

  void _resetController() {
    _controller = TextEditingController(text: '$_lastMax');
  }

  void dispose() {
    _controller.dispose();
    super.dispose();
  }

The _screen object is a reference to the Function that should be employed for rendering the current app screen. I found this to be an elegant way to transition between screens - just change _screen to the appropriate function.

The _problems and _rng objects are used for the application state. The _controller and _ts objects simplify the use of certain UI components. The _selected and _lastMax objects represent the user's inputs at the start screen, and the _lastCorrect object is used to give the user feedback based on whether the last answer was correct.

The initState() method is where any object setup that is not suitable for immediate object initialization occurs. In this case, setting up the controller and setting the initial screen are both facilitated by being included here. The dispose method is unfortunately necessary for cleaning up resource usage from the _controller object.

The functions below represent the three different screens the app displays: a start screen, a problem-answering screen, and a congratulatory concluding screen.

  @override
  Widget build(BuildContext context) {
    _ts = Theme.of(context).textTheme.headline4;
    return Scaffold(
        appBar: AppBar(title: Text(widget.title)), 
        backgroundColor: pickBackground(),
        body: Center(child: _screen()));
  }
  
  Widget setup() {
    return Column (
      mainAxisAlignment: MainAxisAlignment.center,
      children: <Widget>[
        radio("+", Op.plus),
        radio("-", Op.minus),
        radio("x", Op.times),
        radio("/", Op.divide),
        numericalEntry(200, "Maximum", (String value) { }),
        RaisedButton(child: Text("Start", style: _ts), onPressed: () {_start(_controller.text);}),
      ],
    );
  }

  Widget quizScreen() {
    _controller.clear();
    return Column (
      mainAxisAlignment: MainAxisAlignment.center,
      children: <Widget>[
        Row (
          mainAxisAlignment: MainAxisAlignment.center,
          children: <Widget>[
            Text("${_problems.current()} = ", style: _ts),
            numericalEntry(200, "answer", _check),
          ],),
        _restartButton()
      ],
    );
  }
  
  Widget done() {
    return Column (
      mainAxisAlignment: MainAxisAlignment.center,
      children: <Widget>[
        Text("Congratulations! All answers correct.", style: _ts),
        _restartButton(),
      ],
    );
  }
    
  Color pickBackground() {
    if (_screen == quizScreen) {
      return _lastCorrect ? Colors.green : Colors.red;
    } else {
      return Colors.white;
    }
  } 

The build method shows how the _screen object is used to redirect to the current screen. (The text style is set up there due to access to the BuildContext object.) All of the screens in this app have the same basic framing, which is given in build; the role of the _screen object is to plug in a child Widget describing the elements specific to that screen. The pickBackground method determines the background color to be displayed. During a quiz, it depends on whether the last answer was correct. Otherwise, it is simply white, which given the theming would not have been otherwise necessary to specify.

The setup method lays out the startup screen. The user picks one of four radio buttons to specify the operator, specifies a maximum operand value, and when ready starts the quiz. Note that in most cases, the pertinent widgets are actually created by helper functions. This makes the logic of the screen clear and easy to follow. Given the significant boilerplate code associated with each widget, it greatly minimizes code replication as well.

The quizScreen method is the heart of the app. The column contains a row in which the user is presented the problem and given the opportunity to answer. Below that is a button for restarting the app. The string describing the current problem makes nice use of Dart's format string syntax. A $ introduces a variable; a ${} allows the insertion of a full expression.

Finally, the done method congratulates the user on completing the quiz, and uses the same _restartButton method to create a path back to the opening screen. This and the other helper methods are shown below.

  Widget numericalEntry(double width, String label, void Function(String) onSubmitted) {
    return SizedBox(width: width, child: TextField(controller: _controller, style: _ts,
      keyboardType: TextInputType.number, onSubmitted: onSubmitted,
        decoration: InputDecoration(labelText: label)));
  }

  Widget radio(String label, Op value) {
    return ListTile( title: Text(label, style: _ts),
        leading: Radio(groupValue: _selected, value: value, onChanged: (o) {setState(() {
          _selected = value;});}),
        );
  }  
  
  Widget _restartButton() {
    return RaisedButton(onPressed: _restart, child: Text("Restart", style: _ts,));
  }

The numericalEntry method creates an area that allows text entry of numerical values. The Flutter TextField is somewhat finicky; it needs to be deployed within a SizedBox (or another size-controlling widget). The InputDecoration provides a handy way to provide a hint to the user as to what is expected in the box without having to prefix it with a label. The onSubmitted object represents the event handler.

Radio buttons are very straightforward as well. The groupValue designates a variable that tracks which radio button the user has selected. It is updated in the event handler, which in this case is in-place. (The other event handlers in this app are separate functions.)

The raisedButton object is used for the restart button. Note that placing text on a button requires giving it a child widget.

Finally we have the event-handling methods:

  void _processNumberEntry(String value, void Function(int) processor) {
    try {
      processor(int.parse(value));
    } on FormatException {
      print("Threw an exception...");
    }
  } 

  void _start(String value) {
    _processNumberEntry(value, (v) { 
      setState(() {
        _lastMax = v;
        _lastCorrect = true;
        _problems = Quiz(_selected, _lastMax, _rng);
        _screen = quizScreen;
      });
    });
  }

  void _check(String answer) {
    _processNumberEntry(answer, (target) {
      setState(() {
        Outcome result = _problems.enterResponse(target);
        _lastCorrect = (result == Outcome.correct);
        if (_problems.finished()) {
          _screen = done;
        }
      });
    });
  }
    
  void _restart() {
    setState(() {
      _resetController();
      _screen = setup;
    });
  }

The _start method starts a quiz, and the _check method processes an answer. I didn't write a substantive event handler, as using the numeric entry screen should suffice to ensure that FormatException is not possible to raise. By placing the exception handling code in _processNumberEntry, if at a later time I wish to do something more substantive, I won't have to replicate it in both _start and _check. The _restart method returns to the start screen. The resetController call makes sure that the previous maximum operand value reappears on the start screen.

In all three event handlers, an update to the user interface is triggered by a call to setState. The code passed to setState is executed later by the user interface framework prior to refreshing the screen. Transitions between screens are controlled by setting the _screen object to the desired new function. In this way, _screen represents a state in a state machine that transitions based on the events that occur and the app's state.

Happy app building!

Doubly-Linked Lists Are Useless in Collections Libraries

The doubly-linked list is a ubiquitous topic in data structures courses in Computer Science curricula. It is a course I have taught many times over the course of my career as a Computer Science professor. As with most of the standard data structures covered in these courses (such as dynamic arrays, stacks, queues, heaps, singly-linked lists, hash tables, and binary search trees), doubly-linked lists routinely appear as standard collections in data structure libraries. 

Most of these standard data structures are routinely useful. I mention them here in order of the rough frequency with which I seem to employ them:

• Dynamic arrays are, by far, the most useful data structure for representing an arbitrary collection of data. They are friendly to the CPU cache, relatively conservative with memory, and enable constant-time random access.
• Hash tables enable the fastest practical implementations of unordered sets and maps, especially because (like dynamic arrays) they enable cache-friendly memory layout.
• Binary search trees enable fast implementations of totally ordered sets and maps.
• Stacks, queues, and heaps are frequently components of other algorithms, such as graph traversal and A* search algorithms.
• Singly-linked lists are foundational data structures for purely functional programming and purely functional data structures. They are also a prerequisite for understanding binary search trees.

Unlike these other data structures, however, I haven't found doubly-linked lists to be especially useful in practice. The advantages of the doubly-linked list are as follows:

1. Constant-time insertion and deletion of elements anywhere in the list, provided that an iterator is pointing to the pertinent location.
2. Constant-time insertion and deletion of elements at the start or end of the list. This is suitable for a queue or deque.
3. Constant-time splicing of two lists together. 

Its disadvantages include the following:

1. Storing each element also requires storing two pointers, making it somewhat memory-hungry.
2. Accessing an arbitrary element requires linear time.
3. Lots of tiny linked objects are unlikely to be laid out together in memory in a way that is friendly to the CPU cache.

Before discussing the first two advantages of the doubly-linked list, I want to mention that for the third advantage (splicing), it really is the most time-efficient data structure available for a sequence. Curiously, however, some collection implementations (e.g. Java) don't support this operation at all, while others (e.g. Rust, C++) do. 

That said, I have a hard time imagining a situation in which constant-time splicing is useful. I see an analogy between the movement of elements in a list splice and the amortized analysis of the movement of elements when resizing a dynamic array. Once an element is added to a list, there is likely to be a very small number of times in which it is part of a list splice. Moving it through the same number of linear-time array splices could probably be amortized. I need to think more about this, but it is the direction my intuition is moving.

Moving on from there, equally suitable (or better) for the first situation are the following:

1. The gap buffer (implementation in Rust) stores elements in an array, with values accumulating at both ends, leaving a gap in the middle. Insertions take place at a location designated by a cursor, fulfilling a role similar to that of the iterator in a doubly-linked list. Insertions to the left of the cursor accumulate at the start of the array, while insertions to the right of the cursor accumulate towards the end. When the cursor moves left, an element is transferred from the front to the back of the array. When it moves right, an element is transferred in the other direction. As with any array, the gap buffer can be resized in amortized constant time as needed.
2. The zipper is similar, except that instead of an array there are two singly-linked lists representing the sequences on each side of the cursor. This avoids the need for amortization to yield constant-time insertion and deletion without paying the memory penalty of the doubly-linked list.

Both of these approaches are much less memory-hungry than the doubly-linked list. A particular advantage of the zipper (as with any data structure based on a singly-linked list) is that it can be implemented as a purely functional data structure. 

For the second situation, a ring buffer is preferable. This is an array in which two integers point to the indices of the start and end of the sequence. This makes both insertion and deletion at both ends highly efficient. It is still constant time for random access, albeit at a significant performance penalty in comparison to a standard array. 

An arguable advantage of the doubly-linked list is that there is no need for amortization to yield constant-time performance for the target operations of insertion and deletion at the ends. I personally do not think this matters very much, for two reasons:

1. Amortized constant time postulates that occasional linear-time operations can, in effect, "spread out" their time penalty across all operations. In a real-time system, it is possible that a task might miss its deadline when the occasional expensive operation arises. I would argue, however, that a fixed-size array is preferable to either a dynamic array or a linked list in this situation. Real-time systems with constant time bounds also tend to have constant space bounds and an aversion to frequent use of the heap. Determining a suitable fixed-array size for the application leads to guaranteed constant time.
2. The dynamic resizing operations are really not very expensive in practice.

Of course, a claim like the second requires empirical verification. To that end, I implemented a simple experiment in Rust. (Note that, contrary to widely-held views about Rust's ownership system, it is perfectly possible to implement a doubly-linked list in safe Rust by using Weak pointers.) It adds a specified number of elements to both data structures at the end, then removes them all from the front. I not only recorded the total time necessary; I also recorded the maximum time used for a single operation.

Here are some results:

# items	VecDeque total (s)	VecDeque max op (s)	VecDeque fixed size total (s)	VecDeque fixed size op(s)	LinkedList total (s)	LinkedList max op (s)
100,000	0.028143	0.000203	0.028134	0.000022	0.035405	0.000089
1,000,000	0.327679	0.002232	0.314516	0.000061	0.402862	0.000277
10,000,000	2.997163	0.034366	2.966092	0.000251	3.838949	0.002055
100,000,000	32.289343	0.303334	28.891364	0.001622	47.137053	0.019145

I was actually surprised that LinkedList performed as well as it did. While it was always slower than the VecDeque, it still was within 50% or so of its performance. Unsurprisingly, preallocating sufficient space for the elements in the VecDeque resulted in by far the best performance.

What was more interesting was to see just how many items need to be in play for the linear-resizing operation to have a noticeable impact. With 100,000,000 items in play, it could represent a noticeable pause, but this is a particularly extreme situation. If this many items were to be anticipated, preallocating space is the way to go.

This isn't to say that there are no imaginable uses of the doubly-linked list - just not the kind of uses that would cause it to be featured in a collections framework. For example, using a doubly-linked list to represent the insertion order of elements in a hash table seems useful. When removing an element, we already have a pointer into the linked list handy, so the ability to remove in place in constant time really is pertinent. But notice how intrusive this is into the data structure - using an off-the-shelf linked list really isn't sufficient.

To conclude, then, there really doesn't seem to be any use for having a doubly-linked list in a collections library. Anything it can do can be done equivalently or better by another data structure. I also think it is particularly problematic to dedicate a lot of class time to a data structure that isn't really very useful. It gives students the impression that it is important, that it is used a lot, and that it matters, when it really doesn't. And this, in turn, even influences designers of collections frameworks, who in turn mislead developers into thinking that it is actually useful.

Using the trait alias: labeling collections of trait constraints in Rust

When programming in Rust, a major challenge to the DRY principle is in regard to trait constraints. Let's say, for example, that I want to create a trait for random-access sequences whose values are primitive (in Rust terms, Copy) types. Furthermore, I want to be able to sort these sequences, so my values must also be orderable. The result could look something like this:

use len_trait::Len; // I employed len-trait = "0.6.1"

pub trait VTest<T:Copy+PartialEq+PartialOrd+Sized> 
    : Index<usize,Output=T> + IndexMut<usize,Output=T> + Len {
    fn add(&mut self, t: T);

    fn swap(&mut self, i: usize, j: usize) {
        let temp: T = self[i];
        self[i] = self[j];
        self[j] = temp;
    }

    fn selection_sort(&mut self) {
        for i in 0..self.len() {
            let lowest = (i+1..self.len())
                .fold(i, |lowest, j|
                    if self[lowest] < self[j] {lowest} else {j});
            self.swap(lowest, i);
        }
    }
}

Now, in order to implement this trait, we are faced with code duplication for the constraints on the generic variable T:

impl <T:Copy+PartialEq+PartialOrd+Sized> VTest<T> for Vec<T> {
    fn add(&mut self, t: T) {
        self.push(t);
    }
}

impl <T:Copy+PartialEq+PartialOrd+Sized> VTest<T> for VecDeque<T> {
    fn add(&mut self, t: T) {
        self.push_back(t);
    }
}

When coding, the most expedient way forward is to copy-and-paste this sequence of constraints on T. From both an aesthetic and a maintenance perspective, this is a nightmare. 

Option 1: Create an empty trait

So, when faced with this, I undertook a search to determine what others had done when faced with this situation. The top search result suggested something like the following:

pub trait SimpleValue : Copy+PartialEq+PartialOrd+Sized {}

Which, in turn, enables me to write the following:

pub trait VTest<T:SimpleValue> 
    : Index<usize,Output=T> + IndexMut<usize,Output=T> + Len {
    // ...
}

impl <T:SimpleValue> VTest<T> for Vec<T> {
    // ...
}

impl <T:SimpleValue> VTest<T> for VecDeque<T> {
    // ...
}

Now that looks much better! But there is a small wrinkle. Rust won't automatically infer that, say, usize automatically implements the SimpleValue trait. So I do have to declare explicitly that it does:

impl SimpleValue for usize {}

Again, this doesn't seem that much of a price to pay. And within the scope of a single crate, it works perfectly well and solves the problem. Where we run into trouble is if we find that our new VTest trait is so successful that we want to import it from a different crate. We would, of course, import SimpleValue as well.

And actually, this works, most of the time, unless you try something like this:

impl SimpleValue for i64 {}

In response, the compiler will reply with an error message along the following lines:

error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
  --> src\lib.rs:21:5
   |
21 |     impl SimpleValue for i64 {}
   |     ^^^^^^^^^^^^^^---
   |     |             |
   |     |             `i64` is not defined in the current crate
   |     impl doesn't use only types from inside the current crate
   |
   = note: define and implement a trait or new type instead

Something that is extremely cool about the Rust compiler is its inclusion of hyperlinks to explanations of compiler errors. When we follow this particular link, we learn:

This error indicates a violation of one of Rust's orphan rules for trait implementations. The rule prohibits any implementation of a foreign trait (a trait defined in another crate) where

• the type that is implementing the trait is foreign
• all of the parameters being passed to the trait (if there are any) are also foreign.

Orphan rule? What's that? Imagine two crates, each of which implements the same foreign trait for the same foreign datatype. If someone tries to use both crates in a project, we get an ambiguity; that is, it is not clear which trait implementation we should actually use. So the Rust solution is to prohibit the implementation of a foreign trait on a foreign type in all situations, so as to prevent this error from ever occurring. This is actually allowed in the Haskell language, although it triggers a compilation warning and is widely discouraged.

This rule has proven hugely unpopular, as it prevents lots of perfectly correct code (such as the motivating situation in this post) from being compiled. One could imagine expressing a preference for which crate's trait implementation to use, but this runs into trouble when code from the other crate relies on its own version. And simply prohibiting crates from being imported together impedes code reuse. It is clear that there is no straightforward solution.

Option 2: The Trait Alias

This leads to another possible solution, the concept of the trait alias, which is really all we wanted to begin with. With a trait alias, a collection of traits can be given a name, purely local to the crate in which it is embedded. Any qualifying types that match can then implement the trait. Here is what our example looks like with trait aliases:

#![feature(trait_alias)]
pub trait Item = Copy+PartialEq+PartialOrd+Sized;

pub trait VTest<T:Item> : Index<usize, Output="T"> + IndexMut<usize, Output="T"> + Len {
    fn add(&mut self, t: T);

    fn swap(&mut self, i: usize, j: usize) {
        let temp: T = self[i];
        self[i] = self[j];
        self[j] = temp;
    }

    fn selection_sort(&mut self) {
        for i in 0..self.len() {
            let lowest = (i+1..self.len())
                .fold(i, |lowest, j|
                    if self[lowest] < self[j] {lowest} else {j});
            self.swap(lowest, i);
        }
    }
}

impl <T:Item> VTest<t> for Vec<T> {
    fn add(&mut self, t: T) {
        self.push(t);
    }
}

impl <T:Item> VTest<t> for VecDeque<T> {
    fn add(&mut self, t: T) {
        self.push_back(t);
    }
}

Currently, trait aliases are only available in nightly Rust. There is still considerable discussion about how the feature should work and what the syntax should look like, so it is not clear when the feature is going to be stabilized. In the meantime, I think this feature is so essential for ergonomic use of Rust that I am defaulting to the nightly compiler for all of my projects until this feature is stabilized.