13 ms·

Cyclic dependencies are evil (2013)

129 points by nojito 6y ago

Smaug123 6y ago
EDIT: In fact I appear to have paraphrased the next post in the series, https://fsharpforfunandprofit.com/posts/removing-cyclic-dependencies/ https://fsharpforfunandprofit.com/posts/removing-cyclic-depe... . Probably go and read that instead. One pattern this nudges you towards is having a Domain.fs at the top of each project. Since everything in your project wants to talk in terms of the data types you've modelled, it makes sense to put them all in the same place at the top. Moreover, once you've done that, you're guided towards having your data types really being "dumb" - algebraic data types only - because to put actual behaviour into them is harder when all you have is definitions of data types (and no associated modules). You certainly can write OOsagne using the Domain.fs pattern, but it's much harder and the code really smells when you do (because the domain file gets super long). The upshot is that your domain model appears explicitly at the start of the project, which is a big win for anyone who comes into the project and needs to learn quickly what's going on. By contrast, nearly all the C# I've ever come across has the domain spread across many files and all mixed up with implementation details. This is certainly not the only way to write F# - I've written projects which have the domain spread across multiple files - but it's one nice way to handle a small-to-medium-sized project.
- mattgreenrocks 6y ago
  This is hexagonal architecture. I’ve yet to see anything quite as nice as it once I started using it. The only downside to hexagonal architecture is that you start to see how mediocre most architectures are, and how frameworks often cap how good your architecture can be by virtue of their structure. Frameworks tend to resist being put on boxes, and hexagonal architecture tries to put all external dependencies in boxes.
bob1029 6y ago
Language constraints aside, the real world is not something that can be cleanly modeled without the notion of circular dependencies between things. Not very many real, practical activities can be truly isolated from other closely-related activities and wrapped up in some leak-proof contract. Consider briefly the domain model of a bank. Customers rely on Accounts (I.e. have one or many). Accounts rely on Customers (i.e. have one or many). This is a simple kind of test you can apply to your language and architecture to see if you have what it takes to attack the problem domain. Most approaches lauded on HN would be a messy clusterfuck when attempting to deal with this. Now, if I can simply call CustomerService from AccountService and vice versa, there is no frustration anymore. This is the power of reflection. It certainly has other caveats, but there are advantages when it is used responsibly. If you want to understand why functional-only business applications are not taking the world by storm, this is the reason. If it weren't for a few "messy" concepts like reflection, we would never get anything done. Having 1 rigid graph of functions and a global ordering of how we have to compile these things... My co workers would laugh me off the conference call if I proposed these constraints be imposed upon us today.
- titzer 6y ago
  I don't understand how reflection is involved here? Don't you just have a data model (schema) that can be interacted with?
- Smaug123 6y ago
  In F#, you would naturally approach this by defining a Customer independent of the Account (e.g. just containing a name and address), and an Account independent of the Customer (e.g. just containing an ID), and then a Bank which is a mapping of Account to Set<Customer>. What you see as a cyclic dependency, I see as a data type that you haven't reified.
  - JackFr 6y ago
    This came up in an application I had modeling college football. A Team is a member of a Conference and a Conference is made up of Teams. But during realignment a few years ago when teams were switching all over the place it became apparent that Teams and Conferences were truly independent of each other and that their association itself was a first class object which also needed to capture the Season/Year. Not really rocket science but some times your model is telling you something if you’re willing to listen.
    - kd5bjo 6y ago
      This is almost exactly the motivational example that Codd used when originally describing relational algebra. He described 5 different data organization schemes for a single problem and designed relational algebra to work with all of them. This ability for the same program logic to work with many different data storage layouts should make changes like you describe less painful to implement. (see page 2) E. F. Codd. 1970. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377–387. DOI:https://doi.org/10.1145/362384.362685 https://doi.org/10.1145/362384.362685 PDF: https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
      - gpderetta 6y ago
