tag:blogger.com,1999:blog-52354230689739723622024-03-28T22:29:29.715-05:00Computing IntelligentlyObservations and commentary on robotics, AI, machine learning, and computer science (and academic life) in general.Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.comBlogger63125tag:blogger.com,1999:blog-5235423068973972362.post-20995290113454801282023-07-13T12:44:00.003-05:002023-07-15T09:30:26.689-05:00Setting up Raspberry Pi with iRobot Create3<p>I recently decided to change my robotics course to use the <a href="https://edu.irobot.com/what-we-offer/create3" target="_blank">iRobot Create3 educational robot</a>. There are a number of reasons for this decision:</p><p></p><ul style="text-align: left;"><li>The excellent Lego Mindstorms EV3 robot has reached its product end-of-life.</li><li>The Lego Mindstorms Robot Inventor, in my experience, was a largely inferior robot in comparison.</li><li>Even the Robot Inventor has been canceled - Lego seems to be getting out of the educational robot business entirely.</li><li>The iRobot Create3 is comparably priced to the Mindstorms robots.</li><li>The iRobot Create3 has a good path to student professional development due to the ability to control it using ROS2.</li><li>I was able to obtain sufficient internal funding for this purpose.</li></ul><div>The robots work pretty well using the <a href="https://python.irobot.com/" target="_blank">Python Playground</a>. 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. </div><div><br /></div><div>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. </div><div><br /></div><div>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. </div><div><br /></div><div>Setting up the Raspberry Pi for this purpose is a little tricky. The <a href="https://iroboteducation.github.io/create3_docs/setup/pi4humble/" target="_blank">instructions provided by iRobot</a> are very helpful, but there are a few missing details that I will supply here:</div><div><ul style="text-align: left;"><li>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 <a href="https://linuxconfig.org/ubuntu-20-04-remote-desktop-access-from-windows-10" target="_blank">Remote Desktop</a> it has never been easier.</li><li>There are three system files to modify to get the wired USB-C connection to work mentioned in Steps 6-8: </li><ul><li>The file to modify in Step 6 is <span style="font-family: courier;">/boot/firmware/config.txt</span>. </li><li>The file to modify in Step 7 is <span style="font-family: courier;">/boot/firmware/cmdline.txt</span>.</li><li>The file to modify in Step 8 is <span style="font-family: courier;">/etc/netplan/01-network-manager-all.yaml</span>. In addition to the file contents provided, you'll need to add the <span style="font-family: courier;">ethernets </span>and <span style="font-family: courier;">usb0 </span>headers, as I learned from this <a href="https://github.com/iRobotEducation/create3_docs/discussions/424#discussioncomment-6430000" target="_blank">very helpful forum thread</a>.</li></ul><li>In Step 12, right before running <span style="font-family: courier;">sudo apt install -y ros-humble-desktop</span><span style="font-family: inherit;">, run </span><span style="font-family: courier;">sudo apt upgrade</span><span style="font-family: inherit;">. This is suggested on the <a href="https://docs.ros.org/en/humble/Installation/Ubuntu-Install-Debians.html" target="_blank">ROS2 installation page</a>.</span></li><li>To access the Raspberry Pi remotely, I use <span style="font-family: courier;">ssh</span>. To set up <span style="font-family: courier;">ssh</span>, use <span style="font-family: courier;">sudo apt install openssh-server</span>. </li><li>Be sure to reboot the Raspberry Pi after setting up everything. </li><li>Also make sure to set the USB/Bluetooth toggle to USB (on the left).</li><li>If ros2 topic list doesn't show anything beyond<span style="font-family: courier;"> /parameter_events</span> and <span style="font-family: courier;">/rosout</span> after a few attempts, use ping <span style="font-family: courier;">192.168.186.2</span> to see if there is a live wired connection to the robot. If there is, you'll need to reboot the robot. </li><ul><li>Press the two small buttons simultaneously until the blue ring appears to set up the robot's access point. </li><li>Then navigate to 192.168.10.1. </li><li>From Applications, select Reboot Robot. It will take a few minutes.</li><li>Once it chimes, try <span style="font-family: courier;">ros2 daemon stop && ros2 topic list && ros2 topic list</span>. You should see your robot's topics at this point.</li></ul></ul><div>To set up OpenCV for use with a webcam:</div></div><div><ul style="text-align: left;"><li><span style="font-family: courier;">sudo apt install python3-pip</span></li><li><span style="font-family: courier;">pip3 install opencv-python</span></li><li><span style="font-family: courier;">sudo chmod 666 /dev/video0</span></li><ul><li><span style="font-family: inherit;">Without adding read/write permission to the camera, it will be necessary to run all OpenCV scripts using </span><span style="font-family: courier;">sudo</span><span style="font-family: inherit;">. </span></li></ul></ul><div>To view OpenCV windows, follow the instructions at the <a href="https://linuxconfig.org/ubuntu-20-04-remote-desktop-access-from-windows-10">link</a> to enable <a href="https://linuxconfig.org/ubuntu-20-04-remote-desktop-access-from-windows-10" target="_blank">Remote Desktop</a>. </div></div><p></p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-61357004482649149822022-09-06T15:52:00.002-05:002022-09-06T15:52:44.984-05:00Running Rust and Flutter on a Kindle Fire 7<p> Due to my strong interest in both <a href="https://www.rust-lang.org/" target="_blank">Rust </a>and mobile apps, I've been learning to use the <a href="https://crates.io/crates/flutter_rust_bridge" target="_blank"><span style="font-family: courier;">flutter_rust_bridge</span></a> package to build mobile apps using Rust and Flutter. They have a pretty clever <a href="http://cjycode.com/flutter_rust_bridge/tutorial_with_flutter.html" target="_blank">example </a>in their <a href="http://cjycode.com/flutter_rust_bridge/" target="_blank">user guide</a> 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.</p><p>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:</p><p></p><ul style="text-align: left;"><li>I cloned their GitHub repo as instructed. If you use an IDE, I suggest opening it up in Android Studio.</li><li>In the <a href="https://github.com/fzyzcjy/flutter_rust_bridge/blob/master/.github/workflows/ci.yaml" target="_blank">CI Workflow</a>, I examined the <span style="font-family: courier;">flutter_android_test </span>section. The bullets below described what I used or had to adapt.</li><ul><li>I had installed NDK some time ago. The instructions there are for a Unix platform. For Windows, Android provides a <a href="https://developer.android.com/studio/projects/install-ndk#:~:text=%20To%20install%20a%20specific%20version%20of%20the,package%20%28s%29%20consumes.%206%20Click%20OK.%20More%20" target="_blank">useful guide</a>. I think this is what I did, but I honestly don't remember for sure.</li><li>I already had Rust and Flutter installed. </li><li>I next installed the <span style="font-family: courier;">cargo-ndk</span> program: <span style="font-family: courier;">cargo install cargo-ndk</span></li><li><span style="font-family: inherit;">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: </span><span style="font-family: courier;">rustup target add armv7-linux-androideabi </span><span style="font-family: inherit;">in the </span><span style="font-family: courier;">rust </span><span style="font-family: inherit;">subdirectory. This downloads the necessary files for </span><span style="font-family: courier;">rustc </span><span style="font-family: inherit;">to cross-compile to that specific Android architecture.</span></li><li><span style="font-family: inherit;">Note that, other than disk space, there is no particular drawback to including <a href="https://doc.rust-lang.org/beta/rustc/platform-support.html" target="_blank">as many distinct Android targets as you'd like</a>. Each one you compile will be included in the APK, and at runtime it will try to select the correct </span><span style="font-family: courier;">.so</span><span style="font-family: inherit;"> file for the architecture on which it is running. </span></li><li><span style="font-family: inherit;">At this point, I was ready to compile: </span><span style="font-family: courier;">cargo ndk -t armv7-linux-androideabi -o ..\android\app\src\main\jniLibs build</span></li></ul><li><span style="font-family: inherit;">Having completed the above setup, </span><span style="font-family: courier;">flutter run</span><span style="font-family: inherit;"> built the APK, uploaded it to my device, and executed it perfectly.</span></li></ul><div>I realized what the problem was after finding <a href="https://stackoverflow.com/a/72339448/906268" target="_blank">this answer</a> on StackOverflow. I added <a href="https://stackoverflow.com/a/73627439/906268" target="_blank">my own answer</a> as well, then wrote this blog post to add a few more details for any other Android Rust enthusiasts out there!</div><p></p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-57489018651417933682022-08-29T15:24:00.003-05:002022-08-29T15:24:16.392-05:00Socket Programming in Dart and Flutter<p>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.</p><h2 style="text-align: left;">Future, Async, Await</h2><p>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:</p><p></p><ul style="text-align: left;"><li><a href="https://api.dart.dev/stable/2.18.0/dart-async/Future-class.html" target="_blank"><span style="font-family: courier;">Future</span></a> objects</li><li>The <span style="font-family: courier;">async </span>keyword</li><li>The <span style="font-family: courier;">await </span>keyword</li></ul><div>Any function in Dart can be labeled <span style="font-family: courier;">async</span>. Every function labeled <span style="font-family: courier;">async </span>returns a <span style="font-family: courier;">Future </span>object immediately. The function then executes asynchronously with respect to the calling code. </div><div><br /></div><div>There are several ways in which the caller can interact with the returned <span style="font-family: courier;">Future </span>object. The <span style="font-family: courier;">.then()</span> method sets up a callback function to execute once the <span style="font-family: courier;">async </span>function has completed successfully. The <span style="font-family: courier;">.catchError()</span> method sets up a callback function to execute in the event that the <span style="font-family: courier;">async </span>function throws an exception. And the <span style="font-family: courier;">.whenComplete()</span> method's callback executes whenever the <span style="font-family: courier;">async </span>function completes, error or not. These three methods can be thought of as analogous to <span style="font-family: courier;">try</span>, <span style="font-family: courier;">catch</span>, and <span style="font-family: courier;">finally</span>, respectively.</div><div><br /></div><div>Within an <span style="font-family: courier;">async </span>function itself, it is pretty common to call another <span style="font-family: courier;">async </span>function. In that case, the most common way to interact with the <span style="font-family: courier;">Future </span>returned by the called function is to use the <span style="font-family: courier;">await </span>keyword to pause the caller until the callee's <span style="font-family: courier;">Future </span>completes. </div><div><br /></div><div>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 <span style="font-family: courier;">async </span>function. </div><div><br /></div><h2 style="text-align: left;">Listening for Incoming Connections</h2><div>The following examples come from a <a href="https://github.com/gjf2a/text_messenger" target="_blank">peer-to-peer text messenger app</a> I wrote. Here is a code segment for setting up a server socket:</div>
<pre>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;
}
}
</pre>
<div>As <span style="font-family: courier;">_setupServer()</span> is an <span style="font-family: courier;">async </span>method, it needs to return a <span style="font-family: courier;">Future</span>. Since it does not return any concrete values, it returns a <span style="font-family: courier;">Future<void></span>. It uses <span style="font-family: courier;">await </span>to pause until it has acquired a <span style="font-family: courier;">ServerSocket </span>instance. It then instructs the <span style="font-family: courier;">ServerSocket </span>object to use <span style="font-family: courier;">_listenToSocket()</span> as its callback by using the<span style="font-family: courier;"> .listen() </span>method. That method makes <span style="font-family: courier;">_listenToSocket()</span><span style="font-family: inherit;">a subscriber to the </span><span style="font-family: courier;">ServerSocket</span><span style="font-family: inherit;">. </span></div>
<pre>void _listenToSocket(Socket socket) {
socket.listen((data) {
setState(() {
_handleIncomingMessage(socket.remoteAddress.address, data);
});
});
}
</pre>
<div>Within <span style="font-family: courier;">_listenToSocket()</span>, there is no need for asynchronous code. Every time the <span style="font-family: courier;">ServerSocket </span>receives an incoming connection, it executes <span style="font-family: courier;">_listenToSocket()</span> and passes in the <span style="font-family: courier;">Socket </span>it creates to communicate with the incoming connection. The <span style="font-family: courier;">_listenToSocket()</span> 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. </div><div><br /></div><div>Because <span style="font-family: courier;">async </span>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 <span style="font-family: courier;">_MyHomePageState </span>class, of which <span style="font-family: courier;">_listenToSocket()</span> is a method. As <span style="font-family: courier;">_MyHomePageState</span><span style="font-family: courier;"> </span>inherits from the <span style="font-family: courier;">State</span><span style="font-family: courier;"> </span>class, it inherits the <span style="font-family: courier;">.setState()</span> method for updating the user interface. Each call to <span style="font-family: courier;">.setState()</span> places the code passed to it in the UI event queue. The code passed through <span style="font-family: courier;">.setState()</span> is thus effectively protected from data races on the UI state.</div><div><br /></div><h2 style="text-align: left;">Sending Outgoing Messages</h2><div>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 <span style="font-family: courier;">Friend </span>class:</div>
<pre>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)));
}
}
</pre>
<div>When the user sends a message to the specified <span style="font-family: courier;">Friend</span>, the <span style="font-family: courier;">.send()</span> method pauses via <span style="font-family: courier;">await </span>while awaiting the acknowledgement of the connection and the creation of a <span style="font-family: courier;">Socket</span>. The message history is stored in the <span style="font-family: courier;">_messages </span>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 <a href="https://pub.dev/packages/mutex" target="_blank">mutex </a>package. The .protect() method treats its code parameter as an atomic critical section. By using <span style="font-family: courier;">await</span>, we can block until the mutex is free to allow the critical section to enter.</div><div><br /></div><h2 style="text-align: left;">Review of Key Ideas</h2><div>To write a <a href="https://github.com/gjf2a/text_messenger" target="_blank">TCP socket app</a> using Flutter, it is important to understand the following key ideas:</div><div><ul style="text-align: left;"><li>Concurrency via <span style="font-family: courier;">Future</span>, <span style="font-family: courier;">async</span>, and <span style="font-family: courier;">await</span>.</li><li>Subscribing callback code using <span style="font-family: courier;">.listen()</span>.</li></ul></div><p></p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-13293049234452200142020-10-13T13:49:00.000-05:002020-10-13T13:49:02.036-05:00Serialization with JSON in Dart<p>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. </p><p>A <i>de facto</i> standard serialization language that has emerged in recent years is <a href="https://www.json.org/json-en.html" target="_blank">JSON</a>, the JavaScript Object Notation. The Dart language has <a href="https://flutter.dev/docs/development/data-and-backend/json#manual-encoding" target="_blank">adapted it as its own serialization standard</a>, and it is the approach that we will employ here. </p><p>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. </p><p>Here is a simple Dart class representing a <code>User</code> with two strings: a name and title. It creates a JSON object by returning a Dart <code>Map</code> 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.</p>
<pre>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'];
}
</pre>
<p>The Map object containing the JSON representation has a value type of dynamic to avoid overdetermining the data types of the instance variables.</p><p>This next class contains a User object, and helps illustrate how JSON can be built recursively:</p>
<pre>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']);
}</pre>
<p>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.</p><p>To send a UserStampedMessage over a network, then, involves the following steps:</p><p></p><ul style="text-align: left;"><li>Convert the object to JSON.</li><li>Convert the JSON to a string (use the jsonEncode() function from the dart:convert package).</li><li>Send the string into a socket.</li></ul><div>Retrieving a UserStampedMessage from a socket requires the following complementary steps:</div><div><ul style="text-align: left;"><li>The value coming from the socket will be a Uint8List (i.e., a byte sequence). Use String.fromCharCodes() to convert it to a string.</li><li>Convert the string into a JSON map using the jsonDecode() function from the dart:convert package.</li><li>Rebuild the object from the JSON map using the fromJson method.</li></ul><div>The following code fragment shows the encoding process:</div>
<pre>
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...
</pre>
<div>Here are the pieces assembled for the decoding process:</div>
<pre>
String msgStr = /* retrieve from socket, file, or wherever... */;
Map<String, dynamic> decodedMap = jsonDecode(msgStr);
UserStampedMessage recovered = UserStampedMessage.fromJson(decodedMap);
</pre>
<p>Happy coding!</p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com1tag:blogger.com,1999:blog-5235423068973972362.post-52543843958774210912020-09-20T05:37:00.003-05:002020-09-20T19:48:12.677-05:00Getting Started with Dart and Flutter<p> I find the Flutter framework for mobile app development to be appealing and exciting for several reasons:</p><p></p><ul style="text-align: left;"><li>A common source code base can be used to build both an Android and iPhone app.</li><li>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.</li><li>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.</li><li>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.</li></ul><div>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#.</div><div><br /></div><h1 style="text-align: left;">Hello, World!</h1><div>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:</div><div><br /></div><div><pre style="background-color: white; font-family: "courier new"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">import </span><span style="color: green; font-weight: bold;">'package:flutter/material.dart'</span>;<br /><br /><span style="color: navy; font-weight: bold;">void </span>main() {<br /> runApp(<span style="color: #2196f3;">MyApp</span>());<br />}<br /><br /></pre><p>This program starts executing in the <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">main()</span> function. It calls <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">runApp(</span><span style="background-color: white; font-family: "courier new"; font-size: 9pt;">)</span> with a newly created object of the <span style="background-color: white; color: #2196f3; font-family: "courier new"; font-size: 9pt;">MyApp </span>class:</p>
<pre style="background-color: white; font-family: "courier new"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">class </span>MyApp <span style="color: navy; font-weight: bold;">extends </span>StatelessWidget {<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span><span style="color: olive;">@override<br /></span><span style="color: olive;"> </span>Widget build(BuildContext context) {<br /> <span style="color: navy; font-weight: bold;">return </span><span style="color: #2196f3;">MaterialApp</span>(<br /> title: <span style="color: green; font-weight: bold;">'Flutter Demo'</span>,<br /> theme: <span style="color: #2196f3;">ThemeData</span>(<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>primarySwatch: Colors.<span style="color: #660e7a; font-style: italic;">blue</span>,<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>visualDensity: VisualDensity.<span style="color: #660e7a; font-style: italic;">adaptivePlatformDensity</span>,<br /> ),<br /> home: <span style="color: #2196f3;">MyHomePage</span>(title: <span style="color: green; font-weight: bold;">'Flutter Demo Home Page'</span>),<br /> );<br /> }<br />}<br /><br /></pre><p>The architecture of a Flutter app has a <a href="https://api.flutter.dev/flutter/widgets/StatelessWidget-class.html" target="_blank">StatelessWidget</a> at its root, to organize the basic layout. Its stateless nature is implemented by the fact that, under typical circumstances, its <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">build()</span> method is only called when it is created, and it really doesn't do anything other than answer calls to its <span style="background-color: white; font-family: "courier new"; font-size: 12px;">build()</span> method. </p><p>The actual layout, then, is determined by the Widget returned by the <span style="background-color: white; font-family: "courier new"; font-size: 12px;">build()</span> method. In this program, that <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">Widget </span>is a <a href="https://api.flutter.dev/flutter/material/MaterialApp-class.html" target="_blank">MaterialApp</a> 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 <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">MyHomePage </span>class:</p>
<pre style="background-color: white; font-family: "courier new"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">class </span>MyHomePage <span style="color: navy; font-weight: bold;">extends </span>StatefulWidget {<br /> MyHomePage({Key key, <span style="color: navy; font-weight: bold;">this</span>.<span style="color: #660e7a; font-weight: bold;">title</span>}) : <span style="color: navy; font-weight: bold;">super</span>(key: key);<br /><span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span><span style="color: navy; font-weight: bold;">final </span>String <span style="color: #660e7a; font-weight: bold;">title</span>;<br /><br /> <span style="color: olive;">@override<br /></span><span style="color: olive;"> </span>_MyHomePageState createState() => <span style="color: #2196f3;">_MyHomePageState</span>();<br />}<br /><br /></pre><p>Just as <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">StatelessWidget.</span><span style="background-color: white; font-family: "courier new"; font-size: 9pt;">build()</span> is called when a <span style="background-color: white; font-family: "courier new"; font-size: 12px;">StatelessWidget </span>is created, <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">StatefulWidget</span>.<span style="background-color: white; font-family: "courier new"; font-size: 9pt;">createState()</span> is called when a <a href="https://api.flutter.dev/flutter/widgets/StatefulWidget-class.html" target="_blank">StatefulWidget</a> is created. The resulting State object will mutate as needed in response to the pertinent system inputs. Much as with the <span style="background-color: white; font-family: "courier new"; font-size: 12px;">StatelessWidget</span>, there really isn't much to a <span style="background-color: white; font-family: "courier new"; font-size: 12px;">StatefulWidget</span>other than the <span style="background-color: white; font-family: "courier new"; font-size: 12px;">createState()</span> method. The real action is in the <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">State </span>object, as we see next:</p>
<pre style="background-color: white; font-family: "courier new"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">class </span>_MyHomePageState <span style="color: navy; font-weight: bold;">extends </span>State<MyHomePage> {<br /> int <span style="color: #660e7a; font-weight: bold;">_counter </span>= <span style="color: blue;">0</span>;<br /><br /> <span style="color: navy; font-weight: bold;">void </span>_incrementCounter() {<br /> setState(() {<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span><span style="color: #660e7a; font-weight: bold;">_counter</span>++;<br /> });<br /> }<br /><br /> <span style="color: olive;">@override<br /></span><span style="color: olive;"> </span>Widget build(BuildContext context) {<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span><span style="color: navy; font-weight: bold;">return </span><span style="color: #2196f3;">Scaffold</span>(<br /> appBar: <span style="color: #2196f3;">AppBar</span>(<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>title: <span style="color: #2196f3;">Text</span>(<span style="color: #660e7a; font-weight: bold;">widget</span>.<span style="color: #660e7a; font-weight: bold;">title</span>),<br /> ),<br /> body: <span style="color: #2196f3;">Center</span>(<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>child: <span style="color: #2196f3;">Column</span>(<span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>mainAxisAlignment: MainAxisAlignment.<span style="color: #660e7a; font-weight: bold;">center</span>,<br /> children: <Widget>[<br /> <span style="color: #2196f3;">Text</span>(<br /> <span style="color: green; font-weight: bold;">'You have pushed the button this many times:'</span>,<br /> ),<br /> <span style="color: #2196f3;">Text</span>(<br /> <span style="color: green; font-weight: bold;">'</span>$<span style="color: #660e7a; font-weight: bold;">_counter</span><span style="color: green; font-weight: bold;">'</span>,<br /> style: Theme.<span style="font-style: italic;">of</span>(context).<span style="color: #660e7a; font-weight: bold;">textTheme</span>.<span style="color: #660e7a; font-weight: bold;">headline4</span>,<br /> ),<br /> ],<br /> ),<br /> ),<br /> floatingActionButton: <span style="color: #2196f3;">FloatingActionButton</span>(<br /> onPressed: _incrementCounter,<br /> tooltip: <span style="color: green; font-weight: bold;">'Increment'</span>,<br /> child: <span style="color: #2196f3;">Icon</span>(Icons.<span style="color: #660e7a; font-style: italic;">add</span>),<br /> ), <span style="color: grey; font-style: italic;"><br /></span><span style="color: grey; font-style: italic;"> </span>);<br /> }<br />}</pre><pre style="background-color: white; font-family: "courier new"; font-size: 9pt;"><span style="background-color: transparent;"></span></pre></div><p>There are a number of important observations to make about the <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">_MyHomePageState</span> class:</p><p></p><ul style="text-align: left;"><li>Dart does not include public or private keywords; instead, any class or instance variable name that starts with an underscore ("_") is private. So the <span style="background-color: white; font-family: "courier new"; font-size: 12px;">_MyHomePageState</span> class, its _counter instance variable and its _incrementCounter() method are all private.</li><li>Calling <a href="https://api.flutter.dev/flutter/widgets/State/setState.html" target="_blank">State.setState()</a> 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.</li><li>In this specific case, the build() method creates a <a href="https://api.flutter.dev/flutter/material/Scaffold-class.html" target="_blank">Scaffold</a> 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. </li><li>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.</li></ul><div><br /></div><h1 style="text-align: left;">Math Quizzer</h1><div>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. </div><div><br /></div><div>Adding this new functionality only requires changing the <span style="background-color: white; font-family: "courier new"; font-size: 9pt;">_MyHomePageState </span>class. The new version is as follows:</div><p></p><pre style="background-color: white; font-family: "Courier New"; font-size: 9pt;"><span style="color: navy; font-weight: bold;">class </span>_MyHomePageState <span style="color: navy; font-weight: bold;">extends </span>State<MyHomePage> {<br /> int <span style="color: #660e7a; font-weight: bold;">_correct </span>= <span style="color: blue;">0</span>;<br /> int <span style="color: #660e7a; font-weight: bold;">_incorrect </span>= <span style="color: blue;">0</span>;<br /> int <span style="color: #660e7a; font-weight: bold;">_x </span>= <span style="color: blue;">0</span>;<br /> int <span style="color: #660e7a; font-weight: bold;">_y </span>= <span style="color: blue;">0</span>;<br /> Random <span style="color: #660e7a; font-weight: bold;">_rng </span>= <span style="color: navy; font-weight: bold;">new </span><span style="color: #2196f3;">Random</span>();<br /> TextEditingController <span style="color: #660e7a; font-weight: bold;">_controller</span>;<br /><br /> <span style="color: navy; font-weight: bold;">void </span>initState() {<br /> <span style="color: navy; font-weight: bold;">super</span>.initState();<br /> <span style="color: #660e7a; font-weight: bold;">_controller </span>= <span style="color: #2196f3;">TextEditingController</span>();<br /> _reset_nums();<br /> }<br /><br /> <span style="color: navy; font-weight: bold;">void </span>dispose() {<br /> <span style="color: #660e7a; font-weight: bold;">_controller</span>.dispose();<br /> <span style="color: navy; font-weight: bold;">super</span>.dispose();<br /> }<br /><br /> <span style="color: navy; font-weight: bold;">void </span>_reset_nums() {<br /> <span style="color: #660e7a; font-weight: bold;">_x </span>= <span style="color: #660e7a; font-weight: bold;">_rng</span>.nextInt(<span style="color: blue;">12</span>) + <span style="color: blue;">1</span>;<br /> <span style="color: #660e7a; font-weight: bold;">_y </span>= <span style="color: #660e7a; font-weight: bold;">_rng</span>.nextInt(<span style="color: blue;">12</span>) + <span style="color: blue;">1</span>;<br /> }<br /><br /> <span style="color: navy; font-weight: bold;">void </span>_check(String answer) {<br /> <span style="color: navy; font-weight: bold;">try </span>{<br /> <span style="color: navy; font-weight: bold;">var </span>target = int.<span style="font-style: italic;">parse</span>(answer);<br /> setState(() {<br /> int total = <span style="color: #660e7a; font-weight: bold;">_x </span>+ <span style="color: #660e7a; font-weight: bold;">_y</span>;<br /> <span style="color: navy; font-weight: bold;">if </span>(total == target) {<br /> <span style="color: #660e7a; font-weight: bold;">_correct </span>+= <span style="color: blue;">1</span>;<br /> } <span style="color: navy; font-weight: bold;">else </span>{<br /> <span style="color: #660e7a; font-weight: bold;">_incorrect </span>+= <span style="color: blue;">1</span>;<br /> }<br /> _reset_nums();<br /> });<br /> } <span style="color: navy; font-weight: bold;">on </span>FormatException {<br /><br /> }<br /> }<br /><br /> <span style="color: olive;">@override<br /></span><span style="color: olive;"> </span>Widget build(BuildContext context) {<br /> TextStyle _ts = Theme.<span style="font-style: italic;">of</span>(context).<span style="color: #660e7a; font-weight: bold;">textTheme</span>.<span style="color: #660e7a; font-weight: bold;">headline4</span>;<br /><br /> <span style="color: navy; font-weight: bold;">return </span><span style="color: #2196f3;">Scaffold</span>(<br /> appBar: <span style="color: #2196f3;">AppBar</span>(<br /> title: <span style="color: #2196f3;">Text</span>(<span style="color: #660e7a; font-weight: bold;">widget</span>.<span style="color: #660e7a; font-weight: bold;">title</span>),<br /> ),<br /> body: <span style="color: #2196f3;">Center</span>(<br /> child: <span style="color: #2196f3;">Column </span>(<br /> mainAxisAlignment: MainAxisAlignment.<span style="color: #660e7a; font-weight: bold;">center</span>,<br /> children: <Widget>[<br /> <span style="color: #2196f3;">Row </span>(<br /> mainAxisAlignment: MainAxisAlignment.<span style="color: #660e7a; font-weight: bold;">center</span>,<br /> children: <Widget>[<br /> <span style="color: #2196f3;">Text</span>(<span style="color: green; font-weight: bold;">'</span>$<span style="color: #660e7a; font-weight: bold;">_x</span><span style="color: green; font-weight: bold;"> + </span>$<span style="color: #660e7a; font-weight: bold;">_y</span><span style="color: green; font-weight: bold;"> = '</span>, style: _ts),<br /> <span style="color: #2196f3;">SizedBox</span>(width: <span style="color: blue;">100</span>, child: <span style="color: #2196f3;">TextField</span>(controller: <span style="color: #660e7a; font-weight: bold;">_controller</span>,style: _ts,<br /> onSubmitted: (String value) {_check(value); <span style="color: #660e7a; font-weight: bold;">_controller</span>.clear();})),<br /> ],),<br /> <span style="color: #2196f3;">Text</span>(<br /> <span style="color: green; font-weight: bold;">'Correct: </span>$<span style="color: #660e7a; font-weight: bold;">_correct</span><span style="color: green; font-weight: bold;">'</span>,style: _ts,<br /> ),<br /> <span style="color: #2196f3;">Text</span>(<br /> <span style="color: green; font-weight: bold;">'Incorrect: </span>$<span style="color: #660e7a; font-weight: bold;">_incorrect</span><span style="color: green; font-weight: bold;">'</span>,style: _ts,<br /> )<br /> ],<br /> ),<br /> ),<br /> );<br /> }<br />}</pre><div>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 <span style="color: navy; font-family: "Courier New"; font-size: 9pt; font-weight: bold;">import </span><span style="color: green; font-family: "Courier New"; font-size: 9pt; font-weight: bold;">'dart:math'</span><span style="background-color: white; font-family: "Courier New"; font-size: 9pt;">;</span> to use it.) </div><div><br /></div><h1 style="text-align: left;">A More Sophisticated Math Quizzer</h1><div>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 <a href="https://github.com/gjf2a/simple_math" target="_blank">full implementation is available on GitHub</a>. </div><div><br /></div><h2 style="text-align: left;">Data Structures</h2><div>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:</div><br />
<pre>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, "/")
};
</pre>
<p>This enum, <code>Op</code>, 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 <code>Function</code>, 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 <code>this.member</code> to auto-initialize the specified member with the specified parameter. The <code>get</code> keyword denotes a getter method. It is invoked without parentheses or parameters to yield a non-mutable attribute.
</p>
<p>Next we examine an <code>ArithmeticProblem</code>, which combines an <code>Op</code> with two operands to represent a problem for a student to solve: </p>
<pre>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";
}
}
</pre>
<p> The <code>opData</code> Map defined earlier is employed throughout the implementation of the <code>ArithmeticProblem</code> 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.
</p>
<p>A <code>Quiz</code> contains a bunch of <code>ArithmeticProblem</code> objects as well as a random number generator. Each <code>Quiz</code> 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 <code>Quiz</code> is considered complete.</p>
<pre>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()}';
}
</pre>
<p>
The <code>enum Outcome</code> is introduced to enable a <code>Quiz</code> 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.
</p><p><br /></p><h2 style="text-align: left;">Unit Testing</h2><div>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.</div>
<pre>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);
}
</pre>
<p>Dart's unit testing infrastructure is straightforward, albeit a bit different in layout than the various <code>xUnit</code> frameworks. A single <code>main()</code> function calls all the tests. Each test is run by a call to the <code>test</code> function, which supplies the test code in a <code>Function</code> object. Within the test code, each assertion is tested using an <code>expect</code> function call. The expression being evaluated is the first <code>expect</code> parameter, and the target value is the second parameter.
</p><p><br /></p><h2 style="text-align: left;">User Interface Code</h2><div>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 <code>_MyHomePageState</code> class.</div>
<pre> 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();
}
</pre>
<p>The <code>_screen</code> object is a reference to the <code>Function</code> that should be employed for rendering the current app screen. I found this to be an elegant way to transition between screens - just change <code>_screen</code> to the appropriate function.</p>
<p>The <code>_problems</code> and <code>_rng</code> objects are used for the application state. The <code>_controller</code> and <code>_ts</code> objects simplify the use of certain UI components. The <code>_selected</code> and <code>_lastMax</code> objects represent the user's inputs at the start screen, and the <code>_lastCorrect</code> object is used to give the user feedback based on whether the last answer was correct.</p>
<p>The <code>initState()</code> 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 <code>dispose</code> method is unfortunately necessary for cleaning up resource usage from the <code>_controller</code> object.</p>
<p> The functions below represent the three different screens the app displays: a start screen, a problem-answering screen, and a congratulatory concluding screen.</p>
<pre> @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;
}
}
</pre>
<p>The <code>build</code> method shows how the <code>_screen</code> object is used to redirect to the current screen. (The text style is set up there due to access to the <code>BuildContext</code> object.) All of the screens in this app have the same basic framing, which is given in <code>build</code>; the role of the <code>_screen</code> object is to plug in a child <code>Widget</code> describing the elements specific to that screen. The <code>pickBackground</code> 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. </p>
<p>The <code>setup</code> 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.</p>
<p>The <code>quizScreen</code> 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 <code>$</code> introduces a variable; a <code>${}</code> allows the insertion of a full expression.</p>
<p>Finally, the <code>done</code> method congratulates the user on completing the quiz, and uses the same <code>_restartButton</code> method to create a path back to the opening screen. This and the other helper methods are shown below.</p>
<pre> 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,));
}
</pre>
<p>The <code>numericalEntry</code> method creates an area that allows text entry of numerical values. The Flutter <code>TextField</code> is somewhat finicky; it needs to be deployed within a <code>SizedBox</code> (or another size-controlling widget). The <code>InputDecoration</code> 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 <code>onSubmitted</code> object represents the event handler.</p>
<p>Radio buttons are very straightforward as well. The <code>groupValue</code> 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.)</p>
<p>The <code>raisedButton</code> object is used for the restart button. Note that placing text on a button requires giving it a child widget.</p>
<p>Finally we have the event-handling methods:</p>
<pre> 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;
});
}
</pre>
<p>The <code>_start</code> method starts a quiz, and the <code>_check</code> method processes an answer. I didn't write a substantive event handler, as using the numeric entry screen should suffice to ensure that <code>FormatException</code> is not possible to raise. By placing the exception handling code in <code>_processNumberEntry</code>, if at a later time I wish to do something more substantive, I won't have to replicate it in both <code>_start</code> and <code>_check</code>. The <code>_restart</code> method returns to the start screen. The <code>resetController</code> call makes sure that the previous maximum operand value reappears on the start screen. </p>
<p>In all three event handlers, an update to the user interface is triggered by a call to <code>setState</code>. The code passed to <code>setState</code> is executed later by the user interface framework prior to refreshing the screen. Transitions between screens are controlled by setting the <code>_screen</code> object to the desired new function. In this way, <code>_screen</code> represents a state in a state machine that transitions based on the events that occur and the app's state.</p>
<p>Happy app building!</p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-3691465858179606392020-05-15T13:56:00.000-05:002020-05-15T13:56:42.263-05:00Doubly-Linked Lists Are Useless in Collections LibrariesThe <a href="https://en.wikipedia.org/wiki/Doubly_linked_list" target="_blank">doubly-linked list</a> 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 <a href="https://en.wikipedia.org/wiki/Dynamic_array" target="_blank">dynamic arrays</a>, <a href="https://en.wikipedia.org/wiki/Stack_(abstract_data_type)" target="_blank">stacks</a>, <a href="https://en.wikipedia.org/wiki/Queue_(abstract_data_type)" target="_blank">queues</a>, <a href="https://en.wikipedia.org/wiki/Heap_(data_structure)" target="_blank">heaps</a>, <a href="https://en.wikipedia.org/wiki/Linked_list" target="_blank">singly-linked lists</a>, <a href="https://en.wikipedia.org/wiki/Hash_table" target="_blank">hash tables</a>, and <a href="https://en.wikipedia.org/wiki/Binary_search_tree" target="_blank">binary search trees</a>), doubly-linked lists routinely appear as standard collections in data structure libraries. <div><br /></div><div>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:</div><div><ul style="text-align: left;"><li>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.</li><li>Hash tables enable the fastest practical implementations of unordered sets and maps, especially because (like dynamic arrays) they enable cache-friendly memory layout.</li><li>Binary search trees enable fast implementations of totally ordered sets and maps.</li><li>Stacks, queues, and heaps are frequently components of other algorithms, such as <a href="https://en.wikipedia.org/wiki/Graph_traversal" target="_blank">graph traversal</a> and <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" target="_blank">A* search</a> algorithms.</li><li>Singly-linked lists are foundational data structures for <a href="https://en.wikipedia.org/wiki/Purely_functional_programming" target="_blank">purely functional programming</a> and <a href="https://en.wikipedia.org/wiki/Purely_functional_data_structure" target="_blank">purely functional data structures</a>. They are also a prerequisite for understanding binary search trees.</li></ul><div>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:</div><div><ol style="text-align: left;"><li>Constant-time insertion and deletion of elements anywhere in the list, provided that an iterator is pointing to the pertinent location.</li><li>Constant-time insertion and deletion of elements at the start or end of the list. This is suitable for a <a href="https://en.wikipedia.org/wiki/Queue_(abstract_data_type)" target="_blank">queue </a>or <a href="https://en.wikipedia.org/wiki/Double-ended_queue" target="_blank">deque</a>.</li><li>Constant-time splicing of two lists together. </li></ol><div>Its disadvantages include the following:</div></div><div><ol style="text-align: left;"><li>Storing each element also requires storing two pointers, making it somewhat memory-hungry.</li><li>Accessing an arbitrary element requires linear time.</li><li>Lots of tiny linked objects are unlikely to be laid out together in memory in a way that is friendly to the CPU cache.</li></ol><div>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. <a href="https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/LinkedList.html" target="_blank">Java</a>) don't support this operation at all, while others (e.g. <a href="https://doc.rust-lang.org/std/collections/struct.LinkedList.html#method.append" target="_blank">Rust</a>, <a href="http://www.cplusplus.com/reference/list/list/splice/" target="_blank">C++</a>) do. </div><div><br /></div><div>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.</div><div><br /></div><div>Moving on from there, equally suitable (or better) for the first situation are the following:</div></div><div><ol style="text-align: left;"><li>The <a href="https://en.wikipedia.org/wiki/Gap_buffer" target="_blank">gap buffer</a> (<a href="https://crates.io/crates/gapbuf" target="_blank">implementation in Rust</a>) 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 <a href="https://en.wikipedia.org/wiki/Dynamic_array" target="_blank">resized in amortized constant time</a> as needed.</li><li>The <a href="https://en.wikipedia.org/wiki/Zipper_(data_structure)" target="_blank">zipper</a> 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.</li></ol><div>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 <a href="https://en.wikipedia.org/wiki/Purely_functional_data_structure" target="_blank">purely functional data structure</a>. </div></div><div><br /></div><div>For the second situation, a <a href="https://en.wikipedia.org/wiki/Circular_buffer" target="_blank">ring buffer</a> 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 <a href="https://gjf2a.blogspot.com/2020/05/arrays-vs-ring-buffers-performance.html" target="_blank">significant performance penalty in comparison to a standard array</a>. </div><div><br /></div><div>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:</div><div><ol style="text-align: left;"><li>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.</li><li>The dynamic resizing operations are really not very expensive in practice.</li></ol><div>Of course, a claim like the second requires empirical verification. To that end, I <a href="https://github.com/gjf2a/queue_test" target="_blank">implemented a simple experiment in Rust</a>. (Note that, contrary to <a href="https://rcoh.me/posts/rust-linked-list-basically-impossible/" target="_blank">widely-held views about Rust's ownership system</a>, it is <a href="https://play.rust-lang.org/?gist=c3db81ec94bf231b721ef483f58deb35" target="_blank">perfectly possible to implement a doubly-linked list in safe Rust</a> by using <a href="https://doc.rust-lang.org/std/rc/struct.Weak.html" target="_blank">Weak pointers</a>.) 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.</div></div><div><br /></div><div>Here are some results:</div><div><br /></div><div><table border="1" bordercolor="#888" cellspacing="0" style="border-collapse: collapse; border-color: rgb(136, 136, 136); border-width: 1px;"><tbody><tr><td style="min-width: 60px;"> <b># items<span> </span></b></td><td style="min-width: 60px;"><b><a href="https://doc.rust-lang.org/std/collections/struct.VecDeque.html" target="_blank">VecDeque </a>total (s)</b></td><td style="min-width: 60px;"><b> VecDeque max op (s)</b></td><td style="width: 60px;"><b> VecDeque fixed size total (s)</b></td><td style="width: 60px;"><b> VecDeque fixed size op(s)</b></td><td style="width: 60px;"><b> <a href="https://doc.rust-lang.org/std/collections/struct.LinkedList.html" target="_blank">LinkedList </a>total (s)</b></td><td style="min-width: 60px;"><b> LinkedList max op (s)</b></td></tr><tr><td> 100,000</td><td> 0.028143</td><td> 0.000203</td><td style="width: 60px;"> 0.028134</td><td style="width: 60px;"> 0.000022</td><td> 0.035405</td><td> 0.000089</td></tr><tr><td> 1,000,000</td><td> 0.327679</td><td> 0.002232</td><td style="width: 60px;"> 0.314516</td><td style="width: 60px;"> 0.000061</td><td> 0.402862</td><td> 0.000277</td></tr><tr><td style="min-width: 60px;"> 10,000,000</td><td style="min-width: 60px;"> 2.997163</td><td style="min-width: 60px;"> 0.034366</td><td style="width: 60px;"> 2.966092</td><td style="width: 60px;"> 0.000251</td><td style="width: 60px;"> 3.838949</td><td style="min-width: 60px;"> 0.002055</td></tr><tr><td> 100,000,000</td><td> 32.289343</td><td> 0.303334</td><td style="width: 60px;"> 28.891364</td><td style="width: 60px;"> 0.001622</td><td> 47.137053</td><td> 0.019145</td></tr></tbody></table><br /></div><div>I was actually surprised that <a href="https://doc.rust-lang.org/std/collections/struct.LinkedList.html" target="_blank">LinkedList </a>performed as well as it did. While it was always slower than the <a href="https://doc.rust-lang.org/std/collections/struct.VecDeque.html" target="_blank">VecDeque</a>, 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.</div></div><div><br /></div><div>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.</div><div><br /></div><div>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 <a href="https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/LinkedHashMap.html" target="_blank">the insertion order of elements in a hash table</a> 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.<br /><br /></div><div>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.</div>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-57398118677718590412020-05-09T14:07:00.001-05:002020-05-09T14:07:23.102-05:00Using the trait alias: labeling collections of trait constraints in Rust<div>When programming in Rust, a <a href="https://github.com/rust-lang/rust/issues/41517#issuecomment-544340795" target="_blank">major challenge</a> to the <a href="https://en.wikipedia.org/wiki/Don%27t_repeat_yourself" target="_blank">DRY principle</a> is in regard to trait constraints. Let's say, <a href="http://gjf2a.blogspot.com/2020/05/arrays-vs-ring-buffers-performance.html" target="_blank">for example</a>, that I want to create a trait for random-access sequences whose values are primitive (in Rust terms, <a href="https://doc.rust-lang.org/std/marker/trait.Copy.html" target="_blank">Copy</a>) 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:</div>
<pre>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);
}
}
}
</pre>
<p>
Now, in order to implement this trait, we are faced with code duplication for the constraints on the generic variable <code>T</code>:
</p>
<pre>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);
}
}
</pre>
<p>
When coding, the most expedient way forward is to copy-and-paste this sequence of constraints on <code>T</code>. From both an aesthetic and a maintenance perspective, this is a nightmare. </p>
<h1>Option 1: Create an empty trait</h1>
<p>So, when faced with this, I undertook a search to determine what others had done when faced with this situation. The <a href="https://www.worthe-it.co.za/programming/2017/01/15/aliasing-traits-in-rust.html" target="_blank">top search result</a> suggested something like the following:</p>
<pre>pub trait SimpleValue : Copy+PartialEq+PartialOrd+Sized {}
</pre>
<p>
Which, in turn, enables me to write the following:
</p>
<pre>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> {
// ...
}
</pre>
<p>
Now that looks much better! But there is a small wrinkle. Rust won't automatically infer that, say, <code>usize</code> automatically implements the <code>SimpleValue</code> trait. So I do have to declare explicitly that it does:
</p>
<pre>impl SimpleValue for usize {}
</pre>
<p> 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 <code>VTest</code> trait is so successful that we want to import it from a different crate. We would, of course, import <code>SimpleValue</code> as well.
</p>
<p> And actually, this works, most of the time, unless you try something like this:</p>
<pre>impl SimpleValue for i64 {}
</pre>
<p>
In response, the compiler will reply with an error message along the following lines:
</p>
<pre>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
</pre>
<p> Something that is extremely cool about the Rust compiler is its inclusion of hyperlinks to explanations of compiler errors. When we follow <a href="https://doc.rust-lang.org/error-index.html#E0117" target="_blank">this particular link</a>, we learn:</p>
<blockquote>
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
<ul>
<li> the type that is implementing the trait is foreign
</li><li> all of the parameters being passed to the trait (if there are any) are also foreign.
</li></ul>
</blockquote>
<p><a href="https://internals.rust-lang.org/t/revisit-orphan-rules/7795" target="_blank">Orphan rule</a>? <a href="https://github.com/Ixrec/rust-orphan-rules" target="_blank">What's that?</a> 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, <a href="https://qr.ae/pNytsr" target="_blank">it is not clear which trait implementation we should actually use</a>. 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 <a href="https://stackoverflow.com/a/3079748/906268" target="_blank">widely discouraged</a>.</p><p>This rule has proven <a href="https://www.reddit.com/r/rust/comments/f4gow8/is_there_any_hope_of_killing_the_orphan_rules/" target="_blank">hugely unpopular</a>, 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.</p>
<h1> Option 2: The Trait Alias</h1>
<p>This leads to another possible solution, the concept of the <a href="https://github.com/rust-lang/rfcs/blob/master/text/1733-trait-alias.md" target="_blank">trait alias</a>, 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:</p>
<pre>#![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);
}
}
</pre>
<p>Currently, trait aliases are only available in nightly Rust. There is still <a href="https://github.com/rust-lang/rust/issues/41517#issuecomment-544763195" target="_blank">considerable discussion about how the feature should work and what the syntax should look like</a>, 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.</p>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-81802302128672461642020-05-08T12:20:00.002-05:002020-05-08T12:23:44.016-05:00Arrays vs. Ring Buffers: A Performance Comparison in RustThe 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.<div><br /></div><div>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.</div><div><br /></div><div>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.</div><div><br /></div><div>What is not obvious is the degree to which this extra addition to find the index represents a performance penalty. <a href="https://doc.rust-lang.org/std/collections/index.html" target="_blank">Documentation for the Rust Collections library</a> 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. </div><div><br /></div><div>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 <a href="https://github.com/gjf2a/vec_vs_deque/blob/master/src/main.rs" target="_blank">constructed an experiment</a>. </div><div><br /></div><div>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 <a href="https://en.wikipedia.org/wiki/Selection_sort" target="_blank">selection sort</a> 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.</div><div><br /></div><div>Here are the results. For each algorithm, we performed 30 trials with 100000 elements. Each trial featured a different permutation of those values.</div><div><br /></div><div><table border="1" bordercolor="#888" cellspacing="0" style="border-collapse: collapse; border-color: rgb(136, 136, 136); border-width: 1px;"><tbody><tr><td style="width: 60px;"> <b>Data Structure</b></td><td style="width: 60px;"><b>Mean completion time (ms)<span> </span> </b></td><td style="width: 60px;"><b> Standard Deviation</b></td></tr><tr><td> Vec<span> </span><span> </span></td><td><span>3238.4 </span><span> </span></td><td> 205.1558<span> </span><span> </span><span> </span><span> </span><span> </span></td></tr><tr><td style="width: 60px;"> VecDeque<span> </span></td><td style="width: 60px;">4813.2</td><td style="width: 60px;"> 213.019</td></tr></tbody></table><br /></div><div>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.</div><div><br /></div><div>Please feel free to download and experiment with <a href="https://github.com/gjf2a/vec_vs_deque/blob/master/src/main.rs" target="_blank">my source code</a> if you are interested.</div><div><br /></div>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-19942479090181612032020-03-25T08:24:00.003-05:002020-03-25T08:39:21.905-05:00Rust at Apple<div class="tr_bq">
I recently saw the following <a href="https://jobs.apple.com/en-us/details/200144575/software-engineer" target="_blank">job advertisement at Apple</a>, 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.)</div>
<blockquote>
<span style="background-color: white; color: #333333; font-family: "sf pro text" , "sf pro icons" , "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 16px; letter-spacing: -0.357px; white-space: pre-wrap;">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.</span> </blockquote>
<blockquote>
<span style="background-color: white; color: #333333; font-family: "sf pro text" , "sf pro icons" , "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 16px; letter-spacing: -0.357px; white-space: pre-wrap;">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.</span> </blockquote>
<blockquote>
<span style="background-color: white; color: #333333; font-family: "sf pro text" , "sf pro icons" , "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 16px; letter-spacing: -0.357px; white-space: pre-wrap;">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.</span></blockquote>
Here are a few aspects I would like to highlight:<br />
<br />
<ul>
<li>They are migrating an established codebase from C to Rust. This suggests that the <a href="http://trevorjim.com/on-teaching-c/" target="_blank">well-known problems in C</a> of insecure memory accesses and <a href="https://blog.regehr.org/archives/213" target="_blank">undefined behavior</a> are <a href="http://trevorjim.com/using-an-unsafe-language-is-a-design-flaw/" target="_blank">impairing the stability of the system</a>, and that the safety guarantees of Rust are expected to eliminate those problems. Code migration is a lot of work!</li>
<li>They are making significant use of multithreading, another strong point of Rust. The compiler's ability to <a href="https://doc.rust-lang.org/book/ch16-00-concurrency.html" target="_blank">prevent race conditions in RAM</a> will be a big advantage here.</li>
<li>Overhead needs to be minimal. The high performance that Rust facilitates will be helpful here.</li>
<li>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.</li>
</ul>
<div>
I expect we will see more and more similar advertisements as the benefits of Rust continue to become better known.</div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-11387265042349884842020-01-01T17:45:00.001-06:002020-02-06T19:40:30.537-06:00The rise of RustThe <a href="https://www.rust-lang.org/" target="_blank">Rust</a> programming language has been <a href="https://insights.stackoverflow.com/survey/2018/#most-loved-dreaded-and-wanted" target="_blank">increasing in popularity of late</a>. I learned to program in Rust in order to teach my <a href="https://gjf2a.blogspot.com/2017/02/teaching-operating-systems-using-rust.html" target="_blank">Spring 2017 operating systems course</a> using the language, <a href="http://rust-class.org/0/pages/using-rust-for-an-undergraduate-os-course.html" target="_blank">inspired by the work</a> of <a href="http://www.cs.virginia.edu/~evans/" target="_blank">David Evans</a> at the <a href="https://engineering.virginia.edu/departments/computer-science" target="_blank">University of Virginia</a>. 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.<br />
<br />
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: "<a href="https://www.reddit.com/r/rust/comments/eaay3c/why_does_rust_seem_to_inspire_people/" target="_blank">Why does Rust seem to inspire people?</a>"<br />
<blockquote class="tr_bq">
<span style="background-color: white; color: #1a1a1b; font-family: "noto sans" , "arial" , sans-serif; font-size: 14px;">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 </span><em class="_7s4syPYtk5hfUIjySXcRE" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">nuts</em><span style="background-color: white; color: #1a1a1b; font-family: "noto sans" , "arial" , sans-serif; font-size: 14px;">. 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.</span></blockquote>
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.<br />
<blockquote class="tr_bq">
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0px 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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. <span style="background-color: transparent;"> </span></div>
</blockquote>
<blockquote class="tr_bq">
<span style="background-color: white; color: #1a1a1b; font-family: "noto sans" , "arial" , sans-serif; font-size: 14px;">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.</span></blockquote>
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.<br />
<blockquote class="tr_bq">
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0px 0px 0.25em; vertical-align: baseline;">
The sad reality of our world is that <a class="_3t5uN8xUmg0TOwRCOGQEcU" href="https://medium.com/message/everything-is-broken-81e5f33a24e1" rel="noopener noreferrer" style="border: 0px; font: inherit; margin: 0px; padding: 0px; vertical-align: baseline;" target="_blank">everything is broken</a> - as someone who has done security research, I can tell you that every word in that article is true, and more.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
Now imagine a language that breaks that mold. That is fast as C/C++ and can fully replace them, but <em class="_7s4syPYtk5hfUIjySXcRE" style="border: 0px; font-family: inherit; font-size: inherit; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">without the security vulnerabilities.</em> The holy grail that would lets us write code that is secure, reliable and fast <em class="_7s4syPYtk5hfUIjySXcRE" style="border: 0px; font-family: inherit; font-size: inherit; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">all at the same time.</em></div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
That's Rust.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0px; vertical-align: baseline;">
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!</div>
</blockquote>
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 <i>just go away</i>.<br />
<blockquote class="tr_bq">
<span style="background-color: white; color: #1a1a1b; font-family: "noto sans" , "arial" , sans-serif; font-size: 14px;">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.</span></blockquote>
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.<br />
<blockquote class="tr_bq">
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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 (<b>as opposed to: oh, you have a bug, you must be stupid or something for doing wrong things</b>). 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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0.25em; vertical-align: baseline;">
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.</div>
<div class="_1qeIAgB0cPwnLhDF9XSiJM" style="background-color: white; border: 0px; color: #1a1a1b; font-family: "Noto Sans", Arial, sans-serif; font-size: 14px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; padding: 0.8em 0px 0px; vertical-align: baseline;">
So, everything I do in Rust ... feels joyful. <b>I feel like you can achieve anything, and it is not even that difficult.</b> At least the language empowers me, instead of getting in the way, like other ones.</div>
</blockquote>
A couple of comments:<br />
<ul>
<li>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. </li>
<li>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.</li>
</ul>
<div>
The article Why Rust is the Future of Robotics also has interesting insights, most particularly the following information about embedded development:</div>
<blockquote class="tr_bq">
<span style="font-family: inherit;">For embedded systems, specific tools have also been developed:</span>
<br />
<ul>
<li><span style="font-family: inherit;"><span class="jk jv" style="box-sizing: inherit; font-weight: 700;">Peripheral control</span> — There is this thing called <a class="cd dt je jf jg jh" href="https://github.com/japaric/svd2rust" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">svd2rust</a> that can automatically generate a Rust API to access every peripherals on a micro-controller, directly from it’s <a class="cd dt je jf jg jh" href="https://www.keil.com/pack/doc/CMSIS/SVD/html/svd_Format_pg.html" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">SVD description</a>. 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.</span></li>
<li><span style="font-family: inherit;"><span class="jk jv" style="box-sizing: inherit; font-weight: 700;">Ressource collision prevention</span>— In the next version, they will introduce <a class="cd dt je jf jg jh" href="https://github.com/japaric/svd2rust/issues/157" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">singletons</a> 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 <a class="cd dt je jf jg jh" href="https://www.arduino.cc/en/Reference/Servo" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">Servo library</a>, 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 <a class="cd dt je jf jg jh" href="https://github.com/TMRh20/TMRpcm/issues/3" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">many</a>, <a class="cd dt je jf jg jh" href="https://arduino.stackexchange.com/questions/34501/problem-with-pwm-interference" rel="noopener nofollow" style="-webkit-tap-highlight-color: transparent; background-image: url("data:image/svg+xml; background-position: 0px calc(1em + 1px); background-repeat: repeat-x; background-size: 1px 1px; box-sizing: inherit; http: //www.w3.org/2000/svg\"><line x1=\"0\" y1=\"0\" x2=\"1\" y2=\"1\" stroke=\"rgba(0, 0, 0, 0.84)\" /></svg>"); text-decoration-line: none;" target="_blank">many</a>, Arduino users confused. With singletons, Rust can tell you <span class="jk jv" style="box-sizing: inherit; font-weight: 700;">at compile time</span> if the timer is already in use, preventing users massive headaches <span class="jk jv" style="box-sizing: inherit; font-weight: 700;">without any runtime overhead.</span></span></li>
</ul>
</blockquote>
<div>
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 href="https://news.ycombinator.com/item?id=16488227" target="_blank">a Hacker News thread</a>:<br />
<blockquote class="tr_bq">
<span style="background-color: #f6f6ef; font-family: "verdana" , "geneva" , sans-serif; font-size: 12px;">As for the borrow checker, I actually </span><i style="background-color: #f6f6ef; font-family: Verdana, Geneva, sans-serif; font-size: 12px;">did</i><span style="background-color: #f6f6ef; font-family: "verdana" , "geneva" , sans-serif; font-size: 12px;"> find it useful in bare metal. But more for handling </span><i style="background-color: #f6f6ef; font-family: Verdana, Geneva, sans-serif; font-size: 12px;">hardware</i><span style="background-color: #f6f6ef; font-family: "verdana" , "geneva" , sans-serif; font-size: 12px;"> 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 </span><i style="background-color: #f6f6ef; font-family: Verdana, Geneva, sans-serif; font-size: 12px;">statically</i><span style="background-color: #f6f6ef; font-family: "verdana" , "geneva" , sans-serif; font-size: 12px;"> 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.</span></blockquote>
In effect, the borrow checker is proving to be a highly configurable theorem prover for software verification!<br />
<br />
The ownership concept also aids in code optimization. <a href="http://simblob.blogspot.com/2020/02/rust-memory-optimization.html" target="_blank">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</a>.<br />
<br /></div>
For those die-hard C programmers convinced that nothing can beat it, I recommend reading <a href="http://cliffle.com/p/dangerust/" target="_blank">Learning Rust the Dangerous Way</a>. The author's methodology is fascinating. He took a benchmark C program from the Programming Language Shootout and translated it into Rust.<br />
<br />
An important aspect of Rust is that code can be marked <span style="font-family: "courier new" , "courier" , monospace;">unsafe</span>, 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.<br />
<br />
This author, then, takes the C source code for the <a href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/nbody.html" target="_blank">n-body problem</a> and transliterates it into an equivalent Rust program, the entirety of which is in an <span style="font-family: "courier new" , "courier" , monospace;">unsafe </span>block. He then gradually refines each <span style="font-family: "courier new" , "courier" , monospace;">unsafe </span>block into safe Rust code. At the end, the only <span style="font-family: "courier new" , "courier" , monospace;">unsafe </span>code remaining is the calls to the CPU vectorization instructions. As of this writing, the fastest program in the shootout for this problem is <a href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/nbody-rust-7.html" target="_blank">Rust #7</a>, by a different author but taking the same basic approach.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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!Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-47341436475129333152019-12-31T15:16:00.000-06:002020-01-02T14:24:35.790-06:00Thoughts on the process of hiring facultyOver the last several years, I have participated in five search committees seeking to hire tenure-track Assistant Professors. In this essay, I'd like to help potential job applicants gain some understanding of the dynamic of hiring. I also hope that others who are themselves seeking to hire might gain some insight from someone else who has been there.<br />
<br />
Two of these searches were Computer Science searches, one was Spanish, one was Physics, and one was Mathematics. (All five searches were successful.) At Hendrix College, most search committees consist of the following people:<br />
<ul>
<li>All continuing full-time faculty from the department.</li>
<li>One faculty member who is in the same area as the hiring department (Natural Science, Social Science, Humanities) but from a different department.</li>
<li>One faculty member who is outside the area of the hiring department.</li>
<li>Two undergraduate students.</li>
</ul>
<div>
Since our department houses both Computer Science and Mathematics programs, I participated as a department member in all three of those searches. (For the Computer Science searches, I was the committee chair.) I was in-the-area-but-outside-the-department on the Physics search, and outside-the-area on the Spanish search.</div>
<div>
<br /></div>
<div>
As a liberal arts college, our primary criterion is demonstrated potential for excellence in teaching. Criteria can vary significantly among departments, but potential for excellence in scholarship is also important. Perhaps just as important is the concept of "fit"; that is, the ideal candidate should somehow complement the other faculty in the hiring department, and by doing so strengthen the department as a whole. Furthermore, the ideal candidate should also be a good match for Hendrix College. At a school as small as Hendrix, it is important that any candidate should demonstrate the potential for productive relationships with faculty in different disciplines in addition to the home department.</div>
<div>
<ol>
</ol>
<div>
So, how do I go about evaluating a candidate?</div>
</div>
<div>
<br /></div>
<div>
At the application stage, I start by reading the cover letter. I need to see evidence that the candidate has researched both Hendrix College and the target department. Building upon that evidence, the cover letter should tell me a convincing story about how the candidate will succeed as a faculty member at Hendrix College. Failing this, it is possible that I will not read the rest of the application, especially if I have a lot of them to read. </div>
<div>
<br /></div>
<div>
Next, I'll read the candidate's CV. Here, I am looking for the following:</div>
<div>
<ul>
<li>Evidence of teaching experience, especially courses previously taught.</li>
<li>Research record. Here, I am trying to see how well the demonstrated research agenda will work at Hendrix.</li>
<li>Any other interesting tidbits.</li>
</ul>
<div>
Then, I will carefully study the teaching statement, again looking for potential of excellence. I want to see evidence that the candidate has reflected on their experience in the classroom and improved their teaching based on that experience.</div>
</div>
<div>
<br /></div>
<div>
I read the research statement next. I try to find evidence that the research agenda has the potential to productively involve undergraduate students. I really like research statements that explicitly describe how undergraduate students could get involved.<br />
<br />
For both the teaching and research statements, I am also assessing the quality of the candidate's writing. If either statement is poorly written, it implies serious problems down the line. First, the candidate will be unlikely to help students improve their own writing. Second, poor writing is usually symptomatic of incoherent thinking.</div>
<div>
<br /></div>
<div>
Finally, I read the letters of recommendation. I like to see specific examples demonstrating the candidate's potential for excellence in teaching. A description of a visit to a class is much more impressive than the typical "I saw the person give a research presentation, and it was so lucid and clear that I am sure this person will be an excellent teacher." In regards to research, I like to see examples that showcase the candidate's problem-solving abilities and creativity.</div>
<div>
<br /></div>
<div>
For candidates who we select for videoconference interviews, we typically allow 25-30 minutes. The specific questions we ask are a means to a goal, which is to use our brief time with the candidate to see if we can visualize that person as a productive colleague. I look for evidence of deep knowledge of the subject matter that we would like the person to teach. I also evaluate the candidate's ability to clearly and concisely explain concepts and ideas. I try to ask questions that bring about extemporaneous answers from the candidate.<br />
<br />
I also want the candidate to have 3-4 questions ready for us. Those questions should provide evidence that the candidate has thought seriously about the specific position at Hendrix.<br />
<br />
For the on-campus interview, I am looking for the same things, although in more depth. It is again an exercise in visualizing the candidate as a productive colleague. I would recommend that candidates not be too uptight about this; just be yourself! If the application your produced is consistent with what you are like in person, there is nothing to worry about.<br />
<br />
The candidate's public presentation is extremely important (as Dr. McCulloch reminded me in his comment below). It is my opportunity to visualize the candidate in the classroom. It is also an extended introduction to the candidate's thought process and perspective. During the talk, I need to see that the candidate pitches their ideas in a manner that is both accessible to and appealing to students. I really want to see students get excited about the topic that they are presenting. Something that really helps with this is when the candidate is excited about the topic. Such excitement can be contagious.<br />
<br />
The talk can make or break the interview. I have seen a lackluster interview with a phenomenal talk that resulted in an offer. I have seen a strong interview with a problematic talk that resulted in us crossing the candidate off the list. Related to this, the candidate should ensure significant depth of knowledge of the topic of the talk. The candidate need not know everything, and being clear about the limits of our knowledge is important in this profession. But at some point a faculty candidate is expected to have acquired expertise, and we should see evidence of this in the talk.<br />
<br />
Decision time is often very difficult. At times, I must admit that there is not enough evidence that the candidate will be a productive colleague, at which point there is no need to consider that person further. But more often than not, by the time we bring a candidate on campus there is already very good evidence that this person would be an excellent colleague, and the campus visit often confirms this. (This also applies to the videoconference interviews.) From there, we have to weigh the strengths and weaknesses of the candidates against each other in order to make a decision.<br />
<br />
There have been multiple occasions where my impulse is "hire them both!" But as this is usually not practical, a decision must be made. Candidates should not take a negative decision personally. Under other circumstances, and in comparison with other people, we might well have hired them.<br />
<br />
Candidates should also realize that they are not going to get any feedback from us in the event of a negative decision. There is no benefit to us for providing feedback, and there are significant risks in doing so. The biggest risk is simply that the feedback might not be properly understood or contextualized by the candidate. Candidates not receiving an offer have to grasp that there was someone else available who was a better fit, and move on to considering their other options.<br />
<br />
Every search, while stressful and time-consuming, is an experience I consistently enjoy. It is a great opportunity to meet some very interesting and capable people. I have sometimes had productive professional relationships with people I met during a search process who did not wind up hired as a result of it. I wish all candidates the best of luck in their searches!</div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com2tag:blogger.com,1999:blog-5235423068973972362.post-20049371716946038442018-11-06T14:22:00.000-06:002018-11-06T14:22:15.523-06:00An excellent guide to setting up OpenCV on AndroidThis post will be short and to the point.<br />
<br />
I've been trying to get OpenCV going in Android Studio for quite some time. I finally found an <a href="https://android.jlelse.eu/a-beginners-guide-to-setting-up-opencv-android-library-on-android-studio-19794e220f3c" target="_blank">article that clearly described how to get it done</a>. Special thanks to <a href="https://android.jlelse.eu/@elvischidera" target="_blank">Elvis Chidera</a> for his great work on that tutorial!<br />
<br />
Now it is time to start on the actually interesting work. <br />
<br />Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-54511419403885381832018-10-24T04:48:00.002-05:002018-10-24T04:49:32.534-05:00A subtle and interesting race condition<br />
Race conditions are an important and common topic when discussing multithreaded programming. Every instructor benefits by including realistic examples when lecturing on this subject. The best source of realistic examples is, arguably, real examples from real code. In the spirit of recording such an example both for my benefit and for that of anyone reading this, let me describe for you a race condition I fixed today.<br />
<div>
<br /></div>
<div>
The program is an Android app that sends commands to an Arduino board to control a robot. When the user is ready to begin controlling the robot, it starts up a thread to handle the communication. The communication thread maintains a TreeSet data structure (<code>trueFlags</code>) that tracks which sensory conditions are true. On each iteration, it updates the user interface to display these conditions for the user.</div>
<div>
<br /></div>
<div>
In an Android app, to update the user interface from a separate thread requires specifying a block of code for the UI to run when it is ready. In our example, the code looks like this:</div>
<div>
<br /></div>
<pre> private void updateGUI(final Action currentAction) {
getActivity().runOnUiThread(new Runnable() {
@Override
public void run() {
allTrueFlags.setText(trueFlags.toString());
StringBuilder values = new StringBuilder();
for (int i : sensorValues) {
values.append(i + ", ");
}
bytesReceived.setText(values.toString());
bytesSent.setText(currentAction.toString());
}
});
}
</pre>
<div>
<br />
It looks pretty harmless. After all, only the UI data structures are being modified, and only on a thread set aside for that purpose! But it caused our app to crash at seemingly random intervals as the robot wandered around a room.<br />
<br />
The trouble was the call to <code>trueFlags.toString()</code>. This TreeSet is constantly being modified in the communication thread. On the rare occasions when these modifications were interrupted to run the UI thread, a ConcurrentModificationException was thrown when trying to construct a string from it. Often, the robot would run for minutes at a time before this occurred!<br />
<br />
It was not difficult to fix this bug, but it took quite a lot of effort to find it! Hopefully, posting this example will help someone else out there identify a similar bug sometime. Here is the fixed code that avoids the bug, by moving the string conversion back into the communication thread:<br />
<br />
<br /></div>
<pre>
private void updateGUI(final String trueFlagString, final Action currentAction) {
getActivity().runOnUiThread(new Runnable() {
@Override
public void run() {
allTrueFlags.setText(trueFlagString);
StringBuilder values = new StringBuilder();
for (int i : sensorValues) {
values.append(i + ", ");
}
bytesReceived.setText(values.toString());
bytesSent.setText(currentAction.toString());
}
});
}
</pre>Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-69904183945526281982018-08-16T10:21:00.002-05:002018-08-17T09:10:58.656-05:00Probability and Boolean LogicTo understand probability, it is helpful to understand boolean logic. In this post, I will review both and show the connections. This is a first draft of the explanation I have in mind. I welcome suggestions to improve the presentation of these ideas.<br />
<br />
A probability is a real number between 0 and 1 inclusive. This number represents uncertain knowledge of an outcome. The sum of the probabilities of all possible outcomes of an event is 1.<br />
<br />
A classic example is the event of flipping of a coin. There are two possible outcomes: heads and tails. Without performing any experiments, we would estimate the probability of heads as 0.5 and tails as 0.5.<br />
<br />
Boolean logic relies on variables that have two possible values (<b>true</b>/<b>false</b> and <b>1</b>/<b>0</b> are the most popular; we'll rely on <b>true</b>/<b>false</b> for the rest of this post). These variables can be combined and manipulated using the <b>and</b>, <b>or</b>, and <b>not</b> operators. The <b>not</b> operator has one argument, and returns <b>true</b> if the argument is <b>false</b> and <b>false</b> if the argument is <b>true</b>. The <b>and</b> operator has two arguments, returning <b>true</b> if they are both <b>true</b> and <b>false</b> otherwise. The <b>or</b> operator has two arguments, returning <b>false</b> if they are both <b>false</b> and <b>true</b> otherwise.<br />
<br />
We can extend boolean logic to reason about probabilities. We will give arithmetic definitions of the three boolean operators for use with probabilities:<br />
<ul>
<li><b>x and y</b> -> <b>x * y </b>(multiplication)</li>
<li><b>x or y </b>-> <b>x + y </b>(addition)</li>
<li><b>not x </b>-> <b>-x</b> (negation)</li>
</ul>
<div>
So if we do two coin tosses, the probability of getting heads twice is:</div>
<div>
<ul>
<li>heads and heads</li>
<li>0.5 * 0.5</li>
<li>0.25</li>
</ul>
<div>
The same reasoning applies to getting tails twice, yielding the same probability (0.25). The probability of getting either heads twice or tails twice is:</div>
</div>
<div>
<ul>
<li>heads and heads or tails and tails</li>
<li>0.25 + 0.25</li>
<li>0.5</li>
</ul>
<div>
Let's extend this line of reasoning to another example: the rolling of a six-sided die. I'll use fractions to describe the probabilities in order to avoid gratuitous repeating decimals. The probability of any particular value showing up is <sup>1</sup>⁄<sub>6</sub>. To calculate the probability of a member of a set of values showing up, we can add them up individually, as this is just an <b>or</b> operation. So the probability of a 1 or a 4 is <sup>1</sup>⁄<sub>6 </sub> + <sup>1</sup>⁄<sub>6 </sub> = <sup>2</sup>⁄<sub>6</sub>.</div>
<div>
<br />
This gets more interesting when we want to compute probabilities such as "anything except a 6". Since that is equivalent to <b>not</b>, we calculate <sup>6</sup>⁄<sub>6 </sub> - <sup>1</sup>⁄<sub>6 </sub> = <sup>5</sup>⁄<sub>6</sub>. An alternative is to sum the probabilities of those values, but using <b>not</b> makes the calculation much simpler.<br />
<br />
In general, by using <b>not</b> we can greatly simplify our calculations. Consider calculating the probability of getting 16 or less when rolling three dice. If we view it as "<b>not</b> (17 <b>or</b> 18)", the calculation becomes:<br />
<ul>
<li>p(18) = p(6, 6, 6) = p(6) * p(6) * p(6) = <sup>1</sup>⁄<sub>6 </sub> * <sup>1</sup>⁄<sub>6 </sub>* <sup>1</sup>⁄<sub>6 </sub> = <sup>1</sup>⁄<sub>216</sub>.</li>
<li>p(17) = p(6, 5, 5) + p(5, 6, 5) + p(5, 5, 6) = <sup>3</sup>⁄<sub>216</sub>.</li>
<li>p(16 or less) = <b>not</b> (p(17) <b>or</b> p(18)) = 1 - (<sup>1</sup>⁄<sub>216 </sub> + <sup>3</sup>⁄<sub>216</sub>) = 1 - (<sup>4</sup>⁄<sub>216</sub>) = <sup>212</sup>⁄<sub>216</sub> = <sup>53</sup>⁄<sub>54</sub>.</li>
</ul>
<div>
<u>Two important caveats:</u><br />
<div>
<ol>
<li>To represent <b>and</b> as multiplication, the events must be <u>independent</u> of each other. This applies, for example, to coin flipping, because nothing about the first flip has any causative effect on the outcome of the second flip. </li>
<li>To represent <b>or</b> as addition, the events must be <u>mutually exclusive</u>. For example, a die roll cannot be both a 1 and a 4 at the same time.</li>
</ol>
</div>
<br />
<div>
</div>
<br />
<div style="-webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; color: black; font-family: -webkit-standard; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px;">
So, to conclude for now, I personally find it helpful to leverage the convertibility between boolean logic and probability to simplify my calculations and save effort.<br />
<br /></div>
</div>
</div>
</div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-23780223593593562612018-05-23T07:39:00.001-05:002018-05-23T09:57:12.359-05:00Real-time ClusteringClustering algorithms can be conceptualized as a technique for reducing input data in a high-dimensional space into a lower-dimensional space. From the viewpoint of robot programming, clustering is useful for transforming sensor data with a wide range into a small number of categories, each of which can be associated with a suitable action.<br />
<br />
In my research over the last several years, I have explored numerous variations of this approach. I have experimented with several different clustering algorithms as well as several different techniques for action selection. The goal of this research agenda is to make it easier to program a robot to exhibit a desired behavior given complex sensor inputs.<br />
<br />
My first work in this area was to apply clustering as a technique for enabling sonar values to be used as state indices for a robot employing the popular reinforcement learning algorithm <a href="https://en.wikipedia.org/wiki/Q-learning" target="_blank">Q-Learning</a>. <a href="http://ozark.hendrix.edu/~ferrer/research/papers/ccscms10.pdf" target="_blank">In the research I did on this subject</a>, I employed the <a href="http://www.scholarpedia.org/article/Kohonen_network" target="_blank">Kohonen Self-Organizing Map</a> (SOM) as the clustering algorithm that performed that transformation.<br />
<br />
Part of the appeal of the SOM was its ability to learn and adapt the clusters on every cycle as new sonar data arrived. I became intrigued by the possible applicability of this idea to images. To that end, I stopped investigating the Q-Learning context and pursued the idea of <a href="http://ozark.hendrix.edu/~ferrer/research/papers/ferrerMaics2014.pdf" target="_blank">enabling a user to directly specify actions for each cluster</a>. I employed the <a href="https://papers.nips.cc/paper/893-a-growing-neural-gas-network-learns-topologies.pdf" target="_blank">Growing Neural Gas</a> algorithm in that work, as I was intrigued by its potential to adaptively determine an appropriate number of clusters. I followed up by replacing the manual action-selection GUI I built with an <a href="http://ozark.hendrix.edu/~ferrer/research/papers/robotGNG.pdf" target="_blank">imitation learner</a>.<br />
<br />
In continuing to work with GNG, I became frustrated with its large number of hyperparameters. I found it tedious and frustrating to try to figure out appropriate values. Furthermore, although I had initially been intrigued by its flexibility in terms of the total number of clusters, I was starting to find this to be a liability. With a variable number of clusters, the cycle time becomes unpredictable. I concluded it was preferable to be able to bound the cycle time based on knowing ahead of time the total number of clusters.<br />
<br />
To address these concerns, <a href="http://ozark.hendrix.edu/~ferrer/research/papers/RealTimeCluster.pdf" target="_blank">I invented my own clustering algorithm</a>, <a href="https://github.com/gjf2a/maics2016" target="_blank">Bounded Self-Organizing Clusters</a> (BSOC), and benchmarked its performance against the SOM. The key ideas of BSOC are as follows:<br />
<br />
<ul>
<li>There is a fixed number of clusters. </li>
<ul>
<li>This is the only hyperparameter.</li>
</ul>
<li>Each input is added to the set of clusters as it arrives.</li>
<ul>
<li>If the maximum number of clusters is exceeded, the two clusters closest to each other according to the distance metric are merged. </li>
<li>Both the distance and the merge are weighted by the number of "ancestors" that the clusters have.</li>
</ul>
</ul>
My student Eric Huynh and I then employed BSOC <a href="https://github.com/E-R-C/FLAIRS30-BSOC" target="_blank">to implement an imitation learner</a>, <a href="https://aaai.org/ocs/index.php/FLAIRS/FLAIRS17/paper/view/15507" target="_blank">which we assessed with a large number of volunteers</a>.<br />
<br />
Motivated by the need to get a better understanding of the dynamics of the BSOC clustering process, I decided to benchmark it against the well-known <a href="https://en.wikipedia.org/wiki/K-means_clustering" target="_blank">k-means</a> clustering algorithm. To simplify the analysis, instead of the complete image clustering I had been doing in previous work, I focused instead on the problem of color quantization. I created two videos with my Android phone as test cases for the benchmarking process. As the phone's resolution is 1920x1080, clustering every pixel over 10 frames of video (spaced 4.5 seconds apart) results in over 20 million values to cluster. That proved to be about as much as my k-means implementation could handle before running out of heap space. (Maybe Java wasn't the best language in which to program this.)<br />
<br />
Wanting to process more frames, I concluded I needed another benchmark algorithm. I quickly implemented an algorithm I called <a href="https://github.com/gjf2a/flairs2018/blob/master/src/edu/hendrix/cluster/RandomIncrementalClusterer.java" target="_blank">Random Incremental Clustering</a> (RIC). The concept is very simple:<br />
<br />
<ul>
<li>Specify a maximum number of clusters <i>k</i>.</li>
<li>Initialize the number of attempts <i>a </i>to zero.</li>
<li>As each new input arrives:</li>
<ul>
<li>Increase <i>a</i> by one. </li>
<li>If fewer than the maximum number of clusters is in place, add it to the clusters.</li>
<li>Otherwise, with probability <i>k/a</i>, replace at random one of the existing clusters with the newly received input.</li>
</ul>
</ul>
As the number of inputs received increases, it becomes increasingly rare for a new input to replace one of the veteran cluster centers. But it still happens occasionally. This has the effect of creating a uniform statistical sample of the inputs.<br />
<br />
Creating this algorithm enabled me to <a href="https://github.com/gjf2a/flairs2018" target="_blank">benchmark BSOC</a> with close to 200 million pixel inputs. The <a href="http://ozark.hendrix.edu/~ferrer/presentations/Flairs2018Poster.pdf" target="_blank">surprising result</a> was that as the number of clusters increased to 8, the performance of RIC began to closely approximate both BSOC and k-means. (With 2 clusters, RIC performed very poorly.)<br />
<br />
I would not want to conclude too much from this result as of yet. This convergence of performance occurred with an extremely large number of inputs for the very simple RGB representation of a pixel's color. This result might not hold when clustering entire images, as I had been doing in prior work. The result might also improve with an approach to randomized clustering that does non-uniform sampling.<br />
<br />
I am looking forward to the next stages of this research project, in which I plan to explore further the questions that arose from this latest study. I continue to be fascinated by the possibilities that real-time clustering enables, and I plan to investigate both the techniques for clustering and its applications. If anyone reading this is interested in collaborating or comparing results, definitely let me know!<br />
<br />
Here is a summary of the papers and posters I have written on the topic of this post:<br />
<ul>
<li><span style="background-color: white;">Gabriel J. Ferrer. "Performance Evaluation of a Real-Time Clustering Algorithm." In FLAIRS-31 (Melbourne, FL, May 21-23, 2018) (<a href="http://ozark.hendrix.edu/~ferrer/presentations/Flairs2018Poster.pdf" target="_blank">Poster PDF</a>)</span></li>
<li><span style="background-color: white;">Gabriel J. Ferrer and Eric Huynh. "Real-Time Imitation Learning of Visual Behavior by a Mobile Robot." In </span><em><a href="http://www.aaai.org/Library/FLAIRS/flairs17contents.php">Proceedings of the Thirtieth International Florida Artificial Intelligence Research Society Conference</a></em><span style="background-color: white;"> (Marco Island, FL, May 22-24, 2017) </span><span style="background-color: white;">(</span><a href="https://aaai.org/ocs/index.php/FLAIRS/FLAIRS17/paper/view/15507">PDF</a><span style="background-color: white;">, </span><a href="https://github.com/E-R-C/FLAIRS30-BSOC">implementation</a><span style="background-color: white;">)</span></li>
<li><span style="background-color: white;">Gabriel J. Ferrer. "Real-Time Unsupervised Clustering." In <em><a href="http://ceur-ws.org/Vol-1584/">27th Modern Artificial Intelligence and Cognitive Science Conference (MAICS-2016)</a></em> (Dayton, OH, April 22-23, 2016) (<a href="http://ozark.hendrix.edu/~ferrer/research/papers/RealTimeCluster.pdf">PDF</a>, <a href="https://github.com/gjf2a/maics2016">implementation</a>)</span></li>
<li><span style="background-color: white;">Gabriel J. Ferrer. “Towards Human-Induced Vision-Guided Robot Behavior.” In <em>Proceedings of the 2014 AAAI Fall Symposium: Knowledge, Skill, and Behavior Transfer in Autonomous Robots</em> (Arlington, VA, November 13-15, 2014). (<a href="http://ozark.hendrix.edu/~ferrer/research/papers/robotGNG.pdf">PDF</a>)</span></li>
<li><span style="background-color: white;">Gabriel J. Ferrer, "Creating Visual Reactive Robot Behaviors Using Growing Neural Gas," <em>25th Modern Artificial Intelligence and Cognitive Science Conference (MAICS2014)</em> (Spokane, WA, April 26, 2014) (<a href="http://ozark.hendrix.edu/~ferrer/research/papers/ferrerMaics2014.pdf">PDF</a>)</span></li>
<li><span style="background-color: white;">Gabriel J. Ferrer, "Encoding Robotic Sensor States for Q-Learning Using the Self-Organizing Map," <em>Journal of Computing Sciences in Colleges</em> 25:5 (May 2010) 133-139. (<a href="http://ozark.hendrix.edu/~ferrer/research/papers/ccscms10.pdf">PDF</a>)</span></li>
</ul>
<br />Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-79078225780226157392018-03-13T11:56:00.004-05:002018-03-13T11:56:56.265-05:00Loading image files in JavaFXLoading image files into JavaFX applications is not too difficult, but there is a lot of confusing and contradictory advice out there. Even worse, SceneBuilder encodes the files in a manner that is incompatible with how they will be loaded in the Java code. So I would recommend making direct references in the Controller to the files that one is loading.<br />
<br />
Image files are easy to load if you place them in the same package as your code. Given that, an example like the following will do the trick:<br />
<br />
<pre>
import javafx.fxml.FXML;
import javafx.scene.image.Image;
import javafx.scene.image.ImageView;
import javafx.scene.layout.Pane;
public class Controller {
@FXML
private Pane pane;
private ImageView img;
@FXML
void initialize() {
img = new ImageView(new Image(Controller.class.getResourceAsStream("Screen.png")));
pane.getChildren().add(img);
}
}
</pre>
<br />Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-3938911416726853962018-03-13T11:13:00.000-05:002018-03-14T08:55:38.014-05:00Handling Key Events in JavaFXHandling keyboard events is typically a tricky issue in any GUI environment, because it is not always clear which component is supposed to receive those events. This is typically handled by the concept of <b>focus</b>. That is, a component with the focus is the component that receives those events.<br />
<br />
I have put together a short example as to how to make this work well in JavaFX. In this example, when the mouse hovers over a component, that component receives the focus. It retains the focus until another component requests it.<br />
<br />
The two Circle objects change their color when they have the focus and an appropriate key is pressed. The Pane responds to keystrokes by printing them out on the console.<br />
<br />
Although it is not part of this example, it is worth mentioning that clicking on a TextField or TextArea will always give that component the focus.<br />
<br />
The below example is a Controller. I leave the main() and FXML file as <a href="http://gjf2a.blogspot.com/2015/01/creating-minimal-javafx-user-interface.html" target="_blank">exercises for the reader</a>.<br />
<br />
<br />
<pre>import javafx.fxml.FXML;
import javafx.scene.input.KeyCode;
import javafx.scene.input.KeyEvent;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
public class Controller {
@FXML
Pane pane;
@FXML
Circle one;
@FXML
Circle two;
@FXML
void initialize() {
one.setOnMouseEntered(event -> one.requestFocus());
two.setOnMouseEntered(event -> two.requestFocus());
one.setOnKeyPressed(event -> decodeColor(event, one));
two.setOnKeyPressed(event -> decodeColor(event, two));
pane.setOnMouseEntered(event -> pane.requestFocus());
pane.setOnKeyPressed(event -> System.out.println("typed " + event.getText()));
}
void decodeColor(KeyEvent key, Circle obj) {
if (key.getCode() == KeyCode.R) {
obj.setFill(Color.RED);
}
if (key.getCode() == KeyCode.B) {
obj.setFill(Color.BLUE);
}
if (key.getCode() == KeyCode.G) {
obj.setFill(Color.GREEN);
}
}
}
</pre>
<br />
<br />Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-2991438901862200432018-02-20T23:16:00.002-06:002018-02-20T23:16:54.230-06:00The JavaFX canvas and mouse clicksThe <code>Canvas</code> class in JavaFX is a very flexible platform for drawing whatever one would like. It is not that difficult to use, but there are a few elements that are a bit confusing.<br />
<br />
To take advantage of this example, start by <a href="http://gjf2a.blogspot.com/2015/01/creating-minimal-javafx-user-interface.html" target="_blank">creating an FXML file</a> containing a <code>Canvas</code> and a <code>Button</code>. Then connect it to the CanvasDemoController class below:<br />
<br />
<pre>package canvas;
import javafx.fxml.FXML;
import javafx.scene.canvas.Canvas;
public class CanvasDemoController {
@FXML
Canvas canvas;
@FXML
void move() {
d.move(10, 10);
refresh();
}
void refresh() {
canvas.getGraphicsContext2D()
.clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
d.draw(canvas);
}
Drawing d = new Drawing();
@FXML
void initialize() {
canvas.setOnMouseClicked(event -> {
d.teleport(event.getX(), event.getY());
refresh();
});
}
}
</pre>
<br />
The class above references the <code>Drawing</code> class, shown below:<br />
<br />
<pre>package canvas;
import javafx.scene.canvas.Canvas;
public class Drawing {
private double x, y, radius;
public Drawing() {
x = y = 0.0;
radius = 10.0;
}
public void move(double dx, double dy) {
x += dx;
y += dy;
}
public void teleport(double x, double y) {
this.x = x;
this.y = y;
}
public void draw(Canvas canvas) {
canvas.getGraphicsContext2D()
.fillOval(x - radius, y - radius, radius*2, radius*2);
}
}
</pre>
<br />
The combined example illustrates several useful ideas:<br />
<ul>
<li>Creating graphics on a <code>Canvas</code> is not that difficult, but the <code>Graphics2DContext</code> object must be acquired from it in order to draw anything. </li>
<li>Drawings on a <code>Canvas</code> persist until erased. Erase and redraw as necessary to animate.</li>
<li>Mouse click events are pretty easy to handle, as the coordinates of the mouse click are easily obtained from the <code>event</code> parameter. However, we need to code the event handler explicitly in the controller class.</li>
</ul>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-74584465173227122612018-02-01T21:34:00.000-06:002018-02-01T21:34:49.371-06:00JavaFX and TableViewThe <code><a href="https://docs.oracle.com/javase/9/docs/api/javafx/scene/control/TableView.html" target="_blank">TableView</a></code> control in JavaFX is a flexible and powerful interface. Every TableView object is parameterized by a data type that represents a row of the table. The <a href="https://docs.oracle.com/javase/9/docs/api/javafx/scene/control/TableView.html" target="_blank">documentation</a> encourages developers to create row objects that represent each column using <a href="https://docs.oracle.com/javase/9/docs/api/javafx/beans/value/ObservableValue.html" target="_blank">ObservableValue</a> types. Following the documentation, it is necessary to create three methods (a setter and two different getters) for each of these values.<br />
<br />
I find this approach exceedingly verbose, and in this blog post I will demonstrate an alternative that is hinted at in the documentation. I will assume that the reader is comfortable <a href="http://gjf2a.blogspot.com/2015/01/creating-minimal-javafx-user-interface.html" target="_blank">creating a JavaFX interface using SceneBuilder</a>. I will just present the controller to which the FXML file can be attached.<br />
<br />
This is a simple application that lets the user enter names and ages, which are then displayed in the table. The table is not editable. First, we define a data type for the table rows:<br />
<br />
<pre>public class NameAgeRow {
private String name;
private int age;
public NameAgeRow(String name, int age) {
this.name = name;
this.age = age;
}
public NameAgeRow(String name, String age) {
this(name, Integer.parseInt(age));
}
public String getName() {return name;}
public int getAge() {return age;}
}
</pre>
<br />
Next, we define the Controller for the application:<br />
<br />
<pre>import javafx.beans.property.SimpleIntegerProperty;
import javafx.beans.property.SimpleStringProperty;
import javafx.fxml.FXML;
import javafx.scene.control.Button;
import javafx.scene.control.TableColumn;
import javafx.scene.control.TableView;
import javafx.scene.control.TextField;
public class Controller {
@FXML
TableView<NameAgeRow> table;
@FXML
TableColumn<NameAgeRow,String> names;
@FXML
TableColumn<NameAgeRow,Integer> ages;
@FXML
TextField name;
@FXML
TextField age;
@FXML
Button add;
@FXML
void initialize() {
add.setOnAction(e -> {
table.getItems().add(new NameAgeRow(name.getText(),
age.getText()));
name.setText("");
age.setText("");
});
names.setCellValueFactory(cdf ->
new SimpleStringProperty(cdf.getValue().getName()));
ages.setCellValueFactory(cdf ->
new SimpleIntegerProperty(cdf.getValue().getAge()).asObject());
}
}</pre>
<br />
The overall structure is straightforward. For each column, we define a lambda that obtains the value from the <code>NameAgeRow</code> object for the current table row. A real convenience of this approach is that it can be made to work with any user-defined class that represents the row data. I find this more convenient and flexible than what is described in the documentation. Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-63349964804284376772017-12-31T14:28:00.000-06:002017-12-31T14:28:50.049-06:00On Academic Integrity and Being a Good Person<br />
I recently had a conversation with a person who teaches 8th-grade English. She related to me an incident in which she discovered that a student had plagiarized an essay. After confronting (and penalizing) the student for the offense, she asked the student if she had learned anything. The reply was, "I learned that I should not plagiarize <b>in your class</b>." Upon discerning that her teacher did not find her reply to be satisfactory, she added, "Do you think this makes me a <b>bad person</b>?"<div>
<br /></div>
<div>
As an educator concerned with the integrity of the educational process, it seems easy to say "yes", because honesty is "good" and cheating is "bad". But if cheating makes a student successful at the cost of acquiring an unwanted label of "bad", then what is the real cost? In fact, an excuse for cheating I have heard before from a guilty party is "everyone else is doing it, so I have to cheat to keep up."</div>
<div>
<br /></div>
<div>
Given this mindset, I propose that any argument against cheating intended to persuade a perpetrator to stop has to demonstrate <b>direct damage to the cheating student</b>. </div>
<div>
<br /></div>
<div>
Implicit in the act of submitting a solution to an assignment is <b>to claim that the submitter created the solution in accordance with the instructions</b>. Students cheat when it is easier to submit someone else's solution to an assignment than it is to create their own solution. To cheat, then, is to <b>lie. </b></div>
<div>
<b><br /></b></div>
<div>
What makes this lie so pernicious? When I, as an educator, create an assignment, I design the assignment so that correct solutions demonstrate that the student has <b>acquired an ability</b>. When a student cheats, the student <b>falsely claims to have acquired that ability</b>.</div>
<div>
<br /></div>
<div>
<div>
Any reflective person is aware of the power of <b>habitual behavior.</b> When we repeatedly select an action in response to a condition, the selection of that action becomes an unconscious response. One need only reflect on how quickly we respond to boredom by reaching for our smartphones to visualize the truth of this claim.</div>
<div>
<br /></div>
</div>
<div>
A student who cheats one time without being caught has already begun the process of forming the <b>habit of cheating</b>. The habit of cheating is equivalent to the <b>habit of falsely claiming abilities</b>. So what does it mean to have acquired this habit?</div>
<div>
<br /></div>
<div>
It means that, down the line, one's school transcript, in which <b>grades correspond to false claims about acquired abilities</b>, based on that transcript one can be hired for jobs <b>for which one is not actually qualified</b>. Such a job may be appealing for a good salary, but they will have hired a person who can't actually do the work. And the truth has a way of catching up with us, in time. An employer who hires someone who can't do the work will eventually figure this out and <b>fire the person</b>. Why will they figure it out? Nobody likes wasting money.</div>
<div>
<br /></div>
<div>
So, does cheating make a student a "bad person"? <b>Yes</b>. To be more precise, cheating makes a student a person with a habit that damages both the student and everyone around the student, as a result of claiming abilities that are not consistent with reality. </div>
<div>
<br /></div>
<div>
But it is important to emphasize that a <a href="https://en.wikipedia.org/wiki/Mindset#Fixed_and_growth" target="_blank">growth mindset</a> applies to our moral habits just as much as it does to our abilities. If we have acquired bad moral habits (and most of us have), we have the freedom to choose actions that help us alter our habits, to transform the bad habits into good habits. So I would hate to close this essay without emphasizing the fact that the only thing stopping a person with bad habits from becoming a person with good habits is that the person with good habits has made <b>a concrete decision to change for the better</b>.</div>
<div>
<br /></div>
<div>
Another implication of this argument is that <b>educators can do tremendous good for students who cheat by catching and punishing them as early as possible</b>. This gives the student a chance to break the bad habit of cheating before it becomes too ingrained. It is a <b>false mercy</b> to go easy on a cheating student! </div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com1tag:blogger.com,1999:blog-5235423068973972362.post-13560104998026605572017-12-31T11:03:00.001-06:002017-12-31T11:03:20.020-06:00Tractability and learning programming<br />
My oldest son, currently in 3rd grade, is enthusiastically learning programming from Code.org. He has completed Courses 2 and 3 and is currently working on Course 4.<br />
<div>
<br /></div>
<div>
I was having a conversation with my colleague Brent Yorgey about the sudden increase in difficulty in the introductory CS class when we get to while loops. We spent some time discussing the fact that there is no getting around it being hard. He then pointed out that this is the concept that causes the difficulty of algorithm analysis to transition from completely tractable to undecidable. </div>
<div>
<br /></div>
<div>
Interestingly, so far in Code.org every problem my son has had to solve has been in the logically-tractable category.</div>
<div>
<br /></div>
<div>
Related to this, I saw this interesting <a href="https://www.quora.com/How-do-I-know-if-I-can-become-a-programmer/answer/Barry-Rountree">answer</a> by <a href="https://www.quora.com/profile/Barry-Rountree">Barry Roundtree</a> to a <a href="https://www.quora.com/How-do-I-know-if-I-can-become-a-programmer">question</a> on Quora about what it takes to become a programmer:</div>
<blockquote class="tr_bq">
<div class="qtext_para" style="color: #333333; font-family: q_serif, Georgia, Times, 'Times New Roman', serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
In my experience, good programmers don’t bother asking if they can do something or not, and they don’t spend a lot of thought on whether or not they’re wasting time.</div>
<div class="qtext_para" style="color: #333333; font-family: q_serif, Georgia, Times, 'Times New Roman', serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
There are a lot of professions out there where learning skill <span class="render_latex"><span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-1-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="-webkit-transition: none; border: 0px; line-height: normal; margin: 0px; max-height: 5000em; max-width: 5000em; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-1" role="math" style="-webkit-transition: none; border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.599em;"><span style="-webkit-transition: none; border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.491em;"><span style="-webkit-transition: none; border: 0px; clip: rect(1.846em, 1000.491em, 2.604em, -999.997em); left: 0.003em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.436em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-2" style="-webkit-transition: none; border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-3" style="-webkit-transition: none; border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="-webkit-transition: none; border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="-webkit-transition: none; border: 0px; display: inline-block; height: 2.442em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="-webkit-transition: none; border-left-style: solid; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="-webkit-transition: none; -webkit-user-select: none; border: 0px !important; clip: rect(1px, 1px, 1px, 1px); display: block !important; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 1px 0px 0px !important; position: absolute !important; top: 0px; transition: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span></span> is expected to take <span class="render_latex"><span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math>" id="MathJax-Element-2-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="-webkit-transition: none; border: 0px; line-height: normal; margin: 0px; max-height: 5000em; max-width: 5000em; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-4" role="math" style="-webkit-transition: none; border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.545em;"><span style="-webkit-transition: none; border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.436em;"><span style="-webkit-transition: none; border: 0px; clip: rect(1.846em, 1000.436em, 2.821em, -999.997em); left: 0.003em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.436em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-5" style="-webkit-transition: none; border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-6" style="-webkit-transition: none; border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">y </span></span><span style="-webkit-transition: none; border: 0px; display: inline-block; height: 2.442em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="-webkit-transition: none; border-left-style: solid; border-width: 0px; display: inline-block; height: 0.937em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="-webkit-transition: none; -webkit-user-select: none; border: 0px !important; clip: rect(1px, 1px, 1px, 1px); display: block !important; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 1px 0px 0px !important; position: absolute !important; top: 0px; transition: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math></span></span></span>hours and lead to salary <span class="render_latex"><span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>z</mi></math>" id="MathJax-Element-3-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="-webkit-transition: none; border: 0px; line-height: normal; margin: 0px; max-height: 5000em; max-width: 5000em; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-7" role="math" style="-webkit-transition: none; border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.545em;"><span style="-webkit-transition: none; border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.436em;"><span style="-webkit-transition: none; border: 0px; clip: rect(1.846em, 1000.436em, 2.659em, -999.997em); left: 0.003em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.436em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-8" style="-webkit-transition: none; border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-9" style="-webkit-transition: none; border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">z</span></span><span style="-webkit-transition: none; border: 0px; display: inline-block; height: 2.442em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="-webkit-transition: none; border-left-style: solid; border-width: 0px; display: inline-block; height: 0.737em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.13em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="-webkit-transition: none; -webkit-user-select: none; border: 0px !important; clip: rect(1px, 1px, 1px, 1px); display: block !important; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 1px 0px 0px !important; position: absolute !important; top: 0px; transition: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>z</mi></math></span></span></span>. Music, math and chess are not those kind of professions, and programming is more like those than dentistry, auto body repair or being a CPA.</div>
<div class="qtext_para" style="color: #333333; font-family: q_serif, Georgia, Times, 'Times New Roman', serif; font-size: 15px; padding: 0px;">
As to brain wiring: if you have an unusually high level of curiosity and (for tasks that interest you) an exceptional capacity to tolerate failure, you’re good to go. Curious people don’t tend to be overly concerned with wasting time, and people who tolerate failure well don’t spent a lot of effort wondering if they can do something. They just start, and if they fail (and fail repeatedly), no big deal.</div>
</blockquote>
<div>
It seems, then, that succeeding in programming is about having the right attitude. This attitude of curiosity and willingness to fail enable us to persevere in finding heuristic solutions forward even to logically intractable problems. </div>
<div>
<br /></div>
<div>
Interestingly, many useful applications (e.g. spreadsheets, computer animation software) all enable users to do things that once required programming in the full sense. What they represent are domain-specific languages with a tractable logic. This enables them to be used by a wide audience of non-programmers.</div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com2tag:blogger.com,1999:blog-5235423068973972362.post-65291060406408492002017-06-23T08:54:00.000-05:002017-06-23T13:11:47.911-05:00Pen Drawing Robot (Mindstorms NXT)Back when the Mindstorms NXT was the latest and greatest Lego robot, I created the following model for a pen drawing robot. I haven't had the time to revise it for the EV3, which would require a fair amount of work. This is in part because the EV3 has a third motor with a very different footprint than the other two motors. It would be interesting to work on that, but in the meantime, here is a model that anyone should feel free to employ or modify.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrrDRFdMQ4XaqIcnD4OJzmtWb515KDfa4oVLXeyLd4YHvFduqP3cgnIRmxkthyOIbhyphenhyphenqBtK1svGYFNkki_ntVFwpWXXz8f9VSFVHXuTdxjFkQMIUD0-Wj9Xd2ZcAYdsJ1J0o2DgnM17PxY/s1600/Screen+Shot+2017-06-23+at+7.30.15+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="562" data-original-width="364" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgrrDRFdMQ4XaqIcnD4OJzmtWb515KDfa4oVLXeyLd4YHvFduqP3cgnIRmxkthyOIbhyphenhyphenqBtK1svGYFNkki_ntVFwpWXXz8f9VSFVHXuTdxjFkQMIUD0-Wj9Xd2ZcAYdsJ1J0o2DgnM17PxY/s320/Screen+Shot+2017-06-23+at+7.30.15+AM.png" width="207" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB1eGsWyJmYVmc_HpTWUjcIQgzx18gHsjSLiapi0qt_UOOGygVqdaZC4ed9j35HK73kuPwmB0srl142u9evP-QslQtBYM_rTRnGldkUVHb24dT4CuIHv7y4nDbE9RfnHv1GetV0FvmSsiK/s1600/Screen+Shot+2017-06-23+at+7.30.27+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="572" data-original-width="348" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB1eGsWyJmYVmc_HpTWUjcIQgzx18gHsjSLiapi0qt_UOOGygVqdaZC4ed9j35HK73kuPwmB0srl142u9evP-QslQtBYM_rTRnGldkUVHb24dT4CuIHv7y4nDbE9RfnHv1GetV0FvmSsiK/s320/Screen+Shot+2017-06-23+at+7.30.27+AM.png" width="194" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1QCJvYxJxTv7K_S1vSGmS9yfFTErPSvAUqDVH0CozmEBdHJSRfh7ur11SNkNXYpZVkwkN6F66SwNZsT2jOLvxhn3bhfb0tAvdeBrPRsZyJneGUb80HgwyhzoH0XZlkpyKCsP2DGR6Uqs1/s1600/Screen+Shot+2017-06-23+at+7.30.35+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="784" data-original-width="386" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1QCJvYxJxTv7K_S1vSGmS9yfFTErPSvAUqDVH0CozmEBdHJSRfh7ur11SNkNXYpZVkwkN6F66SwNZsT2jOLvxhn3bhfb0tAvdeBrPRsZyJneGUb80HgwyhzoH0XZlkpyKCsP2DGR6Uqs1/s320/Screen+Shot+2017-06-23+at+7.30.35+AM.png" width="157" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaCgnTsg1GB2JRXLdY-tjRir3awzReSbfqCG7W1lV2a0jxqVlaXly2Se3fL-LIaC5eLJwde1LJ2i3cqvRa99M7tvdaKcbAnXcO9Z5RLkc1fPseq7q5OiHRMdGJGOTpWUTl0YVNP7gZhq-j/s1600/Screen+Shot+2017-06-23+at+7.30.43+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="776" data-original-width="364" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaCgnTsg1GB2JRXLdY-tjRir3awzReSbfqCG7W1lV2a0jxqVlaXly2Se3fL-LIaC5eLJwde1LJ2i3cqvRa99M7tvdaKcbAnXcO9Z5RLkc1fPseq7q5OiHRMdGJGOTpWUTl0YVNP7gZhq-j/s320/Screen+Shot+2017-06-23+at+7.30.43+AM.png" width="150" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiiDsTCTHLwx30g2Y3YVCgO_IF9nJWL_RYcdw4rF_97Z9Eq3SLXaeQF-VlYk4fJWHKn9JMwJrx5AWdZvt_RvKSVdUm8Fvlh78V7OE9kX9a4nIYwfSv_YKOqZo2KTqcMAdJgNq-XkawrCBMo/s1600/Screen+Shot+2017-06-23+at+7.30.56+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="786" data-original-width="460" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiiDsTCTHLwx30g2Y3YVCgO_IF9nJWL_RYcdw4rF_97Z9Eq3SLXaeQF-VlYk4fJWHKn9JMwJrx5AWdZvt_RvKSVdUm8Fvlh78V7OE9kX9a4nIYwfSv_YKOqZo2KTqcMAdJgNq-XkawrCBMo/s320/Screen+Shot+2017-06-23+at+7.30.56+AM.png" width="187" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4_1cam9Czx1pV0V8a4aMW505k3hP173aR2TRhV32RWNNe9t5ZJd-IwAWkzYZismKNepW4ZAC8b_ArU98ieRYw4OiPGJyq108sm8ZVvXGJFpCMiVdyr5mPHXMy8P7e7H-AGvMuR9BVJ3VT/s1600/Screen+Shot+2017-06-23+at+7.31.06+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="782" data-original-width="540" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4_1cam9Czx1pV0V8a4aMW505k3hP173aR2TRhV32RWNNe9t5ZJd-IwAWkzYZismKNepW4ZAC8b_ArU98ieRYw4OiPGJyq108sm8ZVvXGJFpCMiVdyr5mPHXMy8P7e7H-AGvMuR9BVJ3VT/s320/Screen+Shot+2017-06-23+at+7.31.06+AM.png" width="220" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJkNwc0lKMcmGolsQq6gvp-nP6DuLOlssNqWBhUDLq2Q_VKmN04DHWwPIbQFT4cO0Xw5eA-Q7XAcBZJX4P_u0v9Pf946yUCKJLdrM-7n6rcJUU8b1JeiYWGQE9g-uEPysz9t9CPwp8drza/s1600/Screen+Shot+2017-06-23+at+7.31.16+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="946" data-original-width="648" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJkNwc0lKMcmGolsQq6gvp-nP6DuLOlssNqWBhUDLq2Q_VKmN04DHWwPIbQFT4cO0Xw5eA-Q7XAcBZJX4P_u0v9Pf946yUCKJLdrM-7n6rcJUU8b1JeiYWGQE9g-uEPysz9t9CPwp8drza/s320/Screen+Shot+2017-06-23+at+7.31.16+AM.png" width="219" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjV-zM9eN8FBB2QXbhNzQn9j7rjieD9aBSKL-1QV_i_fQ4lEsQhq_ZqnN9NFLcfeSu0fSpncdbCCv2LGrvynArYGYU5AzyGyc6RKIY1v-cx2SPzZd07PFEKHFP7RrvRcLVlmTxPGJFSNWp/s1600/Screen+Shot+2017-06-23+at+7.31.24+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="926" data-original-width="658" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjV-zM9eN8FBB2QXbhNzQn9j7rjieD9aBSKL-1QV_i_fQ4lEsQhq_ZqnN9NFLcfeSu0fSpncdbCCv2LGrvynArYGYU5AzyGyc6RKIY1v-cx2SPzZd07PFEKHFP7RrvRcLVlmTxPGJFSNWp/s320/Screen+Shot+2017-06-23+at+7.31.24+AM.png" width="227" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjNDVQVcpMbaRK6La8duGv5rrEIeqGFa9wHkw__t3PHY2YP6BF_1yuy7i3XKsGO1LuSCnNWdfjOpL0FZT6mMdVnUUfjxcIwPn6wkQ5an5nqVkXJ-SkNxVeBnv-nbHa0Oh9Pe2gMMOUHlvy1/s1600/Screen+Shot+2017-06-23+at+7.31.30+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="932" data-original-width="666" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjNDVQVcpMbaRK6La8duGv5rrEIeqGFa9wHkw__t3PHY2YP6BF_1yuy7i3XKsGO1LuSCnNWdfjOpL0FZT6mMdVnUUfjxcIwPn6wkQ5an5nqVkXJ-SkNxVeBnv-nbHa0Oh9Pe2gMMOUHlvy1/s320/Screen+Shot+2017-06-23+at+7.31.30+AM.png" width="228" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiVFO9y1btaDMCZOO-OjlwkNmwJPFZw4sPzaKTyIhjpTMAPBSS98_NPTmzxrTBWu6KGpd_OReG6tD5jDSQpu0AyttRhwxH246BJ3_c1Fxt1FLrNvPfLSl9cqPt2gtaBRAQEY_fmUvXlHs72/s1600/Screen+Shot+2017-06-23+at+7.31.37+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="944" data-original-width="684" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiVFO9y1btaDMCZOO-OjlwkNmwJPFZw4sPzaKTyIhjpTMAPBSS98_NPTmzxrTBWu6KGpd_OReG6tD5jDSQpu0AyttRhwxH246BJ3_c1Fxt1FLrNvPfLSl9cqPt2gtaBRAQEY_fmUvXlHs72/s320/Screen+Shot+2017-06-23+at+7.31.37+AM.png" width="231" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-2KpPO5tjv6YAeKttxVgAi2lVvj97_DyrRDRWOLg25dFnMppE3LSoB3Jue7tjliigNn9X3JKO9Pn1GLaEsW3XyL9pXwaxALqNP4MvVdUKnnj_pgp_Gq3CzrsynFB8KtJv2qpeotPHYM45/s1600/Screen+Shot+2017-06-23+at+7.31.43+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1074" data-original-width="704" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-2KpPO5tjv6YAeKttxVgAi2lVvj97_DyrRDRWOLg25dFnMppE3LSoB3Jue7tjliigNn9X3JKO9Pn1GLaEsW3XyL9pXwaxALqNP4MvVdUKnnj_pgp_Gq3CzrsynFB8KtJv2qpeotPHYM45/s320/Screen+Shot+2017-06-23+at+7.31.43+AM.png" width="209" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyqxuC5QtivHP3cCVgNNpquAbJwsLaLb6vs9lfMEMMjY1Tbtibjfd6T1aeprpLgZ4inWPCsMC0faHZVWEsoLpoTfIcXTcA9mDS5b2GXXa3Hs6gz-RR-NiMRaWiDpplWzXRQHU8Dn-KO-gK/s1600/Screen+Shot+2017-06-23+at+1.05.52+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="132" data-original-width="144" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyqxuC5QtivHP3cCVgNNpquAbJwsLaLb6vs9lfMEMMjY1Tbtibjfd6T1aeprpLgZ4inWPCsMC0faHZVWEsoLpoTfIcXTcA9mDS5b2GXXa3Hs6gz-RR-NiMRaWiDpplWzXRQHU8Dn-KO-gK/s1600/Screen+Shot+2017-06-23+at+1.05.52+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_BlGA-Yfnik_6Ut1gAx9Ng-6w6spnuBc6nEDI0DDFaiexbjxzOMZbbwWywmKHnGZycXZbiZ27-DiebFThyphenhyphenk_Fy9n4z-L1DMBEOC-PnPchiSEG_9p5IUlpe1MM0pp1s6JlmhpCZHedbJyA/s1600/Screen+Shot+2017-06-23+at+1.05.58+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="150" data-original-width="228" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_BlGA-Yfnik_6Ut1gAx9Ng-6w6spnuBc6nEDI0DDFaiexbjxzOMZbbwWywmKHnGZycXZbiZ27-DiebFThyphenhyphenk_Fy9n4z-L1DMBEOC-PnPchiSEG_9p5IUlpe1MM0pp1s6JlmhpCZHedbJyA/s1600/Screen+Shot+2017-06-23+at+1.05.58+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikWZyoCG0jHkqw2750JIUMAz64xz4OByTNjq2t9BPBRyo2FPMq8zodoo197TgA3MHpogYtK4sEeJunQFGfTkFpAQig6gbYWYtM8CYvF6aYOfHbvYuEI_P9fCqF9OPRSmzbGvo521AoIlFa/s1600/Screen+Shot+2017-06-23+at+1.06.03+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="152" data-original-width="212" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikWZyoCG0jHkqw2750JIUMAz64xz4OByTNjq2t9BPBRyo2FPMq8zodoo197TgA3MHpogYtK4sEeJunQFGfTkFpAQig6gbYWYtM8CYvF6aYOfHbvYuEI_P9fCqF9OPRSmzbGvo521AoIlFa/s1600/Screen+Shot+2017-06-23+at+1.06.03+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2nbiCmk4J3f-jUtrh9fhHhEv0LQ3UtM2lE_huNGNj_z3I-15GePwnovrPMrpKdHGHHRmegf8EG0PZtSVPeBP71JSwJEUi240jiHhoY2spUYkmeV70ivkFYq18Se5IzqMm3k5LXg5_QxeR/s1600/Screen+Shot+2017-06-23+at+1.06.10+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="618" data-original-width="248" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2nbiCmk4J3f-jUtrh9fhHhEv0LQ3UtM2lE_huNGNj_z3I-15GePwnovrPMrpKdHGHHRmegf8EG0PZtSVPeBP71JSwJEUi240jiHhoY2spUYkmeV70ivkFYq18Se5IzqMm3k5LXg5_QxeR/s320/Screen+Shot+2017-06-23+at+1.06.10+PM.png" width="128" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjvQ2pO-erShJOsbYn7gGyVVSBpw8-YCSpaQr2dKF1RkVQLQ1dagHRzYS5bcd2SSmNSH3wcuAQo2FCkHHMgL-RbOzMMOzGEkqQvzF73EvvtzPOzlZHgJVWYdkbIRFFzZ08WvJa302YNG5P/s1600/Screen+Shot+2017-06-23+at+1.06.20+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="660" data-original-width="242" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjvQ2pO-erShJOsbYn7gGyVVSBpw8-YCSpaQr2dKF1RkVQLQ1dagHRzYS5bcd2SSmNSH3wcuAQo2FCkHHMgL-RbOzMMOzGEkqQvzF73EvvtzPOzlZHgJVWYdkbIRFFzZ08WvJa302YNG5P/s320/Screen+Shot+2017-06-23+at+1.06.20+PM.png" width="117" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiA0M7rm_kPhQIA6hYTMyeEfRWWnHCF0NZIKoY9oF55UXog2r8st0IOOaNEcg74A3lMQyqZxXNRAfX502DBa12QkjFmDqmuideZouY5dHIYByDBHutWjvpBrnGtGupp-QLo7ajeQPTdUNN3/s1600/Screen+Shot+2017-06-23+at+1.06.28+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="854" data-original-width="266" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiA0M7rm_kPhQIA6hYTMyeEfRWWnHCF0NZIKoY9oF55UXog2r8st0IOOaNEcg74A3lMQyqZxXNRAfX502DBa12QkjFmDqmuideZouY5dHIYByDBHutWjvpBrnGtGupp-QLo7ajeQPTdUNN3/s320/Screen+Shot+2017-06-23+at+1.06.28+PM.png" width="99" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvQtDaXPfDgSbXStgbD0btvWkgyzeosQFisL0wMLl2lE5cGLum4O7nxJDspUZl6vVcDN8r5JgZNfOjBS8w9_7bR0obsQsYh9vthKdNhk1VeYZLbKIdvcIw7sO8f5oYL6t28rOB9CQGnXDq/s1600/Screen+Shot+2017-06-23+at+1.06.37+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="856" data-original-width="268" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvQtDaXPfDgSbXStgbD0btvWkgyzeosQFisL0wMLl2lE5cGLum4O7nxJDspUZl6vVcDN8r5JgZNfOjBS8w9_7bR0obsQsYh9vthKdNhk1VeYZLbKIdvcIw7sO8f5oYL6t28rOB9CQGnXDq/s320/Screen+Shot+2017-06-23+at+1.06.37+PM.png" width="100" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhtE-cONm4AYFE0_bpAfNsWTFXRCUNWHRMMd2UBOCBJsneoC5fAkqOKnkZuf7q_WBrRHva1PJtzuOUf227968E9Q7Ud6JP4tCyxHrMQXKR3dpYaqLUj4KQcWKxMrW6uIvdRJXStPy0tWMh/s1600/Screen+Shot+2017-06-23+at+7.31.50+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1048" data-original-width="746" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhtE-cONm4AYFE0_bpAfNsWTFXRCUNWHRMMd2UBOCBJsneoC5fAkqOKnkZuf7q_WBrRHva1PJtzuOUf227968E9Q7Ud6JP4tCyxHrMQXKR3dpYaqLUj4KQcWKxMrW6uIvdRJXStPy0tWMh/s320/Screen+Shot+2017-06-23+at+7.31.50+AM.png" width="227" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4xMEKaeLbok3as-WblgY0Yes5E8r7oILYLGjfPRkClsQtfZm33q8hyphenhyphenpBlpSj93NjVLpLOlhkdsgFSOiy0xNGtqsm_KQvq8HoC_d7WiJpA9KB7GbU5RdJvbuuzm8i8n0lHq1XJ9PDNzH7I/s1600/Screen+Shot+2017-06-23+at+7.31.59+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1082" data-original-width="742" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj4xMEKaeLbok3as-WblgY0Yes5E8r7oILYLGjfPRkClsQtfZm33q8hyphenhyphenpBlpSj93NjVLpLOlhkdsgFSOiy0xNGtqsm_KQvq8HoC_d7WiJpA9KB7GbU5RdJvbuuzm8i8n0lHq1XJ9PDNzH7I/s320/Screen+Shot+2017-06-23+at+7.31.59+AM.png" width="219" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgX0tWFY_dZCSiOkpwd8lmL55Uahz5cVG39KgO7BTyyG3jWORM0k6rpWOdyhhRc9S2Dll2PZ95vPMh-4pSS4PYAAsuuiUsdULEz3wTvqj4b7TU5W8UsNFTY_r1no-VeSqqAzxM4M6ivBGiL/s1600/Screen+Shot+2017-06-23+at+7.32.10+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1142" data-original-width="982" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgX0tWFY_dZCSiOkpwd8lmL55Uahz5cVG39KgO7BTyyG3jWORM0k6rpWOdyhhRc9S2Dll2PZ95vPMh-4pSS4PYAAsuuiUsdULEz3wTvqj4b7TU5W8UsNFTY_r1no-VeSqqAzxM4M6ivBGiL/s320/Screen+Shot+2017-06-23+at+7.32.10+AM.png" width="275" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGuXRUQYAPQ-tK0fOyErpOcUawRYx5J7uvpeiufhWUzblYnzJbJws014EnQVPT9Uz2HmMO4gU1tNZwBbQHMre1zSos2z1vuODL8WQoZR4cwzFxCMZ03kvRClVkD35sF05tD7uNdU6MCMgb/s1600/Screen+Shot+2017-06-23+at+7.32.20+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1102" data-original-width="952" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGuXRUQYAPQ-tK0fOyErpOcUawRYx5J7uvpeiufhWUzblYnzJbJws014EnQVPT9Uz2HmMO4gU1tNZwBbQHMre1zSos2z1vuODL8WQoZR4cwzFxCMZ03kvRClVkD35sF05tD7uNdU6MCMgb/s320/Screen+Shot+2017-06-23+at+7.32.20+AM.png" width="276" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEyZSNZltEL0k_K8IryzIx9a4H45A8L4f1KmvOT91gG9tVZYIjQyljm1jIB3wlYjZGE8vNKzCDaYqNZlMqGQkv6t_oH3Qos5fulgMR6isCrBpllXZTnjSLnfgq5SSmSB3ReKuFnY7f5kjB/s1600/Screen+Shot+2017-06-23+at+7.32.29+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1120" data-original-width="972" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEyZSNZltEL0k_K8IryzIx9a4H45A8L4f1KmvOT91gG9tVZYIjQyljm1jIB3wlYjZGE8vNKzCDaYqNZlMqGQkv6t_oH3Qos5fulgMR6isCrBpllXZTnjSLnfgq5SSmSB3ReKuFnY7f5kjB/s320/Screen+Shot+2017-06-23+at+7.32.29+AM.png" width="277" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaYsm4AgLYH_1AhMxkvQS7fe1YJG1n4k9AXT-z4jRIMzQh9KqIaFUMYbzvHv-GYKH1glrm0DcSzQs1c75_c6fVIppJCA4CCrVVnekJ-NLlrfI7tsam4s9TvVkryRnpJijMtrfgxFPlns1x/s1600/Screen+Shot+2017-06-23+at+7.32.37+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1130" data-original-width="964" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaYsm4AgLYH_1AhMxkvQS7fe1YJG1n4k9AXT-z4jRIMzQh9KqIaFUMYbzvHv-GYKH1glrm0DcSzQs1c75_c6fVIppJCA4CCrVVnekJ-NLlrfI7tsam4s9TvVkryRnpJijMtrfgxFPlns1x/s320/Screen+Shot+2017-06-23+at+7.32.37+AM.png" width="272" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxBk9UO1VGH8Lt3NY8nWG54ZbOWKVE-j2CufBmVUeJuCPewQL9qclC_wr4KSJBUE_nMTLrGwFoax_k31IbYCyVblMTYkhKD4dQcGm1H0e3p9xtrVZXVUrx3J8zVWWTVJi7jKioYrUxk9a3/s1600/Screen+Shot+2017-06-23+at+7.32.43+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1108" data-original-width="980" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjxBk9UO1VGH8Lt3NY8nWG54ZbOWKVE-j2CufBmVUeJuCPewQL9qclC_wr4KSJBUE_nMTLrGwFoax_k31IbYCyVblMTYkhKD4dQcGm1H0e3p9xtrVZXVUrx3J8zVWWTVJi7jKioYrUxk9a3/s320/Screen+Shot+2017-06-23+at+7.32.43+AM.png" width="283" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZDLLwehlIXbt91Ny2SvfOPS1KBcBJQ_B67h3dbRHtf1_UJNLIJOdbMQjjhHoUOsODgx-TDTZ9qhg3Dctnb8yH5OjXNwli8A4Xih5UEqnxOf96HgIAVUJzLWxeZ8fiBUAUr-8JIXIvzbgl/s1600/Screen+Shot+2017-06-23+at+7.32.51+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1114" data-original-width="990" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZDLLwehlIXbt91Ny2SvfOPS1KBcBJQ_B67h3dbRHtf1_UJNLIJOdbMQjjhHoUOsODgx-TDTZ9qhg3Dctnb8yH5OjXNwli8A4Xih5UEqnxOf96HgIAVUJzLWxeZ8fiBUAUr-8JIXIvzbgl/s320/Screen+Shot+2017-06-23+at+7.32.51+AM.png" width="284" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7XYDeOJfBe1y8aN0k3bn2VwvTZ-SfAPlwB4GzlWM_merUK1mIWeuY7ECvhSmuI9WofwfxlxUg3AS4nPlm3726qxt0QP_Q4k0MS0wny7oxTGYvlztw7_kEumajq_uxj4YTwGSEFdIdczbL/s1600/Screen+Shot+2017-06-23+at+7.32.57+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1096" data-original-width="972" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7XYDeOJfBe1y8aN0k3bn2VwvTZ-SfAPlwB4GzlWM_merUK1mIWeuY7ECvhSmuI9WofwfxlxUg3AS4nPlm3726qxt0QP_Q4k0MS0wny7oxTGYvlztw7_kEumajq_uxj4YTwGSEFdIdczbL/s320/Screen+Shot+2017-06-23+at+7.32.57+AM.png" width="283" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0GZ1F_zx2ug1fIDc6TwXVTt-mFWfe6VON0Lf-ZRFbnmMKtjDkT-T6eHSeYl7KACYqwfOgkZl8X2ClCcmumZDg_F-E2wnQvNt42bnndgtcyje9mqAX0S2q1hiSvTGkrFRHhz7-W_KfxtNZ/s1600/Screen+Shot+2017-06-23+at+7.33.04+AM.png" imageanchor="1" style="clear: right; display: inline !important; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1092" data-original-width="998" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi0GZ1F_zx2ug1fIDc6TwXVTt-mFWfe6VON0Lf-ZRFbnmMKtjDkT-T6eHSeYl7KACYqwfOgkZl8X2ClCcmumZDg_F-E2wnQvNt42bnndgtcyje9mqAX0S2q1hiSvTGkrFRHhz7-W_KfxtNZ/s320/Screen+Shot+2017-06-23+at+7.33.04+AM.png" width="292" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicUWtRi-mLc65hsmgJQKg_s6-ctS9W12NSLt_UV-voBDY6aDHEpwDu-I3HlsRXhWA4rWn7tMSGALdGKMnfhO2YCYyqJyJ8fD_CqkG6GgEL-7HmTqomN4MDI0fm8dlypg0t9rNtuBe_DvUt/s1600/Screen+Shot+2017-06-23+at+1.09.10+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="162" data-original-width="262" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicUWtRi-mLc65hsmgJQKg_s6-ctS9W12NSLt_UV-voBDY6aDHEpwDu-I3HlsRXhWA4rWn7tMSGALdGKMnfhO2YCYyqJyJ8fD_CqkG6GgEL-7HmTqomN4MDI0fm8dlypg0t9rNtuBe_DvUt/s1600/Screen+Shot+2017-06-23+at+1.09.10+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEja24aR-RAnsAXzIXZwhZLVL2ngHBj5_rHm29iBLI0LLZNBxWY7Pe-W5jf-iSk2KgcQzRBw2WTYspU_Uu4j70Bw_V_n7ZBD21WQ0KuxacMHcp1m5BDLRQN97v7UgaXaxf-S9YO0ZKO9EO3f/s1600/Screen+Shot+2017-06-23+at+1.09.17+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="202" data-original-width="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEja24aR-RAnsAXzIXZwhZLVL2ngHBj5_rHm29iBLI0LLZNBxWY7Pe-W5jf-iSk2KgcQzRBw2WTYspU_Uu4j70Bw_V_n7ZBD21WQ0KuxacMHcp1m5BDLRQN97v7UgaXaxf-S9YO0ZKO9EO3f/s1600/Screen+Shot+2017-06-23+at+1.09.17+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWbEeEeGvqHbjJb7XWexKDEED9BaPsJ25Q8YrzaxhJYmj6Yklbah5OvHZCRw_vp3UvkWnmlLKr6x0pQ3JivFYgDOHeqETpl31LMmT9NfGXoiufwyEn19DWMwFe1N1N1lGYo1SnVui8RnWo/s1600/Screen+Shot+2017-06-23+at+1.09.24+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="196" data-original-width="272" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWbEeEeGvqHbjJb7XWexKDEED9BaPsJ25Q8YrzaxhJYmj6Yklbah5OvHZCRw_vp3UvkWnmlLKr6x0pQ3JivFYgDOHeqETpl31LMmT9NfGXoiufwyEn19DWMwFe1N1N1lGYo1SnVui8RnWo/s1600/Screen+Shot+2017-06-23+at+1.09.24+PM.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxb9JAcXGdcrWsqlsnyoVrq9cegTSV0WLrpx7tp3RvTVZXyqtY_BGnw1Jgfud3lTNc7-b6tEPvGiL_znnnxqB2wLA25hg8holh2YYfuXdeaLCotyo6eQEquFxsOn9KGrrRsP_dKemOQwHR/s1600/Screen+Shot+2017-06-23+at+7.33.11+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1104" data-original-width="1010" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhxb9JAcXGdcrWsqlsnyoVrq9cegTSV0WLrpx7tp3RvTVZXyqtY_BGnw1Jgfud3lTNc7-b6tEPvGiL_znnnxqB2wLA25hg8holh2YYfuXdeaLCotyo6eQEquFxsOn9KGrrRsP_dKemOQwHR/s320/Screen+Shot+2017-06-23+at+7.33.11+AM.png" width="292" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVJtvJ5UXyyBGkB8bitv-sot_Zh4N-MROGMwI_fBxoNwiAcQP4Yr1JeCa1rza6opykE_gbuavLC7YANd7DFjJaG4ieFlhZ3DJZZVnBEhLtZFnP9PmYD2L4I-6MrUlmaicnyIiALeM-Yt9X/s1600/Screen+Shot+2017-06-23+at+7.33.17+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1210" data-original-width="1026" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVJtvJ5UXyyBGkB8bitv-sot_Zh4N-MROGMwI_fBxoNwiAcQP4Yr1JeCa1rza6opykE_gbuavLC7YANd7DFjJaG4ieFlhZ3DJZZVnBEhLtZFnP9PmYD2L4I-6MrUlmaicnyIiALeM-Yt9X/s320/Screen+Shot+2017-06-23+at+7.33.17+AM.png" width="271" /></a></div>
<br />Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com1tag:blogger.com,1999:blog-5235423068973972362.post-37570415048106185862017-02-18T11:39:00.004-06:002021-02-10T11:01:25.209-06:00Pipelines in RustA classic Operating Systems assignment is to implement a Unix shell. It's a great assignment for several reasons. Students have to:<br />
<ul>
<li>Get a solid understanding of the concept of a process.</li>
<li>Master some of the more subtle aspects of the file system.</li>
<li>Make direct system calls with subtle semantics.</li>
</ul>
<div>
Since I am teaching my course in Rust, I needed to figure out how I wanted the students to implement pipelines and I/O redirection. The options are:</div>
<div>
<ul>
<li>Rely entirely on the standard library.</li>
<li>Interact directly with libc.</li>
</ul>
<div>
The benefit of relying on the standard library is, first of all, that the resulting code is portable across platforms. Second, there is no need for unsafe blocks. The problem is that the <a href="https://doc.rust-lang.org/std/process/struct.Stdio.html#method.piped">pipe from the standard library only connects a parent and child</a>. The <a href="https://doc.rust-lang.org/std/process/struct.Command.html">Command</a> object is great, but it doesn't allow for the separation between fork() and execv() that is essential for implementing proper I/O redirection. </div>
</div>
<div>
<br /></div>
<div>
The trouble with the <a href="https://doc.rust-lang.org/1.12.0/libc/index.html">standard libc crate</a> is that all of the function calls are unsafe. As far as I am concerned, this is bad news pedagogically because I do not want my students using unsafe blocks unless absolutely necessary. They are still learning the language, and I want them to learn to operate within the safety parameters it gives. Unsafe blocks, while necessary, are for experts, and my students will not be experts after one semester.</div>
<div>
<br /></div>
<div>
Fortunately, I recently discovered the <a href="https://github.com/nix-rust/nix">nix crate</a>. (<b>Update</b>: Starting in <a href="https://crates.io/crates/nix/0.19.0" target="_blank">version 0.19.0</a>, <a href="https://docs.rs/nix/0.19.1/nix/unistd/fn.fork.html" target="_blank">fork() is now marked <b>unsafe</b></a>. The code below works unmodified up to <a href="https://crates.io/crates/nix/0.18.0" target="_blank">version 0.18.0</a>. <a href="https://github.com/rust-lang/rust/issues/39575#issuecomment-442993358" target="_blank">The nature of POSIX requirements for these functions makes them intrinsically unsafe in Rust.</a>) It is a <a href="http://kamalmarhubi.com/blog/2016/04/13/rust-nix-easier-unix-systems-programming-3/">safe alternative to libc</a> that provides everyone's favorite system calls in a Rust-friendly form. The program below executes a simple three-command pipeline. Here are the key concepts for understanding the program:<br />
<br />
<ul>
<li>The fork() system call creates a new process. The new process is a perfect duplicate of the original process. The only difference between them is that fork() returns a different value if it is in the child process. If it is in the parent process, it returns the child's PID. </li>
<li>A parent and child process are connected using a pipe. A pipe is accessed using two file descriptors: one for the pipe's input, one for the pipe's output. The output of the pipe serves as an input stream for a process, and likewise the input of the pipe serves as an output stream for a process.</li>
<li>When a parent and child are connected by a pipe, the parent will typically be receiving data from the child. Therefore, the parent's input will be the pipe's output, and the child's output will be the pipe's input. </li>
<li>When the child is finished generating output, it exits. Then, the parent can finish processing the data it received from the child before it in turn exits as well. It is essential that the child exit first; if the parent exits first, unless other provisions are made both processes end.</li>
<li>To redirect standard input from the pipe instead of from the keyboard, we need to close the file descriptor for the keyboard (always file descriptor 0) and replace it with the file descriptor for the output of the pipe. The dup2() system call accomplishes this.</li>
<li>Similarly, to redirect standard output into the pipe instead of to the monitor, we need to close the monitor's file descriptor (always file descriptor 1) and replace it with the file descriptor for the input of the pipe. Again, we use dup2() for this purpose.</li>
<li>Remember that fork() completely duplicates a process. This includes its open file descriptors. In our case, that includes both ends of the pipe. We need to explicitly close the end of the pipe that the process is not using.</li>
<li>The execvp() system call loads a program and executes it. In doing so, the data for the current process is overwritten completely (except for the open file descriptors). The first argument is the name of the program. The PATH environment variable is searched for that program. The second argument is the complete list of command-line arguments, including the program name.</li>
<li>These parameters to execvp() need to be formatted as fixed-size arrays of C-style strings (which are very different from Rust strings). The program below shows how this conversion can be done.</li>
</ul>
<br />
If you'd like an alternative explanation of how the program works, feel free to view a <a href="https://www.youtube.com/watch?v=LnJ1ZbQb1KE">15-minute video</a> in which I explain the details of this program.</div>
<div>
<br /></div>
<pre>
use nix::unistd::{pipe, fork, ForkResult, close, dup2, execvp};
use std::ffi::CString;
use nix::sys::wait::waitpid;
// Add dependency nix = "0.19" to Cargo.toml
fn main() {
println!("Executes ls -l | grep Cargo | wc");
let ls: Vec<CString> = vec![CString::new("ls").unwrap(),
CString::new("-l").unwrap()];
let grep: Vec<CString> = vec![CString::new("grep").unwrap(),
CString::new("Cargo").unwrap()];
let wc: Vec<CString> = vec![CString::new("wc").unwrap()];
match unsafe {fork()}.unwrap() {
ForkResult::Parent{child} => {
println!("wc pid is {}", child);
waitpid(child, Option::None).unwrap();
println!("Finished! Exiting...");
},
ForkResult::Child => {
let (wc_in, grep_out) = pipe().unwrap();
match unsafe {fork()}.unwrap() {
ForkResult::Parent{child} => {
close(grep_out).unwrap();
println!("grep pid is {}", child);
dup2(wc_in, 0).unwrap();
let array = wc.into_boxed_slice();
execvp(&array[0], &*array).unwrap();
},
ForkResult::Child => {
close(wc_in).unwrap();
let (grep_in, ls_out) = pipe().unwrap();
match unsafe {fork()}.unwrap() {
ForkResult::Parent {child} => {
close(ls_out).unwrap();
println!("ls pid is {}", child);
dup2(grep_out, 1).unwrap();
dup2(grep_in, 0).unwrap();
let array = grep.into_boxed_slice();
execvp(&array[0], &*array).unwrap();
},
ForkResult::Child => {
close(grep_in).unwrap();
dup2(ls_out, 1).unwrap();
let array = ls.into_boxed_slice();
execvp(&array[0], &*array).unwrap();
}
}
}
}
}
}
}
</pre>
<div>
<br /></div>
Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com0tag:blogger.com,1999:blog-5235423068973972362.post-70031360444979969552017-02-18T11:18:00.000-06:002017-03-08T21:03:14.230-06:00Threads, locks, and deadlocks in RustA very compelling feature of the Rust language is <a href="https://doc.rust-lang.org/book/concurrency.html">compile-time protection against data races</a>. This makes it much easier to write correct threaded programs that share mutable state. The following program illustrates how this works. The program runs eight parallel simulations of a coin-flipping experiment.<br />
<br />
<pre>extern crate rand;
use std::thread;
use std::sync::{Arc, Mutex};
fn main() {
let total_flips = Arc::new(Mutex::new(0));
let completed = Arc::new(Mutex::new(0));
let runs = 8;
let target_flips = 10;
for _ in 0..runs {
let total_flips = total_flips.clone();
let completed = completed.clone();
thread::spawn(move || {
simulate(target_flips, total_flips);
let mut completed = completed.lock().unwrap();
*completed += 1;
});
}
loop {
let completed = completed.lock().unwrap();
if *completed == runs {
let total_flips = total_flips.lock().unwrap();
println!("Final average: {}", *total_flips / *completed);
break;
}
}
}
fn simulate(target_flips: u64, total_flips: Arc<Mutex<u64>>) {
let mut consecutive = 0;
let mut iterations = 0;
while consecutive < target_flips {
iterations += 1;
if rand::random() {
consecutive += 1;
} else {
consecutive = 0;
}
}
println!("iterations: {}", iterations);
let mut total_flips = total_flips.lock().unwrap();
*total_flips += iterations;
}
</pre>
<br />
The <code>main()</code> function creates two mutable variables that can be shared among threads. One represents the total flips across all experiments. The other represents the total number of experiments that have completed. They are Arc (atomic reference counted pointers) objects that each contain a Mutex (lockable resource).<br />
<br />
As each thread is created, it needs its own reference to these shared variables. To create a new shared reference, we need to clone() each variable. This clone is then moved into the thread as it is created, so that the thread is now the owner of the cloned reference.<br />
<br />
To access the shared variables, a thread must acquire a lock. The thread blocks if the lock is already held by another thread. A thread releases a lock it holds when the locked variable goes out of scope. The <code>total_flips</code> variable is locked within the <code>simulate()</code> function, while the <code>completed</code> variable is locked after that function completes. The main thread also locks <code>completed</code> periodically as it checks for completion.<br />
<br />
The program works fine as written above. But it would be easy to make a mistake that leads to a deadlock. Consider the following variation.<br />
<br />
<pre>extern crate rand;
use std::thread;
use std::sync::{Arc, Mutex};
fn main() {
let total_flips = Arc::new(Mutex::new(0));
let completed = Arc::new(Mutex::new(0));
let runs = 8;
let target_flips = 10;
for _ in 0..runs {
let total_flips = total_flips.clone();
let completed = completed.clone();
thread::spawn(move || {
simulate(target_flips, total_flips);
let mut completed = completed.lock().unwrap();
*completed += 1;
});
}
<span style="color: red;">
let completed = completed.lock().unwrap();
while *completed < runs {}
let total_flips = total_flips.lock().unwrap();
println!("Final average: {}", *total_flips / *completed);</span>
}
fn simulate(target_flips: u64, total_flips: Arc<Mutex<u64>>) {
let mut consecutive = 0;
let mut iterations = 0;
while consecutive < target_flips {
iterations += 1;
if rand::random() {
consecutive += 1;
} else {
consecutive = 0;
}
}
println!("iterations: {}", iterations);
let mut total_flips = total_flips.lock().unwrap();
*total_flips += iterations;
}
</pre>
<br />
In this variation, the main thread retains ownership of the lock on <code>completed</code>. This causes all of the simulating threads to block. Unfortunately, the simulating threads cannot update <code>completed</code> because they are blocked. In the meantime, the main thread is waiting for the simulating threads to complete! This is an example of a <b>deadlock</b>. Although Rust prevents lots of concurrency problems, <b>it can't prevent all of them</b>! When writing multithreaded Rust code, it is always essential to retain locks for the smallest possible scope in order to avoid deadlocks.<br />
<br />
I'd like to point out that there are alternatives to locks available in Rust. One intriguing option involves <a href="https://aturon.github.io/blog/2015/08/27/epoch/">using lock-free data structures</a>. I'd like to explore that library in more depth when time permits.Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com2tag:blogger.com,1999:blog-5235423068973972362.post-83996999867139009372017-02-18T10:56:00.004-06:002021-01-15T09:30:23.111-06:00Strings in RustOne concept in Rust that those learning the language can find very confusing is the existence of two different types of strings: <code>String</code> and <code>&str</code>. (This post assumes at least a basic understanding of the <a href="https://doc.rust-lang.org/book/ch04-00-understanding-ownership.html" target="_blank">Rust ownership system</a>.)<br />
<br />
The <code>String</code> type represents a block of memory that is <a href="https://doc.rust-lang.org/book/ch04-00-understanding-ownership.html">owned</a>. <a href="https://doc.rust-lang.org/book/ch03-01-variables-and-mutability.html">Mutation</a> is possible if the variable corresponding to the object is appropriately designated.<br />
<br />
The <code>&str</code> type is (generally speaking) <a href="https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html">borrowed</a> from elsewhere rather than owned. This can happen in a couple of ways. String literals are all <code>&str</code> objects. Methods like <code>split()</code> return iterators into their source strings. The iterated items are then borrowed references to substrings within the source string.<br />
<br />
The program below is intended to illustrate these distinctions.<br />
<br />
<pre>use std::io;
use std::io::Write;
fn main() {
match run() {
Ok(_) => println!("Goodbye."),
Err(e) => println!("Error: {}", e),
}
}
fn run() -> io::Result<()> {
let stdin = io::stdin();
let mut longest_overall = String::from("");
loop {
print!("> ");
io::stdout().flush()?;
let mut line = String::new();
stdin.read_line(&mut line)?;
if line.trim().len() == 0 {
break;
}
let mut line_longest: &str = "";
for word in line.split_whitespace() {
if word.len() > line_longest.len() {
line_longest = word;
}
if word.len() > longest_overall.len() {
longest_overall = String::from(word);
}
}
println!("Longest word in this line: {}", line_longest);
}
println!("Longest overall word: {}", longest_overall);
Ok(())
}
</pre>
<br />
This program accepts command-line input from the user. Each line of input is split up to find the constituent words. The program reports the longest word from the current line. When the program ends, it also reports the longest overall word. <br />
<br />
The variable <code>longest_overall</code> is a <code>String</code>. I chose to make it a <code>String</code> because I need for that variable to maintain long-term ownership of the value it is storing, and that's not possible with a <code>&str</code>.<br />
<br />
The variable <code>line</code> is a <code>String</code>. It has to be a <code>String</code> because it gets mutated when input is read from the user.<br />
<br />
The variable <code>line_longest</code> is a <code>&str</code>. It borrows a substring from <code>line</code>. Because it has the same<a href="https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html"> lifetime</a> as <code>line</code>, borrowing is all we need. Note that both of their <a href="https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html">lifetimes</a> end when they go out of scope at the end of each iteration of the loop.<br />
<br />
This brings us back to the need for <code>longest_overall</code> to be a <code>String</code>. Ultimately, the longest word overall is simply a substring of <code>line</code>, which goes out of scope at the end of each loop iteration. That makes it absolutely necessary to make a long-term copy of that longest word, in order to preserve it in existence after its source is deallocated.<br />
<br />
To sum up, when figuring out which type of Rust string to use, pay attention to the <a href="https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html">lifetime</a>. Remember that <code>&str</code> objects are always borrowed from somewhere else. If the string is needed beyond the lifetime of the source of the borrow, you need a <code>String</code>.<br />
<br />
This example does not illustrate this, but many methods and functions expect a <code>&str</code>. If you have a <code>String</code>, and a <code>&str</code> is demanded, just use the <code>as_str()</code> method to lend that <code>String</code> to the function.Gabriel Ferrerhttp://www.blogger.com/profile/08014021536591191108noreply@blogger.com2