Retrospective: Software Engineering Summer Internship (2015) at Jeppesen Systems AB in Gothenburg

Introduction

Jeppesen is a fully owned subsidiary of Boeing, and part of their Digital Aviation business. Concretely, they provide navigational information, crew and fleet management solutions, and offer an industry-leading optimization product. The Gothenburg office started originally as Carmen Systems, which was spun off Chalmers University of Technology. Ties between Chalmers and Jeppesen are still strong. The Gothenburg office of Jeppesen employs around 350 people, of which around 300 are technical staff. Further, there are around 60 contractors in the building.

Jeppesen was not an entirely new entity to me. I had been mentored by one of their managers for about a year, though whom I met several other Jeppesen employees, including a veteran software architect with a very strong technical background, and an experienced software developer. Further, I was one of the winners of a coding competition they held this spring, and one of five students who were invited to what turned out to be an intimate recruiting event, where we were outnumbered by Jeppesen managers and employees. Several managers represented their division, the challenges they are working on, and, of course, the kind of skills they are looking for in future employees. Alas, back then they did not have any openings, but we were told that a number of full-time positions would open up in autumn, and possibly some summer internships as well. Both turned out to be the case.

The interview

I applied for a data processing project with a parallel programming component, which I will detail further below. But before I got to do any work, I had to make it through the interview. Job interviews are often cringe-worthy, particularly the “your greatest weakness”-kind. The interview experience at Jeppesen was distinctly positive, though. The hiring manager briefly came in to shake hands and exchange some niceties, but otherwise, the interview was conducted by two senior engineers. They described the project, how they work, and the technologies they use.

What I greatly appreciated was that they were looking for competence instead of buzzwords. We even talked a bit about the necessary computer science background for their project. It was helpful that I had heard of recursive descent parsing, had written a parser for a subset of C++, or implemented a compiler for a C-like language. Normally, a coding test is also part of the interview process, but I presume this was skipped due to my performance on their recent coding challenge. Still, they asked me a few ‘design’ questions, like how I would approach this or that problem, or pros and cons of concrete approaches to given problems. Thankfully, it was more about how to break down a complex task into manageable subproblems, instead of the dreaded UML and design patterns interview.

The project

Of course I signed and NDA can therefore not be too specific, so I am only going to describe the problem in general terms. Let’s say your software runs on dozens or possibly even hundreds of machines at a customer site. Each copy of the program produces partly unstructured log files, recording all kinds of things. In order to extract useful information from those log files, you have to run a parser that understands the structure of the files, and extracts relevant information, which may be processed further. To make this even more fun, let the client machines run around the clock, and update log files continually. This sounds fairly complicated already. However, keep in mind that you have more than one customer, many more than one parser, and currently you only execute one parser after another in a sequential order via a cron job once a day, for historical reasons, maybe because the programs predate the many-core CPU era.

The goal of the project I was given was to write a framework that parses all log files — think in orders of magnitudes of tens of thousands of files — in pseudo-real time, so that you can extract more useful information from the existing data. For instance, if you take a metric like ‘active instances’ once a day, you’ll learn a lot less than if you are able to update this metric every few minutes.

Concretely, the framework I developed unified the existing parsers for several Jeppesen products. Understanding and modifying existing parsers required a little bit of background in programming languages. This was pretty fun, but the most interesting aspect was trying to find ways to effectively parallelize the execution of the parsers. The hardware at our disposal was pretty decent. Thus, running a single-threaded program on a many-core CPU is a bit of a waste, to put it mildly. My approach was to avoid all shared state. Once this problem was solved, the actual parallelization was easy to achieve. The machine I was mostly working on was an Intel Xeon with 16 cores and over 100 GB RAM, which was far from being the most powerful machine I had access to. Even on that one, we easily hit our performance target.

In my last two weeks, I had plenty of time to ensure the documentation was comprehensive. At the same time, my main supervisor put the project successfully into production at two customer sites, both major European airlines. At both sites we encountered minimal issues that were easily resolved. In one case, the volume was much greater than the fairly large test data directory I had been working with, so I needed to use a more efficient data structure, and make use of memoization at one point in order to resolve a bottleneck. At the other customer site, a slightly different naming convention for some files was used, which was an even easier fix. My last update was that this product has been successfully rolled out to two more customers.