sbelskie 6y ago
I’ve played around with F# over the years, but have only recently started getting into seriously. The top down nature of dependencies (both within a given file and for the files within a project) is a little odd at first, but once you get used to it feels quite natural. If nothing else, it encourages (somewhat) common ways of structuring projects and avoids a lot of bike shedding about separation of concerns and project structure I encounter in C#.
- piaste 6y ago
  I had to sell F# (over C#) as the language for new projects to my CEO a while back. What I really wanted to say was: "F# lets us be lazy. You write way less code, you have fewer things to keep track of, you need fewer abstractions, you can write everything in the most straightforward way possible and then extend only when necessary because refactoring is super safe." What I _actually_ said was: "F# is an extremely rigid language. It will not let junior developers take shortcuts, because you must write your code properly or it won't compile. Your classes and functions must be written in the correct hierarchical order, you must cover every corner case. I know it's going to be stressful or boring to be forced to do things right every time and never be able to just push some sloppy cowboy fix, but it's a sacrifice we're willing to make :)"
titzer 6y ago
Nice article. The first thing that came to mind when seeing the title was "but circular dependencies just mean that your layers are wrong and those should all be in the same layer" and funnily enough that's exactly what's explained in the article! What would be interesting would be to organize modules into named layers--instead of just explicit 1-by-1 module dependencies (i.e. edges). I have not seen a language do that yet. Another interesting thing that I haven't seen touched on in more mainstream languages is the idea of bidirectional interfaces. The somewhat DSL-like NesC language had this, primarily driven by the need to write device drivers that serviced interrupts (and events).
- klyrs 6y ago
  > What would be interesting would be to organize modules into named layers--instead of just explicit 1-by-1 module dependencies (i.e. edges). I have not seen a language do that yet. Correct me if I'm wrong, but I think you're describing namespaces here
squibbles 6y ago
I still cringe when I think back to some C projects from long ago, where the dependency chains of headers and libraries where unfathomably byzantine. On a related note, lately I have been looking into some biochemistry topics and their relation to computer science. It seems that cyclic dependencies are possibly a requirement for life, which makes faithful simulations of biochemical processes an interesting challenge.
- dilawar 6y ago
  That is an interesting observation. I wonder whether the cycling in chemistry is more about information flow then like (negative?) feedback, it helps in making a stable system.
- mattgreenrocks 6y ago
  I’m a compiler nerd at the moment. I have an inherent trust of things that bootstrap themselves, as if it means they are conceptually more pure. I’m not sure whether that is 100% well founded, but it sounds similar to some of these observations. :)
  - ReactiveJelly 6y ago
    I think self-hosting is just a little over-rated for languages. It's good that Rust and C++ are self-hosting, you'd expect those to be languages you can write a compiler in. But Lua and JavaScript satisfy their own niche just fine without having popular runtimes written in themselves.
    - TheBrokenRail 6y ago
      There are a few JS interpreters written in JS, don't know about Lua.
    - mattgreenrocks 6y ago
      Most languages don't aspire to be so conceptually-complete that they insist on being bootstrapped. Which is fine, I make my living with them. Those that do, however, are immensely beautiful and there is more to be learned from them.
qudat 6y ago
For my FE projects I employ a module based code structure. If you import a module, you get the whole thing. This lends itself to many positives but one negative is it makes it easy to run into circular dependencies. I wrote an article discussing my architecture and how I solve circular dependencies in js. https://erock.io/scaling-js-codebase-multiple-platforms/ https://erock.io/scaling-js-codebase-multiple-platforms/ In the article I argue that circular dependencies are a good thing because they uncover poor code organization.
kstenerud 6y ago
This is one of the things that frustrates me about go. They started with this very good advice and then took it one step stupider: Disallowing circular imports. Why is this bad? It makes it impossible in many situations to locate your public API at the top level. Let's say you have a Widget interface and APIs to do things with those Widgets. Eventually your library gets complex enough that you want to separate functionality into subdirs. Now you have a problem: You can't access the definition for Widget from the subdir because importing the top level would create a circular import! The only way to get around this problem is to have no code at the top level, and put your public API in a subdir. Just be sure to do this when first starting your library or you'll have to break things.
- caylus 6y ago
  You can deal with that issue by defining things in a submodule, then importing and re-exporting them in the top-level (e.g. `type Foo = subdir.Foo`). That even lets you move things into the submodule without breaking callers. Other submodules can then import from the submodule rather than the top-level.
