3 ms·

Does this measure make sense for pure functional languages? Can it be defined for terms in the lambda calculus or in combinatory logic?

by tromp 3y ago

marcosdumay 3y ago
You still have a number of atoms, composed and selected, in a way that is completely similar. But you'll discover that almost every program in a functional language has an enormous complexity when measured that way. So, it does pretty much make as much sense as on the imperative case, and also it's completely useless (instead of only partially useless, I guess).
Verdex 3y ago
Probably not. Although, you can immediately follow that up with asking whether this makes any sense in any programming language. From the wikipedia link: https://en.wikipedia.org/wiki/Cyclomatic_complexity#Correlation_to_number_of_defects https://en.wikipedia.org/wiki/Cyclomatic_complexity#Correlat... Correlation between CC and defects isn't always present and in fact lines of code might be a better metric. I assert that there is no current objective metric where you can plug in source code and get out some sort of comprehensibility value. Lines of code is the best we have at the moment. And it goes without saying (but I'm going to say it anyway) that lines of code isn't a great metric to be stuck with. Right now the only thing we have are best practices (ie some other people were "successful" in some other context and they happened to be doing this) and code smells (right, the code makes my tummy feel bad, you can just feel the objectivity pouring out). [It's been pointed out to me in the past that Weyuker's 9 Properties can be used to determine comprehensibility, but when you look at the papers published about it they're all really underwhelming. Basically, people have built a machine that when given source code dumps out a number that correlates to Weyuker, but then nobody takes the next step to see if that number actually correlates to anything that anyone cares about. People are trying things though. For example, there's this: https://www.sonarsource.com/resources/cognitive-complexity/ https://www.sonarsource.com/resources/cognitive-complexity/ I'm not particularly convinced by it, but it does a better job than Weyuker, iirc.]
- CharlieDigital 3y ago
  > I assert that there is no current objective metric where you can plug in source code and get out some sort of comprehensibility value. Ratio of ternary operators more than 1 level deep to total LoC. You know you're in for some pain when you randomly open a file and the ternary expressions go 6 levels deep.
  - Verdex 3y ago
    > Ratio of ternary operators more than 1 level deep to total LoC. Sure. I should have said, "no current general objective metric". For example, if we detect any symbols longer than 6 billion characters, then we know the code is likely to be hard to grok. Or if the only character used in symbols is the underscore. And maybe the path forward for determining objectively comprehensible code is to collect every pathological case and then good code is code without the bad stuff. But I personally hope for a general solution that we can setup which will emergently determine that too many nested ternary operators is bad from first principles. I'm more than ready to be disappointed when this turns out not to be possible, but everyone is allowed a dream.
  - bluGill 3y ago
    Sure, but the vast majority of programmers don't do that type of thing. Often in cases like the above I'm not sure if the metric is correct - or is it just that you are not used to reading that style. For years I worked at places that banned the ternary expression and so I didn't use them and it was a lot of work to remember what was going on the rare times I saw them. Then I got a job on the team that did use them all the time (but never more than 1 level deep) and I soon learned to read them and now I use them often where they make sense.
