"Concatenative programming and stack-based languages" by Douglas Creager

The speaker begins by expressing gratitude for being invited to present at the final Strange Loop and Papers We Love event. They highlight their passion for programming languages and their impact on programming thinking. The focus of the talk is on stack-based languages, which are less familiar to many developers but are significant to understand. The speaker clarifies that the talk will not be about a specific stack-based language like Forth but will explore the characteristics common to this family of languages. They also mention the importance of citations in the talk, providing references for further learning.

The speaker compares stack-based languages with more mainstream, name-based languages. They explain that stack-based languages do not use names for values, which is their defining characteristic. Using the Pythagorean theorem as an example, the speaker demonstrates how a simple Python program that calculates the hypotenuse of a right triangle would look in a stack-based language. They contrast the complexity of managing environments and frames in name-based languages with the simplicity of stack-based languages, which operate on a linear sequence of instructions.

The speaker delves into the execution state of stack-based languages, emphasizing the simplicity of a stack of values. They illustrate how instructions in these languages are executed from left to right, with integer literals pushing values onto the stack and operations like addition being implicit. The speaker introduces additional instructions like 'dupe' and 'swap' to handle more complex operations, showing how they can be used to translate a Python program into a stack-based language equivalent.

Building on the previous examples, the speaker discusses how to abstract logic in stack-based languages, similar to how functions are used in Python. They introduce the concept of quotations and the 'apply' instruction, which allows for function-like invocation in stack-based languages. The speaker demonstrates how to use these features to perform calculations for different triangles, highlighting the need for specific instructions to manipulate the stack order for correct execution.

The speaker explores the meaning of stack programs, discussing how they can be described in English and then more rigorously in mathematical terms. They introduce the concept of stack effects, originally developed in the context of the Factor programming language, to describe the impact of a program on the runtime stack. The speaker also provides a mathematical definition of a program as a stack transformer, explaining how each instruction affects the stack.

The speaker addresses the Turing completeness of stack languages, explaining that any computational process can be expressed in a stack language if it is Turing complete. They compare stack languages to the Lambda calculus, a known Turing-complete language, and discuss the process of reducing Lambda calculus to stack language. The speaker also touches on the Church encoding for numbers and the use of combinatory logic to eliminate names in Lambda calculus, leading to a stack language equivalent.

The speaker discusses the concept of associativity in stack language, explaining how syntactic concatenation of program text corresponds to function composition in the stack's semantics. They highlight the importance of this property, which allows for parallel execution of program parts without affecting the final result. The speaker also demonstrates how this property can be leveraged in compiling stack language into assembly, enabling parallelism in execution.

In the final part of the talk, the speaker introduces UXN, a real-world stack-based language. They mention the language's capabilities and the community around it, focusing on demonstrations of programs written in UXN, such as a snake game and a clock. The speaker emphasizes the simplicity and elegance of stack-based languages, suggesting their suitability for constrained devices and their potential for implementation in various environments.

The speaker concludes the talk by summarizing the key points discussed about stack-based languages. They reiterate the simplicity and theoretical appeal of these languages, as well as their practical applications. The speaker thanks the audience for their time and participation, ending the presentation on a positive note.