Implement a Functional Language in Scala

What attendees will learn

Dive deep into the fascinating world of functional language implementation! This workshop will guide you through building a simplified subset of Dhall, a purely functional language with a Haskell-like syntax, entirely in Scala. You'll gain practical experience translating the often-abstract academic notation for type-checking and semantics into concrete, working code. We'll provide sample code for exploration and hands-on exercises as Scala notebooks, making the learning process interactive and engaging.

Target audience

• Scala developers interested in language design and implementation.
• Programmers curious about the internals of functional programming languages.
• Individuals looking to deepen their understanding of type systems and semantics.

Prerequisites

• Solid understanding of Scala fundamentals. We will be using Scala 2.
• Familiarity with functional programming concepts (e.g., immutability, pure functions, higher-order functions).

Requirements

A laptop with Scala, jupyter notebook, “almond” Scala 2.13 kernel installed. Or, the “ammonite” installed for Scala 2.13

Length

This is a half-day workshop, from 9AM - 2PM.

Agenda

Part 1: Foundations of μDhall (50 minutes) 9 am

• Introduction to μDhall: A brief overview of Dhall and the simplified subset (μDhall) we'll be implementing.
• Concrete Syntax Trees: Understanding the type of concrete syntax trees for μDhall expressions, covering both types and values.
• De Bruijn Indices: Demystifying de Bruijn indices and implementing essential operations with them.
• Hands-on Exploration: Time to try out some initial code and get comfortable with the concepts.

Break (10 minutes)

Part 2: Parsing and Type-Checking (50 minutes) 10 am

• Grammar Definition: Exploring the ABNF grammar definition for μDhall syntax.
• Parsing with Fastparse: Implementing the parsing of μDhall syntax using the fastparse library.
• Type-Checking Rules (Gamma-notation): How to understand type-checking rules in the Gamma-notation, and how to implement them in Scala.

Break (10 minutes)

Part 3: Evaluation and Normal Forms (50 minutes) 11 am

• Small-Step Reduction: Specifying evaluation into a "normal form" using small-step reduction notation.
• Scala Implementation of Evaluation: Implementing the evaluation process in Scala.
• Tests and examples: Getting intuition about "normal-form programming”.

Break (10 minutes)

Part 4: Optimizations and Advanced Topics (50 minutes) 1pm

• μDhall to Scala Conversion: Converting μDhall code to a corresponding Scala value.
• Simple Optimizations: Implementing basic optimizations, such as caching.
• Open Hacking & Exercises: Time for participants to apply their knowledge by hacking on the language or working on provided exercises.

Exercises will include (but are not limited to):

• Implementing alpha-conversion.
• Adding more syntax rules for operations and/or constants.
• Implementing more advanced type inference.