Generalizing 'jq' and Traversal Systems using optics and standard monads
chrispenner.ca
chrispenner.ca
[1] https://www.inkandswitch.com/cambria.html
[2] https://news.ycombinator.com/item?id=24699615
[3] https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
It’s a shame I don’t know that many people who’d enjoy it as much as I do!
For anyone interested in computing pre-history, early twentieth century punched-card processing, before von Neumann, was all about taking (monoidal) data structures (encoded as a deck of cards) with historical values and either querying them or running updates (encoded as a second deck of cards) to produce freshly copied current values.
So much work goes in most languages into processing nested data structures, especially in this day and age of heterogeneous APIs, and a lot of it is actually not that difficult to generalize conceptually into most languages. A few weeks ago I wrote a PoC in Python and it was remarkably easy to make a lens for traversing data structures.
Declarative optics and updates would make writing business logic a lot easier on so many domains.
monadic list comprehensions aren't quite the same thing as optics, however.
https://research.utwente.nl/en/publications/functional-progr...
In particular, the metaphor isn't used in Algorithmics: Towards Programming as a Mathematical Activity (1986).
for staff in company.staff:
for pet in staff.pets:
if pet.type == 'cat':
print(pet.name + " belongs to " + staff.name)
`.company.staff | .pets | flatten | filter .type == "cat" | log(...)`
The original version with for loops just looks like a block of text. Spacing would help, but I would still need to look carefully to pick out the important bits.
You don't want to listen to any specific camp. The best is always in the middle and you are on the right track:
"Pick what is easy to read."
However there is a caveat, which is that functional style is only hard to read at the beginning. Have a look at how modern languages integrate functional programming (see java, C#, C++, etc.).
Java streams are a common example. They make most code much easier to read ONCE you are used to it, because they provide standardized behaviour that is side-effect free. When you write everything in plain syntax, the reader needs to abstract your code in his head, while when using streams, you just know what `filter`, `map`, `reduce`, etc. do and you only need to look at the small customizations. It's easier to read once you are used to it.
However there is a limit and this limit get hit quickly. A lot of people like to make their code as complicated and fancy as possible and reduce every possible line. This is definitely wrong. Code must be easy to understand and change. If you fail that, you are doing it wrong.
This also depends on your environment. If your co-workers don't understand the code you write, you have failed, no matter if your code is "nicer" or not. You either need to write simpler code or educate your co-workers to create common ground.
That's my point. The fact that you didn't include it implies to me that it was too difficult to figure out, and a true implementation would be far more complicated, so it's not a fair comparison.
.company.staff | .pets | flatten | filter .type == "cat" | print(.name + " belongs to " + ..name)Now if you restrict yourself to not introduce any side effects, the interpreter can be proven correct, the execution can be analysed much better and you can have some neat safety guarantees.
That's why.
I don't understand what you mean by "analyzed much better" and "neat safety guarantees". Is my code hard to analyze or unsafe?
For loops can be easily mapped into functional constructs, but not your snipped does not compute anything. It's not a function.
State mutation is a side effect. If you mean it builds it up locally, it would then not have nonlocal side effects (e.g., it would have a pure functional interface even though it has an imperative implementation). But to do that, you'd have construction and mutation overhead in the code, whereas with functional idioms / comprehensions, you would not.
This is especially the case when (as is often the case in practice) you are taking collection datastructures and producing collection structures to work with.
For example, if you want to take a list of integers and return a list of those those integers plus one ([1,2,3] -> [2,3,4]), that new list needs to be built up in memory somehow before it is returned, no? Sure that process might be hidden behind a generic `map` function (something like `map(lambda x:x+1, [1,2,3])`), lambda, but then you just have the `map` function building up the new list. Or if `map` returns a generator (so you don't need to construct the whole return list first), you're still storing some local state to keep track of which element of the input list you're currently processing.
What am I missing or getting wrong here?
But that's not what FP people mean by state.
RAM is an implementation detail. (You don't even strictly need RAM to compute. But that's another conversation.)
In your example, one part of the state is the list [1,2,3]. That isn't mutated when the program runs. It's passed around. The implementation probably passes it by reference - a pointer to the list - but actually the programmer can't tell and doesn't care if it's copied or passed by reference. There's no visible difference, when values can't be mutated.
The other part is [2,3,4]. As the program runs, it will be allocated in new memory, and from the programmer's point of view, it's as if the value [2,3,4] always existed, just waiting to be looked at. When it does look, that's always the value it's going to find, so in a very meaningful sense, that value is already there.
It's not usually allocated and stored in RAM until the program looks there, but it could be, it makes no difference from the perspective of the FP programmer. (In some implementations it actually might be. If you called map(f,[1,2,3]) twice it might "rediscover" the value already existing in RAM on the second call and use that.)
And the [1,2,3] might get freed at some point. But that only happens when it's not being "looked at". It gets forgotten then. (Or in an exotic implementation if there's still a reference to it, the memory containing the value might be freed, and it might be reallocated and recalculated when it's looked at again later. All invisible to the FP programmer.)
For your generator example, the implementation might create a state variable to implement it, or it might not. Either way it's hidden from the pure FP program, and it's as if the list [2,3,4] is just there, waiting to be looked at. Some implementations won't use a stateful generator like you'd think in Python though. They may instead represent the list as having a lazy tail: [2,3,lazymore...] where lazymore... is a placeholder in the list in RAM, which represents the part of the list which hasn't been looked at yet. This is lazy evaluation. The lazymore... is completely invisible to the pure FP program, because the act of looking at it (to do something useful) causes it to be replaced with the "real" calculated value, [4] in this case. Only those "real" values are visible to the program.
Overall, in the pure FP programming model, it's as if all the values exist already and never change, and they are determined by the FP expressions from other values which also never change.
The only "effect" is an implementation detail, triggered by the the act of looking at values to see what they already are, which converts lazy placeholders into useful values. The equivalence between lazy placeholder and useful value is so well hidden in pure FP that the implementation is free to do things like calculate values before they are needed or even if they are never needed, and to discard some values (putting the placeholder back) and recalculate them again later whenever it feels like. Yet to the pure FP programmer, it's always the same values.
The underlying implementation will allocate, free, move values around in memory, and perform lazy evaluation as its way of "looking at" values as requested. But those are all implementation details which are hidden from the pure FP programmer, and the details will vary between different implementations too. In practice there's still debugging and timing and memory usage visible, but not to the FP program (except through "cheating" non-pure FP escape hatches), and we think of those as part of the implementation, separate from the FP programming model.
const head = ([x, ...xs]) => x;
const tail = ([x, ...xs]) => xs;
const map = (list, fn) => {
if (list.length === 0) {
return [];
} else {
return [fn(head(list)), ...map(tail(list), fn)];
}
};
map([1, 2, 3], x => x + 1); // [2, 3, 4]
Somewhere underneath there will need to be something maintaining state, but it won't have to be local state in the function (in a pure language, typically it will be within a built-in with a pure interface.) FP isn't about changing the fact that computers operate by mutating state, but to isolate such mutations (and other side effects) behind pure interfaces, so that risk and difficulties associated with effectful code are isolated to, ideally, extremely well understood pieces of infrastructure code rather than permeating large codebases.
One of the major goals for Haskell programmers (and users of fancy-type-systems in general) is to make it easy to transform runtime errors to compile-time errors. Further, an additional goal (albeit one which Haskell doesn't prioritize as much as some of its relatives) is to make the compiler better at telling the programmer what is wrong and how to fix it. If you have no interest in these projects and don't see why they could lead to code which is more reliable and easier to maintain, then your confusion about why people care about this stuff in the first place is perfectly reasonable IMO.
Conversely, when writing green-fields code, side effects are extremely convenient and make developers more productive in the very short-term.
So I'd agree that focusing on the reason you are writing the code makes everyone more productive, though not just in the short term. ¯\_(ツ)_/¯
Now how you organize your code so that you don't mix things up willy-nilly is a different, more nuanced and, I think, more interesting question.
I am a big fan of hexagonal architecture, where you have a very localized and super-testable core with, ideally, all the complex functionality, surrounded by adapters that are as trivial as possible and communicate with the outside world, be that the user, persistence, network etc.
FP is one way of achieving this, but certainly not the only one.
Functional programmers (of the Haskell bent, at least) would prefer that they not have to write printCatsBelongingToStaff, printCatsBelongingToCustomers, printCatsBelongingToChildrenOfStaff, printDogsBelongingToStaff, renameCatsBelongingToStaff, &c. They would instead prefer to write print, rename, staff, customers, cats, dogs (or perhaps just pets, with an ability to discriminate between cats and dogs...), children, and compose. They would also prefer to write these functions in such a way that the computer (rather than the human) can analyze the resulting compositions and guarantee that they operate in the way you would expect (with "expect" being precisely codified between the types of the functions and a succinct set of laws).
The big picture here is that computers are much faster and more consistent in their checking ability than humans, so the more things we can encode in our programs in a computer-checkable way, or in laws that we can prove are preserved under composition, the more reliable our software will be on whole.
Of course in Python you could parametrize the predicates or the attributes or attribute values, and it would still be fine FP code.
Say we want to reuse your cat search code. Sometimes we want to log it, and sometimes we want to export it as a different data structure.
You could write a function that took a company and returned a list of pets.
What if you wanted to take the first 10 of 10 million. Returning the full list wouldn't be very efficient, you would need to alter your function to support limits.
What if you were then given a list of companies. You would need to modify the function, or write a wrapper.
What if it isn't a list anymore but an async stream of companies. More modifications.
With functional techniques, we can abstract the concept of "filtering a company for pets" without worrying about the concrete implementation of how the returned pets are stored. This allows the one function to be reused efficiently in many different applications, in ways not possible with imperative code.
This is just one example of abstraction that is possible. Functional techniques are not a good fit for all problems, but they are a good tool to have in your toolbox as they make some problems much easier to reason about.
Paul Graham has written a lot on the power of functional languages. OnLisp is a good place to start: http://www.paulgraham.com/onlisp.html
Or some of his early blog posts discuss these concepts: http://www.paulgraham.com/articles.html
Another classic that will change the way you look at code design is Structure and Interpretation of Computer Programs: https://web.mit.edu/alexmv/6.037/sicp.pdf
Ah - how about if we add "by the compiler": They can be analyzed much better by the compiler, and we get neat safety guarantees by the compiler.
> Is my code hard to analyze or unsafe?
Not for a human, no :) But optics allow us to drop some boilerplate, retain all flexibility, and also allow the compiler to do a deeper analysis so we can compose computational patterns. That composition composes, so as we build more complex things we have tools with us to help navigate them.
The second advantage is conciseness. I don't know if you've actually used jq, but if you have, I really don't know why anyone prefers a verbose for-loop-and-if-statement block over a single concise jq expression. Paul Graham expressed this idea better than I could have so read this: http://www.paulgraham.com/power.html
{company: {staff: [{..., pets: []}]}}
And what we want to do is to produce a list of all the pet cats with its owner name.
[{cat: "bla", owner: "bla"}...]
or
[{owner: "bla", cats:[...],...}, ...]
So I guess what Im trying to explain is that what is important is the change in the way of thinking about problems. When you think of them as data transformations there is a whole lot of possibilities that open. And it is not more expensive because you even have things like transducers. When you abstract away the iteration you are able to compose much more easily.
And to answer your question directly in my example the print function would print for each cat belonging to the staff which is not great flattening would be more elegant. What I wanted to convey is thinking in data transformations and abstracting away the implementation details of the iteration.
const stf = [
{name: "x", pets: [{type: "cat", name: "kitty"},
{type: "cat", name: "kitty2"}]},
{name: "y", pets: [{type: "dog"}]},
{name: "z", pets: [{type: "cat", name: "miau"}]},
];
const myTransform = ({ pets, name: ownerName }) => pets
.filter(({type}) => type === "cat")
.map(({ name: catName }) => ({ ownerName, catName }))
stf
.map(myTransform)
.flat()
.forEach(({ownerName, catName}) => console.log(`Cat ${catName} to ${ownerName}`))It's all right. In the sense of using a tool when you find yourself constrained perhaps it's worth waiting till you find a problem where you feel "there's got to be a better way".
It's happened to me when I was writing generators/shrinkers for generative tests that operate over any Thrift or Protobuf type.
for (owner <- company.staff)
for (pet <- staff.pets if pet.type=="cat")
yield (owner.name, pet.name)
That said, I'm presently struggling with AST transformations and other fun stuff in Haskell, so I completely agree with stating it imperatively. It's far, far easier to learn and read simple imperative code.
That's why in my language Tenet[1] I'm trying a hybrid approach: the underlying representation is immutable, but the language uses ordinary control flow and mutation.
Not all functional languages have static typing. Also type checking helps, but saying that if the types check out it just work it pushing it IMO.
No type checker will catch this error:
sqrt :: double -> double
sqrt x = x
sqrt 10The types of the arguments to the function can have value constraints on it, and those constraints can be determined from a value that exists there: the name of the function.
First, I don't know that dependent types have huge decidability issues that are an inherent obstacle in general; Idris for one has a very practical and elegant model of computation – things like totality checking, linearity rules and elimination of "scaffolding" types do a lot for us.
Dependent types do allow telling the compiler about more dimensions to consider – in a way that allows for a computational explosion at compile time – but those were always an available to consider as part of the computation; Dependent types dont add that complexity, rather they allow us to address it in the type system. I see it such that we're in a stronger position to manage and navigate that complexity by allowing us to express it to the compiler in a succinct and clear way near the core context of desired action. Dependent types allow us to do less by allowing us to do more.
And integrating purely functional mechanisms with side effects is a fun and interesting avenue of research, and I don't know that adding dependent types makes that more difficult; I'd think it makes it easier?
"This function's type depends on its function name. If its function name is "sqrt", then {check some simple rules about square roots, like if x is 0 then output is 0, if x > 1 then output < x, etc.}"
This one too:
"This function's type depends on its function name. If its function name is "sqrt", then check that it calls and returns a formally verified square root function applicable to its input type that is known to be decidable and appropriate to the floating point math definitions we're operating in right now"
In any case, the more code you put into the type system the higher the chance that your dependent type specification haS a bug in it.
Wrote a bit more earlier: https://news.ycombinator.com/item?id=24716477
> the more code you put into the type system the higher the chance that your dependent type specification haS a bug in it.
Unbounded infinity has infinite, uncountable bugs. A defined, bounded, well-constructed, proven type system has fewer bugs. Dependent types are not an axis of explosion, but rather a way to express useful bounds on multiple axes.
Less bugs does sound good, but after a minute thought there still seem to be uncountably infinite bugs even in the presence of dependent types. Just a few less than without. :)
(But yes: It's a good place to hook the AGI up!)
Obviously if the spec says to create a word processor program, and you instead write a flight simulator, the compiler isn't going to correct that mistake.
Even the multi-paradigm, late-bound languages that are adding functional programming are adding static typing, e.g. TypeScript and mypy.
> No type checker will catch this error...
Sure, math is hard. In the domain of structural transformations, one's intuition combined with a decent type checker really does work, though.
Especially, I've done large refactorings of complex transformations, tracked down the typing errors, and then been pleasantly surprised when my test-suites passed the first time.
> sqrt :: double -> double
I can use QuickCheck[1]:
prop_Sqrt_Sqr n = sqrt n * sqrt n == abs n
[1]: http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html
I strongly dislike hybrids, multiparadigm, metaprogramming, and inheritance-heavy OOAD.
Most of our work is CRUD, meaning data centric. Right?
My arm wavy overgeneratalization is that functional programming promotes functional decomposition style programming, which emphasizes flow of control modeling over data modeling. Especially when noobs go overboard with lambdas, stream processing, reducers, and so forth, which obfuscates the data transformations.
Whereas imperative programming can be more straightforward for simple data processing. Until noobs go overboard with OOAD stuff like inheritance, making wrapper classes for everything, and design pattern overkill. Then the wheels fall off and the engine explodes once someone reads a book about inversion of control, dependency injection, mocking, aspects, or optionals (non-null).
YMMV.
The fact that method selectors only appear very rarely as first-class values in most languages means that most people aren’t tuned in to scenarios where they could be applied. But I bet you’ve invented special cases of this yourself, when you had a function that needed to dig data out of one of several locations, depending on other inputs.
And leaky "abstractions" that create more problems than they solve but look cooler than doing things the straightforward way.
I know it's easy to forget how much .. stuff .. there is in an imperative language. You have the side-effect in print, and if you replace that with appending a string you're going to invoke the weird and wonderful assignment operator.
It's easy to forget how strange these things (state and side effects) are once you have mastered them in your craft.
The reason I love functional style with immutable data is because it is so dead simple and easy on my tired brain.
import optics.for as o_for
o_for company.staff.pets as (.{pet}, optics.parentNode as owner) where (pet.type == "cat"):
print "{.name|%s} belongs to {owner.name|%s}")
This is the very simplest use of optics. Optics also allow us to do express wild things over those structures, such as selecting nodes based on some defined statistical relationship to the statistics of defined parts of the whole structure. It's as simple and concise as the example above. And as efficient as possible.
- lenses “focus” on elements of a product type
- prisms “split” a sum type so that optics can work over selected branches
...feels nice when you’ve been working with it for awhile.
1. The analogies made do hint at their meanings.
2. But at the same time, the names are more proper nouns than definitions. For something so abstract, it's better to give it an opaque, easy-to-remember name than to give it a "better" name that maybe oversimplifies what it is.
This is basically the "Functor" vs "Mappable" argument.
[1] Also follows the rule of "if you're going to name something after a common word, maybe give it a qualifier not usually used with that word to make it unique and easy to find". Examples: sphinx (doc, search), click (cli), pyramid (web framework), pacman (linux), language (programming).
In response to the naming in general: I’m not overly convinced about the naming thing considering that the Go Programming Language is not often confused with the game of Go, nor is the Rust Programming Language with the fungus or iron oxide.
https://www.google.com/search?source=hp&ei=mL5-X7iCJNCs0PEPo...
First result is to the popular and well-documented `optics` library which is exactly this topic. It's perfectly discoverable.
On that note, try googling "Haskell >>=" or "Haskell <$>". Good results for both. Looks like the "Haskell's symbols and esoterica isn't googlable" is a dead argument now :)
Wow, it works! I wonder when this happened.
The basic implementation is predicate composition as we support multiple combinations of filters.
I hadn't thought any deeper about 'traversal systems' or optics, just parsing a grammar, creating predicates, and composing them. This is an interesting read, perhaps I should take the Clojure impl. further.
https://www.youtube.com/watch?v=7krDIMjVzZM
Probably the most fun coding I've done this year because I had an excuse to use the wonderful Instaparse again.
from __future__ import print_function
import json
struct = json.loads(open('staff.json','r').read())
staff = struct['staff']
salaries = struct['salaries']
def visit_pets(staff, cond, visit):
for person in staff:
for pet in person["pets"]:
if (cond((person, pet))):
visit((person, pet))
# Find all cats owned by any of our employees
visit_pets(staff, lambda t: t[1]["type"] == "cat", lambda t: print(t[1]))
# Find each pet and their owner
visit_pets(staff, lambda t: True, lambda t: print("{} belongs to {}".format(t[1]["name"], t[0]["name"])))
# Give a $5 raise to anyone who owns a dog
dog_owners = set()
visit_pets(staff, lambda t: t[1]["type"] == "dog", lambda t: dog_owners.add(t[0]["id"]))
for staff_id,salary in salaries.items():
if staff_id in dog_owners:
salaries[staff_id] += 5
I wish more people promoted this view of FP - just pure functions, higher order functions and referential transparency. It gives you the ability to reason locally and extend code well. The remaining type system and architecture astronomy buys very little in relation to what it costs.
1. let the compiler reason about my code to catch errors when the requirement changes (say, when some record fields change their names or types),
2. thus lower my cognitive load, and
3. allow me to reason about more important aspects of the project.
At work, the use of a powerful and expressive type system allowed me to work on multiple projects at once, achieving at least 2 times boost in productivity (definitely more than 20% gain).
Moreover, if optics is not well-known to everyone, I can just link to this blog post as a documentation, and give more examples if needed (I think people underestimate how coworkers could be productive without completely understanding everything).
It is hard to explain the experience of “pair-programming with the compiler”, but such complication is worthwhile for the productivity gain (and developer happiness).
The fundamental idea behind the approach in the article is the following:
Treat the path through a nested data structure as a first-class thing.
This gives helps us mainly in two scenarios:
1. Allowing for easy field-update-like code to exist for immutable data structures in addition to mutable data structures. This is especially valuable for updates.
2. Unify everything that can be "field-like" under a consistent field syntax.
In most class-based languages we can write something like
myObject.field0.subfield1.subsubfield2
def myPath(someObject):
return someObject.field0.subfield1.subsubfield2
To the second point, even if someObjet were mutable, there are a variety of things that would be nice to have as field accesses, but aren't, simply because they don't fit into a class definition. As an example, consider the bits of an integer.
# Imagine .permissions.bitMask.lastBit to be a path
# through user
set(user, .permissions.bitMask.lastBit, 0)
If path access through data were a first-class concept, there's no reason that paths should be restricted to only fields in classes. You can fit the same interface to anything that supports the notion of "field-like" access.