The software development process

While Jeppesen is officially committed to “Agile”, they nonetheless have a strong engineering culture, which entails that they make use of software processes not for their own sake but when there is a clear benefit. The first few days on the job, I was expected to do the daily “stand up” song and dance, and report on everything I’ve done, what I intended to do that day, and give various estimates about the next few days. Personally, I found this more annoying than helpful. After I showed a proof of concept of this product after a few days, instead of the planned two weeks, my supervisors concluded that I can apparently work well on my own, and scrapped daily meetings. Instead, we had the occasional demo session, or just casually discussed progress during company breakfast.

I did like that, after proving myself, I was given relatively free reign with regards to the development, of course while still conforming to the overall vision of the product, which I received at the beginning in the form of a succinct document. The eventual software development process was somewhat reminiscent of Iterative and incremental development.

The work environemnt

Based on my experience at a previous employer, and from various company visits, I would say that Jeppesen has a clearly above average office environment. It’s not uncommon that three or four employees share their own, reasonably spacious office. However, there are also several open-plan office areas, the kind that is claimed to foster cooperation and communication, even though they are “damaging to the workers’ attention spans, productivity, creative thinking, and satisfaction”. Well, Joe Programmer, no matter where on the world he works, sadly does not command enough status to get his own office. Thus, companies are, quite literally, squandering money by not giving people access to (genuinely) quiet working environments.

Still, thanks to artificial dividers, plants, and a reasonable amount of space, the open-space areas at Jeppesen are quite okay. I was sitting in one of the larger ones in the building, among around 15 employees, all fairly well spread-out. The main office hours are a bit busy, with infrequent distractions. However, if you come in very early or stay late, you can enjoy a quiet working environment and get a lot done. During the busier hours of the day, you may notice decreased productivity, compared to, say, intently working on something in the privacy of your home.

A few perks are offered, too. Every morning, there is free basic breakfast, which is also a great opportunity to talk to people outside of your department. Further, bowls of fruit are placed all over the building. This being Sweden, there is also a strong tradition of having ‘fika’, i.e. a short break for consuming coffee and pastries. Noteworthy is that a masseuse visits the office in regular intervals, for which you can sign up at reception, and get the cost deducted from your pay. Regular employees are even entitled to some free money (friskvård) for that purpose, or other health-related expenditures.

Working hours are quite flexible. You are expected to put in 40 hours per week. As a rank-and-file employee you have to be present during core business hours (9:00 to 15:00), but you do have some flexibility otherwise. For instance, taking the occasional long lunch break, and staying longer some other days is certainly something you can discuss with your manager, just like taking half a day off and putting in a few more hours on some other days to make up for it. Overall, they try to achieve a good work/life balance.

Summary

This was a very enjoyable internship, and a summer well-spent. The end result was that I wrote, relatively independently, a medium-sized application weighing in at thousands of lines of code, all tested and well-documented. It was a good mixture of intellectual challenge and more mundane practical aspects. In the beginning, intellectual challenges were more dominant, like the entire design of the product, or figuring out effective parallelization. Later on, the focus was much more on polishing the code base, and eventually deploying it. The latter was not quite as mentally stimulating, but on the other hand it was immensely gratifying to see the project hitting or exceeding all performance targets, as well as its successful deployment.

A graduate’s perspective on the Software Engineering and Management Bachelor’s program at the University of Gothenburg

Introduction

I graduated from the University of Gothenburg with a Bachelor’s degree in Software Engineering and Management (SEM) in June. When I applied, in 2012, there was relatively little authentic information available online. The university websites surely were informative, and the PDF flyers well-produced. On the other hand, students did not seem overly vocal online. Thus, I would like to give my personal perspective, which may help future applicants. The information below should be useful for at least the next five to seven years, considering the pace at universities. For the past few years there has been an initiative in the department to further evolve the curriculum, though. This will lead to some changes, but from what I gather the changes will be of an evolutionary nature.

