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.

Arrays vs. Ring Buffers: A Performance Comparison in Rust

The VecDeque collection in Rust implements a double-ended queue with O(1) operations to push and pop on either end. (Other language libraries have similar data structures, such as ArrayDeque in Java.) It also provides O(1) random access to individual elements.

These ring buffers are implemented behind-the-scenes with an array and two index variables: a start and an end. For the sake of simplicity, imagine that the deque is initialized with a starting capacity of 10. Both the start and end variables could then be initialized to point at index 5. Any push to the front decreases the starting index, and any push to the back increases the ending index.

When accessing an individual element, the index is added to the starting index to determine the final array position to employ. If this sum exceeds the size of the array, it "wraps around" to the lower part of the array.

What is not obvious is the degree to which this extra addition to find the index represents a performance penalty. Documentation for the Rust Collections library states that whenever Vec and VecDeque have the same asymptotic time bounds for an operation, that the Vec will generally be faster, but no further details are provided. 

I became interested in this question because of how the constant-time double-ended push and pop operations for a VecDeque incur no asymptotic time penalty for direct random access. If the penalty is, in fact, insignificant, then maybe there is no need to use a regular Vec at all. So to satisfy my curiosity, I constructed an experiment. 

In this experiment, we create a Vec with a specified number of elements. (I used 100000 to produce the data below.) We then randomly shuffle these elements. At this point, the experiment begins. We copy these values into another Vec and then a VecDeque, and then sort them using the selection sort algorithm. While this is not a very good sorting algorithm in general, for this purpose it is ideal, as it requires a lot of random accesses that are widely spaced across the sequence being sorted. By using the same sequence of shuffled values for each data structure, the test should also be fair.

Here are the results. For each algorithm, we performed 30 trials with 100000 elements. Each trial featured a different permutation of those values.

Data Structure	Mean completion time (ms)	Standard Deviation
Vec	3238.4	205.1558
VecDeque	4813.2	213.019

It is pretty clear, then, that for random access the Vec is consistently faster than the VecDeque. In exchange for constant-time front-end pushes and pops, the VecDeque takes about 50% longer to complete each random access. It seems to me to be well worth the cost when that functionality is pertinent, but when it is not the plain Vec is strongly preferable.

Please feel free to download and experiment with my source code if you are interested.

Rust at Apple

I recently saw the following job advertisement at Apple, posted January 29, 2020. (I assume the link will eventually go away once the job is filled, but the text of the ad is what is pertinent here.)

We are seeking an experienced software engineer with a passion for computer networking and security. Be part of a small, highly skilled team building network infrastructure services at Apple. 

The Apple Cloud Traffic team provides a secure networking layer to underpin consumer-facing applications. Based on a custom implementation of IPsec, it must handle the encryption of every packet passing between servers within and across vast data centres, with minimal overhead. Custom-built secure RPC protocols manage the keying, authentication and authorization of all traffic flows. 

The performance and security of the systems we build are critical. We interface directly to low-level Linux kernel interfaces, using asynchronous I/O and threads to distribute workload. Following a very successful first foray into Rust we are migrating an established codebase from C to Rust, and building new functionality primarily in Rust.

 Here are a few aspects I would like to highlight:

• They are migrating an established codebase from C to Rust. This suggests that the well-known problems in C of insecure memory accesses and undefined behavior are impairing the stability of the system, and that the safety guarantees of Rust are expected to eliminate those problems. Code migration is a lot of work!
• They are making significant use of multithreading, another strong point of Rust. The compiler's ability to prevent race conditions in RAM will be a big advantage here.
• Overhead needs to be minimal. The high performance that Rust facilitates will be helpful here.
• The system is making direct system calls to the kernel. Again, the ability of Rust to compete with C in the low-level systems space is emphasized.

I expect we will see more and more similar advertisements as the benefits of Rust continue to become better known.

The rise of Rust

The Rust programming language has been increasing in popularity of late. I learned to program in Rust in order to teach my Spring 2017 operating systems course using the language, inspired by the work of David Evans at the University of Virginia. I was so pleased with the experience that I taught the course in Rust a second time in Spring 2019. I have also started using Rust in software development in my research program.

