Functional programming trivia from Scalathon

By popular request, here are the questions and answers from the quizzo at Scalathon. I've formatted them so you can try the questions for yourself! The questions were written by Ben Karel, Randall Schulz, and yours truly. I put the final wording on all the questions, so any mess-ups are my fault alone.

Round 1

1. What language is most closely associated with the actors model of concurrency?
2. Who wrote "Purely Functional Data Structures"?
3. Place the following languages in chronological order, from oldest to newest: Lisp, Fortran, Cobol.
4. Two of the three primary techniques of giving formal semantics to a programming language are operational and denotational semantics. What is the third of the trio?
5. What term am I defining? "A tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute."

Round 2

1. Can you have functional programming without static typing?
2. Who invented LISP?
3. What is the name of the type inference algorithm used by Haskell and ML?
4. What is the more common name for Schönfinkelization?
5. What language is CompCert, the formally verified C-compiler written in?

Round 3

1. Analogy: Types are to values, as kinds are to what?
2. Some type systems have the feature that a type can depend upon a value. What is that feature called?
3. Name the co-author of most of the original Lambda papers (his name is the longer one).
4. According to Tony Hoare, this was "a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors." Name the language, which was (almost) based on the fully-typed call-by-value lambda calculus.
5. Peter J. Landin described the SECD machine in 1963; what language was he defining?

Round 4

1. What is the difference between a total function and a partial function?
2. Name the titles of two of the three original "lambda papers"?
3. Which of these languages is Turing-complete: SQL, The Coq Specification Language, XSLT, XML, JSON, Prolog, Ant.
4. What common higher-order function implements a catamorphism?
5. Who quipped that "Syntactic sugar causes cancer of the semicolon."?

Tie-break Round

1. The quirky bird, thrush, and mockingbird are all names of closed lambda terms, also known as what?
2. A paper called "Macaroni is better than spaghetti" was published in 1977 on efficient implementation of call stacks. Name the author, who also gave an OOPSLA speech starting only with words of one syllable, and is known for his work on Scheme and Common Lisp, among many other languages.
3. Peter Landin defined an operator to capture continuations; it shares a name with an array-based functional programming language derived from APL. What was the name of Landin's operator?
4. Compositional type inference is assured by the property of what?

Round 1 Answers
A1: Erlang, A2: A: Chris Okasaki, A3: Fortran (1956), Lisp (1958), Cobol (1959), A4: axiomatic semantics, A5: "type system"

Round 2 Answers

A1: Yes; A2: John McCarthy; A3: Hindley-Milner [Hindley-Dumas was also accepted. Daniel Spiewak registered his strong protest that the question as worded does not make sense. It confuses type systems and type inference algorithms.]; A4: Currying; A5: Coq

Round 3

Answers

A1: Types; A2: Dependent typing; A3: Gerald Jay Sussman; A4: Algol 60; A5: ISWIM

Round 4

Answers

A1: Partial functions are undefined for some argument values. [Many other answers were accepted since the term "function" is used in many contexts.]; A2: [This question should have been worded differently. We only wanted papers with the words "Lambda the Ultimate" in the title, so any three of these four counted: "Lambda The Ultimate Imperative", "Lambda The Ultimate Declarative", "... Lambda The Ultimate GOTO", "... LAMBDA the Ultimate Opcode"] A3: XSLT, Prolog, Ant; A4: Fold/reduce; A5: Alan Perlis

Tie-break Round

Answers

A1: combinators; A2: Guy Steele; A3: J; A4: principal typings

Scalathon 2011 recap

The idea for Scalathon sprang into my head on a Thursday four months ago. Brian Clapper (organizer of the Philly Area Scala Enthusiasts, and the consultant behind ArdenTex) and Jamie Allen (Chariot Solutions) were quickly on board. By Monday we had a website and were actively looking for sponsors and speakers. My primary motivations were, at first, to simply improve the Scala ecosystem and have some fun. Later on, Scalathon planning took on new dimensions as I learned more about the Scala community and development process.