The target student

I assume that you, the reader, are a non-Swede and, for whatever reason, want to move to Sweden to pursue an IT-related education. If you are flexible with regards to the location, and can afford paying tuition fees, you certainly should explore other options as well. My motivation for coming to Sweden was to live with my girlfriend. Indeed, talking to other international students, male and female alike, this seems to be a fairly common motivation.

If you don’t speak Swedish, your options with regards to Bachelor’s degrees in Sweden are rather limited. In 2012 there were very few options available, and the SEM program seemed the most promising. Proper computer science programs were, and still are, taught in Swedish. It seems the issue a lack of willingness to provide access to certain programs to foreigners. For instance, almost every course in the computer science program here in Gothenburg is taught in English. Yet, a very small number of introductory courses in that program are offered only in Swedish, which thus precludes foreigners from enrolling. The language is hardly the problem, considering that you may take courses in the SEM program that are officially taught in English, but by people who do not have a proper grasp of the language. On the other hand, some of the introductory courses in the CS program are taught by academics who speak excellent English, but for whom Swedish is only their third language.

Whatever the reason, fact of the matter is that your options with regards to English-speaking Bachelor’s programs in Sweden are limited. The SEM program is one of very few choices. Thus, the question is whether it is good enough. In my opinion, even though my view is not entirely positive, for reasons I will elaborate later on, it is a decent program that tries hard to teach relevant knowledge and skills, with the aim of turning you into a productive cog in the wheel in the IT industry. They are not turning out superstars, but given that there’s a perennial Amateur Hour in large parts of the software industry, with all their “ninjas” and “gurus” who barely grasp the basics of their craft, they don’t have to.

Prerequisites

Formally, the SEM program does not expect students to have any kind of programming experience. However, it would be rather naive to enter a program like this without having done any programming at all, since it will be a major part of your education. Quite frankly, if you have never programmed in your life, and you nonetheless consider BSc programs related to IT or CS, you should set your priorities straight. Computer science is one of if not the most democratic discipline at university, since there are no artificial barriers. All the information you would need to educate yourself is available for free online. Nowadays you can even find entire university courses online. In short, there is absolutely no excuse not to have at least basic programming knowledge. If you don’t then you may end up in the rather uncomfortable position to find out that programming is not quite as trivial as you imagined it to be.

Let me point out that the word, management, in the name of this degree program is potentially misleading. The management part in the SEM program is concerned with managing software projects, but not with general management. If you are interested in an education in business, this is the wrong degree to pursue. Sadly, this is apparently not at all self-evident. If you are “more of an ideas guy” and have wet dreams of bossing nerds around, then business school is where it’s at. Unfortunately, there is at least a handful of incoming students who come to class impeccably dressed for a few weeks, and who eventually realize that the content of the SEM program does not meet their expectations.

I don’t think you necessarily have to like or “love” programming. For most people in this industry software development is a job. Their studies were a series of hoops they had to jump through, but their craft is nothing they have any, to use a horribly overused word, “passion” for. That’s okay, though. The commoditization of software development has been going on for about two decades. If you’re a True Believer, you might even find some worthy cause in that movement. Otherwise, you are either fortunate to be employed by a company that does interesting work, or you use your brain in your spare time. No matter where you might be on this spectrum, at the very least you should have done enough programming so that you can assess whether you have some aptitude for it. It’s okay if you find it tedious — mainstream programming languages are indeed tedious to work in. However, if you happen to dislike programming and struggle with basic concepts like control flow or boolean operators, you won’t do yourself any favour by pleasing your parents who think that a career in IT is a sound choice in the early 21st century.

The curriculum

Considering that computer science tends to have the reputation of being too theoretical, one can easily make the claim that the SEM program is too practical. Indeed, the curriculum is strongly geared towards teaching skills that make you employable in the IT sector. Each semester has a particular theme. You get exposed to several mainstream languages: Java, C++, and C, as well as one particular off-beat language that is part of the curriculum because a local employer infrequently needs people with that skill: Erlang, which is used within Ericsson. If you try hard, you can avoid learning Python or JavaScript, but normally students use at least one of these in some of the projects, even though there will only be very little formal instruction, or none at all.