- xiphias2 6y ago
  This is how libraries are exported inside Google (use /public subdir for the public interface), and I guess with Go this got into the language. But I think Go made much worse things than this :)
codazoda 6y ago
I've never tried F# so I'm not sure I'm exactly "on base" here, but I actually think this way. It's frustrating to me when dependencies happen automatically or when they can be used before they are declared. It helps me understand what's included if I can see a nice list of all the dependencies. It helps me narrow down where the problem is if I only have to address dependencies I know have already loaded. I learned to program in the 80's however, and it probably is a bit "old school".
lazulicurio 6y ago
In a related vein, is there any sort of theoretical transform that can be used to convert cyclic dependencies into a tree? Similar to how lambda lifting eliminates free variables. (Other than the obvious one of treating the entire cycle as one node)
KingOfCoders 6y ago
This was one of the reasons I used lots of Interfaces back in the day with Java.
- username90 6y ago
  That doesn't remove circular dependencies though, it just hides them.
layer8 6y ago
The generic way to remove a cyclic dependency is by Dependency Inversion (not to be confused with Dependency Injection), so that a mutual dependency A <–> B is transformed into the noncircular set of dependencies { A –> BIntf, BImpl –> BIntf, BImpl –> A }. That is, at least one node in the dependency cycle is split into interface and implementation, breaking the cycle. Compilers for languages like C# and Java can deal with (seemingly) circular dependencies within a set of classes to compile, because when A uses B they only have to consider the interface (type signature) of B, not its implementation. (Cyclic dependencies between modules are still a problem, in particular for build systems.) I'm not really familiar with F# (so someone please correct me if necessary), but in languages that use type interference to determine function signatures, one consequence is that the interface (type signature) of the function then depends on its implementation, so you can't as easily invert the dependency as when you have explicitly declared type signatures.
- dfgdghdf 6y ago
  F# could have out of order definitions, but the designers chose not to because it lengthens compile times considerably.
danielovichdk 6y ago
Funny to see those layered architectures/designs. Tightly coupled dependencies are bad. Cyclic or not. And if you do mange to to a cyclic dependency you are not thinking about your design property. Imo
edflsafoiewq 6y ago
The simplest case where I'd want a circular dependencies is I have a module that defines some data types and functions on those types mod widget struct Widget fn show(Widget) { ... } fn join(Widget) { ... } fn calc_box(Widget) { ... } and one function is getting very long and complicated so I want to spin it out into its own module mod widget mod calc_box import calc_box from widget import Widget struct Widget fn calc_box(Widget) { ... } fn show(Widget) { ... } fn join(Widget) { ... } The reason the article gives that this is "evil" is that there is no hierarchy between the modules; the cycle is really just one big supermodule. That's true... but that was basically the point. Where is the "evil" here?
- vasergen 6y ago
  In that case you can separate ’struct Widget’ into another file. This way there will be no circular dependency
  - edflsafoiewq 6y ago
    I know how to break the cycle. What I'm asking is why should I break the cycle?
    - vasergen 6y ago
      It depends on situation. As an example, it could be difficult to write tests when you have circular dependency. As well depends on the language there could be strange ’side effects’ which would be difficult to debug.
cratermoon 6y ago
The mention of Lakos' book "Large-Scale C++ Software Design" reminds me of the epiphany I had when I read it. You could almost boil the entire book (and it's not a small one) down to "eliminate circular dependencies". That's trite, but Lakos walks through all the problems that large C++ projects had and lays out how all of them boil down to the dependency problem. Particularly interesting to me, at the time, was his analysis of how compile times got exponentially longer as interdependencies grew, to the point where even a small change required recompiling the entire code base. The section in Lakos on how to identify and remove circular dependencies was worth the price of the book.
pabs3 6y ago
Debian has been doing some work on this: https://wiki.debian.org/DebianBootstrap https://wiki.debian.org/DebianBootstrap Also the Guix and Bootstrappable Builds folks are working on this too, at a different layer: https://bootstrappable.org/ https://bootstrappable.org/ https://bootstrapping.miraheze.org/wiki/ https://bootstrapping.miraheze.org/wiki/