zackmorris 3y ago
That's what I was wondering as a woefully uninformed armchair warrior burnout. The main (only?) difference between functional and imperative programming is mutability. The ideal FP representation is a spreadsheet with no infinitely cyclical references to cells like A1->B1->C1->A1, and the ideal IP representation is a Turing tape reading/writing/moving with no registers. I'm probably wrong about both of these, but that's how I think of them. So most IP languages like JavaScript eventually reach a state complexity limit where humans can no longer analyze them. It's like trying to remember more than 7 digits in a phone number while someone is yelling more phone numbers at you. Whereas FP languages work more like piping STDIN/STDOUT/STDERR streams between executables running in isolated processes, and have no scalability limit. We just don't have the hardware to properly run them, because we went the SIMD/GPU route instead of CPU clusters. Note that most of the FP lingo like currying, closures, lazy evaluation, etc are clever and have their applications, but distract from the core essence separating it from IP. People a little older than me did a lot of work in the 1990s to move away from mutable state (assembly, C++) and transition to pure functional synchronous blocking deterministic idempotent logic (Lisp, Prolog, VHDL/Verilog, HTTP, etc). Unfortunately corporations unwound most of that progress by reintroducing every anti-pattern in a million-monkeys typing proprietary race for profit. Async/nonblocking code is borrowed from monads and is a workaround for single-threaded code lacking proper scatter-gather arrays and higher order functions that can fork/join other threads. The only language I know that gets this stuff mostly right is ClojureScript, which attempts to use pure FP by avoiding monads and executing logic as a one-shot process with new input/output passed while suspended waiting for events, similarly to how PHP works. It also has a software transactional memory that works like Redux for storing state, which is also related to copy-on-write arrays in PHP before version 5 introduced pass-by-reference classes and permanently derailed what made it compelling. Haskell and other FP languages mostly miss the point due to their over-reliance on monads and syntactic sugar, which costs them purity and makes them little better than IP languages for use-cases in real life. And of course since ClojureScript is Lisp-based, its parenthesis syntax makes it difficult to read, putting it into the category of write-only languages like Perl, which all but guarantees that it will never reach mainstream adoption. I'm mostly skeptical of Rust for these reasons. Because a properly structured program doesn't have much/any mutable state, which negates most of the need for the borrow checker. I have a few dozen criteria that I use to judge what a "good" language would look like, and there simply isn't one yet. I would dearly love to write one, but it would take me perhaps 2-5 years, so with just nights and weekends and a few weeks of vacation per year if I'm lucky, that will never happen. The main challenge I face in my daily work is overcoming this condemnation of being forced to work with mediocre tools for the reminder of my life. And I see the 100x overhead cost of poor tooling reflected in the $200/hr wages of programmers whose productivity has fallen so low that a social network is considered a big lift. Whereas if we look at the logic involved, a teenager could write one in a couple of weeks with something like HyperCard/FileMaker/Access. I'm reminded of the Kirk-Picard conversation that goes "I take it the odds are against us and the situation is grim?" because I've mostly witnessed regression instead of progress the last 25 years. But revolutions happen when things are at their worst, so that keeps me going and inspired. TL;DR: mutability matters more than cyclomatic complexity.
James_K 3y ago
The issue you face here is one of program inputs. Any time you are passing functions as values, you can't guarantee how exactly the body of a function will execute. In a simple example: (lambda (a) (a (lambda () (b)) (lambda () (c))) You can't tell how the calls to b and c will be executed without also knowing something about the value of a. The function a could be a branching construct, or it could just evaluate it's inputs directly. You could assume the worst case and assign a high complexity to this code, but all lambda calculus terms are delayed in this way, so every function call would be assigned the worst case complexity for control flow. More generally, imagine an interpreter that accepts a string as input and that string contains a program. You can make the program contained in the string as complex as you like without affecting the complexity of the interpreter, and effectively cheat the metric.

Does this measure make sense for pure functional languages? Can it be defined for terms in the lambda calculus or in combinatory logic?

by tromp 3y ago

Does this measure make sense for pure functional languages? Can it be defined for terms in the lambda calculus or in combinatory logic?

marcosdumay 3y ago

You still have a number of atoms, composed and selected, in a way that is completely similar. But you'll discover that almost every program in a functional language has an enormous complexity when measured that way. So, it does pretty much make as much sense as on the imperative case, and also it's completely useless (instead of only partially useless, I guess).

Verdex 3y ago

Probably not. Although, you can immediately follow that up with asking whether this makes any sense in any programming language. From the wikipedia link: https://en.wikipedia.org/wiki/Cyclomatic_complexity#Correlation_to_number_of_defects https://en.wikipedia.org/wiki/Cyclomatic_complexity#Correlat... Correlation between CC and defects isn't always present and in fact lines of code might be a better metric. I assert that there is no current objective metric where you can plug in source code and get out some sort of comprehensibility value. Lines of code is the best we have at the moment. And it goes without saying (but I'm going to say it anyway) that lines of code isn't a great metric to be stuck with. Right now the only thing we have are best practices (ie some other people were "successful" in some other context and they happened to be doing this) and code smells (right, the code makes my tummy feel bad, you can just feel the objectivity pouring out). [It's been pointed out to me in the past that Weyuker's 9 Properties can be used to determine comprehensibility, but when you look at the papers published about it they're all really underwhelming. Basically, people have built a machine that when given source code dumps out a number that correlates to Weyuker, but then nobody takes the next step to see if that number actually correlates to anything that anyone cares about. People are trying things though. For example, there's this: https://www.sonarsource.com/resources/cognitive-complexity/ https://www.sonarsource.com/resources/cognitive-complexity/ I'm not particularly convinced by it, but it does a better job than Weyuker, iirc.]

CharlieDigital 3y ago
> I assert that there is no current objective metric where you can plug in source code and get out some sort of comprehensibility value. Ratio of ternary operators more than 1 level deep to total LoC. You know you're in for some pain when you randomly open a file and the ternary expressions go 6 levels deep.
- Verdex 3y ago
  > Ratio of ternary operators more than 1 level deep to total LoC. Sure. I should have said, "no current general objective metric". For example, if we detect any symbols longer than 6 billion characters, then we know the code is likely to be hard to grok. Or if the only character used in symbols is the underscore. And maybe the path forward for determining objectively comprehensible code is to collect every pathological case and then good code is code without the bad stuff. But I personally hope for a general solution that we can setup which will emergently determine that too many nested ternary operators is bad from first principles. I'm more than ready to be disappointed when this turns out not to be possible, but everyone is allowed a dream.
