Overhaul of Standard ML of New Jersey System Wins Special IFL Award

August 05, 2021

In the fast-moving world of computer science, very few programming languages live long enough to measure their age in decades instead of years. But while it may not be a common sight in today’s programming bootcamps, Standard ML has been an enormously important and influential language since its original development in the late 1980s. As one of the first formally-defined functional programming languages, it has been used ever since for commercial applications, research, and education. 

One prominent implementation , Standard ML of New Jersey (SML/NJ), was created in the 90’s by a team at Bell Labs and Princeton University including John Reppy, today a Professor of Computer Science at the University of Chicago. In the 30 years since SML/NJ debuted, Reppy has stayed active in the open source project’s constant renovation, a process he compares to the legendary “Ship of Theseus” puzzle. In a new paper presented earlier this year at the 2020 Implementation of Functional Languages (IFL) conference, Reppy and his former PhD student Kavon Farvardin described one of their most substantial upgrades yet: a new backend utilizing the LLVM compiler infrastructure.

That work and the model it set for future programming language updates earned Reppy and Farvardin the Peter Landin Prize, awarded to the symposium’s best paper each year and named for one of the fathers of functional programming. Besides making sure SML/NJ will continue to work seamlessly with modern computer architectures such as the increasingly ubiquitous ARM processor, Reppy hopes that the paper will help other language implementations .

“There are people who are going to come along and want to port their language to use LLVM, because writing code generators and register allocators and all that is a very time-consuming activity, and it's not necessarily something that's going to be on their research path,” Reppy said. “So this paper provides a useful roadmap in terms of how to do this, explaining a lot of the decisions that had to be made, and the design space and techniques needed to get LLVM to do what one wanted it to do.”

The new paper follows on from previous work by Reppy’s group: a paper where Farvardin and Reppy described the implementation of LLVM for Manticore, an experimental parallel functional programming language developed by Reppy and Matthew Fluet. Farvardin’s experience with that effort made him a useful collaborator as Reppy tackled this new challenge.

“It was kind of the opposite of the normal advisor-advisee relationship,” said Farvardin, who now works at Apple on the Swift programming language. “I was using my expertise and the work from my PhD thesis to help with the paper that John was working on.”

“Kavon was extremely helpful in terms of consulting during the implementation effort that I was working on, because for me, that was a big learning process,” Reppy said. “LLVM is this humongous system, and there's a lot of knowledge and expertise that you have to accumulate.”

Though LLVM was originally developed for imperative and object-oriented languages, it has also proved useful for functional languages such as Manticore and SML/NJ. Most valuable is its code generating and optimizing abilities, which convert programmer-written code to machine code for multiple types of processors instead of requiring separate compilers for different architectures. In the mid-90s, Reppy was part of a team that developed a code generator called MLRisc for SML/NJ, but that project ceased active development even as new CPU types — most notably the ARM processors used for chips such as Apple’s new M1 — gained in popularity. 

“The motivation for this work was the fact that we have new architectures coming along like the ARM, and we didn't want to invest the resources to do a complete rewrite of the code generation infrastructure,” Reppy said. “The last port that we did was for 64 bit Intel processors, 12 or 15 years ago, so we needed to modernize.”

Reppy hopes to release the new-backend version of SML/NJ before the fall quarter, when he uses the language to teach his “Compilers for Computing Languages” course. In the meantime, he is honored that the work received an award named for a computer scientist who he holds in high regard.

“Because I've been a functional programmer for essentially 40 years, winning a prize that was named for Peter Landin is very special,” Reppy said.