Least fixed points, and the grouping of behaviours

Frank Shearar wrote “Sometimes one has a set of interrelated (monotonic) recursive equations one needs to solve. An naïve implementation will recurse infinitely. Handily there’s a solution: the least fixed point. I had need of one the other day, implementing parsing with derivatives. So why bother with least fixed points? Let’s find out…”

Resumable exceptions can macro-express delimited dynamic variables

Frank Shearar wrote “We already know that delimited continuations are more expressive than undelimited ones (call/cc). We can trivially express undelimited continuations by wrapping our entire program in a reset marker, while we need a mutable cell to express delimited continuations using call/cc. There’s another very handy construct in programming that uses the call stack: dynamic variables. We…”

Fun with Blocks

Frank Shearar wrote “We’ve already seen that Smalltalk has a very lightweight syntaxes for closures: [:x | x] for the identity function, for instance. We’ve seen them form an essential part of Smalltalk’s structure, allowing us to have all control structures part of the library rather than baked into the language. For what else might we use them?”

“Duck-finding” for testing your Theories

Frank Shearar wrote “A while ago I wrote a semi-port of Haskell’s QuickCheck. Easy enough – a property is like a test method but with arity 1, into which you inject data – potential counterexamples to your theory. In Haskell, the type system can, through unification, figure out the type of the generator required for that property. What…”

Unifying parts of structures

Frank Shearar wrote “Those with even a passing familiarity with Prolog should recognise statements like [H|T] = [1,2,3]. In particular, = here is not “is equal to” but rather “unifies with”. So that statement causes the variable H to unify with 1, and T with the rest of the list, [2, 3]. Clojure’s abstract bindings provide much the…”

Translating a persistent union-find from ML to Smalltalk

Frank Shearar wrote “When I wrote my unification library a while back, I tried to add an “or matcher”. That is, something that would allow | matcher mgu | matcher := OrUnifier     left: (TreeNode left: #x asVariable)     right: (TreeNode right: #x asVariable). mgu := matcher =? (TreeNode left: (Leaf value: 1)). mgu at: (#x…”

Clojure to Smalltalk translation notes

Frank Shearar wrote “Clojure has an interesting implementation of a Huet-style zipper. I started translating it to Smalltalk, and in the process discovered a number of things not really related to zippers. Given that the end result ends up looking very similar to something we’ve already seen , let’s talk more about the translation process itself.”

Checking Squeak Quickly

Frank Shearar wrote “The good fellows in Haskell land came up with a nice idea one day: instead of relying on a programmer writing well-thought out tests, with test data designed to flush out edge cases, they realised that people aren’t very good at finding bugs in their own code. The real world is too random, too crazy,…”

PetitParser Bon Mots

Frank Shearar wrote “I’ve been working with parsing number literals in Smalltalk recently. I’ve discovered a small collection of tricks not entirely explained in PetitParser’s otherwise excellent documentation, so I thought I’d share my experiences:”

Rolling your own control structures with lambdas

Frank Shearar wrote “Squeak Smalltalk ships with an, ahem, mildly controversial feature: a case statement. Case statements usually evoke “but that’s not OO!” from people, usually with good reason: a complicated case statement only gets less understandable as it evolves, while a State implementation’s complexity remains more or less constant. (You can concentrate on only the bit you…”

Un Petit Haskell

Frank Shearar wrote “It’s time to visit another Smalltalk PEG parser. We’ve seen OMeta2, and now it’s time for a rather different approach to parsing. Lukas Renggli wrote PetitParser, a parser library based on parser combinators.”

The Other Kind of Zipper

Frank Shearar wrote ““A zipper is a[n editable] suspended walk.”[1] Take a map: it takes some traversable structure, executes a function on each element, and returns a new traversable structure with the values obtained by applying the function to the elements of that structure. Define a function that returns a pair (value, partial continuation) where the partial continuation…”

Zipping over Magritte-described Objects

Frank Shearar wrote “Magritte is a metamodel description framework for Smalltalk, that is, a way of describing your domain objects. Having a description of your domain objects allows you to do a bunch of neat things, like automatically building a Seaside form for displaying an object. If you’ve used C#’s ASP.Net MVC framework, you might think of the…”

Unification: pattern matching, but twice as nice!

Frank Shearar wrote “Languages like ML, Newspeak, and Scala support pattern matching: it’s a bit like a case/switch statement, only instead of matching on a series of boolean conditions you switch on the shape of some variable. But Prolog goes twice as far: Prolog uses unification. What’s that, you ask?”

Algebraic Data Types and OMeta2

Frank Shearar wrote “There have been a recent rash of grammar libraries written for Smalltalk. We have at least three Parsing Expression Grammar (PEG) libraries: OMeta2/Squeak, Xtreams and PetitParser. Today we’re going to look at OMeta2.”

Balancing trees

Frank Shearar wrote “Have tree. Will use zipper to mutate. Much rejoicing. Only, when you have a binary search tree, you’d like to have a balanced tree so you get the O(lg n) search rather than a list masquerading as a tree (so all nodes only have left or right children), which would give you O(n) search. What…”