PLSE Blog RSS Feed

Verilog Programs are Pure Expressions

keywords: #verilog #hardware
Verilog is a language of fundamental importance. Yet, despite that fact, it is mostly ignored in the world of programming languages (PL) and compilers research. In this post, I present one very simple fact about Verilog programs: they represent pure expressions. In explaining this, I hope to make Verilog more approachable by a programming languages and compilers audience.
Read More

The Theoretical Aspect of Equality Saturation (Part II)

keywords: #equality-saturation #program-optimization

In the last post, we showed the connections between chase and techniques developed in databases literature and tree automata literature, and how these connections help us understand equality saturation (EqSat). In this blog post, we will focus on a specific problem EqSat faces: the termination problem1, something my collaborators and I have been working on recently.

Read More

Programming in Space and Time

keywords: #space #time

While “Goto Considered Harmful” (Dijkstra, 1968) is one of the most famous pieces of writing in Computer Science, its enduring relevance to programming languages is almost wholly unappreciated or — at best — misunderstood. Historically, supporters and detractors from the original letter have addressed themselves to the conclusion that use of the goto statement should be avoided. (Including Knuth [1]) Depressingly, it took over two decades [2] before anyone bothered to empirically test Dijkstra’s claim. To the best of my knowledge, no-one ever disputed, supported, or merely considered Dijkstra’s premises and form of argument.

Read More

slice of life content in undergrad PL

keywords: #education #undergraduate-pl

Hi! My name is Matt (he/him), one of the new teaching faculty at the Allen School this fall. I’ve been given a warm welcome by the community at UW, including at PLSE – where I’ve already met some wonderful people who do all things software engineering, programming languages, and running!

Read More

The Theoretical Aspect of Equality Saturation (Part I)

keywords: #equality-saturation #program-optimization

The phase-ordering problem is a long standing problem in program optimization: Consider program \((a\times 2)/2\). A program optimizer may readily optimize the subexpression \(a\times 2\) into \(a\ll 1\) and get \((a\ll 1)/2\), at which stage it cannot optimize the program further. Or it can also realize that the multiplication and division operators can be simply canceled out, yielding \(a\). This indicates that applying one optimization may disable another optimization, but naively exploring all optimization orders can lead to a combinatorial explosion.

Read More