129 points by nojito 6y ago

EDIT: In fact I appear to have paraphrased the next post in the series, https://fsharpforfunandprofit.com/posts/removing-cyclic-dependencies/ https://fsharpforfunandprofit.com/posts/removing-cyclic-depe... . Probably go and read that instead. One pattern this nudges you towards is having a Domain.fs at the top of each project. Since everything in your project wants to talk in terms of the data types you've modelled, it makes sense to put them all in the same place at the top. Moreover, once you've done that, you're guided towards having your data types really being "dumb" - algebraic data types only - because to put actual behaviour into them is harder when all you have is definitions of data types (and no associated modules). You certainly can write OOsagne using the Domain.fs pattern, but it's much harder and the code really smells when you do (because the domain file gets super long). The upshot is that your domain model appears explicitly at the start of the project, which is a big win for anyone who comes into the project and needs to learn quickly what's going on. By contrast, nearly all the C# I've ever come across has the domain spread across many files and all mixed up with implementation details. This is certainly not the only way to write F# - I've written projects which have the domain spread across multiple files - but it's one nice way to handle a small-to-medium-sized project.

mattgreenrocks 6y ago
This is hexagonal architecture. I’ve yet to see anything quite as nice as it once I started using it. The only downside to hexagonal architecture is that you start to see how mediocre most architectures are, and how frameworks often cap how good your architecture can be by virtue of their structure. Frameworks tend to resist being put on boxes, and hexagonal architecture tries to put all external dependencies in boxes.

bob1029 6y ago

Language constraints aside, the real world is not something that can be cleanly modeled without the notion of circular dependencies between things. Not very many real, practical activities can be truly isolated from other closely-related activities and wrapped up in some leak-proof contract. Consider briefly the domain model of a bank. Customers rely on Accounts (I.e. have one or many). Accounts rely on Customers (i.e. have one or many). This is a simple kind of test you can apply to your language and architecture to see if you have what it takes to attack the problem domain. Most approaches lauded on HN would be a messy clusterfuck when attempting to deal with this. Now, if I can simply call CustomerService from AccountService and vice versa, there is no frustration anymore. This is the power of reflection. It certainly has other caveats, but there are advantages when it is used responsibly. If you want to understand why functional-only business applications are not taking the world by storm, this is the reason. If it weren't for a few "messy" concepts like reflection, we would never get anything done. Having 1 rigid graph of functions and a global ordering of how we have to compile these things... My co workers would laugh me off the conference call if I proposed these constraints be imposed upon us today.

titzer 6y ago
I don't understand how reflection is involved here? Don't you just have a data model (schema) that can be interacted with?
Smaug123 6y ago
In F#, you would naturally approach this by defining a Customer independent of the Account (e.g. just containing a name and address), and an Account independent of the Customer (e.g. just containing an ID), and then a Bank which is a mapping of Account to Set<Customer>. What you see as a cyclic dependency, I see as a data type that you haven't reified.
- JackFr 6y ago
  This came up in an application I had modeling college football. A Team is a member of a Conference and a Conference is made up of Teams. But during realignment a few years ago when teams were switching all over the place it became apparent that Teams and Conferences were truly independent of each other and that their association itself was a first class object which also needed to capture the Season/Year. Not really rocket science but some times your model is telling you something if you’re willing to listen.
  - kd5bjo 6y ago
    This is almost exactly the motivational example that Codd used when originally describing relational algebra. He described 5 different data organization schemes for a single problem and designed relational algebra to work with all of them. This ability for the same program logic to work with many different data storage layouts should make changes like you describe less painful to implement. (see page 2) E. F. Codd. 1970. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377–387. DOI:https://doi.org/10.1145/362384.362685 https://doi.org/10.1145/362384.362685 PDF: https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
    - gpderetta 6y ago

sbelskie 6y ago

I’ve played around with F# over the years, but have only recently started getting into seriously. The top down nature of dependencies (both within a given file and for the files within a project) is a little odd at first, but once you get used to it feels quite natural. If nothing else, it encourages (somewhat) common ways of structuring projects and avoids a lot of bike shedding about separation of concerns and project structure I encounter in C#.