Considering that the SEM program does not expect students to have any kind of programming experience, you will spend the first semester on basics: Java, relational databases, but also a bit of software engineering theory where you learn about some common software development processes, and get your first dose of Agile/Scrum indoctrination. Half of the entire course load is dedicated to a group project where you build a simple CRUD application. The first semester will be the most chaotic of the program, due to large numbers of students dropping out, and others hanging on for too long. This tends to affect the group project as well. In my cohort, so many students dropped out, and others found out that they tremendously dislike each other, that several groups had to be dissolved, rearranged, joined, or split.

In the second semester, in a second course on programming, you will learn about basic algorithms and data structures, which takes 25 % of the course load. Another 25 % is spent on software engineering courses that may make your eyes glaze over, and 50 % on a relatively open ended group project where you build a “system”, which is supposed to mean that your code shall make a piece of hardware do something non-trivial. In my class, we got to play around with the educational robot NAO by Aldebaran. Among others, we managed to make it navigate a maze. One of the more ambitious recent projects consisted of building a quadcopter and making it do some things you may easily take for granted if you buy one off the shelf, for instance making it stabilize itself if you throw it off balance.

In the third semester you will be exposed to functional programming. You will have the privilege to learn Erlang and gain practical experience in building a medium-sized distributed application in it. You can also learn that putting Erlang on your LinkedIn profile has the side effect that recruiters from the UK will start contacting you. The software engineering courses on software architecture and software management will provide you with the right vocabulary for interviews at typical software development companies. Considering that most of the SEM program is spent on mainstream technologies, a semester mainly devoted to functional programming in Erlang is a welcome breath of fresh air.

Working in a more expressive language like Erlang might have changed how you view programming. Dropping down several levels of abstraction to manipulating bits in C might have the very same effect. In the fourth semester you will start with programming a microcontroller and gain intimate acquaintance with segmentation faults. The semester project is by far the most ambitious of the SEM program: you are supposed to build a self-driving miniature car. In a course on testing you will, among others, get exposed to randomised testing using QuickCheck, which might make you question why people bother with unit tests.

In the fifth semester you get exposed to some rather questionable software engineering modules, with a focus on change management. Quite frankly, I saw very little value in it. Thankfully, if you have any experience with academic writing, none of the courses should take much of your time. Part-time work isn’t so easy to find in Gothenburg, so if this is not an option for you, then taking computer science courses, or working on your technical skill set may be worth thinking about.

Lastly, this degree program culminates in a Bachelor’s thesis project. The faculty is very supportive, which means that as long as you have the necessary skills and can write a decent thesis proposal that is related to software engineering or computer science, you can work in many areas — even theoretical computer science is possible, provided you took some additional courses. Most students work in groups of two, some in groups of three, and some on their own. Further, you can do your thesis either in an academic setting, or in collaboration with the industry. The latter may be a good opportunity to find an employer, but the downside is that you will be less flexible with regards to the choice of your thesis topic.

After graduation

The goal of this program is to prepare you for a role within the software industry. While some of the graduates work as software developers, others become testers or technical writers. If technical skills aren’t really your strong suit, then you may get the chance to enter a larger company and get promoted to the position of “Agile Coach” or “Scrum Master”. Particularly if you are a member of a protected class, several career paths may open up that are only tangentially related to technology. After all, Swedes love their ‘diversity’ and political correctness.

Judging from my graduating class, people seem to find work relatively quickly. Gothenburg is not exactly a hotbed of technology, though. In my opinion, there are not so many interesting positions available locally. On the other hand, if your prime goal is to get a job in the IT industry that pays the bills and puts food on the table, then Gothenburg has plenty to offer. For instance, there are several large consulting companies. Sigma and HiQ are relatively prominent, and readily hire graduates from this program. Other large employers in the region include Ericsson and Volvo IT. The kind of work you can get at those companies may be sleep-inducing, but it presumably beats the heat and humidity that is part of flipping burgers.