The event started on Friday with Adriaan Moors' talk to Penn's PL Club on Dependent Object Types. Following the talk we had a lunch with the Scalathon attendees, PL Club, and many Penn professors, including the programming languages group (Benjamin Pierce, Steve Zdancewic and Stephanie Weirich). After lunch we launched into a documentation spree run by Scala's new doc czar Heather Miller. She explained the system for contributing documentation on GitHub. Paul Phillips was on hand to promptly merge pull requests.

Unlike most hackathons, Scalathon wasn't a competition. Well, except for Friday night which had a ferocious functional programming quizzo (Philadelphia pub trivia contest) between groups from Scalathon and Philly Lambda. After the normal four rounds, two teams (Daniel Spiewak, Ricky Nilsson, and Runar Oli Bjaranson on team forall a . a, and Daniel Sobral, Iain McGinniss, Pedro Furlanetto, and Seth Tisue on team _|_) were tied for first place. A tie-break round ensued after which forall a . a emerged victorious by one point. (Winning question, Q: Compositional type inference is assured by the property of what? A: Principal typings).

Saturday and Sunday brought the main events, and over 100 developers from Belgium, Brazil, Canada, France, Germany, Russia, Switzerland, Sweden, the United States, and the United Kingdom). In addition to dozens of representatives from major Scala libraries, Typesafe and EPFL sent several representatives each. The format of the event itself was a hybrid of a Scala Days-style conference and a traditional hackathon. At all times there were presentations in the auditorium (Saturday project talks and Sunday Scala enrichment talks) and hacking outside the auditorium. Many attendees told me they were relieved that no one was forced to sit through any particular talk or hack to the point of exhaustion.

Saturday and Sunday also had a few special lunches: Scala community leaders, Scala commercial users, and MongoDB users. Donald Fischer, CEO of Typesafe, flew in from Boston specifically to meet the community and hear from the commercial users. Minutes from these meetings are being expanded and prepared for discussion with EPFL, Typesafe, and the community. Sneak preview: at the community leaders lunch the documentation situation was extensively discussed with Heather, who will be preparing a new centralized, searchable site for the best Scala documentation on the Internet.

I hope Scalathon's lasting accomplishment will be bridge-building. Bridges between community leaders, industry leaders, Typesafe, and EPFL. Although there were plenty of commits, there were innumerably more conversations, plans, jokes, and business cards exchanged that will influence the Scala ecosystem for years to come.

Photos are already up (Friday, Saturday, Sunday). Stay tuned, videos will be up very shortly, to be announced on the scala-announce listserv.

Scala Community Petition

After many discussions with individuals in the community about how to improve the Scala development process, I've decided to create a democratic forum for people to present suggestions.
Please see our Google Moderator page to see suggestions for the Scala core developers. You can make your own suggestions, as well as voting on and replying to others.

The leading suggestions will be discussed with the various Scala insiders who attend Scalathon. Plus the whole Internet.

This is being done in a positive, friendly spirit. Scala needs the community. So let's improve Scala!

My GNOME customization script

I find myself reformatting my computers dozens of times a year. Don't ask why. So after many lost hours I created a script that completely sets up a new Debian or Ubuntu computer. It sets every bit just the way I like it. Unfortunately I can't post that entire script because it's deeply entangled with various passwords, system-specific info, etc. So as a compromise I teased out my GNOME customization stuff and am posting it as a standalone script.

There are two things you might find useful about the script:

1. It makes gconf changes as root, something that's tricky to do. While that isn't really necessary for GNOME customization, my full setup script needs to run as root.
   
2. It incorporates a bunch of customizations, some of which you may wish to automate too.
   

Can’t see the code?

Case classes with toStrings that print label names

Overview
The Labeled ToString project provides several traits you can mix into case classes in order to get toString representations that include parameter labels. That means you get Person(name=John Doe,age=30) instead of Person(John Doe,30).