There are a few things I have come across recently that, I think, demonstrate the appeal of programming in Rust. The following quotes come from a Reddit thread posing the question: "Why does Rust seem to inspire people?"

It took me literally a day and a half from "I'm going to try writing my first Rust program" to "here's a working multithreaded network program with string processing that can pump out 100GB+ a day of throughput with no memory leaks or buffer overflow errors." That's nuts. I couldn't have done that in a GC'd language or C++, or at least not as quickly. The way move semantics, the borrow checker, thread spawning, and channels/atomics work is very well thought out.

I can vouch for this experience personally. In fact, writing a multithreaded web server is one of the key assignments I employ in my operating systems course. The ownership guarantees embedded in Rust's static type system make this possible.

I’m a college professor in software engineering, so I’m saturated in young people excited about tech. For the last few years, it’s been fascinating to see how excitement for Rust has gained momentum.

In our major, you tend to learn C freshman year alongside Python, Ruby, and Java. Lots of folks love C for being system-level and fast. But, pointers and malloc are brutal to learn. I witness it every year. Even if you enjoy C, everyone had a story about staying up all night debugging a segfault. I recently met with a mental health counselor who sees a lot of students in my major. Segfaults came up. Yeah. Anecdotally, C’s memory management hurts peoples’ mental health.

Then, when they take my security course and learn about buffer overflows and other memory corruption issues they start to question the wisdom of such permissive language like C and C++. It’s a phase we all go through. We all question the establishment in college.

Then when students learn about Rust, they hear about how memory allocation is safe and zero-cost abstraction. They get excited and start evangelizing to their peers. The excitement is noticeably more than other tech, which I always thought was interesting. We don’t cover it in any class (yet...), so they pick it up in their spare time.  

I’m honestly surprised that a lot of my students like Rust. (Thrilled that they are!) Its a tough language to learn. It’s got some different concepts (e.g borrowing, lifetimes) that are a big paradigm shift for them. For me, I rolled my eyes about it for like three years and just recently started learning Rust and I’m impressed.

It really is time to question the establishment. The experience of programming in Rust demonstrates that you can write bare-metal code in a language with a type system that guarantees the absence of buffer overflows and memory corruption without compromising on performance. At this point, it is arguably an ethical imperative to show our students that there is a better way.

The sad reality of our world is that everything is broken - as someone who has done security research, I can tell you that every word in that article is true, and more.

The reason why everything is broken is because there are two kinds of programming languages: the slow ones (Python, Java, Go) and the ones that lead to horrific security vulnerabilities (C, C++). We need our computers to go fast, so we use C and C++, and so everything is glitchy and broken.

Now imagine a language that breaks that mold. That is fast as C/C++ and can fully replace them, but without the security vulnerabilities. The holy grail that would lets us write code that is secure, reliable and fast all at the same time.

That's Rust.

I seriously cannot overstate how big of a deal this is. Nothing like this has ever existed before. Most thought creating such a language impossible!

This reinforces what the professor had to say, from the viewpoint of a computer security researcher. Rust is a tool that suffices to make legions of computer security problems just go away.

Five days trying to figure out a segfault. (Personal project in highschool) Gave up. Half a year later, checked it out again. Blindingly obvious after ten minutes. Even experience doesn't beat the three seconds it takes to read the rust compiler's output. Heavenly.

This quote comes from a manifestly talented and experienced developer. It is interesting to think about the useful experience this person could have developed in solving problems other than finding segmentation faults if, in his career, the compiler had been a reliable ally in avoiding these problems.

Rust is far from perfect, and sometimes feels a bit pedantic, but coding in Rust I never ever put my hands in the air and think "damn, I hate this language so much, it's so stupid", which I routinely do when using other mainstream languages.

Rust is the first language I am actually pleased to work with, and it's been years now. Tooling is great, community works well, popularity is good enough. And the language feels like it was coherently and carefully designed for humans (as opposed to: oh, you have a bug, you must be stupid or something for doing wrong things). And it is a programming language suitable even for low level systems/kernel/embedded programming, just as much for web dev, which is simply amazing.

I love the core features: ownership/borrowing, thread-safety, good type system, and miss them soo much when I can't use them in other languages. It's a very powerful force, reinforcing the appreciation of Rust.

