[HN Gopher] Mindset shifts for functional programming (with Cloj...
___________________________________________________________________
Mindset shifts for functional programming (with Clojure)
Author : janetacarr
Score : 143 points
Date : 2023-04-04 14:11 UTC (1 days ago)
(HTM) web link (blog.janetacarr.com)
(TXT) w3m dump (blog.janetacarr.com)
| koito17 wrote:
| As a Clojure programmer, I find it a bit unfortunate that most of
| this post, like many other posts demonstrating Clojure, tend to
| paint a rosey picture and never mention the realities one has to
| reconcile in a Clojure codebase.
|
| For instance, one of the sections in this blog post is titled
| "Functions over Objects" but any Clojure programmer with
| experience will agree that most code ends up becoming some sort
| of map munging. Rather than "functions over objects" you really
| have "map-munging and function instrumentation in dev over
| banging on concrete instances of classes".
|
| There is also this statement
|
| > functional programming languages often facilitate iteration
| through recursion
|
| then the author proceeds to mention loop/recur, which is nice,
| but it is dishonest at best and lying at worst to imply
| loop/recur is the most natural or common way we iterate over a
| structure. Off the top of my head, I always see idioms like `(for
| [[k v] some-map] (do things with k v))`. It would also be nice to
| demonstrate how faux-recursive looks like with loop/recur rather
| than stating Clojure's lack of TCO and not elaborating further on
| how the idiomatic version of `recursive-map` would look like.
|
| Next,
|
| > by (nearly) eliminating side-effects, functional programming
| (nearly) elminates this whole class of bugs.
|
| That may be the intent of purely functional code in general, but
| in Clojure one regularly interoperates with the host, to take
| advantage of their rich ecosystem. Many of the libraries one will
| interop with will involve some imperative or stateful things! So
| I think it'd be better if the author had mentioned the idea of
| "functional core, imperative shell." That is a pattern most
| Clojurists would agree with, and it is what people really do in a
| code base, or at least attempt to design.
|
| Lastly, while Clojure allows one very naturally to mock up a
| finite state machine with a single map and writing a few
| functions to describe transitions given the current state of the
| machine, I want to emphasize that not much Clojure codebases I've
| seen ever used FSMs explicitly :-)
|
| Overall, the article is okay, but my brain registers it as
| another "Clojure portrayed with rose-tinted glasses and contrived
| examples" article. Not that this is bad. It's just not the kind
| of sales pitch I'd want to show to non-Clojure programmers,
| because they will likely want to ask questions about
| maintainability, testing, instrumentation, etc. And it _is_
| possible to show Clojure being nice for each of these things. At
| a previous job I got to see ClojureScript code dating back to
| 2014, untouched, and surviving 8 years worth of language _and_
| library updates.
| sharas- wrote:
| The advantage of clojure is in data centricity. It is not about
| shifting mind to recursion from looping. Clojure has a 'for'
| which is it's list comprehension loop. The actual fun of clojure:
| https://bitslap.it/blog/posts/fun-of-clojure.html
| janetacarr wrote:
| Clojure data type's are fantastic, but the main thesis of my
| post isn't what's required for FP in Clojure, rather, what's
| required to become comfortable with pure functional programming
| concepts which is why I reference Haskell a lot in the post.
| The examples just happen to be in Clojure.
|
| Sorry for the confusion.
| sharas- wrote:
| I get it. But my point is that clojure is not snobbish about
| pure functional programming. It's angle is data centricity.
| Very different to haskell in that respect and type centricity
| of it.
| janetacarr wrote:
| I agree with you, but I also never said it's snobbish about
| pure functional programming. The way I see it, pure
| functional programming, like anything, is just a tool in
| the belt to help think about solutions in a different
| manner.
| margorczynski wrote:
| I think the main thing is not really FP vs whatever else but the
| most fundamental thing is declarative vs imperative. That is
| probably the biggest jump in mindset when coming from e.g. C or
| C++ to something like Haskell - that instead of telling the
| computer/compiler what to do, you describe what you want.
| crop_rotation wrote:
| You are still telling the computer what to do, describing what
| you want is more like prolog. The main difference between
| Haskell and C in a case like this would be the level at which
| you tell it what to do.
| margorczynski wrote:
| That's a truism that when extend equates Firefox or Excel
| with programming with C because at the end of the day you
| tell the computer what to do via some interface (text
| programming language or graphical with much more abstraction
| layers).
| janetacarr wrote:
| I think this would be correct for declarative programming
| languages, but I don't agree that Haskell is a declarative
| programming language. Haskell is pure functional programming in
| my mind. A declarative programming language might be something
| more akin to DML SQL for a RDBMS, or HCL for Terraform (pre-
| looping, v0.X).
| margorczynski wrote:
| Pure FP languages are declarative just with additional
| restrictions like referential transparity, no explicit
| handling of state and immutability of the underlying state.
| For these restrictions to be effectively held it requires for
| it to be declarative.
| janetacarr wrote:
| Oh I see what you mean. I had to look into this a bit.
| Sorry for the confusion!
| tourgen wrote:
| [dead]
| twic wrote:
| I am not a Clojure programmer, and am pretty skeptical of LISPs
| and FP more generally, but i have to say that transducers are
| pretty great. The descriptions of them, and the way the interface
| is expressed, are a bit off-putting, but once you grok them
| they're actually simple and useful.
|
| They occupy the same space as Java's streams, but manage to do
| the same stuff with a smaller, more generic, more extensible
| interface, that can do more stuff (eg intermediate stages get
| told when input is finished). I'm jealous.
|
| EDIT: IIUC, in Java terms, Clojure's "reducing functions" are
| like Collector, and a transducer is a function which takes a
| Collector and returns another one. There is then a little bit of
| top-level sugar so you can give a sequence of transducers,
| terminating in a concrete reducing function, and get back a
| reducing function which itself feeds things through the chain of
| reducing functions built by the transducers. You could probably
| replicate this in Java, but it might be too clunky even for Java
| programmers.
| janetacarr wrote:
| Transducers are great!
|
| They were an small obsession of mine last week as I wrote an
| accompanying blog post to demystify them.
| twic wrote:
| Aha, this one i suppose (your blog does not have a browseable
| index, although it does have search):
| https://blog.janetacarr.com/clojure-transducers-your-
| composa...
|
| Personally, i would say that a blog post which starts "We can
| think of a transducer as a context-independent transformation
| composed of, say, many reducers" and then starts adding
| parentheses is not really demystifying. But perhaps i am not
| the target audience.
| janetacarr wrote:
| Oh yeah. If you didn't know what a reducer was, the article
| might be a bit confusing, eh?
| twic wrote:
| I couldn't stop myself having another go at transducers in
| Java, this time sticking more closely to using collectors:
|
| https://gist.github.com/tomwhoiscontrary/1d4799fb85b4890a96e...
| Liberonostrud wrote:
| [dead]
| roenxi wrote:
| > Recursion over Looping
|
| Part of what makes Clojure a great programming language is that
| you don't have to believe this if you don't want to. Nobody has
| yet convinced me that recursion has any sustained advantage over
| looping.
|
| Using a loop is generally bad practice if a more specialised
| operation is available (don't loop if something is a simple map
| or reduce for example). But if the situation justifies a
| recursion then it usually justifies a loop unless the recursion
| is particularly neat. Recursion has the same problem as looping -
| it doesn't tell anyone anything about what the code is really
| doing. If I see map then I have implicit and explicit
| expectations about what is about to happen.
|
| I enjoyed the article though.
| thewarrior wrote:
| Had GPT-4 clarify some of the syntax for me
| https://poe.com/s/uj80au2i4TuNWgUa1pNm
| janetacarr wrote:
| That's pretty cool. Armed with the fundamentals outlined in
| the post, my intent was for the reader to infer how he or she
| can design a system in FP. I'm sorry if it wasn't clear
| enough in the code.
| js8 wrote:
| I mostly agree, and proponents of FP shouldn't stress the
| recursion too much.
|
| When I program in Haskell, I rarely use recursion myself. Most
| loops are just maps and folds. Need to build another structure
| from existing structure? Foldl'. Once I understood that the
| value being folded can be arbitrarily complex, FP became
| simpler (but terser) than iterative programming for me.
| janetacarr wrote:
| Agreed, I rarely reach for recursion myself when developing.
| Most of my transformations are map, filter, and reduce.
| Although from time to time, I will combine them with
| recursion when necessary. I find recurring from a reducing
| function to be great for traversing or searching trees or
| other recursive data structures. Usually these are
| accompanied by a ton of comments for the next developer. :)
| ballenf wrote:
| I don't think of map operations as loops. Instead as parallel
| operations on elements of a list works as a better mental
| model for me.
|
| When learning them coming from an imperative background, it's
| inevitable to start with that idea, but somehow feels like a
| limiting model.
| tmtvl wrote:
| I used Scheme for a while so I like using recursion when loops
| get a bit hairy, but Guy Steele's talk on Parallel Programming*
| made me aware of the limitations of that way of working. Now
| that I've switched to Common Lisp I try to think about the
| algebraic properties of my functions so I can apply them using
| lparallel's preduce.
|
| * https://www.infoq.com/presentations/Thinking-Parallel-
| Progra...
| PartiallyTyped wrote:
| Maybe it's my background but recursion feels more natural,
| either you are at the base, or at a point with N-1 items below.
| This gives you two different invariants that you can use to
| simplify the code.
|
| Small example, though not exactly comparable to looping.
|
| I needed to create a human readable qualified path appended by
| a hash (to avoid conflicts). This qualified path was needed
| ahead of the construction of an object, and the logical name
| must have been used in both the hash and qualified path as it
| was global (Yes, it was an S3 bucket).
|
| I wrote a function uniqueQualifiedName:
| Construct x Optional(logicalId) x Properties -> string.
|
| The recursive step is at the top, where the logicalId is
| transformed to a construct in the scope of the first argument,
| and the function is called again with NewConstruct x Nothing x
| Properties. This could easily be adjusted to work with a list
| of logicalIds instead.
|
| The invariant in the recursive step is that once the call
| returns, the construct at the end of the chain will be exactly
| the construct I inserted, and I can pop it safely, and the
| scope object will be none the wiser.
|
| The invariant in the base is simply that I don't need to worry
| about logicalId being anything.
|
| You can see then how easy it is to adapt this to work with a
| list, whereas with a loop you'd have to write it from zero, and
| then roll back. Too messy imho.
| roenxi wrote:
| I don't understand your problem or your solution, but that
| seems like a lot of things going on to construct a string.
|
| But it sounds like you could just bash the logicalIds
| together and append the hash of the bash of the mash. Might
| not need loops or recursion.
| PartiallyTyped wrote:
| To just bash them together I'd have to either use the
| private api which is not a good thing. Alternatively I can
| push a list of items N steps to each object and have each
| one of them both adding and removing the logical names.
| Herval_freire wrote:
| >Nobody has yet convinced me that recursion has any sustained
| advantage over looping.
|
| Recursion gives you a stack by default. You don't have to
| explicitly think about the stack. In looping the stack must be
| explicit.
|
| Recursion and looping are the same thing. Recursion can be
| mechanically translated to a for loop and a stack, the concepts
| are isomorphic.
| KRAKRISMOTT wrote:
| On paper perhaps, but I have yet to see a compiler that can
| take any _arbitrary_ recursive subroutine and automatically
| optimize it into a Tail Call Optimized (that is, transform
| the recursive parts into goto /jumps similar to a loop)
| version. Non optimized recursion is not hard to understand,
| the problem is any performant recursive code needs to be
| manually rewritten as tail recursive which adds a lot of
| complexity. Built a better compiler and maybe more people
| would be willing to embrace functional programming.
| illiarian wrote:
| Unless I'm mistaken, Erlang's compiler rewrites all
| recursion that explicitly returns a function call into
| tail-call, and eliminates all the stack in between
| timmg wrote:
| > all recursion that explicitly returns a function call
|
| Yeah, but that's not " _all_ recursion ".
| chriswarbo wrote:
| > On paper perhaps, but I have yet to see a compiler that
| can take any arbitrary recursive subroutine and
| automatically optimize it into a Tail Call Optimized (that
| is, transform the recursive parts into goto/jumps similar
| to a loop) version.
|
| General recursion can be modelled coinductively via the
| "Delay" or "Partial" type, e.g.
| https://arxiv.org/abs/cs/0505037
|
| Type-inference can figure out when recursive calls need to
| be wrapped in `Later`. We can then compile into a single
| `while` loop to unwrap the layers.
| Herval_freire wrote:
| It doesn't make any sense to convert any arbitrary
| recursion into tail called optimized.
|
| If the recursion can be tail called optimized then yes the
| loop is the optimized performant implementation.
|
| But if the recursion fundamentally utilizes the call stack
| then the reverse is actually true. The recursion is now the
| performant implementation of a for loop. So a loop
| conversion optimization actually doesn't make sense here.
| That's partly why a compiler won't optimize this.
|
| Why? Because in recursion you utilize the call stack, in
| the for loop you're going to create a heap allocated stack
| and allocate on it repeatedly. Allocation slows down the
| iterations.
|
| The only advantage of the for loop in this case is that
| there won't be stack overflow, but overall the recursive
| version will actually be faster.
| [deleted]
| zelphirkalt wrote:
| > The only advantage of the for loop in this case is that
| there won't be stack overflow, but overall the recursive
| version will actually be faster.
|
| In languages, which have realized the value of recursion,
| a stack overflow does not happen. For example:
| https://docs.racket-
| lang.org/guide/Lists__Iteration__and_Rec...
| mike_hock wrote:
| Works for O(log n) stack depth. In general, recursion is
| not viable.
| zelphirkalt wrote:
| This is quite false. Languages like Scheme (dialects), ML
| variants, Erlang and Haskell all make use of recursion in
| general and they produce very viable results.
| sokoloff wrote:
| > If the recursion can be tail called optimized then yes
| the loop is the optimized performant implementation.
|
| Is it? My mental model of tail-call optimization is that
| it's just a replacement of the stack variable values in
| place and a jump to the function entry point (which seems
| like the same amount of work as updating local variables
| in a loop and jumping to the head of the loop).
| austin-cheney wrote:
| Looping, as in using a loop keyword, is synchronous. Recursion
| is also a loop, but can iterate asynchronously as necessary.
| That is the primary advantage.
| codr7 wrote:
| Recursion vs iteration reminds me of ordered sets vs hash
| tables.
|
| Maybe partly because ordered sets are often implemented as
| trees, which are definitely easier to traverse recursively.
|
| I find recursion nicer to work with mentally; continuous rather
| than discrete, with less edge cases to consider.
| janetacarr wrote:
| Totally! Clojure is kind of great for this, the loop form in
| Clojure is really recursion as `loop` just provides a point(fn)
| for `recur` to return as well as a let binding. You could also
| just call `recur` in any fn. And, it has side-effect forms like
| do, doseq, dotimes, etc.
|
| I'm glad you enjoyed the read though :)
| dangwhy wrote:
| > Nobody has yet convinced me that recursion has any sustained
| advantage over looping.
|
| most sql systems support recursive queries. I believe recursive
| code can be analyzed by the system and executed in a the most
| efficient manner.
|
| Loops have sideffects closely linking them to actual execution,
| which makes them blackboxes to the system.
| twic wrote:
| If you're talking about recursive common table expressions,
| those are called recursive, but are really iterative. The
| PostgreSQL documentation describes the iterative evaluation:
|
| https://www.postgresql.org/docs/current/queries-
| with.html#id...
|
| Note how there is no way to remove a row from the result set
| once it has been added. That would not be the case with a
| truly recursive query, because you would be constructing a
| new result set at every step. As a concrete example, try to
| write a graph query which finds all nodes exactly three edges
| from some starting node. That would be trivial with true
| recursion, but is impossible with a recursive CTE alone.
| nerdponx wrote:
| I think the difference between recursion and looping is that
| the former requires you to be very explicit about the state you
| intend to modify and persist between iterations, while it's
| generally somewhat of a free-for-all in imperative loops.
| slifin wrote:
| The most common looping construct I see in clojure is the for
| statement
|
| Which isn't quite the free for all it is in traditional
| languages
|
| You have to be very conscious and coding against the grain to
| use it to bang on values in place
| nerdponx wrote:
| This is a general design principle that I appreciate about
| the Lisp family of languages in general. You _can_ write
| highly imperative code that mutates things in-place, but it
| 's a little harder to do and it's something you do only
| when you really need to do it. Whereas the _default_ idioms
| are functional, and functional design is the path of least
| resistance. Perl is morally the opposite of functional
| programming in many ways, but I actually think this design
| is a great embodiment of the "make easy things easy, make
| hard things possible" ethos of Larry Wall.
| librexpr wrote:
| I mostly agree, but one really nice use case for recursion is
| when dealing with trees. For example, writing a function
| parse_object() that recursively calls itself to parse child
| objects is way more pleasant than manually managing your own
| stack, especially if the tree has many kinds of objects and
| many branches.
|
| Unfortunately in most languages this pattern will lead to stack
| overflow on medium-sized inputs, so you can't often use it
| unless you're using a language like Racket or Erlang which
| can't really stack overflow.
| chriswarbo wrote:
| > Nobody has yet convinced me that recursion has any sustained
| advantage over looping.
|
| Looping may require trampolining or defunctionalisation, whilst
| recursion can be written much more directly and simply. As a
| very simple example (in pseudocode): even(n:
| uint): boolean = n match { case 0: true case n:
| odd(n-1) } odd(n: uint): boolean = n match {
| case 0: false case n: even(n-1) }
|
| Whilst these are pretty silly implementations of odd & even, I
| don't know of a direct analogue using loops. For more realistic
| examples, just look at any "main loop"; AKA "trampoline
| boilerplate to work-around our language's lack of tail-call
| elimination" ;)
| actionfromafar wrote:
| It's heretic and beside the point, but:
| bool odd(uint n){return n&1;} bool even(uint n){ return
| !odd(n);}
|
| I can't help but think in terms of classic CPU.
| Joker_vD wrote:
| fun odd (n: Uint32) -> Bool = let Uint32(n0, _,
| _, _) = n in let Byte(b0, _, _, _, _, _, _, _)
| = n0 in b0
|
| Who needs hardware support for integers anyway? If you want
| a two-complement arithmetic, you can build it yourself
| (although presumably it'll be in the standard library).
| twic wrote:
| I'm not going to argue this is good, but it's fairly
| analogous: boolean isEven(int n) {
| boolean even = true; for (; n > 0; --n) even =
| !even; return even; }
| chriswarbo wrote:
| Your implementation has lost the encapsulation of mine, and
| broken the call-graph relationships. For example:
|
| - Updates and bug-fixes to the `isOdd` function will not be
| inherited by your `isEven` function.
|
| - If I set a breakpoint in this function, it won't get
| triggered when I call `isOdd`.
|
| - Your `isEven` function requires an implementation of `!`
|
| - etc.
| twic wrote:
| > - Updates and bug-fixes to the `isOdd` function will
| not be inherited by your `isEven` function.
|
| > - If I set a breakpoint in this function, it won't get
| triggered when I call `isOdd`. boolean
| isOdd(int n) { return !isEven(n); }
|
| > - Your `isEven` function requires an implementation of
| `!`
|
| Yes, but this language has one, so that's fine.
| chriswarbo wrote:
| Many of the replies to this comment seem to have focused on
| the problem domain (numbers and booleans); and missed the
| main feature I was trying to show about recursion, which is a
| collection of functions delegating sub-tasks between
| themselves (rather than e.g. trampolining via a "main loop")
|
| A closer analogy to my code would be something like this: the
| domain logic is still abstracted and encapsulated into
| separate units; the relationships between those units are
| preserved (e.g. if we set a breakpoint in `even_step`, it
| will be triggered by `odd`); etc. However, the loop here is
| literally just a trampoline for thunks, which makes it highly
| non-idiomatic for imperative/looping style:
| type STEP[T] = either[T, unit => STEP[T]]
| stepper[T](current: STEP[T]): T = { for (result =
| current; result.isRight(); result = result.value(unit))
| return result } even(n: uint): boolean =
| stepper(n match { case 0: left(true) case n:
| right(() => odd(n-1)) }) odd(n: uint):
| boolean = stepper(n match { case 0: left(false)
| case n: right(() => even(n-1)) })
|
| Instead, we could defunctionalise; but that requires some
| separate data structure and "interpreter":
| type STEP = ODD(n: uint) | EVEN(n: uint) | RETURN(x: boolean)
| even_impl(n: uint): STEP = n match { case 0:
| RETURN(true) case n: ODD(n-1) }
| odd_impl(n: uint): STEP = n match { case 0:
| RETURN(false) case n: EVEN(n-1) }
| interpret(current: STEP): boolean = { while
| (!current.isReturn) { current = current match {
| case ODD(n): odd_impl(n) case EVEN(n):
| even_impl(n) } } return current.x
| } odd(n: uint): boolean = interpret(ODD(n))
| even(n: uint): boolean = interpret(EVEN(n))
| LegionMammal978 wrote:
| I think the underlying claim by the OP is that they don't
| really run into situations in practice that need this kind
| of mutual recursion. Certainly, mutual recursion is not at
| all necessary for this boolean example; you argue that the
| obvious imperative form is not a direct analogue, but it's
| not really clear in what situation a direct analogue is
| desirable in the first place.
| willdearden wrote:
| FWIW for my comment I essentially used your code and
| cleaned up compiler-generated imperative code.
|
| So yes it used the fact that it only recursed to n-1 but
| did not use any optimizations related to booleans. And
| looking at other examples can see general principles. You
| store a data structure for each function which acts as a
| cache. For example, suppose you said even(0) = True,
| even(1) = False, and even(n) = even(n - 2), then one way
| would to unroll it would be to use a size 2 ring buffer as
| a cache.
| willdearden wrote:
| Here's how I would write the loop version of this. It does
| involve an optimization since we know parity only depends on
| n - 1. #include <algorithm>
| template <typename T> bool even(T n) {
| bool is_even{true}, is_odd{false}; for (; n--;)
| { std::swap(is_even, is_odd); }
| return is_even; }
| roenxi wrote:
| for(range(n)): is_true = !is_true
|
| And adjust for all the off by 1 errors. You're managing the
| same amount of state both ways, but with the loop all the
| state mutation lives on one line instead of spread throughout
| a stack.
| chriswarbo wrote:
| That's not a "direct analogue" of my implementation, for
| many reasons; you've changed the semantics and engineering
| tradeoffs so much that we might as well write `n % 2 == 0`.
|
| The biggest problem is that, assuming we copy your snippet
| into a couple of function definitions, we've completely
| lost the encapsulation/separation-of-
| concerns/delegation/etc. provided by my `odd` and `even`
| functions; i.e. all of the "software engineering" stuff
| that makes source code more maintainable than disassembled
| binary.
|
| Your loop is more like the following, which is _not_ what I
| wrote: even(n: uint): boolean = n match {
| case 0: true case n: !even(n-1) }
| odd(n: uint): boolean = n match { case 0: false
| case n: !odd(n-1) }
|
| The major difference is the use of iteration/tail-recursion
| in this implementation:
|
| - This loop collapses all of the abstraction, forcing each
| function to implement the entire solution. In contrast, my
| implementation uses divide-and-conquer: only the zero case
| is handled directly, and the non-zero case is delegated to
| a more suitable handler.
|
| - Wrapping two copies of this loop into `even` and `odd`
| functions will completely lose the relationships inherent
| in my implementation. For example, if we add
| instrumentation, optimisations, logging, etc. to the `even`
| function, that will affect my `odd` function but have no
| effect if we were to write independent loops.
|
| - This looping implementation has extra dependencies,
| specifically on `range` and `!`. The `!` function requires
| knowledge of boolean algebra, the `range` function requires
| knowledge of lists/sequences/iterators, and `range` also
| seems to make more sophisticated use of number theory than
| the `odd`/`even`/`-` required to understand and maintain my
| implementation.
|
| Note that I'm not claiming either of these is
| "better"/"worse" than the other. Simply that your loop _is
| not_ representative of my example; that 's specifically why
| I chose a mutually-recursive example, and not an
| iterative/tail-recursive one!
|
| (Of course, all of these are exaggerations for such a
| simple example; but complex, real-world codebases require
| such engineering practices and tradeoffs to be taken
| seriously for the sake of maintenance)
| vrglvrglvrgl wrote:
| [dead]
| samsquire wrote:
| If your team and you can read it later or when it goes wrong,
| then it's fine.
|
| I don't want to need to think hard about what code does, it
| should be clear. Or jump through 100 files to find a simple
| algorithm that has been divided into 100 pieces.
|
| I think people refactor to their own understanding or mental
| model or refactor-to-understand.
|
| I think there are cases where imperative code is intuitive and
| others where functional code is intuitive.
|
| I've worked on two professional projects in Clojure at a surface
| level but I still find Python easier to read, but that's my
| experience YMMV.
|
| There's a point in my programming projects when my own
| understandability is weakened and I this week I've been trying to
| think of a mindset that simplifies the problem. I am
| experimenting with multithreaded code in Java that implements
| left-right concurrency control. The idea is readers don't block
| writers and writers don't block readers and writers don't block
| writers. Give each thread a shard and rely on commutative
| property of your tree data structure and have a coordinator
| thread handle merging. The benefit: each thread can operate at
| single core speeds without any synchronization for reading OR
| writing. Buffer flipping is handled by the coordinator thread.
|
| Each thread has its own copy of state which is merged by the
| coordinating thread. So it's an eventually consistent system. The
| result: each thread can modify its own copy of the data as much
| as it wants and it can see its own snapshot of global state at
| the last snapshot point. Cross thread writes always happen on the
| inactive buffer.
|
| How do you think about data transformation pipelines? If only
| there was an IDE for kafka or clojure transformation pipelines.
| janetacarr wrote:
| Agreed, cyclomatic complexity is definitely something to be
| aware of when designing functional programming systems.
|
| Although, I disagree about Clojure's readability, but that's
| probably because I've been doing it for so long.
|
| Interesting Java project you've got there. Reminds me of
| Clojure's core.async library and software transaction memory ;)
| (though, I know it's not exactly the same thing).
|
| If I was transforming large streaming input from Kafka or
| Kinesis, I would probably reach for Cortex (a map-reduce style
| lib for Clojure), or I might rig up some strange, stream-to-
| lazy-seq adapter and reach for transducers as they have much
| better performance when dealing with larger input.
| samsquire wrote:
| I am really interested by Software transactional memory and
| enjoyed reading the Joe Duffy's blog posts about Midori and
| adventures with STM.
|
| https://github.com/joeduffy/joeduffy.github.io/blob/master/_.
| ..
|
| I like left-right concurrency control because it sidesteps a
| number of thread safety problems by ensuring that a thread
| can always safely read or write to its own buffer.
| twawaaay wrote:
| > Transformations over Instructions
|
| Hell yeah! The problem with "functional" programming is that a
| lot of people simply don't get you want to push as much of your
| program to be generic tools that transform things (ie FUNCTIONS!)
| When I start on a new problem I typically look at what kind of
| tools (functions) would make the solution concise and readable.
| Then create the tools and then write the solution with the tools.
|
| Unfortunately most developers come with preconceived notions of
| how the program should be laid out and what the development
| process should be. If they come from OOP world, you will see code
| that pretty much looks like objects just without OOP machinery.
| If they come from scripting/procedural then you will see long
| stretches of instructions just split into smaller "functions".
|
| > Recursion over Looping
|
| Recursion is elegant but it is also hard to understand for many
| people. I object putting anything into code when the only purpose
| is making the code look elegant / more advanced at the cost of
| narrowing audience that can effectively work with it.
|
| My goal is to make the code stupid simple. My main challenge is
| preventing my ego from trying to impress the reader.
|
| Frequently recursion is more readable than looping. I don't
| hesitate using recursion in that case. But I make sure that the
| reader should be able to instantly recognise the pattern and the
| pattern is not too complex.
|
| Another thing to push recursion to be more manageable is just
| structuring your code to extract recursion from everything else.
| Make one or two very small functions that are only responsible
| for recursion, extract all other logic into other functions that
| are meaningful on its own (and just happen to be used in
| recursive context).
|
| If the recursion would be too complex, usually iteration is going
| to be easier to represent the solution in manageable chunks
| without requiring the reader to take everything in in one go.
| janetacarr wrote:
| I agree with your sentiment about recursion. It took me a damn
| long time to get used to it. But that's why I call it a mindset
| shift ;). If the codebase was written in Haskell, then there'd
| be no looping. Clojure is a bit odd in this case as it has a
| form called "loop" but it's really just a let binding over a
| fn, providing a point for `recur` to, well, recur to.
| twawaaay wrote:
| Again, the ultimate goal is to make the code readable
| (without sacrificing too much other qualities like
| performance).
|
| When you have a language and context that makes recursion
| easier to understand than loop -- go for recursion.
|
| One other reason to go for loops is to make sure you control
| the stack. With recursion it is not always immediately clear
| that the loop is going to get tail call optimisation. And
| good 9/10ths of developers meet me with a blank stare when I
| mention it. At least with a loop it is clearly visible how
| much space and in what way you are allocating. I had one dev
| who said he likes recursion because he says it is more memory
| efficient. To which I had to point out that each level of
| recursion creates a new stack frame. The guy just wasn't
| aware of it...
| epgui wrote:
| This "recursion is more complicated" idea is a myth.
|
| Yes, a lot of people seem to have trouble with it, but it isn't
| fundamentally more complex or difficult. The hardest thing
| about learning recursion is unlearning the other patterns. It's
| totally a matter of familiarity.
| mrkeen wrote:
| > If the recursion would be too complex, usually iteration is
| going to be easier to represent the solution in manageable
| chunks without requiring the reader to take everything in in
| one go.
|
| Perhaps? But the reason I reach for recursion is so that I
| don't have to first produce the "wrong answer", and then modify
| it until it's the "right answer". The sum of 1..10 is always
| 55. It isn't first 0, then 1, then 3, then 6, etc.
| twawaaay wrote:
| I don't understand where you come from with your argument.
|
| Recursion is also producing results that are "wrong answers"
| although I prefer to call them partial results. Just like a
| loop that is producing partial results as long as it has not
| finished yet.
| mrkeen wrote:
| > Recursion is also producing results that are "wrong
| answers"
|
| Not true. If you share your copy of:
| answer = sum [1..10]
|
| One viewer might see: answer = 3 + sum
| [3..10]
|
| and another viewer might see: answer = 6
| + sum [4..10].
|
| They may be "partial results", but they are correct and
| equal to each other. This is different from one viewer
| seeing 3 and another viewer seeing 6.
|
| "But can't you just hide the partial result until it's
| ready?"
|
| Sure. Get rid of class fields and getters(). I'm happy to.
| Are you?
| Joker_vD wrote:
| Have you heard about the concept of "loop invariant"?
| s = 0 i = 0 // Invariant: before and
| after every iteration, s is equal to sum of [0..i]
| // End condition: i == n while i != n:
| s += i i += 1 // Here, i == n
| and so s is a sum of [0..n] because the invariant still
| holds
|
| That's how loops were supposed to be thought about (and
| written) since the 70ies, and it's more or less
| equivalent to induction which is what you're supposed to
| use when you think about recursive functions.
| mpweiher wrote:
| You tend to not put temporary results of loops in
| instance variables, but in local variables. Which aren't
| visible externally at all.
|
| And yes, if you do have that exceptional case of a
| complex algorithm that needs to store partial results in
| ivars as they are required by different methods and
| inconvenient to pass around individually, those ivars
| tend to not be exposed.
|
| In fact, you'd more likely create a separate context
| object that you pass around, so also not visible
| externally.
| mrkeen wrote:
| > You tend to not put temporary results of loops in
| instance variables, but in local variables. Which aren't
| visible externally at all.
|
| Cool! Then it follows:
|
| If a result is not temporary, then it can be immutable.
| Properly immutable, not just final.
|
| If a result is temporary, then it is not to be visibly
| external at all. Not as a field, and not via any getter.
|
| I could live with that.
| mpweiher wrote:
| That doesn't follow. Objects do (much) more than
| implement algorithms in loops.
|
| In fact, I'd say that if you're doing algorithms as
| objects, you're almost certainly Holding it Wrong(tm).
|
| Algorithms tend to be perfectly fine contained in a
| method of an object.
| wizofaus wrote:
| Out of curiosity is there actually any chipset with the
| algorithmic ability to add more than 2 numbers altogether
| in one operation (without having to store intermediate
| results)?
|
| I'd also think looping is far closer than recursion to how
| we tend to manually calculate things (either entirely in
| our heads or using a pen & paper or even a basic
| calculator).
|
| (Edit: looks like a number of other posters have made the
| same point already, but in dead/downvoted posts, not sure
| why...)
| twawaaay wrote:
| Chips have ability to run vector operations that can add
| a bunch of numbers.
|
| The issue is that recursion in software development is
| relatively rarely about arithmetic operation. For
| example, you might want to traverse a tree of objects
| (like a filesystem folder) to run some operation on them,
| etc.
|
| In this case the intermediate information is pointers to
| where you are currently processing various folders in
| your tree structure, etc. In a loop you would have to
| create a data structure to hold these. In recursive
| function this would typically be spread in multiple
| frames on your stack pointing to objects in your heap.
| wizofaus wrote:
| Vector operations that perform the _same_ fixed addition
| to each element, yes, but that 's not really the same
| thing.
|
| And yes I'm very much in agreement that the real power of
| recursive algorithms is when working with tree-like data
| structures.
| twawaaay wrote:
| Your question was, and I quote:
|
| > is there actually any chipset with the algorithmic
| ability to add more than 2 numbers altogether in one
| operation (without having to store intermediate results)
|
| I was just answering your question. I am not responsible
| for quality of your questions.
|
| What you do is you posted a question but had something
| else in mind. You got an answer but that answer does not
| match the question you had in your mind so now you think
| it is ok to berate somebody for not being able to read
| your mind.
| wizofaus wrote:
| My understanding is those vector operations don't , in
| fact, add more than 2 numbers together, but rather
| simultaneously add lots of pairs of numbers. Happy to be
| corrected and no berating intended.
| mrkeen wrote:
| > Out of curiosity is there actually any chipset with the
| algorithmic ability to add more than 2 numbers
|
| Perhaps? But this would be like asking if there was a
| chipset that can work without branching because of
| someone mentioning "GOTO bad".
|
| > I'd also think looping is far closer than recursion to
| how we tend to manually calculate things
|
| It's not the looping I mind, it's the mutation.
| wizofaus wrote:
| If there were such an ability at the machine language
| level, it would be a strong argument against expressing
| the addition of a set of numbers using either a loop _or_
| recursion. I don 't really see that either manner of
| expressing such an operation is always preferable, and
| would rather simply use a built-in language or feature
| (e.g. reduce) that the compiler/interpreter is free to
| translate into the most appropriate machine instructions
| for the given hardware.
| TheOtherHobbes wrote:
| The only difference there is whether the "wrong answer" is
| visible while it's being calculated.
|
| Sums and factorials are the worst possible way to teach
| recursion because they look like a loop with a weird twist
| that adds conceptual complexity but doesn't seem to be there
| for any other reason.
|
| Recursion should really be taught by application to complex
| nested data structures. It's a lot clearer when you apply it
| to structures with multiple sub-levels that can be processed
| identically than with a simple linear list or range.
| hurril wrote:
| It isn't, though. I recently started learning Rust and've
| basically been having to teach myself loops again. For over
| 10 years, I've not constructed a single loop; I've been
| getting it done by constructing my program with different
| combinators and recursion instead. And I've not ever felt
| that what I'd done would have been better with a loop.
|
| It's even very seldomly that I even need if-statements.
| It's clearly a difference and I really would like to think
| of myself that I'm not _that_ deep into the cool aid.
|
| This has been done with Scala, F#, Haskell and Elm.
|
| With Rust, not only do loops feel more natural, they're
| very clearly the right tool.
| dandeere wrote:
| [dead]
| urthor wrote:
| The problem with recursion is we don't teach people what
| corecursion is.
|
| Corecursion, aka literally just plain looping, is a lot simpler
| and better for many, many activities.
|
| If we taught recursion by contrast, then it makes sense.
| Liberonostrud wrote:
| [dead]
| dandeere wrote:
| [dead]
___________________________________________________________________
(page generated 2023-04-05 23:03 UTC)