Functional core, imperative shell (2012)
destroyallsoftware.com
destroyallsoftware.com
I end up recommending this video at least once every year.
(EDIT: Another one from Gary that pairs well is "Boundaries": https://www.destroyallsoftware.com/talks/boundaries . The core idea is that values -- data, not code -- should form the boundaries between distinct systems.)
It is the observation that all software is built of 3 layers -
Inbound IO, what you call imperative shell Business logic core, what you call functional core Outbound IO, what you call again imperative shell.
The problem with the terms in functional programming is that when they say side effects, in most cases they mean IO.
The functional core does not have to be functional for you to get the benefits - easy testing, easy to reason about, easy to develop. In fact, in some cases, functional programing is the wrong tool while having a business logic core that is separated from IO is still a very valid architecture.
https://www.destroyallsoftware.com/talks/the-birth-and-death...
What I find fascinating is that, at least for me, using GenServers/Agents/Tasks has made this distinction much more obvious than it has been in other languages.
I've built horrifying systems that muddled things together, only to realize quite far in how much of a mess I made, but with my Elixir projects I usually realize what I've done pretty quickly, and I end up course-correcting earlier on.
I think it's also related to the concept of building a DSL in which to implement business requirements. Once you have the right 'primitives' you can then combine them in useful ways that are easy to verify (by reading the code) that the implementation matches the requirements.
If you want to insert stuff randomly, you wouldn't use lists to get the best results in a functional setting. You might use something like finger trees instead.
For instance, the "single linked list" or simply "list" has constant-time push and pop operations. Here such a list of 3 elements (NIL is a special value that says "no more list")
L = (((v1, (v2, (v3, NIL)))
To add v0 in front, you just create a new "cell" that reuses the old list (which remains valid by itself) as the "tail" of the new list:
L2 = (v0, L)
L2 = (v0, (((v1, (v2, (v3, NIL))))
Depending on your requirements, there are more complicated and smarter data structures that can make the operations you care about either constant, or at most logarithmic.
I recommend this free book to learn more and get better at Computer Science in general: https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
* GC: it probably had a very simple algorithm, rather than a fancy generational GC
* Data structures: it wouldn't support modern functional structures like HAMT
* Compilation: you probably used an interpreter, rather than compiling the code to bytecode or native code
...and of course, the algorithm itself. It may not have been designed for functional data structures, or you may not even have implemented it in a functional style in the first place (Scheme supports mutation).
It's a Scheme-to-C compiler (plus interpreter / repl / script runner.) The Scheme code is transformed into continuation passing style (CPS) and then translated into C function calls that never return, but call other functions instead, forever. Therefore the C stack can only grow, never shrink, and is used as a natural "nursery" or first generation of allocation. When it eventually overflows, the garbage collector is invoked, which scans the stack for "live" values and moves them into the permanent generation (on the heap) and resets the stack; after which, execution resumes.
It's the most ingenious way I've ever seen to turn not just Scheme, but any language with automatic allocation into fully standard C code. I think there's only one non-portable function written in assembly, the garbage collector that runs when the C stack overflows. That's a small price to pay to have a compiler that can piggyback on any existing C compiler, for virtually any platform. (It's not even entirely in assembly. IIRC, it uses some kind of setjmp / longjmp sorcery.)
Moreover, the generated C code is fully tail-recursive and call/cc comes for free, so you can use first-class continuations in complex ways, without any performance penalty. It has hygienic macros and all the advanced stuff you expect from a modern Scheme. And of course you can link to any C library, use standard C APIs from Scheme and have your code compiled to optimized machine code.
If only Scheme was not a dynamically typed language... but that's a rant for a different time.
The term for this is "persistent data structures", usually implemented via trees, where replacing an object in a vector is implemented by building a new tree, reusing all of the old nodes except the ones that appear in the path from the root to the replaced node. That's why Clojure's Vector is log32; it's a 32 b-tree. (I'm writing this from memory and have little Clojure experience, but I'm pretty sure I have it right.)
Many languages have implementations now, but most aren't as fast as Clojure's. E.g., there's immutable.js: http://facebook.github.io/immutable-js/
I was not familiar at all with this stuff when I read through it the first time, so it was a tad mind-bending and I probably understood ~10% of it, but it was certainly educational.
The biggest benefit seems to be when adding elements within a for loop. The example on this page illustrates how you could use this. https://clojure.org/reference/transients#_example
At times, the simple process of figuring out what the really necessary points of mutation/IO are and how to "fence them off" is all I need to simplify big chunks of an existing "ball of mud".
Monadic interfaces in the context of non-deterministic effects are a consolation prize. They represent a way to combine effectful code, but ideally your code would have almost no effects at all.
As far as I can tell, the idealized version of this talk is a batch interface: one effect to grab all the data you need, transform the data, and then one effect to "flush" the transformed data (where flush could mean to persist the data in a database, send it out as commands to control a robot, etc).
Tracking side effects in your types (maybe what you were going for?) is helpful for measuring to what degree your code fails to adhere to this idealized model. If most of your code has an effect type, that's probably a sign to refactor. It also keeps you honest as to the infectious nature of effectful code by propagating the type as necessary.
Monads exist exactly because mutation is a reality. Monads do not defy the "mutation reality", nor try to encourage programmers to never look inside them. They are a means of dealing with the "mutation reality" by encouraging to separate pure and impure parts properly and while still making functional composition possible. The image you create for monads is a straw man. Monads ARE a kind of "disciplined mutation" as you put it.
You don't have to like them nor prefer them. But they are clearly a great and established abstraction loved and used by many. You may prefer Clojure, I get it, but I see no reason to talk shit about monads in this way. Have you ever used monads and similar abstractions extensively?
> Monads is taking it too far.
> Mathematical purity of programs is a myth propagated by Type theorists dont buy into it.
Those are big words. Are you some kind of authority? You could have at least prepended "I think" to those phrases.
> Those are big words. Are you some kind of authority?
Yrs of writing programs have taught me that programming functions are not equivalent to mathematical functions, there is no equivalence that exist stop pretending that it does.
Monads exist independently from Haskell and are not about "things that change".
You didn't respond to anything they said and you doubled down with your nonsense about "Monads exist because because haskell people want to pretend that there is this ideal mathematical world where things dont change."
That monads ignore the "mutation reality" isn't a very strong point when monads are a concession for the "mutation reality." Unless you want to repeat yourself a third time, the ball is in your court to bring concrete supporting arguments since you're making the extreme and somewhat self-aggrandizing claim that these other people don't really see the mutation reality of the world like you do, thus they are using inferior tools.
I'd say that anyone specifically trying to corral/isolate their I/O code (monads or not) are so "enlightened" about the mutation reality of the world that they use specific abstractions to address it.
If you want to see code that tries to paper over I/O, look at a program where you can't even tell when and where the I/O is performed because it just looks like any other function call. Active Record in Ruby on Rails might be a good candidate in its effort to make DB access opaque to the programmer.
Large projects inevitably benefit from static guarantees enforced automatically by your environment. That can be a 3rd party static code analysis tool or the compiler. Even just a linter will improve code quality and thus developer happiness and productivity.[] Having your compiler enforce* the functional core/imperative shell, and exposing your business logic only through functional components is what makes a strongly typed language of the ML family stand out over, say Clojure.
Mutating state is no problem in a strongly typed functional language. In Haskell, just put your computation in an ST Monad. You can even still expose a functional signature that doesn't leak the ST monad if your algorithm is faster with mutation.
[*] Overall. Some people will probably be unhappier, because they have to follow "arbitrary" rules now, but those would usually have been the worst offenders.
Immutability also makes you code better but it's an orthogonal concern and utilising both is a smart move.
That works reasonably well in some situations, but not all.
We often work with local, temporary state, meaning something mutable that is only referenced within one function and only needs to be maintained through a single execution/evaluation of that function. (Naturally this extends to any children of that function, if the parent passes the state down.)
If that function happens to be at a high level in our design, this can feel like global state, but fundamentally it’s still local and temporary. I/O with external resources like database connections and files typically works the same way.
We can also have this with functions at a lower level in the design. An example would be using some local mutable storage for efficiency within a particular algorithm.
However, not all useful state is local and temporary in this sense. We can also have state that is only needed locally in some low-level function but must persist across calls to that function. A common example is caching the results of relatively expensive computations on custom data types that recur throughout a program. A related scenario is logging or other instrumentation, where the state may be shared by several functions but still only needed at low levels in our design.
Now we have a contradiction, because the persistence implies a longer lifetime for that state, which in turn naturally raises questions of initialisation and clean-up. We can always deal with this by elevating the state to some common ancestor function at a higher level, but now we have to pass the state down, which means it infects not just the ancestor but every intermediate function as well. While theoretically sound in a purely functional world, in practice this is a very ugly solution that undermines modularity and composability, increases connectedness and reduces cohesion. And weren’t those exactly the kinds of benefits we hoped to achieve from a functional style of programming?
If anyone would like to read more about this, we had an interesting discussion about these issues and how people are working around them in practice over on /r/haskell a couple of years ago:
https://www.reddit.com/r/haskell/comments/4srjcc/architectur...
Spoiler: We didn’t find any easy answers, and everyone is compromising somewhere.
Then look at Elm code. Elm does not have any imperative hatches. The monad that runs everything is at the very top level (“shell” as the article calls it) and hidden.
As such Elm code is forced to use functional decomposition resulting in very easy to follow, refactor and maintain designs.
If you're working with a free monad, or if you don't specify IO (just some of the generic IO like typeclasses like say MonadError), you can still choose your own interpreter for the monad and "program" the semicolon. Which means you get back all the benefits of testability etc.
To get a similar effect in an imperative language, you would use e.g. coroutines and `yield` every side effect to the execution engine. The engine will take the action "specs" (probably a data structure describing the action to perform, e.g. set some value in memory) and decide what to do with them, and you can swap the real engine with a test/mock engine in your tests.
It is pity that modern conveniences like polimorphic record types with nice syntax for record updates were not invented earlier. With those even with complex code monads can be used only at the top level when the sugar of do blocks is not even necessarily.
If one looks at the desugared version one can see where the trouble comes. Functional code using monadic style depends on the state of the monad interpreter that can be arbitrary complex and spread over many closures with many interdependencies. It can be rather hard to uncover what exactly is going on, precisely in the same way as with imperative code it models.
Thank you for saying this. You clearly have a good understanding of English(far better than mine at least). I feel like this is an area that is glossed over. For every article that is written in english there are at least 10+ non-native speaker struggling to understand the work, who could extract something useful or help explicate the work.
Almost any app will involve some imperative code, but using pure functions within that, where possible, makes it easier to reason about what is going on. That's all there is to it. https://en.wikipedia.org/wiki/Referential_transparency
As a native English speaker, I generally have the same preference you do. Articles I can skim, they're easier to refer back to, and I can search.
I hope you can take solace that I will sometimes search for an error message and the only result is a forum posting in a foreign language that Google Translate barfs on.
In this particular case, I'm annoyed too. I've learned (what I think is exactly) this concept from other sources, and I've been recently linked to this video a couple times. What I would love to do is to quickly diff my existing knowledge with contents of the talk, but I can't do that because it's in a video format. I've been putting off watching it for couple weeks now.
That said, I'd also prefer an article that tells me the same thing.
How do you do this cleanly when, e.g., you need to make a network call and then based on what the result returned to you is, either do something with a local database, make a different network call, or return a result to your user. Also, error handling...
It seems to me like monads must be the logical conclusion to this style of programming, or else you wind up with a mess (or just abandoning this technique.)
It's really extremely productive to code this way... I wrote a job scheduler from scratch in 3 months and never once had to write or use a mutex or semaphore. Immutability makes you very confident about your code.
Similarly, my UI guy wrote a UI in basically functional react. It's amazing. With very little js experience I made code patches that.. just worked because I was guaranteed that no function calls had mysterious side effects...
For a fp react example: https://github.com/streamproject/cryptopotamus-web
It's quiet the opposite really from what I've seen. Elixir places absolutely no constrains on when and how IO happens, and provides extremely useful primitives for shutting state between (VM) processes in otherwise stateless code. A library function that looks totally pure could, for example, boot an entirely different subsystem that fired a missile into the sun before providing a return value and you'd never know it if you didn't read the docs, or use one of many pieces of fantastic beam tooling to inspect the runtime state of the system.
This is part of what makes these languages pragmatic to work in. There are foot guns everywhere, but the VM ensures you sign into the foot gun registry whenever you use them.
Here is a good talk about these ideas: https://www.youtube.com/watch?v=US8QG9I1XW0
This is a good example:
https://www.theerlangelist.com/article/spawn_or_not
(Note the context is Elixir, so it’s talking about lightweight processes, not OS processes. It explains how to keep that stateful / effectful code very simple, and have all the real logic be pure functional code.)
A lot of apps out there do nothing more than fetching data from one service, and dumping it out to another.
Now of course, you don't have to cleanly separate a functional core from a stateful shell. But if you don't, all of your code is going to end up wrapped in nested Monads declaring all of the ways that it's inadvertently stateful, and that's a very painful way to program. So Haskell pushes you strongly towards having a functional core and stateful shell.
For projects written in Haskell, the wiki has a long list: https://wiki.haskell.org/Haskell_in_industry
Yeah, I guess the `do` notation makes it pretty painless. If you start mixing monads, though, things get hairy quickly.
It also provides a huge opportunity for testing. At a very high level, you describe all of your effects as a series of embedded, compostable DSLs that you define interpreters for. The awesome part is that you can switch out the interpreters at will, so you can, for example, replace something that handles network requests with something that returns dummy data almost effortlessly.
http://hackage.haskell.org/package/transformers-0.5.5.0/docs...
> It also provides a huge opportunity for testing. [...]
That's a neat point, thanks for bringing it up.
You don’t need full blown monads to do this, just need to be cognizant to how you separate the what (functional core) from the how (imperative shell). I recommend giving it a try!
Most of the code (Layout.hs and StackSet.hs) is pure and has extensive unit (property-based) tests for all the pure functional core.
https://github.com/xmonad/xmonad/tree/master/tests/Propertie...
Then there is a layer that talks to X11 and interfaces with the functional core. (Core.hs and Main.hs)
The good part is the set of pure functions that take input and compute something from it.
But the awkward part (assuming you're coding in a typical mainstream imperative language) is the "transaction script" that gets an input, passes it to the pure functions, and then takes the result and writes it out. If there's no event loop and you're not using promises or something like that, it forces an awkward boundary right down the middle of your code that just feels unnatural.
Still, I think it's worth it for many problems. The vast majority of your code is pure functions -- simple, understandable, testable. The price you pay is this unnatural seam at each point of IO.
Monads are nice, but there's a lot of work on algebraic effects/effects in general which may pan out into something useful (and more general).
That is locally scoped, mutation-heavy, imperative code is fine as long as you can wrap it in a deterministic, immutable interface for general use. This is the premise behind things like Haskell's ST type. More generally it's the usual way FP languages try to recover competitive performance.
Yes! Clojure supports this via transients. What's even better is that you can write the loop using immutable data, make sure it works. Then just
1. add a call to transient in the initializations,
2. add a call to persistent! in the end and
3. add a ! to each function that modifies the transient, e.g. conj becomes conj!
The benefit in doing it this way is that the language will catch and flag as errors any "mixed" usage - calling a pure function with a mutable argument or vice-versa.
https://clojure.org/reference/transients
http://www.hypirion.com/musings/understanding-clojure-transi...
Return a DTO that encapsulates all the business information about the result state of the I/O call. Do not throw exceptions. Log them if you like, but you must return all the data necessary for the business logic to react to failure conditions, encoded in your own use case specific structure.
If you don't care about whether you failed due to timeouts or refused connections or query parse failures what have you, don't return that data, just return a hasError kind of property on the return structure (bonus points if your language supports discriminated unions, but this is not necessary). If the parent logic needs to react to timeouts and failures to connect differently, then catch those exceptions or state separately and return didTimeout or cantConnect flags separately.
Values values values
It’s much safer to type-check at compile time that you have discriminated between result and error, than to hope that you are ‘if’-checking some flags at the right time at runtime.
(In Haskell, one way of getting into unproductive infinite loops is by mistakenly asking "parse elements until the first failure" to a parser combinator that can always succeed without consuming input.)
The ideal is that the core of the application should be both pure and total, purity and totality being tracked by the type system. In fact, one can often relegate partiality to a single function of the outer shell.
Edit: correction from commenter, thanks!
Seriously though, this talk, Boundaries, and Simple Made Easy are the trifecta that forms the foundation of the software I design.
Reminds me a bit of Ryan Bate's ruby/rails videos.
InfoQ has a very nice summary of DDD book: https://www.infoq.com/minibooks/download/domain-driven-desig...
For example, to avoid excessive memory consumption to sum matrixes one wants to code it like A += B, not like C = A + B. Yet one still benefits from all the testing, design etc. benefits of pure functional code. At the end one call always get a functional version just by turning A += B into C = A; C += B.
The timeline as he explains it, is updated by creating a new timeline instance which consists of previous timeline + new tweets. It seems to me then, that his client does not remove from the timeline tweets that were deleted by its author subsequently to having been downloaded.
To some it might be a feature to capture as many tweets as possible, but at the same time, if your view of the timeline includes deleted tweets then you might find yourself trying to reply to a deleted tweet, and then you would get an error response from Twitter when you try to post your reply. (Though I don’t know if his client also does posting, or if it’s a read-only client.)
Furthermore, what about tweets that are edited by their author subsequently to having been downloaded? Seems that you would not see those edits.
How might this be implemented within the data model?
If you have N elements, then the initial worst case time is N^2. Say after the first partition, you are left with pieces N/3 and 2N/3; the worst case time is now (N/3)^2 + (2N/3)^2. Your progress after the first partition is the difference between the original worst case and the new worst case.
This can make for uneven progress advancement but it’s monotonic: the progress bar will never go backwards.
1: Returns the sorted list (once finished)
2: Returns an intermediate state containing the progress of the sort in addition to the current state of the sort.
You would repeatedly pass the intermediate state to the sorting function until finished. You can use the progress component of the intermediate state to track progress.
Something like the following (I don't actually write Haskell, so this could probably be represented better):
data SomeIntermediateState = ...
data Progress = Double
data SortState a =
Complete [a]
| InProgress (SomeIntermediateState, Progress)
sortInit :: [a] -> SortState
sort :: SortState -> SortStateI end up with a lot of code writing values to the disk, which is currently mixed in with the computations. I'm wondering if there's some way to automate this "save intermediate values to the disk" so I can write the code in a more functional style without having to constantly go in and out of the imperative shell portion.
The process of ML experimentation is extremely painful compared to normal software development where nothing really takes that long to compute.
The "Embedded DSL + Interpreter" pattern is incredibly powerful, and it's nice to see it catching on more.
You're complaining about syntax, but this screencast is about semantics.