text:
It should be obvious from the giant peak in around October of last year that I defended in November of 2015. In a perfect world I would have immediately made all the changes requested by my committee and finished up no later than December. Instead, I moved to California. Finally around May or so I felt settled enough in my new station in life that I could go finish up my nagging dissertation. You can of course see this in the flurry of activity around May or June on the graph.
I'm glad to be done!
It's been a long road, and I've been fortunate to have tons of supportive people along the way to help out. A Ph.D. is really too big of a task for just one person, so even though I'm the one who gets to put the extra letters after my name if I want, I'm truly grateful for everyone who has helped along the way!
I mentioned earlier that I moved to California. Back in January I started working at Google, doing some really fun stuff with WebAssembly. I'm hoping in my new post grad school life I'll also get the chance to revisit some personal projects I put on the back burner in order to graduate. One of those projects is blogging more. It's been over two years since my last post, and I honestly find that a little bit embarrassing. Of course, the reality is that it always seems like I'll have more time in the future than I actually end up having, so we'll have to see.
I realize this post is pretty late as well. So it goes.↩
If you're using Chrome, feel free to try it out:
Unfortunately, it seems that Firefox doesn't yet support the APIs I used, although rumor has it that this should work in the nightlies. I haven't tested Safari, but I wouldn't be surprised if it works there because it also uses WebKit.
The Web Audio APIs are a new way of generating audio and applying rich effects. The basic idea is to create a set of nodes and connect them together to form an audio processing network. Some of these nodes are audio sources, such as from a file you loaded off the web, while others are generated in place, like the OscillatorNode.
I was happy to find the OscillatorNode, as I expected I was going to have to directly generate audio data. Instead, I just have to set the frequency I wanted and tell it to start generating tones. Basically, like this:
1 2 3 4 5 6 7
This code gives us a continually playing tone, which quickly gets
annoying. We need a way to generate dots and dashes so we can actually
generate Morse Code. Unfortunately, I couldn't see an easy way to do
this using
start and
stop. I thought about using
setTimeout, but
I didn't trust it to give me reliable enough timing.
I was afraid I was going to have to generate the audio data directly after all, but then I found out that the APIs include parameter automation. This let's us schedule changes in various audio parameters at specific points in time, and the standard even seems to require these to take effect at the per-sample granularity. This seems to be exactly what we need.
It seemed as though it'd be as simple as calling
oscillator.volume.setValueAtTime, but
oscillator.volume turned out
not to be a thing. Instead, we need to add a GainNode, which allows
us to adjust the volume. Wiring the whole thing up looks something like this:
1 2 3 4 5 6 7 8 9 10 11
Now we can generate Morse Code by simply toggling the gain between 0
and 1. I did this by creating a table mapping all the letters to a
string of dots and dashes (for example, "A" maps to
.-, "B" to
-..., etc.). Then it was just a matter of creating a couple
loops to translate strings of letters into dots and dashes and then
dots and dashes into sequences of volume changes. For the full
details, I've shared my code in a gist.
So there you have it: generating Morse Code using the Web Audio APIs in less that 100 lines of code. One thing I like about the design is that it mimics an actual telegraph. You have a signal generator (the OscillatorNode) connected to a key (the GainNode) which is connected to a transmitter (the AudioContext).]]>
Much of the display work involved adapting the Adafruit-provided example code. The Arduino communicates with the display using SPI, which can apparently be implemented in software or by hardware built into the microcontroller. I decided to try using the hardware version (hardware's always better, right?), which meant I had to change some pins and such. It was a little tricky to find the right pins because different guides name them different things. For example, the Data pin on the display board should connect to the MOSI pin on your Arduino. This makes some sense if you know that MOSI stands for master output, slave input. It turns out I only needed to change two pins. After consulting the Arduino SPI page, I decided on the following pin mapping for my Arduino Mega.
This was enough to start writing the code to draw the game board, make the ball bounce, and control the computer player. To add the human player, we need to add a couple of buttons. To keep things simple, I just added one up button and one down button.
Wiring switches is a little more complicated than I would expect. You'd think you could just run a wire from 5 volts to one side of the switch and then from the other side of the switch to one of the Arduino's digital inputs. The problem with this is that when the switch is not being pushed there is no way of knowing what value we should expect to read from the digital pins. Instead, we use a pull-down resistor (although I got the ground and +5 backwards on mine, so I have a pull-up resistor instead). The Wikipedia page has a good diagram of what this circuit looks like. Basically, the idea is that we tie the digital pin to a known value with a fairly big resistor (I used 10k ohms), while the switch connects the pin to a different value with a much lower resistance. In this case, when you push the switch you read the correct voltage, but the large resistor keeps a lot of current from flowing. At least, that's my best understanding of it; perhaps someone else can explain it better.
Once I had everything wired up, all that was left was to finish writing the code and then have some fun playing.
You can see the code I wrote on GitHub: https://github.com/eholk/Arduino-Pong
I also drew up a schematic for the circuit using 123D Circuits: http://123d.circuits.io/circuits/244849-arduino-pong
If you decide to tinker with this, there are some obvious improvements. For example, the game could restart when the ball hits one of the side walls, and the game could keep score. The microcontroller gets kind of warm after a while, which means the sketch could use some changes to reduce power consumption. This circuit could also work for entirely different games, such as Frogger! Whatever you decide to do, have fun!]]>
What I have found useful is to think of monads as a style of programming (like continuation passing style), or even a design pattern. I've found monads are really handy when you need to thread some object through a sequence of function calls. To see how this works, we're going to start with a store-passing interpreter for a small language and show how to use monads to hide the store in the cases where we don't need it.
Let's start by looking at an interpreter. This is basically the first interpreter from this post, but we've added mutable references.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
There are a couple of high level changes from the standard environment
passing interpreter. First, we've added an additional store
parameter. This represents the state of the memory, as opposed to the
environment, which tracks variables on the stack. Second, since
operations such as
ref and
update can modify the store, in
addition to returning the value of an expression, we also have to
return a potentially updated store. We could use Scheme's support for
multiple return values, but I went with
cons instead for
simplicity's sake.
The first few cases are pretty straightforward. Starting on line 4, we have the variable lookup line. This reads a value from the environment and returns it. The store is left unchanged, so we just return that as is. Likewise with the number case in line 6.
For the lambda case on line 8, we use Scheme's lambda to represent
functions in our language. There's a slight subtly here. Instead of
having the procedure only take a value argument (
v), it also must
take a store. The reason is that otherwise this procedure would modify
the store that was in effect when it the procedure was created, rather
than the store in effect at the call site.
Next we have
deref and
update. This is where the store
starts to be interesting. We've represented the store as an
association list between labels and values. We use
ref to create a
new reference (think of it like
new in C++ or Java), which we
implement by using
gensym to create a new label, and then adding a
new label:value pair to the store. The value of a
ref expression is
a value tagged as a reference, containing an address into the
store. Think of these as pointers.
deref, we first evaluate the argument and use
match to unpack
the label from the returned reference value. Once we have the label,
we use
assq to look it up in the store then we return its value.
update expression requires us to evaluate two arguments: the
destination location and the new value. We do this with two recursive
calls to
value-of/store. In the interpreter from previous posts, we
could have used
match's catamorphism facility to make this quite a
bit shorter, but here we need to be explicit about ordering because of
a potentially changing store. When we get around to actually updating
the store, we just prepend a new label:value pair. Because
returns the first match it finds, this results in whatever value was
previously there being ignored.
Finally, the application case (line 30) is similar to before. The main changes are that we need to be explicit about the order of evaluation and we pass the current store into the function we are applying.
What we have now is an interpreter for a small language with mutable
references. You'll notice we didn't use any side effects in creating
the interpreter, which is kind of cool. Still, a few things are less
than ideal. To go from a language without mutable references to one
with mutable references, we had to change basically every line in the
interpreter. Every recursive call to
value-of/store needs an
additional store parameter, and every return from the interpreter has
to return a store as well. This is the case even though only
ref and
update can modify the store. What we'd like is to only have to be
aware of the store for cases that interact with the store. Monads can
help us do that.
To deal with some of the shortcomings in the previous paragraph, we are going to derive a monad through a series of correctness-preserving transformations. Some of the intermediate steps will look rather ugly, but the end should look pretty nice.
The first thing we're going to do is Curry (Schönfinkel?) the store argument.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
As I said, we're going to make things worse for a while. Curried
functions in Scheme programs are always kind of messy. The nice thing
is that now we can push the
(lambda (store) ...) part inside each of
the match branches. It will become clear why we might want to do this
in a second.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
Notice how we have a couple of cases, such as the variable and number
case, where all we do is
cons some value onto an unchanged
store. Since we repeat this pattern a few times, let's pull it into a
separate function that we'll call…
1 2 3 4
We can rewrite our previous interpreter using return:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
For the first time, we've introduced a transformation that makes our program shorter! While I was at it, I also did a transformation called an eta reduction in the lambda line at lines 9-10. The result is that the first three cases in the interpreter make no mention of the store. This is real tangible progress towards our goal.
Let's look at the last case, the application case, for a bit. Here we
take a store, pass it into a call to evaluate the operator, and then
thread the resulting store into a call to evaluate operand, and then
finally we thread that store into the actual application of the
operand. In each case, we don't really care about the store; we only
care about the value of the expression. Let's see if we can write a
function that does the store-threading for us. We'll call
1 2 3 4 5 6
m is for monad, meaning it's a function that does something
when it receives a store. The
f parameter is a function describing
what to do next. It expects a value and returns a new monad. We get
this value by applying a store to the
m argument. We expect
f to
return a function expected a new store, and we apply this function to
the updated store returned by
m. It's a bit complicated, but it
simplifies our application line somewhat:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
Our interpreter just shrunk by another line. The only cases where we
see the store actually appears are
deref, and
update, which
are exactly the cases that need to read or write memory. The rest of
the interpreter is completely oblivious to the existence of memory.
We can clean up the application line a little further. If you squint a
little, you'll noticed that the calls to
bind look a little like the
traditional expansion of
(let ((x e)) b) to
((lambda (x) b)
e). Let's build some extra syntax to make it easier to chain lots of
calls to
bind together. We'll call it…
1 2 3 4 5 6
This macro works a little like
let*, where it performs a sequence of
computations in order and names each of their results. Using this
macro, our interpreter becomes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
Not bad.
We're going to cheat a little for the last few cases. We're doing to
define three new functions,
get-ref and
which do the store manipulation for us. Here they are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
These feel like cheating to me because we got these functions
basically by copying and pasting the body of the
deref and
update cases. But, we can think of it as defining a clean interface
to the store, which is just good software engineering. Plus, our
interpreter was actually doing two things in each case. First it had
to evaluate the arguments and then it had to access the store. Using
these helper functions makes that separation clearer.
Using these functions in the interpreter completes our transition over to monads.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Our interpreter is now a whole 11 lines shorter than where we started! Granted, we've moved some of the functionality into helper functions, so the total length of the program may be longer. Still, this program seems much better factored to me. The interpreter itself shows how to evaluate different language forms, and things like order of evaluation are very clear. The details of how to manipulate the store-related data structures are all hidden in the monad.
I've found that thinking of deriving monads through a series of program transformations has helped them make a lot more sense to me. In functional programming it's common to simulate stateful things by threading extra arguments around. This quickly gets tedious. Monads help you keep this hidden when you don't care about it and cleanly expose it in cases where you do.
Another benefit of this style of programming that I've found is that
once your program is written in terms of
bind and
you can modify the monad without having to change the rest of your
program. In rewriting the Harlan type inferencer, there were a few
times I realized I had some more information to thread through the
inferencer. In the old style, I would have had to change many lines of
code to do this. Since the type inferencer was written monadically,
however, I could modify a handful of functions while leaving the bulk
of the code unchanged.
The biggest challenge for me was deciding what are the expectations for a high quality artifact. Artifact evaluation is still quite new and many of us have not seen many if any artifacts from other papers, meaning we don't have a clear set of expectations as a community. With papers, on the other hand, things are clearer. We've read our share of good and bad papers, and as a reviewer we generally know that we expect the paper to make claims about a clearly motivated problem and provide sufficient evidence that their solution works. We expect papers to be well-written, although as long as grammatical issues do not seriously hamper understanding the paper, we are pretty forgiving about this.
In the context of artifacts, I was interested first of all in whether I could run the software and verify that it does what the paper claims it does. Secondly, I wanted to see whether I felt I could use the code as a starting point if I were to try to do more research built on the claims of the paper.
The second point, especially, challenges the common practice for research code. Research code is notorious for being duct taped and hacked together at the last minute in order to run just barely well enough to generate the graphs in the paper. In one of my early projects as a grad student, our system involved S-Expressions embedded in C++ code, with a Python script to extract them, run them through a compiler written in Scheme and then stitch the generated C++ code back into the original program. As far as I know, the only programs that ran were the benchmarks in our paper. Even worse, there wasn't a single SVN revision that worked. You'd need some files from one revision, and other files from another revision, depending on which compiler features you wanted to enable. This is exactly the kind of horror that drove Matt Might to create the CRAPL.
This is also a challenge to artifact evaluation. On the one hand, research is about doing whatever is necessary to prove a concept. We should not expect research code to be Version 1.0 production quality. On the other hand, research is about repeatability and being able to build off previous results. In the project I just mentioned, three days after the paper deadline, I had forgotten with magic combination of SVN revisions to make the code work. If I couldn't remember how to run my own software, how could I expect anyone else to? This is one of the reasons that we started building an extensive test suite at the very beginning and tried to make the zero-to-tests-running process as simple as possible.
One issue that Lindsey mentioned in her post was that her paper (and several others) relied on some commercial software that they could not redistribute. This creates more tension as a reviewer, because while researchers should be allowed and even encouraged to use whatever tools help them get better results faster, the fact is this also makes it harder for me do evaluate their work. Fortunately, many of us in the research community are part of institutions that have licenses to a variety of software, meaning at least one of the reviewers likely has the necessary software. In spite of these challenges, I don't want us to get to a place where there is de facto requirement that all research code must be built only with GPL software.
I'll close with a list of things that I found really helpful in the artifacts I saw.
With the exception of creating a virtual machine, these suggestions not only make the artifact evaluator's job easier, they also make conducting research easier. READMEs and an easy way to install the software will help bring new people onboard the project. Being able to automatically regenerate all the graphs in a paper makes it easy to quickly see the impact of changes in your software. It may seem like a lot of time at first, I'm convinced doing this early will more than make up for it in the long run.]]>
With the recent release of Rust 0.9, I've decided to start a tradition of tagging releases for my Rust projects to coincide with releases of the Rust language. Although things like Rust CI have helped keep Rust code running as the language matures, there's still some frustration in using Rust projects if you'd rather not always run the latest master build. Sometimes, it may even be impossible to make two projects work together if their maintainers do not update at the same pace. By tagging releases with official Rust releases, it will become much easier to always find a version of my code that works with the latest release of Rust.
Without further ado, here are the projects:
Besides shamelessly plugging my own software, I hope that this post will encourage others who maintain Rust projects to do the same. As the Rust community grows, more people will want to stick with official releases, and these are much more valuable when most of the Rust projects have easy-to-find versions that work with these releases.]]>
This new style is called continuation passing style. You can think of a continuation as what to do next in a program, and so continuation passing style means we make the continuation an explicit argument of a function. This means we can do a lot more with the control flow of the program, which is important in a debugger, for example, since we want to be able to pause and inspect the execution at arbitrary points.
We'll continue with a quick introduction to continuations and
continuation passing style, then look at how to apply this to our
interpreter. Once that is done, we will see how to implement
in our new interpreter.
You can think of a continuation as the rest of the program. What I mean is that at any point in a program's execution we can think of it in terms of what has already been done and what still needs to be done. Consider the expression below.
This program has two things to do. First, we have to multiply 2 and 3, and then it needs to add 5 to the result. In other words, "add 5 to the result" is the continuation of "multiply 2 and 3." We can see this a little more clearly if we rewrite our program like this:
1 2 3
In this case, the continuation isn't terribly interesting because it's always the same. What if we did this instead?
1 2 3 4 5 6 7 8
Functions has an implicit continuation, and the cool thing is that the
continuation can change. In the function
foo above, sometimes the
continuation is to add 5 to the result, and other times the
continuation is to add 7. The continuation is just wherever the
function happens to return to.
If you're used to programming in lower level languages like C and thinking about things like stacks and return addresses, you might notice that stacks and return addresses are really similar to continuations.
So far we can only see continuations by looking at the source code. Sure, we can rewrite the program to make the continuation a little easier to see, but nothing really changes. What if we could make a function that represents a continuation? Starting with our first example, we might end up with something like the program below.
1 2 3
Here, we've pulled the "add 5 to the result" part of the program into
a function which we can use just like any other function. By
convention, we always call the continuation
k. This process has a
fancy name: reifyication. To reify something is to take an abstract idea
and make it into something concrete that you can manipulate. In this
case, we took our abstract notion of the continuation of
(* 2 3) and
turned it into a function that we can control. Sure, we haven't done
anything other than apply it in the right place, but instead we could
pass it as an argument to another function. This leads us to
continuation passing style.
We've seen that any function has an implicit continuation, which is
where the function returns to. What if instead functions never
returned? Well, this wouldn't be very interesting, because the caller
would never be able to do anything with the result of a
function. Fortunately, the caller could also tell the function what to
do when it's done. Let's look at this new version of
1 2
foo doesn't return, but calls
k with its result instead. The
caller gets to control what happens next by deciding what function to
pass in as
We'd have to rewrite the callers of
foo to respect this new style:
1 2 3 4 5
This style of passing a continuation into a procedure which never returns but instead calls the continuation is called, as you might expect, continuation passing style (CPS). It's a little harder to read, but it has some nice properties.
We've made a couple of toy examples so far, but let's look at a more realistic program. First, recall the interpreter from last time:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
We'll translate this to CPS one line at a time.
First, we add an extra argument to
value-of which provides the
continuation to invoke once the expression is evaluated:
1 2
For environment lookup, we'll consider
lookup to be simple,
meaning we aren't going to worry about converting it to CPS. Thus, the
variable line becomes:
(,x (guard (symbol?x)) (k (lookup x env)))
Basically, as soon as we know the value of the expression, we pass it to
Numbers are similar:
(,n (guard (number? n)) (k n))
Lambdas are a bit more involved. If you recall, we evaluated interpreted lambdas into native lambdas, and later the application line just applies this function. Thus, these need to be in CPS as well. Our lambda line, therefore, looks like this:
((lambda (,x) ,e)
(k (lambda (v k) (value-of-cps e (cons (cons x v) env) k))))
Notice a couple of things. First, lambdas immediate evaluate to
values, so we pass the
(lambda (v k) ...) directly to
k. Secondly,
this newly created lambda doesn't know in what context it will be
called, so it needs to receive a continuation argument as well. This
is why it's a two argument lambda instead of just a one argument
lambda like before and like it is in the source language. This is the
continuation we pass into
value-of-cps inside the lambda.
The next line, primitive operators, is a little more tricky as
well. Before we could just recursively call
value-of on the
e1 and
e2. In CPS, however, functions never return, so
if we do that we'll never get a chance to evaluate the second argument
or perform the operation. Instead, we call
value-of-cps on the first
argument, and in the continuation we evaluate the second argument, and
finally in the innermost continuation we actually apply the
operator. Here's the code.
((,op ,e1 ,e2) (guard (memq op '(+ * -)))
(value-of-cps e1 env
(lambda (v1)
(value-of-cps e2 env
(lambda (v2)
(k ((eval op) v1 v2)))))))
Our final line is similar to the primitive operator line, in that we have to do the same sort of sequencing. It looks like this:
((,e1 ,e2)
(value-of-cps e1 env
(lambda (f)
(value-of-cps e2 env
(lambda (v)
(f v k))))))
First we evaluate
e1 and the result gets bound to
f when the
(lambda (f) ...) continuation is invoked. Next we evaluate the
e2. Finally, we apply the function to its argument. Notice
that we also pass in
k. This is the
k that was passed into
value-of-cps the first time. Presumably this function call that we
are evaluating is part of a larger expression, and so this
captures how to integrate that result with the outer expression.
Here's the whole interpreter in continuation passing style:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
At this point, you might be wondering why we did all that. The code is harder to read, and we haven't changed the language that the interpreter understands. In one way, this is a powerful thing about interpreters—the details of how the interpreter is written don't leak into the source language.
Like most programming techniques, sometimes CPS simplifies your program and other times it makes it more complicated. What we'd like is to be able to use CPS where it's convenient and use direct style everywhere else. In all our examples so far, however, we either right the whole thing in CPS or the whole thing in direct style. We don't have a good way to switch styles.
Scheme provides an operation that lets us do just that:
which is short for
call/cc takes
one argument, which is a procedure that takes one argument.
creates a Scheme function that represents the continuation at the
point at which it is called and passes this function into its
argument. Here's a really simple example:
If you evaluate this expression, you'll realize we could have just as
well written 5 and the result would be the same. The cool this is that
now we have a procedure that we can pass into, for example,
value-of-cps in order to use the CPS interpreter in a non-CPS
call/cc can be a bit magical, but adding it to our
interpreter isn't too hard since we already have continuations. Like
most language features, we just need to add one line to the interpreter:
((call/cc ,e)
(value-of-cps e env
(lambda (f)
(f (lambda (v k^) (k v))))))
This is once again similar to the application line. We evaluate the
argument, which should yield a procedure, and then we apply it to a
new procedure that captures the current continuation. Notice that this
continuation has access to two continuations.
k^ represents the
continuation at the point that the procedure is applied and
represents the continuation that was active when we evaluated
call/cc. In this case, we ignore
k^ and instead apply the
continuation that
call/cc captured.
We've had a quick introduction to continuations, continuation passing
style and how to use this in a Scheme interpreter. From there, we show
that having a CPS interpreter makes it easy to add
call/cc. Continuations open up a lot of interesting control flow
possibilities. For example, calling a continuation is not too
different from throwing an exception that is caught
later. Continuations can also be used to interleave the execution of
two threads. I hope to explore some of these options in more depth in
later posts.
The thing that surprises me most about UEFI is that it now appears possible to boot your machine without ever writing a single line of assembly language. Booting used to require this tedious process of starting out in 16-bit real mode, then transitioning into 32-bit protected mode and then doing it all over again to get into 64-bit mode. UEFI firmwares, on the other hand, will happily load an executable file that you give it and run your code in 64-bit mode from the start. Your startup function receives a pointer to some functions that give you basic console support, as well as an API to access richer features. From a productivity standpoint, this seems like a win, but I also miss the sorcery you used to have to do when you were programming at this level.
Booting to Rust is a lot like writing bindings to any C library, except that the linking process is a bit more involved.
I was trying to find the simplest way to get my code running. As such, I'm not sure I did this in the most official way, or that my terminology is totally correct, but here's something that worked.
UEFI firmware works around this idea of applications. These could be things like a shell to help you troubleshoot a broken computer, but most of the apps seem to be bootloaders. As far as I can tell, a bootloader is just an app that transfers control over to an operating system rather than returning control to the firmware.
One of the things that confused me is that all of the example code I could find was written in C. I always thought code that runs this early in the boot process should be written in assembly language. The difference is that now a lot of this early boot code is handled by the firmware. Thus, you just have to run a program that looks kind of like this example from over on the OSDev wiki
1 2 3 4 5 6 7 8 9 10 11 12 13
I'm not super wild about all of the extra code this example uses from an EFI library, but fortunately the spec tells us what we need to know to recreate this. Now we can look at how to do a similar program in Rust.
Much of the UEFI spec looks like reading C header files, since the API that UEFI exposes to applications is basically a C API. This is fantastic, because Rust has always had very good C interoperability. Basically, we just have to transcribe the various structs and function pointers and start writing our application. Here's what the system table struct looks like.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
It's basically a transliteration of the C definition. However, we do start to see the advantages of using a higher level language like Rust. For example, we can mark the
Reserved field in
EFI_TABLE_HEADER as private to make sure nothing uses this when it's not supposed to.
You'll notice I left out a lot of fields from the structure. For now I'm just trying to get a simple Hello, World program running, which means all I need is text output. For the same reason, I leave the
EFI_SIMPLE_TEXT_INPUT_PROTOCOL struct completely unspecified:
EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL, we define just enough to output a string.
1 2 3 4 5 6 7 8 9 10
One thing I like about this code is that all you have to do to access functions provided by the UEFI firmware is declare a function pointer. You can then call this function just like any other, although you must call from an unsafe block.
Now we have enough to write our UEFI entry point. The skeleton of it looks like this:
1 2 3 4 5
This function just does an infinite loop. The return type is probably not exactly correct, but we don't need to worry about this since our function doesn't return anyway. Building from this, we can fill in the function to print "Hello, World!"
Ideally, we'd just do
SystemTable.ConOut.OutputString("Hello, World!"). Unfortunately, it's not quite that simple. One problem is that Rust represents strings as UTF-8, while UEFI's console output needs UTF-16 strings. We'll deal with this for now by rather verbosely making an array of
u16s where each element is filled with a character casted to
u16, such as
'H' as u16. We also need to be sure we set the last element to 0, and we should add both the carriage return (
'\r') and linefeed (
'\n') characters. Once we have this array, we use
transmute to get a
*u16 that points to its contents.
We're working with a lot of unsafe pointers, so we'll put the whole body of
efi_main in an unsafe block. We'll also have to be rather explicit about where we are dereferencing our pointers.
Here's the code to print out hello world:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
We had to define
transmute as a Rust intrinsic directly, rather than using the version that's in Rust's standard library. The reason is that we can't use Rust's standard library because we don't even have an operating system.
Now that we have our program, we need to figure out how to run it.
Rust generally assumes you are writing programs that you want to run on your own machine, meaning it generates binaries in the format that the host operating system expects. On Linux, for example, these are ELF files. According to the UEFI spec, we need a PE32+ file, and it needs to be marked as using subsystem 10, meaning it's a UEFI Application. Fortunately, the Linux linker can generate nearly any binary format known to man.
We'll have to tell Rust to only compile our program and not link it,
and then we'll write the linker command ourselves. Let's say our
program was in a file called
boot.rs. You can see my
here. We
compile it using this command:
This creates a file called
boot.o, which we can then link.
My linker didn't support the right output format by default, so I had
to install a cross-linker. I was running Gentoo, so I got this by
sudo crossdev -s0 --target x86_64-efi-pe.
Once we have an appropriate linker, we build our PE file as follows:
That's quite a mouthful. Let's break down the options.
x86_64-efi-pe-ld – this is what
crossdev called my custom linker.
--oformat pei-x86-64 – Generate a PE32+ file containing 64-bit code.
--subsystem 10 – set the subsystem to 10. This tells the firmware
that this is a UEFI application.
-pie – generate position independent code. This is important. This
program runs before virtual memory is enabled, so the firmware might
have to relocate your program if the addresses you requested were
already in use.
-e efi_main – set the entry point to
boot.o – this is the file we are linking.
-o boot.efi – call the result
I also had to add the
#[no_mangle] attribute to
efi_main in the
Rust code so that Rust would not use a different symbol name in the
final object code.
The first time I ran this, the linker complained that
was missing. The easiest way to deal with this is to add the
#[no_split_stack] attribute to whatever functions report that symbol
as missing, which in our case is
efi_main. This attribute prevents
LLVM from inserting the stack safety checks.
When all is said and done,
file reports that we have the correct
kind of executable:
There's one more issue we have to deal with, which is calling conventions. Calling conventions describe rules for where function arguments go when you call a procedure. For example, some calling conventions say all arguments go on the stack, while others pass some parameters through registers. Rust purposefully leaves its calling convention undefined for now, so we don't really know what's going to happen. Let's take a look at some assembly and see what we get.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Let's work backwards through this to see where this code expects its arguments to come from. We know our function made one procedure call, which seems to be the
callq instruction on line 16. Line 16 calls the procedure pointed to by
rax, and we see this value is assigned in line 6. This reads the value at 8 bytes away from the
rsi register, which in turn came form 32 bytes offset from the original value of
rsi. If you work out the field offsets from the system table struct and the console output struct, we see that Rust assumed the pointer to the system table was in
The UEFI spec, however, says that the system table will be in
when it calls your entry point. The calling convention described in
that document for x86_64 happen to match the convention used by
Microsoft Windows. Rust didn't support this convention by default
(although it is probably the convention used when you run Rust on
Windows), but it was only a
few lines of code
to add support for it. Once we've made this change, we add
as the calling convention and see what the new assembly code looks
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Line 5 shows us reading from
rdx, which is what we wanted.
Now the moment of truth.
The easiest way to boot this code is to stick it on a CD image. The EFI spec states that you can create a file called
/efi/boot/bootx64.efi and the firmware will try to use this file to boot from a removable media. I used
mkisofs to build an ISO image with the right format.
In theory I could burn this to a CD and boot an EFI-capable computer off it. I'm not quite brave enough to try this yet, so I used VirtualBox instead. I created a new VM, saying the operating system was an other/unknown 64-bit OS. In the system settings, I had to check the Enable EFI option as well. Then, I pointed the virtual CD-ROM device at my ISO image and booted the machine.
It worked!
Okay, so it didn't actually work on the first try. It took a while to get the PE file format right, the calling conventions correct, and all the pointers pointing to the right place. Fortunately, once that much is done, adding more functionality shouldn't be hard.
So we've covered how to make a minimally interesting EFI application in Rust. The next step is to fill out the EFI API and start building more interesting applications, such as a full-fledged operating system. The initial working version of this code is available here. Since then, I've cleaned it up and added a few more pieces. You can see the latest version at the location below.
The first step is to find out where we are spending our time so we know what to try and optimize. I had a hunch that I was pretty sure about, but it's good to have some data to confirm our suspicions. We start with the code from last time, but add timing statements like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The function has two phases. First, it has to copy the data in from the host program. Secondly, it launches a kernel to actually perform the dot product computation. To get a very non-scientific idea of how we are spending our time, we just have to run the program a bunch of times. A typical run on my machine generates results like this (note that these results are using OpenCL on the CPU instead of the GPU):
1 2 3 4
We can see that we're actually spend the majority of our time copying the two input vectors around. This accounts for half a second, while the actual computation time is only 375ms. Incidentally, it's not terribly uncommon to spend more time shuffling data around than actually computing on that data. This is why techniques like zero copy are so important.
We'll try two things to improve the performance: ensuring compiler optimizations are enabled, and making compiler optimizations work better.
There's an adage that says there's a difference between optimization
and not being stupid. This "optimization" truly falls in the not being
stupid stupid category. The function
import-float-vec relies on the
unsafe-deref-float and
unsafe-set!-float functions, which I
implementated builtin functions. Thus, most of the time in these
functions is actually spent in the runtime. When I checked the
Makefile for the runtime, I realized I had never enabled compiler
optimizations. My thinking was probably something like "oh, we don't
need optimizations, since all the interesting computation in Harlan
happens in OpenCL kernels." It was easy enough to pass the
-O2 flag
to the compiler and see what happens. After this change, the results
look more like this:
1 2 3 4
We've shaved off about 82ms, which is actually more than I
expected. Also, we see a bit of an artifact in the data, which is that
importing vector
b takes half the time of vector
a, even though
they are both the same size. It seems the timer I'm using only has a
resolution of about an eighth of a second. This isn't great, but it's
good enough for our purposes.
The body for the
unsafe-deref-float and
functions are one line of code. They are a single memory reference
each. These are cheap and really should just be open coded by the
compiler. I didn't do it this way at first because I would have had to
push a new language form through a lot of the compiler and wanted
something quick and dirty. This would be easier if more of the
compiler used the Nanopass framework. However, these functions are
prime candidates for inlining, and compilers are pretty good at
inlining. Writing these functions this way shouldn't be a problem
because the compiler will just inline them away. After all, just look
at this section of the disassembly from
import-float-vec and see how
there are no procedure calls:
1 2 3 4 5 6 7 8 9
Oh, just kidding! There are calls to
unsafe-deref-float and
unsafe-set!-float. Since these functions are just a single memory
reference, I wouldn't be surprised if we're paying ten times the cost
of the function in just call overhead.
The problem is that the compiler cannot inline these functions because
they are in a separate library. Instead, we want to include these
functions in the source code we are compiler. The easiest way to do
this is to move their definition to
harlan.hpp, which is included in
every Harlan program. After making this change, the performance looks
something like this:
1 2 3 4
Now we're spending the majority of time in the kernel, which is what we'd like.
Here's the chart from last time, along with our new results.
We've got a ways to go still, but this is a significant improvement over where we were before. The next step is to dig deeper into the why the kernel time is as large as it is.]]>
I'm happy to report that it's now possible to pass non-trivial amounts
of data from C++ to Harlan. Two new features made this
possible. First, there are library functions like
unsafe-set!-float which allow reading and writing from raw
pointers. Second, there's a new primitive form called
which gives a raw pointer to the contents of a vector. These are very
low level, but they give us the tools we need to build a reasonably
usable FFI. Let's see how to use these to implement a dot product in
Harlan and use it from a C++ program.
First, we need to write the dot product function. This is pretty short in Harlan.
1 2 3 4 5 6 7
For the most part, this is a straightforward dot product written in
Harlan. The main new thing is the call to
import-float-vec, which
copies a C-style array into a Harlan vector. If you're curious, it's
implementation is in ffi.kfc.
Unlike most Harlan programs, this does not define a
function. Instead, we compile it to a shared library by running the
following from your Harlan directory.
When this is done, you'll have a
dotprod.so which you can link to
your C++ programs. The
harlan_dot function is exposed under the
float harlan_dot(int N, float *pa, float *pb).
Now, let's plug this function into the dot product benchmark I wrote
about previously. Basically, we add a prototype for
then add a call to
TIME(harlan_dot) along with the rest of the
benchmarks. You can see the full set of changes
here. I
commented out the CUBLAS version because I ran into runtime errors
that I didn't feel like debugging. Below is a graph of how Harlan
compares with the other implementations.
Clearly I've got some performance issues to deal with. On the bright side, Harlan runs faster on the GPU than it does on the CPU. I'll be investigating these performance problems soon.
As far as the FFI goes, there are some usability issues that remain too. For example, the Harlan compiler and the code it produces have some relative paths hard coded, which means they must run from the Harlan source directory. These shouldn't be hard to fix. In the meantime, it's now possible to integrate Harlan code into projects written in other languages.]]>
We'll start by writing an interpreter for a small but interesting subset of Scheme. Then we'll show see how to add debugging features to the interpreter. As usual, you'll be able to see all the code on Github.
We'll start with the so-called "Three Line Interpreter" and then add a
few features to make it a bit more interesting. If you're familiar
with Scheme interpreters, feel free to skim this section. If you want
more detail, check out the Essentials of Programming Languages. Our
value-of, takes two arguments. The first is the
expression to evaluate, and the second is the environment that maps
variable names onto values. Here's the interpreter:
1 2 3 4 5 6 7 8 9
It's a few more than three lines, but we're mainly interested in the
three match clauses. The first line is the variable reference
line. If you try to evaluate something like
x, we use
lookup to go
find the current value of
x in the environment. I'll omit the
definition of lookup, but it's basically the same as
(cdr (assq x
The next line is the lambda line. This creates a procedure from a
lambda expression. We cheat and use perfectly good Scheme's built-in
lambda. Notice this procedure we create takes a value,
v, and then
value-of on the body of the lambda. The important bit is the
(cons (cons x v) env), which adds a binding of
x to the value that
was passed in to the environment, so that the interpreter can find the
correct value when evaluating the body.
Finally, we have the application line. Basically, we use
catamorphism feature to recursively compute the value of both the
thing to be applied and the value to apply it to. Since our lambda
line evaluates to Scheme procedures, we just apply the value
e1 to
its argument,
Although this doesn't seem like a very rich language, you could use it to compute any computable function if you wanted to. You probably don't want to though.
Now that we have the core of our interpreter, we can add features to
the language. In most cases, this is as simple as adding a few more
clauses to our
match expression. Let's start with numbers.
1 2 3
The first line leaves numbers as they are. There's not really much more to do with them.
The second line lets you do things to numbers. We make sure the
operation is one of
* or
-. We could add more, but these are
enough for now. I cheated once again and use
eval to convert the
symbol representing the operator into the Scheme procedure that
performs that operation. As before, we use catamorphism to evaluate
the two arguments to the operator.
To make debugging a little more interesting, let's add some side
effects. We add
set! with the following
match clause.
1 2
Of course, this isn't very interesting without knowing what
update-env! does. Here you go!
1 2 3 4
Basically, we just search through the environment until we find the
variable to change and then use
set-cdr! to change its value.
Finally, let's add
begin. We could simulate this with lambdas and
function applications, but it's much cleaner just to add it
directly. We get begin with this clause:
1 2 3 4 5 6 7 8
We start by evaluating each of the first expressions for their effect, and then we return the value of the last expression.
At this point, we have enough that we can start to write some reasonably interesting programs. In particular, we can write programs that have bugs that we might want to debug. Let's add a debugger!
The first thing we're going to do is add a way to get into the
debugger. Most of the time the debugger does this by loading the
source files and letting you click on the point in the code where you
want a break point. This takes more UI work than I want to do right
now, so instead we'll just add a special command to our language,
(debug), which breaks into the debugger. As usual, this is as simple
as adding another match clause:
1 2
This calls out to a function we have yet to define, called
debugger. We pass in the environment debugger needs to see the
environment so we can inspect it.
The debugger itself is just a read-eval-print loop (REPL). It prompts the programmer for a command, then evaluates the command, prints out any results and then continues. Let's start with a debugger that we can get out of:
1 2 3 4 5 6 7 8 9 10
We start out by printing
debug> and then using
read to read in an
S-Expression. Much like our interpreter (in fact, this is just an
interpreter for another language), we use
match to determine which
command we're given and then evaluate it. For now we support one
(continue), which continues the execution of the
program. We do this by setting a flag that tells the debugger not to
continue it's loop. Since we were called by
value-of, we just return
to that function and the interpreter picks up where it left off.
Here's an example debugging session:
1 2 3
At the Scheme REPL, we call
value-of with a simple expression that
immediately breaks into the debugger, and we start in the empty
environment (
Most debuggers give you some kind of call stack. The closest analog to that in our language is a list of all the variables in scope, so let's add a way to see these. Once again, we add one more match clause:
This just forwards to a procedure,
show-env, which prints out the
values in the environment. Here's an example of how to use it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
So now we can stop the execution, continue the execution, and see
what's in the environment. What if we want to change things? We could
add commands to set values, but a more powerful way is to use the
target language itself to do this. Thus, we'll add an
eval command,
which evaluates an expression in the debugger:
1 2
Now, if we want to change values, we can just evaluate a
expression, like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
As expected, the resulting value changes to reflect the fact that we modified the environment during program execution.
So there's a first steps towards a Scheme debugger. We were able to do this with relatively few changes to our interpreter. It seems to me that adding more advanced features would require more changes. For example, there's no way to inspect or change the code that's running now. To do this, we would have to keep track of this data in a form that is accessible to the debugger. Furthermore, we're still missing a way to do finer grained execution control, such as stepping over a single statement or out of the current lambda. I suspect most if not all of these problems can be solved by writing our interpreter in continuation passing style. I hope to explore this in a later post.]]>
Iota and Jot are examples of Turing Tarpits, that is, languages "in
which everything is possible but nothing of interest is easy." The
term comes from Alan Perlis. Turing Tarpits have some utility. The
Lambda Calculus is arguably a Turing Tarpit, and yet it is quite
useful in the study of programming languages and computability. Iota
is notable as a Turing-complete language which consists of only two
symbols. For example,
*i*ii, and
**iii are all legal programs
in Iota. Sadly, some strings, such as
i*i are not legal. This makes
Iota less than ideal for enumerating many programs, as we can't choose
arbitrary strings but must instead be sure we follow the grammar. Jot
was designed to fix this. Jot has the property that any binary string
is a legal program.
Using Jot, it's now incredibly easy to enumerate large numbers of programs. The next step is to plot the behavior. We chose to see how many steps a program executes for before terminating (or until we give up, as not all programs will terminate), and then use this to generate a color for a certain point. Below is an animated example of what we ended up with.
This visualization works by generating a random bit string, then converting it to a real number, and then mapping this into 2D space using a Hilbert Curve. The color indicates how long the program at that point took to execute, and the larger dots also indicate longer-running programs. Black dots indicate programs that didn't terminate in time.
You can see this and several other examples on our gallery page. You can see more details about our approach in our paper.]]>
Indiana University has for years taught their introductory computer science courses in Scheme. The more advanced programming language concepts and compilers courses are also taught in Scheme. This means we had were starting with a lot of experience in writing compilers and exploring programming languages with Scheme. In fact, Will Byrd did his dissertation on a logic programming language embedded in Scheme. We were starting off as Scheme experts.
Joel Spolsky advises not to "start a new project without at least one architect with several years of solid experience in the language." In our case, we knew how to implement languages in Scheme, and were proficient at some of the powerful tools available to Schemers, like the match macro. We considered other tools, like ROSE or Wave, but we found that we were losing too much productivity in the time it took to learn the tool. Early on, I even tried modifying Clang. While I found the Clang code to be very well designed and easy to modify, it was also clear the they had built a production compiler which made it less suitable for the kind of experimentation we wanted to do. The Clang code was set up so that failing to implement proper error messages led to compiler errors. These things are one of the reasons Clang is such a fantastic compiler now, but we had different goals.
Lisp, the ancestor of Scheme, is an abbreviation for "list processing." The natural data structure in Lisp and Scheme is the list, and trees are just lists of lists. Compilers spend a lot of their time manipulating abstract syntax trees, so using a language that's built to manipulate trees makes a lot of sense.
We built Harlan using a the nanopass philosophy. The compiler is structured as many passes that are each responsible for making one fairly small change to the language. This has a lot of benefits. It's been easy to refactor or rewrite portions of the compiler as necessary. Most passes can be written or rewritten in an afternoon. Each pass is easier to debug because it's only concerned with a small portion of the language. We can insert optimization steps at the right level of abstraction. For example, kernel fusion happens relatively early because it is a high level, structural optimization. On the other hand, it would make sense to put more traditional compiler optimizations, such as common subexpression elimination a bit later when the language is lower level.
Macros are a favorite feature of any serious Schemer. Basically, they let you build the perfect language for whatever program you happen to be writing. We realized early on that with our many compiler passes, we could run into problems where language forms might leak further through the compiler than they're meant to, or a poorly written pass might generate outright invalid code. To combat this, Claire wrote an awesome grammar verifier, which checks to make sure that the output of each pass conforms to some grammar. At times it was tedious to have to go through and update the grammars when the language changed, but overall I'm convinced that this has saved us time by forcing us to keep the code quality high.
Andy Keep has pushed this idea to the extreme with his Nanopass Framework, which we've started using in the newer Harlan passes. With the Nanopass Framework, you can define a language, and use this to guide the development of compiler passes. Each pass transforms one language into another, and subsequent languages are specified in terms of deltas from the previous language. The Nanopass Framework makes sure that all language terms are well formed. Language terms are represented as records, which are more efficient than plain old lists. The coolest part of the Nanopass Framework, however, is that it can automatically generate many of the transformers. This lets you focus on the portions of the language that change, rather than duplicating language forms that remain the same.
Parsing isn't a terribly interesting problem. One of the great consequences of Scheme's homoiconicity is that you basically have a universal grammar built in. Rather than writing a parser, we just read in S-expressions from a file and go to town. We originally envisioned a C-like syntax for Harlan, but decided we wanted to focus on the implementation and do parsing later.
As I understand it, this is basically how Lisp's syntax came about. The implementors didn't want to spend a lot of time on parsing at first, so they decided to write programs in the actual abstract syntax tree. Over time, the syntax stuck. A similar thing happened with Harlan. We intended to design a more traditional syntax for the language, but the fact that we had S-expressions influenced the design of the language. For example, we realized many of the forms we wanted in Harlan could be implemented as source level transformations, and so we added a macro system to enable this.]]>
A couple years back we started working on the design of a new language to handle GPUs. One of the initial observations was that people seem generally pretty content with languages like C or even Fortran for specifying computational code, but one of the difficulties in GPU programming is managing the data transfer between host and device memories and also within the memory hierarchy on the GPU. It seemed like this was an area that was ripe for a new language to address. Thinking about it some more, we realized the computational kernels really decide when data needs to be where, so we should let our language schedule data transfers around kernels. Indeed, the language we designed has no way of explicitly doing data transfers, but instead these are driven by the computations being done in kernels.
It became clear that kernels would play an important part in the
language we were building. The word "kernel" happens to sound a bit
like "colonel," and one particularly famous colonel is
Colonel Sanders. My advisor mentioned that Colonel Sanders' first
name was Harland, but I misheard this as Harlan, and by the time we
figured this out, the name Harlan had already stuck. This is also why
all of the test cases have the file extension
It's fitting, in a way, that we accidentally dropped the last letter from the name, given that a similar thing happened with Scheme, the language in which Harlan is implemented. Scheme was supposed to be called Schemer, but the operating system at the time limited filenames to only six characters, so the "r" was dropped.
Harlan is a new programming language for GPU computing. Harlan aims to push the expressiveness of languages available for the GPU further than has been done before. Harlan already has native support for rich data structures, including trees and ragged arrays. Very soon the language will support higher order procedures.
To give an example of the look and feel of a Harlan program, below is a simple N-Body Simulation program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
The language is still research quality, but I have worked hard to keep it fairly usable. I'd encourage you to try it out and let me know how it works for you!
This is work that I've done with my advisor, Andrew Lumsdaine of CREST, with significant contributions from Claire Alvis, Will Byrd, Ryan Newton, and Arun Chauhan.]]>
Recall that macros are basically programs that transform your program's code, rather than runtime values. In doing so, they may introduce new variable bindings. If we're not careful, these new bindings can end up capturing variables in your own code. That is, the new binding might shadow a variable you as the programmer have already created. All of a sudden, the variable you thought you were referring to is no longer the same thing, and because all of this code is hidden in a macro expansion, it will be very hard to figure out what's going on.
Consider the following Scheme macro for
1 2 3 4 5
Like a good macro, this uses a temporary variable,
t, to avoid
e1 twice and potentially duplicating any side effects in
that expression. Unfortunately, if we're not careful, this binding can
capture an existing binding of
t. Consider the following program.
1 2
If you run this in the Scheme REPL, you should get
5. Let's see what
happens if we blindly expand the
or macro without regard for
hygiene. We would end up with the following program.
1 2 3
This program evaluates to
#f, which is the exact opposite of what we
were supposed to get! Expanding our macro has shadowed the binding of
t to
5 with a binding of
t to
One way to work around this, which was a common trick for LISP
programmers of yore is to choose variable names that a programmer is
unlikely to guess. We could rewrite our
or macro like this:
1 2 3 4 5 6 7
This works okay, except it's a lot more typing. Eventually, some
overly clever programmer is going to name their own variable
this-is-my-super-secret-name-which-you-will-never-guess, and then
their program will break in really unexpected ways. It'd really be
great if our macro expander could take care of these issues on its
own. That way, the macro writers could type less and use names they
like, and macro users don't have to worry about their variables being
captured unexpectedly.
We could modify the macro expander to automatically rename any
variables bound by a macro expansion. In this case, our simple test
program would expand as follows, using our first definition of
1 2 3
This program evaluates as expected, so things are looking good. But, what if someone writes this program?
1 2
We'll use our variable-renaming expander and see that we end up with the following program:
1 2 3
This program once again evaluates to
#f instead of
5 like we'd
like it too. This illustrates the second, and more subtle, class of
hygiene error. The problem is that the programmer's definition of
has captured the
if used by the expansion of
or. Now, many
languages treat keywords like
if specially and don't let you name
your variables after them. Enforcing a rule like that in Scheme would
solve this particular case, but at the cost of a lot of the power that
Scheme programmers love. The proper solution is to find some way of
tracking what
if was bound to when the
or macro was defined and
using that version in the expansion of
Properly maintaining hygiene in macro systems turns out to be really tricky. The reward is worth it, however, as programmers can then reason much more easily about the behavior of macros and start to rely on them in large projects. Macros are a powerful feature of programming languages, and many newer language have some form of macro system. Sadly, these are often not hygienic, or they so "Oh, we'll add hygiene later." Given how important hygiene is, and how tricky it is to get right, language designers should really implemented hygiene in their macro systems from the very beginning.
Let's consider an example program written in Harlan:
1 2 3 4
I believe this is the first time I've included Harlan code snippets in my blog, so some introduction is in order. Harlan is a high level language for data parallel computing that I've been working on for a while now as part of my Ph.D. research. You can read our initial paper about Harlan here, although it will be immediately apparent from the drastically different syntax that the language has evolved significantly in that time.
The primary construct for parallelism in Harlan is the
form. Syntactically, this looks like Scheme's
let, in that it takes
a list of variable names and expressions to bind the names to, and
then a body describing what computation to do on those variables. The
difference is that each of the bound expressions must be a vector, and
the result of a kernel is another vector. Furthermore, each input
vector must be of the same length, and the result of the kernel will
have the same length as its inputs. Kernels operate on parallel, with
the body being applied to each corresponding set of elements in the
inputs. You can think of kernels as a parallel map or zipWith.
In the example above, if we imagine
x* and
y* as containing the X
and Y coordinates of a set of 2D vectors, then the code snippet
calculates the magnitude of each of these vectors. As written,
however, we have a couple of obvious inefficiencies. This example
allocates space for the result of the first kernel,
temp*, which
could be significant if
x* and
y* are very long. Secondly, both
kernels are tiny—that is, they have low arithmetic
intensity. Arithmetic intensity is a measure of how many arithmetic
operations we have for each memory reference. If it is low, we won't
be using the full computational power of the GPU.
Fortunately, we can solve both of these problems with the first form of fusion, which I feel is better called kernel inlining. With kernel inlining, we would transform our program into the following:
1 2 3
In case it's not clear what happened, we took the body of the first
kernel and inserted it into the second kernel. In doing this, we also
got rid of the parameters to the second kernel and replaced them with
the parameters from the first kernel. Now there is only one kernel,
temp* vector is completely gone, and the arithmetic intensity of
the newly fused kernel is higher than we had before.
This transformation is usually a win when it's possible. We may not
want to do it if, for example, the
temp* array is also referenced
somewhere else. Also, while kernels with higher arithmetic intensity
tend to work better because there is more computation for the GPU to
use to hide memory access latency, it can also increase the number of
registers needed by each thread and thereby limit how much parallelism
is possible.
For the next type of fusion, let's consider the following code that would appear in a hypothetical program to render the Mandelbrot set:
1 2 3
Harlan allows nested kernels like this, but Harlan compiles to OpenCL, which does not support nested kernels. Harlan generally deals with this by sequentializing all but one of the kernels. In this case, we could either transform the out or inner kernel into a loop. However, since the kernels form a grid with no dependencies between them, the compiler can fuse these into a single, two dimensional kernel, which OpenCL does support. The Harlan compiler is able to do this for simple cases like this one.
Let's look at one more form of fusion, although the Harlan compiler does not currently do this form. Consider a program like this:
1 2 3 4 5
Here we have two kernels that execute in sequence with no dependencies
between them. Furthermore, they have the same set of inputs. If we
pretend for a moment that Harlan has a multiple return value form,
like Scheme's
values, we could combine these two kernels as follows:
1 2 3 4 5
In keeping with the general theme of fusion transformations, we now have only one kernel that performs more work instead of two smaller kernels.
We've looked at three different program transformations that could be called fusion. A key point is that they are transformations, not necessarily optimizations. In my experience, these sorts of transformations almost always improve performance, but that need not always be the case. By combining small pieces of code into larger chunks, we reduce the overhead of launching new kernels and also give the GPU more code to use for overlapping memory accesses with computation. On the other hand, larger code could lead to less efficient instruction cache usage, and also lead to more memory accesses if each thread's working set can no longer fit in registers. It's good to be able to do these transformations, but it's important to benchmark and see what works best for each particular program.]]>
Lately I've seen a lot of GitHub repositories that include an image like this in their Readme:
It turns out this is from a free service called Travis CI, which makes it easy to integrate continuous integration with GitHub projects. Basically, this means you can define a set of tests that run every time you push a commit to GitHub, and you'll be notified if something breaks.
Scheme was not one of the languages with first class support, but fortunately we can make it work. Here's how.
Travis CI gives a lot of flexibility with the scripts you can run on their servers. Thus, we will pretend that we are a C project, and that our build process installs Petite Chez Scheme. Once that's done, we run a small wrapper script which launches our Scheme test suite.
First, we need a script to install Petite. You can find our script here, but I've included the contents below.
1 2 3 4 5 6 7 8 9 10 11
Notice that we can use sudo within our script. This is because Travis CI gives you your very own virtual machine and allows passwordless sudo. Once your tests are done, the VM is destroyed and your next build will happen on an entirely new instance.
Next, lets assume our test suite is called
run-tests.scm. We can
then create a simple wrapper script to execute these. Be sure to
mark it as executable before you check it in.
1 2 3
Some of the parameters will be specific to your project. For example,
the Elegant Weapons code lives in the
lib subdirectory, so we are
sure to add this to the compiler's load path.
Finally, with all the necessary pieces, we can create the
file that will actually enable our project with Travis CI:
1 2 3 4 5 6 7
Once you add this file to your repository, push it to GitHub, create your Travis CI account and enable Travis CI for your repository, you should have your tests automatically running.
Obviously, these instructions have been unique to Petite Chez Scheme. It should not take too much trouble to adapt these to your Scheme implementation of choice. In the future, I hope to learn how to automatically run the tests on a variety of Scheme implementations to help keep us honest as far as portability is concerned.]]>
I was amazed at how many people felt the need to put "IPDPS 2013" on every single slide in their presentation, as if I might forget what conference I'm attending. I suspect this is the result of some Beamer template being helpful, but really it's unnecessary. Some helpful presenters even thought it'd be useful to remind me on every slide that I'm in Boston. Even if I was somehow unaware of my location, the fact the we are in Boston likely does nothing to help me understand the information you are trying to convey to me. In the same way, if I wanted to know the date, I'd look at the cell phone in my pocket, rather than at your slides.
That said, often slides are posted on web sites afterwards for archival purposes, and in this case the conference name and date actually are somewhat useful. Putting this information on the title slide is sufficient. It doesn't need to go on every slide.
One piece of information that I realized would actually be useful to have on every slide is the title of the talk. I was surprised at how many times we were on about slide 3, chest deep in technical details and I realized I had completely forgot what the point of it all was. The fact is, most of us in the audience are not giving you our complete attention. Make it easy for us to try to tune back in by keeping some kind of a reminder of the big picture on every slide.
Put as little text as possible on your slides. If you can, come up with a clear graphic or tasteful animation that makes your main point clear. The sooner I can understand your main point, the easier it will be for me to put the rest of your slides in context and avoid the existential crisis mentioned in the previous point.
Make your graphs easy to understand. Often they will have some of the smallest text in your presentation, which means I won't be able to read it. That's fine, since graphs are about presenting information visually. Generally, the only thing I'm looking for in your graphs is how much better your system is than the ones you compare against. Make this easy for me. Clearly indicate whether up is better or down is better. Even better, be consistent and set up all your graphs so that up is always better or down is always better. Make it really clear which bars are lines are your system. Make them a brighter color, bold your system's name in the legend, or put an asterisk next to it. This is particularly important if you are comparing a bunch of systems whose names are all acronyms.
You don't need to include every graph from your paper. Focus on the key ideas. What are the major results that will make me want to read the rest of your paper? I can get all the nitty gritty details once I decide to read your paper.
For each graph you do include, spend some time telling me what I am supposed to see in it. Remember the saying, a picture is worth a thousand words. You can't adequately explain your picture with a dozen words. You need to say more than "here is our memory usage." Why is this result significant? Does it show your system if far faster than anything else? Does it show you have excellent scaling characteristics? Does the chart show you are only marginally worse than other systems, but yours provides other important benefits to make it worth the sacrifice? You should be trying to convince me to adopt your ideas in my own work. How does your graph help convince me of that?]]>
Map takes as input a vector and an operation, and returns a new vector
that is the result of applying the operation on each element of the
vector. For example, we can map
add1 over a vector to increment each
element by 1:
1 2 3
Related to this is
zip-with, which takes some number of equal-length
vectors and applies an operator to corresponding elements in each
vector. For example, we can add two vectors using the
+ operation:
1 2 3
Map and zip-with can work on segmented vectors as well, and the result will have the same shape as the original:
1 2 3
However, if we try to apply
zip-with on vectors with differing
shapes, we will end up with an error.
Reduce takes a vector of elements and combines them into a single element using a given operation. The operator \(\oplus\) must be an associative binary operator. It helps if the operator has a 0 element, that is, one for which \(a \oplus 0 = a\) and \(0 \oplus a = a \). We can do even better if we know the operator is commutative.
Below is an example of how to add all elements in a vector:
1 2 3
We can similarly define a segmented variant of reduce, which results in a vector containing the reduction of each segment. For example:
1 2 3
The two operators we've seen before are very powerful. We can define many linear algebra operations in terms of them, and they all form the basis for MapReduce. Still, there are cases where more operators are extremely helpful.
Scan is like reduce, except that it returns a vector of all of the intermediate results. Here's an example:
1 2 3
Each entry in the resulting vector is the sum of all of the elements to the left of the corresponding element in the source vector.
Scan is often handy as an intermediate step in a larger computation. For example, we may have a vector of vectors where the lengths of the inner vectors vary wildly. In this case, scan can be used to help balance the work between some number of worker threads.
Permute is used to rearrange elements in a vector. It takes a vector, of course, and also a function that maps indices to indices. The element at the input index will be stored in the output index. Here's a basic example that reverses a vector:
1 2 3
There are a couple of caveats. Suppose our mapping function were
i ->
0. If we apply this to the vector
[1 2 3 4], all of the elements
would be mapped to the first position and there would be nothing for
the later positions. To solve the first problem, we can provide a
combining function that is used when multiple elements map to the same
location. For example, we may want the maximum value of all elements
that map to a given location. For the second problem, we can provide a
default element that is used when none of the inputs are mapped to a
certain output location. Of course, now our permutation function is
more complicated to use and also more complicated to implement.
In many ways, back-permute is a simpler version of permute. Back-permute also takes an input vector and an index mapping function, but instead of mapping input indices to output indices, it maps output indices to input indices. Because of this, we don't have the problem of multiple values mapping to the same location, as the mapping function can only produce one value. This also means we can avoid the combining function. That said, because this function is simpler, it is also less powerful than permute.
All of our operators so far except for reduce have essentially mapped some number of inputs to the same number of outputs. Sometimes we need to remove elements that we are working with. An example is when writing Quicksort. We'd need to split a vector into one vector containing those elements greater than the pivot and another containing those elements less than the pivot. Using filter, we could do this as follows:
1 2 3 4 5 6 7 8 9 10 11
Many of these operators can be written in terms of other ones. For example, you can get reduce from scan by reading the last element of the result and adding the last element of the input. This version will probably not be efficient, as it may allocate far more storage than necessary. In designing a data parallel system, one important decision is which operators will be considered primitive, and which will be built in terms of others. Ideally, these decisions should consider the characteristics of the underlying hardware. In Guy Bleloch's book, Vector Models for Data-Parallel Computing, he argues in favor of a set of primitives that can execute in about the same amount of time it would take to read the input vector from memory. Similarly, when implementing a data parallel system for GPUs, it's important to consider what operators are easy to implement. Map and back-permute are pretty straightforward, but others are more difficult. Ideally, upon choosing a good set of primitives, the compiler and runtime can optimize the other operators into efficient code.]]>