If you just want to find reasonably interesting work, then the SEM degree should do. In Sweden it is not at all uncommon to find people who work in this industry without having any degree at all, and it is still possible to enter it without any piece of paper. The only difficulty is getting a foot in the door. On the other hand, if you want to expand your horizon, and possibly prepare yourself for working in particular industry sectors, then studying towards a Master’s degree may be a good idea. In that regards, some students take the easy way out and study the Software Engineering Master’s program at Gothenburg University. I’m not sure whether SEM graduates are guaranteed a place, but even if not, it seems very easy to get admitted coming from the SEM program, which is no surprise since the Master’s program builds upon some of the Bachelor’s courses. It is much more about software engineering processes and ideologies than developing technical skills, though.

It is not at all uncommon that students move into related fields. Some pursue degrees in IT Management, others go to business school. Pursuing more technical fields is also possible. A minority of graduates moves on to study computer science in various flavors at the Master’s level. One of my former class mates, for instance, is currently studying towards an MSc in Financial Systems Engineering at University College London, for instance. The vast majority of graduates seem to want to stay in Sweden. In fact, very few even move away from the Gothenburg area.

Recommendation

In my opinion, the SEM program is a good choice for people wanting to gain a decent technical skill set. There are some disadvantages, though. Personally, I think university studies should first and foremost provide a sound theoretical foundation, and not concern themselves too much with applicability. Concretely, in the case of the SEM program, I would certainly say that there is value in doing one larger group project, where you learn to collaborate, to plan your work effectively, and practice leadership skills. However, four projects are overkill. I would have much preferred seeing a curriculum that reduced group work and instead added a few more computer science courses. That being said, if you do have solid technical skills and are able to organize your work well, then the group projects will not take up too much of your time. Thus, you can take additional courses. I managed to squeeze an additional year’s worth of mathematics and computer science courses into my three years in the SEM program, for instance.

When I started, in 2012, there were very few Swedish universities that offered Bachelor’s degrees in English. This is no longer the case. These days, though, you can study technical degrees at the Bachelor’s level at Uppsala, KTH, and Lund. Depending on your interests, those may be better choices. One downside of the SEM program is that it is relatively narrowly focused on software engineering, and only provides a small core of computer science knowledge, which may limit you in the future. On the other hand, for instance, a Bachelor’s degree in Mathematics at Lund, which leaves significant room for electives, will provide you with much greater flexibility. If you think that software development is exactly what you want to do (how would you know that?), then the SEM program is a good choice. Otherwise, I would recommend a more foundational degree, like computer science, or even mathematics. The former, though, is currently not an option in Sweden if you don’t speak Swedish.

Diceware, Security Theater, and “Women in Tech” Propaganda

I recently came across an article on ArsTechnica that was the epitome of the inane “More XX chromosome carriers in Tech” propaganda that has been infesting this industry for quite some time. Of course, the problem is not that there should be no women in tech, but that there is a celebration of pseudo-achievements that do the industry, the organizations behind this social engineering initiative, and women themselves a disservice.

In the story, entitled This 11-year-old is selling cryptographically secure passwords for $2 each, we learn that Mira Modi the daughter of Julia Angwin, a “veteran privacy-minded journalist” is selling “cryptographically secure passwords”. As you you read the article, you are tempted to conclude that Mira Modo has simply been paraded around by her mother, as she seems to have little insight into what she is actually doing. In the end, the entire story boils down to her mother looking for a cute marketing gimmick, which made her enlist her daughter for selling passwords on her book tour — and now there is a website, too!

The idea behind Diceware passwords is simple: you roll five dice, or one die five times, and then look up the corresponding word in a publicly available list, which pairs a number combination with a string. For instance, if you throw 5-5-6-5-5, your passphrase is “suave”. One word itself is not particularly secure, since it would yield to a simple dictionary attack. Thus, you should repeat this process a few times, and concatenate all phrases you generate this way. There are 6^5 = 7776 words in the Dicewords list, so feel free to exponentiate this number at will. For instance, after six rounds, you end up with one out of 7776^6 possible combinations.

