Thinking > story
Originate Scala Days Challenge

Scala Days is the premier Scala Conference, making its fifth annual debut in Berlin on June 16th, 2014. 

To add a little fun to this year's conference, we have put together a challenge.  Here is how it works:

  • The Originate Scala Architects have come up with a challenge (below) that is open to all attendees at Scala Days 2014.
  • Email your submission to scaladays@originate.com by 11:59PM on Sunday, June 22nd.
  • We will run your code through a set of test inputs varying in size and complexity. You will be rated based on the correctness of the output, the quality and elegance of your code, and the overall performance.
  • First place will receive $1000, and second place will receive $500.

We are excited to be a part of this growing community. We are looking forward to several days of learning and networking with some of the best in the business! 

Scala Days 2014 Challenge:

Introduction:

Since you are at Scala Days, you surely love function composition. Because Scala is an applicative language, function composition is accomplished by applying the results of functions to other functions. Applicative composition is the most common type of composition in functional languages. There are, however, languages that allow composition through other means.

A concatenative language is a language where functions are composed by simply concatenating, or juxtaposing them. For example, if 'dup' is an operation that duplicates its argument, and '*' is an operation that multiplies two arguments, 'square' can be expressed as 'dup *'. Concatenative languages are almost always implemented as stack languages, where arguments and return values are simply pushed onto and popped off of the stack. Concatenative operations can be thought of in purely functional terms as functions that take a stack and return a new stack, and programs are then just stack functions composed from simpler stack operations.  

The Challenge:

Implement a purely functional interpreter for a type-safe concatenative language in Scala. You should be able to represent arbitrary programs as Scala expressions, and be able to perform the computation that the program expresses. Start with simple operations like 'dup' (duplicate the top value on the stack), 'swap' (swap the top two values on the stack) and 'drop' (discard the top value on the stack), then add arithmetic operations. Bonus points: add boolean operations and conditional branching.

Examples:

  • '3 dup *' should calculate the product of 3 and 3, leaving 9 on the top of the stack.
  • '3 4 dup * swap dup * +'  should calculate the sum of the squares of 3 and 4, leaving 25 on the top of the stack.

Submission:

Email (attach) your source code and any tests to scaladays@originate.com by 11:59PM on Sunday, June 22nd. If you have questions, you can email those as well. Any answers provided will be posted here, so check back often. Good luck!

Questions and Answers:

- "How do you expect a type-safe interpreter will behave? Could you give an example around that?"

A type-safe interpreter would only support operations on the correct type of stack, e.g. a "+" operation needs a stack with 2 numbers on top, and "swap" needs a stack with at least 2 values. Ideally, attempting to run the interpreter with the wrong type of stack would fail to type-check.

- "What types should be supported by the language?"

The language should support numbers, at least, but ideally any Scala type would be supported.

- "By boolean operations you mean AND OR XOR on booleans?"

Yes.

- "Should the conditional logic look like: '2 3 gt "2 is greater than 3" "2 is not greater than 3" ifelse', provided the language would support string type with literals quoted with ""?

Yes, that makes sense. Ideally each branch would support multiple operations.

Update from Juy 2014: Congratulations to first place winner Stefan Plantikow and second place winner Noel Walsh!

Recent Posts

Let's talk.

Give Us a Call
(800) 352-2292
Business Inquiries