The plan-execute pattern(mmapped.blog)
mmapped.blog
The plan-execute pattern
https://mmapped.blog/posts/29-plan-execute
80 comments
Indeed plans get hard when the plan has to be dynamic. Pulumi and terraform have similar troubles.
Cast that thought in terms of state. If all the state can be represented up front then plans are great. But if the understanding of the problem changes half way through a project and previously un-identified state is found during the runtime then a plan-execute pattern will get ugly quickly.
It is good to name things, but the challenge to manage isn't in the implementing of a plan-execute architecture. It is in identifying the threshold where there is enough runtime state in the problem domain that a plan-execute architecture can't be sustained.
It is good to name things, but the challenge to manage isn't in the implementing of a plan-execute architecture. It is in identifying the threshold where there is enough runtime state in the problem domain that a plan-execute architecture can't be sustained.
This is a similar pattern to Terraform, correct? (Plan/Apply). I like this pattern, however, when implementing it into automation it presents a conundrum. Often, code will be checked into a repository with a "plan" attached to it. Great. Merge after plan is approved, then automation executes the plan. However, lots of providers will only show errors on the "execute" phase (e.g., on apply, "resource already exists" errors, etc.), leading to a ridiculously slow feedback loop of having to open new PR's, go through all approval chains again, merge, execute plan again. Debugging a simple issue like a misnamed variable can take days this way.
I have yet to see a graceful work flow here in a production environment and would love to hear about one. (No I will not use terraform cloud)
I have yet to see a graceful work flow here in a production environment and would love to hear about one. (No I will not use terraform cloud)
It's more manageable to have automation (i.e., Atlantis) do the apply on the open PR and then only merge if it succeeds. You have to rely on the locking feature of Atlantis to avoid conflicts, but it's worked pretty well at scale at Enova (~50 Terraform changes a day).
I’d recommend testing the Apply step in a staging environment before rolling out.
For releases, the plans don’t need to be committed to version control. Instead they can be generated in CI just before release, then put reviewing the plan on the checklist before confirming the release to prod.
For releases, the plans don’t need to be committed to version control. Instead they can be generated in CI just before release, then put reviewing the plan on the checklist before confirming the release to prod.
[deleted]
I love this pattern. I agree with the author that design patterns that only exist because, say, your programming languages doesn't have function types, aren’t worth writing a book on.
This pattern seems like a specific application of the general idea to favor data structures over logic. If you manage to make a clear datastructure that encapsulates all the different ways in which your data/users/etc might behave, the implementation of the logic is often very straight forward. Conversely, if your data structure is either too generic or too specific, you end up having to code a lot of special cases, exceptions, mutable state and so on in the logic to deal with that.
This pattern seems like a specific application of the general idea to favor data structures over logic. If you manage to make a clear datastructure that encapsulates all the different ways in which your data/users/etc might behave, the implementation of the logic is often very straight forward. Conversely, if your data structure is either too generic or too specific, you end up having to code a lot of special cases, exceptions, mutable state and so on in the logic to deal with that.
This pattern has several other advantages that are worth mentioning:
- You can attach the plan to your Change Management, both for documentation and approval.
- You can manually edit the plan.
- The plan can be processed by other tools (linting, optimizations).
- The "complexity" of the pair planner+executor is often lower than a monolithic algorithm (above a certain size).
- Having a side-effect-free planner makes testing so much easier.
The big downside, of course, is that you're building a VM. You'll have to design operations, parameters, encoding. And stacktraces will make much less sense.
My rule of thumb is to use plan-execute for scripts that combine business logic with destructive operations or long runtime.
- You can attach the plan to your Change Management, both for documentation and approval.
- You can manually edit the plan.
- The plan can be processed by other tools (linting, optimizations).
- The "complexity" of the pair planner+executor is often lower than a monolithic algorithm (above a certain size).
- Having a side-effect-free planner makes testing so much easier.
The big downside, of course, is that you're building a VM. You'll have to design operations, parameters, encoding. And stacktraces will make much less sense.
My rule of thumb is to use plan-execute for scripts that combine business logic with destructive operations or long runtime.
I spent the first bit of this article going "Wait isn't that just what a finite state machine is?" and then was subsequently super satisfied by the next bit where they say that this is indeed a really good way to handle the general case
Reducing program logic to a small state machine and business logic that interacts with it in predefined ways is a pattern I learned while doing asynchronous netcode for a game project, but gradually realized was applicable in a ton of places, and framing it as a robust version of a "plan-execute" pattern is really intuitive but also really powerful. Great article
Reducing program logic to a small state machine and business logic that interacts with it in predefined ways is a pattern I learned while doing asynchronous netcode for a game project, but gradually realized was applicable in a ton of places, and framing it as a robust version of a "plan-execute" pattern is really intuitive but also really powerful. Great article
It's quite sad that generał purpose language designers are not yet at the stage of daring to provide any convenient syntax for high level concepts like state machines or entity component systems.
At least in Erlang there is a standard state machine built-in module: https://www.erlang.org/doc/system/statem.html
Most of TLS support in the built-in library is implemented using gen_statem, on top of the lower level crypto primitives provided by OpenSSL, same for SSH support.
Others have built Raft using it. It's quite nice and I appreciate that it comes as a standard module.
Most of TLS support in the built-in library is implemented using gen_statem, on top of the lower level crypto primitives provided by OpenSSL, same for SSH support.
Others have built Raft using it. It's quite nice and I appreciate that it comes as a standard module.
UnrealScript has (had?) built-in syntactic support for state machines.
I think Jonathan Blow had some ideas for language support for ECS in Jai, or at least support for structure-of-array stuff. I'm not sure if it panned out.
My experience with both of those patterns is that each implementation tends to have enough unique requirements that it's hard for a language to find a sweet spot where built-in syntax can cover enough real-world use cases.
For example, off the top of my head, with state machines I've had questions like:
* Can states be defined dynamically or are they all known at compile time?
* Likewise, is the set of possible transitions fixed (and declarative) or freely specified at runtime?
* Does every instance of a given state machine always have the same set of states or do some vary?
* Can you attach arbitrary data to states? Arbitrary behavior?
* Can you attach arbitrary data to state transitions? Arbitrary behavior?
* Is the predicate logic for determining when to perform a state transition declarative and built-in, or can arbitrary imperative code cause a state transition?
* Are transitions synchronous? Asynchronous? Either?
* Can outside code observe when transitions occur in some way?
* Is the current state publicly accessible or encapsulated?
* Are states first-class objects? Are transitions?
I've tried just to build a reusable FSM library and even that wasn't very successful because there's just so much variance in each implementation.
I think Jonathan Blow had some ideas for language support for ECS in Jai, or at least support for structure-of-array stuff. I'm not sure if it panned out.
My experience with both of those patterns is that each implementation tends to have enough unique requirements that it's hard for a language to find a sweet spot where built-in syntax can cover enough real-world use cases.
For example, off the top of my head, with state machines I've had questions like:
* Can states be defined dynamically or are they all known at compile time?
* Likewise, is the set of possible transitions fixed (and declarative) or freely specified at runtime?
* Does every instance of a given state machine always have the same set of states or do some vary?
* Can you attach arbitrary data to states? Arbitrary behavior?
* Can you attach arbitrary data to state transitions? Arbitrary behavior?
* Is the predicate logic for determining when to perform a state transition declarative and built-in, or can arbitrary imperative code cause a state transition?
* Are transitions synchronous? Asynchronous? Either?
* Can outside code observe when transitions occur in some way?
* Is the current state publicly accessible or encapsulated?
* Are states first-class objects? Are transitions?
I've tried just to build a reusable FSM library and even that wasn't very successful because there's just so much variance in each implementation.
> Can states be defined dynamically or are they all known at compile time?
You can say that about classes as well, give different answer and have languages that support one of those or both.
Similar questions exist about a lot of concepts that landed in some or many languages, like objects, async, events, promises, continuations. In most of them we achieved some sort of fuzzy consensus of what their capabilities should be.
You can say that about classes as well, give different answer and have languages that support one of those or both.
Similar questions exist about a lot of concepts that landed in some or many languages, like objects, async, events, promises, continuations. In most of them we achieved some sort of fuzzy consensus of what their capabilities should be.
I actually don't think we have achieved any kind of consensus here which is why there are a proliferation of popular languages.
Concurrency is handled in wildly different ways between C/C++/Java/C# (threads), Go/Lua (goroutines/coroutines), JavaScript/Dart (async promises), etc.
Object-oriented programming is interpreted so differently by different languages that people can't even agree on what the term means. Do you have multiple inheritance or not? Are methods always virtual, virtual by default, or non-virtual by default? Is there overloading? What control do you have over inheritance? Are there interfaces or not? How are static methods handled?
Concurrency is handled in wildly different ways between C/C++/Java/C# (threads), Go/Lua (goroutines/coroutines), JavaScript/Dart (async promises), etc.
Object-oriented programming is interpreted so differently by different languages that people can't even agree on what the term means. Do you have multiple inheritance or not? Are methods always virtual, virtual by default, or non-virtual by default? Is there overloading? What control do you have over inheritance? Are there interfaces or not? How are static methods handled?
We needed a state machine to manage app startup in Ardour, and initially (since we're using C++) we used a boost library for this.
It was pretty cool - you just create a text based table describing state transitions and various methods that execute before, after and as a result of the transition, and it generates all the code for you. It was very, very quick to get things basically working with this template library.
But then ... we had to start dealing with corner cases and some fiddly little details of precisely how this FSM was supposed to work.
We still have the table in a comment in the code, because it's probably one of the easiest things to read to understand the FSM, but the implementation is now just the usual C/C++ nested switch statements.
It was pretty cool - you just create a text based table describing state transitions and various methods that execute before, after and as a result of the transition, and it generates all the code for you. It was very, very quick to get things basically working with this template library.
But then ... we had to start dealing with corner cases and some fiddly little details of precisely how this FSM was supposed to work.
We still have the table in a comment in the code, because it's probably one of the easiest things to read to understand the FSM, but the implementation is now just the usual C/C++ nested switch statements.
For both cases I think it's less that there isn't convenient syntax for it, and more that the generality of the syntax doesn't restrict you enough to enforce the pattern. For example, you can do a decent job approximating a monadic state machine system in C++14 with just optional and structs, so long as you follow the rule that all mutable state is kept in a state struct and all business logic must be in the form of functions with the signature optional<state>(const state&). Hell, you could even remove the optional if you don't consider there to be any "failure" cases, just cases that don't mutate the state
Then, you can use any container you like to keep track of your valid state transitions and not even have to use polymorphism. But of course C++ gives you many ways in which to trivially break this nice system of guarantees, including mutable lambdas, or even just implicit reliance on fixed memory addresses via explicit allocation and pointers in an external scope. This pattern is very general, so it's hard to capture in a guardrail
Then, you can use any container you like to keep track of your valid state transitions and not even have to use polymorphism. But of course C++ gives you many ways in which to trivially break this nice system of guarantees, including mutable lambdas, or even just implicit reliance on fixed memory addresses via explicit allocation and pointers in an external scope. This pattern is very general, so it's hard to capture in a guardrail
[deleted]
I would argue that the domain of language design is quite a bit lower-level than the domain of specific design patterns like state machines or ECS.
A language that wants to support ECS, shouldn't implement ECS as part of its syntax. It should provide features that allow library developers to implement ECS (in an ergonomic and efficient way).
A language that wants to support ECS, shouldn't implement ECS as part of its syntax. It should provide features that allow library developers to implement ECS (in an ergonomic and efficient way).
Why not? When defining a class I should have to be able to have implicit collection of objects of this class with each field of the class kept in its own separate array. It's about memory organisation. And languages certainly feel free to impose those with stack, heap and colocation of all fields of an instance regardless of how varied they are in meaning and usage.
mbeddr[0] has a state machine language extension. It ends up being really useful primarily because of the IDE's table view for the data flow, vs the normal case-by-case nested flow.
[0]: http://mbeddr.com/
[0]: http://mbeddr.com/
I use this pattern a lot (and I often find myself wishing I used it more). Another way to think about this is "noun-ification" (aka the Command pattern) - instead of invoking a function directly, capture all of its arguments, serialize them to some "store", then provide the ability to rehydrate them and actually run it.
Interesting you used the term hydrate because I only hear that used when talking about front-end web development (specifically Next and React) and it's a relatively new term. The "Hydration (web development)" Wikipedia article was only created in December 2020. https://en.wikipedia.org/wiki/Hydration_(web_development)
I feel like serialize/deserialize or marshal/demarshal are more common in broader computer science contexts.
I feel like serialize/deserialize or marshal/demarshal are more common in broader computer science contexts.
"Hydrate" is much older than 2020. Here's a StackOverflow reference from 2011 [1], for instance. I first heard it used around that time, for loading objects from databases (in a banking context).
[1] https://stackoverflow.com/a/4929478
[1] https://stackoverflow.com/a/4929478
I came here to say basically the same thing. To me, this reads like an example of the Command pattern, which is one of my favorite, most-used patterns.
The idea of taking some chunk of imperative behavior and reifying it into an object that can perform that behavior is very powerful:
* It allows you to attach other metadata to the object so that code can ask questions about it: "Do you perform IO?" "Can you be reverted?" It lets surrounding code introspect over operations in useful ways.
* It allows you to separate the code that creates the command from the code that performs it (what this blog post is about). This can nicely decouple "strategy"-type code from "execution harness" type code. Both of those are often fairly complex in their own right, so a pattern that lets you build a nice abstraction layer between them can be very helpful.
* It allows the command object to support multiple related operations. The most common example, which I deeply love, is implementing undo. A Command object for some UI operation can also support a separate method to undo the same operation. Your undo stack is then just a list of these Command objects.
The idea of taking some chunk of imperative behavior and reifying it into an object that can perform that behavior is very powerful:
* It allows you to attach other metadata to the object so that code can ask questions about it: "Do you perform IO?" "Can you be reverted?" It lets surrounding code introspect over operations in useful ways.
* It allows you to separate the code that creates the command from the code that performs it (what this blog post is about). This can nicely decouple "strategy"-type code from "execution harness" type code. Both of those are often fairly complex in their own right, so a pattern that lets you build a nice abstraction layer between them can be very helpful.
* It allows the command object to support multiple related operations. The most common example, which I deeply love, is implementing undo. A Command object for some UI operation can also support a separate method to undo the same operation. Your undo stack is then just a list of these Command objects.
Used something very similar many times in my past without knowing it is formalised as a pattern.
For example, one application of this was a long migration project where a large collection of files (some petabytes of data) was to be migrated from an on-prem NAS to cloud filesystem. The files on NAS were managed with additional asset management solution which stored metadata in a PostgreSQL (actual filenames, etc.)
The application I wrote was composed of a series of small tools. One tool would contact all of the sources of information and create a file with a series of commands (copy file from location A to location B, create a folder, set metadata on a file, etc.)
Other tools could take that large file and run operations on it. Split it into smaller pieces, prioritise specific folders, filter out modified files by date, calculate fingerprints from actual file data for deduplication, etc. These tools would just operate on this common file format without actually doing any operations on files.
And finally tool that could be instantiated somewhere and execute a plan.
I designed it all this way as it was much more resilient process. I could have many different processes running at the same times and I had a common format (a file with a collection of directives) as a way to communicate between all these different tools.
For example, one application of this was a long migration project where a large collection of files (some petabytes of data) was to be migrated from an on-prem NAS to cloud filesystem. The files on NAS were managed with additional asset management solution which stored metadata in a PostgreSQL (actual filenames, etc.)
The application I wrote was composed of a series of small tools. One tool would contact all of the sources of information and create a file with a series of commands (copy file from location A to location B, create a folder, set metadata on a file, etc.)
Other tools could take that large file and run operations on it. Split it into smaller pieces, prioritise specific folders, filter out modified files by date, calculate fingerprints from actual file data for deduplication, etc. These tools would just operate on this common file format without actually doing any operations on files.
And finally tool that could be instantiated somewhere and execute a plan.
I designed it all this way as it was much more resilient process. I could have many different processes running at the same times and I had a common format (a file with a collection of directives) as a way to communicate between all these different tools.
This is an excellent pattern. Nix uses it to allow one to create a full transitive build graph, serialized that plan, move it around, and execute it in a distributed and reproducible fashion.
There are always temptations to loosen the constraints this imposes, but they nearly always come at a cost of undermining the value of the pattern.
There are always temptations to loosen the constraints this imposes, but they nearly always come at a cost of undermining the value of the pattern.
I don't see how that is a pattern. Rather, it's a new name to an old thing: writing a virtual machine or an JIT-compiler. And no, interpreter is not a "special case of plan-execute pattern": by definition, if data structure can be run, it means it is a program for some virtual machine. And "a plan" is a lousy definition of "something that can be run", i.e. a program. So it's not a "special case", it's synonymous.
That also explains why it isn't a good and useful "pattern": inventing new DSLs with custom compilers all the time is not a trivial thing to pull off without shooting yourself in the leg, so if are writing a VM (e.g. an RDBMS query planner) you must be already perfectly aware that you are writing a fucking VM with its own programming language (e.g. SQL). And if you are not, inventing a data structure that encapsulates a whole program is probably a bigger task than the problem you are actually trying to solve.
That also explains why it isn't a good and useful "pattern": inventing new DSLs with custom compilers all the time is not a trivial thing to pull off without shooting yourself in the leg, so if are writing a VM (e.g. an RDBMS query planner) you must be already perfectly aware that you are writing a fucking VM with its own programming language (e.g. SQL). And if you are not, inventing a data structure that encapsulates a whole program is probably a bigger task than the problem you are actually trying to solve.
I do this for a code generation tool we use internally! Plans contain all the metadata to actually do a thing, but allow transformation, filtering etc before execution. It also forces you to abstract your code in a cleaner way, and minimize the surface of your plan generation/execution functions, which makes them infinitely more testable.
The way I think about when to use a plan is whenever you're doing batches of I/O of some kind, or anything that you might want to make idempotent.
The way I think about when to use a plan is whenever you're doing batches of I/O of some kind, or anything that you might want to make idempotent.
A key motivator of this pattern is identifying invalid configurations early, and in particular preventing execution if a known invalid configuration is requested (e.g. fail-fast). For example, if you delete a resource from a configuration, and it ends up being one that is depended upon by another, a "plan-execute" pattern should identify this at the start and prevent any execution from happening.
The correct name is "staged generative programming".
The best form for plans is DAG w/o control flow.
You may run perception->planning->execution in a loop.
The best form for plans is DAG w/o control flow.
You may run perception->planning->execution in a loop.
> I feel uneasy about design patterns. ... they solve problems that a choice of programming language or paradigm creates.
I don't understand the ambivalence. I have to make some choice of language and paradigm, and then I have to solve problems using it.
Great article and description of the plan-execute pattern, though!
I don't understand the ambivalence. I have to make some choice of language and paradigm, and then I have to solve problems using it.
Great article and description of the plan-execute pattern, though!
I really like this pattern and have been using it in the rewrite for vdirsyncer.
One nice advantage is that an application can show me the whole plan for me to review before executing it. This is basically what terraform did too.
This pattern also makes coding and testing much much easier.
One nice advantage is that an application can show me the whole plan for me to review before executing it. This is basically what terraform did too.
This pattern also makes coding and testing much much easier.
I've also successfully used this in production — another side effect is that you can inspect the exact information that each step is using to compute its own output, if you ensure that the output plan is a pure function of the input plan.
I think postgres really excelled at this pattern. As well as other databases implementing a query planner.
"I feel uneasy about design patterns. On the one hand, my university class on design patterns revived my interest in programming. On the other hand, I find most patterns in the Gang of Four book to be irrelevant to my daily work; they solve problems that a choice of programming language or paradigm creates."
My relationship with design patterns changed when I stopped viewing them as prescriptive and started viewing them as descriptive.
My relationship with design patterns changed when I stopped viewing them as prescriptive and started viewing them as descriptive.
Descriptive of the kinds of workarounds that a lack of proper abstraction capabilities made necessary in ancient Java.
The GoF book uses C++ and was written before the first version of Java existed.
Furthermore, the purpose of design patterns is not to introduce anything new, it’s to provide a catalog of repeatedly occurring existing patterns in software development, including the respective situations each pattern is applicable in, and their individual benefits and drawbacks. An important motivation was to name each pattern, so that when one software engineer says “builder”, the other engineers know what it means. Previously developers encountered certain patterns sooner or later, but didn’t know what to call each pattern, or each developer invented their own names, or meant different things by the same name.
The set of relevant patterns will change over time to some extent as software development changes, but that is orthogonal to the concept of design patterns. It’s a mistake to think of design patterns as specifically the set of 23 GoF patterns. Though some GoF patterns are unlikely to ever become irrelevant, like Adapter, Decorator, Composite, Proxy, Interpreter, Strategy.
Furthermore, the purpose of design patterns is not to introduce anything new, it’s to provide a catalog of repeatedly occurring existing patterns in software development, including the respective situations each pattern is applicable in, and their individual benefits and drawbacks. An important motivation was to name each pattern, so that when one software engineer says “builder”, the other engineers know what it means. Previously developers encountered certain patterns sooner or later, but didn’t know what to call each pattern, or each developer invented their own names, or meant different things by the same name.
The set of relevant patterns will change over time to some extent as software development changes, but that is orthogonal to the concept of design patterns. It’s a mistake to think of design patterns as specifically the set of 23 GoF patterns. Though some GoF patterns are unlikely to ever become irrelevant, like Adapter, Decorator, Composite, Proxy, Interpreter, Strategy.
Or any other major commercially used language right now?
Look, I'm glad you work in a language where you don't need to describe those things any more, but the vast majority of people still do. And for that group of people, understanding that "Design Patterns" is a dictionary, not a recipe book, is a really important thing.
Look, I'm glad you work in a language where you don't need to describe those things any more, but the vast majority of people still do. And for that group of people, understanding that "Design Patterns" is a dictionary, not a recipe book, is a really important thing.
What modern version of a "commercially used language" needs patterns a la GoF? Most of them simply disappear as the language is made more expressive than the horror that was pre-standard C++. Modern Java or C# are not at all like that.
It's not a bad book if you read it as positive account rather than a normative prescription, I have the dead tree version on my bookshelf, but it's also a narrow, historically-informed perspective. Nothing about patterns is a fundamental concept that persists across languages (or even time), unlike things like SICP, algorithms, CS concepts, etc.
It's not a bad book if you read it as positive account rather than a normative prescription, I have the dead tree version on my bookshelf, but it's also a narrow, historically-informed perspective. Nothing about patterns is a fundamental concept that persists across languages (or even time), unlike things like SICP, algorithms, CS concepts, etc.
How are (for example) Adapter and Proxy not fundamental patterns applicable in most programming languages? Many people take them for granted today and maybe don’t think about them as design patterns, and a modern description will use different examples than the GoF book, but they are patterns nonetheless, and the GoF book contributed a lot to them having universally agreed and well-recognized names.
Neither of them is a fundamental idea about programming in general, unless the only languages we are considering are Java, C#, and Python spoken with a thick Java accent.
Adapter is an OOP-ism. If you take, for example, any ML-family language, you won't find anything of the sort. Even staying in OOP-land, in a language where inheritance goes on the prototypal chain, you wouldn't solve the problem like that.
Proxy is a more general concept, but the way it's described in GoF is still tied to a class/interface/implementation mechanism. In other languages it would often just be a function. I don't know what overarching lesson you would draw from it except "write code to do things".
As I said I don't think it's a bad book, it's definitely something you should read, even just for the meta-level language it (successfully!) introduced. Where I differ is that I don't believe the book is quite as successful at transcending the "traditional" OOP mechanisms. It's mostly "how to accomplish things in Java 1.5".
Adapter is an OOP-ism. If you take, for example, any ML-family language, you won't find anything of the sort. Even staying in OOP-land, in a language where inheritance goes on the prototypal chain, you wouldn't solve the problem like that.
Proxy is a more general concept, but the way it's described in GoF is still tied to a class/interface/implementation mechanism. In other languages it would often just be a function. I don't know what overarching lesson you would draw from it except "write code to do things".
As I said I don't think it's a bad book, it's definitely something you should read, even just for the meta-level language it (successfully!) introduced. Where I differ is that I don't believe the book is quite as successful at transcending the "traditional" OOP mechanisms. It's mostly "how to accomplish things in Java 1.5".
> Adapter is an OOP-ism. If you take, for example, any ML-family language, you won't find anything of the sort.
This is incorrect. For example in SML you have signatures and structures, which are roughly analogous to interfaces and implementing classes in OOP. And SML functors are adapters that can adapt a structure of one signature to a different signature. Or they may create a proxy structure for a given structure. Furthermore, you could easily imagine a derived language where functors are just regular functions and structures are regular values.
This is incorrect. For example in SML you have signatures and structures, which are roughly analogous to interfaces and implementing classes in OOP. And SML functors are adapters that can adapt a structure of one signature to a different signature. Or they may create a proxy structure for a given structure. Furthermore, you could easily imagine a derived language where functors are just regular functions and structures are regular values.
I would argue that ML functors are significantly more general than Adapter as presented in Design Patterns, the transferable "big idea" being the underlying type theory (functors as high-kindered types) as opposed to the pattern.
> you could easily imagine a derived language where functors are just regular functions and structures are regular values
I'm pretty sure someone taught me this some time ago but I have forgotten it, can you do it that easily? Aren't you at least supposed to make a distinction about types and kinds? I really don't remember, I'm genuinely asking.
> you could easily imagine a derived language where functors are just regular functions and structures are regular values
I'm pretty sure someone taught me this some time ago but I have forgotten it, can you do it that easily? Aren't you at least supposed to make a distinction about types and kinds? I really don't remember, I'm genuinely asking.
These are still relevant even in modern Java or C# or C++. Just because the language can express things in a more modern way doesn't mean you always will. Or should. Or can.
And I agree that it's a historically informed perspective. But guess how much code is modern code versus historic^W legacy code. Nobody is arguing (well, at least I'm not) it's a foundation of CS. Nor is any reasonable person arguing it's a normative prescription - see the comment about "not a recipe book".
It's the equivalent of a dictionary/thesaurus for a writer - necessary, but not world-changing. Always has been. Still is.
And I agree that it's a historically informed perspective. But guess how much code is modern code versus historic^W legacy code. Nobody is arguing (well, at least I'm not) it's a foundation of CS. Nor is any reasonable person arguing it's a normative prescription - see the comment about "not a recipe book".
It's the equivalent of a dictionary/thesaurus for a writer - necessary, but not world-changing. Always has been. Still is.
I have heard this said, mainly because some patterns can be made unnecessary with first-class functions and pattern matching. Closures are emulated with explicit objects, and the visitor pattern is equivalent to pattern matching. Something that's pretty interesting, though, is that it's a transform called defunctionalization. There's an article about it [1] that has been shared before on HN.
One form of defunctionalization is the well-known transformation of a recursive function into one that uses an explicit stack.
The thing is, I don't think defunctionalization (from the equivalent functional form) present in object-oriented languages is strictly worse. Defining things with explicit objects may sometimes be more understandable, and more extensible; for example, the command pattern could be implemented as a closure, but then you can't later add an "undo" method to it later.
Here's an example where defunctionalization makes the code more readable, not less.
Haskell has a difference list [0] data structure; the purpose of it is that you can concatenate two difference lists in constant time, and then turn it into one long normal linked list in O(n) time. This gives much better performance than concatenating lists directly all the time. It's a lot like a rope, except for lists, not strings, and it's immutable.
But the code is somewhat cryptic; it makes use of partial application and stores the tree in terms of partially applied functions. The "Demystifying DList" [0] article I shared shows a defunctionalized form explicitly defined as a tree in concrete data types.
To those interested in it, if you're familiar with the syntax of ML-like languages, I'd recommend the papers [2], [3], and [4].
[0]: http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/
[1]: https://blog.sigplan.org/2019/12/30/defunctionalization-ever...
[2]: "Defunctionalization at work": https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/d...
[3]: "Refunctionalization at work": https://www.brics.dk/RS/07/7/BRICS-RS-07-7.pdf
[4]: "Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity": https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continue...
One form of defunctionalization is the well-known transformation of a recursive function into one that uses an explicit stack.
The thing is, I don't think defunctionalization (from the equivalent functional form) present in object-oriented languages is strictly worse. Defining things with explicit objects may sometimes be more understandable, and more extensible; for example, the command pattern could be implemented as a closure, but then you can't later add an "undo" method to it later.
Here's an example where defunctionalization makes the code more readable, not less.
Haskell has a difference list [0] data structure; the purpose of it is that you can concatenate two difference lists in constant time, and then turn it into one long normal linked list in O(n) time. This gives much better performance than concatenating lists directly all the time. It's a lot like a rope, except for lists, not strings, and it's immutable.
But the code is somewhat cryptic; it makes use of partial application and stores the tree in terms of partially applied functions. The "Demystifying DList" [0] article I shared shows a defunctionalized form explicitly defined as a tree in concrete data types.
To those interested in it, if you're familiar with the syntax of ML-like languages, I'd recommend the papers [2], [3], and [4].
[0]: http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/
[1]: https://blog.sigplan.org/2019/12/30/defunctionalization-ever...
[2]: "Defunctionalization at work": https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/d...
[3]: "Refunctionalization at work": https://www.brics.dk/RS/07/7/BRICS-RS-07-7.pdf
[4]: "Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity": https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continue...
There are definitely cases where a structured value is clearer than a function. But at that point you're just modelling your domain and it's not really a "command pattern" at all. The point of the command pattern is that you have an object that really and truly is just a function, you're only representing it as an object because you need to pass it around - but in that case it really is just a workaround for your language lacking first-class functions.
A good language makes it easy to use both functions-as-values and structured-objects-as-callables, and use whichever representation is appropriate to the situation.
A good language makes it easy to use both functions-as-values and structured-objects-as-callables, and use whichever representation is appropriate to the situation.
That's a fair point; not having first-class functions is a flaw for a high-level programming language, and the command pattern is just making up for a deficiency in the case that it would never need to be anything more than a closure in a language that does have one.
[deleted]
[deleted]
There are a wide range of “patterns” that derive from compilers that are the higher teachings behind functional programming and OO patterns. People don’t usually call them patterns. (Scheme isn’t special because it has closures, it is special because you can write functions that write functions.)
Reminds me of a thread a few days back when someone was talking about state machines as if they were obscure. At a systems programming level they aren’t obscure at all (how do you write non-blocking network code without async/await? how does regex and lexers work?). Application programmers are usually “parsing” with regex.match() or index() or split() and frequently run into brick walls when it gets complex (say parsing email headers that can span several lines) but state machines make it easy.
Reminds me of a thread a few days back when someone was talking about state machines as if they were obscure. At a systems programming level they aren’t obscure at all (how do you write non-blocking network code without async/await? how does regex and lexers work?). Application programmers are usually “parsing” with regex.match() or index() or split() and frequently run into brick walls when it gets complex (say parsing email headers that can span several lines) but state machines make it easy.
> Scheme isn’t special because it has closures, it is special because you can write functions that write functions.
When Scheme was developed, it was special, because it used lexical binding and provided lexical closures. That was new. Writing functions that write functions would not have been new, since LISP had that already -> including Maclisp, which was used for the first SCHEME implementation. Later Scheme got used for exploring different macro systems.
When Scheme was developed, it was special, because it used lexical binding and provided lexical closures. That was new. Writing functions that write functions would not have been new, since LISP had that already -> including Maclisp, which was used for the first SCHEME implementation. Later Scheme got used for exploring different macro systems.
> Scheme isn’t special because it has closures, it is special because you can write functions that write functions.
I swear this informational parasite will never die, any language with eval can write functions that write functions. What makes Scheme and other homoiconic languages special is that the code that is currently executing can be manipulated live like any other data structure and it works.
I swear this informational parasite will never die, any language with eval can write functions that write functions. What makes Scheme and other homoiconic languages special is that the code that is currently executing can be manipulated live like any other data structure and it works.
> What makes Scheme and other homoiconic languages special is that the code that is currently executing can be manipulated live like any other data structure and it works.
That would be true for source level interpreters, but not for compiled implementations.
That would be true for source level interpreters, but not for compiled implementations.
No, Scheme does not make self-modifying code defined.
See this example in R7RS for the set-car! function:
In Common Lisp, it is likewise undefined behavior.
Running Lisp code is not necessarily still made of nested lists. That may be the case if it is interpreted, but Lisp code is often compiled. Modifying the original nested lists that comprise the source code will do nothing to the object code, except if those parts are modified that serve as literals, which the compiled code may be sharing with the source code.
In short, your understanding is wrong. When Lisp people talking about modifying the running program, that just refers to redefining functions and other entities. Common Lisp has strong support for redefining classes of which there are existing instances. Existing objects can be migrated to new representations in the redefined classes.
None of that is related to homoiconicity or related topics.
See this example in R7RS for the set-car! function:
(define (f) (list 'not-a-constant-list))
(define (g) '(constant-list))
(set-car! (f) 3) ⟹ unspecified
(set-car! (g) 3) ⟹ error
In Common Lisp, it is likewise undefined behavior.
Running Lisp code is not necessarily still made of nested lists. That may be the case if it is interpreted, but Lisp code is often compiled. Modifying the original nested lists that comprise the source code will do nothing to the object code, except if those parts are modified that serve as literals, which the compiled code may be sharing with the source code.
In short, your understanding is wrong. When Lisp people talking about modifying the running program, that just refers to redefining functions and other entities. Common Lisp has strong support for redefining classes of which there are existing instances. Existing objects can be migrated to new representations in the redefined classes.
None of that is related to homoiconicity or related topics.
>What makes Scheme and other homoiconic languages special is that the code that is currently executing can be manipulated live like any other data structure
I think I know Scheme well, and I don't catch your meaning. Most Scheme implementations are compilers that output a machine-language executable. How can this executable be "manipulated live" in a way that differs from an executable produced by any other language? What am I not seeing?
I think I know Scheme well, and I don't catch your meaning. Most Scheme implementations are compilers that output a machine-language executable. How can this executable be "manipulated live" in a way that differs from an executable produced by any other language? What am I not seeing?
At the level where you're executing assembly every language is the same. Which is a way of saying that assembly is homoiconic. And even in C you're more than capable of W&Xing your binary to change behavior at runtime but you're doing it at a level below the language. It's the (not completely unrestricted) self-modifying bit that's cool
and unique. You can go into an existing function and change what it does by manipulating or outright replacing its code.
Other languages you end up having to evaluate and re-point/redefine the reference and it gets you where you need to go but not nearly as cool. For folks that liked Dijkstra's whole structured programming thing but didn't want to give up the power entirely.
Other languages you end up having to evaluate and re-point/redefine the reference and it gets you where you need to go but not nearly as cool. For folks that liked Dijkstra's whole structured programming thing but didn't want to give up the power entirely.
>You can go into an existing function and change what it does by manipulating or outright replacing its code.
I still don't see what this might mean. It doesn't sound like anything I've ever done in Scheme or I've ever heard of anyone else doing. You probably don't mean editing Scheme source code and recompiling.
I still don't see what this might mean. It doesn't sound like anything I've ever done in Scheme or I've ever heard of anyone else doing. You probably don't mean editing Scheme source code and recompiling.
How about monkey patching in languages like Javascript and Python?
I'd also say "homoiconic" is a less important concept than people would think. A while back I was writing a lodash-like library for Java because I don't like the Streams API (though in the end I just used the collectors from the Stream API because they were easy to fit into my system) One thing I found frustrating about that was that I didn't want to write 8 different functions for the 8 primitive types (never mind 64 functions for the direct product of the primitive types) and conceived of a code generator that would let you write Java-in-Java with a somewhat Lispy looking API that builds up something like S-expressions with typed static imports, here is some sample code
https://github.com/paulhoule/ferocity/blob/main/ferocity0/sr...
The plan was to write a ferocity0 sufficient to write a code generator that could generate stubs for the standard library plus a persistent collection library, then write most of ferocity1 in ferocity0 and maybe write a ferocity2 in ferocity1 and ferocity2 would be the master tool for code generation in Java. Look how nice the stub generator is
https://github.com/paulhoule/ferocity/blob/main/ferocity0/sr...
Now many people would think this combines all the drawbacks of Common Lisp and Java and they might be right. On the other hand, I think if you're aggressive in organizing your code and using code generation you might cut your code volume enough to make up for the bulking that happens when you write Java-in-Java. The stubs to write Java-in-Java are a huge amount of code but they're 99% generated and once you have Java-in-Java you can keep recursing and messing around with quote and eval and do all the stuff you'd do in a homoiconic language except you are having to write code in a DSL.
I'd also say "homoiconic" is a less important concept than people would think. A while back I was writing a lodash-like library for Java because I don't like the Streams API (though in the end I just used the collectors from the Stream API because they were easy to fit into my system) One thing I found frustrating about that was that I didn't want to write 8 different functions for the 8 primitive types (never mind 64 functions for the direct product of the primitive types) and conceived of a code generator that would let you write Java-in-Java with a somewhat Lispy looking API that builds up something like S-expressions with typed static imports, here is some sample code
https://github.com/paulhoule/ferocity/blob/main/ferocity0/sr...
The plan was to write a ferocity0 sufficient to write a code generator that could generate stubs for the standard library plus a persistent collection library, then write most of ferocity1 in ferocity0 and maybe write a ferocity2 in ferocity1 and ferocity2 would be the master tool for code generation in Java. Look how nice the stub generator is
https://github.com/paulhoule/ferocity/blob/main/ferocity0/sr...
Now many people would think this combines all the drawbacks of Common Lisp and Java and they might be right. On the other hand, I think if you're aggressive in organizing your code and using code generation you might cut your code volume enough to make up for the bulking that happens when you write Java-in-Java. The stubs to write Java-in-Java are a huge amount of code but they're 99% generated and once you have Java-in-Java you can keep recursing and messing around with quote and eval and do all the stuff you'd do in a homoiconic language except you are having to write code in a DSL.
I glanced at your code examples and it looks quite similar to ByteBuddy[0], a Java library for manipulating JVM bytecode.
[0]: https://github.com/raphw/byte-buddy
[0]: https://github.com/raphw/byte-buddy
Now suppose three of you are working on the same project, and each brings their own code generator like this.
You can take Common Lisp macros from multiple sources and use them in the same expression, in any pattern of nesting.
You can take Common Lisp macros from multiple sources and use them in the same expression, in any pattern of nesting.
In principle. Most people find somebody else's metaprogramming-heavy Common Lisp difficult to work with. When you look at classic programs from the golden age of AI you find they either rewrote their Lisp prototype in C++ for speed or the Lisp program (like an expert system shell) is much smaller than you imagine possible but it looks like the engine of a UFO.
Though I've only seen other people's Lisp projects online and in books, I haven't seen metaprogramming that made it less readable - usually, it makes the program more readable. At most, it defines a DSL, e.g. COMFY 6502, which is a thin wrapper over 6502 assembly implemented as a DSL in Emacs Lisp. But most of the time, macros provide a readable interface over a bunch of hard-to-understand boilerplate generated code.
[0]: https://dl.acm.org/doi/pdf/10.1145/270941.270947
[0]: https://dl.acm.org/doi/pdf/10.1145/270941.270947
Right. The reliable reference point for comparing the program with macros is the same program in which the macros have been expanded.
Comparing it to some completely different, nonexistent program which solves the same problem without macros is fallacious.
Comparing it to some completely different, nonexistent program which solves the same problem without macros is fallacious.
> Most people find somebody else's metaprogramming-heavy Common Lisp difficult to work with.
Citation needed. Org names, projects, numbers.
Also, how easy do people find someone's Java metaprogramming? Where the whole metaprogramming system is locally invented, not just its application to the problem?
Citation needed. Org names, projects, numbers.
Also, how easy do people find someone's Java metaprogramming? Where the whole metaprogramming system is locally invented, not just its application to the problem?
Do you have a link to one of these UFO engines that I can study up on?
See https://www.cs.unm.edu/~luger/ai-final/code/LISP.ess.html and the more modern http://www.clara-rules.org/
That code looks readable to me. It is well formatted and the functions are small, with simple control paths. No variable assignments or loops to unravel.
It defines no macros, but refers to some defined elsewhere; the instructions say you are supposed to use a certain other source file related to Chapter 14 of a book.
I could probably ramp up on this in a day, if I had reason to.
It defines no macros, but refers to some defined elsewhere; the instructions say you are supposed to use a certain other source file related to Chapter 14 of a book.
I could probably ramp up on this in a day, if I had reason to.
[deleted]
> the code that is currently executing can be manipulated live
Typically when people say this about Lisp, they mean that they can redefine functions and objects live, having all the code adapt to use the new definitions, or when their code hits an error, they can not only redefine functions and objects live, but also examine the state of the call stack and change the values of variables live, and then let the code run again. This[0] is a clear explanation that I found. There's also a video[1] that shows the same thing.
However, I don't know if those apply to Scheme. Also, I am pretty sure it is unrelated to Lisp being homoiconic, and that it's more about it being dynamically typed and interpretable.
[0]: https://malisper.me/debugging-lisp-part-1-recompilation/
[1]: https://youtu.be/jBBS4FeY7XM
Typically when people say this about Lisp, they mean that they can redefine functions and objects live, having all the code adapt to use the new definitions, or when their code hits an error, they can not only redefine functions and objects live, but also examine the state of the call stack and change the values of variables live, and then let the code run again. This[0] is a clear explanation that I found. There's also a video[1] that shows the same thing.
However, I don't know if those apply to Scheme. Also, I am pretty sure it is unrelated to Lisp being homoiconic, and that it's more about it being dynamically typed and interpretable.
[0]: https://malisper.me/debugging-lisp-part-1-recompilation/
[1]: https://youtu.be/jBBS4FeY7XM
But that can't be "what makes Scheme and other homoiconic languages special".
I suppose that, if I'm asked "What is something that makes homoiconic languages special?" and the answer can't be that it makes macros easy, then I would say it's that it's easy to write an interpreter for that language in the language itself, because the data structures that form the syntactic structure of the language are themselves first-class objects. That's why the interpreter from the appendix of the LISP 1.5 manual can be so short. That's also why the EVAL function takes as a parameter a list of atoms, and not a string, as in non-Lisp dynamically typed languages; since a Lisp program is also a list of atoms, that's the form it takes in the interpreter. The first Lisp compiler [0] isn't so long, either. The equivalent eval function in non-homoiconic languages requires a lexer, parser, and special definitions of data structures to represent the syntax, as well as functions to manipulate those data structures.
[0]: https://texdraft.github.io/lisp-compiler/internals.html
[0]: https://texdraft.github.io/lisp-compiler/internals.html
I like that answer, and want to add to it.
Scheme was the first language with lexical scoping of variables, and after Scheme was published in 1975, most new languages have had lexical scope and most languages used now (Java, C#, Javascript, Rust) have it. I think the qualities you describe make it easier to experiment with (Lisp-like) languages and language implementations, which is why lexical scope appeared in a Lisp-like first. Also, I think the concept of a "closure" appeared first in discussions about Lisp (maybe as part of the same discussions that led to lexical scope). Ditto I think continuations and continution-passing style. Also the interpreter you refer to in Appendix A of the Lisp 1.5 manual had a subtle problem or area for improvement around functions appearing as arguments to functions, and the Lisp's community's discovery of that and solution to that seems to have been incorporated into other languages, probably first the early functional languages like Miranda, then on to Javascript, etc.
Scheme was the first language with lexical scoping of variables, and after Scheme was published in 1975, most new languages have had lexical scope and most languages used now (Java, C#, Javascript, Rust) have it. I think the qualities you describe make it easier to experiment with (Lisp-like) languages and language implementations, which is why lexical scope appeared in a Lisp-like first. Also, I think the concept of a "closure" appeared first in discussions about Lisp (maybe as part of the same discussions that led to lexical scope). Ditto I think continuations and continution-passing style. Also the interpreter you refer to in Appendix A of the Lisp 1.5 manual had a subtle problem or area for improvement around functions appearing as arguments to functions, and the Lisp's community's discovery of that and solution to that seems to have been incorporated into other languages, probably first the early functional languages like Miranda, then on to Javascript, etc.
It's funny, because I had just recently read about there being a bug in that interpreter due to dynamic scoping, but forgot about when writing that.
[deleted]
>code that is currently executing can be manipulated live like any other data structure and it works.
I heard from someone who did this with x86(-64?) assembly in production code, but I don't know the details.
I heard from someone who did this with x86(-64?) assembly in production code, but I don't know the details.
[deleted]
Back in the 1980s I found a book at the public library where somebody had a BASIC program that would read a BASIC program without line numbers and with structured programming loops and rewrite it an ordinary BASIC. It was oriented towards CP/M so I typed the program in and modified it to run on my TRS-80 Coco. It was kinda like
https://en.wikipedia.org/wiki/Ratfor
Similarly I've written awk programs that write shell scripts (guilty pleasure), Python programs that write AVR-8 assembly, toolkits to write Java ASTs with static imports like
There are many paths to metaprogramming but the Lisp family leads in putting it on your fingertips. Once you learn those methods you can apply them in the trashiest programming languages, but I think often people miss the point.
https://en.wikipedia.org/wiki/Ratfor
Similarly I've written awk programs that write shell scripts (guilty pleasure), Python programs that write AVR-8 assembly, toolkits to write Java ASTs with static imports like
@Test
public void buildAList() {
var stream = callBuild(callAdd(callAdd(callAdd(callBuilder(), Literal.of(7)),
Literal.of(11)),Literal.of(15)));
var expr = callToList(stream);
var l = expr.evaluateRT();
assertEquals(3,l.size());
assertEquals(7, l.get(0));
assertEquals(11, l.get(1));
assertEquals(15, l.get(2));
}
There are many paths to metaprogramming but the Lisp family leads in putting it on your fingertips. Once you learn those methods you can apply them in the trashiest programming languages, but I think often people miss the point.
Very common for me to write shell scripts that generate shell scripts to run.
Instead of creating gnuplot scripts to loaded, sometimes a good sequence of echo "set terminal png 800,600; plot..." | gnuplot > my.png
or a very long imagemagick drawing command or a simple svg generated then converted to png then assembled (thank montage), can do the job.
The whole advantage of generating intermediate shell scripts, is to replay one part specifically to debug a small part of a script pipeline.
Instead of creating gnuplot scripts to loaded, sometimes a good sequence of echo "set terminal png 800,600; plot..." | gnuplot > my.png
or a very long imagemagick drawing command or a simple svg generated then converted to png then assembled (thank montage), can do the job.
The whole advantage of generating intermediate shell scripts, is to replay one part specifically to debug a small part of a script pipeline.
[deleted]
However, when I later revisited the design of Ninja I found that removing the separate planning phase better reflected the dynamic nature of how builds end up working out, where you discover information during the build that impacts what work you have planned. See the "Single pass" discussion in my design notes[2], which includes some negatives of the change.
If the author reads this, in [2] I made a Rust-based Ninja rewrite that has some similar data structures to those in the blog post, you might find it interesting!
[1] https://github.com/ninja-build/ninja/blob/dcefb838534a56b262... [2] https://neugierig.org/software/blog/2022/03/n2.html