text:
If your source is true, and the jury is still out on that one.
40 million gallons of free gas a year!
Oh the horror!
That's about 1/10 of ONE DAYS consumption in the US.
And that's based on a reliable source.
How much gasoline does the United States consume? - FAQ - U.S. Energy Information Administration (EIA)
In 2011, the United States consumed about 134 billion gallons1 (or 3.19 billion barrels2) of gasoline, a daily average of about 367.08 million gallons

subset: commoncrawl


text:
Texas-native and reigning Camping World Truck Series champion James Buescher scored his fourth career top-10 finish at Texas Motor Speedway on Friday night as he crossed the finish line ninth.
He started the race uncharacteristically deep in the field, qualifying 18th despite winning the pole twice before in his career at the 1.5-mile track in Fort Worth, which is about 45 miles from his hometown of Plano.
Fellow sportswriter Terrence Hunley and I met with Buescher, the subject of my Friday column, March 3 at the speedway's Media Day.
The 23-year-old said qualifying wasn't typically a problem, but something always happened during the race to keep him from battling for a win.
He didn't have any major problems in Friday's race and was running sixth with 50 laps, but late in the race he had to struggle to stay in the top 10. He remained sixth in the points standings, 50 points behind leader Matt Crafton, who finished fourth.
The night was more special for Jeb Burton, the son of 2002 Daytona 500 winner Ward Burton, who got his first career victory.


