[HN Gopher] Reflecting on Transducers in Scheme (2023)
___________________________________________________________________
Reflecting on Transducers in Scheme (2023)
Author : fanf2
Score : 42 points
Date : 2024-08-20 17:42 UTC (5 hours ago)
(HTM) web link (www.thatgeoguy.ca)
(TXT) w3m dump (www.thatgeoguy.ca)
| tonyg wrote:
| I wonder if the author considered SRFI-42 at all? It looks, at a
| glance, similar.
| bjoli wrote:
| They are not similar at all, except that they might overlap.
| Transducers are functions that perform one-way transformations
| of data. Srfi-42 is couple of loop macros.
|
| I wrote both srfi-171 (mentioned in the post) and this looping
| macro https://git.sr.ht/~bjoli/goof-loop which is probably the
| most powerful one scheme (at least that generates fast code)
| has to offer until someone reimpmements Olin's loops.
| tonyg wrote:
| > They are not similar at all, except that they might
| overlap.
|
| (Well, which is it?)
|
| Perhaps I was misled by the intro to the article, that wished
| for something like Rust's iterators: generic data-source-
| neutral map/filter/zip/etc utilities, static dispatch,
| extensible. Srfi-42, Racket's for/* system, and your goof-
| loop all seem to fit the bill. Obviously the article ended up
| at a dynamically dispatched system, like -171, but to start
| with it didn't seem like it had to have headed in that
| direction.
|
| > Srfi-42 is couple of loop macros.
|
| This is decidedly ungenerous, especially given its historical
| relationship to Barzilay's work and descendants.
| taeric wrote:
| Fun article. I'm somewhat still in the camp of loving Common
| Lisp's LOOP over many of the newer tools that are for looping
| over things. Articles like this do a good job of shining light on
| a lot of the concerns.
|
| Quick nit/question. For the fold method, I don't think I've seen
| it called sentinel value. Usually it is seed or initial?
|
| Now, my main question. Transducer? I'm curious on the etymology
| of that word. By itself, I don't think I could ever guess what it
| was referencing. :(
| zappacino wrote:
| AFAIK, the term was popularized by Rich Hickey in Clojure's
| implementation [1]. His talk introducing the concept goes into
| the etymology specifically. If I remember correctly it's
| something like "to carry across."
|
| [1] https://clojure.org/reference/transducers
| bjoli wrote:
| Transducers are not loops. You can create transducers and pass
| them as arguments to functions, that in their turn can prepend
| or append then.
|
| They are composable algorithmic transformations.
| drcode wrote:
| composable algorithmic transformation in the streets
|
| but mostly an alternative to LOOP in the sheets
| bjoli wrote:
| Sure. But in that case it is somewhere between
| map(car)-and-friends and LOOP.
|
| Which is a situation where they add very little. Being able
| to use them as an intermediate step wherever data flows is
| probably the only place I use them myself. In channels, in
| file-readers etc. in places where you really need speed you
| should of course reach for whatever loop construct you
| prefer.
| Zambyte wrote:
| You are correct with your question, SRFI 1[0] describes the
| knil argument as the "seed" or fold state (the latter for a
| recursive implementation). A sentinel value usually refers to a
| final value.
|
| Regarding the etymology: transform + reduce = transduce
|
| [0] https://srfi.schemers.org/srfi-1/srfi-1.html#fold
| jiehong wrote:
| Nice to see Scheme being active. It is really used much in
| companies?
|
| While the author speaks about Rust iterators at first,
| Transducers seem better in the end.
|
| In Java 23, the introduction of gatherers seems to be an attempt
| at having a more open set of functions of a stream, which
| transducers don't suffer from.
|
| Rust Iterators seems to also have this limited sed of actions
| available (but some crate like tap seem to allow to .pipe() a
| function).
| veqq wrote:
| > It is really used much in companies?
|
| Cisco seems to use Chez for something mysterious, a video game
| company scripted in Scheme, stopped and restarted again. I know
| a guy who does option trading in Racket, I have some large
| valuation models in Racket (most of the system is in and Common
| Lisp). I know a few guys who do vague data analysis and
| scripting in scheme (especially Guile or Gerbil for some
| reason) where their clients only care about the result.
| https://www.itasoftware.com/ is in scheme. There are some dead
| webshops(?) like
| https://www.greghendershott.com/2018/05/extramaze-llc-using-...
| or https://defn.io/2019/08/20/racket-ecommerce/
|
| That's about it.
| Jtsummers wrote:
| ITA used Common Lisp. The game company you mentioned is
| probably Naughty Dog who created "Game Oriented Assembly
| Language" for their games. GOAL was created in Common Lisp
| but was Scheme-like. They switched away after being acquired
| by Sony and needing to fit in better, they brought it back
| later on though.
|
| https://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp
| kazinator wrote:
| Never try to fit in after being acquired. Be what they
| acquired.
| bjoli wrote:
| I wrote the transducers srfi.
|
| I don't really mind schemes monomorphic nature and chose to
| adhere to it and leave a generic transduce form for whenever
| there is a good way to implement it in a portable way. There is
| really nothing stopping anyone from extending SRFI-171 with a
| generic transduce form (and some more transducers that I left out
| because didn't really think it through). Such a project has my
| blessing and I would be happy to mark the SRFI as superseded.
|
| A vector-reduce form would be trivial but icky, and I chose not
| to do it to not have to have the continuation safety discussion.
| I have an idea to make thread and continuation safe transducers
| with immutable and visible state, but the first PoC was pretty
| slow. (I am going to say it... I miss c++ move semantics. Ouch)
|
| Anyway, if I read things correctly the complaint that srfi-171
| has delete dupes and delete neighbor dupes forgets that
| transducers are not always used to or from a data structure. They
| are oblivious to context. That is why both are necessary.
|
| The SRFI document was written for someone who already knows what
| a transducer is, and specifies an API that implementers are to
| follow. I did not intend for it to be user documentation. User
| documentation is severely lacking. I was hoping for it to make it
| into r7rs-large (hubris. I know) and then I would make some kind
| of push to document it better. As it is now I have very little
| computer time.
|
| Regarding why transducers are faster I am still pretty certain it
| has to do with mutation and boxing. Looking at the assembly
| generated by srfi-171 in chez I don't really see that much
| aggressive inlining - and I don't think chez would fare much
| worse with srfi-158. Generators and accumulators use set!
| everywhere, meaning chez (and guile) doesn't really try to keep
| the values unboxed or typed. That incurs quite a slowdown. It
| does use more state though.
|
| Sorry about the messy response. Typing this while walking home.
|
| In short: his library looks fine. Use it. From what I can see the
| only differences are ordering of clauses to make the transduce
| form generic and naming conventions. His library shadows a bunch
| of bindings in a non-compatible way. The transduce form is still
| not generic but moves the list-, vector-, generator- part of
| transduce into a "folder". Which is fine. But a generic dispatch
| would be nicer.
|
| Ask me anything I guess.
___________________________________________________________________
(page generated 2024-08-20 23:00 UTC)