Innovation in computer programming

Researchers in Tufts School of Engineering frequently invent new ways to approach old problems. Associate Professor Norman Ramsey of the Department of Computer Science recently published a paper that outlines a more efficient method to convert arbitrarily complex computer programs to use structured control flow. The higher-level the programming language, the farther removed it is from a format that a computer can understand, such as binary code. Programs that are written in a high-level language require a compiler, which takes the code and translates it into a lower-level format that the computer can understand.

A key element of most low-level formats is the goto instruction, which tells the program to jump to another part of the code. But formats designed for the Web, such as Javascript and WebAssembly cannot express the goto instruction and can accept only structured control flow. In 1973, researchers devised a workaround to translate goto programs into structured control flow programs, but the method took three passes to implement successfully and was not intuitive to use.

Ramsey iterates and improves upon this method, reducing three passes down to one pass to successfully translate goto programs into structured control flow. His method uses techniques from functional programming including recursive functions and immutable abstract syntax trees and ultimately enables the compiler to target Web formats. His method is currently included in the open-source Glasgow-Haskell compiler, which is part of the Haskell programming language.

Ramsey’s paper, titled "Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow (Functional Pearl)," was published in the Proceedings of the Association for Computing Machinery on Programming Languages. He presented the paper at the International Conference on Functional Programming as a ‘functional pearl’ or an interesting case study within the field that holds potential to be applicable to a range of scenarios.

At Tufts, Ramsey works on functional programming and low-level programming-language infrastructure including dataflow analysis and optimization, code generation, debugging, linking, binary translation, register allocation and more.