So, everything I do in Rust ... feels joyful. I feel like you can achieve anything, and it is not even that difficult. At least the language empowers me, instead of getting in the way, like other ones.

A couple of comments:

• I boldfaced an important line above, which references the common notion that memory bugs are signs of bad programming. The Rust environment eliminates this needless hazing. 
• The second line I boldfaced reflects my own experience, but I want to include an important caution: it takes quite a bit of practice with Rust to get to the point where it is not difficult to use. The language is well-known for its steep learning curve. I would like to encourage anyone starting out with Rust to persevere until you get to that point.

The article Why Rust is the Future of Robotics also has interesting insights, most particularly the following information about embedded development:

For embedded systems, specific tools have also been developed:

• Peripheral control — There is this thing called svd2rust that can automatically generate a Rust API to access every peripherals on a micro-controller, directly from it’s SVD description. Rust is smart and it can enforce at compile time that you use peripherals as they should be. You cannot compile if you try writing to a read-only register, or read to a write-only registers. You cannot write invalid bit patterns to a register too. The SVD can define a range of valid values and Rust won’t let you go out of range.
• Ressource collision prevention— In the next version, they will introduce singletons to let Rust know when some code wants to use a peripheral already in use, for example a timer. This is a common source of problems in embedded systems were resources are limited and several devices might want to use them. It is a classic with Arduino Uno boards that only have few timers. So when you use the Servo library, you cannot use PWM on the pin 9 and 10. But the code will compile, push to the board and fail badly by producing very strange behaviours extremely hard to debug. This made many, many, Arduino users confused. With singletons, Rust can tell you at compile time if the timer is already in use, preventing users massive headaches without any runtime overhead.

That is, it turns out the ownership concept can be employed to avoid many specific hardware-utilization errors at compile time. Here is a similar comment from a Hacker News thread:

As for the borrow checker, I actually did find it useful in bare metal. But more for handling hardware resources. Different measurements require different sets of power supplies to be activated, and exclusive control over different I/Os, etc. The ownership model made it easier to ensure statically that we sequence the measurements in a way such that the different measurement routines can never reconfigure resources that are in use by a different routine.

In effect, the borrow checker is proving to be a highly configurable theorem prover for software verification!

The ownership concept also aids in code optimization. Amit Patel describes how, thanks to knowing the owner of an array, Rust code for an array copy uses 50% fewer memory accesses than the equivalent C++ code.

For those die-hard C programmers convinced that nothing can beat it, I recommend reading Learning Rust the Dangerous Way. The author's methodology is fascinating. He took a benchmark C program from the Programming Language Shootout and translated it into Rust.

An important aspect of Rust is that code can be marked unsafe, indicating that the compiler's safety guarantees won't be enforced on that block of code. This transfers the safety burden from the compiler to the programmer. It acknowledges that there are situations where the programmer really knows better than the compiler. What is great about this is that by eliminating safety checks on the smallest possible block of code, the bulk of the program still retains safety guarantees, making it easier to reason about its correctness.

This author, then, takes the C source code for the n-body problem and transliterates it into an equivalent Rust program, the entirety of which is in an unsafe block. He then gradually refines each unsafe block into safe Rust code. At the end, the only unsafe code remaining is the calls to the CPU vectorization instructions. As of this writing, the fastest program in the shootout for this problem is Rust #7, by a different author but taking the same basic approach.

The significance of this achievement is to end the belief that unsafe code is generally necessary for high performance. For the most part, except for small, specialized routines, it is not, and most (if not all) of any given program can genuinely be checked at compiler time to be safe.

Although there are not necessarily a huge number of jobs available in Rust as of yet, I suspect this is about to change very quickly. Here's one example. A student of mine was recently hired at Google, and his group was ecstatic that he learned Rust in my operating systems course. While the group does not yet have Rust in production, they are looking for an opportunity.

As talented programmers begin to insist on using Rust for the sake of its safety guarantees, I predict that companies will respond to this pressure by starting more and more projects in Rust. I expect it to be a top-10 programming language by the end of this newly inaugurated decade. I highly encourage anyone interested in these possibilities to take the time to learn to program in Rust. I think this language is one of the most important technological advances in computing from the past decade, and now is the time to embrace progress moving forward!