piaste 6y ago
I had to sell F# (over C#) as the language for new projects to my CEO a while back. What I really wanted to say was: "F# lets us be lazy. You write way less code, you have fewer things to keep track of, you need fewer abstractions, you can write everything in the most straightforward way possible and then extend only when necessary because refactoring is super safe." What I _actually_ said was: "F# is an extremely rigid language. It will not let junior developers take shortcuts, because you must write your code properly or it won't compile. Your classes and functions must be written in the correct hierarchical order, you must cover every corner case. I know it's going to be stressful or boring to be forced to do things right every time and never be able to just push some sloppy cowboy fix, but it's a sacrifice we're willing to make :)"

titzer 6y ago

Nice article. The first thing that came to mind when seeing the title was "but circular dependencies just mean that your layers are wrong and those should all be in the same layer" and funnily enough that's exactly what's explained in the article! What would be interesting would be to organize modules into named layers--instead of just explicit 1-by-1 module dependencies (i.e. edges). I have not seen a language do that yet. Another interesting thing that I haven't seen touched on in more mainstream languages is the idea of bidirectional interfaces. The somewhat DSL-like NesC language had this, primarily driven by the need to write device drivers that serviced interrupts (and events).

klyrs 6y ago
> What would be interesting would be to organize modules into named layers--instead of just explicit 1-by-1 module dependencies (i.e. edges). I have not seen a language do that yet. Correct me if I'm wrong, but I think you're describing namespaces here

squibbles 6y ago

I still cringe when I think back to some C projects from long ago, where the dependency chains of headers and libraries where unfathomably byzantine. On a related note, lately I have been looking into some biochemistry topics and their relation to computer science. It seems that cyclic dependencies are possibly a requirement for life, which makes faithful simulations of biochemical processes an interesting challenge.

dilawar 6y ago
That is an interesting observation. I wonder whether the cycling in chemistry is more about information flow then like (negative?) feedback, it helps in making a stable system.
mattgreenrocks 6y ago
I’m a compiler nerd at the moment. I have an inherent trust of things that bootstrap themselves, as if it means they are conceptually more pure. I’m not sure whether that is 100% well founded, but it sounds similar to some of these observations. :)
- ReactiveJelly 6y ago
  I think self-hosting is just a little over-rated for languages. It's good that Rust and C++ are self-hosting, you'd expect those to be languages you can write a compiler in. But Lua and JavaScript satisfy their own niche just fine without having popular runtimes written in themselves.
  - TheBrokenRail 6y ago
    There are a few JS interpreters written in JS, don't know about Lua.
  - mattgreenrocks 6y ago
    Most languages don't aspire to be so conceptually-complete that they insist on being bootstrapped. Which is fine, I make my living with them. Those that do, however, are immensely beautiful and there is more to be learned from them.

qudat 6y ago

For my FE projects I employ a module based code structure. If you import a module, you get the whole thing. This lends itself to many positives but one negative is it makes it easy to run into circular dependencies. I wrote an article discussing my architecture and how I solve circular dependencies in js. https://erock.io/scaling-js-codebase-multiple-platforms/ https://erock.io/scaling-js-codebase-multiple-platforms/ In the article I argue that circular dependencies are a good thing because they uncover poor code organization.

kstenerud 6y ago

This is one of the things that frustrates me about go. They started with this very good advice and then took it one step stupider: Disallowing circular imports. Why is this bad? It makes it impossible in many situations to locate your public API at the top level. Let's say you have a Widget interface and APIs to do things with those Widgets. Eventually your library gets complex enough that you want to separate functionality into subdirs. Now you have a problem: You can't access the definition for Widget from the subdir because importing the top level would create a circular import! The only way to get around this problem is to have no code at the top level, and put your public API in a subdir. Just be sure to do this when first starting your library or you'll have to break things.

caylus 6y ago
You can deal with that issue by defining things in a submodule, then importing and re-exporting them in the top-level (e.g. `type Foo = subdir.Foo`). That even lets you move things into the submodule without breaking callers. Other submodules can then import from the submodule rather than the top-level.
xiphias2 6y ago
This is how libraries are exported inside Google (use /public subdir for the public interface), and I guess with Go this got into the language. But I think Go made much worse things than this :)