text:
Web Historical Disclaimer:
This is a historical page and is no longer maintained. Read our Web history statement for more information.
Skip to Content
The Robert Strauss Center for International Security and Law and mtvU will be hosting a screening of the documentary film Darfur Now on Tuesday, November 6, 2007 at 7:00pm in CPE 2.214 (View Map). This is a special sneak preview screening, ten days prior to the film's commercial opening in Texas. The film's director, Ted Braun, will be in attendance and will participate in a Q&A session after the screening.
According to the film's producers, Darfur Now is a story of hope in the midst of one of humanity's darkest hours – a call to action for people everywhere to end the catastrophe unfolding in Darfur, Sudan. In this documentary, the struggles and achievements of six different individuals from inside Darfur and around the world bring to light the tragedy in Sudan and show how the actions of one person can make a difference to millions.
Articles about the film have been published this week in the New York Times, Newsweek, and Time:
Newsweek article
New York Times article
Time article
This presentation is part of the Strauss Center's International Security Film Series that screens new and forthcoming documentaries and feature films on topics of global concern, including ethnic conflict and humanitarian intervention. The series is organized and moderated by Strauss Center fellow and LBJ School assistant professor Alan J. Kuperman.
mtvU is MTV's 24-hour college network, dedicated to every aspect of college life--from emerging music to student life to on-campus events.


