Planet Haskell

October 23, 2018

Mark Jason Dominus

Getting Applicatives from Monads and “>>=” from “join”

I conplained recently about GHC not being able to infer an Applicative instance from a type that already has a Monad instance, and there is a related complaint that the Monad instance must define >>=. In some type classes, you get a choice about what to define, and then the rest of the functions are built from the ones you provided. To take a particular simple example, with Eq you have the choice of defining == or /=, and if you omit one Haskell will construct the other for you. It could do this with >>= and join, but it doesn't, for technical reasons I don't understand [1] [2] [3].

But both of these problems can be worked around. If I have a Monad instance, it seems to work just fine if I say:

    instance Applicative Tree where
      pure = return
      fs <*> xs = do
          f <- fs
          x <- xs
          return (f x)

Where this code is completely canned, the same for every Monad.

And if I know join but not >>=, it seems to work just fine if I say:

    instance Monad Tree where
      return = ...
      x >>= f  = join (fmap f x) where
        join tt = ...

I suppose these might faul foul of whatever problem is being described in the documents I linked above. But I'll either find out, or I won't, and either way is a good outcome.

[ Addendum: Vaibham Sagar points out that my definition of <*> above is identical to that of Control.Monad.ap, so that instead of defining <*> from scratch, I could have imported ap and then written <*> = ap. ]

by Mark Dominus (mjd@plover.com) at October 23, 2018 01:15 PM

Applicative WTF?

While I was writing up last week's long article about Traversable, I wrote this stuff about Applicative also. It's part of the story but I wasn't sure how to work it into the other narrative, so I took it out and left a remark that “maybe I'll publish a writeup of that later”. This is a disorganized collection of loosely-related paragraphs on that topic.

It concerns my attempts to create various class instance definitions for the following type:

    data Tree a = Con a | Add (Tree a) (Tree a)
        deriving (Eq, Show)

which notionally represents a type of very simple expression tree over values of type a.


I need some function for making Trees that isn't too simple or too complicated, and I went with:

    h n | n < 2 = Con n
    h n = if even n then Add (h (n `div` 2)) (h (n `div` 2))
                    else Add (Con 1) (h (n - 1))

which builds trees like these:

    2 = 1 + 1
    3 = 1 + (1 + 1)
    4 = (1 + 1) + (1 + 1)
    5 = 1 + ((1 + 1) + (1 + 1))
    6 = (1 + (1 + 1)) + (1 + (1 + 1))
    7 = 1 + (1 + (1 + 1)) + (1 + (1 + 1))
    8 = ((1 + 1) + (1 + 1)) + ((1 + 1) + (1 + 1))

Now I wanted to traverse h [1,2,3] but I couldn't do that because I didn't have an Applicative instance for Tree. I had been putting off dealing with this, but since Traversable doesn't really make sense without Applicative I thought the day of reckoning would come. Here it was. Now is when I learn how to fix all my broken monads.

To define an Applicative instance for Tree I needed to define pure, which is obvious (it's just Con) and <*> which would apply a tree of functions to a tree of inputs to get a tree of results. What the hell does that mean?

Well, I can kinda make sense of it. If I apply one function to a tree of inputs, that's straightforward, it's just fmap, and I get a tree of results. Suppose I have a tree of functions, and I replace the function at each leaf with the tree of its function's results. Then I have a tree of trees. But a tree that has trees at its leaves is just a tree. So I could write some tree-flattening function that builds the tree of trees, then flattens out the type. In fact this is just join that I already know from Monad world. The corresponding operation for lists takes a list of lists and flattens them into a single list.) Flattening a tree is quite easy to do:

    join (Con ta) = ta
    join (Add ttx tty) = Add (join ttx) (join tty)

and since this is enough to define a Monad instance for Tree I suppose it is enough to get an Applicative instance also, since every Monad is an Applicative. Haskell makes this a pain. It should be able to infer the Applicative from this, and I wasn't clever enough to do it myself. And there ought to be some formulaic way to get <*> from >>= and join and fmap, the way you can get join from >>=:

    join = (>>= id)

but I couldn't find out what it was. This gets back to my original complaint: Haskell now wants every Monad instance to be an instance of Applicative, but if I give it the fmap and the join and the return it ought to be able to figure out the Applicative instance itself instead of refusing to compile my program. Okay, fine, whatever. Haskell's gonna Hask.

(I later realized that building <*> when you have a Monad instance is easy once you know the recipe; it's just:

    fs <*> xs = do
      f <- fs
      x <- xs
      return (f x)

So again, why can't GHC infer <*> from my Monad instance, maybe with a nonfatal warning?

    Warning: No Applicative instance provided for Tree; deriving one from Monad

This is not a rhetorical question.)

(Side note: it seems like there ought to be a nice short abbreviation of the (<*>) function above, the way one can write join = (>>= id). I sought one but did not find any. One can eliminate the do notation to obtain the expression:

    fs <*> xs = fs >>= \f -> xs >>= \x -> return (f x)

but that is not any help unless we can simplify the expression with the usual tricks, such as combinatory logic and η-conversion. I was not able to do this, and the automatic pointfree converter produced (. ((. (return .)) . (>>=))) . (>>=) ARGH MY EYES.)

Anyway I did eventually figure out my <*> function for trees by breaking the left side into cases. When the tree of functions is Con f it's a single function and we can just use fmap to map it over the input tree:

    (Con f) <*> tv = fmap f tv

And when it's bigger than that we can break it up recursively:

    (Add lt rt) <*> tv = Add (lt <*> tv) (rt <*> tv)

Once this is written it seemed a little embarrassing that it took me so long to figure out what it meant but this kind of thing always seems easier from the far side of the fence. It's hard to understand until you understand it.

Actually that wasn't quite the <*> I wanted. Say we have a tree of functions and a tree of arguments.

three-node tree diagram of the expression below
Add (Con (* 10))
    (Con (* 100))
5-node tree diagram of the expression below
Add (Add (Con 3) (Con 4)) (Con 5)

I can map the whole tree of functions over each single leaf on the right, like this:

tree diagram of the expression below, showing how each of the leaves of the second tree has been replaced by a complete copy of the first tree. The complete tree has five 'Add' nodes and six leaves with values 30, 300, 40, 400, 50, 500.
Add (Add (Add (Con 30) (Con 300))
         (Add (Con 40) (Con 400)))
    (Add (Con 50) (Con 500))

or I can map each function over the whole tree on the right, like this:

tree diagram of the expression below, showing how each of the leaves of the first tree has been replaced by a complete copy of the second tree. As before, the complete tree has five 'Add' nodes and six leaves with the same values, but this time the structure is different and the leaves are grouped by length instead of by leading digit.
Add
  (Add (Add (Con 30)  (Con 40))  (Con 50))
  (Add (Add (Con 300) (Con 400)) (Con 500))

The code I showed earlier does the second of those. You can see it from the fmap f tv expression, which takes a single function and maps it over a whole tree of values. I had actually wanted the other one, but there isn't anything quite like fmap for that. I was busy trying to understand Applicative and I was afraid if I got distracted trying to invent a reverse fmap I might lose the thread. This happens to me a lot with Haskell. I did eventually go back and figure it out. The reverse fmap is

    pamf fs v = fmap ($ v) fs      -- good

or

    pamf = flip (fmap . flip id)   -- yuck

Now there's a simple answer to this which occurs to me now that I didn't think of before, but I'm going to proceed with how I planned to do it before, with pamf. The <*> that I didn't want looked like this:

    (Con f) <*> tv = fmap f tv
    (Add lt rt) <*> tv = Add (lt <*> tv) (rt <*> tv)

I need to do the main recursion on the values argument instead of on the functions argument:

    tf <*> (Con tv)    = pamf tf tv
       where pamf fs v = fmap ($ v) fs
    tf <*> (Add lv rv) = Add (tf <*> lv) (tf <*> rv)           

(This is an interesting example: usually the base case is trivial and the recursive clause is harder to write, but this time it's the base case that's not perfectly straightforward.)

Anyway, this worked, but there was an easier solution at hand. The difference between the first version and the second is exactly the same as the difference between

        fs <*> xs = do
          f <- fs
          x <- xs
          return (f x)

and

        fs <*> xs = do
          x <- xs
          f <- fs
          return (f x)

Digging deeper into why this worked this way was interesting, but it's bed time, so I'm going to cut the scroll here.

by Mark Dominus (mjd@plover.com) at October 23, 2018 03:19 AM

October 22, 2018

Philip Wadler

Co-Recursive Interview


Adam Gordon Bell interviewed me for his Co-Recursive podcast. Thanks, Adam!

by Philip Wadler (noreply@blogger.com) at October 22, 2018 07:38 PM

Functional Jobs

Haskell Developer Position at Karamaan Group (Full-time)

Karamaan Group is an investment firm based in Manhattan. We are looking for an outstanding software developer to develop tools for financial analysis and knowledge management. Since we are investors and not traders, our focus is not on building trading systems, but on business and data analysis. We strongly value people who take pride in their work and have a craftsman’s dedication to building bespoke products. Our ideal candidate is an experienced software developer with a penchant for abstraction and analysis, a solid sense of organization, and an ability to communicate and persuade. While we are looking for a candidate who demonstrates an intense focus on quality, she also needs a master engineer’s intuition for how to make trade offs that are a necessary part of day-to-day software development.

Candidates should have some formal training in a quantitative field and a keen interest in building robust and elegant software. This is a high-impact, high-visibility position where successful candidates will be entrusted with a lot of responsibility for products that have a direct effect on the P&L of the firm and influence on our workflow.

The ideal candidate will have production experience with Haskell or another functional language, relational databases and relational data modeling, Python, and Java. Additionally, as this is a startup environment, the ideal candidate will be comfortable filling many different technology roles, and contributing to the success of the firm wherever they can, not just in agreement with their job description.

Karamaan Group is an investment adviser and manager catering to family offices and institutional investors. We value innovative thinking, encourage an entrepreneurial atmosphere, and enjoy spirited discussions.

Get information on how to apply for this position.

October 22, 2018 03:46 PM

Michael Snoyman

Kick the Tires - Rust Crash Course lesson 1

In this lesson, we just want to get set up with the basics: tooling, ability to compile, basic syntax, etc. Let’s start off with the tooling, you can keep reading while things download.

This post is part of a series based on teaching Rust at FP Complete. If you’re reading this post outside of the blog, you can find links to all posts in the series at the top of the introduction post. You can also subscribe to the RSS feed.

Tooling

Your gateway drug to Rust will be the rustup tool, which will install and manage your Rust toolchains. I put that in the plural, because it can manage both multiple versions of the Rust compiler, as well as cross compilers for alternative targets. For now, we’ll be doing simple stuff.

Both of these pages will tell you to do the same thing:

  • On Unix-like systems, run curl https://sh.rustup.rs -sSf | sh
  • Or run a Windows installer, probably the 64-bit installer

Read the instructions on the rust-lang page about setting up your PATH environment variable. For Unix-like systems, you’ll need ~/.cargo/bin in your PATH.

Along with the rustup executable, you’ll also get:

  • cargo, the build tool for Rust
  • rustc, the Rust compiler

Hello, world!

Alright, this part’s easy: cargo new hello && cd hello && cargo run.

We’re not learning all about Cargo right now, but to give you the basics:

  • Cargo.toml contains the metadata on your project, including dependencies. We won’t be using dependencies quite yet, so the defaults will be fine.
  • Cargo.lock is generated by cargo itself
  • src contains your source files, for now just src/main.rs
  • target contains generated files

We’ll get to the source code itself in a bit, first a few more tooling comments.

Building with rustc

For something this simple, you don’t need cargo to do the building. Instead, you can just use: rustc src/main.rs && ./main. If you feel like experimenting with code this way, go for it. But typically, it’s a better idea to create a scratch project with cargo new and experiment in there. Entirely your decision.

Running tests

We won’t be adding any tests to our code yet, but you can run tests in your code with cargo test.

Extra tools

Two useful utilities are the rustfmt tool (for automatically formatting your code) and clippy (for getting code advice). Note that clippy is still a work in progress, and sometimes gives false positives. To get them set up, run:

$ rustup component add clippy-preview rustfmt-preview

And then you can run them with:

$ cargo fmt
$ cargo clippy

IDE

There is some IDE support for those who want it. I’ve heard great things about IntelliJ IDEA’s Rust add-on. Personally, I haven’t used it much yet, but I’m also not much of an IDE user in the first place. This crash course won’t assume any IDE, just basic text editor support.

Macros

Alright, we can finally look out our source code in src/main.rs:

fn main() {
    println!("Hello, world!");
}

Simple enough. fn says we’re writing a function. The name is main. It takes no arguments, and has no return value. (Or, more accurately, it returns the unit type, which is kind of like void in C/C++, but really closer to the unit type in Haskell.) String literals look pretty normal, and function calls look almost identical to other C-style languages.

Alright, here’s the first “crash course” part of this: why is there an exclamation point after the println? I say “crash course” because when I first learned Rust, I didn’t see an explanation of this, and it bothered me for a while.

println is not a function. It’s a macro. This is because it takes a format string, which needs to be checked at compile time. To prove the point, try changing the string literal to include {}. You’ll get an error message along the lines of:

error: 1 positional argument in format string, but no arguments were given

This can be fixed by providing an argument to fill into the placeholder:

println!("Hello , world! {} {} {}", 5, true, "foobar");

Take a guess at what the output will be, and you’ll probably be right. But that leaves us with a question: how does the println! macro know how to display these different types?

Traits and Display

More crash course time! To get a better idea of how displaying works, let’s trigger a compile time error. To do this, we’re going to define a new data type called Person, create a value of that type, and try to print it:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let alice = Person {
        name: String::from("Alice"),
        age: 30,
    };
    println!("Person: {}", alice);
}

We’ll get into more examples on defining your own structs and enums later, but you can cheat and read the Rust book if you’re curious.

If you try to compile that, you’ll get:

error[E0277]: `Person` doesn't implement `std::fmt::Display`
  --> src/main.rs:11:28
   |
11 |     println!("Person: {}", alice);
   |                            ^^^^^ `Person` cannot be formatted with the default formatter
   |
   = help: the trait `std::fmt::Display` is not implemented for `Person`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
   = note: required by `std::fmt::Display::fmt`

That’s a bit verbose, but the important bit is the trait `std::fmt::Display` is not implemented for `Person`. In Rust, a trait is similar to an interface in Java, or even better like a typeclass in Haskell. (Noticing a pattern of things being similar to Haskell concepts? Yeah, I did too.)

We’ll get to all of the fun of defining our own traits, and learning about implementing them later. But we’re crashing forward right now. So let’s throw in an implementation of the trait right here:

impl Display for Person {
}

That didn’t work:

error[E0405]: cannot find trait `Display` in this scope
 --> src/main.rs:6:6
  |
6 | impl Display for Person {
  |      ^^^^^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
  |
1 | use core::fmt::Display;
  |
1 | use std::fmt::Display;
  |

error: aborting due to previous error

For more information about this error, try `rustc --explain E0405`.
error: Could not compile `foo`.

We haven’t imported Display into the local namespace. The compiler helpfully recommends two different traits that we may want, and tells us that we can use the use statement to import them into the local namespace. We saw in an earlier error message that we wanted std::fmt::Display, so adding use std::fmt::Display; to the top of src/main.rs will fix this error message. But just to prove the point, no use statement is necessary! We can instead us:

impl std::fmt::Display for Person {
}

Awesome, our previous error message has been replaced with something else:

error[E0046]: not all trait items implemented, missing: `fmt`
 --> src/main.rs:6:1
  |
6 | impl std::fmt::Display for Person {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `fmt` in implementation
  |
  = note: `fmt` from trait: `fn(&Self, &mut std::fmt::Formatter<'_>) -> std::result::Result<(), std::fmt::Error>`

We’re quickly approaching the limit of things we’re going to cover in a “kicking the tires” lesson. But hopefully this will help us plant some seeds for next time.

The error message is telling us that we need to include a fmt method in our implementation of the Display trait. It’s also telling us what the type signature of this is going to be. Let’s look at that signature, or at least what the error message says:

fn(&Self, &mut std::fmt::Formatter<'_>) -> std::result::Result<(), std::fmt::Error>

There’s a lot to unpack there. I’m going to apply terminology to each bit, but you shouldn’t expect to fully grok this yet.

  • Self is the type of the thing getting the implementation. In this case, that’s Person.
  • Adding the & at the beginning makes it a reference to the value, not the value itself. C++ developers are used to that concept already. Many other languages talk about pass by reference too. In Rust, this plays in quite a bit with ownership. Ownership is a massively important topic in Rust, and we’re not going to discuss it more now.
  • &mut is a mutable reference. By default, everything in Rust is immutable, and you have to explicitly say that things are mutable. We’ll later get into why mutability of references is important to ownership in Rust.
  • Anyway, the second argument is a mutable reference to a Formatter. What’s the <'_> thing after Formatter? That’s a lifetime parameter. That also has to do with ownership. We’ll get to lifetimes later as well.
  • The -> indicates that we’re providing the return type of the function.
  • Result is an enum, which is a sum type, or a tagged union. It’s generic on two type parameters: the value in case of success and the value in case of error.
  • In the case of success, our function returns a (), or unit value. This is another way of saying “I don’t return any useful value if things go well.” In the case of an error, we return std::fmt::Error.
  • Rust has no runtime exceptions. Instead, when something goes wrong, you return it explicitly. Almost all code uses the Result type to track things going wrong. This is more explicit than exception-based languages. But unlike languages like C, where it’s easy to forget to check the type of a return to see if it succeeded, or tedious to do error handling properly, Rust makes this much less painful. We’ll deal with it later.
    • NOTE Rust does have the concept of panics, which in practice behave similarly to runtime exceptions. However, there are two important differences. Firstly, by convention, code is not supposed to use the panic mechanism for signaling normal error conditions (like file not found), and instead reserve panics for completely unexpected failures (like logic errors). Secondly, panics are unrecoverable, meaning they take down the entire thread of execution.

Awesome, that type signature all on its own gave us enough material for about 5 more lessons! Don’t worry, you’ll be able to write some Rust code without understanding all of those details, as we’ll demonstrate in the rest of this lesson. But if you’re really adventurous, feel free to explore the Rust book for more information.

Semicolons

Let’s get back to our code, and actually implement our fmt method:

struct Person {
    name: String,
    age: u32,
}

impl std::fmt::Display for Person {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        write!(fmt, "{} ({} years old)", self.name, self.age)
    }
}

fn main() {
    let alice = Person {
        name: String::from("Alice"),
        age: 30,
    };
    println!("Person: {}", alice);
}

We’re using the write! macro now, to write content into the Formatter provided to our method. This is beyond the scope of our discussion, but this allows for more efficient construction of values and production of I/O than producing a bunch of intermediate strings. Yay efficiency.

The &self parameter of the method is a special way of saying “this is a method that works on this object.” This is quite similar to how you’d write code in Python, though in Rust you have to deal with pass by value vs pass by reference.

The second parameter is named fmt, and &mut Formatter is its type.

The very observant among you may have noticed that, above, the error message mentioned &Self. In our implementation, however, we made a lower &self. The difference is that &Self refers to the type of the value, and the lower case &self is the value itself. In fact, the &self parameter syntax is basically sugar for self: &Self.

Does anyone notice something missing? You may think I made a typo. Where’s the semicolon at the end of the write! call? Well, first of all, copy that code in and run it to prove to yourself that it’s not a typo, and that code works. Now add the semicolon and try compiling again. You’ll get something like:

error[E0308]: mismatched types
 --> src/main.rs:7:81
  |
7 |       fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
  |  _________________________________________________________________________________^
8 | |         write!(fmt, "{} ({} years old)", self.name, self.age);
  | |                                                              - help: consider removing this semicolon
9 | |     }
  | |_____^ expected enum `std::result::Result`, found ()
  |
  = note: expected type `std::result::Result<(), std::fmt::Error>`
             found type `()`

This is potentially a huge confusion in Rust. Let me point out something else that you may have noticed, especially if you come from a C/C++/Java background: we have a return value from our method, but we never used return!

The answer to that second concern is easy: the last value generated in a function in Rust is taken as its return value. This is similar to Ruby and—yet again—Haskell. return is only needed for early termination.

But we’re still left with our first question: why don’t we need a semicolon here, and why does adding the semicolon break our code? Semicolons in Rust are used for terminating statements. A statement is something like the use statement we saw before, or the let statement we briefly demonstrated here. The value of a statement is always unit, or (). That’s why, when we add the semicolon, the error message says found type `()`. Leaving off the semicolon, the expression itself is the return value, which is what we want.

You’ll see the phrase that Rust is an expression-oriented language, and this kind of thing is what it’s referring to. You can see mention of this in the FAQ. Personally, I find that the usage of semicolon like this can be subtle, and I still instinctively trip up on it occasionally when my C/C++/Java habits kick in. But fortunately the compiler helps identify these pretty quickly.

Numeric types

Last concept before we just start dropping in some code. We’re going to start off by playing with numeric values. There’s a really good reason for this in Rust: they are copy values, values which the compiler automatically clones for us. Keep in mind that a big part of Rust is ownership, and tracking who owns what is non-trivial. However, with the primitive numeric types, making copies of the values is so cheap, the compiler will do it for you automatically. This is some of that automatic magic I mentioned in my intro post.

To demonstrate, let’s check out some code that works fine with numeric types:

fn main() {
    let val: i32 = 42;
    printer(val);
    printer(val);
}

fn printer(val: i32) {
    println!("The value is: {}", val);
}

We’ve used a let statement to create a new variable, val. We’ve explicitly stated that its type is i32, or a 32-bit signed integer. Typically, these kinds of type annotations are not needed in Rust, as it will usually be able to infer types. Try leaving off the type annotation here. Anyway, we then call the function printer on val twice. All good.

Now, let’s use a String instead. A String is a heap-allocated value which can be created from a string literal with String::from. (Much more on the many string types later). It’s expensive to copy a String, so the compiler won’t do it for us automatically. Therefore, this code won’t compile:

fn main() {
    let val: String = String::from("Hello, World!");
    printer(val);
    printer(val);
}

fn printer(val: String) {
    println!("The value is: {}", val);
}

You’ll get this intimidating error message:

error[E0382]: use of moved value: `val`
 --> src/main.rs:4:13
  |
3 |     printer(val);
  |             --- value moved here
4 |     printer(val);
  |             ^^^ value used here after move
  |
  = note: move occurs because `val` has type `std::string::String`, which does not implement the `Copy` trait

error: aborting due to previous error

Exercise 1 there are two easy ways to fix this error message: one using the clone() method of String, and one that changes printer to take a reference to a String. Implement both solutions. (Solutions will be posted separately in a few days.)

Printing numbers

We’re going to tie off this lesson with a demonstration of three different ways of looping to print the numbers 1 to 10. I’ll let readers guess which is the most idiomatic approach.

loop

loop creates an infinite loop.

fn main() {
    let i = 1;

    loop {
        println!("i == {}", i);
        if i >= 10 {
            break;
        } else {
            i += 1;
        }
    }
}

Exercise 2 This code doesn’t quite work. Try to figure out why without asking the compiler. If you can’t find the problem, try to compile it. Then fix the code.

If you’re wondering: you could equivalently use return or return () to exit the loop, since the end of the loop is also the end of the function.

while

This is similar to C-style while loops: it takes a condition to check.

fn main() {
    let i = 1;

    while i <= 10 {
        println!("i == {}", i);
        i += 1;
    }
}

This has the same bug as the previous example.

for loops

For loops let you perform some action for each value in a collection. The collections are generated lazily using iterators, a great concept built right into the language in Rust. Iterators are somewhat similar to generators in Python.

fn main() {
    for i in 1..11 {
        println!("i == {}", i);
    }
}

Exercise 3: Extra semicolons

Can you leave out any semicolons in the examples above? Instead of just slamming code into the compiler, try to think through when you can and cannot drop the semicolons.

Exercise 4: FizzBuzz

Implement fizzbuzz in Rust. The rules are:

  • Print the numbers 1 to 100
  • If the number is a multiple of 3, output fizz instead of the number
  • If the number is a multiple of 5, output buzz instead of the number
  • If the number is a multiple of 3 and 5, output fizzbuzz instead of the number

Next time

Next time, the plan is to get into more details on ownership, though plans are quite malleable in this series. Stay tuned!

Rust at FP Complete | Introduction

October 22, 2018 04:00 AM

October 21, 2018

Neil Mitchell

Announcing Profiterole - GHC Profile Viewer

Summary: profiterole reformats GHC profile reports so they are easier to read.

Do you often work with GHC time profiling reports? Do you find them excessively long and hard to navigate? Profiterole reads standard GHC .prof files and generates both textual and HTML reports which are typically more than 10x smaller. As an example compare HLint profile input to HLint Profiterole output.

Usage

To run, first install (cabal update && cabal install profiterole), generate a GHC profile the normal way, then run:

profiterole myprogram.prof

Profiterole will generate myprogram.profiterole.txt and myprogram.profiterole.html - both contain the same information, but the HTML has hyperlinks. There are three columns of numbers:

  • TOT is the total time spent in any item under this code, what GHC calls inherited time.
  • INH is the total time spent in the items that Profiterole did not move out to the top level.
  • IND is the individual time, just like GHC profiles.

For large programs, using +RTS -P (instead of the common -p) will give more accurate results.

How it works

Profiterole aims to make the profile shorter by combining common subtrees and lifting them to the root - e.g. if you call parseFile from 7 places in the code, instead of having 7 pieces of parseFile profiling, Profiterole will give you one. With only 1 place containing parseFile, it's easier to optimise parseFile, and it's easier to read the code calling it without getting lost in the internals.

How to profile

Given profile data, different ways of looking at it reveal different insights, and the ones discovered by Profiterole have definitely had value. I tend to use:

  • I first use Profiteur to get an overall sense of where the time is going visually. Profiteur lets me orientate myself, but tends to be a little difficult to drill into the details and repeat experiments.
  • I then use Profiterole to see if there were any repeated pieces of code Profiteur missed, and then dig into the details using Profiterole.
  • Only if I'm really going into the details do I go to the GHC .prof output - it's pretty rare.

by Neil Mitchell (noreply@blogger.com) at October 21, 2018 01:03 PM

October 20, 2018

Dan Piponi (sigfpe)

Running from the past


Preface

Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It's a change of perspective that can have a big impact on how we reason about our code. But it's also a change of perspective that can be useful in mathematics and I'd like to give an example: a really beautiful technique that alows you to sample from the infinite limit of a probability distribution without needing an infinite number of operations. (Unless you're infinitely unlucky!)



Markov Chains

A Markov chain is a sequence of random states where each state is drawn from a random distribution that possibly depends on the previous state, but not on any earlier state. So it is a sequence such that for all . A basic example might be a model of the weather in which each day is either sunny or rainy but where it's more likely to be rainy (or sunny) if the previous day was rainy (or sunny). (And to be technically correct: having information about two days or earlier doesn't help us if we know yesterday's weather.)


Like imperative code, this description is stateful. The state at step depends on the state at step . Probability is often easier to reason about when we work with independent identically drawn random variables and our aren't of this type. But we can eliminate the state from our description using the same method used by functional programmers.


Let's choose a Markov chain to play with. I'll pick one with 3 states called , and and with transition probabilities given by where


Here's a diagram illustrating our states:





Implementation

First some imports:



