uberpyro / prowl

WIP stack language that uses regex for control flow

Introduction

The Prowl Language is a statically-typed stack-based programming language that draws from a wide range of inspirations, mainly functional, logic, and stack-based languages. However, the language is unique with its powerful program combinator system. Prowl exploits a homomorphism between string concatenation and concatenative languages that allows regex to be used as a computational and mental model for control flow. This model provides a rigid framework to solve combinatory and constraint problems (in addition to general purpose programming) yet retains performant translations into DFAs due to the regex base. With stacks for data and regex for control flow, Prowl provides a unique but ergonomic way to think about hard problems.

Prowl has 3 major influences that you should know about:

• The Kitten Language
• The Vinegar Language
• Oniguruma Regex

Prowl mirrors Kitten’s ambition in modernizing the concatenative paradigm with syntactic and semantic ML features. Prowl sheds its concatenative purity and imports key quality of life features such as infix, lexically scoped variable bindings, anonymous functions, destructuring, and pattern matching to elevate the language’s productivity and expressivity. From OCaml, we borrow a lot of syntax, binding operators, ML modules and functors, and even the plan for modular implicits. Indeed, Prowl does not shy away from the deeper developments of other languages – we also borrow some of Haskell’s common abstractions such as monoids, functors, and monads, and plan to use the modular implicits feature to support them and their infix operators. We also take significant inspiration from Joy, importing it's closures, stack combinators, and recursive combinators – the latter modified to better accomodate Prowl's spin.

Prowl also draws inspiration directly from Vinegar and Oniguruma Regex in its unique and powerful descriptions of control flow. It all starts with Vinegar’s key innovation:

• All operators can fail

While typical concatenative languages have functions of (in Haskell notation) Stack -> Stack, Vinegar has functions of Stack -> Maybe Stack. Every function can fail but can be handled with the alternation operator |, so that alternate branches can be tried if one fails. It’s an interesting novelty and variation of the paradigm, and it’s definitely worth checking out in its own right. However, Prowl takes things one step further by innovating that functions should be Stack -> List Stack, where the list is actually lazy in practice. This is to say that all functions produce some number of viable future stacks based off some past stack, and that we are guiding a search down these spaces, adding and pruning stacks as we move along.  We can then use concatenation to compose these functions, alternations to search down one list before the other, and then define quantifiers such as Kleene star in terms of the existing definitions of concatenation and alternation. Kleene stars and n-times quantifiers in regex are like while and for loops in imperative programming, and so it actually forms a nice basis to program in. And it’s efficient – regex control flow can target DFAs where edges are programs rather than characters, enabling some unique optimization opportunities, yet we retain Turing completeness with heap-allocated lists.  

Prowl is an ambitious language with a unique spin but aims to remain fully productive. If this sounds like it interests you, give the tutorial a look, as the parts are described in much greater detail.