text:
Home List of Titles Learning social skills with 2D animated social stories for children with Autism Spectrum Disorders
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/226212
|Download Vivi Mandasari Thesis (Adobe Acrobat PDF, 13 MB)
- Title
- Learning social skills with 2D animated social stories for children with Autism Spectrum Disorders
- Author(s)
- Mandasari, Vivi
- Abstract
- Autism Spectrum Disorders (ASD) are a group of neuro‐developmental disorders caused by brain abnormalities which results in impaired social skills. There are five variants of the spectrum: Asperger Syndrome, Pervasive Developmental Disorder - Not Otherwise Specified, Autistic Disorders, Rett's Syndrome and Childhood Disintegrative Disorders. These broad variants produce a wide variety of symptoms among children with ASD, where each child with ASD will have his own pattern of autism; however, all children with ASD will share the same deficits in the areas of social skills which include social interaction, verbal and non-verbal communication and unusual behavior/interest. Research on treatment in helping children with ASD to improve social skills is growing as the cases of children diagnosed with ASD are on the rise. Social Story™ is one of the proven methods of treatment in helping children with ASD to learn social skills. However, the current presentation format of Social Story™ has not been attractive and it requires intensive teacher‐student interaction for the full benefit of social skills acquisition. Numerous studies have proved that children with ASD are motivated and have a better understanding from reading or visual illustration learning rather than learning through spoken instructions. Results from studies have also discovered that the computer is attractive and engaging for children with ASD, as it offers much benefit to them. It has been said that learning is most effectual when motivated, thus, the purpose of this study is to discover a learning tool that children with ASD will be motivated to use on their own, and it is achievable by combining elements that they are interested in. This research focuses on the combination of Social Story™, 2D animation, and the computer as a medium of presentation to present an interactive pedagogical tool for children with ASD to learn social skills. This combination is anticipated to be an effective tool in teaching social skills to children with ASD, as they are naturally drawn to computers and visual cues, combined with the fact that Social Story™ has been effective in changing the social behavior of children with ASD. The prototype titled 'I-Learn Social Story' has been developed and evaluated on thirty children with ASD in a special school located in Kuching, Sarawak. A preliminary study has been conducted on three children with ASD prior to this final evaluation to ensure that the final prototype functions are properly based on the children's needs. The method used in the evaluation study is the quantitative method, specifically single subject design, which is one type of experimental design. Results of the experimental study reveal that the prototype is effective in changing the participants' social behavior and in improving their social skills. There are significant improvements in the appropriate social behavior, decrease in the inappropriate social behavior, and increase in the number of social interactions made by the participants. Thus, this study has contributed to the emergent research of treatment for children with ASD in social skills learning. The result of this study is important as we have discovered a novel method of treatment that can be used effectively in assisting children with ASD to improve their main deficit, social skills.
- Publication type
- Thesis (Masters)
- Research centre
- Swinburne University of Technology. Sarawak Campus. School of Engineering, Computing and Science
- Publication year
- 2012
- Keyword(s)
- 2D animation; Asperger syndrome; Autism; Social skills; Social Story
- Publisher URL
- Copyright
- Copyright © 2012 Vivi Mandasari.
- Thesis Supervisor
- [Lau Bee Theng]
- Thesis Note
- [A thesis submitted in fulfillment of the requirements for the degree of Masters of Science (by Research), Swinburne University of Technology, 2012.]
- Full text