> {-# LANGUAGE LambdaCase #-}
> {-# LANGUAGE TypeApplications #-}



> import Data.Sequence(replicateA)
> import System.Random
> import Control.Monad.State
> import Control.Monad
> import Data.List
> import Data.Array



And now the type of our random variable:



> data ABC = A | B | C deriving (Eq, Show, Ord, Enum, Bounded)



We are now in a position to simulate our Markov chain. First we need some random numbers drawn uniformly from [0, 1]:



> uniform :: (RandomGen gen, MonadState gen m) => m Double
> uniform = state random



And now the code to take a single step in the Markov chain:



> step :: (RandomGen gen, MonadState gen m) => ABC -> m ABC
> step A = do
> a <- uniform
> if a < 0.5
> then return A
> else return B
> step B = do
> a <- uniform
> if a < 1/3.0
> then return A
> else if a < 2/3.0
> then return B
> else return C
> step C = do
> a <- uniform
> if a < 0.5
> then return B
> else return C



Notice how the step function generates a new state at random in a way that depends on the previous state. The m ABC in the type signature makes it clear that we are generating random states at each step.


We can simulate the effect of taking steps with a function like this:



> steps :: (RandomGen gen, MonadState gen m) => Int -> ABC -> m ABC
> steps 0 i = return i
> steps n i = do
> i <- steps (n-1) i
> step i



We can run for 100 steps, starting with , with a line like so:



*Main> evalState (steps 3 A) gen
B



The starting state of our random number generator is given by gen.


Consider the distribution of states after taking steps. For Markov chains of this type, we know that as goes to infinity the distribution of the th state approaches a limiting "stationary" distribution. There are frequently times when we want to sample from this final distribution. For a Markov chain as simple as this example, you can solve exactly to find the limiting distribution. But for real world problems this can be intractable. Instead, a popular solution is to pick a large and hope it's large enough. As gets larger the distribution gets closer to the limiting distribution. And that's the problem I want to solve here - sampling from the limit. It turns out that by thinking about random functions instead of random states we can actually sample from the limiting distribution exactly.



Some random functions


Here is a new version of our random step function:



> step' :: (RandomGen gen, MonadState gen m) => m (ABC -> ABC)
> step' = do
> a <- uniform
> return $ \case
> A -> if a < 0.5 then A else B
> B -> if a < 1/3.0
> then A
> else if a < 2/3.0 then B else C
> C -> if a < 0.5 then B else C



In many ways it's similar to the previous one. But there's one very big difference: the type signature m (ABC -> ABC) tells us that it's returning a random function, not a random state. We can simulate the result of taking 10 steps, say, by drawing 10 random functions, composing them, and applying the result to our initial state:



> steps' :: (RandomGen gen, MonadState gen m) => Int -> m (ABC -> ABC)
> steps' n = do
> fs <- replicateA n step'
> return $ foldr (flip (.)) id fs



Notice the use of flip. We want to compose functions , each time composing on the left by the new . This means that for a fixed seed gen, each time you increase by 1 you get the next step in a single simulation: (BTW I used replicateA instead of replicateM to indicate that these are independent random draws. It may be well known that you can use Applicative instead of Monad to indicate independence but I haven't seen it written down.)



*Main> [f A | n <- [0..10], let f = evalState (steps' n) gen]
[A,A,A,B,C,B,A,B,A,B,C]



When I first implemented this I accidentally forgot the flip. So maybe you're wondering what effect removing the flip has? The effect is about as close to a miracle as I've seen in mathematics. It allows us to sample from the limiting distribution in a finite number of steps!


Here's the code:



> steps_from_past :: (RandomGen gen, MonadState gen m) => Int -> m (ABC -> ABC)
> steps_from_past n = do
> fs <- replicateA n step'
> return $ foldr (.) id fs



We end up building . This is still a composition of independent identically distributed functions and so it's still drawing from exactly the same distribution as steps'. Nonetheless, there is a difference: for a particular choice of seed, steps_from_past n no longer gives us a sequence of states from a Markov chain. Running with argument draws a random composition of functions. But if you increase by 1 you don't add a new step at the end. Instead you effectively restart the Markov chain with a new first step generated by a new random seed.


Try it and see:



*Main> [f A | n <- [0..10], let f = evalState (steps_from_past n) gen]
[A, A, A, A, A, A, A, A, A, A]



Maybe that's surprising. It seems to get stuck in one state. In fact, we can try applying the resulting function to all three states.



*Main> [fmap f [A, B, C] | n <- [0..10], let f = evalState (steps_from_past n) gen]
[[A,B,C],[A,A,B],[A,A,A],[A,A,A],[A,A,A],[A,A,A],[A,A,A],[A,A,A],[A,A,A],[A,A,A],[A,A,A]]



In other words, for large enough we get the constant function.


Think of it this way: If f isn't injective then it's possible that two states get collapsed to the same state. If you keep picking random f's it's inevitable that you will eventually collapse down to the point where all arguments get mapped to the same state. Once this happens, we'll get the same result no matter how large we take . If we can detect this then we've found the limit of as goes to infinity. But because we know composing forwards and composing backwards lead to draws from the same distribution, the limiting backward composition must actually be a draw from the same distribution as the limiting forward composition. That flip can't change what probability distribution we're drawing from - just the dependence on the seed. So the value the constant function takes is actually a draw from the limiting stationary distribution.


We can code this up:



> all_equal :: (Eq a) => [a] -> Bool
> all_equal [] = True
> all_equal [_] = True
> all_equal (a : as) = all (== a) as



> test_constant :: (Bounded a, Enum a, Eq a) => (a -> a) -> Bool
> test_constant f =
> all_equal $ map f $ enumFromTo minBound maxBound



This technique is called coupling from the past. It's "coupling" because we've arranged that different starting points coalesce. And it's "from the past" because we're essentially asking answering the question of what the outcome of a simulation would be if we started infinitely far in the past.



> couple_from_past :: (RandomGen gen, MonadState gen m, Enum a, Bounded a, Eq a) =>
> m (a -> a) -> (a -> a) -> m (a -> a)
> couple_from_past step f = do
> if test_constant f
> then return f
> else do
> f' <- step
> couple_from_past step (f . f')



We can now sample from the limiting distribution a million times, say:



*Main> let samples = map ($ A) $ evalState (replicateA 1000000 (couple_from_past step' id)) gen



We can now count how often A appears:



*Main> fromIntegral (length $ filter (== A) samples)/1000000
0.285748



That's a pretty good approximation to , the exact answer that can be found by finding the eigenvector of the transition matrix corresponding to an eigenvalue of 1.



> gen = mkStdGen 669




Notes

The technique of coupling from the past first appeared in a paper by Propp and Wilson. The paper Iterated Random Functions by Persi Diaconis gave me a lot of insight into it. Note that the code above is absolutely not how you'd implement this for real. I wrote the code that way so that I could switch algorithm with the simple removal of a flip. In fact, with some clever tricks you can make this method work with state spaces so large that you couldn't possibly hope to enumerate all starting states to detect if convergence has occurred. Or even with uncountably large state spaces. But I'll let you read the Propp-Wilson paper to find out how.

by Dan Piponi (noreply@blogger.com) at October 20, 2018 11:22 PM

Brent Yorgey

What’s the Difference? video and slides

At ICFP in St. Louis I presented my paper with Kenny Foner, What’s the Difference? A Functional Pearl on Subtracting Bijections. Many people seemed to enjoy the talk and we got lots of great feedback afterwards. We will probably write up an extended version of the paper for JFP, to include extra stuff we could not fit in the paper and to incorporate things we learned at ICFP.

(Fun fact: this was actually my first ICFP talk—though not my first ICFP paper. I am glad I have a bunch of experience giving talks at this point; I can remember a time in my life when giving a talk on that stage would have been terrifying.)

Here is the video of the talk:

<iframe allowfullscreen="true" class="youtube-player" height="360" src="https://www.youtube.com/embed/hq9gAe-pmzM?version=3&amp;rel=1&amp;fs=1&amp;autohide=2&amp;showsearch=0&amp;showinfo=1&amp;iv_load_policy=1&amp;wmode=transparent" style="border:0;" type="text/html" width="640"></iframe>

You can download my slides here. This version of the slides includes speaking notes—it’s not exactly what I ended up saying, but it should give you a decent idea if you just want to read the slides without watching the video.

by Brent at October 20, 2018 08:38 PM

Mark Jason Dominus

I struggle to understand Traversable

Haskell evolved a lot since the last time I seriously wrote any Haskell code, so much so that all my old programs broke. My Monad instances don't compile any more because I'm no longer allowed to have a monad which isn't also an instance of Applicative. Last time I used Haskell, Applicative wasn't even a thing. I had read the McBride and Paterson paper that introduced applicative functors, but that was years ago, and I didn't remember any of the details. (In fact, while writing this article, I realized that the paper I read was a preprint, and I probably read it before it was published, in 2008.) So to resuscitate my old code I had to implement a bunch of <*> functions and since I didn't really understand what it was supposed to be doing I couldn't do that. It was a very annoying experience.

Anyway I got that more or less under control (maybe I'll publish a writeup of that later) and moved on to Traversable which, I hadn't realized before, was also introduced in that same paper. (In the prepublication version, Traversable was been given the unmemorable name IFunctor.) I had casually looked into this several times in the last few years but I never found anything enlightening. A Traversable is a functor (which must also implement Foldable, but let's pass over that for now, no pun intended) that implements a traverse method with the following signature:

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

The traversable functor itself here is t. The f thing is an appurtenance. Often one looks at the type of some function and says “Oh, that's what that does”, but I did not get any understanding from this signature.

The first thing to try here is to make it less abstract. I was thinking about Traversable this time because I thought I might want it for a certain type of tree structure I was working with. So I defined an even simpler tree structure:

    data Tree a = Con a | Add (Tree a) (Tree a)
        deriving (Eq, Show)

Defining a bunch of other cases wouldn't add anything to my understanding, and it would make it take longer to try stuff, so I really want to use the simplest possible example here. And this is it: one base case, one recursive case.

Then I tried to make this type it into a Traversable instance. First we need it to be a Functor, which is totally straightforward:

    instance Functor Tree where
        fmap f (Con a) = Con (f a)
        fmap f (Add x y) = Add (fmap f x) (fmap f y)

Then we need it to be a Foldable, which means it needs to provide a version of foldr. The old-fashioned foldr was

    foldr :: (a -> b -> b) -> b -> [a] -> b

but these days the list functor in the third place has been generalized:

    foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b

The idea is that foldr fn collapses a list of as into a single b value by feeding in the as one at a time. Each time, foldr takes the previous b and the current a and constructs a new b. The second argument is the initial value of b. Another way to think about it is that every list has the form

    e1 : e2 : .... : []

and foldr fn b applied to this list replaces the (:) calls with fn and the trailing [] with b, giving me

    e1 `f` e2 `f` .... `f` b

The canonical examples for lists are:

    sum = foldr (+) 0

(add up the elements, starting with zero) and

    length = foldr (\_ -> (+ 1)) 0

(ignore the elements, adding 1 to the total each time, starting with zero). Also foldr (:) [] is the identity function for lists because it replaces the (:) calls with (:) and the trailing [] with [].

Anyway for Tree it looks like this:

   instance Foldable Tree where
        foldr f b (Con a) = f a b
        foldr f b (Add x y) = (foldr f) (foldr f b x) y

The Con clause says to take the constant value and combine it with the default total. The Add clause says to first fold up the left-side subtree x to a single value, then use that as the initial value for folding up the right-side subtree y, so everything gets all folded up together. (We could of course do the right subtree before the left; the results would be different but just as good.)

I didn't write this off the top of my head, I got it by following the types, like this:

  1. In the first clause

        foldr f b (Con a) = ???
    

    we have a function f that wants an a value and a b value, and we have both an a and a b, so put the tabs in the slots.

  2. In the second clause

        foldr f b (Add x y) = ???
    

    f needs an a value and none is available, so we can't use f by itself. We can only use it recursively via foldr. So forget f, we will only be dealing only with foldr f, which has type b -> Tree a -> b. We need to apply this to a b value and the only one we have is b, and then we need to apply that to one of the subtrees, say x, and thus we have synthesized the foldr f b x subexpression. Then pretty much the same process gets us the rest of it: we need a b and the only one we have now is foldr f b x, and then we need another tree and the only one we haven't used is y.

It turns out it is easier and more straightforward to write foldMap instead, but I didn't know that at the time. I won't go into it further because I have already digressed enough. The preliminaries are done, we can finally get on to the thing I wanted, the Traversable:

    instance Traversable Tree where
      traverse = ....

and here I was stumped. What is this supposed to actually do? For our Tree functor it has this signature:

    traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b) 

Okay, a function a -> f b I understand, it turns each tree leaf value into a list or something, so at each point of the tree it gets out a list of bs, and it potentially has one of those for each item in the input tree. But how the hell do I turn a tree of lists into a single list of Tree b? (The answer is that the secret sauce is in the Applicative, but I didn't understand that yet.)

I scratched my head and read a bunch of different explanations and none of them helped. All the descriptions I found were in either prose or mathematics and I still couldn't figure out what it was for. Finally I just wrote a bunch of examples and at last the light came on. I'm going to show you the examples and maybe the light will come on for you too.

We need two Traversable functors to use as examples. We don't have a Traversable implementation for Tree yet so we can't use that. When I think of functors, the first two I always think of are List and Maybe, so we'll use those.

    > traverse (\n -> [1..n]) Nothing
    [Nothing]
    > traverse (\n -> [1..n]) (Just 3)
    [Just 1,Just 2,Just 3]

Okay, I think I could have guessed that just from the types. And going the other way is not very interesting because the output, being a Maybe, does not have that much information in it.

    > let f x = if even x then Just (x `div` 2) else Nothing

If the is even then the result is just half of , and otherwise the division by 2 “fails” and the result is nothing. Now:

    > traverse f [ 1, 2, 3, 4 ]
    Nothing
    > traverse f [ 10, 4, 18 ]
    Just [5,2,9]

It took me a few examples to figure out what was going on here: When all the list elements are even, the result is Just a list of half of each. But if any of the elements is odd, that spoils the whole result and we get Nothing. (traverse f [] is Just [] as one would expect.)

That pretty much exhausts what can be done with lists and maybes. Now I have two choices about where to go next: I could try making both functors List, or I could use a different functor entirely. (Making both Maybe seemed like a nonstarter.) Using List twice seemed confusing, and when I tried it I could kinda see what it was doing but I didn't understand why. So I took a third choice: I worked up a Traversable instance for Tree just by following the types even though I didn't understand what it ought to be doing. I thought I'd at least see if I could get the easy clause:

    traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b) 

    instance Traversable Tree where
      traverse fn (Con a) = ...

In the ... I have fn :: a -> f b and I have at hand a single a. I need to construct a Tree b. The only way to get a b is to apply fn to it, but this gets me an f b and I need f (Tree b). How do I get the Tree in there? Well, that's what Con is for, getting Tree in there, it turns a t into Tree t. But how do I do that inside of f? I tinkered around a little bit and eventually found

  traverse fn (Con a) = Con <$> (fn a)

which not only type checks but looks like it could even be correct. So now I have a motto for what <$> is about: if I have some function, but I want to use it inside of some applicative functor f, I can apply it with <$> instead of with $.

Which, now that I have said it myself, I realize it is exactly what everyone else was trying to tell me all along: normal function application takes an a -> b and applies to to an a giving a b. Applicative application takes an f (a -> b) and applies it to an f a giving an f b. That's what applicative functors are all about, doing stuff inside of f.

Okay, I can listen all day to an explanation of what an electric drill does, but until I hold it in my hand and drill some holes I don't really understand.

Encouraged, I tried the hard clause:

  traverse fn (Add x y) = ...

and this time I had a roadmap to follow:

  traverse fn (Add x y) = Add <$> ...

The Con clause had fn a at that point to produce an f b but that won't work here because we don't have an a, we have a whole Tree a, and we don't need an f b, we need an f (Tree b). Oh, no problem, traverse fn supposedly turns a Tree a into an f (Tree b), which is just what we want. And it makes sense to have a recursive call to traverse because this is the recursive part of the recursive data structure:

  traverse fn (Add x y) = Add <$> (traverse fn x) ...

Clearly traverse fn y is going to have to get in there somehow, and since the pattern for all the applicative functor stuff is

  f <$> ... <*> ... <*> ...

let's try that:

  traverse fn (Add x y) = Add <$> (traverse fn x) <*> (traverse fn y)

This looks plausible. It compiles, so it must be doing something. Partial victory! But what is it doing? We can run it and see, which was the whole point of an exercise: work up a Traversable instance for Tree so that I can figure out what Traversable is about.

Here are some example trees:

 t1 = Con 3                              -- 3
 t2 = Add (Con 3) (Con 4)                -- 3 + 4
 t3 = Add (Add (Con 3) (Con 4)) (Con 2)  -- (3 + 4) + 2

(I also tried Add (Con 3) (Add (Con 4) (Con 2)) but it did not contribute any new insights so I will leave it out of this article.)

First we'll try Maybe. We still have that f function from before:

    f x = if even x then Just (x `div` 2) else Nothing

but traverse f t1, traverse f t2, and traverse f t3 only produce Nothing, presumably because of the odd numbers in the trees. One odd number spoils the whole thing, just like in a list.

So try:

    traverse f (Add (Add (Con 10) (Con 4)) (Con 18))

which yields:

          Just (Add (Add (Con 5) (Con 2)) (Con 9))

It keeps the existing structure, and applies f at each value point, just like fmap, except that if f ever returns Nothing the whole computation is spoiled and we get Nothing. This is just like what traverse f was doing on lists.

But where does that spoilage behavior come from exactly? It comes from the overloaded behavior of <*> in the Applicative instance of Maybe:

 (Just f) <*> (Just x) = Just (f x)
 Nothing  <*> _        = Nothing
       _  <*> Nothing  = Nothing

Once we get a Nothing in there at any point, the Nothing takes over and we can't get rid of it again.

I think that's one way to think of traverse: it transforms each value in some container, just like fmap, except that where fmap makes all its transformations independently, and reassembles the exact same structure, with traverse the reassembly is done with the special Applicative semantics. For Maybe that means “oh, and if at any point you get Nothing, just give up”.

Now let's try the next-simplest Applicative, which is List. Say,

    g n = [ 1 .. n ]

Now traverse g (Con 3) is [Con 1,Con 2,Con 3] which is not exactly a surprise but traverse g (Add (Con 3) (Con 4)) is something that required thinking about:

    [Add (Con 1) (Con 1),
     Add (Con 1) (Con 2),
     Add (Con 1) (Con 3),
     Add (Con 1) (Con 4),
     Add (Con 2) (Con 1),
     Add (Con 2) (Con 2),
     Add (Con 2) (Con 3),
     Add (Con 2) (Con 4),
     Add (Con 3) (Con 1),
     Add (Con 3) (Con 2),
     Add (Con 3) (Con 3),
     Add (Con 3) (Con 4)]

This is where the light finally went on for me. Instead of thinking of lists as lists, I should be thinking of them as choices. A list like [ "soup", "salad" ] means that I can choose soup or salad, but not both. A function g :: a -> [b] says, in restaurant a, what bs are on the menu.

The g function says what is on the menu at each node. If a node has the number 4, I am allowed to choose any of [1,2,3,4], but if it has the number 3 then the choice 4 is off the menu and I can choose only from [1,2,3].

Traversing g over a Tree means, at each leaf, I am handed a menu, and I make a choice for what goes at that leaf. Then the result of traverse g is a complete menu of all the possible complete trees I could construct.

Now I finally understand how the t and the f switch places in

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 

I asked “how the hell do I turn a tree of lists into a single list of Tree b”? And that's the answer: each list is a local menu of dishes available at one leaf, and the result list is the global menu of the complete dinners available over the entire tree.

Okay! And indeed traverse g (Add (Add (Con 3) (Con 4)) (Con 2)) has 24 items, starting

      Add (Add (Con 1) (Con 1)) (Con 1)
      Add (Add (Con 1) (Con 1)) (Con 2)
      Add (Add (Con 1) (Con 2)) (Con 1)
      ...

and ending

      Add (Add (Con 3) (Con 4)) (Con 1)
      Add (Add (Con 3) (Con 4)) (Con 2)

That was traversing a list function over a Tree. What if I go the other way? I would need an Applicative instance for Tree and I didn't really understand Applicative yet so that wasn't going to happen for a while. I know I can't really understand Traversable without understanding Applicative first but I wanted to postpone the day of reckoning as long as possible.

What other functors do I know? One easy one is the functor that takes type a and turns it into type (String, a). Haskell even has a built-in Applicative instance for this, so I tried it:

     > traverse (\x -> ("foo", x)) [1..3]
     ("foofoofoo",[1,2,3])                     
     > traverse (\x -> ("foo", x*x)) [1,5,2,3]
     ("foofoofoofoo",[1,25,4,9])

Huh, I don't know what I was expecting but I think that wouldn't have been it. But I figured out what was going on: the built-in Applicative instance for the a -> (String, a) functor just concatenates the strings. In general it is defined on a -> (m, b) whenever m is a monoid, and it does fmap on the right component and uses monoid concatenation on the left component. So I can use integers instead of strings, and it will add the integers instead of concatenating the strings. Except no, it won't, because there are several ways to make integers into a monoid, but each type can only have one kind of Monoid operations, and if one was wired in it might not be the one I want. So instead they define a bunch of types that are all integers in obvious disguises, just labels stuck on them that say “I am not an integer, I am a duck”; “I am not an integer, I am a potato”. Then they define different overloadings for “ducks” and “potatoes”. Then if I want the integers to get added up I can put duck labels on my integers and if I want them to be multiplied I can stick potato labels on instead. It looks like this:

   import Data.Monoid
   h n = (Sum 1, n*10)

Sum is the duck label. When it needs to combine two ducks, it will add the integers:

   > traverse h [5,29,83]
   (Sum {getSum = 3},[50,290,830]) 

But if we wanted it to multiply instead we could use the potato label, which is called Data.Monoid.Product:

    > traverse (\n -> (Data.Monoid.Product 7, 10*n)) [5,29,83]
    (Product {getProduct = 343}, [50,290,830])                                                                                        

There are three leaves, so we multiply three sevens and get 343.

Or we could do the same sort of thing on a Tree:

    > traverse (\n -> (Data.Monoid.Product n, 10*n)) (Add (Con 2) (Add (Con 3) (Con 4)))
    (Product {getProduct = 24}, Add (Con 20) (Add (Con 30) (Con 40)))               

Here instead of multiplying together a bunch of sevens we multiply together the leaf values themselves.

The McBride and Paterson paper spends a couple of pages talking about traversals over monoids, and when I saw the example above it started to make more sense to me. And their ZipList example became clearer too. Remember when we had a function that gave us a menu at every leaf of a tree, and traverse-ing that function over a tree gave us a menu of possible trees?

       > traverse (\n -> [1,n,n*n]) (Add (Con 2) (Con 3))
       [Add (Con 1) (Con 1),
        Add (Con 1) (Con 3),
        Add (Con 1) (Con 9),
        Add (Con 2) (Con 1),
        Add (Con 2) (Con 3),
        Add (Con 2) (Con 9),
        Add (Con 4) (Con 1),
        Add (Con 4) (Con 3),
        Add (Con 4) (Con 9)]

There's another useful way to traverse a list function. Instead of taking each choice at each leaf we make a single choice ahead of time about whether we'll take the first, second, or third menu item, and then we take that item every time:

    > traverse (\n -> Control.Applicative.ZipList [1,n,n*n]) (Add (Con 2) (Con 3))
    ZipList {getZipList = [Add (Con 1) (Con 1),
                           Add (Con 2) (Con 3),
                           Add (Con 4) (Con 9)]}

There's a built-in instance for Either a b also. It's a lot like Maybe. Right is like Just and Left is like Nothing. If all the sub-results are Right y then it rebuilds the structure with all the ys and gives back Right (structure). But if any of the sub-results is Left x then the computation is spoiled and it gives back the first Left x. For example:

 > traverse (\x -> if even x then Left (x `div` 2) else Right (x * 10)) [3,17,23,9]
 Right [30,170,230,90]                
 > traverse (\x -> if even x then Left (x `div` 2) else Right (x * 10)) [3,17,22,9]
 Left 11

Okay, I think I got it.

Now I just have to drill some more holes.

by Mark Dominus (mjd@plover.com) at October 20, 2018 02:44 PM

October 19, 2018

Michael Snoyman

Is it healthy? Depends on context

Some relevant backstory: I’ve been experimenting quite a bit over the past 6 months to see how I respond to different eating patterns. Included in that have been a few months of high carb consumption, focusing mostly on starches as an energy source. However, I’m generally in a low-carb mode, and my family are pretty familiar with that. With that information…

A family member recently asked me why oatmeal is healthy. The question makes sense: if I typically avoid carbohydrates, why would oatmeal—a food I ate quite a bit of during that high carb phase—be a healthy choice?

In that conversation, I introduced the concept of context for diet. This isn’t a novel concept I’ve come up with, but I wanted to explain it here anyway. Let’s start off with the extreme versions of this.

“Is sugar healthy?” I’ve written plenty here already claiming that sugar is not healthy. However, if someone is about to die due to lack of sufficient calories, sugar would be very healthy (it will prevent imminent death).

Which is healthier: a cheeseburger or a cucumber? Most people probably think the cucumber. In the context of modern Western disease, where overconsumption is rampant, the cucumber is probably healthier. However, the cheeseburger includes more micronutrients, and for someone with a deficiency may be considered healthier.

Coming back to the oatmeal. When I was following a high carb diet, I considered oatmeal a healthy choice (others may disagree). I was eating a whole grain, so taking in significant fiber with the starch. To my knowledge, I have no insulin resistance, and therefore can tolerate carbohydrates well. Oatmeal is satiating, making it less likely that I would overeat it. And it provides a decent amount of protein, something which I was looking for in my context (significant resistance training).

Right now, I’m eating a ketogenic diet. If I was to eat a bowl of oatmeal, it would kick me out of ketosis and spike my insulin. All of that fat that I’m eating during this keto phase would likely end up getting stored as body fat, something I’m trying to avoid. It would be a terrible idea.

Similarly, during that high carb phase, if I’d eaten a super-high-fat meal like I do right now, most of that fat would have gone to storage instead of to providing my body’s energy needs.

Keep this in mind when making nutrition choices. Even if someone else who is highly health conscious is eating it, it may not be the right choice for you. Make sure to analyze:

  • Your goals (gain weight, perform in the gym, etc)
  • Any specific aspects of your body (autoimmune, insulin resistance, current weight, etc) relevant to the decision
  • What activities you’re performing (someone with a desk job doesn’t need as many calories as a marathon runner)
  • What the rest of your diet looks like

Also, if you’re vegan, vegetarian, or keep kosher, that cheeseburger I mentioned above is probably always a bad choice.

October 19, 2018 05:51 AM

October 18, 2018

Holden Karau

Michael Snoyman

Introducing the Rust crash course

I’m announcing an upcoming series of blog posts, which I’m calling the Rust crash course. In this blog post, I want to explain:

  • Why I’m interested in Rust
  • Why I’m writing up this series
  • Who this series is for
  • My intended flavor for the series
  • Some examples of Rust gotchas I want to cover

I’m getting to work on this series due to increased Rust usage at FP Complete.

Why Rust?

I’m a strong believer in using the compiler to help eliminate bugs. No programming language can eliminate all bugs and even the best designed language will typically need to leave developers plenty of wiggle room to shoot themselves in the foot. Still, there’s significant value in safety and long term maintainability of projects that use languages with this focus.

For about ten years now, my primary language has been (and continues to be) Haskell. It gets a lot of things right here, such as immutability, explicit effects, and strong typing. But I’ve got two problems with an intense focus on Haskell:

  • There’s always something to be learned from other languages. It’s quite easy to fall into the trap of knowing one language well, and becoming blind to its shortcomings. Haskell is now the language I’ve used for the longest stretch of time as a primary language, finally displacing Java. I need to avoid this trap.
  • There are some legitimate technical advantages of Rust:
    • Performance is better, and more reliable as well, relying less upon things like rewrite rules firing
    • It’s got a better story right now for mobile and frontend development
    • Lack of garbage collection opens up new possibilities in real time development
    • Rust improves on Haskell’s safety guarantees in some places, such as defaulting to requiring complete pattern matches

Like many others, I’ve been hearing a buzz around Rust for years. Two or so years ago, I started playing around with it more, and have been steadily dedicating more personal time to it. But recently, we’ve had more Rust interest at work, and therefore we’ve been expanding our internal Rust team.

Why this series?

We’re a globally distributed team at FP Complete, and we make a heavy push towards using written communication tools wherever possible. This also overlaps heavily with training material. As I do more training (both internally, and for customers), I’m discovering places where:

  • I’m finding my own knowledge of the language was lacking
  • Newcomers are stumbling hard

This series is intended to collect both initial pointers of how to get started with Rust, and hard-learned lessons of how to avoid getting stuck. Some of these stumbling blocks may favor the kind of audience I’m working with directly (lots of Haskell and DevOps engineers), but that will likely change over time.

Target audience

I’m gearing this series towards the Rust curious. I’m assuming programming knowledge, and some basic idea of what Rust is about, but no real knowledge of the language itself. I’ll try to call out when you should go read the Rust book.

If you’re a Java user, a Rubyist, or a Haskeller, and Rust intrigues you, I hope this will help you. And maybe even Rustaceans will enjoy seeing the pain points I find myself and others are hitting.

Flavor of the series

There is already really good material on Rust available from rust-lang.org. I have no intention of trying to replace that. Instead, I’ll assume that people are reading through the Rust book, and point to sections where appropriate.

One concrete example: I don’t intend to spend a lot of time talking about Rust syntax, or explaining that it’s an expression-oriented language. The book covers that.

Instead, I want to give people:

  • Real code to look at and play with
  • Simple problems to build up experience with
  • Explanations of tricky cases that catch people up

And on that note…

Rust gotchas

A few people on Twitter asked me to share some Rust gotchas, especially coming from the perspective of a Haskell developer. I’ll certainly be covering more gotchas going forward, but I wanted to give some examples in this first post so you can get a feel for the kinds of things we’ll be addressing in the series. I’m not going to be explaining details of these problems here; that’s what the series is for!

Just so you know: there’s no content following these examples, besides the Disqus comments below. If you’re not interested in the gotchas, feel free to quit reading now and stay tuned for more posts.

Mutable values, mutable variables

I’ve got a simple mental model in Haskell. Values are all immutable, period. A few special reference types allow me to mutate their contents. And mutating like that is an effect tracked in the type system.

From that perspective, Rust is a bit surprising. Here’s one:

fn main() {
    let i: isize = 1;
    let j: isize = foo(i);
    println!("{}", j);
}

fn foo(mut i: isize) -> isize {
    i += 1;
    i
}

Wait a second… i is immutable. Then I pass it to foo, and it becomes mutable. Then I return this mutable value as an immutable value. What?

I assure you, this ultimately makes sense, but it’s kind of surprising. Also, the fact that x: &mut isize and mut x: &mut isize are both real things that mean different things:

fn main() {
    let mut i: isize = 1;
    let mut j: isize = 2;
    foo(&mut i, &mut j);
    println!("{} {}", i, j);
}

fn foo<'a>(mut i: &'a mut isize, j: &'a mut isize) {
    *i *= 10;
    i = j;
    *i *= 10;
}

So many strings

I was warned about this one and blew it off. I thought to myself there’s no way a Haskeller, trained in the arts of String, strict Text, lazy Text, ByteStrings and more could be daunted. I was wrong.

fn main() {
    let hello1 = String::from("Hello, ");
    let hello2 = String::from(", hello!");
    let name = "Alice";
    println!("{}", hello1 + name);
    println!("{}", name + hello2);
}

Nope, the code above doesn’t compile.

Magically works, until it doesn’t

There are a number of “magic” things that happen in Rust in the name of ergonomics. Often, they work perfectly and save a lot of frustration. And sometimes, they fail. Look at this broken code:

fn main() {
    for arg in std::env::args().skip(1) {
        respond(arg);
    }
}

fn respond(arg: &str) {
    match arg {
        "hi" => println!("Hello there!"),
        "bye" => println!("OK, goodbye!"),
        _ => println!("Sorry, I don't know what {} means", arg),
    }
}

You’ll get an error message:

expected &str, found struct `std::string::String`

Oh, well that makes sense! I need to get a reference to a str instead of the String I got from args(). Easy enough to fix:

respond(&arg);

But then I realize that the respond function is silly and inline the match:

fn main() {
    for arg in std::env::args().skip(1) {
        match &arg {
            "hi" => println!("Hello there!"),
            "bye" => println!("OK, goodbye!"),
            _ => println!("Sorry, I don't know what {} means", arg),
        }
    }
}

I remembered to match on &arg instead of arg, so you’d think it would be fine. But it isn’t:

  |             ^^^^ expected struct `std::string::String`, found str
  |
  = note: expected type `&std::string::String`
             found type `&'static str`

Huh, that’s weird. In order to figure out what’s going on here, you have to understand quite a few details of the deref magic going on behind the scenes. I dare say some of this magic is even a leaky abstraction. (Don’t worry, it’s still zero cost.) You can solve this with either:

match &*arg {

or

match arg.as_ref() {

Moving data into closures

The biggest pain points I’ve encountered so far in my Rust odyssey are all around moving data into closures. I’ve been spoiled by Haskell: I like to use closures constantly, and am used to garbage collection just letting it all magically work.

I’ve got some real head scratchers to demonstrate later, but have fun with this relatively simple example:

fn main() {
    let hello = String::from("Hello, ");
    let greet = |name| hello + name;
    println!("{}", greet("Alice"));
    println!("{}", greet("Bob"));
}

October 18, 2018 03:04 AM

FP Complete

Is Rust functional?

In the past few months, and in particular in the past two weeks, I’ve gotten a number of people asking me the question: Is Rust a functional programming language? This makes sense: I’m a big advocate of functional programming, I work at a company with FP in its name, my primary programming language is Haskell, and yet I use and enjoy Rust. So is Rust consistent with everything else in my FP-centric world, or is it my dirty vice to get away from it all?

by Michael Snoyman (michael@fpcomplete.com) at October 18, 2018 03:02 AM

Holden Karau

End to End ML with Kubeflow: Scaling with Big & Tiny Data (+ deep learning of course) @ signal

Thanks for joining me on 2018-10-17 at signal 2018 San Francisco, CA, USA for End to End ML with Kubeflow: Scaling with Big & Tiny Data (+ deep learning of course).

The slides are at http://bit.ly/2pWFUKj.And if you want there is a related codelab you can try out.

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="356" marginheight="0" marginwidth="0" scrolling="no" src="https://www.slideshare.net/slideshow/embed_code/key/2BqS2cdxyqAvyG" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" width="427"> </iframe> Comment bellow to join in the discussion :).Talk feedback is appreciated at http://bit.ly/holdenTalkFeedback

by Holden Karau (noreply@blogger.com) at October 18, 2018 01:30 AM

October 17, 2018

FP Complete

Development Workflows in Haskell

Our monthly webinar series is really starting to take off and judging by the registration numbers we might be forced into allowing more than 500 people to register for our next webinar which could be about Rust - Don't hold us to that ;)  For Roman's, Development Workflows in Haskell, we had 434 registrants which makes this our most popular webinar so far.  

by Robert Bobbett (robert@fpcomplete.com) at October 17, 2018 08:04 PM

October 16, 2018

Mark Jason Dominus

I redesign the LA Times’ Hurricane Maria chart

This could have been a great chart, but I think it has a big problem:

The chart plots “monthly deaths in Puerto Rico” month by month for the year 2017 (a bold red line) and for comparison, the historical average and range. The 2017 counts are similar to the historical counts for January through August.  In August and September they increase rapidly to a high of 3,000 in October, and then fall back to normal by November 2017.  December 2017 is missing.  A note explains: “Hurricane Maria struck Sept. 20, 2017”.

It appears that the death toll started increasing in early August, even though the hurricane didn't hit until 20 September. According to this chart, the hurricane was shortly followed by a drastic decrease in the death rate.

What's actually going on is that the August value is a total for all of August and is typically low, the September value is a total for all of September and is atypically high, and the chart designer has drawn a straight line between the August and September values, implying a linear increase over the course of August. The data for August is at the mark “A” on the chart, which seems reasonable, except that one has to understand that “A” as marking the end of August instead of the beginning, which is the opposite of the usual convention.

I think a bar chart would have been a better choice here. The lines imply continuous streams of data, but the reality is that each line represents only twelve data points. Maybe something like this instead?

Same data, same colors, but each misleading continuous line has been replaced by twelve discrete bars.

I'm not sure the historical range bars are really adding much.

The same, but with only the historical average and the 2017 data.

If I were designing this from scratch I think I might replace the blue bars with brackets (although maybe the LA Times knows that their readership finds those confusing?). Or maybe plot the difference between the 2017 data and ths historical average. But I think you get the point.

by Mark Dominus (mjd@plover.com) at October 16, 2018 02:30 PM

Neil Mitchell

Announcing Shake 0.17

I'm delighted to announce Shake 0.17. As always, the full changelog is on GitHub, but I'd like to highlight three areas that have seen most attention.

Error Messages

Error messages now support GHC's HasCallStack feature, giving code locations in error messages. As an example, let's define rules for both *.txt and overlap.*, then try and build overlap.txt. With Shake 0.17 we get the far more informative error:

Error when running Shake build system:
at Example.hs:50:46-55:
* Depends on: overlap.txt
* Raised the exception:
Build system error - key matches multiple rules:
Key type: FileQ
Key value: overlap.txt
Rules matched: 2
Rule 1: "overlap.*" %> at Example::21:94-106:
Rule 2: ".txt" %> at Example::24:94-106:
Modify your rules so only one can produce the above key

We can see where the dependency was introduced (line 50), where the rules were defined (lines 21 and 24), and what their patterns were.

The Database module

The new module Development.Shake.Database provides operations for working with open Shake databases - meaning you can now open the database, run some actions against, and shut it. Unlike before, you can now run against an open database repeatedly, and query the resulting database for live or erroneous files. When combined with the new feature that /dev/null for shakeFiles results in no on-disk representation of Shake, you can create an in-memory database, execute it many times, then throw it away. These features aren't targetted at build systems, but allow reuse of Shake in other domains.

If you are using the Database module, and have a way to observe changes interactively, the deprioritize function may be of use, to cause Shake to build some unimportant rules last.

This work was supported by Digital Asset.

Changes to Builtin Rules

Most users shouldn't need to define their own types of rules, but for those who do, the biggest improvement is probably the better documentation in Development.Shake.Rule, complete with a worked example. At the same time, the builtin rules have changed slightly in incompatible ways - the docs explain the new state. These changes are intended to set the stage for Cloud Shake, following the pattern described in Build Systems a la Carte. I hope that a forthcoming release of Shake will provide an actual implementation of Cloud Shake.

by Neil Mitchell (noreply@blogger.com) at October 16, 2018 09:49 AM

Magnus Therning

October 15, 2018

Ken T Takusagawa

[jhomitso] Haskell pack int to bytes

The following Haskell code demonstrates packing a 32-bit unsigned integer (Word32) into a (lazy) ByteString with big-endian byte ordering, using the Put monad of Data.Binary in the binary package.  Essentially, runPut . putWord32be is the Word32 -> ByteString conversion function.

module Main(main) where {
import qualified Data.Binary.Put;
import Data.Word(Word32);
import qualified Data.ByteString.Lazy;

value :: Word32;
value = 65539; -- 3 + 2^16

main :: IO();
main = out_bytestring $ Data.Binary.Put.runPut $ Data.Binary.Put.putWord32be value;

{- expected output:
0 1 0 3
-}

out_bytestring :: Data.ByteString.Lazy.ByteString -> IO();
out_bytestring = putStrLn . unwords . map show . Data.ByteString.Lazy.unpack;
}

This code is analogous to Perl's pack function.  Here is the mapping from Perl's pack template characters to Haskell functions:

L = putWord32host
N = putWord32be (network, big-endian)
V = putWord32le (x86, vax, little-endian)

To convert from lazy to strict ByteString, do Strict.concat . Lazy.toChunks

by Ken (noreply@blogger.com) at October 15, 2018 08:27 PM

Mark Jason Dominus

'The' reader monad does not exist

Reading over my recent article complaining about the environment functor I realized there's yet another terminology problem that makes the discussion unnecessarily confusing. “The” environment functor isn't unique. There is a family of environment functors, one for each possible environment type e. If g is the environment functor at type e, a value of type g t is a function e → t. But e could be anything and if g and h are environment functors at two different types e and e’ they are of course different functors.

This is even obvious from the definition:

    data Environ e t = Env (e -> t)
    instance Functor (Environ e) where
      fmap f (Env x) = Env $ \e -> f (x e)

The functor isn't Environ, it's Environ e, and the functor instance declaration, as it says on line 2. (It seems to me that the notation is missing a universal quantifier somewhere, but I'm not going to open that issue.)

We should speak of Environ e as an environment functor, not the environment functor. So for example instead of:

When operating in the environment functor, fmap has the type (a -> b) -> g a -> g b

I should have said:

When operating in an environment functor, fmap has the type (a -> b) -> g a -> g b

And instead of:

A function p -> q is a q parcel in the environment functor

I should have said:

A function p -> q is a q parcel in an environment functor

or

A function p -> q is a q parcel in the environment functor at p

although I'm not sure I like the way the prepositions are proliferating there.

The same issue affects ⸢the⸣ reader monad, ⸢the⸣ state monad, and many others.

I'm beginning to find remarkable how much basic terminology Haskell is missing or gets wrong. Mathematicians have a very keen appreciation of the importance of specific and precise terminology, and you'd think this would have filtered into the Haskell world. People are forever complaining that Haskell uses unfamiliar terms like “functor”, and the community's response is (properly, I think) that these terms are pre-existing and there is no point to inventing a new term that will be just as unfamiliar, or, worse, lure people into thinking that the know what it means when they don't. You don't want to call a functor a “container”, says the argument, because many functors (environment functors for example) are nothing at all like containers. I think this is wise.

But having planted their flag on that hill, the Haskell folks don't then use their own terminology correctly. I complained years ago that the term “monad” was used interchangeably for four subtly different concepts, and here we actually have a fifth. I pointed out that in the case of Environment e t, common usage refers to both Environment e and Environment e t as monads, and only the first is correct. But when people say “the environment monad” they mean that Environment itself is a monad, which it is not.

by Mark Dominus (mjd@plover.com) at October 15, 2018 02:15 PM

Chris Smith 2

Fixpoints in Haskell

I gave a brief informal talk about fixpoints and their uses in functional programming at the Norcross Haskathon yesterday. I ended up promising to write it up as a blog post, as well. This is that post.

Just to set expectations from the beginning:

  • This is not research; it’s just exposition of things that are already widely known in programming language theory. If you eat denotational semantics for breakfast, nothing here will be new.
  • This is also not an applied post. You won’t learn (at least directly) how to build better software in Haskell. You might, though, learn a new way of thinking about what your existing Haskell code means.

If you’re still with me, let’s go!

What is a fixpoint?

If you have a function from any set to itself, then a fixpoint of that function is any input that maps to itself. On a standard, graph you can think of these as being values that fall on the line xy.

<figure><figcaption>Fixpoints of a simple function (from Wikimedia Commons)</figcaption></figure>

Here are a few examples:

  • Consider the function f(x) = x². It has two fixpoints: 0 and 1. These are the two real numbers that don’t change when you square them. (Negative numbers become positive, so they can’t work. Numbers between 0 and 1 become smaller. Numbers larger than 1 get larger.)
  • Now consider the cosine function, with its argument in radians. You may have unknowingly calculated the fixpoint of this function when you were bored in high school math class. If you start with any number, and repeatedly press the cosine button on your calculator, you’ll notice that the answer converges to a number around 0.739. This is the only fixpoint of the cosine function.
  • Finally, consider g(x) = x + 1. This function has no fixpoints, since if g(x) = x, then subtracting x from both sides, you could conclude that 0 = 1.

In general, deciding whether a function has fixpoints or not can be difficult. So there are many different fixpoint theorems. For example, Brouwer’s fixpoint theorem says that any continuous function from a closed ball into itself in Euclidean space must have a fixpoint. Another, which will be important in a bit, is the Knaster-Tarski theorem, which says that any order-preserving function on a complete lattice has a complete lattice of fixpoints. But more on that in a bit.

Why care about fixpoints?

That’s what a fixpoint is, but why should we care about it? Are fixpoints more interesting than a children’s amusement with the cosine button of a calculator? In fact, they are.

A really beautiful sequence of the MIT text Structure and Interpretation of Computer Programs deals with progressively more abstract representations of algorithms for computing a square root. Heron of Alexandria proposed an algorithm as follows. To compute the square root of n: (a) start with a guess, a; (b) compare a with n / a; (c) if they are close enough to each other, then stop; otherwise, average the two and repeat with that as your guess.

For example, if we start by guessing that the square root of 10 is 5, then we go through these steps:

  1. a = 5, but n / a = 2. Those are not close, so our new guess is 7/2.
  2. a = 7/2 (3.5), but n / a = 20/7 (about 2.86). Those are not close, so our new guess is 89/14.
  3. a = 89/28 (about 3.18), but n / a = 280/89 (about 3.15). Those are not quite close enough, so our new guess is 15761/4984.
  4. a = 15761/4984 (about 3.16), and n / a = 49840/15761 (also about 3.16). Those pretty close, so we can stop.

See what’s happening? Just like with the cosine button, we’re repeating a computation to make a guess better until it converges. The point where it converges is a fixpoint. But this time, the computation was chosen so that its fixpoint is the square root of n, giving a technique for calculating square roots.

To express this, we can write a Haskell implementation built around the notion of searching for a fixpoint.

<iframe frameborder="0" height="0" scrolling="no" src="https://medium.com/feed/@cdsmithus/" width="0">https://medium.com/media/561dd185b05b03f9d6cd549f491e90ae/href</iframe>

You can play with this code using CodeWorld, and compute your own square roots.

This is sort of a funky way to compute a fixpoint, though.

  • First, it requires a starting value, which is a wart in the API. A function’s fixpoints don’t really depend on any particular starting value.
  • Second, it relies on the function to converge — to produce a value closer to a fixpoint in its result than its input. This is the reason the average is there at all, instead of just using n/2, which has the right fixpoint but doesn’t converge to that fixpoint.
  • Third, the function may not even have a fixpoint at all! Here, a fixpoint exists for Double because it has finite precision. But the function f(x) = (x + 10/x) / 2 has no fixpoint in the rational numbers, so there’s no chance this would also work with Rational.

These problems are hard to overcome in the current form, but it turns out that by creatively modifying some definitions, we can distill the essence of this into a more abstract combinator, which is Haskell’s fix.

Haskell’s fix combinator

In the Data.Function module of Haskell’s base library, there’s a surprising function.

fix :: (a -> a) -> a

This function computes a fixpoint of any Haskell function. It does it without any of the disadvantages of the version above, and even without any constraints on the types! But how can this be? First of all, even demonstrating the existence of fixpoints is so difficult that it requires heavy mathematical theorems. And even worse, some functions (like g(x) = x + 1, above) have no fixpoints at all!

The trick is that Haskell functions aren’t just ordinary functions on ordinary sets. Haskell functions can throw exceptions, and they can loop indefinitely. To reconcile this with the world of mathematical functions, we say that Haskell functions work not just with the set of ordinary values of its types, but the set of all partially defined values.

Here’s how that works. In math, the set of integers is {0, 1, -1, 2, -2, …}. That’s it! There is nothing else in that set. But in Haskell, we say that the type Integer includes one more value: ⊥. This special value is used to indicate that the function doesn’t produce a true number at all, instead either running forever in an infinite loop, or throwing an exception. In essence, ⊥ means “I don’t know.”

Once ⊥ is taken into account, g(x) = x + 1 does actually have a fixpoint, because g(⊥) = ⊥. That is, if you don’t know what number is passed in, you also don’t know what number comes back out. And this is, in fact, the fixpoint you get from fix. The expression fix g loops forever instead of producing a value, so we say its value is ⊥.

In fact, any time that f(⊥) = ⊥, fix f will produce ⊥. (This is unfortunate if we’re looking for actual numbers as fixpoints like we are above. But later, we’ll be able to recover our original notion of fixpoint in terms of this new one!) This might make you wonder why fix is useful at all! After all, if you don’t know the input to a function, can you ever know the output? Are there any functions for which ⊥ is not a fixpoint? Well, yes there are, and it’s all because of laziness. Consider a constant function, like h(x) = 42. Because it’s a non-strict language, Haskell will produce an output of 42 without even looking at the input. In other words, h(⊥) = 42. ⊥ is not a fixpoint. And, in fact, fix h is 42 for this function.

The definedness ordering

With functions on simple types like Double, these are the only two possibilities: if the function is constant, then fix will produce the constant value, and otherwise it will produce ⊥. (The word for these simple types is “flat”; either you know nothing about the value, or you know everything.) But the result is more interesting when the types have more structure. Given a linked list, for example, there are many possible values where different parts of the value are unknown:

  • ⊥ means that nothing about the list is known.
  • ⊥ : ⊥ means that the list is known to be non-empty, but neither the first element nor the rest of the list are known. This is more information than you have about ⊥ (which might be an empty list).
  • 3 : ⊥ means that the list starts with a 3, but you don’t know what (if anything) comes after that. This is strictly more information than ⊥ : ⊥.
  • ⊥ : [] (also known as [⊥]) means that the list is known to only contain one element, but it’s not known what that element is. This is again strictly more information than ⊥ : ⊥, but it’s incomparable to 3 : ⊥. They are both more info than just whether the list is empty, but neither is strictly more informative than the other. They provide different information.
  • 3 : [] (also known as [3]) is strictly more information than either of ⊥ : [] or 3 : ⊥.

This defines a partial order on Haskell values. It’s different from the order given by Ord, which is the usual meaningful order for that type. This order sorts the values by how much we know about them. So in this order, neither of 3 or 4 is less than the other (they are both completely defined, just different); but ⊥ is less than ⊥ : ⊥, which is in turn less than either 3 : ⊥ or ⊥ : [], and each of these is in turn less than 3 : [].

In fact, any Haskell type has a complete semilattice of values in this definedness order, which just means that given any nonempty collection of values, there is always some unique greatest lower bound, which is the most-defined possible value that’s still less defined — but compatible — with all of them. For example, for lists of numbers, the greatest lower bound of the set {[3, 2], [3, 1, 5], [3, 4, 5, ⊥]} is 3 : ⊥ : ⊥, since all three lists are compatible with this type, but making it any more defined would have to exclude some of them.

An important attribute of Haskell functions is that they preserve this definedness order. In other words, if x is less than or equal to y in this order — meaning that x is compatible with y but possibly less defined — , then f(x) is also less then or equal to f(y). If you think about it, this makes sense. If knowing a little bit about the input gives you some knowledge about the output, then learning more about the input might tell you more about the output, but it should never contradict or take away from what you already knew.

Now here’s where everything starts to come together. The fix combinator always produces the least fixpoint in this definedness ordering. This least fixpoint will be guaranteed to exist by the Knaster-Tarski theorem mentioned earlier, which says that any order-preserving function on a complete semilattice must also have a complete semilattice of fixpoints — and in particular, there must be a least one of them. Definedness is a complete semilattice, and all Haskell functions are order-preserving, and that’s good enough to guarantee that the least fixpoint exists.

Let’s look at another example. Define threeAnd list = 3 : list. A fixpoint here is a list that is not changed at all by prepending a 3 onto it. It can’t be ⊥, because 3 : ⊥ is definitely not the same as ⊥. The answer is an infinite list of 3s, so fix threeAnd gives you exactly that: an infinite list of 3s. We can check this with GHCi.

ghci> import Data.Function
ghci> fix (3 :)
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ^C
Interrupted

Fixpoints and recursion

The reason that fixpoints play such a dominant role in functional programming is that they are intricately related to recursion, and that relationship is an important bridge between the operational realm — understanding what the program does— and the denotational realm — understanding what the program means.

In the operational sense, Haskell’s fixpoints can be defined using recursion, like this:

fix f = x  where x = f x

This definition seems almost too cute to work, but it does! It just starts with an x, and then keeps replacing every x with f(x). After an infinite number of substitutions, we find that the least fixpoint of f is just f(f(f(f(f(f(f(f(…)))))))). In other words, any time we need to refer to the input of the function, we just substitute another function application instead.

In the opposite direction, though, general recursion can be defined in terms of the fixpoint combinator. Suppose you have a programming language with no direct recursion allowed, but you are given a fixpoint combinator. Then there’s a simple syntactic sugar for recovering general recursion. Just take your recursive definition, like x = ... x ..., and rewrite it with an extra parameter that takes the place of recursive uses: x1 x0 = ... x0 .... Notice that x1 is not defined recursively. But setting x = fix x1 satisfies the equation given for x.

In the untyped lambda calculus, fix is known as the Y combinator, and it’s a crucial step to showing that the untyped lambda calculus is computationally universal. That’s because lambda calculus doesn’t have general recursion as an a priori language feature. But Y combinators can be built within the untyped lambda calculus itself, so that general recursion can be simulated with fixpoints as described above.

Once you add types, things change a little bit. It’s impossible to define a Y combinator directly in most sound typed lambda calculi, because it would allow for nontermination, which typed lambda calculi usually try to avoid. When these calculi are used as the basis for general programming languages, the first step is usually introduce some kind of general recursion (such as a recursive let) to allow for nonterminating programs to be written.

There’s still an important place for a fixpoint combinator, though! If we care only about what our programs do, then adding recursion might be sufficient. But recursion literally means defining things in terms of themselves, and that’s not safest thing to do if you would like words to keep having meanings that make sense. So what does a recursive definition even mean?

Fortunately, the Knaster-Tarski theorem guarantees that any function has a unique least fixpoint in the definedness order! So, at least for the pure fragment of Haskell, it’s okay to just define the meaning of a recursive definition to be the least fixed point of the related non-recursive function obtained by pull recursive uses into a parameter exactly as we did above. This ensures that any recursive definition can be given a solid meaning, even though on face value it’s just a circular definition.

(Incidentally, fixpoints are a nice way out of all kinds of self-referential paradoxes like this — what Hofstadter called “strange loops”. So next time you’re debating your science fiction geek friends about time travel and the integrity of the space-time continuum, remember that there’s no paradox in time travel as long as the universe is a fixpoint of the function obtained by pulling the back references out as parameters.)

Looping back, then, we could now redefine the fixpoint function from the introduction — using iterative refinement to close in on the right value of the square root — using the least fixpoint of a Haskell function.

A fun puzzle

Putting together all that we’ve talked about, here’s a question. Suppose you get frustrated with fixing your Haskell code, and type the following into GHCi:

ghci> import Data.Function
ghci> fix error

What happens next? Give it some thought before reading on.

To solve the puzzle, let’s first explore the types. The error function in Haskell has the type String -> a. It cannot reasonably have a fixpoint unless the domain and codomain are the same, so the type specializes to String -> String. Then fix error has the type String.

What is this magical string that fixes all errors? Well, it must be a fixpoint of the error function, but the result of theerror function is always ⊥. That is its whole purpose in life! So fix error must be ⊥, too. Not so special after all?

Ah, but on the operational side, there are many kinds of ⊥. Some are just infinite loops, while others throw exceptions. If they throw exceptions, then there’s an exception value to think about. These are all invisible to the pure fragment of Haskell, but immensely important to what the program does! To understand what’s going on here, recall that fix error = error (error (error ...))), an infinite nesting of error functions. The result is quite interesting.

ghci> fix error
"*** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception:^C
Interrupted

Let’s just say it did not fix any errors. Instead, it threw an exception, with an associated exception message that itself throws an exception when printed, and that exception has another exploding error message, and so on as long as you allow it to continue!

by Chris Smith at October 15, 2018 04:23 AM

October 14, 2018

Holden Karau

The magic of distributed systems: when it all breaks and why @ Reversim Summit 2018

Thanks for joining me on 2018-10-09 for The magic of distributed systems: when it all breaks and why.

The slides are at http://bit.ly/2A8HfDI.

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="356" marginheight="0" marginwidth="0" scrolling="no" src="https://www.slideshare.net/slideshow/embed_code/key/b58RlpWd9bNtPQ" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" width="427"> </iframe> Comment bellow to join in the discussion :).Talk feedback is appreciated at http://bit.ly/holdenTalkFeedback

by Holden Karau (noreply@blogger.com) at October 14, 2018 12:29 AM

Magnus Therning

Picking up new rows in a DB

I’ve been playing around a little with postgresql-simple in combination with streaming for picking up inserted rows in a DB table. What I came up with was

It seems almost too simple so I’m suspecting I missed something.

  • Am I missing something?
  • Should I be using streaming, or is pipes or conduit better (in case they are, in what way)?

October 14, 2018 12:00 AM

October 13, 2018

Holden Karau

October 12, 2018

Gabriel Gonzalez

Detailed walkthrough for a beginner Haskell program

<html lang="" xml:lang="" xmlns="http://www.w3.org/1999/xhtml"><head> <meta charset="utf-8"/> <meta content="pandoc" name="generator"/> <meta content="width=device-width, initial-scale=1.0, user-scalable=yes" name="viewport"/> post <style type="text/css"> code{white-space: pre-wrap;} span.smallcaps{font-variant: small-caps;} span.underline{text-decoration: underline;} div.column{display: inline-block; vertical-align: top; width: 50%;} </style> <style type="text/css">a.sourceLine { display: inline-block; line-height: 1.25; } a.sourceLine { pointer-events: none; color: inherit; text-decoration: inherit; } a.sourceLine:empty { height: 1.2em; } .sourceCode { overflow: visible; } code.sourceCode { white-space: pre; position: relative; } div.sourceCode { margin: 1em 0; } pre.sourceCode { margin: 0; } @media screen { div.sourceCode { overflow: auto; } } @media print { code.sourceCode { white-space: pre-wrap; } a.sourceLine { text-indent: -1em; padding-left: 1em; } } pre.numberSource a.sourceLine { position: relative; left: -4em; } pre.numberSource a.sourceLine::before { content: attr(data-line-number); position: relative; left: -1em; text-align: right; vertical-align: baseline; border: none; pointer-events: all; display: inline-block; -webkit-touch-callout: none; -webkit-user-select: none; -khtml-user-select: none; -moz-user-select: none; -ms-user-select: none; user-select: none; padding: 0 4px; width: 4em; color: #aaaaaa; } pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; } div.sourceCode { } @media screen { a.sourceLine::before { text-decoration: underline; } } code span.al { color: #ff0000; font-weight: bold; } /* Alert */ code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */ code span.at { color: #7d9029; } /* Attribute */ code span.bn { color: #40a070; } /* BaseN */ code span.bu { } /* BuiltIn */ code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */ code span.ch { color: #4070a0; } /* Char */ code span.cn { color: #880000; } /* Constant */ code span.co { color: #60a0b0; font-style: italic; } /* Comment */ code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */ code span.do { color: #ba2121; font-style: italic; } /* Documentation */ code span.dt { color: #902000; } /* DataType */ code span.dv { color: #40a070; } /* DecVal */ code span.er { color: #ff0000; font-weight: bold; } /* Error */ code span.ex { } /* Extension */ code span.fl { color: #40a070; } /* Float */ code span.fu { color: #06287e; } /* Function */ code span.im { } /* Import */ code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */ code span.kw { color: #007020; font-weight: bold; } /* Keyword */ code span.op { color: #666666; } /* Operator */ code span.ot { color: #007020; } /* Other */ code span.pp { color: #bc7a00; } /* Preprocessor */ code span.sc { color: #4070a0; } /* SpecialChar */ code span.ss { color: #bb6688; } /* SpecialString */ code span.st { color: #4070a0; } /* String */ code span.va { color: #19177c; } /* Variable */ code span.vs { color: #4070a0; } /* VerbatimString */ code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */ </style> </head><body>

This post walks through the development of a small Haskell program for aligning equals symbols in a block of text. This walkthrough targets a beginning programmer by describing several steps and concepts in extra detail.

Note that this post describes how to author, compile, and run single-file Haskell programs for ease of experimentation and learning. For larger Haskell projects you will want to use cabal or stack to scaffold and run the project and to share your work with others. I mainly introduce things this way because this provides a lightweight way to get started and try the language.

Background

I obsess about visual cleanliness of the code I write because I optimize for ease of reading rather than ease of writing. One way I try to improve appearance is aligning equals signs. For example, the code might begin like this:

address = "192.168.0.44"
port = 22
hostname = "wind"

… and then I manually indent the equals signs to all align with each other:

address  = "192.168.0.44"
port = 22
hostname = "wind"

My editor is vim, and you can install support for that using the Tabular plugin. However, I thought this would be an instructive example to implement from scratch to illustrate how to program in a functional style.

One neat feature of vim is that you can transform text inside your editor using any command line program. For example, I can select text using visual mode and then type:

:!some-command

… and vim will feed the selected text as standard input to the command-line program named some-command and replace the selected text with whatever the command emits to standard output.

This means that I only need to write a program that takes text to align on standard input and then emits the aligned text on standard output. I’ll call this program: align-equals.

Development environment

The command line is my “IDE”,so I will usually keep up to three terminal windows open:

  • One window edits text using vim
  • One window displays type errors using ghcid
  • One window tests the Haskell code I write in a REPL

I also use Nix, specifically a nix-shell to provision my development tools. I prefer Nix to provision development tools is because I don’t want to accumulate globally installed cruft on my system. Using Nix, I can provision any development tool or library transiently using nix-shell.

I will run all of the following examples inside of the following Nix shell (created for each new terminal):

That creates a transient shell that provides ghc, ghci, ghcid, and hoogle with the text and safe Haskell packages available. If I need to change the set of available Haskell packages I edit the command line and recreate the shell.

I turn on live type-checking by running:

… which will then automatically reload align-equals.hs every time the file changes and display any errors or warnings that the Haskell compiler has found.

In another terminal, I open the code I’m editing inside the ghci REPL so that I can interactively test the functions that I am writing:

Then in the third terminal, I actually edit the file:

The program

First, let’s describe what we plan to do using English prose, before we translate that to code:

We want to find the longest prefix preceding an = sign and then add spaces to the end of all other prefixes to match the length of the longest prefix.

Prefix length

In order to do that, we first need a function that computes the number of characters preceding an = sign for a given line. This function should have the following type:

You can read that type signature as saying: “prefixLength is a function whose input is a value of type Text (i.e. a line of input) and whose output is an Int (the number of characters preceding the first = sign)”. We can even add comments to that effect:

I import Data.Text because I prefer not to use the default String type provided by Haskell’s Prelude, which is inefficient. The text package provides a high-performance alternative type named Text along with many useful utilities.

The implementation of the prefixLength function directly follows the description:

As the name suggests, the prefixLength is the length of the prefix. The only non-trivial part is just knowing how to discover the Data.Text.breakOn function created for this purpose.

I usually browse the online documentation for Haskell packages by doing a Google search for “hackage ${package name}” (i.e. “hackage text”). That’s how I found the breakOn function here:

However, some people also prefer to use hoogle, which indexes and searches Haskell functions by name and by type. For example, if I’m looking for a function that splits a Text value into a prefix and suffix, I can run:

I can also verify that my function works as expected by testing my function in the long-running REPL I have open:

I have to enable theOverloadedStrings extension because I’m not using the default String type from the Haskell Prelude. This extension allows other packages to override how string literals behave to work with alternative implementations like Text.

One thing that’s neat about Haskell is how order-insensitive the language is. You can define things out of order and the compiler doesn’t mind. That’s why we can write our code as if it says: “prefixLength is the length of the prefix … and by the way you can compute the prefix and suffix by splitting the string using breakOn”.

This out-of-order coding style also jives well with lazy evaluation. Haskell is a “lazy” language, meaning that the program can evaluate things out-of-order, too, or even not at all if they are never used. For example, our prefixLength function never actually uses the suffix, so the program will never actually bother to compute or allocate that value.

The more you program in Haskell the less you think about your program as a sequence of statements and the more you think about your program as a graph of dependent computations.

Indenting a line

Now we need a function that pads a prefix with spaces up to a desired number of characters:

… or with comments:

This function is slightly longer, but still pretty straightforward:

Note that we can reorder all the lines after the where with no change to the program’s behavior. However, to keep things readable we order them so that the reader can understand them from top to bottom:

  • Split the line into a prefix and suffix
  • Compute the actual length of the prefix
  • Compute the number of spaces to pad by subtracting the actual length from the desired length
  • Create the padding by repeating a space the specified number of times
  • Create a new line by inserting the padding in between the prefix and suffix

Note that this reads a lot like a function defined in an imperative language. For example, the analogous Python code is not much different:

In general, you can port functional programs to imperative programs in this way if the functional program sticks to simple types (i.e. strings, numbers, records, etc.). For these simple programs, the functional program is essentially an imperative program where you forbid reassigning a value (i.e. “mutation”), which is generally good practice anyway for ease of program comprehension.

We can confirm that our function works by saving the complete program so far:

… and then :reloading that program in our REPL:

Indenting multiple lines

Now we can define a function to indent multiple lines:

This function takes advantage of two convenient utilities called lines and unlines.

Data.Text.lines splits a block of Text into a list of lines:

… and Data.Text.unlines combines a list of lines back into a block of Text:

You can use these two utilities to simplify line-oriented Text transformations in Haskell:

  • Split the block of Text into a list of lines
  • Process the list of lines into a new list of lines
  • Join the new list of lines back into a block of Text

The interesting part of our adjustText function is how we process the list of lines:

You can read the above code as saying:

  • Apply (“map”) the prefixLength function over each element of our list of lines to get a list of prefix lengths
  • Find the maximum length
  • If there is no maximum length, return an empty list of lines
  • If there is a maximum length, pad each line using that length

You might wonder: “Why would there not be a maximum length?” Well, consider the case where we begin with 0 lines of input: what is the maximum value of an empty list? The maximumMay function doesn’t throw an exception or return a bogus sentinel value that might be confused for real data. Instead, the maximumMay function returns an optional result:

The a in the type of maximumMay can be any type that is comparable ( i.e. implements Ord), and in the context of our code that type is Int, so we can pretend that the maximumMay function actually has this more specific type:

In other words, given a list of Ints, the maximumMay function will Maybe return an Int (i.e. it might return an Int or it might not). This means that the result will either be a Nothing (i.e. no result) or an Int value wrapped inside of a Just.

We consume the result of maximumMay by “pattern matching” on the result, like this:

The first branch covers the case where the list is empty. Here, the desiredPrefixLength is not in scope, so if we try to use that value we will get a type error. This provides a nice safeguard so that we can’t attempt to access a result that does not exist. In other languages this might be caught at runtime as a java.lang.NullPointerException or AttributeError: 'NoneType' object has no attribute 'x', but with pattern matching the type-checker can detect these sorts of bugs before we even attempt to run the program.

The second branch covers the case where the list is non-empty and does have a sensible maximum length. There we use that length to adjust each line.

The nice thing about pattern matching is that you can’t forget to handle these cases. If you try to use the result of maximumMay directly as an Int then you will get a type error. The maximumMay function wraps its own result in a Maybe to force downstream users to carefully consider how to handle the case where the list may be empty.

Tying it all together

So far all of our functions are “pure” functions, meaning that they are deterministic conversions from their inputs to their outputs that don’t mutate any variables and don’t have any side effects that we care about.

Carefully note the key phrase: “side effects that we care about”. These functions do technically have side effects, including:

  • Allocating memory/registers
  • Taking a non-zero amount of time to compute

Sometimes we do care about these types of side effects in certain contexts, like cryptography (where secure information can leak through these side channels) or embedded programming (where programs require careful attention to time/memory). However, for our simple utility these functions are effectively “pure”.

We can’t use our utility functions from the command line, though, unless we wrap them in a main function which a program can run, like this:

The interact function converts any pure Text transformation into a runnable program that transforms standard input into standard output using the supplied transformation:

This is an example of a “higher-order” function: a function whose input is another function. The input to the interact function is another function of type Text -> Text. Conveniently, our adjustText function has exactly the correct type to be supplied as an argument to the interact function:

… and then any value of type IO () can be assigned to main, which is what our program will run when invoked as a command-line executable.

If we save the following complete example to align-equals.hs:

… then we can compile that using:

… and verify that the executable works using:

That means that I can now use ./align-equals to transform my text buffer by selecting a text block like this:

address = "192.168.0.44"
port = 22
hostname = "wind"

… and running :!./align-equals to align the block:

address  = "192.168.0.44"
port = 22
hostname = "wind"

… and now I don’t have to tediously align the code manually.

Conclusion

Hopefully this illustrates one way to learn the Haskell language in the course of building small but practical programs. The language introduces many cool features and concepts and this post only touches the tip of the iceberg.

</body></html>

by Gabriel Gonzalez (noreply@blogger.com) at October 12, 2018 02:24 PM

October 10, 2018

Sandy Maguire

Protobuffers Are Wrong

I've spent a good deal of my professional life arguing against using protobuffers. They're clearly written by amateurs, unbelievably ad-hoc, mired in gotchas, tricky to compile, and solve a problem that nobody but Google really has. If these problems of protobuffers remained quarantined in serialization abstractions, my complaints would end there. But unfortunately, the bad design of protobuffers is so persuasive that these problems manage to leak their way into your code as well.

Ad-Hoc and Built By Amateurs

Stop. Put away your email client that is half-way through writing me about how "Google is filled with the world's best engineers," and that "anything they build is, by definition, not built by amateurs." I don't want to hear it.

Let's just get this out of the way. Full disclosure: I used to work at Google. It was the first (but unfortunately, not the last) place I ever used protobuffers. All of the problems I want to talk about today exist inside of Google's codebase; it's not just a matter of "using protobuffers wrong" or some such nonsense like that.

By far, the biggest problem with protobuffers is their terrible type-system. Fans of Java should feel right at home with protobuffers, but unfortunately, literally nobody considers Java to have a well-designed type-system. The dynamic typing guys complain about it being too stifling, while the static typing guys like me complain about it being too stifling without giving you any of the things you actually want in a type-system. Lose lose.

The ad-hoc-ness and the built-by-amateurs-itude go hand-in-hand. So much of the protobuffer spec feels bolted on as an afterthought that it clearly was bolted on as an afterthought. Many of its restrictions will make you stop, scratch your head and ask "wat?" But these are just symptoms of the deeper answer, which is this:

Protobuffers were obviously built by amateurs because they offer bad solutions to widely-known and already-solved problems.

No Compositionality

Protobuffers offer several "features", but none of them see to work with one another. For example, look at the list of orthogonal-yet-constrained typing features that I found by skimming the documentation.

  • oneof fields can't be repeated.
  • map<k,v> fields have dedicated syntax for their keys and values, but this isn't used for any other types.
  • Despite map fields being able to be parameterized, no user-defined types can be. This means you'll be stuck hand-rolling your own specializations of common data structures.
  • map fields cannot be repeated.
  • map keys can be strings, but can not be bytes. They also can't be enums, even though enums are considered to be equivalent to integers everywhere else in the protobuffer spec.
  • map values cannot be other maps.

This insane list of restrictions is the result of unprincipled design choices and bolting on features after the fact. For example, oneof fields can't be repeated because rather than resulting in a coproduct type, instead the code generator will give you a product of mutually-exclusive optional fields. Such a transformation is only valid for a singular field (and, as we'll see later, not even then.)

The restriction behind map fields being unable to be repeated is related, but shows off a different limitation of the type-system. Behind the scenes, a map<k,v> is desugared into something spiritually similar to repeated Pair<k,v>. And because repeated is a magical language keyword rather than a type in its own right, it doesn't compose with itself.

Your guess is as good as mine for why an enum can't be used as a map key.

What's so frustrating about all of this is a little understanding of how modern type-systems work would be enough to drastically simplify the protobuffer spec and simultaneously remove all of the arbitrary restrictions.

The solution is as follows:

  • Make all fields in a message required. This makes messages product types.
  • Promote oneof fields to instead be standalone data types. These are coproduct types.
  • Give the ability to parameterize product and coproduct types by other types.

That's it! These three features are all you need in order to define any possible piece of data. With these simpler pieces, we can re-implement the rest of the protobuffer spec in terms of them.

For example, we can rebuild optional fields:

product Unit {
  // no fields
}

coproduct Optional<t> {
  t    value = 0;
  Unit unset = 1;
}

Building repeated fields is simple too:

coproduct List<t> {
  Unit empty = 0;
  Pair<t, List<t>> cons = 1;
}

Of course, the actual serialization logic is allowed to do something smarter than pushing linked-lists across the network---after all, implementations and semantics don't need to align one-to-one.

Questionable Choices

In the vein of Java, protobuffers make the distinction between scalar types and message types. Scalars correspond more-or-less to machine primitives---things like int32, bool and string. Messages, on the other hand, are everything else. All library- and user-defined types are messages.

The two varieties of types have completely different semantics, of course.

Fields with scalar types are always present. Even if you don't set them. Did I mention that (at least in proto31) all protobuffers can be zero-initialized with absolutely no data in them? Scalar fields get false-y values---uint32 is initialized to 0 for example, and string is initialized as "".

It's impossible to differentiate a field that was missing in a protobuffer from one that was assigned to the default value. Presumably this decision is in place in order to allow for an optimization of not needing to send default scalar values over the wire. Presumably, though the encoding guide makes no mention of this optimization being performed, so your guess is as good as mine.

As we'll see when we discuss protobuffers' claim to being god's gift to backwards- and forwards-compatible APIs, this inability to distinguish between unset and default values is a nightmare. Especially if indeed it's a design decision made in order to save one bit (set or not) per field.

Contrast this behavior against message types. While scalar fields are dumb, the behavior for message fields is outright insane. Internally, message fields are either there or they're not---but their behavior is crazy. Some pseudocode for their accessor is worth a thousand words. Pretend this is Java or something similar:

private Foo m_foo;

public Foo foo {
  // only if `foo` is used as an expression
  get {
    if (m_foo != null)
      return m_foo;
    else
      return new Foo();
  }

  // instead if `foo` is used as an lvalue
  mutable get {
    if (m_foo = null)
      m_foo = new Foo();
    return m_foo;
  }
}

The idea is that if the foo field is unset, you'll see a default-initialized copy whenever you ask for it, but won't actually modify its container. But if you modify foo, it will modify its parent as well! All of this just to avoid using a Maybe Foo type and the associated "headaches" of the nuance behind needing to figure out what an unset value should mean.

This behavior is especially egregious, because it breaks a law! We'd expect the assignment msg.foo = msg.foo; to be a no-op. Instead the implementation will actually silently change msg to have a zero-initialized copy of foo if it previously didn't have one.

Unlike scalar fields, at least it's possible to detect if a message field is unset. Language bindings for protobuffers offer something along the lines of a generated bool has_foo() method. In the frequent case of copying a message field from one proto to another, iff it was present, you'll need to write the following code:

if (src.has_foo(src)) {
  dst.set_foo(src.foo());
}

Notice that, at least in statically-typed languages, this pattern cannot be abstracted due to the nominal relationship between the methods foo(), set_foo() and has_foo(). Because all of these functions are their own identifiers, we have no means of programmatically generating them, save for a preprocessor macro:

#define COPY_IFF_SET(src, dst, field) \
if (src.has_##field(src)) { \
  dst.set_##field(src.field()); \
}

(but preprocessor macros are verboten by the Google style guide.)

If instead all optional fields were implemented as Maybes, you'd get abstract-able, referentially transparent call-sites for free.

To change tack, let's talk about another questionable decision. While you can define oneof fields in protobuffers, their semantics are not of coproduct types! Rookie mistake my dudes! What you get instead is an optional field for each case of the oneof, and magic code in the setters that will just unset any other case if this one is set.

At first glance, this seems like it should be semantically equivalent to having a proper union type. But instead it is an accursed, unutterable source of bugs! When this behavior teams up with the law-breaking implementation of msg.foo = msg.foo;, it allows this benign-looking assignment to silently delete arbitrary amounts of data!

What this means at the end of the day is that oneof fields do not form law-abiding Prisms, nor do messages form law-abiding Lenses. Which is to say good luck trying to write bug-free, non-trivial manipulations of protobuffers. It is literally impossible to write generic, bug-free, polymorphic code over protobuffers.

That's not the sort of thing anybody likes to hear, let alone those of us who have grown to love parametric polymorphism---which gives us the exact opposite promise.

The Lie of Backwards- and Forwards-Compatibility

One of the frequently cited killer features of protobuffers is their "hassle-free ability to write backwards- and forwards-compatible APIs." This is the claim that has been pulled over your eyes to blind you from the truth.

What protobuffers are is permissive. They manage to not shit the bed when receiving messages from the past or from the future because they make absolutely no promises about what your data will look like. Everything is optional! But if you need it anyway, protobuffers will happily cook up and serve you something that typechecks, regardless of whether or not it's meaningful.

This means that protobuffers achieve their promised time-traveling compatibility guarantees by silently doing the wrong thing by default. Of course, the cautious programmer can (and should) write code that performs sanity checks on received protobuffers. But if at every use-site you need to write defensive checks ensuring your data is sane, maybe that just means your deserialization step was too permissive. All you've managed to do is decentralize sanity-checking logic from a well-defined boundary and push the responsibility of doing it throughout your entire codebase.

One possible argument here is that protobuffers will hold onto any information present in a message that they don't understand. In principle this means that it's nondestructive to route a message through an intermediary that doesn't understand this version of its schema. Surely that's a win, isn't it?

Granted, on paper it's a cool feature. But I've never once seen an application that will actually preserve that property. With the one exception of routing software, nothing wants to inspect only some bits of a message and then forward it on unchanged. The vast majority of programs that operate on protobuffers will decode one, transform it into another, and send it somewhere else. Alas, these transformations are bespoke and coded by hand. And hand-coded transformations from one protobuffer to another don't preserve unknown fields between the two, because it's literally meaningless.

This pervasive attitude towards protobuffers always being compatible rears its head in other ugly ways. Style guides for protobuffers actively advocate against DRY and suggest inlining definitions whenever possible. The reasoning behind this is that it allows you to evolve messages separately if these definitions diverge in the future. To emphasize that point, the suggestion is to fly in the face of 60 years' worth of good programming practice just in case maybe one day in the future you need to change something.

At the root of the problem is that Google conflates the meaning of data with its physical representation. When you're at Google scale, this sort of thing probably makes sense. After all, they have an internal tool that allows you to compare the finances behind programmer hours vs network utilization vs the cost to store x bytes vs all sorts of other things. Unlike most companies in the tech space, paying engineers is one of Google's smallest expenses. Financially it makes sense for them to waste programmers' time in order to shave off a few bytes.

Outside of the top five tech companies, none of us is within five orders of magnitude of being Google scale. Your startup cannot afford to waste engineer hours on shaving off bytes. But shaving off bytes and wasting programmers' time in the process is exactly what protobuffers are optimized for.

Let's face it. You are not Google scale and you never will be. Stop cargo-culting technology just because "Google uses it" and therefore "it's an industry best-practice."

Protobuffers Contaminate Codebases

If it were possible to restrict protobuffer usage to network-boundaries I wouldn't be nearly as hard on it as a technology. Unfortunately, while there are a few solutions in principle, none of them is good enough to actually be used in real software.

Protobuffers correspond to the data you want to send over the wire, which is often related but not identical to the actual data the application would like to work with. This puts us in the uncomfortable position of needing to choose between one of three bad alternatives:

  1. Maintain a separate type that describes the data you actually want, and ensure that the two evolve simultaneously.
  2. Pack rich data into the wire format for application use.
  3. Derive rich information every time you need it from a terse wire format.

Option 1 is clearly the "right" solution, but its untenable with protobuffers. The language isn't powerful enough to encode types that can perform double-duty as both wire and application formats. Which means you'd need to write a completely separate datatype, evolve it synchronously with the protobuffer, and explicitly write serialization code between the two. Seeing as most people seem to use protobuffers in order to not write serialization code, this is obviously never going to happen.

Instead, code that uses protobuffers allows them to proliferate throughout the codebase. True story, my main project at Google was a compiler that took "programs" written in one variety of protobuffer, and spit out an equivalent "program" in another. Both the input and output formats were expressive enough that maintaining proper parallel C++ versions of them could never possibly work. As a result, my code was unable to take advantage of any of the rich techniques we've discovered for writing compilers, because protobuffer data (and resulting code-gen) is simply too rigid to do anything interesting.

The result is that a thing that could have been 50 lines of recursion schemes was instead 10,000 lines of ad-hoc buffer-shuffling. The code I wanted to write was literally impossible when constrained by having protobuffers in the mix.

While this is an anecdote, it's not in isolation. By virtue of their rigid code-generation, manifestations of protobuffers in languages are never idiomatic, nor can they be made to be---short of rewriting the code-generator.

But even then, you still have the problem of needing to embed a shitty type-system into the targeted language. Because most of protobuffers' features are ill-conceived, these unsavory properties leak into our codebases. It means we're forced to not only implement, but also use these bad ideas in any project which hopes to interface with protobuffers.

While it's easy to implement inane things out of a solid foundation, going the other direction is challenging at best and the dark path of Eldrich madness at worst.

In short, abandon all hope ye who introduce protobuffers into your projects.


  1. To this day, there's a raging debate inside Google itself about proto2 and whether fields should ever be marked as required. Manifestos with both titles "optional considered harmful" and "required considered harmful." Good luck sorting that out.

October 10, 2018 03:06 PM

October 09, 2018

Philip Wadler

Developer Yoga

<iframe allowfullscreen="allowfullscreen" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/055aMWWWWUQ/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/055aMWWWWUQ?feature=player_embedded" width="320"></iframe>

My favourite is the first, Lambdasana. Spotted while at LambdUp in Prague.

by Philip Wadler (noreply@blogger.com) at October 09, 2018 05:36 PM

October 08, 2018

FP Complete

2018 Haskell Survey Results

The results are in!!

The powerful Haskell community includes researchers who advance the language, and users who apply the language to solve real-world problems. Recently 1100 people took the time to respond to FP Complete's Haskell User Survey. Here are the key results. See the full report by clicking here.

by Aaron Contorer (aaron@fpcomplete.com) at October 08, 2018 05:52 PM

Michael Snoyman

RAII is better than the bracket pattern

I recently wrote an FP Complete blog post entitled ResourceT: A necessary evil. I had a line in that post I wanted to expand upon:

I believe this is an area where the RAII (Resource Acquisition Is Initialization) approach in both C++ and Rust leads to a nicer solution than even our bracket pattern in Haskell, by (mostly) avoiding the possibility of a premature close.

IO Thief

To demonstrate what I’m talking about, let’s first see an example of the problem in Haskell. First, the good code:

import Control.Exception (bracket)

data MyResource = MyResource

newMyResource :: IO MyResource
newMyResource = do
  putStrLn "Creating a new MyResource"
  pure MyResource

closeMyResource :: MyResource -> IO ()
closeMyResource MyResource = putStrLn "Closing MyResource"

withMyResource :: (MyResource -> IO a) -> IO a
withMyResource = bracket newMyResource closeMyResource

useMyResource :: MyResource -> IO ()
useMyResource MyResource = putStrLn "Using MyResource"

main :: IO ()
main = withMyResource useMyResource

This is correct usage of the bracket pattern, and results in the output:

Creating a new MyResource
Using MyResource
Closing MyResource

We’re guaranteed that MyResource will be closed even in the presence of exceptions, and MyResource is closed after we’re done using it. However, it’s not too difficult to misuse this:

main :: IO ()
main = do
  myResource <- withMyResource pure
  useMyResource myResource

This results in the output:

Creating a new MyResource
Closing MyResource
Using MyResource

We’re still guaranteed that MyResource will be closed, but now we’re using it after it was closed! This may look like a contrived example, and easy to spot in code. However:

  1. Many of us choose Haskell because it forces programming errors to be caught at compile time. This is an error which is definitely not caught at compile time.
  2. In larger code examples, it’s easier for this kind of misuse of the bracket pattern to slip in and evade notice.

Rust

By contrast, with the RAII approach in Rust, this kind of thing can’t happen under normal circumstances. (Sure, you can use unsafe code, and there might be other cases I’m unaware of.) Check this out:

struct MyResource();

impl MyResource {
    fn new() -> MyResource {
        println!("Creating a new MyResource");
        MyResource()
    }

    fn use_it(&self) {
        println!("Using MyResource");
    }
}

impl Drop for MyResource {
    fn drop(&mut self) {
        println!("Closing MyResource");
    }
}

fn main() {
    let my_resource = MyResource::new();
    my_resource.use_it();
}

Despite looking closer to the bad Haskell code, it still generates the right output:

Creating a new MyResource
Using MyResource
Closing MyResource

In fact, try as I might, I cannot figure out a way to get this to close the resource before using it. For example, this is a compile error:

fn main() {
    let my_resource = MyResource::new();
    std::mem::drop(my_resource);
    my_resource.use_it();
}

And this works just fine:

fn create_it() -> MyResource {
    MyResource::new()
}
fn main() {
    let my_resource = create_it();
    my_resource.use_it();
}

The life time of the value is determined correctly and only dropped at the end of main, not the end of create_it.

Fixing it in Haskell

UPDATE In my efforts to make this as simple as possible, I included a “solution” that’s got a massive hole in it. It still demonstrates the basic idea correctly, but if you want actual guarantees, you’ll need to include the phantom type variable on the monad as well. See Dominique’s comment for more information.

We can use a similar approach as the ST strict state transformer via a phantom variable to apply a “lifetime” to the MyResource:

{-# LANGUAGE RankNTypes #-}
import Control.Exception (bracket)

data MyResource s = MyResource

newMyResource :: IO (MyResource s)
newMyResource = do
  putStrLn "Creating a new MyResource"
  pure MyResource

closeMyResource :: MyResource s -> IO ()
closeMyResource MyResource = putStrLn "Closing MyResource"

withMyResource :: (forall s. MyResource s -> IO a) -> IO a
withMyResource = bracket newMyResource closeMyResource

useMyResource :: MyResource s -> IO ()
useMyResource MyResource = putStrLn "Using MyResource"

main :: IO ()
main = withMyResource useMyResource

Now the bad version of the code won’t compile:

main :: IO ()
main = do
  myResource <- withMyResource pure
  useMyResource myResource

Results in:

Main.hs:22:32: error:
    • Couldn't match type ‘s0’ with ‘s’
        because type variable ‘s’ would escape its scope
      This (rigid, skolem) type variable is bound by
        a type expected by the context:
          forall s. MyResource s -> IO (MyResource s0)
        at Main.hs:22:17-35
      Expected type: MyResource s -> IO (MyResource s0)
        Actual type: MyResource s0 -> IO (MyResource s0)
    • In the first argument of ‘withMyResource’, namely ‘pure’
      In a stmt of a 'do' block: myResource <- withMyResource pure
      In the expression:
        do myResource <- withMyResource pure
           useMyResource myResource
   |
22 |   myResource <- withMyResource pure
   |                                ^^^^

This approach isn’t used much in the Haskell world, and definitely has overhead versus Rust:

  • You need to add a type variable to all resource types, which gives more things to juggle
  • It’s non-trivial to deal with promoting values beyond their original scope (like we did in Rust with passing outside of the create_it function)

As I mentioned in the original blog post, regions based on a paper by Oleg explores this kind of idea in more detail.

October 08, 2018 03:18 AM

Holden Karau

Using Spark ML on Spark Errors - What Do the Clusters Tell Us? @ Spark Summit EU 2018

Thanks for joining me on 2018-10-04 for Using Spark ML on Spark Errors - What Do the Clusters Tell Us?.The talk covered:

If youre subscribed to user@spark.apache.org, or work in a large company, you may see some common Spark error messages. Even attending Spark Summit over the past few years you have seen talks like the "Top K Mistakes in Spark." While cool non-machine learning based tools do exist to examine Sparks logs they dont use machine learning and therefore are not as cool but also limited in by the amount of effort humans can put into writing rules for them. This talk will look what happens when we train "regular" clustering models on stack traces, and explore DL models for classifying user message to the Spark list. Come for the reassurance that the robots are not yet able to fix themselves, and stay to learn how to work better with the help of our robot friends. The tl;dr of this talk is Spark ML on Spark output, plus a little bit of Tensorflow is fun for the whole family, but probably shouldnt automatically respond to user list posts just yet. Session hashtag: #SAISML10

.

The slides are at http://bit.ly/2NoIFxr.

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="356" marginheight="0" marginwidth="0" scrolling="no" src="https://www.slideshare.net/slideshow/embed_code/key/haLz2T25nnr4zM" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" width="427"> </iframe> Comment bellow to join in the discussion :).Talk feedback is appreciated at http://bit.ly/holdenTalkFeedback

by Holden Karau (noreply@blogger.com) at October 08, 2018 02:17 AM

October 06, 2018

Brent Yorgey

Counting inversions with monoidal sparks

Time for me to reveal the example I had in mind that led to the generalization in my previous post. Thanks for all the interesting comments: it seems like there are some interesting connections to be explored (e.g. to the algebra of graphs, formal group laws, …?)!

This is a literate Haskell post; download it and play along in ghci! (Note it requires GHC 8.6 since I couldn’t resist making use of DerivingVia…)

> {-# LANGUAGE DefaultSignatures          #-}
> {-# LANGUAGE FlexibleInstances          #-}
> {-# LANGUAGE MultiParamTypeClasses      #-}
> {-# LANGUAGE DerivingStrategies         #-}
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> {-# LANGUAGE DerivingVia                #-}
> {-# LANGUAGE TypeApplications           #-}
> {-# LANGUAGE ScopedTypeVariables        #-}
> 
> import Data.Semigroup
> import Data.Coerce

Consider a sequence of integers \sigma = a_1, a_2, \dots, a_n. (Actually, integers is too specific; any linearly ordered domain will do.) An inversion is a pair of positions in \sigma which are “out of order”: that is, (i,j) such that i < j but a_i > a_j. So, for example, \sigma = [3,5,1,4,2] has six inversions, namely (3,1), (3,2), (5,1), (5,4), (5,2), (4,2). (Here I’ve written the elements that are out of order rather than their positions, which doesn’t matter much when the elements are all distinct; but it’s important to keep in mind that e.g. [2,2,1] has two inversions, not one, because each copy of 2 makes an inversion with the 1.) The total number of inversions of \sigma is denoted \mathrm{inv}(\sigma).

One way to think about the inversion count is as a measure of how far away the sequence is from being sorted. In particular, bubble sort will make precisely \mathrm{inv}(\sigma) adjacent swaps while sorting \sigma. The highest possible value of \mathrm{inv}(\sigma) is n(n-1)/2, when \sigma is sorted in reverse order.

The obvious brute-force algorithm to count inversions is to use two nested loops to enumerate all possible pairs of elements, and increment a counter each time we discover a pair which is out of order. This clearly takes O(n^2) time. Can it be done any faster?

It turns out the (generally well-known) answer is yes, using a variant of mergesort. The trick is to generalize to counting inversions and sorting the sequence at the same time. First split the sequence in half, and recursively sort and count the inversions in each half. Any inversion in the original sequence must either be entirely contained in one of the two halves (these will be counted by the recursive calls), or have one endpoint in the left half and one in the right. One key observation at this point is that any inversion with one endpoint in each half will still be an inversion even after independently sorting the two halves. The other key observation is that we can merge the two sorted subsequences and count inversions between them in linear time. Use the usual two-finger algorithm for merging two sorted sequences; each time we take an element from the right subsequence, it’s because it is less than all the remaining elements in the left subsequence, but it was to the right of all of them, so we can add the length of the remaining left subsequence to the inversion count. Intuitively, it’s this ability to count a bunch of inversions in one step which allows this algorithm to be more efficient, since any algorithm which only ever increments an inversion counter is doomed to be O(n^2) no matter how cleverly it splits up the counting. In the end, the number of total inversions is the sum of the inversions counted recursively in the two sublists, plus any inversions between the two sublists.

Here’s some Haskell code implementing this sorted-merge-and-inversion-count. We have to be a bit careful because we don’t want to call length on the remaining sublist at every step (that would ruin the asymptotic performance!), so we precompute the length and pass along the length of the left subsequence as an extra parameter which we keep up-to-date as we recurse.

> -- Precondition: the input lists are sorted.
> -- Output the sorted merge of the two lists, and the number of pairs
> -- (a,b) such that a \in xs, b \in ys with a > b.
> mergeAndCount :: Ord a => [a] -> [a] -> ([a], Int)
> mergeAndCount xs ys = go xs (length xs) ys
>   -- precondition/invariant for go xs n ys:   n == length xs
>   where
>     go [] _ ys = (ys, 0)
>     go xs _ [] = (xs, 0)
>     go (x:xs) n (y:ys)
>       | x <= y    = let (m, i) = go xs (n-1) (y:ys) in (x:m, i)
>       | otherwise = let (m, i) = go (x:xs) n ys     in (y:m, i + n)
> 
> merge :: Ord a => [a] -> [a] -> [a]
> merge xs ys = fst (mergeAndCount xs ys)
> 
> inversionsBetween :: Ord a => [a] -> [a] -> Int
> inversionsBetween xs ys = snd (mergeAndCount xs ys)

Do you see how this is an instance of the sparky monoid construction in my previous post? A is the set of sorted lists with merge as the monoid operation; B is the natural numbers under addition. The spark operation takes two sorted lists and counts the number of inversions between them. So the monoid on pairs A \times B merges the lists, and adds the inversion counts together with the number of inversions between the two lsits.

We have to verify that this satisfies the laws: let a be any sorted list, then we need

  • a \cdot \varepsilon_A = \varepsilon_B, that is, a `inversionsBetween` [] = 0. This is true since there are never any inversions between a and an empty list. Likewise for \varepsilon_A \cdot a = \varepsilon_B.

  • a `inversionsBetween` (a1 `merge` a2) == (a `inversionsBetween` a1) + (a `inversionsBetween` a2). This is also true since a1 `merge` a2 contains the same elements as a1 and a2: any inversion between a and a1 `merge` a2 will be an inversion between a and a1, or between a and a2, and vice versa. The same reasoning shows that (a1 `merge` a2) `inversionsBetween` a == (a1 `inversionsBetween` a) + (a2 `inversionsBetween` a).

Note that A and B are commutative monoids, but the spark operation isn’t commutative; in fact, any given pair of elements is an inversion between a1 and a2 precisely iff they are not an inversion between a2 and a1. Note also that A and B aren’t idempotent; for example merging a sorted list with itself produces not the same list, but a new list with two copies of each element.

So let’s see some more Haskell code to implement the entire algorithm in a nicely modular way. First, let’s encode sparky monoids in general. The Sparky class is for pairs of types with a spark operation. As we saw in the example above, sometimes it may be more efficient to compute a_1 \diamond a_2 and the spark a_1 \cdot a_2 at the same time, so we bake that possibility into the class.

> class Sparky a b where

The basic spark operation, with a default implementation that projects the result out of the prodSpark method.

>   (<.>) :: a -> a -> b
>   a1 <.> a2 = snd (prodSpark a1 a2)

prodSpark does the monoidal product and spark at the same time, with a default implementation that just does them separately.

>   prodSpark :: a -> a -> (a,b)
>   default prodSpark :: Semigroup a => a -> a -> (a,b)
>   prodSpark a1 a2 = (a1 <> a2, a1 <.> a2)

Finally we can specify that we have to implement one or the other of these methods.

>   {-# MINIMAL (<.>) | prodSpark #-}

Sparked a b is just a pair type, but with Semigroup and Monoid instances that implement the sparky product.

> data Sparked a b = S { getA :: a, getSpark :: b }
>   deriving Show
> 
> class Semigroup a => CommutativeSemigroup a
> class (Monoid a, CommutativeSemigroup a) => CommutativeMonoid a
> 
> instance (Semigroup a, CommutativeSemigroup b, Sparky a b) => Semigroup (Sparked a b) where
>   S a1 b1 <> S a2 b2 = S a' (b1 <> b2 <> b')
>     where (a', b') = prodSpark a1 a2
> 
> instance (Monoid a, CommutativeMonoid b, Sparky a b) => Monoid (Sparked a b) where
>   mempty = S mempty mempty

Now we can make instances for sorted lists under merge…

> newtype Sorted a = Sorted [a]
>   deriving Show
> 
> instance Ord a => Semigroup (Sorted a) where
>   Sorted xs <> Sorted ys = Sorted (merge xs ys)
> instance Ord a => Monoid (Sorted a) where
>   mempty = Sorted []
> 
> instance Ord a => CommutativeSemigroup (Sorted a)
> instance Ord a => CommutativeMonoid (Sorted a)

…and for inversion counts.

> newtype InvCount = InvCount Int
>   deriving newtype Num
>   deriving (Semigroup, Monoid) via Sum Int
> 
> instance CommutativeSemigroup InvCount
> instance CommutativeMonoid InvCount

Finally we make the Sparky (Sorted a) InvCount instance, which is just mergeAndCount (some conversion between newtypes is required, but we can get the compiler to do it automagically via coerce and a bit of explicit type application).

> instance Ord a => Sparky (Sorted a) InvCount where
>   prodSpark = coerce (mergeAndCount @a)

And here’s a function to turn a single a value into a sorted singleton list paired with an inversion count of zero, which will come in handy later.

> single :: a -> Sparked (Sorted a) InvCount
> single a = S (Sorted [a]) 0

Finally, we can make some generic infrastructure for doing monoidal folds. First, Parens a encodes lists of a which have been explicitly associated, i.e. fully parenthesized:

> data Parens a = Leaf a | Node (Parens a) (Parens a)
>   deriving Show

We can make a generic fold for Parens a values, which maps each Leaf into the result type b, and replaces each Node with a binary operation:

> foldParens :: (a -> b) -> (b -> b -> b) -> Parens a -> b
> foldParens lf _  (Leaf a)   = lf a
> foldParens lf nd (Node l r) = nd (foldParens lf nd l) (foldParens lf nd r)

Now for a function which splits a list in half recursively to produce a balanced parenthesization.

> balanced :: [a] -> Parens a
> balanced []  = error "List must be nonempty"
> balanced [a] = Leaf a
> balanced as  = Node (balanced as1) (balanced as2)
>   where (as1, as2) = splitAt (length as `div` 2) as

Finally, we can make a balanced variant of foldMap: instead of just mapping a function over a list and then reducing with mconcat, as foldMap does, it first creates a balanced parenthesization for the list and then reduces via the given monoid. This will always give the same result as foldMap due to associativity, but in some cases it may be more efficient.

> foldMapB :: Monoid m => (e -> m) -> [e] -> m
> foldMapB leaf = foldParens leaf (<>) . balanced

Let’s try it out!

λ> :set +s
λ> getSpark $ foldMap single [3000, 2999 .. 1 :: Int]
Sum {getSum = 4498500}
(34.94 secs, 3,469,354,896 bytes)
λ> getSpark $ foldMapB single [3000, 2999 .. 1 :: Int]
Sum {getSum = 4498500}
(0.09 secs, 20,016,936 bytes)

Empirically, it does seem that we are getting quadratic performance with normal foldMap, but O(n \log n) with foldMapB. We can verify that we are getting the correct inversion count in either case, since we know there should be n(n-1)/2 when the list is reversed, and sure enough, 3000 \cdot 2999 / 2 = 4498500.

by Brent at October 06, 2018 08:53 PM

October 05, 2018

Douglas M. Auclair (geophf)

August 2018 1HaskellADay problems and solutions

by geophf (noreply@blogger.com) at October 05, 2018 12:41 PM

October 04, 2018

FP Complete

Well-Typed.Com

Upcoming Haskell events: Haskell eXchange, Courses, MuniHac

Upcoming events

In the upcoming months, Well-Typed will be participating in a number of events that we would like to advertise here:

Well-Typed’s Guide to the Haskell Type System

London, 10 October 2018

On the day before the Haskell eXchange, Adam Gundry will teach a single-day compact course on Haskell type system extensions. Learn all about GADTs, data kinds, rank-n polymorphism, type families and more.

Registration is open.

Haskell eXchange 2018

London, 11–12 October 2018

The Haskell eXchange will return to London for the seventh time, with keynotes by Simon Peyton Jones, Stephanie Weirich, Niki Vazou and Simon Marlow, and more than 30 other talks on all topics Haskell. This year’s programme includes three talks by Well-Typed: Andres Löh on Deriving Via, Duncan Coutts on the Cardano Cryptocurrency, and David Eichmann on Geometry with Denotational Design.

Registration is open.

Well-Typed’s Guide to Performance and Optimisation

London, 15–16 October 2018

After the Haskell eXchange, Andres Löh will teach a two-day course on performance and optimisation. Learn about data structures, performance pitfalls, common optimisations that GHC applies, how to read GHC’s internal Core language, and more.

Registration is open.

MuniHac 2018

Unterföhring / Munich, 16–18 November 2018

After the successful MuniHac in 2016, we will have a second MuniHac in Munich this November! Join us for three days of conversations and hacking on Haskell libraries, applications and tools. Everyone is welcome, whether beginner or expert. There are some talks, including keynotes by Ben Gamari from Well-Typed, Matthew Pickering from the University of Bristol and Ryan Scott from Indiana University. Furthermore, there will be plenty of opportunity to learn and improve. You can work on your own project or join others in theirs.

Well-Typed is co-organising this event with TNG Technology Consulting. The event is free to attend, but the number of spaces is limited, so be sure to register early.

Registration is open.

by andres at October 04, 2018 12:48 PM

Functional Jobs

Software Engineer - Haskell at Capital Match (Full-time)

Who We Are Capital Match is the largest marketplace invoice financing platform in Southeast Asia based in Singapore. We are an innovative fintech business with a range of financial solutions to SMEs and investors. We have funded more than US$80 million in Singapore over the past 3 years. We are funded by multiple VCs and institutional investors including Dymon Asia Capital, an alternative asset manager with $6bn AUM and Eduardo Saverin's B Capital Group.

Role We are looking for experienced developers to lead our tech growth in the fintech space, expand into surrounding countries, develop new products and integrations. You will be involved in all aspects of the creation, growth and operations of a secure web-based platform. Experience in front-to-back feature development, distributed deployment and automation in the cloud, build and test automation, is highly desirable.

Our Platform Our platform is primarily developed in Haskell with a ClojureScript frontend. We use Docker containers, Nix and standard cloud infrastructure systems to manage our production rollouts. We make heavy use of modern functional programming practices, such as property-based testing and type-driven programming, to improve the quality of our code. We use many popular Haskell libraries such as Lens, QuickCheck, Servant, Scotty, Aeson, Attoparsec and Pandoc. We use continuous testing, integration and deployment wherever possible

Job Requirements

  • Adequate software engineering experience
  • Software engineering experience with Haskell
  • Strong foundation in data structures, algorithms, and software design
  • Experience of developing both server and web applications

Additional Points

  • Experience with modern software engineering practices such as TDD, CI, Emergent Design, Refactoring, Peer Review and Continuous Improvement
  • Familiarity with Linux systems, command-line environments and cloud-based deployments
  • A background in fintech and especially the lending space would be an advantage, but is not essential

What We Offer

  • Monthly salary from SGD 5,000-10,000 depends on experience
  • Equity options for excellent candidate
  • Working visa will be provided

How to Apply Send your resume to careers [at] capital-match [dot] com

Get information on how to apply for this position.

October 04, 2018 02:07 AM

Tweag I/O

capability: the ReaderT pattern without boilerplate

Andreas Herrmann, Arnaud Spiwack

About a year ago, Michael Snoyman made a blog post about the ReaderT pattern. Ostensibly, it's a blog post about preferring to encode state as IORef-s when you can. But that's not how we read it. What we saw first and foremost is a story about using extensional type classes describing specifically the effects that functions use, but not how the effects are implemented (see the MonadBalance story in Michael's blog post). We call these extensional type classes capabilities. Here is an excellent blog post from Matt Parsons which takes this aspect to heart.

Capability is a library to replace the MTL with capabilities. In this post, we'll argue why capabalities are important, why you should use them, and tell you about what it took to design a library of capabilities with good ergonomics. It turns out that a brand new language extension that shipped with GHC 8.6, -XDerivingVia, has a crucial role in this story.

The difference with the MTL

How is using capabilities, like in Snoyman's and Parsons's blog posts any different from using the well-trodden MTL? Quite a bit! The MTL's classes, like MonadReader, MonadState and their close relatives, are intensional: they reflect how the monad has been constructed. A monad MyM is a MonadState because it is a stack of monad transformers, one of which is a StateT.

This is because of what Haskell instances mean: if I have an instance,

instance MonadState s m => MonadState s (ReaderT r m)

while it may look like we're saying that it suffices to have MonadState s m for ReaderT r m to be MonadState s, what we are really saying is that MonadState s (ReaderT r m) means that MonadState s m. It defines a computation, rather than a deduction. In particular, we are not permitted to add the following instance:

data St = ...
instance MonadState St (ReaderT (IORef St) IO)

You may want to work around this issue using {-# OVERLAPPING #-} instances. However, in doing so, you are acting against the semantics of instances, and heading for trouble. For an example of issues with overlapping instances, see the warning at the end of the Overlapping instances section of the GHC manual.

In contrast, what the ReaderT pattern is advertising is extensional classes, indicating what an individual function is allowed to do (hence the name "capability"), regardless of how the monad is implemented.

The problem

Irrespective of whether you are willing to twist the arm of the MTL with {-# OVERLAPPING #-} instances, when programming with capabilities you will run into two kind of issues. The first is probably the lesser of the two, but has been a known pain point with the MTL for a while: it's that the MTL uses types (e.g. the state type) to discriminate layers. In other words: with the MTL, you can't have two states of the same type in your capabilities.

This, of course, is not a problem if you are writing your own type classes: you can simply use a different class for each piece of state (e.g. MonadBalance). This leads us to the second, more serious issue: lack of inference. With all its faults, the MTL gives a very comfortable environment: it defines plenty of generic instances, so that when we give a concrete monad stack, then all the instances are automatically computed for us. In contrast, with capabilities and the ReaderT pattern, we collect all the capabilities, and assemble a bespoke type to handle all of these instances. Haskell's instance resolution is simply not equipped for this.

The bottom line is: an insane amount of boilerplate. Custom type class definitions. A slew of instances at each main entry point (where a concrete type is defined for the monad).

Deriving Via

What we would really like is a way to use type class instances the other way around, compared to instance resolution. Instead of reading

instance MonadState s m => MonadState s (ReaderT r m)

as saying that MonadState, on ReaderT means that MonadState s m, and fixing the implementation, we would like to read it as: if I have an implementation of MonadState s m, then this is a possible implementation of MonadState on a ReaderT.

This is made possible by a new language extension available in the freshly released GHC 8.6: -XDerivingVia.

In short, -XDerivingVia is a generalisation of -XGeneralizedNewtypeDeriving that allows you not only to derive an instance for a newtype, but also from a newtype, or, and this is most relevant for us, from a combination of newtypes. For example:

{-# LANGUAGE DerivingVia #-}

import Data.Monoid (Sum (..))

newtype MyInt = MyInt Int
  deriving (Monoid, Semigroup) via Sum Int
  deriving Num via Int

In the above snippet we define MyInt which wraps an Int, and derive two instances for it. The Monoid instance is taken from Sum Int, and the Num instance is taken directly from Int. Note the via keyword in the deriving clauses. (In this example we could also have derived the Num instance using -XGeneralizedNewtypeDeriving.)

You will find a more complete introduction in Baldur Blondal's talk on the subject. If you want all the details, head to the proposal or the paper.

Enter capability

With the above piece of kit in hand, we can write the capability library. This library provides strategies that can be composed to derive capabilities using the -XDerivingVia language extension.

capability defines a set of standard, reusable capability type classes, such as HasReader, or HasState. Contrary to the MTL type classes these are parameterized by a name (aka tag), which makes it possible to refer to, say, multiple different states in the same computation, even if they correspond to the same type.

getAB :: (HasState "a" Int m, HasState "b" Int m) => m (Int, Int)
getAB = do
  a <- get @"a"  -- get state under tag "a"
  b <- get @"b"  -- get state under tag "b"
  pure (a, b)

The library then provides newtypes to derive instances of these capability type-classes in deriving via clauses, similar to Sum in the MyInt example above.

For example, given an MTL MonadReader instance, we can derive a HasReader capability as follows:

data AppData = ...

newtype AppM a = AppM (ReaderT AppData IO a)
  deriving (HasReader "appData" AppData) via
    MonadReader (ReaderT AppData IO)

We can also combine multiple newtypes to derive capability instances. Building on the above example, we can pick a field within AppData as follows:

data AppData = AppData { intRef :: IORef Int, ... }
  deriving Generic

newtype AppM a = AppM (ReaderT AppData IO a)
  deriving (HasReader "intRef" (IORef Int)) via
    Field "intRef" "appData" (MonadReader (ReaderT AppData IO))

The Field combinator takes two tags as arguments. The first specifies the field name, and also the new tag. The second specifies the old tag, which provides the record with the requested field. Note, that the MonadReader newtype can provide an instance for any tag. The Field combinator uses generic-lens under the hood, which is why AppData needs to have a Generic instance.

A worked example: combining writers without guilt

Let's consider a complete example to demonstrate how you could use capability in your own projects. The code is available in the capability repository if you want to follow along.

In this example we will receive a text as input and want to count occurrences of words and letters in the text, ignoring white space. To that end we will use a writer monad. Recall, that writer has the method tell :: w -> m (), which will mappend the given w to the current tally, starting from mempty. This requires a Monoid instance on w.

We start with counting single letters and words.

-- | Count the occurrence of a single letter.
countLetter ::
  HasWriter "letterCount" (Occurrences Char) m
  => Char -> m ()
countLetter letter = tell @"letterCount" (oneOccurrence letter)

-- | Count the occurrence of a single word.
countWord ::
  HasWriter "wordCount" (Occurrences Text) m
  => Text -> m ()
countWord word = tell @"wordCount" (oneOccurrence word)

The type Occurrences k is a newtype around a Map from values k to their count. Its Monoid instance will add occurrences in the expected fashion.

newtype Occurrences k = Occurrences (Map k Int)

instance Ord k => Monoid (Occurrences k)
  -- See repository for instance implementation.

-- | A single occurrence of the given value.
oneOccurrence :: k -> Occurrences k
oneOccurrence k = Occurrences $ Map.singleton k 1

Next, we combine countLetter and countWord to handle one word in the input text.

-- | Count the occurrence of a single word and all the letters in it.
countWordAndLetters ::
  ( HasWriter "letterCount" (Occurrences Char) m
  , HasWriter "wordCount" (Occurrences Text) m )
  => Text -> m ()
countWordAndLetters word = do
  countWord word
  mapM_ countLetter (Text.unpack word)

Finally, we can handle the full input text by first splitting it into its words and then applying the above function to each word.

-- | Count the occurrences of words and letters in a text,
-- excluding white space.
countWordsAndLettersInText ::
  ( HasWriter "letterCount" (Occurrences Char) m
  , HasWriter "wordCount" (Occurrences Text) m )
  => Text -> m ()
countWordsAndLettersInText text =
  mapM_ countWordAndLetters (Text.words text)

In a production setting we might prefer to stream the input, instead of holding he whole text in memory. For simplicity's sake we will omit this here.

With that we have written a program that demands two HasWriter capabilities.

Before we can execute this program we need to define a concrete implementation that provides these capabilities. This is where we make use of the deriving-via strategies that the library offers.

It is well-known that the writer monad provided by MTL has a space leak. In capability, we can derive a writer capability from a state capability instead, to avoid this issue. In fact, we don't even provide a way to derive a writer capability from a writer monad. Following the ReaderT pattern we derive the state capabilities from reader capabilities on IORefs.

First, we define the application context. A record holding two IORefs - one for each counter.

-- | Counter application context.
data CounterCtx = CounterCtx
  { letterCount :: IORef (Occurrences Char)
    -- ^ Counting letter occurrences.
  , wordCount :: IORef (Occurrences Text)
    -- ^ Counting word occurrences.
  } deriving Generic

Next, we define our application monad.

-- | Counter application monad.
newtype Counter a = Counter { runCounter :: CounterCtx -> IO a }
  deriving (Functor, Applicative, Monad) via (ReaderT CounterCtx IO)

Note that we use ReaderT in the deriving via clause as a strategy to derive the basic Functor, Applicative, and Monad instances.

Deriving the writer capabilities makes use of a large set of newtypes provided by the capability library. Each line after the via keyword corresponds to one newtype. Comments explain the purpose of the respective newtype. Read these from bottom to top.

  deriving (HasWriter "letterCount" (Occurrences Char)) via
    (WriterLog  -- Generate HasWriter using HasState of Monoid
    (ReaderIORef  -- Generate HasState from HasReader of IORef
    (Field "letterCount" "ctx"  -- Focus on the field letterCount
    (MonadReader  -- Generate HasReader using mtl MonadReader
    (ReaderT CounterCtx IO)))))  -- Use mtl ReaderT newtype

The "wordCount" writer is derived in the same way:

  deriving (HasWriter "wordCount" (Occurrences Text)) via
    WriterLog (ReaderIORef
    (Field "wordCount" "ctx" (MonadReader (ReaderT CounterCtx IO))))

The only thing left is to combine all these pieces into an executable program. We will take the text as an argument, and return an IO action that executes countWordsAndLettersInText using our Counter monad, and prints the resulting word and letter counts to standard output.

-- | Given a text count the occurrences of all words and letters in it,
-- excluding white space, and print the outcome to standard output.
wordAndLetterCount :: Text -> IO ()
wordAndLetterCount text = do

First, we setup the required IORefs and the counter context:

  lettersRef <- newIORef Map.empty
  wordsRef <- newIORef Map.empty
  let ctx = CounterCtx
        { letterCount = lettersRef
        , wordCount = wordsRef
        }

Then, we call countWordsAndLettersInText on the input text, and instantiate it using our Counter application monad:

  let counter :: Counter ()
      counter = countWordsAndLettersInText text

Finally, we run counter and print the results:

  runCounter counter ctx
  let printOccurrencesOf name ref = do
        putStrLn name
        occurrences <- readIORef ref
        ifor_ occurrences $ \item num ->
          putStrLn $ show item ++ ": " ++ show num
  printOccurrencesOf "Letters" lettersRef
  printOccurrencesOf "Words" wordsRef

Executing this program in GHCi should produce the following output:

>>> wordAndLetterCount "ab ba"
Letters
'a': 2
'b': 2
Words
"ab": 1
"ba": 1

This concludes the example. We invite you to experiment with this library. It is still in an early stage and the API is subject to change. However, your feedback will help to evolve it in a better direction.

A word on free monads

Another solution to many of the same problems has been known for a while: free monads and extensible effects. As it happens, capability and free monads can be formally compared. In this paper, Mauro Jaskelioff and Russell O'Connor, prove that free monads are a special case of capabilities (it's not phrased in these terms, of course, but that's what the paper amounts to).

So another way of looking at capability is that it is a library of extensible effects. It makes it possible to write effects which are not available to free monads: free monads can only model algebraic effects, while capabilities do not have such a restriction. For instance the HasCatch capability, giving a function the ability to catch errors, is not algebraic, hence not available to free monads.

However, the most important reason for us to develop capability is that we find this style of programming quite manageable and idiomatic, whereas free-monad programming quickly becomes unwieldy. This is an entirely subjective judgement of course, but we believe that it has slowed the adoption of extensible effects. Absolutely wonderful though they are! As a bonus, capabilities should be more efficient than free-monad-style programming because it doesn't rely on a tagged encoding.

October 04, 2018 12:00 AM

October 03, 2018

Christopher Allen

Wrapping up Haskell Book

I’d like to summarize some of the background to Haskell Programming from First Principles’ development and finalization.

A brief summary of events

Julie and I worked together on the book as equal partners until we started to disagree about its direction. Even though we had different ideas and work needs, I explicitly expressed my intention that we still finish the first edition of the Haskell Book together. The book was in limbo after that point. Work from both of us after that was sporadic and unfocused. There was disagreement on whether the book needed further editing to be finalized and printed. The emails we got about syntax errors, typos and other issues in the book seemed conclusive to me that it did need further editing. I suggested an editor for the book which Julie rejected. It became more and more difficult for Julie and I to communicate with each other about the book which created more tension.

In October 2017, Julie demanded that I enter into negotiations with her over the book’s completion and management. This is when the lawyers started talking. We tried working through different scenarios such as:

  • We would continue as equal partners, but there’s a structured agreement in place for the book’s completion and management.
  • I would sell Julie my rights in the book or vice versa.

There was a lot of back and forth and it took nearly a year of negotiations before we arrived at an agreement. Work on the book was halted because we could not agree and our working relationship had soured. The final agreement that we arrived at was based largely on the terms Julie demanded. It was supposed to be an amicable resolution to our problems. Julie got what she wanted and would benefit from the book’s final publication and the readers would finally get a finished product. The agreement included a confidentiality clause as well. To see Julie attack me online with spiteful insinuations and untruthful comments about me and what happened with the book after she voluntarily signed the agreement is upsetting.

What happens now

The book is going through its final edit. When that is done the final electronic version will be published and then the print version will be sorted out.

I know this site is a bit of a disaster zone, but if you like my writing or think you could learn something useful from me, please take a look at the Haskell book I've been writing. There's a free sample available too!

October 03, 2018 12:00 AM

October 02, 2018

Michael Snoyman

How I research health

I’d like to present two fairly straightforward points:

  • I’ve written multiple blog posts on health related topics
  • I have absolutely no formal training on the topic, and there’s no reason people should take my blog posts as authoratative

That said, I continue to write these blog posts, share information with friends and family, and make decisions for myself. How do I reconcile this? How do I approach the truly terrifying level of contradictory information available in the health/nutrition/exercise landscape? How do I want other people reading content from me to relate to it, given that I’m a self-acknowledged non-expert?

I strongly believe that the biggest hurdle for people to adopt healthy lifestyle choices these days is knowing where to begin (with willpower to do so in second place). Are you supposed to follow low carb, or low fat? Jog, or sprint? Body weight training, or free weights?

In general, this is similar to the Paradox of Choice, only worse: not only can you become paralyzed by the sheer number of options out there, but you can also be paralyzed by the fact that different sources will claim that each alternative will actively harm you. Given that landscape, it’s only natural for people to walk away saying “the experts are just going to change their minds in 10 years, there’s no point trying to make changes to my lifestyle.” And I should know: I felt that way for years.

My process

Having established my credentials as a non-expert in this field, here’s how I’ve approached gathering knowledge and making decisions on the topics:

  • Trust very little. If “experts” can completely contradict each other, blindly trusting “experts” is impossible. You’ll end up on a low-fat, low-carb, vegan, carnivore diet. In other words, you’ll starve yourself to death. Except the experts also say not to use fasting.
  • Listen to everything. This may sound contradictory to my previous point, but it’s not. You should read, listen to podcasts, watch videos, and consume any other content from as varied a set of sources as you can. Take them all into account, but don’t blindly trust anything. Look for patterns in the recommendations. Pay attention to the inconsistencies. Watch for trends. This may help guide you towards some relatively uncontroversial opinions (e.g., “avoid processed foods,” “don’t eat unless you’re hungry”), and help you understand better what the current debates are all about.
  • Dig into the sources. This stage is honestly optional, but I find it enjoyable because I like this stuff. Having understood where the “authorities” are arguing, look at their sources, and others they don’t provide. Read nutrition studies and reviews. It may help you understand how those “authorities” are misrepresenting some facts, for example. Accept the fact that even these primary sources are going to contradict, but see if you can parse through the contradictions. Example: it’s very common for “low carb” studies to come up with vastly different results; pay attention to if they’re using the same definition of “low carb.”
  • Experiment on yourself. Sample size 1 experiments without a double blind control aren’t real science. Fair enough. But they do tell you a lot about your own body and how you respond. Even if it’s the placebo effect, it’s still an effect. If you get a headache every time you eat X, even if all of the studies say it helps with headaches… maybe don’t eat X. (Intentionally not giving a concrete example, I don’t want to cause a placebo effect in anyone.)
    • One caveat I always feel obligated to restate: I am not a doctor. My advice is just the advice of someone who doesn’t know anything. If you have medical conditions, or specific medical instructions, I am absolutely not telling you to ignore them.

My sources

My sources of information these days tend towards voices in the low carb and barbell training communities. More on how I ended up here a bit below. As I said above, I’d strongly recommend gathering many different sources. And even if you disagree with one side (e.g., you’re either pro- or anti-vegan), I suggest finding the best sources on each side that you can.

Here are some of the sources I read or listen to.

And books I’ve read and recommend:

  • The Obesity Code
  • The Complete Guide to Fasting
  • The Hungry Brain
  • The Case Against Sugar
  • The Secret Life of Fat

Some notes on these:

  • The Hungry Brain and The Case Against Sugar are in many ways contradictory. However, as I’ll mention below, I think they can complement each other.
  • I got less out of The Complete Guide to Fasting than I expected. It was interesting and motivational, but I was already motivated to try fasting. If you want to know why you should try fasting, read it. If you just want to do it: feel free to just fast :)
  • Similarly, The Secret Life of Fat was more theoretical on topics I was less interested in, and didn’t lend much on the practical side. Still a good collection of information.

My filters

There’s a huge amount of information out there. It’s simply not humanly possible to read everything, experiment with everything, etc. You’ll need to ultimately install some filters to help you parse through the information. Here are some I use:

  • I like to be educated on a topic. But if it doesn’t affect me personally, or I’m happy with my approach for the moment, I’ll stop focusing on it.

  • I believe sources are biased. This applies to me (as I tried to point out a bit above, and will do more so of soon). As a religious Jew, I use this example: if a Rabbi told me that eating pork was unhealthy, I would distrust him. I believe there’s quite a bit of that in the health space, where moral arguments end up influencing, for example, complete avoidance of animal products or using only humanely raised products. I’m not going to comment here on the moral arguments at all, but I will say that I think they bias many proponents. Similarly, people who have made a career on advocating a certain dietary or exercise approach will have a vested interest in continue to espouse it, despite new evidence contradicting.

    We can’t eliminate this bias, it’s human nature. My best advice, and what I try to do, is to identify it, and weigh arguments. When possible, I try to find less-biased sources on topics, such as Jeff Nippard’s video on vegan diet science.

  • After I get into a rut of a specific approach, I try to force myself to listen to contradicting views again. It’s enlightening to see how I will react negatively on hearing the arguments. I try hard to force myself to get past my own biases and judge the information on its own. Basically: when I listen to a video or read a post/article/book, I try to turn off my falsehood filter temporarily, absorb the information, and only analyze its veracity after the fact.

I’m currently actively looking for information sources which are more positive of high-carb and vegan eating approaches. The sources I’ve found so far typically have been too moralistic (eating animals is bad) or authoritarian (all major organizations support what we say) for my taste. I’d be happy if people want to leave some recommendations below.

My biases

This section is mostly irrelevant, but for those curious, I want to be more explicit about my current biases:

  • I believe resistance training is overall more important to health than cardio. Of resistance training, I believe weight training is easier to improve with than bodyweights or resistance bands. And of weight training, freeweights (barbells in particular) give the best results, though require significant effort in learning the form. And you’ll never beat deadlifts for back problems.
  • Sugar is the worst part of our diets today. You should avoid it like the plague. I’m mixed on artificial sweeteners.
  • Vegetable oil is almost as bad as sugar.
  • Both low carb and low fat work really well. But overall, low carb is easier to lose weight with and adhere to.
  • The simple rule of “no processed foods” will solve about 80% of diet problems, if you include sugar, vegetable oil, and refined grains as processed foods.
  • Fasting (intermittent, multiday, etc), are healthy. Not only are they good physically, but more importantly they prove to yourself that you’re stronger than you think.
  • While hormones are an important part of obesity, and likely the prime factor (constantly high insulin), the approach in “The Hungry Brain” of highly palatable foods/food reward causing overconsumption of calories seems to be a factor. (I might even say it’s obviously a factor.) Despite much public attention, I don’t see the hormone and food reward hypotheses as completely conflicting, and believe both should be paid attention to for optimizing health.

October 02, 2018 07:08 PM

Neil Mitchell

Full-time Haskell jobs in Zürich/New York, at Digital Asset

Summary: We're hiring 3 Haskell programmers and a few other roles too.

I am currently working at Digital Asset, working on our DAML programming language. We're seeking 3 additional Haskell programmers to join, 2 in New York and 1 in Zurich (remote work is not currently an option). There are also a ton of other jobs on our website, including Formal Methods and nix + some Haskell Build Engineering (also available at a more junior level).

What we do

We have built DAML, the Digital Asset Modelling Language, which is the centerpiece of our distributed ledger technology. DAML is a contract language that consists of a strongly-typed purely functional core extended with domain specific constructs to express the flow of rights and obligations underlying today's multi-party business processes. Application Developers using DAML and our distributed ledger technology are supported by the DAML SDK. It provides a type-safe integration of DAML with existing technology like Java, Scala, XML and SQL, and contains DAML Studio, which provides a modern IDE experience to develop, test, and analyse DAML programs.

Working on the Language Engineering team with Digital Asset involves partnering with people around the world (we have centers in New York, Zurich and Sydney), working with exciting new technology, where many of the answers haven't yet been figured out, producing solutions for clients, such as replacing the settlement and clearing platform of the Australian Stock Exchange (ASX), and making sure the end result has the quality required for robust usage. It's challenging work, but the impact could be huge.

What we require

We're looking for the best functional programmers out there, with a strong bias towards Haskell. If not Haskell, then Scala is useful, as other teams in the company write Scala. However, we've hired ML/F# programmers too, with good results. In particular we want:
  • Experienced functional programmer. Either some open-source libraries (Hackage/GitHub) or commercial experience.
  • Writes good, clean, effective code.
  • Existing compiler development experience is useful, if it's with GHC then even better.
We do not require any existing blockchain/DLT/finance knowledge.

How to apply

To apply, email neil.mitchell AT digitalasset.com with a copy of your CV. If you have any questions, email me.
The best way to assess technical ability is to look at code people have written. If you have any packages on Hackage or things on GitHub, please point me at the best projects. If your best code is not publicly available, please describe the Haskell projects you've been involved in.

by Neil Mitchell (noreply@blogger.com) at October 02, 2018 11:21 AM

Matt Parsons

Keep your types small...

… and your bugs smaller

In my post “Type Safety Back and Forth”, I discussed two different techniques for bringing type safety to programs that may fail. On the one hand, you can push the responsibility forward. This technique uses types like Either and Maybe to report a problem with the inputs to the function. Here are two example type signatures:

safeDivide
    :: Int
    -> Int
    -> Maybe Int

lookup
    :: Ord k
    => k
    -> Map k a
    -> Maybe a

If the second parameter to safeDivide is 0, then we return Nothing. Likewise, if the given k is not present in the Map, then we return Nothing.

On the other hand, you can push it back. Here are those functions, but with the safety pushed back:

safeDivide
    :: Int
    -> NonZero Int
    -> Int

lookupJustified
    :: Key ph k
    -> Map ph k a
    -> a

With safeDivide, we require the user pass in a NonZero Int – a type that guarantees that the underlying value is not 0. With lookupJustified, the ph type guarantees that the Key is present in the Map, so we can pull the resulting value out without requiring a Maybe. (Check out the tutorial for justified-containers, it is pretty awesome)

Expansion and Restriction

“Type Safety Back and Forth” uses the metaphor of “pushing” the responsibility in one of two directions:

  • forwards: the caller of the function is responsible for handling the possible error output
  • backwards: the caller of the function is required to providing correct inputs

However, this metaphor is a bit squishy. We can make it more precise by talking about the “cardinality” of a type – how many values it can contain. The type Bool can contain two values – True and False, so we say it has a cardinality of 2. The type Word8 can express the numbers from 0 to 255, so we say it has a cardinality of 256.

The type Maybe a has a cardinality of 1 + a. We get a “free” value Nothing :: Maybe a. For every value of type a, we can wrap it in Just.

The type Either e a has a cardinality of e + a. We can wrap all the values of type e in Left, and then we can wrap all the values of type a in Right.

The first technique – pushing forward – is “expanding the result type.” When we wrap our results in Maybe, Either, and similar types, we’re saying that we can’t handle all possible inputs, and so we must have extra outputs to safely deal with this.

Let’s consider the second technique. Specifically, here’s NonZero and NonEmpty, two common ways to implement it:

newtype NonZero a 
    = UnsafeNonZero 
    { unNonZero :: a 
    }

nonZero :: (Num a, Eq a) => a -> Maybe (NonZero a)
nonZero 0 = Nothing
nonZero i = Just (UnsafeNonZero i)

data NonEmpty a = a :| [a]

nonEmpty :: [a] -> Maybe (NonEmpty a)
nonEmpty []     = Nothing
nonEmpty (x:xs) = x :| xs

What is the cardinality of these types?

NonZero a represents “the type of values a such that the value is not equal to 0.” NonEmpty a represents “the type of lists of a that are not empty.” In both of these cases, we start with some larger type and remove some potential values. So the type NonZero a has the cardinality a - 1, and the type NonEmpty a has the cardinality [a] - 1.

Interestingly enough, [a] has an infinite cardinality, so [a] - 1 seems somewhat strange – it is also infinite! Math tells us that these are even the same infinity. So it’s not the mere cardinality that helps – it is the specific value(s) that we have removed that makes this type safer for certain operations.

These are custom examples of refinement types. Another closely related idea is quotient types. The basic idea here is to restrict the size of our inputs. Slightly more formally,

  • Forwards: expand the range
  • Backwards: restrict the domain

Constraints Liberate

Runar Bjarnason has a wonderful talk titled Constraints Liberate, Liberties Constrain. The big idea of the talk, as I see it, is this:

When we restrict what we can do, it’s easier to understand what we can do.

I feel there is a deep connection between this idea and Rich Hickey’s talk Simple Made Easy. In both cases, we are focusing on simplicity – on cutting away the inessential and striving for more elegant ways to express our problems.

Pushing the safety forward – expanding the range – does not make things simpler. It provides us with more power, more options, and more possibilities. Pushing the safety backwards – restricting the domain – does make things simpler. We can use this technique to take away the power to get it wrong, the options that aren’t right, and the possibilities we don’t want.

Indeed, if we manage to restrict our types sufficiently, there may be only one implementation possible! The classic example is the identity function:

identity :: a -> a
identity a = a

This is the only implementation of this function that satisfies the type signature (ignoring undefined, of course). In fact, for any function with a sufficiently precise type signature, there is a way to automatically derive the function! Joachim Breitner’s justDoIt is a fascinating utility that can solve these implementations for you.

With sufficiently fancy types, the computer can write even more code for you. The programming language Idris can write well-defined functions like zipWith and tranpose for length-indexed lists nearly automatically!

Restrict the Range

I see this pattern and I am compelled to fill it in:

  Restrict Expand
Range   :(
Domain :D  

I’ve talked about restricting the range and expanding the domain. Expanding the domain seems silly to do – we accept more possible values than we know what to do with. This is clearly not going to make it easier or simpler to implement our programs. However, there are many functions in Haskell’s standard library that have a domain that is too large. Consider:

take :: Int -> [a] -> [a]

Int, as a domain, is both too large and too small. It allows us to provide negative numbers: what does it even mean to take -3 elements from a list? As Int is a finite type, and [a] is infinite, we are restricted to only using this function with sufficiently small Ints. A closer fit would be take :: Natural -> [a] -> [a]. Natural allows any non-negative whole number, and perfectly expresses the reasonable domain. Expanding the domain isn’t desirable, as we might expect.

base has functions with a range that is too large, as well. Let’s consider:

length :: [a] -> Int

This has many of the same problems as take – a list with too many elements will overflow the Int, and we won’t get the right answer. Additionally, we have a guarantee that we forget – a length for any container must be positive! We can more correctly express this type by restricting the output type:

length :: [a] -> Natural

A perfect fit

The more precisely our types describe our program, the fewer ways we have to go wrong. Ideally, we can provide a correct output for every input, and we use a type that tightly describes the properties of possible outputs.

October 02, 2018 12:00 AM

October 01, 2018

Brent Yorgey

Monoidal sparks

While at ICFP in St. Louis this past week, I discovered an interesting construction on monoids that no one I talked to (including Kenny Foner and Edward Kmett) seemed to have heard of or thought about before. In this post I’ll present the abstract construction itself, and in another post I’ll explain the particular context in which I first came up with it. (Normally I would put the examples first, before explaining the idea in general; but I only know of one example so far, and I’m curious to see if anyone will come up with more. I don’t want to bias people’s thinking too much with my one example!)

The bigger context here is thinking about different ways of putting a monoid structure on a product type A \times B, assuming A and B are themselves monoids. Previously I knew of two ways to do this. The obvious way is to just have the two sides operate in parallel, without interacting at all: (a_1,b_1) \diamond (a_2,b_2) = (a_1 \diamond a_2, b_1 \diamond b_2) and so on. Alternatively, if A acts on B, we can form the semidirect product.

But here is a third way. Suppose (A, \varepsilon_A, \diamond) is a monoid, and (B, \varepsilon_B, \oplus) is a commutative monoid. To connect them, we also suppose there is another binary operation - \cdot - : A \to A \to B, which I will pronounce “spark”. The way I like to think of it is that two values of type A, in addition to combining to produce another A via the monoid operation, also produce a “spark” of type B. That is, values of type B somehow capture information about the interaction between pairs of A values.

Sparking needs to interact sensibly with the monoid structures on A and B: in particular, fixing either argument must result in a monoid homomorphism from A to B. That is, for any choice of a \in A, we have a \cdot \varepsilon_A = \varepsilon_B (i.e. \varepsilon_A is boring and can never produce a nontrivial spark with anything else), and a \cdot (a_1 \diamond a_2) = (a \cdot a_1) \oplus (a \cdot a_2) (i.e. sparking commutes with the monoid operations). Similar laws should hold if we fix the second argument of - \cdot - instead of the first.

Given all of this, we can now define a monoid on A \times B as follows:

(a_1, b_1) \otimes (a_2, b_2) = (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2))

That is, we combine the A values normally, and then we combine the B values together with the “spark” of type B produced by the two A values.

Let’s see that this does indeed define a valid monoid:

  • The identity is (\varepsilon_A, \varepsilon_B), since

    (\varepsilon_A, \varepsilon_B) \otimes (a,b) = (\varepsilon_A  \diamond a, \varepsilon_B \oplus b \oplus (\varepsilon_A \cdot a)) =  (a, b \oplus \varepsilon_B) = (a,b)

    Notice how we used the identity laws for A (once) and B (twice), as well as the law that says \varepsilon_A \cdot a =  \varepsilon_B. The proof that (\varepsilon_A, \varepsilon_B) is a right identity for \otimes is similar.

  • To see that the combining operation is associative, we can reason as follows:

    \begin{array}{rcl} & & ((a_1,b_1) \otimes (a_2,b_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus (a_1 \cdot a_2) \oplus b_3 \oplus ((a_1 \diamond a_2) \cdot a_3)) \\[0.5em] & = & \qquad \text{\{\begin{math}- \cdot a_3\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}

    and

    \begin{array}{rcl} & & (a_1,b_1) \otimes ((a_2,b_2) \otimes (a_3,b_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1,b_1) \otimes (a_2 \diamond a_3, b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus (b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \oplus (a_1 \cdot (a_2 \diamond a_3))) \\[0.5em] & = & \qquad \text{\{\begin{math}a_1 \cdot -\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}

    In a formal proof one would have to also explicitly note uses of associativity of \diamond and \oplus but I didn’t want to be that pedantic here.

In addition, if A is a commutative monoid and the spark operation - \cdot - commutes, then the resulting monoid (A \times B, \otimes) will be commutative as well.

The proof of associativity gives us a bit of insight into what is going on here. Notice that when reducing (a_1,b_1) \otimes (a_2,b_2) \otimes (a_3,b_3), we end up with all possible sparks between pairs of a’s, i.e. (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3), and one can prove that this holds more generally. In particular, if we start with a list of A values:

[a_1, a_2, \dots, a_n],

then inject them all into A \times B by pairing them with \varepsilon_B:

[(a_1, \varepsilon_B), (a_2, \varepsilon_B), \dots, (a_n, \varepsilon_B)],

and finally fold this list with \otimes, the second element of the resulting pair is

\displaystyle \bigoplus_{i \neq j} (a_i \cdot a_j),

that is, the combination (via the monoid on B) of the sparks between all possible pairings of the a_i. Of course there are O(n^2) such pairings: the point is that whereas computing this via a straightforward fold over the list may well take O(n^2) time, by using a balanced fold (i.e. splitting the list in half recursively and then combining from the leaves up) it may be possible to compute it in O(n \log n) time instead (at least, this is the case for the example I have in mind!).

Please leave a comment if you can you think of any instances of this pattern, or if you have seen this pattern discussed elsewhere. In a future post I will write about the instance I had in mind when coming up with this generalized formulation.

by Brent at October 01, 2018 04:15 PM

Magnus Therning

Using a configuration in Scotty

At work we’re only now getting around to put correlation IDs into use. We write most our code in Clojure but since I’d really like to use more Haskell at work I thought I’d dive into Scotty and see how to deal with logging and then especially how to get correlation IDs into the logs.

The types

For configuration it decided to use the reader monad inside ActionT from Scotty. Enter Chell:

In order to run it I wrote a function corresponding to scotty:

Correlation ID

To deal with the correlation ID each incoming request should be checked for the HTTP header X-Correlation-Id and if present it should be used during logging. If no such header is present then a new correlation ID should be created. Since it’s per request it feels natural to create a WAI middleware for this.

The easiest way I could come up with was to push the correlation ID into the request’s headers before it’s passed on:

It also turns out to be useful to have both a default correlation ID and a function for pulling it out of the headers:

Getting the correlation ID into the configuration

Since the correlation ID should be picked out of the request on handling of every request it’s useful to have it the configuration when running the ChellActionM actions. However, since the correlation ID isn’t available when running the reader (the call to runReaderT in chell) something else is called for. When looking around I found local (and later I was pointed to the more general withReaderT) but it doesn’t have a suitable type. After some help on Twitter I arrived at withConfig which allows me to run an action in a modified configuration:

Making it handy to use

Armed with this I can put together some functions to replace Scotty’s get, post, etc. With a configuration type like this:

The modified get looks like this (Scotty’s original is S.get)

With this in place I can use the simpler ReaderT Config IO for inner functions that need to log.

October 01, 2018 12:00 AM

September 30, 2018

ERDI Gergo

Composable CPU descriptions in CλaSH, and wrap-up of RetroChallenge 2018/09

My last post ended with some sample CλaSH code illustrating the spaghetti-ness you can get yourself into if you try to describe a CPU directly as a function (CPUState, CPUIn) -> (CPUState, CPUOut). I promised some ideas for improving that code.

To start off gently, first of all we can give names to some common internal operations to help readability. Here's the code from the previous post rewritten with a small kit of functions:

intensionalCPU (s0, CPUIn{..}) = case phase s of
    WaitKeyPress reg ->
        let s' = case cpuInKeyEvent of
                Just (True, key) -> goto Fetch1 . setReg reg key $ s
                _ -> s
            out = def{ cpuOutMemAddr = pc s' }
        in (s', out)                   
    Fetch1 ->
        let s' = goto Exec s{ opHi = cpuInMem, pc = succ $ pc s }
            out = def{ cpuOutMemAddr = pc s' }
        in (s', out)
  where
    s | cpuInVBlank = s0{ timer = fromMaybe 0 . predIdx $ timer s0 }
      | otherwise = s0
    

Using a State monad

To avoid the possibility of screwing up the threading of the internal state, we can use the State CPUState monad:

stateCPU :: CPUIn -> State CPUState CPUOut      
stateCPU CPUIn{..} = do
    when cpuInVBlank $
        modify $ \s -> s{ timer = fromMaybe 0 . predIdx $ timer s }
    gets phase >>= \case 
      WaitKeyPress reg -> do
        forM_ cpuInKeyEvent $ \(pressed, key) -> when pressed $ do
            setReg reg key
            goto Fetch1
        return def{ cpuOutMemAddr = pc s' }
      Fetch1 -> do
        modify $ \s -> s{ opHi = cpuInMem, pc = succ $ pc s }
        goto Exec
        return def{ cpuOutMemAddr = pc s' }
    

At this point, the state-accessing actions either come from the kit, because they are useful in many parts of our CPU description (like setReg), or they read or change individual fields of the CPUState record. This second group can benefit from using lenses:

stateCPU CPUIn{..} = do
    when cpuInVBlank $
        timer %= fromMaybe 0 . predIdx
    use phase >>= \case 
      WaitKeyPress reg -> do
        forM_ cpuInKeyEvent $ \(pressed, key) -> when pressed $ do
            setReg reg key
            goto Fetch1
        return def{ cpuOutMemAddr = pc s' }
      Fetch1 -> do
        opHi .= cpuInMem
        pc %= succ
        goto Exec
        return def{ cpuOutMemAddr = pc s' }
    

Problems with composability

While this code is much more readable than the original one, and allows describing the internal state changes piecewise, it still has a problem with composability. To illustrate this, let's add some more functionality by implementing some CPU instructions (simplified a bit from a real CHIP-8 which can only write to memory through a save-registers instruction and even that is addressed by a dedicated pointer register; and accessing the framebuffer is also done via multiple-byte blitting only).

stateCPU CPUIn{..} = do
    when cpuInVBlank $
        timer %= fromMaybe 0 . predIdx
    use phase >>= \case 
      WaitKeyPress reg -> do
        forM_ cpuInKeyEvent $ \(pressed, key) -> when pressed $ do
            setReg reg key
            goto Fetch1
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Idle -> do
        goto Fetch1
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Fetch1 -> do
        opHi .= cpuInMem
        pc %= succ
        goto Exec
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Exec -> do
        opLo .= cpuInMem
        pc %= succ
        goto Fetch1
        decode >>= \case
          WaitKey reg -> do
            goto $ WaitKeyPress reg
            pc <- use pc    
            return def{ cpuOutMemAddr = pc }
          LoadImm reg imm -> do
            setReg reg imm
            pc <- use pc    
            return def{ cpuOutMemAddr = pc }
          WriteMem addr reg -> do
            val <- getReg reg
            goto Idle -- flush write to RAM before starting next fetch
            return def{ cpuOutMemAddr = addr, cpuOutMemWrite = Just val }           
          SetPixel regX regY -> do
            x <- getReg regX
            y <- getReg regY
            pc <- use pc
            return def{ cpuOutMemAddr = pc, cpuOutFBAddr = (x, y), cpuOutFBWrite = Just True }          
          -- And a lot more opcodes here
    

Since there are going to be a lot of opcodes to support, it could seem like a good idea to refactor the Exec state to be a separate function, leaving only the implementation of the other control phases in the main function:

stateCPU cpuIn@CPUIn{..} = do
    when cpuInVBlank $
        timer %= fromMaybe 0 . predIdx
    use phase >>= \case 
      WaitKeyPress reg -> do
        forM_ cpuInKeyEvent $ \(pressed, key) -> when pressed $ do
            setReg reg key
            goto Fetch1
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Idle -> do
        goto Fetch1
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Fetch1 -> do
        opHi .= cpuInMem
        pc %= succ
        goto Exec
        pc <- use pc    
        return def{ cpuOutMemAddr = pc }
      Exec -> do
        opLo .= cpuInMem
        pc %= succ
        goto Fetch1
        decode >>= exec cpuIn
        
exec CPUIn{..} (WaitKey reg) = ... -- same as previous version
exec CPUIn{..} (LoadImm reg imm) = ... -- same as previous version
exec CPUIn{..} (WriteMem addr reg) = ...
exec CPUIn{..} (SetPixel regX regY) = ...
    

However, this becomes problematic if we want to set some parts of the CPUOut result in a generic way, outside exec. Suppose we implement sound support, which in CHIP-8 is done via another 60Hz timer:

stateCPU cpuIn@CPUIn{..} = do
    when cpuInVBlank $ do
        timer %= fromMaybe 0 . predIdx
        soundTimer %= fromMaybe 0 . predIdx
    soundOn <- uses soundTimer (/= 0)
    def <- return def{ cpuOutSound = soundOn }
    

This takes care of setting cpuOutSound in the branches for WaitKeyPress, Idle and Fetch1 (albeit in an ugly way, by shadowing def), but now this needs to be passed as an extra parameter to exec (or the code to set cpuOutSound needs to be duplicated).

Assembling the output piecewise

So what we want is a way to specify the resulting CPUOut such that

  1. Reasonable defaults (like reading the next instruction from RAM via cpuOutMemAddr = pc) are applied automatically, without requiring any code. Note that the defaults shouldn't need to be static; they can depend on the state.
  2. Various parts of the CPU implementation can contribute to the final CPUOut result that is visible from the outside.

This has led me to a design where the CPU is described by a type CPU i s o = RWS i (Endo o) s:

  • The State axis is, of course, the internal state, i.e. the CPU registers, as before.
  • The Reader axis provides easy access to the inputs (as of the current clock cycle) to (potentially deeply nested) functions, without having to pass anything around by hand.
  • The Writer axis collects an Endo CPUOut; in other words, a function CPUOut -> CPUOut with "later" functions applied after (and thus overriding) "earlier" functions. Thus, the final collected Endo CPUOut can be applied to a CPUOut computed as the default output for the final CPUState:
    runCPU :: (s -> o) -> CPU i s o () -> (i -> State s o)
    runCPU mkDef cpu inp = do
        s <- get
        let (s', f) = execRWS (unCPU cpu) inp s
        put s'
        def <- gets mkDef
        return $ appEndo f def    
            

With this setup, we can rewrite our CPU implementation as:

cpu = do
    CPUIn{..} <- input
    when cpuInVBlank $
        timer %= fromMaybe 0 . predIdx
        soundTimer %= fromMaybe 0 . predIdx
    soundOn <- uses soundTimer (/= 0)
    when soundOn $ do
        tell $ \out -> out{ cpuOutSound = True }

    use phase >>= \case 
      WaitKeyPress reg -> do
        forM_ cpuInKeyEvent $ \(pressed, key) -> when pressed $ do
            setReg reg key
            goto Fetch1
      Idle -> do
        goto Fetch1
      Fetch1 -> do
        opHi .= cpuInMem
        pc %= succ
        goto Exec
      Exec -> do
        opLo .= cpuInMem
        pc %= succ
        goto Fetch1
        decode >>= exec

exec (WaitKey reg) = do
    goto $ WaitKeyPress reg
exec (LoadImm reg imm) = do
    setReg reg imm
exec (WriteMem addr reg) = do
    val <- getReg reg
    writeMem addr val
    goto Idle -- flush write to RAM before starting next fetch
exec (SetPixel regX regY) = do
    x <- getReg regX
    y <- getReg regY
    writeFB (x, y) True
    

Most branches don't need to do anything to get the correct final CPUOut; and just like we were able to name the State kit of setReg &c, we can define

writeMem addr val = tell $ \out -> out{ cpuOutMemAddr = addr, cpuOutMemWrite = Just val }
writeFB addr val = tell $ \out -> out{ cpuOutFBAddr = addr, cpuOutFBWrite = Just val }
    

The system described above is implemented here for the reusable library definitions and here for CHIP-8 specifically; the version that uses lenses is in the branch linked above, since I am not 100% convinced yet that the cognitive overhead of the lens library is worth it once enough kit is developed around state access.

Future directions

There are two questions about the above that I feel that haven't been resolved yet:

  • Is it a good idea to include ContT in the CPU monad stack? On one hand, it is known to be problematic to compose ContT with Reader/Writer; on the other hand, here we only need ask and tell, not local or pass. On the gripping hand, ContT might be useful, for example, to describe CPU sub-states that wait for some external output before proceeding normally, as an early exit from the CPU monad.
  • Can the CPUState and Phase types themselves be defined piecewise? Is there some unholy union of extensible effects, extensible records and extensible sum types that would allow us to, informally speaking, define the WaitKeyPress phase together with its handler, in the middle of exec where the WaitKey instruction is implemented?

RetroChallenge 2018/09 wrap-up

All in all, even though I couldn't get as far as I originally hoped, I am glad I at least managed to build a CHIP-8 computer in CλaSH that can boot up on real hardware and play original CHIP-8 games; that's pretty much what I originally set out to do. The RetroChallenge format of detailed blog posts concurrent with the actual development work being done is quite taxing on me, because I am slow to write these posts; overall, I have probably spent about half and half of my RetroChallenge time on coding/design vs. writing about it. But the fixed one-month timeframe and the great progress reports by the other participants have been great motivators; I would probably try something next time where I can expect less uknown unknowns.

There is still work to be done even on this CHIP-8 computer: I've found some games that don't work as expected when they try to use the built-in hexadecimal digit font; and there are of course the previously discussed performance problems inherent in addressing the frame buffer as single bits. Also, I would like to adapt it to use a real four-by-four keypad (by scanning the key rows from the FPGA) and a PCD8544 monochrome matrix LCD

And then, of course, further exploration of the design space of CPU descriptions discussed above; and then moving on to a "real" CPU, probably by rewriting my Lava 6502 core. Also, I will need to get a new FPGA dev board with a chip that is supported by a contemporary toolchain, so that I won't get bogged down by problems like the Spartan-6 synthesis bug.

September 30, 2018 09:15 PM

September 29, 2018

Stackage Blog

Announcing stackage nightly snapshots with ghc-8.6.1

I am pleased to announce that Stackage nightly snapshots now use ghc-8.6.1. Stack users can simply use resolver: nightly-2018-09-29 in a project’s stack.yaml file in order to build and test with ghc-8.6.1.

As is usual when a new ghc is released, many packages were removed from the nightly snapshot due to version constraints and build failures. We expect many packages to return quickly to the build plan, and we hope that the existing snapshots will help mainatainers get back in by making it easy to build and test their packages.

Please check to see if your favorite packages are in the latest nightly snapshot, and open up a PR or an issue on Stackage if you find anything missing which is known to work with ghc-8.6.1.

As ghc moves to its new 6-month release cycle, I’d like to encourage everyone to be proactive in bumping bounds and testing packages you rely on with the new ghc alphas and release candidates as they come out. Haskell has a remarkable ecosystem; let’s strive to make it even better!

September 29, 2018 12:01 AM

Lysxia's blog

September 24, 2018

Ken T Takusagawa

[zvyswyrq] Fun with accents

Cès̋ hll m̀a̋k lw̏ r̋p̏e̊c̋tın̑g̀ ån̄ s̃tbhṅt öf liḡi, r̃ p̏r̈hıbıtiğ th fèé ĕx́ŕc̄iśë théf; õ ăbr̊idg̈ıthe̋ fr̊èdȏ f ȅćh, f thẽ p̊r̊; thig̈ht f thĕ p̈ēŏp̋l p̈e̋āc̄èảblỹ to̊ äbl, d tő p̈tıtiỏń thė Gŕn̉t f ä ŕde̋s̋ṡ f g̈r̋is̃.

Unicode combining diacritics can put an accent on any character.  We limit to characters without ascenders.  i and j are treated specially as explained below.  We also experimented with diacritical marks below (cedilla, ogonek), but it caused formatting problems with some fonts when there was both a mark above and below: the mark below was (probably correctly) off center, but it caused the mark above to incorrectly go off center also.  Therefore, we did underline via HTML, and only below letters without descenders.

We experimented with putting accents on dotless i and j, but formatting got messed up with some fonts: the accents were wider than the character so overlapped with accents on neighboring characters.  (This is only a problem in proportional fonts, not monospace.)  Therefore the only "accent" possible on i and j are the removal of the dot.  Possible problem: if a font has a "f i" ligature, it might be difficult to distinguish the ligature versus f followed by a dotless i: dotted= fi fj, dotless= fı fȷ

The general idea is that ascenders and descenders in some letters force space to be reserved for them for all letters, so fill empty space with an accent or underline to increase information density.  (Of course, it will become harder to read, as increased density often does.)  Encoding information as a pattern of accents on some "carrier" text is mixed-radix base conversion.

There was a choice between the curved breve/inverted breve pair or the angled circumflex/caron pair: probably don't use both because they look too similar.  We chose curvy because there were lots of angles already with the single and double acute and grave.  Tilde and macron look somewhat similar, but we used both.  We chose [ 0x300, 0x301, 0x306, 0x311, 0x303, 0x304, 0x30b, 0x30f, 0x308, 0x307, 0x30a, 0x309 ].

Although not relevant to the above example, some fonts have descenders for capital Q and J so should not be underlined.  QJQJOIOI.  Same using CSS instead of the HTML U tag (some browsers do CSS differently than <u>): QJQJOIOI.

Haskell source code to add random accents, and to enumerate the range of possible characters subject to the constraints we've chosen.  Editorially: Unicode is supposed to capture all the world's languages that actually exist.  It isn't supposed to be used to invent new characters not used in any real language, a capability we are abusing here.

a<wbr></wbr>à<wbr></wbr>á<wbr></wbr>ă<wbr></wbr>ȃ<wbr></wbr>ã<wbr></wbr>ā<wbr></wbr>a̋<wbr></wbr>ȁ<wbr></wbr>ä<wbr></wbr>ȧ<wbr></wbr>å<wbr></wbr>ả<wbr></wbr>a<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>b<wbr></wbr>b<wbr></wbr>c<wbr></wbr>c̀<wbr></wbr>ć<wbr></wbr>c̆<wbr></wbr>c̑<wbr></wbr>c̃<wbr></wbr>c̄<wbr></wbr>c̋<wbr></wbr>c̏<wbr></wbr>c̈<wbr></wbr>ċ<wbr></wbr>c̊<wbr></wbr>c̉<wbr></wbr>c<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>d<wbr></wbr>d<wbr></wbr>e<wbr></wbr>è<wbr></wbr>é<wbr></wbr>ĕ<wbr></wbr>ȇ<wbr></wbr>ẽ<wbr></wbr>ē<wbr></wbr>e̋<wbr></wbr>ȅ<wbr></wbr>ë<wbr></wbr>ė<wbr></wbr>e̊<wbr></wbr>ẻ<wbr></wbr>e<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>f<wbr></wbr>f<wbr></wbr>g<wbr></wbr>g̀<wbr></wbr>ǵ<wbr></wbr>ğ<wbr></wbr>g̑<wbr></wbr>g̃<wbr></wbr>ḡ<wbr></wbr>g̋<wbr></wbr>g̏<wbr></wbr>g̈<wbr></wbr>ġ<wbr></wbr>g̊<wbr></wbr>g̉<wbr></wbr>h<wbr></wbr>h<wbr></wbr>i<wbr></wbr>ı<wbr></wbr>i<wbr></wbr>ı<wbr></wbr>j<wbr></wbr>ȷ<wbr></wbr>k<wbr></wbr>k<wbr></wbr>l<wbr></wbr>l<wbr></wbr>m<wbr></wbr>m̀<wbr></wbr>ḿ<wbr></wbr>m̆<wbr></wbr>m̑<wbr></wbr>m̃<wbr></wbr>m̄<wbr></wbr>m̋<wbr></wbr>m̏<wbr></wbr>m̈<wbr></wbr>ṁ<wbr></wbr>m̊<wbr></wbr>m̉<wbr></wbr>m<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>n<wbr></wbr>ǹ<wbr></wbr>ń<wbr></wbr>n̆<wbr></wbr>n̑<wbr></wbr>ñ<wbr></wbr>n̄<wbr></wbr>n̋<wbr></wbr>n̏<wbr></wbr>n̈<wbr></wbr>ṅ<wbr></wbr>n̊<wbr></wbr>n̉<wbr></wbr>n<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>o<wbr></wbr>ò<wbr></wbr>ó<wbr></wbr>ŏ<wbr></wbr>ȏ<wbr></wbr>õ<wbr></wbr>ō<wbr></wbr>ő<wbr></wbr>ȍ<wbr></wbr>ö<wbr></wbr>ȯ<wbr></wbr>o̊<wbr></wbr>ỏ<wbr></wbr>o<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>p<wbr></wbr>p̀<wbr></wbr>ṕ<wbr></wbr>p̆<wbr></wbr>p̑<wbr></wbr>p̃<wbr></wbr>p̄<wbr></wbr>p̋<wbr></wbr>p̏<wbr></wbr>p̈<wbr></wbr>ṗ<wbr></wbr>p̊<wbr></wbr>p̉<wbr></wbr>q<wbr></wbr>q̀<wbr></wbr>q́<wbr></wbr>q̆<wbr></wbr>q̑<wbr></wbr>q̃<wbr></wbr>q̄<wbr></wbr>q̋<wbr></wbr>q̏<wbr></wbr>q̈<wbr></wbr>q̇<wbr></wbr>q̊<wbr></wbr>q̉<wbr></wbr>r<wbr></wbr>r̀<wbr></wbr>ŕ<wbr></wbr>r̆<wbr></wbr>ȓ<wbr></wbr>r̃<wbr></wbr>r̄<wbr></wbr>r̋<wbr></wbr>ȑ<wbr></wbr>r̈<wbr></wbr>ṙ<wbr></wbr>r̊<wbr></wbr>r̉<wbr></wbr>r<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>s<wbr></wbr>s̀<wbr></wbr>ś<wbr></wbr>s̆<wbr></wbr>s̑<wbr></wbr>s̃<wbr></wbr>s̄<wbr></wbr>s̋<wbr></wbr>s̏<wbr></wbr>s̈<wbr></wbr>ṡ<wbr></wbr>s̊<wbr></wbr>s̉<wbr></wbr>s<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>t<wbr></wbr>t<wbr></wbr>u<wbr></wbr>ù<wbr></wbr>ú<wbr></wbr>ŭ<wbr></wbr>ȗ<wbr></wbr>ũ<wbr></wbr>ū<wbr></wbr>ű<wbr></wbr>ȕ<wbr></wbr>ü<wbr></wbr>u̇<wbr></wbr>ů<wbr></wbr>ủ<wbr></wbr>u<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>v<wbr></wbr>v̀<wbr></wbr>v́<wbr></wbr>v̆<wbr></wbr>v̑<wbr></wbr>ṽ<wbr></wbr>v̄<wbr></wbr>v̋<wbr></wbr>v̏<wbr></wbr>v̈<wbr></wbr>v̇<wbr></wbr>v̊<wbr></wbr>v̉<wbr></wbr>v<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>w<wbr></wbr>ẁ<wbr></wbr>ẃ<wbr></wbr>w̆<wbr></wbr>w̑<wbr></wbr>w̃<wbr></wbr>w̄<wbr></wbr>w̋<wbr></wbr>w̏<wbr></wbr>ẅ<wbr></wbr>ẇ<wbr></wbr>ẘ<wbr></wbr>w̉<wbr></wbr>w<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>x<wbr></wbr>x̀<wbr></wbr>x́<wbr></wbr>x̆<wbr></wbr>x̑<wbr></wbr>x̃<wbr></wbr>x̄<wbr></wbr>x̋<wbr></wbr>x̏<wbr></wbr>ẍ<wbr></wbr>ẋ<wbr></wbr>x̊<wbr></wbr>x̉<wbr></wbr>x<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>y<wbr></wbr>ỳ<wbr></wbr>ý<wbr></wbr>y̆<wbr></wbr>y̑<wbr></wbr>ỹ<wbr></wbr>ȳ<wbr></wbr>y̋<wbr></wbr>y̏<wbr></wbr>ÿ<wbr></wbr>ẏ<wbr></wbr>ẙ<wbr></wbr>ỷ<wbr></wbr>z<wbr></wbr>z̀<wbr></wbr>ź<wbr></wbr>z̆<wbr></wbr>z̑<wbr></wbr>z̃<wbr></wbr>z̄<wbr></wbr>z̋<wbr></wbr>z̏<wbr></wbr>z̈<wbr></wbr>ż<wbr></wbr>z̊<wbr></wbr>z̉<wbr></wbr>z<wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr><wbr></wbr>A<wbr></wbr>A<wbr></wbr>B<wbr></wbr>B<wbr></wbr>C<wbr></wbr>C<wbr></wbr>D<wbr></wbr>D<wbr></wbr>E<wbr></wbr>E<wbr></wbr>F<wbr></wbr>F<wbr></wbr>G<wbr></wbr>G<wbr></wbr>H<wbr></wbr>H<wbr></wbr>I<wbr></wbr>I<wbr></wbr>J<wbr></wbr>K<wbr></wbr>K<wbr></wbr>L<wbr></wbr>L<wbr></wbr>M<wbr></wbr>M<wbr></wbr>N<wbr></wbr>N<wbr></wbr>O<wbr></wbr>O<wbr></wbr>P<wbr></wbr>P<wbr></wbr>Q<wbr></wbr>R<wbr></wbr>R<wbr></wbr>S<wbr></wbr>S<wbr></wbr>T<wbr></wbr>T<wbr></wbr>U<wbr></wbr>U<wbr></wbr>V<wbr></wbr>V<wbr></wbr>W<wbr></wbr>W<wbr></wbr>X<wbr></wbr>X<wbr></wbr>Y<wbr></wbr>Y<wbr></wbr>Z<wbr></wbr>Z

Total number of possibilities: 460.

More capital letters possible.

by Ken (noreply@blogger.com) at September 24, 2018 08:16 PM

September 23, 2018

ERDI Gergo

CPU modeling in CλaSH

My entry for RetroChallenge 2018/09 is building a CHIP-8 computer. Previously, I've talked in detail about the video signal generator and the keyboard interface; the only part still missing is the CPU.

The CHIP-8 instruction set

Since the CHIP-8 was originally designed to be an interpreted language run as a virtual machine, some of its instructions are quite high-level. For example, the framebuffer is modified via a dedicated blitting instruction; there is a built-in random number generator; and instructions to manipulate two 60 Hz timers. Other instructions are more in line with what one would expect to see in a CPU, and implement basic arithmetic such as addition or bitwise AND. There is also a generic escape hatch instruction but that doesn't really apply to hardware implementations.

The CPU has 16 generic-purpose 8-bit registers V0…VF; register VF is also used to report flag results like overflow from arithmetic operations, or collision during blitting. Most instructions operate on these general registers. Since the available memory is roughly 4K, these 8-bit registers wouldn't be too useful as pointers. Instead, there is a 12-bit Index register that is used as the implicit address argument to memory-accessing instructions.

For flow control, the program counter needs 12 bits as well; the CHIP-8 is a von Neumann machine. Furthermore, it has CALL / RET instructions backed by a call-only stack (there is no argument passing or local variables).

Modeling the CPU's internal state

We can collect all of the registers described above into a single Haskell datatype. I have also added two 8-bit registers for the high and low byte of the current instruction, but in retrospect it would be enough to just store the high byte, since the low byte is coming from RAM exactly when we need to dispatch on it anyway. The extra phase register is to distinguish between execution phases such as fetching the first byte of the next instruction, or for instructions that are implemented in multiple clock cycles, like clearing the frame buffer (more on that below).

type Addr = Unsigned 12
type Reg = Index 16

data CPUState = CPUState
    { opHi, opLo :: Word8
    , pc, ptr :: Addr
    , registers :: Vec 16 Word8
    , stack :: Vec 24 Addr
    , sp :: Index 24
    , phase :: Phase
    , timer :: Word8
    , randomState :: Unsigned 9
    }
    

I implemented the random number generator as a 9-bit linear-feedback shift register, truncated to its lower 8 bits; this is because a maximal 8-bit LFSR wouldn't generate 0xFF.

lfsr :: Unsigned 9 -> Unsigned 9
lfsr s = (s `rotateR` 1) `xor` b4
  where
    b = fromIntegral $ complement . lsb $ s
    b4 = b `shiftL` 4
    

Input and output "pins"

Similar to how a real chip has various pins to interface with other parts, our CPU description will also have multiple inputs and outputs. The input consists of the data lines read from main memory and the framebuffer; the events coming from the keypad, and the keypad state; and the 60 Hz VBlank signal from the video generator. This latter signal is used to implement the timer register's countdown. The keypad's signals are fed into the CPU both as events and statefully; I've decided to do it this way so that only the peripheral interface needs to be changed to accomodate devices that are naturally either parallel (like a keypad matrix scanner) or serial (like a computer keyboard on a PS/2 connector).

type Key = Index 16
type KeypadState = Vec 16 Bool

data CPUIn = CPUIn
    { cpuInMem :: Word8
    , cpuInFB :: Bit
    , cpuInKeys :: KeypadState
    , cpuInKeyEvent :: Maybe (Bool, Key)
    , cpuInVBlank :: Bool
    }      
    

The output is even less surprising: there's an address line and a data out (write) line for main memory and the video framebuffer.

type VidX = Unsigned 6
type VidY = Unsigned 5

data CPUOut = CPUOut
    { cpuOutMemAddr :: Addr
    , cpuOutMemWrite :: Maybe Word8
    , cpuOutFBAddr :: (VidX, VidY)
    , cpuOutFBWrite :: Maybe Bit
    }
    

So, what is a CPU?

As far as CλaSH is concerned, the CPU is extensionally a circuit converting input signals to output signals, just like any other component:

extensionalCPU :: Signal dom CPUIn -> Signal dom CPUOut
    

The internal CPU state is of no concern at this level. Internally, we can implement the above as a Mealy machine with a state transition function that describes behaviour in any given single cycle:

intensionalCPU :: (CPUState, CPUIn) -> (CPUState, CPUOut)

extensionalCPU = mealy intenstionalCPU initialState
    

As far as a circuit is concerned, a clock cycle is a clock cycle is a clock cycle. If we want to do any kind of sequencing, for example to fetch two-byte instruction opcodes from the byte-indexed main memory in two steps, we need to know in intensionalCPU which step is next. This is why we have the phase field in CPUState, so we can read out what we need to do, and store what we want to do next. For example, in my current version the video framebuffer is bit-indexed (addressed by the 6-bit X and the 5-bit Y coordinate), and there is no DMA to take care of bulk writes; so to implement the instruction that clears the screen, we need to write low to all framebuffer addresses, one by one, from (0, 0) to (63, 31). This requires 2048 cycles, so we need to go through the Phase that clears (0, 0), to the one that clears (0, 1), all the way to (63, 31), before fetching the first byte of the next opcode to continue execution. Accordingly, one of the constructors of Phase stores the (x, y) coordinate of the next bit to clear, and we'll need to add some logic so that if phase = ClearFB (x, y), we emit (x, y) on the cpuOutFBAddr line and Just low on the cpuOutFBWrite line. Blitting proceeds similarly, with two sub-phases per phase: one to read the old value, and one to write back the new value (with the bitmap image xor'd to it)

data Phase
    = Init
    | Fetch1
    | Exec
    | StoreReg Reg
    | LoadReg Reg
    | ClearFB (VidX, VidY)
    | Draw DrawPhase (VidX, VidY) Nybble (Index 8)
    | WaitKeyPress Reg
    | WriteBCD Word8 (Index 3)      
    

So how should we write intensionalCPU? We could do it in direct style, i.e. something like

intensionalCPU (s0, CPUIn{..}) = case phase s of
    Fetch1 ->
        let s' = s{ opHi = cpuInMem, pc = succ $ pc s, phase = Exec }
            out = CPUOut{ cpuOutMemAddr = pc s', cpuOutMemWrite = Nothing
                        , cpuOutFBAddr = minBound, cpuOutFBWrite = Nothing
                        }
        in (s', out)
    WaitKeyPress reg ->
        let s' = case cpuInKeyEvent of
                Just (True, key) -> s{ registers = replace reg key (registers s), phase = Fetch1 }
                _ -> s
            out = CPUOut{ cpuOutMemAddr = pc s', cpuOutMemWrite = Nothing
                        , cpuOutFBAddr = minBound, cpuOutFBWrite = Nothing
                        }
        in (s', out)                   
    -- and lots of other cases as well, of course
  where
    s | cpuInVBlank = s0{ timer = fromMaybe 0 $ predIdx $ timer s0 }
      | otherwise = s0
    

If you think this is horrible and unreadable and unmaintainable, then yes! I agree! Which is why I've spent most of this RetroChallenge (when not fighting synthesizer crashes) thinking about nicer ways of writing this.

This post is getting long, let's end on this note here. Next time, I am going to explain how far I've gotten so far in this quest for nicely readable, composable descriptions of CPUs.

September 23, 2018 09:50 PM

Edward Z. Yang

HIW’18: Let’s Go Mainstream with Eta!

My name is Rahul Muttineni, CTO of TypeLead, working on building services around a language named Eta. To get started, I'll give an overview of how the project started, and where it is now.

It started as a HSOC project. It was called GHCVM; back then we had plans of making it both on JVM and CLR... we don't think about CLR anymore. I was mentored by Edward Kmett. We got pretty good response on this, so Jo and I decided to take the risk and work on this full time.

Big thanks to the GHC team, really good work. We've worked with the codebase for two years, and the more and more we work with it, we see how much awesome stuff there is. I've learned a lot by working with the code.

What is Eta? Eta is a fork of GHC. During the GSOC project, it started off as a Haskell program that used the GHC API. Midway in the program, I found that there were certain things that I wanted to do that I couldn't do, and I spent 3-4 days setting up a fork. I'll talk about what those limitations are. Like Haskell, it's a ... language, but the key difference is that it runs on the JVM. That is its own set of challenges, primarily with respect to tail calls. The nice thing about Eta is that it runs on the JVM, and it can run a good chunk of projects just like that. lens... recently, in the last month, we got Yesod working... it's in good shape. The next really great type of Eta is the strongly typed FFI. That works really well with the subtyping in JVM. A good chunk of the talk is about how we got that working. One of the main focuses of Eta is to be focused on industrial use. GHC is focused on industrial use, and research, both. There's a tension between the two... the nice thing we have for Eta is we don't have to face that tension; it's easy to make decisions on how to add new features, because will it help companies? If it is yes, otherwise we don't. (SPJ: That can be a hard question to answer!)

Haskell: Avoid success at all costs. We're not going to sacrifice core principles of language for benefit. Pursue success, at minimum cost. We want to make it successful as much as possible, but we want to make as little sacrifice as possible. That will be a little tricky...

What is Eta? What language features does it support? It started off as a fork of GHC 7.10.3. All extensions that work there, work with Eta as well. The only thing was TemplateHaskell and QuasiQuotes didn't work for a long time. We got it working 3-4 months ago. Biggest change is JavaFFI. GHC 7.10.3 is MINUS C FFI. We could have supported it: Java has JNI, but we tried to avoid it because we didn't want to make platform specific bindings to all the libbraries.

Joe backported a bunch of GHC 8 features: StrictData, ApplicativeDo, OverloadedLabels. Backpack was got recently. There's a very particular reason we had to do it: it has to do with the fact that we don't have green threads by default, and we wanted to give the user a choice of threaded runtime versus blocking runtime.

The compiler? It's a fork of GHC, so all the compiler passes are the same. We just chopped off everything after STG; e.g., C-- is gone. We generate bytecode from STG. We don't do any optimizations right now, and won't need to for some fine. We don't have to because in JVM, it's JIT compiled, so we don't have to optimize as much since JVM will remove a lot of the code that's not used anyway. And the driver: GHC generates object files... we decided to use JAR files. They're just zip files that package up a bunch of class files that store Java bytecodes. We also added one more mode for Uberjars. These are JAR files that are packaged up into one giant package.

I'll talk a little bit about how we implemented the REPL; template haskell. It works through the external-interpreter architecture. In GHC that's called iserv: the process, what it does, is handles running the code. So the compiler will still do the typechecking and everything, but once it's done with all that stuff, GHC will generate, a specific bytecode set, for interpreting Haskell efficiently. Because we already generated JVM bytecodes. We didn't need that custom bytecode set; we just compile with optimizations off; that gives us JVM bytecodes, then we send it to the external process, load it up, and execute them. Implementing the REPL is pretty easy how to get all this working together. JVM has a mechanism called classloading, which is very flexible. You can download bytecodes from the network, get code an runtime. Once you load the class, it's statically compiled code, it's optimized the same, etc.

The build tool we use is Etlas. We didn't want to move too far off of GHC, we stuck with Cabal. At the point we started using it, we forked off of Cabal 2.0. Main difference is that it lets you manage Eta versions. Etlas is almost like Stack, but it's much much closer to Cabal. We took the nice features of Stack and added them to Cabal. The other thing is that it does patch management. What we've been finding as we add more features and backport, Eta is not exactly GHC 7.10, nor is it GHC 8.0, it's a weird intermediate state, so certain packages that won't exactly compile without small changes, so we needed some system to apply those changes before we actually run the build. So we setup a GitHub repository that stores all the patch files. What etlas will do, it will get you the most recent set of patches. Then if you install a package, lens or something, it will download lens, apply the patch, and then it will build. Just recently, we were using base 4.8, and recently we upgraded to base 4.11. But we couldn't update to the new Generics infrastructure, because it slowed down compile times. So there were a bunch of packages that would check if they were GHC 8... and then use new generics. So we had to do a bunch of patching for that. But that's the kind of stuff we have to deal with.

The title of this talk is lets go mainstream with eta. I want to take a moment and say, what does that mean? "The ideas, attitudes, or activities that are shared by most people and regarded as normal or conventional." So at what point does a programming language become consdiered normal or conventional? It has to be used a big company, solve a big real world problem, and people have to believe it works. That's a very complicated question, multifaceted, one part of that answer is, it should make it easier to solve real world problems easier than the status quo. Take for example PHP. PHP came out when there was nothing better to program dynamic web applications. It had just the minimum features required to make it useful to build these. Now everyone here is asking the question: Haskell clearly solves a lot of problems better than the status quo. So why isn't it moving forward? That's a big question, I'm going to talk about how we're approaching it.

The strategy we're using internally, is we put on a "Big Company Hat"; we pretend we're a big company with a lot of employees, millions or billions of lines, and try to figure out what problems they'll face. Some problems are crazy long build times, when trying to build huge software; dynamic where you have to make sure junior developers get up to speed... etc. That's couple to get this conversation started.

After thinking about this a long time, we boiled it down to three basic principles, how we will develop Eta.

1. User Experience
2. Performance
3. Safety

User Experience is mainly, an emotional thing, how you feel when you use Eta technology, how you interact with it, what you feel when you get an error, psychologically. When something has good UX, we feel good. That's a very subjective thing, it can vary between different people, we have to figure out a way to standardize / make it universal. Something we forget as software and tool developers, the person developing the software is human. If they get errors persistently over time, they'll get frustrated. Machines will do what you tell them over and over again.

So what have we done in Eta to concern? We've done something very recently; it's not in master yet. Jo and I spent a week refactoring the codebase to refactor the error reporting part of the typechecker. It stores a list of strings; internally in GHC, there's a pretty printed data type, a list of those. The problem is we can't do postprocessing on that. So, what Jo did was made a giant data type with three hundred data constructors, one for every error message in GHC. That refactor to a week (SPJ: only a week?!) How it is now, it's decoupled, now you have, instead of storing in the typechecking monad, storing strings, you store a data type that stores the relevant data to print out that error message. And then at the final point, you can traverse the data type; based on the presence of other errors, you can decide what to do. Now it's pattern matching on certain error patterns and reporting them nicely. This is one example. We talked about simple errors: refactoring, adding an argument, changing the type, that's one of the most common errors you'll get working with Haskell. So we focused on those first. This shows an example of a type error... 'checker', it's an IO action.

GHC would tell you, couldn't match Int -> IO () with IO (). The problem is, for people who don't know how the typechecker works, they won't be able to understand what the typechecker is doing: going argument by argument. Because of the refactor we've done, it was easy to pattern match on this particular case, and say, hey, if the user forgot to put an argument, you can print out an error message of this form. You print an argument is missing, you highlight. (SM: You might have been missing the first argument, in this case!) That's true. It's tricky; sometimes the suggestion you give, might not. We don't tell people what they did exactly wrong, because we don't know. This is not a perfect thing, but we try to give the best suggestion that we can. And an important feature of this, most of how we decdied this layout, we studied languages like Elm and Purescript, which have done good work in this error. PureScript and Elm both, what they do, for a certain type of error, and you're not sure what to do... e.g., our info is not complete, they can go to a particular link and see other things that could have happened. So we don't have to flood the user with every suggestion, we just have to show the user what probably is the cause for it. And if it's a tricky case, not what we posted, in the link, we'll have the case as well.

(BG: There's other information that might be relevant; expanding type synonyms, etc. Do you have this info?) We're still thinking about that. Probably we'll have extra flags and stuff. Eventually, we'll have a mode that prints out JSON for IDEs, then it's easier to parse on the IDE side. (BG: Incidentally, there's a ticket, a student working with Richard, trying to figure out smoething similar).

Another aspect of UX is we added the REPL. Tried to simplify the entry point, try to make it easy. You want types, kinds, and where to find out more information. This is a statically typed language: you always hhave to be thinking about types. So we :set +t: always print out the types when you print things. One more thing, one of the former Scala engineers, has been learning Haskell, and he made a critique of one aspect of the REPL experience. f is a function of two argumets. In a second statement of the REPL, I applied 1. Find instance, show instance, for a goes to a. He said that... no show instance found, just say that this is a function, and you can't print it. That's a change we did. This was very easy for us to do.

Performance: it can mean many things. We're talking about fast developer feedback loop. Compile time and develop time, reducing that feedback loop. Some work we've done in this direction is reproducible builds. As of now, we have bit-for-bit reproducibility in Eta. That amounted to... nikita already did lots of work on reproducibility, he made HAskell interface reproducible; but the last mile of bit for bit is hard, there's many places. For our code generator, it was a lot simpler, we didn't have to do as much. It was 20 lines of code to make it deterministic. The main source of nondeterminism in GHC is the Unique data type, that changes between different runs depending on environment. What we did, was we added a counter. We used to print the uniques in the Java class name; that will make it nondeterministic. So we made a counter: the order in which the bindings make it to STG is the same.

GHCi is known to take up lots of memory, esp. with IDE. Simon Marlow has a bunch of fixes to that; we also backported those.

Another aspect of performance is the actual runtime performance. We're on the JVM, that puts us at a huge disadvantage. We don't have control over many things. The runtime system... this is Java. It's OO, so the runtime system is implemented in Java. We setup a hierarchy for values, that are defined in Eta. We have Closure, it's a class, parent class of all values, thunks, WNF. The Closure class has two methods. evaluate, evaluate to WHNF, and enter will actually enter... it's similar to GHC runtime system. The initial version was modeled exactly after GHC, except for tail calls. The terminology is similar. It's primarily used when you do the body of function. The main subclasses of Closure are Thunk and Value. Value will be the parent class, of things like functions, partiallly applied functions, and data constructors. Thunk will be the superclass of things like CAFs, single entry thunks, and updatable thunks. CAFs don't have free variables, so there's a special case for that, and you create a blackholing entry every time, to avoid two threads evaluating the same thunk. UpdatableThunk pushes an update frame, when it's finished evaluating, it will update the thunk to point to the newly computed value. And SingleEntryThunk, they're evaluated only once, so you can just evaluate it directly without pushing an update frame. This terminology is borrowed from GHC as well.

VAlues: DataCon, Function and PAPs. In the early days, and even now, every function call that was a tail call, is just a method call. This is the only way to make it remotely efficient. (More on stack soon). For static tail recursive calls: singly recursive or mutually recursive, they get compiled to loops. In most cases, they get a nice tight loop. In the mutual case, what will happen is, we collect all of the SCC, and we make one giant method that goes into a loop. Let's say you're in the even/odd example, what will happen is, when even calls odd, there's a variable called target, an integer. Even will be assigned 0, odd is assigned 1, so then you set 1 and restart. (BG: Do you always have unfoldings available for functions you compiled?) This is mutually recursive functions defined in the same module. (SPJ: They might have very different type arguments.) We cat all the arguments into one. The main problem with this argument, is parsers generated with Happy and Alex, we hit limits. (BG: Crash?) Not stack blowup. JVM has method size limit, so you can only have 65000 bytecodes. That's Eta compiled with itself. That's the only thing that's preventing us from using Eta with Eta. But all you need to do is split method into smaller chunks.

So how do we handle tail calls? When we know it , tail recursive, let's say you don't. Let's say you're using CPS. It's so common in Haskell, any fast parser uses CPS. In early days, Aeson would just blow the stack, it was pretty bad. So, we explored trampolining by default, and it was just awful, it was slow, super slow. What we did is turn it off, and let stack blow up. We found a better solution. The JVM has... the only way to unwind the stack is throwing an exception, or returning, and keep on returning until you return all the way down. It turns out, with exceptions, you can turn off the feature that captures the stack trace: that's the most expensive part of an exception. So we have a general exception. So this trampoline mechanism is optional. So, what we do, we have a function 'trampoline :: a -> a', runtime primitive, what it does is activates a boolean in the context which says, I'm going to trampoline now, and it activates a codepath that turns a counter, and once you reach a certain number, which is configurable, it will unwind the stack, and then continue where it needed to go. Our limit is 400, and then we unwind. It used to be in 1000s, but with Happy and Alex, we needed a smaller number. (BG: Inside that context, how much does it cost? But observably, it's faster. A couple months ago, we got PureScript to work in Eta, and it wasn't bad by default?) (SPJ: So you could turn it on by default: all you're doing is counting.) The counting is how we know how big the stack is. In your main function, you could call trampolineIO, and trampoline your whole program. (SPJ: Maybe it's low overhead, and you can do it all the time.) If it's low, we will do it. (How do you resume? Once you raise the exception, what do you store?) The counter happens at the entry point, and it's guarded bby the boolean. So, that, if the limit is exceeded, it will call another function that takes the context. So we store all the arguments in a context variable that gets passed to every eta function. We stash all the arguments into a function that has the state, then wjhen it unwinds, marked by this function, it will call that, with that function and those arguments.

As I mentioned, it's guarded by a boolean. JVM has an optimization, where it observes the boolean is true for a lot of times, it won't even compile that branch in the native code. So if you don't use trampolining, it doesn't affect you at all; the code for the counter will just not be there.

One nice thing I like about Eta is that you actually get stack traces for exceptions. This is because, to get good perf for Eta, you have to implement most primitives on JVM stack. This is a sample stack. You have a schedule loop, and you hare evaluting some IO acttion. applyV/applyN, these are partial applications. Execute an IO action. And another nice part, we've tried to encode it close to the original name. So you can tell this fucntion call happened in statistics.Regression, rnfAll. If you see, you notice there are line numbers. This is not perfect, and we can definitely make it better later... GHC gives you a lot of debugging info at STG time, but because the JVM doesn't have much flexibility, we can only attach one line number to code, so we have to discard all that info. This will get better; we'll stash that debug information in the classfile itself, and then access it and render a better stack trace. (BG: This is Source Notes?) Yeah.

Concurrency: One nice part is, it's nice or not. If you're evaluating a long chain of thunks, you're going to blow the stack. This happily coincides with GHC also having a space leak. Neil Mitchell wrote a blog post about how to detect space leaks: restrict stack size and then figure out which thunk was being evaluated. If you see a stack trace like this, and you see a huge chain of evaluates, in a long chain, you probably have a space leak.

How do I do interop? The way we did interop was, made a thing called the Java monad. IT's supposed to give you the experience of programming JAva. The basic implementation is inspired from IO monad. Object# c is "this", the object that is being threaded through. Because of this encoding, you get the Java experience: you can call dot on the Java object. It's almost like working with Java inside. The argument is called... that's the type constructor that forced us to fork, instead of use the API. You can't declare primitive types in the API. And we had to introduce a new low level representation. Declare wrapper types, wrapping the iterable interface in Java. We've stolen better syntax, which were type applications... resolve it somehow. I'm declaring an Eta type that wraps a JAva type, @java.lang.Iterable.

You use the java function to run the Java monad. All of these have to be imported. newArrayList, newInteger, but we brought some combinators, that let you call methods. It owrked out with the monad. This is sample code that does the same thing as Java code. it just uses standard monadic combinators. If it's a fixed c, it's an instance.

You can use Eta as a better JAva, with referential transparency! Unlike Kotlin or Scala.

How do we handle subtyping? We define uilt in type families. We have a typeclass named extends. Any time you declare a function that takes a given class and any subtype of that class, you can, instead of actually subtyping, we do it with constraints. Extends' takes the info from Inherits and figures it out. You can use the dot operator on anything that is a subclass of Iterator. We had to extend the typechecker just a little bit: a lot of times the type gets stuck in the form Extends' (List JSTring) (List a) where a is unconstrained.

Imports are tiresome, so we're setting up direct Java Interop; actually use JAva reflection to get info class files, and generate imports. "import java java.lang.Math" works, but doesn't scale. Biggest priority for the rest of the year is Java interop, really good IDE support, documentation, language extensions: UnboxedSums, TypeApplications, DerivingVia, QuantifiedConstraints. We have some new language extensions in mind, AnonymousRecords, RowTypePolymorphism... We'll see how that goes.

I was thinking about ways... we work on the same codebase, how to collaborate? We're interested in compile performance, support for unbboxed sums. Worker wrapper has some glitch, and no one got around to fixing it. At some point, maybe not any time soon, that and mutable fields. Pretty important for us. (BG: Do unboxed sums get a lot of usage? Why unboxed sums? Does Eta code make a lot of use?) No. But a lot of people on JVM are annoyed that Maybe is boxed all the time. But if you have unboxed sums, you can represent it as null. (SPJ: Or you can say, just box it, and you won't notice it. If it's fast enough all the time, focus on what's going to make a difference.)

Q: Did you consider using Graal (it's a new virtual machine that supports partial evaluation and partial escape analysis, good for functional languages)?

A: We have looked into it, it's not completely there yet to use, and we're not sure if it's something we can invest time with. We're keeping up with it. (BG: But you lose the JVM!) That's what's preventing us from going there. Maybe if it gets integrated into a mainline VN we might look at it. (Mainline Java is planning to integrate Graal)

Q: (SM) Are you keeping the fork up to date with master GHC?

A: One thing that is out of bounds for us, and for a long time, is all the dependent Haskell work. Everything else, we keep up. If there's any nice bugfixes... (SM: So you're selectively backporting).

Q: (BG) Have you considered unforking.

A: Not yet, no.

by Edward Z. Yang at September 23, 2018 03:02 PM

September 22, 2018

ERDI Gergo

Back in the game!

For most of this week, it seemed I will have to throw in the towel. As I mentioned in my previous entry last Saturday, I ran into what at first seemed like a CλaSH bug. However, further investigation showed that the error message was actually pointing at an internal bug in the Xilinx ISE synthesizer. The same generated VHDL didn't cause any problems when fed into the Yosys open source synthesizer, Altera Quartus, or the newer version of Xilinx Vivado. But the Papilio Pro I'm using is based on the Spartan 6 FPGA, which is not supported by the newer Xilinx tools, so I am stuck with ISE 14.7 from 2013. So the conclusion is, just like all other closed-source proprietary software from FPGA vendors, the Xilinx ISE is simply a piece of shit that falls over under its own weight on perfectly valid VHDL.

I was thinking of ordering a new FPGA board, but I only have until next Wednesday to finish this (I won't be able to put in any work on the last Retrochallenge weekend), so it's not even a given it would get here in time. Also, I'd like to do a bit more research on what board I should get -- on one hand, both Altera and Xilinx have nice, more modern dev boards with good IO ports for my retro-computing-oriented needs, but on the other hand, it feels a bit like throwing good money after bad, since these would still be programmed with proprietary shitty software, with no way forward when (not if!) they break.

Then there's Lattice's ICE40 line which is fully supported by the open source toolchain IceStorm, but the largest ICE40 is still quite small compared to the Spartan 7 or the Cyclone V series; not to mention that even the nicest ICE40 board I could find doesn't have a USB connector on board, so you have to play around with an Arduino and plug jumper wires into this weird connector to get anything working. Also, while I'm ranting, of course the Lattice ICE40 open source toolchain is not from Lattice themselves; instead, its bitstream format had to be reverse-engineered by awesome free software hackers

So anyway, I had a perfectly functioning board betrayed by its software toolchain. I tried some desparate ideas like generating Verilog instead of VHDL or getting rid of the unguarded block statements, but nothing made any difference. Then Thursday night I had an even wilder idea. If the Xilinx ISE is crashing because the generated VHDL is triggering some weird corner case in the synthesizer, then maybe using the same ISE version, but changing the target FPGA model, would get over the hurdle? And that's when I remembered I still have my first ever FPGA board: the Papilio One based on the Spartan 3E. Luckily, the Spartan 3-series is also supported by the 14 series ISE, so the same toolchain can serve both boards.

On Friday morning, I did the necessary changes to my code to target the Papilio One. The clock generator is different between the models, so I needed to replace that; the other difference was that the Spartan 3 doesn't seem to have wide enough blocks for 64-bit arithmetic. This shouldn't be a problem for the CHIP-8, but CλaSH generates code that converts everything into 64 bits. I initially overcame that by post-processing CλaSH's output with sed, but then I discovered that there is a flag -fclash-intwidth to set that properly.

With these changes, I was able to get it through the Xilinx ISE's synthesizer, and all the way through the rest of the pipeline! As before, the code is on GitHub.

<object height="350" width="425"><param name="movie" value="http://www.youtube.com/v/eqpMFACw-B4"/><param name="wmode" value="transparent"/><embed height="350" src="http://www.youtube.com/v/eqpMFACw-B4" type="application/x-shockwave-flash" width="425" wmode="transparent"></embed></object>

And with this, I am where I was supposed to be a week ago at half-time. I probably won't have time to work on this project next weekend since we'll be travelling; this looks like a good time to take inventory of the project.

  • I am very happy with how the video and keyboard peripheral interfaces turned out; the CλaSH code is nice and clean.
  • I still need to write a blog post about the design I came up with for implementing the CPU. I'm convinced it should scale to more complex processors; but of course the proof of that pudding will be in implementing a real retro-CPU like a 6502 or a Z80.
  • The font ROM is not hooked up yet; I plan to finish that tomorrow.
  • The plan was to get it working first, and make it more performant later. I'm afraid I won't have time before the RetroChallenge finishes to implement improvements. The biggest deficiency here is that the framebuffer is accessed one bit at a time, so clearing the screen (a single opcode in CHIP-8!) takes 64⨯32 = 2048 cycles!
  • The signal-less high-level simulation makes debugging the CPU implementation very convenient and fast. Being able to run the CHIP-8 machine in real-time, with interactive graphics and input, is immensely satisfying.
  • I prefer the code I was able to write in CλaSH, when compared to Kansas Lava. Of course, I don't know how much of that is simply because this is the second time I was implementing these circuits.
  • There's a lot to be improved in CλaSH itself. Significant improvements to compilation time are already coming, which will be welcome given that even this tiny CHIP-8 circuit is now taking about 5 minutes to compile; this issue is exacerbated by the fact that compilation cannot use multiple cores. The other problem is that CλaSH generates very inefficient HDL, putting big pressure on the vendor-specific synthesis tools. As we've seen, this pressure can be too big for crappy software like the old version of the Xilinx ISE I am forced to use with my FPGA.
  • Writing these posts takes a lot of time! I love reading the posts of other RetroChallenge entrants, but there is no way I could have written more frequent updates. I wouldn't have had time to do the actual work then!

September 22, 2018 07:10 PM

September 20, 2018

FP Complete

Deploying Postgres based Yesod web application to Kubernetes using Helm

Yesod is one of the most popular web frameworks in the Haskell land. This post will explore creating a sample Postgres based Yesod web application and then deploying it to Kubernetes cluster. We will create a Helm chart for doing our kubernetes release. Note that the entire source lives here:

by Sibi Prabakaran at September 20, 2018 10:45 PM

September 18, 2018

Chris Smith 2

CodeWorld Update — September 17, 2018

It’s been a couple months, so here’s some of the latest news about CodeWorld.

First of all, if you’re reading this and will be at ICFP, please consider coming to dinner on Monday night, Sep 24, to talk with other interested people about Haskell (and Haskell-like languages) in K-12 education. Please RSVP here as soon as you can.

Platform

There have been a number of changes made to the CodeWorld platform lately.

Classes

CodeWorld is being taught in quite a few places now!

  • In Louisiana, a pilot program is continuing to teach computational thinking with CodeWorld, organized by a group at LSU. This program reaches 350 students, including many schools and teachers who were trained over the summer.
  • In a separate effort in Louisiana, middle school students have seen a brief introduction to CodeWorld as part of a survey course that also includes p5.js, Arduino, and web programming.
  • In California, Brooklyn Cook is teaching CodeWorld to a new class, keeping it alive there even after my moving to New York.
  • Together with a coworker and a local teacher, I’m leading a class at The Clinton School in New York. This is CodeWorld’s first entry into the New York area. Schools here start quite a bit later in the year, so we’ve just had our first class today.

Curriculum

I’ve been working on updating the Guide to match our current best understanding of how to teach CodeWorld. Every time I do this, though, it gets quite a lot longer. My plan is to try to keep up with my own class this school year, so I’ll have a good chunk of the updates done by the end of the year. I’ve also swapped the Guide to use markdeep, a powerful variant of markdown that makes for a surprisingly complete publishing platform. I’ve extended markdeep locally with some features like collapsible notes that can be expanded for more information. Just seeing the results makes me excited to be writing the guide again!

Fernando Alegre at Louisiana State University is also building a separate curriculum focused on 9th grade, and with different elements and API entry points involved.

by Chris Smith at September 18, 2018 01:04 AM

September 15, 2018

ERDI Gergo

Very high-level simulation of a CλaSH CPU

Initially, I wanted to talk this week about how I plan to structure the CλaSH description of the CHIP-8 CPU. However, I'm postponing that for now, because I ran into what seems like a CλaSH bug, and I want to see my design run on real hardware before I describe it in too much detail. So instead, here's a post on how I am testing in software.

CPUs as Mealy machines

After stripping away all the nice abstractions that I am using in my description of the CPU, what remains is a Mealy machine, which simply means it is described by a state transition and output function s -> i -> (s, o). If that looks familiar, that is not a coincidence: this is, of course, just one argument flip away from the Kleisli category of the State s monad. Just think of it as being either this or that, depending on which one you have more intuition about. A lot more on this in my upcoming blogpost.

My CHIP-8 CPU is currently described by a Mealy machine over these types:

data CPUIn = CPUIn
    { cpuInMem :: Word8
    , cpuInFB :: Bit
    , cpuInKeys :: KeypadState
    , cpuInKeyEvent :: Maybe (Bool, Key)
    , cpuInVBlank :: Bool
    }

data Phase
    = Init
    | Fetch1
    | Exec
    | StoreReg Reg
    | LoadReg Reg
    | ClearFB (VidX, VidY)
    | Draw DrawPhase (VidX, VidY) Nybble (Index 8)
    | WaitKeyPress Reg

data CPUState = CPUState
    { opHi, opLo :: Word8
    , pc, ptr :: Addr
    , registers :: Vec 16 Word8
    , stack :: Vec 24 Addr
    , sp :: Index 24
    , phase :: Phase
    , timer :: Word8
    }

data CPUOut = CPUOut
    { cpuOutMemAddr :: Addr
    , cpuOutMemWrite :: Maybe Word8
    , cpuOutFBAddr :: (VidX, VidY)
    , cpuOutFBWrite :: Maybe Bit
    }        

cpu :: CPUIn -> State CPUState CPUOut
      

Running the CPU directly

Note that all the types involved are pure: signal inputs are turned into pure input by CλaSH's mealy function, and the pure output is similarly turned into a signal output. But what if we didn't use mealy, and ran cpu directly, completely sidestepping CλaSH, yet still running the exact same implementation?

That is exactly what I am doing for testing the CPU. By running its Mealy function directly, I can feed it a CPUIn and consume its CPUOut result while interacting with the world — completely outside the simulation! The main structure of the code that implements the above looks like this:

stateful :: (MonadIO m) => s -> (i -> State s o) -> IO (m i -> (o -> m a) -> m a)
stateful s0 step = do
    state <- newIORef s0
    return $ \mkInput applyOutput -> do
        inp <- mkInput
        out <- liftIO $ do
            s <- readIORef state
            let (out, s') = runState (step inp) s
            writeIORef state s'
            return out
        applyOutput out
      

Hooking it up to SDL

I hooked up the main RAM and the framebuffer signals to IOArrays, and wrote some code that renders the framebuffer's contents into an SDL surface and translates keypress events. And, voilà: you can run the CHIP-8 computer, interactively, even allowing you to use good old trace-based debugging (which is thankfully removed by CλaSH during VHDL generation so can even leave them in). The below screencap shows this in action: :main is run from clashi and starts the interactive SDL program, with no Signal types involved.

<object height="350" width="425"><param name="movie" value="http://www.youtube.com/v/ZkxcBDMonvs"/><param name="wmode" value="transparent"/><embed height="350" src="http://www.youtube.com/v/ZkxcBDMonvs" type="application/x-shockwave-flash" width="425" wmode="transparent"></embed></object>

September 15, 2018 07:24 PM

Chris Smith 2

The ups and downs of STEM standards

Last week, in a widely hailed move, California adopted model K-12 computer science standards. Headlines have described this move as “California embraces computer science in its schools”, or “California board of education expands access to computer science”. For the last seven years of my life, I’ve volunteered much of my life to computer science at the middle school level. The tools I’ve build are used in a schools across the country by many teachers to reach hundreds of students, and I’m proud of this. You might think I’m thrilled by this news.

You would be wrong, though.

I am still hopeful that this works out for the best. It might raise enough awareness, and motivate and fund enough school districts, to offset the harm of the standards themselves. But the move to quickly adopt standards for K-12 computer science is deeply misguided, and I believe we will likely come to regret the push for early standardization.

<figure><figcaption>Girls learning computer science using Scratch (source)</figcaption></figure>

This is unusual of me to say. The push for updated standards like the Common Core, NGSS, etc., has been a huge part of the education reform movement over the past decade, and it’s admittedly been largely successful. I certainly don’t align myself with those naysayers who see the Common Core as government overreach or argue that children need more drills on long division. But computer science is different, in a few ways.

Computer science is a young field of knowledge.

<figure><figcaption>The first computer, only 70 years ago</figcaption></figure>

It might seem like computer science has been around forever, but it’s pretty new by any measure. The first computers themselves were built barely 70 years ago — barely the blink of an eye compared to the storied millenia of mathematics, language, science, and history. And yet even that 70 years is misleading. Software in 1948 was a very different beast from what it looks like today. It doesn’t look like that pace of change is slowing. If anything, the advent of new fundamental ways of looking at computing is proceeding at breakneck speed.

Computer science shows telltale signs of immaturity. The common university computer science curriculum looks like a list of all the things we thought computer programmers needed to do 30 years ago. There are courses in writing operating systems, implementing compilers, assembly language, databases, network programming, graphics, and artificial intelligence. Compare this to mathematics or science, and you’ll find a quite different story, with a mature field organized around key ideas, not tasks.

If CS is still young, CS in K-12 education is in its infancy.

We aren’t talking about computer science, though, but about computer science education. And that is far, far newer and less certain than the topic as a whole. The current push for computer science education is maybe 15 years old. There have been older generations of the effort, to be sure, but without a lot of success to show for it.

<figure><figcaption>Scratch, a language designed for early computer science</figcaption></figure>

The current thinking in computer science education, led by Scratch and Hour of Code, is that CS can be made accessible to younger children with a drag-and-drop tools and game-like learning environments. Yet most success stories come without real learning objectives, much less authentic transfer of skills. Researchers often measure interest instead of outcomes, and on success or failure rather than building a theory of how students make meaning and learn.

The standards themselves show telltale signs of this. If you compare with the Common Core, the first and most striking difference is how much of California’s new CS standards are about auxiliary concerns — they talk a lot about making sure students know to respect copyright and can talk about the social implications of computing (something that is important, but belongs in a civics curriculum!), but fall very short in enumerating the skills students need to build toward robust technical competency. There’s a reason for that: we don’t really understand those early technical skills even remotely well enough to say what they are, much less where a student should be at which grade levels!

Computer science is a mess of different languages and tools.

A third challenge is that the professional practice of computer programming is a bewildering mixture of different notations, languages, libraries, paradigms, and tools. Great debates can be found, both in professional practice and in the education space, about the choice of tools and notations. Little if anything is known about how well children transfer expertise in one tool (especially drag-and-drop languages, for example) to others, and the early hints we do have don’t look so promising.

<figure></figure>

Standardization implies that we’ve converged on some consensus, and it’s time to get everyone on the same page. In computer science today, what page is that? By reading the standards, one can only conclude that the page we’re aiming at is a very shallow surface understanding of technical content, in an effort to be as vague as possible about what that content might be.

Computational thinking is still poorly defined.

<figure></figure>

Finally, it’s important to look back at why we’re doing this. Not every student will develop computer software for a living. But we have taken as an article of faith (and I agree with this wholeheartedly) that easy and ubiquitous computation has changed the world, creating new opportunities for learning, and new ways of thinking and understanding. These are important not just for computer programmers, but for educated citizens in the world at large.

If we believe this, though, why does our computer science education, even in elementary school, look so much like the profession of software engineering? Why are we using languages that either are built for industry (like Python, and JavaScript, and later Java), or mimic their structure and organization (like Scratch or Hour of Code)? There’s been much debate in recent years over how we define computational thinking in a way that keeps faith with its meaning as a universal skill. A great answer is that it’s about using decomposition, abstraction, and modeling to tackle the kinds of enormously complex tasks that arise when the grunt work of computation becomes trivial. Today’s standards don’t reflect that answer.

Why not standardize?

One could ask, even if these aren’t the best standards, why not have standards? Even before adoption, my colleagues in California have already been asked The Question. “Is your activity aligned with the proposed CS standards?” If the standards talked about syntax, this question would exclude using block-based languages. They don’t, though, because there are powerful groups working on block-based languages. This is a huge gap, since learning to be creative in formal notations is a huge part of what students stand to gain from learning computer science. The standards do talk about loops and mutating variables, so this question makes it harder to justify functional programming — despite the fact that Bootstrap, a curriculum based on functional programming, shows the best research evidence I’ve seen of transfer learning between computer science and mathematics.

Misuse of standards and why it matters

There’s an even bigger problem: computer science is an inherently creative field, and the way standards are used in STEM stands in the way of students’ ability to create.

Maybe you’ve decided to do some weight-lifting. You might join a gym and try a circuit on the weight machines. Big mistake, say almost all experts! Instead, they advise you to use free weights. Weight machines isolate and develop a small set of major muscles. But lifting free weights also builds a bunch of little muscles that you need for balance and versatility.

<figure><figcaption>The wrong way to start strength training.</figcaption></figure>

In a very similar way, building interesting and complex things in computer science develops a huge number of small skills, without which you might pass an exam, but you will struggle to build new things on your own. Standards are like the major muscles: if you are missing one in your training routine, it’s worth fixing. But it’s not sufficient to isolate just the standards, and train each one in isolation. There’s a whole second tier of skills that, while each one may not be critical, leaves students in a precarious position if they don’t pick up any!

Unfortunately, the current educational climate is about lessons carefully aligned to standards; the educational equivalent of weight machines. When they learn to read, students read a selection of books that give them a broad exposure to examples of literary value. But almost everywhere else, teachers are expected to choose resources, tools, and curriculum that’s stripped down to spend time only on the specific skills mentioned in the standards document. This laser-like focus on specific standards doesn’t do students any goals if we want them to apply the content independently and creatively!

If not standards, then what?

The push for California to adopt computer science standards was supported by most of the CS education community. I’d suggest this was not at all about a feeling that there’s too little standardization! Instead, it’s just because issuing standards is what the board of education does to encourage things like CS education. It was about recognizing the need for CS, not controlling the content.

But standards don’t fix budget problems. They don’t fix teacher education. And they don’t replace high-quality curriculum. Instead of pushing for the state to declare what teachers should be doing about computer science, I much prefer to help teachers do what they already know is good for their students.

by Chris Smith at September 15, 2018 05:03 AM

September 13, 2018

Neil Mitchell

Review of Apple Watch (series 2)

Summary: I like mine.

I've worn a watch since I was 10, starting with a Casio F-91W, replacing it with an identical model about seven times over the years. Last year the strap broke (it's almost always the strap that breaks), and I made the decision to buy an Apple Watch. I'm very happy with my Apple Watch (series 2, 38mm).

What I use it for

The main things I use my watch for are:

  • Alarms and timers, often using Siri to set them. If you treat the voice interface like a bad command line it works well - if you say "Add an alarm at 4pm" and you had an alarm at 4pm yesterday, it just shows you the alarm but doesn't enable it. Instead you have to say "Set alarm at 4pm". If you say "Set alarm at 4:10pm" the odds of getting an alarm at 10pm are quite high.
  • Receiving notifications, email, texts, Slack messages, phone calls. When you lift your arm you get a quick preview of the message, which is enough to decide whether it's important (take out the phone), or can happily be ignored.
  • Sleep tracking, via the Sleepwatch app. It's an awesome app that tracks your sleep showing trends.
  • Paying for things via the ApplePay. Nowadays I'm on the verge of not shopping at places that don't take ApplePay. It's more secure than contactless, works everywhere contactless works, has a higher limit, and is incredibly convenient. It can also swipe through multiple credit cards. Easy and seamless.

What I wish was better

There are other features the watch offers that I was hoping to use, but for various reasons haven't worked out.

  • I am terrible at navigation, and wanted to use Google Maps on my watch, particularly while cycling. Unfortunately, there is no Google Maps app for the watch, and the Apple Maps one is even less useful than normal Apple Maps. There is a recurrent bug where it loses the map display and just displays a checkered background - which can be fixed by some complex steps including wiping the watch and reinstalling. Part of the reason for buying this watch was for navigation, so I hope this gets resolved eventually.
  • I wanted to quickly and easily track train departures on the move. Unfortunately the National Rail train time app is useless - it omits the time the train is leaving, merely saying "On time" or not. As a consequence you have to memorise the timetable, plus believe it has refreshed and isn't just showing stale information. All in all, impressively close, and totally useless.
  • The actual display of the watch is adequate - it takes a noticeable pause to display the watch face (sub-second), but compared to my Casio, it's not always available. I like actual seconds on my watch, which limits me to exactly one digital watch face. I can't believe "knowing the precise time" is such a niche feature on a watch.
  • You can't hide apps from the watch that you don't use, which means my watch face has 50 odd apps, of which I use maybe 10. Removing most of the apps would make navigation much easier.
  • The watch slows down over time, so after a couple of months it starts to lag. A reboot fixes that.
  • The straps you can buy for the watch are fantastically overpriced. The default one is OK, but my wrist in between two holes, so it's usually either a bit loose or a bit tight.
  • Exercise features haven't been much use to me, but I'd blame that on me rather than the watch...

Conclusions

The positives are enough to make it worth me having an Apple Watch, and inevitably replacing when the battery life gets too bad (for the moment, it runs about 30hrs on a charge, which is fine).

by Neil Mitchell (noreply@blogger.com) at September 13, 2018 03:03 PM

September 12, 2018

Tweag I/O

Haskell WebAssembly calling JavaScript and back again

Shao Cheng

Previously, we announced the Asterius compiler, a new GHC-backend that translates Haskell to WebAssembly. Since then, we made a lot of progress; not just by supporting more of Haskell's language features, but also by improving interoperability. Today, we are proud to introduce a critical new feature: Haskell-JavaScript interop via a dedicated foreign function interface (FFI). Why is this important? It means we can finally interact with browser's DOM to in the future create full webapps.

In the style of Haskell's standard FFI, all you need to provide are simple Haskell import & export declarations. To the best of our knowledge, Asterius is the first compiler for a high-level FP language targeting WebAssembly that has reached this critical milestone.

Haskell calling JavaScript

For any compiler targeting WebAssembly, a natural question arises: how to interact with the JavaScript world and perform side effects — for example to update the browser DOM? In general, applications use application-specific API's and frameworks. Legacy applications want to use existing API's like SDL2 or Cairo to draw inside the browser window. Elm-style web apps are expressed as pure functions transforming state to state. Some applications might cut through all the layers of abstraction and call web API's directly. What all these applications have in common is that at the lowest level of the abstraction stack, there needs to be a common bridge mechanism to call JavaScript from the host language of the application (be it C, Elm or Haskell). This post is about the low-level bridge mechanism.

The spec for the Haskell language already provides for a general bridging mechanism: foreign import and foreign export declarations. We just need to teach the compiler how to handle these declarations when they're about JavaScript code.

Here is what Asterius let's you do today:

import Control.Monad

foreign import javascript "Math.random()" js_random :: IO Double
foreign import javascript "console.log(${1})" js_print_double :: Double -> IO ()
foreign import javascript "new Date()" js_current_time :: IO JSRef
foreign import javascript "console.log(${1})" js_print :: JSRef -> IO ()

main :: IO ()
main = do
  replicateM_ 5 $ js_random >>= js_print_double
  js_current_time >>= js_print

If you would like to try this at home, put the above snippet in a file called jsffi.hs in the current directory. Then, you can invoke ahc-link to compile it to .wasm/.js files (using the pre-built Asterius Docker images, as explained in the Asterius documentation):

$ docker run -it --rm -v $(pwd):/mirror terrorjack/asterius
root@6be395fd9d1e:~# ahc-link --input /mirror/jsffi.hs --run
[INFO] Loading boot library store from "/root/.stack-work/install/x86_64-linux/ghc-8.7/8.7.20180822/share/x86_64-linux-ghc-8.7.20180822/asterius-0.0.1/.boot/asterius_lib/asterius_store"
[INFO] Populating the store with builtin routines
[INFO] Compiling /mirror/jsffi.hs to Cmm
[INFO] Marshalling from Cmm to WebAssembly
[INFO] Marshalling "Main" from Cmm to WebAssembly
[INFO] Attempting to link into a standalone WebAssembly module
[INFO] Invoking binaryen to marshal the WebAssembly module
[INFO] Validating the WebAssembly module
[INFO] Serializing the WebAssembly module to the binary form
[INFO] Writing WebAssembly binary to "/mirror/jsffi.wasm"
[INFO] Writing Node.js script to "/mirror/jsffi.js"
[INFO] Running /mirror/jsffi.js
0.9698822149494266
0.7414732842838012
0.8133696271413504
0.4627748238958229
0.06512700662524917
2018-09-12T09:34:43.088Z

We can use the foreign import javascript syntax directly, without enabling any additional GHC extensions. The string after the keyword javascript needs to be a JavaScript expression, where we use positional arguments ${1}, ${2}, and so forth to refer to the imported function's arguments. The result type of an imported function may be IO wrapped, depending on whether the underlying computation is pure and can be safely cached. Our current implementation supports a variety of primitive types, such as, Bool, Char, and Int as argument and result types of imported functions. See the reference documentation for a full list.

Besides primitive types, Asterius supports importing JavaScript references represented by values of type JSRef in Haskell land. What is a JSRef? After all, the WebAssembly MVP spec only supports marshalling integers and floating point values.

Under the hood, JSRefs are really just Ints. The Asterius runtime maintains a table mapping JSRefs to actual JavaScript objects. We use the table indices to represent those objects and pass them across JavaScript-WebAssembly boundary instead. When the runtime invokes the JavaScript computation in a foreign import javascript declaration, it decides, based on the type information, whether to pass arguments and the result in their raw form or whether to use an object in the JSRef table.

Marshalling more advanced types

At this point, you may be wondering how we can marshal more advanced types, such as strings and arrays. We are going to take a page out of the standard Haskell FFI playbook and implement more complex marshalling in plain Haskell by building on top of the primitive types supported by plain foreign import javascript declarations, entirely without any further, specialised support by the runtime. For example, here is the code to marshal strings:

type JSString = JSRef

toJSString :: String -> JSString
toJSString = foldl' (\s c -> js_concat s (js_string_fromchar c)) js_string_empty

fromJSString :: JSString -> String
fromJSString s = [js_string_tochar s i | i <- [0 .. js_length s - 1]]

foreign import javascript "\"\"" js_string_empty
  :: JSRef

foreign import javascript "${1}.concat(${2})" js_concat
  :: JSRef -> JSRef -> JSRef

foreign import javascript "${1}.length" js_length
  :: JSRef -> Int

foreign import javascript "String.fromCodePoint(${1})" js_string_fromchar
  :: Char -> JSRef

foreign import javascript "${1}.codePointAt(${2})" js_string_tochar
  :: JSRef -> Int -> Char

Here, we are implementing utility functions for converting between a Haskell String and a JavaScript string. Since Char is a JavaScript FFI primitive type, supported directly by the JavaScript-WebAssembly bridge, we simply traverse the string, marshalling it character by character and re-assembling it at the other end. Similarly, we can also convert between Haskell lists and JavaScript arrays as well as between Haskell records and JavaScript objects.

JavaScript calling Haskell

A Haskell-to-JavaScript FFI is not sufficient. We also need to be able to go back. Asterius supports this in two ways.

Firstly, we have foreign export javascript declarations. They export a top-level binding as a JavaScript function, much like its cousin foreign export ccall, but also supporting JSRef as a primitive type. Here is a simple example:

foreign export javascript "mult_hs" (*) :: Int -> Int -> Int

This exposes Haskell's multiplication on plain Ints as a WebAssembly function mult_hs. Now, we just need to be able to call it from JavaScript as well.

All our previous examples assumed the existence of a function Main.main. Then, the linker generates a .js file that (1) initialises the runtime, (2) runs Main.main, and (3) finally exits. When we invoke Haskell code from JavaScript, we cannot rely on this flow of control. In the worst case, JavaScript could try to invoke Haskell code before the Haskell runtime has been initialised. That would sure lead to undesirable behaviour. Hence, we need to inject some custom code at the point where the WebAssembly code has been successfully compiled and instantiated.

The tool ahc-link provides a flag --asterius-instance-callback=, which takes a JavaScript callback function, which is to be called once an Asterius instance has been successfully initiated. An Asterius instance contains the instantiated WebAssembly module together with mappings from Cmm (GHC's C-like intermediate language) symbols to addresses. Hence, JavaScript code can call exported functions by way of accessing this symbol mapping. Continuing with the above example, in order to call mult_hs in JavaScript, the callback that we need to supply would be:

i => {
    i.wasmInstance.exports.hs_init();
    console.log(i.wasmInstance.exports.mult_hs(6, 7));
}

i.wasmInstance is the instantiated WebAssembly.Instance. We call i.wasmInstance.exports.hs_init() to initialise the runtime first before any Haskell computation occurs. After that, we can call any exported function or main as many times as we want.

The --asterius-instance-callback= flag is suitable for the scenario where we expect that all logic is contained in the JavaScript file output by ahc-link. However, this is not always the case. Instead, for a more seamless interaction with other JavaScript libraries, we may wish to encapsulate the Asterius instance and invoke hs_init in advance. In that case, it is hard to contain all logic in one JavaScript callback. For now, this remains a limitation as we continue to improve the JavaScript FFI.

Additionally, we need to supply --export-function=mult_hs to ahc-link in this example, since Main.main does not have a transitive dependency on mult_hs, without this flag, the function will be stripped from the output WebAssembly binary.

Using Haskell closures as JavaScript callbacks

The discussed foreign export javascript declarations are sufficient when all Haskell functions to be called from JavaScript are statically known. However, we often want to produce closures at runtime (e.g., by partially applying curried functions), and then, export such dynamic runtime-generated closures for use in JavaScript. For instance, when providing a Haskell closure as a JavaScript event handler, the handler often captures some contextual info as free variables, which are unknown at compile time.

We might want to work around that by adding the runtime context as a separate argument to an exported function. Then, the JavaScript code would be in charge of providing the right context when invoking a Haskell function. However, this would be a step back from the convenience of a language with first-class functions and would require substantial boilerplate code. Instead, we want to pass closure directly.

Again, we follow the approach of the standard Haskell FFI, and much as we represent JavaScript references in Haskell via JSRef values and a table, we use StablePtrs to refer to Haskell closures in JavaScript. GHC’s StablePtrs are also table indexes, which serve as a handle to a Haskell object on the heap, which can be passed between Haskell and C, or in our case, Haskell and JavaScript. We can't pass raw addresses, since the storage manager may move objects around. Hence, the StablePtr API also maintains a table of heap objects and we use table indexes to refer to them. This enables garbage collection to move objects around, as long as it takes care to also update the StablePtr table.

The Asterius JavaScript FFI supports StablePtr a as a primitive type, and as usual, we can use Foreign.StablePtr.newStablePtr to turn any Haskell closure into a StablePtr. However, we cannot directly pass a StablePtr to a JavaScript function that expects a callback. Instead, we first need to convert a StablePtr into a JSRef pointing to a valid JavaScript function which re-enters the Asterius runtime and triggers Haskell evaluation when called.

The asterius runtime provides special interfaces for this purpose: makeHaskellCallback and makeHaskellCallback1. They convert arguments of type StablePtr (IO ())and StablePtr (JSRef -> IO ()) into JSRefs referring to proper JavaScript functions, which can directly be used as event handlers, etc. This interface can be imported into Haskell like this:

foreign import javascript "__asterius_jsffi.makeHaskellCallback(${1})" js_make_hs_callback
  :: StablePtr (IO ()) -> IO JSRef

foreign import javascript "__asterius_jsffi.makeHaskellCallback1(${1})" js_make_hs_callback1
  :: StablePtr (JSRef -> IO ()) -> IO JSRef

Now, let's put together a complete example using a Haskell closure inside a JavaScript event handler:

import Foreign.StablePtr

foreign import javascript "Math.random()" js_random :: IO Double

foreign import javascript "console.log(${1})" js_print_double :: Double -> IO ()

foreign import javascript "__asterius_jsffi.makeHaskellCallback(${1})" js_make_hs_callback
  :: StablePtr (IO ()) -> IO JSRef

foreign import javascript "process.on(\"beforeExit\",${1})" js_process_beforeexit
  :: JSRef -> IO ()

main :: IO ()
main = do
  x <- js_random
  newStablePtr (js_print_double x) >>= js_make_hs_callback >>=
    js_process_beforeexit

When this example runs, Main.main first obtains a random number x, then converts the (as of yet unevaluated computation) (js_print_double x) into a StablePtr (IO ()), then into a JSRef, and finally sets it as a handler of the beforeExit event of the node process. Before the node process shuts down, it invokes the handler, which re-enters the Asterius runtime, evaluates the Haskell closure, which in turn invokes js_print_double to print the random number we obtained earlier. This is obviously a contrived example, but it does demonstrate the ability to use runtime-computed Haskell closures within JavaScript callbacks.

What's next?

There are limitations still to the current JavaScript FFI:

  • Currently, the marshalling of large objects, such as strings and arrays is fairly costly, as it requires many function calls between Haskell and JavaScript. Hence, we plan to provide custom marshalling for common bulk types (such as, ByteString, Text, and even aeson Values) in the runtime.
  • The standard Haskell FFI allows directly marshalling primitive types wrapped in newtype declarations. Asterius currently lacks that capability, but we plan to add it in a later version. This would allow us to e.g. make JSString a newtype wrapper around JSRef above.
  • We did not discuss properly freeing JSRefs and StablePtrs. Besides manual freeing, we plan to look into the usual support for finalisers as well as a ResourceT-like mechanism that frees JSRefs upon exiting a scope. Even better, we should be able to use GHC's experimental support for linear types.
  • We need to consider exception handling at language boundaries and ideally propagate them transparently.
  • Finally, we need to look into using other JavaScript packages from Haskell and wrapping Haskell libraries transparently as JavaScript packages?

However, the JavaScript FFI as it stands is already sufficient to build fairly complete web apps. That will be the topic of our next installment in this series. Stay tuned!

September 12, 2018 12:00 AM

September 11, 2018

Chris Smith 2

“Teaching Haskell in K-12” Dinner at ICFP

Dear Haskellers: You are cordially invited to a dinner discussion on “Teaching Haskell in K-12” at ICFP in St. Louis.

<figure><figcaption>Middle school students learning Haskell with CodeWorld</figcaption></figure>

This meeting is for anyone around the world with an interest in teaching Haskell and related languages at the K-12 (that is, pre-university) level. We will hope to find a critical mass of people to build a connected and supportive community. In this community, we can share experiences and resources, ask for and receive help, and encourage each other as we strive to bring functional programming to a new generation.

Personally, I’ve been working for six years on using Haskell to build algebraic thinking skills in middle school students. I am not alone. Emmanuel Schanzer and many others have explored the same approach with Bootstrap. Christopher Anand and colleagues have done the same with Elm at McMaster University as early as 4th grade, and the Gordon Cain Center at Louisiana State University has trained teachers using CodeWorld for a 9th grade computational thinking class for hundreds of students. Just as importantly, the Haskell community is built of thousands of individuals who have something unique contribute to your own communities and children.

You’re invited to come discuss our common goals, how we can organize and teach, which tools and libraries we find helpful, what technology is missing that could help the effort move forward, and even how to scale our efforts to reach as many children as possible around the world.

Let’s meet for dinner about 7:00 pm on Monday the 24th. Please RSVP here. I hope to see you there!

by Chris Smith at September 11, 2018 01:28 AM

September 08, 2018

ERDI Gergo

PS/2 keyboard interface in CλaSH

This week, most of my weekday evenings were quite busy, but I did manage to squeeze in a PS/2 keyboard interface in small installments; then today I went down the rabbit hole of clearing up some technical debt I've accumulated so far by not really looking into how CλaSH handled clock domains.

PS/2 signals

(Just to preempt any possible confusion, we're talking about the peripheral port of the IBM Personal System/2 introduced in the late '80s, not the Playstation 2 console)

The same way VGA is ideal for hobbyist video signal generation since it is both simple and ubiquitous, PS/2 is the go-to interface for keyboards. It is a two-directional, synchronous serial protocol with a peripheral-generated clock in the 10-20 KHz range. Any PC keyboard old enough will support it. One important caveat, though, is that the common USB-to-PS/2 adapters don't actually convert signals, and so they only work with keyboards that were originally designed with that conversion in mind. Here, we are only concerned with device to host communication; it is also possible to communicate in the other direction to e.g. change the Num Lock LED's state.

"Synchronous" here means that there is a separate clock line, unlike in the family of asynchronous serial protocols that were used in RS-232; it is this latter one that is usually meant as "serial communication" when unqualified. In synchronous serial communication, everything happens on the clock ticks; in asynchronous communication, there is no separate clock signal, so the data signal has enough structure that the two communicating sides can agree on the exact framing.

Turning the data line of PS/2 into a stream of bits is a straightforward process: the standard prescribes sampling the data line on the falling edge of the clock line. We also apply an 8-cycle debouncer for good measure, just because some pages on the Internet suggest it:

data PS2 dom = PS2
    { ps2Clk :: Signal dom Bit
    , ps2Data :: Signal dom Bit
    }

samplePS2
    :: (HiddenClockReset dom gated synchronous)
    => PS2 dom -> Signal dom (Maybe Bit)
samplePS2 PS2{..} = enable <$> isFalling low ps2Clk' <*> ps2Data'
  where
    ps2Clk' = debounce d3 low ps2Clk
    ps2Data' = debounce d3 low ps2Data        
      

The second step in that pipeline is to shift in the bits, 11 at a time. A leading low bit signals the start of a packet; eight data bits and one parity bit follow; the packet is finished with one high bit. Of course, only the eight data bits are presented externally. I use a WriterT (Last Word8) (State PS2State) monad to implement this logic, and then turn that into a CλaSH Mealy machine, in a pattern that I plan to use a lot in implementing the CHIP-8 CPU later:

 data PS2State
    = Idle
    | Bit Word8 (Index 8)
    | Parity Word8
    | Stop (Maybe Word8)

decodePS2
    :: (HiddenClockReset dom gated synchronous)
    => Signal dom (Maybe Bit) -> Signal dom (Maybe Word8)
decodePS2 = flip mealyState Idle $ \bit -> fmap getLast . execWriterT . forM_ bit $ \bit -> do
    state <- get
    case state of
        Idle -> do
            when (bit == low) $ put $ Bit 0 0
        Bit x i -> do
            let x' = shiftInLeft bit x
            put $ maybe (Parity x') (Bit x') $ succIdx i
        Parity x -> do
            let checked = bit /= parity x
            put $ Stop $ enable checked x
        Stop x -> do
            when (bit == high) $ tell $ Last x
            put Idle       
      

A quick change in hardware

To be able to try out on real hardware what I had at this point, I had to leave the trusty LogicStart Mega-Wing of my Papilio Pro, and instead switch over to the Arcade since that one has a PS/2 port. There are actually two ports on it, so that one could connect e.g. a keyboard and a mouse.

This change involved rewriting my UCF file since the pinout is different from the LogicStart. Also, the Arcade has 4+4+4 bits of VGA color output instead of the previous 3+3+2; of course with the black & white graphics of the CHIP-8, that color depth is all going to waste with this project.

PS/2 scan codes

Unfortunately, it is not enough to shift in the PS/2 data into a byte: we also have to make sense of that byte. While this could be as straightforward as interpreting each byte as the ASCII code of the character on the key pressed, the reality is not this simple. Keyboards emit so-called scan codes, where one or several bytes can encode a single keypress or key release event (see here for example for a list of some keyboard scan codes). I haven't been able to come up with an elegant way of handling this yet, so for now I just have some messy Mealy machine that returns a 16-bit code, where the high byte is zero for one-byte codes. You can see in the comment my frustration at both the implementation and the spec itself:

data KeyEvent = KeyPress | KeyRelease
    deriving (Generic, NFData, Eq, Show)

data ScanCode = ScanCode KeyEvent Word16
    deriving (Generic, NFData, Eq, Show)

data ScanState
    = Init
    | Extended Word8
    | Code KeyEvent Word8

-- TODO: rewrite this for clarity.
-- All it does is it parses 0xE0 0xXX into an extended (16-bit) code, and everything else into
-- an 8-bit code. The only complication is that the key release marker 0xF0 is always the
-- second-to-last byte. Who does that?!?
parseScanCode
    :: (HiddenClockReset dom gated synchronous)
    => Signal dom (Maybe Word8) -> Signal dom (Maybe ScanCode)
parseScanCode = flip mealyState Init $ \raw -> fmap getLast . execWriterT . forM_ raw $ \raw -> do
    let finish ev ext = do
            tell $ Last . Just $ ScanCode ev $ fromBytes (ext, raw)
            put Init
    state <- get
    case state of
        Init | raw == 0xe0 -> put $ Extended raw
             | raw == 0xf0 -> put $ Code KeyRelease 0x00
             | otherwise -> finish KeyPress 0x00
        Extended ext | raw == 0xf0 -> put $ Code KeyRelease ext
                     | otherwise -> finish KeyPress ext
        Code ev ext -> finish ev ext
  where
    fromBytes :: (Word8, Word8) -> Word16
    fromBytes = unpack . pack        
      

Driving a CHIP-8 pixel around

With the video output from last time and the keyboard from this post, but no CPU yet, our options to put everything together into something impressive are somewhat limited. I ended up showing a single CHIP-8 pixel that can be moved around in the CHIP-8 screen space with the arrow keys; this results in something tangible without needing a CPU or even a framebuffer yet. Note how well the code lends itself to using applicative do syntax:

VGADriver{..} = vgaDriver vga640x480at60
ps2 = decodePS2 $ samplePS2 PS2{..}

(dx, dy) = unbundle $ do
    key <- parseScanCode ps2
    pure $ case key of
        Just (ScanCode KeyPress 0xe075) -> (0, -1) -- up
        Just (ScanCode KeyPress 0xe072) -> (0, 1)  -- down
        Just (ScanCode KeyPress 0xe06b) -> (-1, 0) -- left
        Just (ScanCode KeyPress 0xe074) -> (1, 0)  -- right
        _ -> (0, 0)

pixel = do
    x <- fix $ register 0 . (+ dx)
    y <- fix $ register 0 . (+ dy)
    x0 <- (chipX =<<) <$> vgaX
    y0 <- (chipY =<<) <$> vgaY
    pure $ case (,) <$> x0 <*> y0 of
        Just (x0, y0) -> (x0, y0) == (x, y)
        _ -> False
      

<object height="350" width="425"><param name="movie" value="http://www.youtube.com/v/AaECocamB-o"/><param name="wmode" value="transparent"/><embed height="350" src="http://www.youtube.com/v/AaECocamB-o" type="application/x-shockwave-flash" width="425" wmode="transparent"></embed></object>

But wait! There's more!

In reality, after getting the PS/2 decoder working, but before hooking it up to the scan code parser, I thought I'd use the serial IO on the Papilio Pro to do a quick test by just transmitting the scan codes straight away as they come out of the decoder. This has then prompted me to clean up a wart on my UART implementation: they took the clock rate as an extra term-level argument to compute the clock division they need to do:

tx
    :: (HiddenClockReset domain gated synchronous)
    => Word32
    -> Word32
    -> Signal domain (Maybe Word8)
    -> TXOut domain
tx clkRate serialRate inp = TXOut{..}
  where
    (txReady, txOut) = unbundle $ mealyState (tx0 $ clkRate `div` serialRate) (0, Nothing) inp        
      

This bothered me because the clock domain already specifies the clock rate, at the type level. Trying to remove this redundancy has led me down a rabbit hole of what I believe is a CλaSH bug; but at least I managed to work around that for now (until I find an even better way).

This, in turn, forced me to use a proper clock domain with the correct clock period setting in my CHIP-8 design:

-- | 25.175 MHz clock, needed for the VGA mode we use.
-- CLaSH requires the clock period to be specified in picoseconds.
type Dom25 = Dom "CLK_25MHZ" (1000000000000 `Div` 25175000)        
      

But then, this allowed me to start putting pixel clock specifications into the type of VGATimings, allowing me to statically enforce that the clock domain in which the VGA signal generator runs is at exactly the right frequency:

vgaDriver
    :: (HiddenClockReset dom gated synchronous, KnownNat w, KnownNat h)
    => (dom ~ Dom s ps, ps ~ (1000000000000 `Div` rate))
    => VGATimings rate w h
    -> VGADriver dom w h
    
-- | VGA 640*480@60Hz, 25.175 MHz pixel clock
vga640x480at60 :: VGATimings 25175000 10 10
vga640x480at60 = VGATimings
    { vgaHorizTiming = VGATiming 640 16 96 48
    , vgaVertTiming  = VGATiming 480 11  2 31
    }
      

September 08, 2018 06:24 PM

Philip Wadler

A new EU law could end the web as we know it (redux)


In June, the EU avoided voting for Articles 11 and 13, which have the potential to end the web as we know it. Now they're back; the vote is 12 September. Up to date info is at Creative Commons, links to help you write, call or tweet are at SaveYourInternet.eu. Below is what I wrote to my MEPs. If you are an EU citizen, you should write too; WriteToThem makes it easy.

Dear Nosheena Mobarik, Alyn Smith, Ian Hudghton, Catherine Stihler, David Martin, and David Coburn,

I write to you greatly disturbed by the new proposals for copyright. These would require any service provider to maintain large, expensive, and ineffective filters. While YouTube, Twitter, or Facebook will have no problems funding these, they will prevent the next innovative service from getting off the ground. Experience with such filters show that they ban all sort of material which should be in the public domain or which is fair use.

I am also concerned by the resurrection of the "link tax". Previous experience with adding a link tax in Germany and Spain showed that the newspapers that requested it soon stopped using it. It is particularly worrying that the legal formulation chosen will invalidate Creative Commons licenses. Many academic journals (including the one which I edit) depend crucially on Creative Commons, and passing a law that invalidates it is against the public interest.

An excellent one-page summary of the issues, with further links, can be found here:

https://boingboing.net/2018/04/11/evidence-free-zone.html

The web has been a huge boon to innovation, creativity, cooperation, and scientific progress. Please don't kill the goose that lays the golden eggs.

Yours sincerely,



Philip Wadler
Professor of Theoretical Computer Science
University of Edinburgh

by Philip Wadler (noreply@blogger.com) at September 08, 2018 12:18 PM

September 06, 2018

Chris Smith 2

My discussion group is meeting on Friday, so I’ll let you know!

My discussion group is meeting on Friday, so I’ll let you know! I’d planned to revisit some of this and share some thoughts after I’d left this for a week or so. But I’ll go ahead and say a few things now.

Personally, I think when people talk about computational thinking, they mostly have the right set of ideas in mind — decomposition, abstraction, and modeling. There’s another bit, though, sort of underlying all of these, that’s harder to name. It’s the sense that, instead of trying to *first* understand and *then* formalize, we can build understanding through the creation of a formally validated symbolic representation. (There’s a beautiful section of the SICP text in which the application of more and more abstraction to a procedure for computing square roots leads to exploring its connections with important ideas like fixpoints, signal damping, and derivatives. In lecturing on this at IBM, Abelson commented on how this lets us comprehend the meaning of Heron of Alexandria’s process, in a way that even Heron could not access.)

The validation is necessary, by the way, as a crutch, because we’ve left the realm in which intuition works well as a guide. Having some intuition is a good thing, but when trying to state things formally, we always make mistakes, and they are usually not even subtle ones. They are glaringly obvious things that make our work nonsense even if we know what we meant to build. All computation environments do some amount of validation, even if it’s just checking syntax, or making the bad behaviors of our broken models obvious and observable. Some do more than that, such as checking consistent use of types or abstraction boundaries.

This is, I think, is one way in which the computer is relevant to computational thinking. Without constant validation, we still go through qualitatively the same abstraction process, but each step toward abstraction introduces a new possibility of error. The work of carefully verifying each step grows to overwhelm the invention of new abstractions, limiting its feasible scope. Similarly, computer scientists are by no means the first to approach difficult tasks by structured decomposition. Yet, when you are designing a bridge, the work of the engineer is necessarily dwarfed by the hundreds of laborers pouring concrete and welding beams, not to mention mining iron or milling parts! It gives quite a different perspective when coping with complexity is the *main* determinant of success or failure.

The problem is that people say all these things, but then they teach what they know. And for many of us who were trained as computer programmers, what we know is the *practice* of computer programming. Some of that practice is relevant to computational thinking, but much of it is an accident of history, or a consequence of which company had more marketing money in which decades. Even when it’s quite justified as a technology, it’s quite a different thing whether a skill is part of that *core* that gets at the essence of how computation opens up new worlds.

Computer programmers are attached to their tools, but the UNIX command line, integrated development environments, and revision control systems are surely not part of that core. Maybe there’s not much debate on that point. Loops, though, are a main player in even elementary school computing activities. Should they be? They seem to me to have been invented entirely for the practice of computer programming, and are not at all important to abstraction, decomposition, or modeling.

Alas, it seems I have written a blog post in this comment. I might recycle a lot of it in my later recap after having thought this over more!

by Chris Smith at September 06, 2018 02:07 AM

September 05, 2018

Philip Wadler

Why Technology Favors Tyranny


A thoughtful article by Yuval Noah Harari in The Atlantic. Anyone working in computing should be considering the issues raised.
[A]s AI continues to improve, even jobs that demand high intelligence and creativity might gradually disappear. The world of chess serves as an example of where things might be heading. For several years after IBM’s computer Deep Blue defeated Garry Kasparov in 1997, human chess players still flourished; AI was used to train human prodigies, and teams composed of humans plus computers proved superior to computers playing alone.

Yet in recent years, computers have become so good at playing chess that their human collaborators have lost their value and might soon become entirely irrelevant. On December 6, 2017, another crucial milestone was reached when Google’s AlphaZero program defeated the Stockfish 8 program. Stockfish 8 had won a world computer chess championship in 2016. It had access to centuries of accumulated human experience in chess, as well as decades of computer experience. By contrast, AlphaZero had not been taught any chess strategies by its human creators—not even standard openings. Rather, it used the latest machine-learning principles to teach itself chess by playing against itself. Nevertheless, out of 100 games that the novice AlphaZero played against Stockfish 8, AlphaZero won 28 and tied 72—it didn’t lose once. Since AlphaZero had learned nothing from any human, many of its winning moves and strategies seemed unconventional to the human eye. They could be described as creative, if not downright genius.

Can you guess how long AlphaZero spent learning chess from scratch, preparing for the match against Stockfish 8, and developing its genius instincts? Four hours. For centuries, chess was considered one of the crowning glories of human intelligence. AlphaZero went from utter ignorance to creative mastery in four hours, without the help of any human guide.

by Philip Wadler (noreply@blogger.com) at September 05, 2018 03:56 PM