Example
Here's a normal case class:

  case class Person(name: String, age: Int)
  Person("John Doe", 30).toString
  //result is "Person(John Doe,30)"

Here's our labeled case class:

  import com.yuvimasory.tostring._
  case class Person(name: String, age: Int) extends LabeledToStringDef
  Person("John Doe", 30).toString
  //result is  "Person(name=John Doe,age=30)"

Choosing a trait
The com.yuvimasory.tostring package provides three traits: LabeledToStringDef, LabeledToStringVal, and LabeledToStringLazyVal. They override the default case class's toString method with a def, val, and lazy val, respectively.

• If you're not sure which to use, start with LabeledToStringDef, which works in all cases.
• Consider LabeledToStringVal if you know the case class's parameters are either immutable (e.g., primitive types, immutable collections), or have string representations that never change (e.g., arrays).
• Try LabeledToStringLazyVal if you meet the criteria for LabeledToStringVal and want lazy initialization.
• Both of the *Val traits may run slightly faster (since they don't have to recompute toString every time it's needed) at the cost of more memory usage.
• You must use LabeledToStringDef if your case classes are Squeryl tables. If you don't Squeryl will generate bogus SQL.

Performance
The ToString traits use Apache Commons Lang under the hood, which uses reflection to find the parameter lables. Surprisingly, there does not seem to be any performance cost for this. In fact, using these traits actually results in code faster than the default case class toString. Try the tests yourself by running sbt run.

Warning

• These traits do not produce the right strings in the REPL yet due to the way the REPL wraps code and mangles names.
• These traits do not work if you add bodies to your case classes (i.e., additional methods or fields).

Detect Scala version at run-time

Thanks to Josh Suereth for this one.

Update 1: add stainsby's improvement.
Update 2: add Ismael Juma's improvement.
Update 3: add Samuel Tardieu's improvement.

Can’t see the code?

Scalathon - how you can help

Today marks the "official" announcement of Scalathon, even though people have been eagerly tweeting about it for days now.

This event was born in no small part from my frustration in finding new projects and collaborators. I don't know how you all do it, but I never seem to find the right group to work with that wants to work with me too. I'm hoping Scalathon will change all that. Putting 100 of the best Scala developers in a room for two days should make it easy for anyone to give something back to the community. Or at the very least have a good time trying.

Some other idealistic goals for the event are:

• Improving scalac and scala-lib documentation. Once logistics are worked out with the core team I'm hoping to announce a documentation spree on Friday, July 15 for anyone who wants to make this shindig last 3 days. Stay tuned. Anything on Friday will be separate from the hackathon and totally optional.
• Putting a face on the core team. Until a few weeks ago I didn't even know who was *on* the core team. Sure there was Martin. And uh ... After Scalathon you'll know them, their favorite text editors, and their beers of choice. And what the hell does a Swiss accent sound like anyway?

The Scalathon organizers are doing everything they can to make this event a success. But you can help too:

• We need sponsors! We'd love to fly out the entire EPFL team, issue travel grants to student Scala hackers from Germany and Australia, provide meals at the event, etc. But that costs a lot more money then we're getting from the measly $35 registration fee. We're counting on the Scala community to try and hook us up with sponsors. Can you help us?
• Send someone to represent your Scala project. We'd like to have *every* major Scala library represented at the event. All you need to do is give a quick talk on Saturday aimed at helping newcomers develop your project.
• Volunteer to give a Sunday enrichment talk. Those NE Scala videos are pretty awesome, am I right? We'll be posting our talks too. Now we just need some more awesome speakers.

I want to thank PHASE, especially Brian Clapper and Jamie Allen for agreeing to be my co-conspirators. Also special thanks to Daniel Spiewak, whom we tricked into joining the organizers listserv and accepting assignments. Logo by Felice Ford. Finally, a big thank you to Martin Odersky and Josh Suereth for enthusiastically getting behind this idea.