codazoda 6y ago

I've never tried F# so I'm not sure I'm exactly "on base" here, but I actually think this way. It's frustrating to me when dependencies happen automatically or when they can be used before they are declared. It helps me understand what's included if I can see a nice list of all the dependencies. It helps me narrow down where the problem is if I only have to address dependencies I know have already loaded. I learned to program in the 80's however, and it probably is a bit "old school".

lazulicurio 6y ago

In a related vein, is there any sort of theoretical transform that can be used to convert cyclic dependencies into a tree? Similar to how lambda lifting eliminates free variables. (Other than the obvious one of treating the entire cycle as one node)

KingOfCoders 6y ago

This was one of the reasons I used lots of Interfaces back in the day with Java.

username90 6y ago
That doesn't remove circular dependencies though, it just hides them.

layer8 6y ago

The generic way to remove a cyclic dependency is by Dependency Inversion (not to be confused with Dependency Injection), so that a mutual dependency A <–> B is transformed into the noncircular set of dependencies { A –> BIntf, BImpl –> BIntf, BImpl –> A }. That is, at least one node in the dependency cycle is split into interface and implementation, breaking the cycle. Compilers for languages like C# and Java can deal with (seemingly) circular dependencies within a set of classes to compile, because when A uses B they only have to consider the interface (type signature) of B, not its implementation. (Cyclic dependencies between modules are still a problem, in particular for build systems.) I'm not really familiar with F# (so someone please correct me if necessary), but in languages that use type interference to determine function signatures, one consequence is that the interface (type signature) of the function then depends on its implementation, so you can't as easily invert the dependency as when you have explicitly declared type signatures.

dfgdghdf 6y ago
F# could have out of order definitions, but the designers chose not to because it lengthens compile times considerably.

danielovichdk 6y ago

Funny to see those layered architectures/designs. Tightly coupled dependencies are bad. Cyclic or not. And if you do mange to to a cyclic dependency you are not thinking about your design property. Imo

edflsafoiewq 6y ago

The simplest case where I'd want a circular dependencies is I have a module that defines some data types and functions on those types mod widget struct Widget fn show(Widget) { ... } fn join(Widget) { ... } fn calc_box(Widget) { ... } and one function is getting very long and complicated so I want to spin it out into its own module mod widget mod calc_box import calc_box from widget import Widget struct Widget fn calc_box(Widget) { ... } fn show(Widget) { ... } fn join(Widget) { ... } The reason the article gives that this is "evil" is that there is no hierarchy between the modules; the cycle is really just one big supermodule. That's true... but that was basically the point. Where is the "evil" here?

vasergen 6y ago
In that case you can separate ’struct Widget’ into another file. This way there will be no circular dependency
- edflsafoiewq 6y ago
  I know how to break the cycle. What I'm asking is why should I break the cycle?
  - vasergen 6y ago
    It depends on situation. As an example, it could be difficult to write tests when you have circular dependency. As well depends on the language there could be strange ’side effects’ which would be difficult to debug.

cratermoon 6y ago

The mention of Lakos' book "Large-Scale C++ Software Design" reminds me of the epiphany I had when I read it. You could almost boil the entire book (and it's not a small one) down to "eliminate circular dependencies". That's trite, but Lakos walks through all the problems that large C++ projects had and lays out how all of them boil down to the dependency problem. Particularly interesting to me, at the time, was his analysis of how compile times got exponentially longer as interdependencies grew, to the point where even a small change required recompiling the entire code base. The section in Lakos on how to identify and remove circular dependencies was worth the price of the book.

pabs3 6y ago

Debian has been doing some work on this: https://wiki.debian.org/DebianBootstrap https://wiki.debian.org/DebianBootstrap Also the Guix and Bootstrappable Builds folks are working on this too, at a different layer: https://bootstrappable.org/ https://bootstrappable.org/ https://bootstrapping.miraheze.org/wiki/ https://bootstrapping.miraheze.org/wiki/