Overall, following this procedure is trivial. Yet, ArsTechnica found plenty to gush about. Mira Modi is quotes with,

I wanted to make it a public thing because I wasn’t getting very much money,” she said. “I thought it would be fun to have my own website.”

Each time an order comes in, Modi rolls physical dice and looks up the words in a printed copy of the Diceware word list. She writes—by hand—the corresponding password string onto a piece of paper and sends it by postal mail to the customer. (Full disclosure: I ordered two.)

That sounds like an amazing business indeed. In fact, she does not even generate enough money to cover the cost of a domain name and hosting. Considering that she has getting free publicity by her mother, it’s not a very impressive business at all. Yet, this does not keep the fawning journalist from demonstrating to the world his naivety:

If she kept busy at it full-time, Modi would be raking in about $12 per hour—fully one-third more than New York state’s $8.75 minimum wage, which is set to go up to $9.00 on December 31, 2015. As of now, she said she’s sold “around 30” in total, including in-person sales.

Oh, so she barely sells any passwords, but if she suddenly managed to sell more passwords in a day than she sold since starting her business, she would beat minimum wage. Needless to say, if she ever had to hire employees, in case her business enters hockey stick growth, she won’t even break even, assuming labor, materials and shipping aren’t for free. I found the numbers amusing, though, because they suggest that it takes her ten minutes to generate a pass phrase. Guess what also takes about ten minutes? Writing a script that does this for you automatically and which can spew out pass phrases until the cows come home. In very straightforward Python, it looks like this (also on Github):

from random import randint

WORDLIST = "diceware.wordlist.asc.txt"
PARTS    = 6

def createPhrase(dct, nums):
    result = ""
    for i in range(0, nums):
        result += dct[throwDice()] + " "
    return result

def throwDice():
    result = ""
    for i in range(0,5):
        result += str(randint(1,6))
    return result

def main():
    with open(WORDLIST, "r") as ins:
        diceDict = {}
        for line in ins:
            (nums, word) = line.split()
            diceDict[nums] = word
            
    print createPhrase(diceDict, PARTS)
        
main()

A clear giveaway that little Mira Modi does not really grasp her business, which was arguably all the creation of her mother anyway is that the ArsTechnica article shows the following picture:

Can publicly available information be top secret?

Can publicly available information be top secret?

That’s right, a publicly available list is declared “top secret”.

What I find grating about articles like this is that they celebrate non-achievement. It would be far more impressive to find an 11-year old who is able to write a simple program that would automate this task, and if said 11-year old had a well-connected parent, we would surely see articles in ArsTechnica about them as well, which would be just as misplaced because a modicum of precocity is hardly worthy of a story. This ties into a much bigger problem of today’s education at the primary and secondary level. Pupils are coddled, and don’t really learn to exert real effort. But those who continue their education at a decent university and who do not enroll in a fluffy subject will have a rude awakening. After covering Diceware and hinting at the downsides of today’s education, it’s now time to move on to talk about “security theater”.

I mentioned that a computer program would be able to automate the task of generating pass phrases. The Diceware webpage does not agree, but it is mistaken:

Can I use a computer to generate Diceware passphrases?

Generating truly random numbers using a computer is very tricky. The so-called random number generators that come with most programming libraries are nowhere near good enough. For most users dice is by far a better way to select passphrase words.

This is nonsense. To be more polite, it is an example of FUD. True, the randomness in your machine is not truly random. Using a computer program for generating Diceware phrases, though, is safe for precisely the reason that it is simply implausible that an attacker would be able to recreate and maintain the exact same state (!) your machine was in when you ran a Diceware generator. If an entity was as powerful as that, it surely would find more efficient uses for their resources.

FUD seems to be the forte of Arnold G. Reinhold, the creator of Dicewords, as he gives the following advice:

For maximum security make sure you are alone and close the curtains. Write on a hard surface — not on a pad of paper. After you memorize your passphrase, burn your notes, pulverize the ashes and flush them down the toilet.