text: EDIT: i forgot about finding the angle CAD. Note that you can find the length of BC in the same way we found AB. once that is found, we can use Pythagoras' theorem to find the length AC. Thus we will know the lengths of all the sides of triangle ACD, and we can use the law of cosines to find any angle in that triangle we want.


text:
The Begin Center presents an annual prize to a person or organized body who accomplished an extraordinary act or acts for the benefit of the State of Israel and/or the Jewish People. Individuals, organizations and institutions are invited to submit nominations to the Prize Committee.
Over the years, the Prize was awarded to numerous exceptional individuals and organizations such as: Ilan Ramon, Israel's first astronaut who died in the Columbia disaster; Kaare Kristiansen, the Norwegian statesman who resigned from the Nobel Prize Committee when it awarded the Prize to Arafat; Rabbi Avraham Elimelech Firer, the remarkable founder of "Ezra L'Marpeh" an organization that has helped thousands in their medical treatment and ability to overcome illness; and many others.
Recommendations should be submitted in writing to our offices at email: firstname.lastname@example.com or to fax: 02-5652010. Nominations will be accepted until September 10, 2009.
In addition, at the Prize Awarding Ceremony, scholarships and stipends in the framework of the 'PERACH' project are granted to exceptional tutors from the Aliza and Menachem Begin Nobel Peace prize Fund, established in 1978 with the money awarded to Mr. Begin by the Nobel Peace Prize Committee.
The Fund's aims include "the granting of scholarshipss, loans and assistance to needy students, giving aid and care to suffering children in order to assure their future and their standing in society" as fixed by Mr. Begin.
At the discretion of the Committee, in consultation with the Center's Executive, additional Awards of Honor have been granted. Among those have been Artur Cohen, Hulda Gurevitz, Prof. Devora Lipstadt, Mordechai Ben-Porat, Ro'i Klein, Emmanuel Moreno, Prof. Yirmiyhau Branover and kidney transplant donor, Eric Swinn.
The Prize CommitteeMoshe Nissim - ChairmanYehiel KadishaiMiriam Glazer-TaasaRaya YaglomDov ShilanskyDr. Meir Rosenne
Previous Awardees
The IDF's Homefront Command's Emergency Search, Extraction and Rescue Unit was the first recipient for their work in Israel and abroad, especially following the earthquake in Turkey.
The "Or M'Ophir" Immigrant Military Academy, working to generate a leadership cadre from amongst immigrants from Ethiopia, received the Begin Prize for their integrated program based on military service and academic furtherance.
The Amana Settlement Organization, promoting Jewish residency throughout the Jewish national home regions was awarded the Begin Prize. Almost 80 communities were established by Amana since 1978 in Judea, Samaria, Gaza, the Galil and Negev in an act of genuine Zionist vision accomplishment.
2002In this year of terror, three organizations involved in aiding terror victims and providing medical and social care were granted the award: Magen David Adom; ZAKA; and the Terror Victims Organization,.
Israel's first space pilot, Colonel Ilan Ramon, had been already selected prior to his unfortunate demise. Having participated in the bombing raid on Iraq's nuclear facility - at the command of Menachem Begin in 1981 - his selection was but natural. The Prize was given to his widow, Rona.
The Nefesh B'Nefesh organization, promoting immigration to Israel from North America and facilitating their absorption in the country, received this year's prize.
Rabbi Avraham Elimelech Firer, founder of "Ezra L'Marpeh" an organization that has helped thousands in their medical treatment and ability to overcome illness, was the recipient of the Prize.
The residents of Sderot, represented by Mayor Eli Moyal, were awarded the Prize for their firm standing in the face of six years of unceasing terror and rocket attacks from Gaza. Their behavior serves as an oustanding example of the spirit of the Jewish People in the face of adversary in the process of the return of the Jewish People to its land and its holding on to its patrimony in Eretz-Yisrael.
The Pre-Military Yeshiva Bnai David at Eli was found worthy to receive the prize for education and preparing a generation of students steeped in faith and sacrifice on behalf of the People and the Land of Israel in a full and significant service in the IDF. Two graduates of the Yeshiva who fell during the Second Lebanon War, Major Ro'i Klein of the Golani Brigade and Lt. Col. Yehuda Emmanuel Moreno of the Sayeret Matkal.
Professor Reuven Orr of the Hadassah University Hospital received the Prize for two major national medical projects he is responsible for: the stem cell and the umblical blood banks.