- bluGill 3y ago
  Sure, but the vast majority of programmers don't do that type of thing. Often in cases like the above I'm not sure if the metric is correct - or is it just that you are not used to reading that style. For years I worked at places that banned the ternary expression and so I didn't use them and it was a lot of work to remember what was going on the rare times I saw them. Then I got a job on the team that did use them all the time (but never more than 1 level deep) and I soon learned to read them and now I use them often where they make sense.

zackmorris 3y ago

That's what I was wondering as a woefully uninformed armchair warrior burnout. The main (only?) difference between functional and imperative programming is mutability. The ideal FP representation is a spreadsheet with no infinitely cyclical references to cells like A1->B1->C1->A1, and the ideal IP representation is a Turing tape reading/writing/moving with no registers. I'm probably wrong about both of these, but that's how I think of them. So most IP languages like JavaScript eventually reach a state complexity limit where humans can no longer analyze them. It's like trying to remember more than 7 digits in a phone number while someone is yelling more phone numbers at you. Whereas FP languages work more like piping STDIN/STDOUT/STDERR streams between executables running in isolated processes, and have no scalability limit. We just don't have the hardware to properly run them, because we went the SIMD/GPU route instead of CPU clusters. Note that most of the FP lingo like currying, closures, lazy evaluation, etc are clever and have their applications, but distract from the core essence separating it from IP. People a little older than me did a lot of work in the 1990s to move away from mutable state (assembly, C++) and transition to pure functional synchronous blocking deterministic idempotent logic (Lisp, Prolog, VHDL/Verilog, HTTP, etc). Unfortunately corporations unwound most of that progress by reintroducing every anti-pattern in a million-monkeys typing proprietary race for profit. Async/nonblocking code is borrowed from monads and is a workaround for single-threaded code lacking proper scatter-gather arrays and higher order functions that can fork/join other threads. The only language I know that gets this stuff mostly right is ClojureScript, which attempts to use pure FP by avoiding monads and executing logic as a one-shot process with new input/output passed while suspended waiting for events, similarly to how PHP works. It also has a software transactional memory that works like Redux for storing state, which is also related to copy-on-write arrays in PHP before version 5 introduced pass-by-reference classes and permanently derailed what made it compelling. Haskell and other FP languages mostly miss the point due to their over-reliance on monads and syntactic sugar, which costs them purity and makes them little better than IP languages for use-cases in real life. And of course since ClojureScript is Lisp-based, its parenthesis syntax makes it difficult to read, putting it into the category of write-only languages like Perl, which all but guarantees that it will never reach mainstream adoption. I'm mostly skeptical of Rust for these reasons. Because a properly structured program doesn't have much/any mutable state, which negates most of the need for the borrow checker. I have a few dozen criteria that I use to judge what a "good" language would look like, and there simply isn't one yet. I would dearly love to write one, but it would take me perhaps 2-5 years, so with just nights and weekends and a few weeks of vacation per year if I'm lucky, that will never happen. The main challenge I face in my daily work is overcoming this condemnation of being forced to work with mediocre tools for the reminder of my life. And I see the 100x overhead cost of poor tooling reflected in the $200/hr wages of programmers whose productivity has fallen so low that a social network is considered a big lift. Whereas if we look at the logic involved, a teenager could write one in a couple of weeks with something like HyperCard/FileMaker/Access. I'm reminded of the Kirk-Picard conversation that goes "I take it the odds are against us and the situation is grim?" because I've mostly witnessed regression instead of progress the last 25 years. But revolutions happen when things are at their worst, so that keeps me going and inspired. TL;DR: mutability matters more than cyclomatic complexity.

James_K 3y ago

The issue you face here is one of program inputs. Any time you are passing functions as values, you can't guarantee how exactly the body of a function will execute. In a simple example: (lambda (a) (a (lambda () (b)) (lambda () (c))) You can't tell how the calls to b and c will be executed without also knowing something about the value of a. The function a could be a branching construct, or it could just evaluate it's inputs directly. You could assume the worst case and assign a high complexity to this code, but all lambda calculus terms are delayed in this way, so every function call would be assigned the worst case complexity for control flow. More generally, imagine an interpreter that accepts a string as input and that string contains a program. You can make the program contained in the string as complex as you like without affecting the complexity of the interpreter, and effectively cheat the metric.