This would have worked in the world of James Bond in the 1960s. However, today’s super villains of course have cameras installed everywhere, so you better construct the resulting passphrase entirely in your head. Indeed, once you try them on, tinfoil hats are somewhat comfortable. Let’s get back to reality, though. In case you have not been following the news for a couple of years, you should know that privacy on the Internet does not really exist anymore.

Widespread electronic surveillance is commonplace. For instance, the NSA has direct access to Google, Facebook and Apple, as well as others, though their PRISM program anyway. (Here is an article from The Guardian on PRISM.) Thus, they would not need to “hack” your password. Also, there have been several cases of backdoors. So, despite advances in cryptography, it seems that the intelligence agencies of the world would simply sidestep the issues of passwords altogether by getting access to your data in some other way. This does not mean that all your passwords should be “password”, though. Thus, let’s hope that Mira Modi always draws the curtains before generating Diceware pass phrases and does not communicate with her customers electronically.

Compiling Agda to System Fω in Theory

In early June I submitted the final revision of my Bachelor’s thesis, with the potentially impenetrable title “Compiling Agda to System Fω in Theory”.

I wrote this thesis under the supervision of Andreas Abel (Chalmers University of Technology), who is one of the main Agda implementers.

Abstract:

We develop a theoretical foundation for compiling the programming language Agda to System Fω, which is a stepping stone towards a compiler from Agda to Haskell. The practical relevance for software engineering and the problem of providing correctness guarantees for programs is highlighted. After describing relevant λ-calculi, we specify the semantics for compiling Agda to System Fω. Finally, we illustrate those compilation rules by manually translating several Agda code examples to System Fω.

The full paper is available here:
http://gregorulm.com/files/GregorUlm.BSc.FinalRevision.pdf

An FFT (Cooley–Tukey) for a synchronous dataflow extension to Feldspar

Unfortunately I’m not able to share most of my university course work, due to our honor code. There are some exceptions, though. For instance, the last assignment in Patrik Jansson’s MSc/PhD course Advanced Functional Programming at Chalmers University of Technology is self-directed and open-ended. The general task is to “read, understand, evaluate and extend an advanced Haskell code base”, with the underlying goal of getting us students involved with an ongoing local research project, or in open-source development by contributing to one of the more popular Haskell package on Hackage.

In this article I will merely provide some background for the work we did, including relevant references. The information below should suffice to give an overview of this project.

Emil Axelsson, one of the authors of the Feldspar language [1], which is an embedded DSL for digital signal processing that is implemented in Haskell, gave a guest lecture on combining deep and shallow embeddings [2], and how this technique was used for the implementation of Feldspar.

In our project, my lab partner Niklas Logren and me collaborated with Markus Aronsson, a PhD Student in the Software Technology division in the Department of Computer Science and Engineering at Chalmers. Markus is currently working on a synchronous data flow extension to Feldspar, i.e. an extension to Feldspar that allows it to operate on streams. For details, please refer to the corresponding paper [3].

We implemented an FFT based on Cooley-Tukey. Our implementation is based on the FFT implementation that is outlined by Bjesse, Claessen and Sheeran in their paper on the hardware description language Lava [4]. Our entire code is available in my Github repository gregorulm/fft_feldspar. Markus Aronsson’s Feldspar extension is currently work-in-progress and not publicly available. Our FFT implementation, though, will be part of the eventual release.

References:

[1] E. Axelsson, K. Claessen, G. Devai, Z. Horvath, K. Keijzer, B. Lyckegard, A. Persson, M. Sheeran, J. Svenningsson, and A. Vajda. “Feldspar: A domain specific language for digital signal processing algorithms”. MEMOCODE 2010.

[2] J. Svenningsson and E. Axelsson. “Combining deep and shallow embedding for EDSL”. Trends in Functional Programming, LLNCS 2012.

[3] M. Aronsson, E. Axelsson, M. Sheeran. “Stream Processing for Embedded Domain Specific Languages”, (draft, submitted to IFL 2014).

[4] P. Bjesse, K. Claessen, M. Sheeran, S. Singh. “Lava: Hardware design in Haskell”, International Conference on Functional Programming, pp. 174–184, 1998.