Clojurians Log v2

I think this should solve your needs to share code between userscripts, @neumann. Please let me know how you fare!

can i ask what the project is? im intrigued

oh, I went down a rabbit hole reading this paper https://arxiv.org/abs/2305.00813 and ended up making mcp which allows a LLM to load source code into a js sandbox, parse it with tree sitter, and then ask questions about stuff like function usage, call graphs, etc., which they normally have a hard time doing since it just ends up being ad hoc grepping https://github.com/yogthos/chiasmus

so you're using tree sitter parse trees as like a langauge-agnostic intermediate representation for z3 to analyze things? and it works?

yup seems to be working, still playing with it to tune things, but promising so far

prolog actually appears to be the more useful thing, cause you can trivially ask graph based questions using it

what sort of questions can you ask and what answers do you get back

I have some examples here https://github.com/yogthos/chiasmus?tab=readme-ov-file#why-chiasmus_graph-over-grep

the really interesting application is verification because you can ask questions like if there's only a specific path towards a particular bit of code

even just asking for callchain would be super useful. especially if it had a skill/tool description with some example questions that work well. i find that grepping around to see callchains happens pretty often.

yeah the trick is using templates, the llm can search for a template that roughly matches what it's trying to do, and fill in the blanks

fuzzy templates? is that a tree sitter thing or a prolog thing

templates are for the solver and prolog

tree sitter just gives the initial graph of the code that gets adapted

I'm really surprised this sort of stuff isn't standard in tools like claude code, it would make so much more sense to load the project into a graph, and then work against that instead of grepping files constantly

https://tree-sitter.github.io/tree-sitter/using-parsers/queries/1-syntax.html i was thinking of this.

like the way these tools work is the dumbest way possible

but prolog templates seem much better.

the language agnostic graph/tree sitter seem slkie the missing piece for these tools.

yeah that would be the ideal

can it apply edits using the graph? like somehow mutate the graph then go back to source? that would probably be super tricky and whitespace would be messed up

or maybe text edits + trees sitter feedback would be enough

yeah you'd need to do a bit more work there, but in theory you could parse the project into graph representation, then work against it, and serialize back when you're done

I'm actually playing with this approach here https://github.com/mycelium-clj/sporulator

but in a more restricted context

syntax/paren errors in trees-titter graph might be more useful than the clj explosions.

with Clojure we can just use the repl as the workspace

i looked at sporulator and i was a bit confused. visual buidler? are there screenshots?

there are two parts to it, there is a UI component, and a server side API driven part which is doing all the heavy lifting

the idea there is to box the LLM into doing very specific tasks, and doing a lot of the verification mechanically

so then LLM lives in a fast feedback loop where it produces code, it gets executed, then LLM gets results fed back to it with clear explanations on what needs changed

I did post some screenshots of the UI in the #ai-assisted-coding channel

I basically have a declarative graph for the execution flow, and then have the llm implement each step in the graph as an isolated component which gets resources and state, and produces a new state, then the workflow engine examines it and dispatches to the next node in the graph

how do you draw that graph? xyflow/react/uix? whats the ui stack

I used react flow

> I'm really surprised this sort of stuff isn't standard in tools like claude code, it would make so much more sense to load the project into a graph, and then work against that instead of grepping files constantly Same for humans. But we end up grepping about quite often too lol. I wonder if this could be made useful for editor use as well

oh I imagine yeah, IDEs do some of this stuff already, but you definitely could do a lot more with a logic engine

I wonder if it's just that most people aren't aware these tools exist and what you can do with them

I think IntelliJ recently added structural search. That's the first I’ve ever seen from editor land.

and IDEs have had stuff like find usages for a while, so the work of building the graph was already being done, it's just the step of feeding this graph into a logic engine that's been missing

And something like “(string-rope-by :line ….” Could maybe implement alternative indexing.

That's just an idea - there are significant hurdles to implementing it I think

I'm getting a lot closer to a 0.2.1 with some nice cleanups, optimizations, and specialized ropes. The index stuff is interesting but for another day

@smith.adriane i know my re-seq performance on the string rope is weak though. (that was your use-case, right?)

also, did you see my Zorp's Guide? lol https://github.com/dco-dev/ordered-collections/blob/master/doc/zorp-example.md

I use https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/regex/Matcher.html#find(), but I think it's the same idea. I don't think it's a performance bottleneck though.

For my code editor, I need some way to slice by several different index types, https://clojurians.slack.com/archives/C06MAR553/p1775779888581529?thread_ts=1775679394.837649&cid=C06MAR553

i touched on that idea. code points in the string ropes 🤢 and arbitrary extraction from byte buffers

For working with tree-sitter and rendering text via skia, it's also important to be able to grab byte array slices by byte index (eg. grab all bytes between 121-154).

we do that

Surprisingly, indexing by code point hasn't really been useful.

utf8 is a miricle and we should all cut our losses and say thats the best idea we’ve got

Yea, my code editor only supports utf-8

I looked at the docs and it didn't seem like the same rope could be indexed via bytes, code unit, grapheme cluster, line, etc.

not yet. i don’t even know what the hell a grapheme cluster is yet

i have a bunch of ideas about code unit and denotational semantics

I did make a video about all of these things, Designing Clobber: A Deep Dive into a Clojure-Powered Editor for Text and Code https://youtu.be/kRd4JYIiWb0?si=u3hd5dKHuysTfVRm

Happy to answer any questions as well.

A grapheme cluster is a "user perceived character". Multiple code points can be combined into a single visual symbol. The unicode standard includes tables and rules for how to do it. Programmatically, you can use icu4j's https://srl295.github.io/icu-docs/apidoc/released/icu4j/com/ibm/icu/text/BreakIterator.html

i guess one question before i continue I keep getting up on signed versus unsigned semantics with byte rope I am very unused to signed. I should have both, right?

*hung up

I'm just passing them along to these native libraries, so I just need a byte-array

oh we do that

I don't think there's any reason to provide unsigned semantics, since there are appropriate functions that work with Java's byte and byte-array types.

i keep running into where i want to

I'm curious what some example use cases might be

where you wouldn't just use byte and byte-array

i mean, you are very likely right. i have another library where i fought an existential battle to get the ideas right. The whole thing was founded on the pain points with unsigned arithmatic on the JVM https://github.com/danlentz/clj-uuid

maybe this question is just PTSD

also, it's probably easier to just give users byte-arrays and let them decide how to deal with them than try to guess what they need

thats a good architectural boundary

i love those

however

materialization costs a lot. Doing it within the rope is free

no maybe i understand

tbd

ropes are not easy

if you have ideas def add issue on github i want to work on this more

i go into more detail in the documention theres an overview you can look at here. Ropes are more efficient for splitting, joining, splicing, concatting, etc. CLJS doesn't supported multithreaded and also would be a significant rewrite so i'm not sure theres a lot of motivation

https://github.com/dco-dev/ordered-collections/blob/master/doc/ropes.md

i also ship a full set of benchmarks with it

yes. for <10 items Persistent Vector is faster (because at that size we are just a PersisitentVector wrapped in a one leaf tree.). Experimentally i found a chunk size invariant of 128-256 elements was reasonable. So, you won't see any advantage before that.

motivation for cljs support is for the user, if one wants to write portable code. Today one can use the built-in data structures and functions working with those will work on cljs

y, thats true. I might take a look at it at some point. and babashka. But, because JS has such different OO design and Performance characteristics than the JVM it would be a significant rewrite

definitely, it's not a cheap task

Otherwise, for context, here is the design rationale https://github.com/dco-dev/ordered-collections/blob/master/doc/concept/concept.md

Yeah the main motivation for my Rope in particular is the fact that it implements CharacterSequence which allows using them with Regex

Ya I’m definitely going to add specialized ropes for characters and bytes next

ok this is fun (string-rope (slurp \"big-file.txt\"))

Yeah it's great!

performant string rope not as easy as i thought it would be i may have to adjust my claim that ropes are "only 400 lines more code" I'm at a performance crossover at length of ~1K right now and after that we start to quickly dominate. Is that the right target? maybe try to treat smaller ones as regular strings under the hood?

thats just a ballpark i'm working on improving benchmarks

Depends on your use case. For a code editor, I think it's more important that it works for large code files than being optimized when used for small files. It's also really important to be able to slice and index code in various ways: • by byte • by code unit • by grapheme cluster • by line • by line and row (eg. grab lines 126-186 and only include columns 20-120) You also want to be able to keep track of offsets for various things that shift as you insert and remove text (code mirror calls them https://codemirror.net/examples/decoration/). This is important for stuff like styled text, inline code evaluation, syntax highlighting, auto complete placeholders, etc.

this is only very early and not fully reiewed but i’m making progress

strings first

i'm sorry i'm on two different laptops. i'm the hat and rabbit

i love this its fascinating. plus ropes are so tactile and fun to play with

If you're interested this is where we stand performance wise now if you're interested. The numbers are looking even more compelling

i wrote up the benchmarking methodology here: https://github.com/dco-dev/ordered-collections/blob/021-specialized-ropes/doc/benchmarks.md

do byte-ropes want to have signed or unsigned semantics?

well all java primitives are both

that is, they are treated as signed but you can specifically do unsigned ops

ok y. i was thinking of it too much like a vector of ints

the specialized-ropes are really just a "chunk" protocol over strings, vectors, and byte[]

or whatever else we want

it all abstracts away to the actual rope.

Rather than working with byte arrays directly, it might be interesting to use dtype-next's containers as nodes. Then you can work with byte arrays or off heap memory. This could be especially useful if you are using the rope alongside tree sitter or some other native library.

wow

its hard though

i need to read more about the gc maybe

i support bare chunks internally so that eliminates pressure to optimize the rope for small sizes. we should be about the equal performance until we blast off

my wife says if i say "rope" or "chunk" one more time i have to go sleep in the tree

i think it wouldn't be weight balanced anymore

Have you read much of the stuff on how clojure's persistent data structures work? I think that's what Bifurcan's rope is based on.

well bagwell and there's an excellent blog series on the persistent vectors. i did a ctrie project in common lisp, so there was a lot of that type of thing. but i'm sure there may be things i've forgotten to remember so i'm open to pointers

I thought part of the optimization for these data structures was using 32 way branching and chunk sizes that are good sizes for CPU caching. Is your library doing something similar?

no. its a binary tree

however, the set algebra is work-optimal

and its an amazing workhorse for implementing arbitrary concrete collection types

i beat the built in hash set down to very small sizes for set algebra

It was my impression that binary trees aren't very efficient on modern CPUs and that is solved by using a higher branching factor.

well, its a really good question for sure. i don't know if there is any literature that supports the idea that set ops (union intersection etc) can be done more efficiently than split-join binary tree with fork join parallelism. with or without memory locality its just the optimal algorthm.

now, proving that is way way above my pay grade. but i have links in the references

there are always trade offs. I thought ctries would be great then i went back to ths

they have 32 branching factor

its basically a hash map with optomistically parallel inserts.

well, I believe Bifurcan's rope is more similar to clojure's data structures. It might be interesting to see how it compares.

for sure it is a nice library.

and thats helpful feedback i defintely will

It also keeps track of code points for indexing and slicing. I've been meaning to try to update it to track code units, grapheme clusters, and newlines.

i haven't looked at those but the hope is they fit into my Chunk protocol and are trivial to add

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Rope Chunk Protocol
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defprotocol PRopeChunk
  "Chunk abstraction allowing the rope kernel to be generic over chunk type.
  Extended to APersistentVector (generic rope) and String (string rope).
  Protocol dispatch cost (~2-3ns) is comparable to the type-hinted interface
  calls it replaces."
  (chunk-length [c] "Number of elements/characters in chunk")
  (chunk-slice [c start end] "Subrange [start, end)")
  (chunk-merge [c other] "Concatenate two chunks")
  (chunk-nth [c i] "Element/character at index i")
  (chunk-append [c x] "Append a single element/character")
  (chunk-last [c] "Last element/character")
  (chunk-butlast [c] "All but last element/character")
  (chunk-update [c i x] "Replace element/character at index i")
  (chunk-of [c x] "Create a new single-element chunk of the same type")
  (chunk-reduce-init [c f init] "Reduce over elements/characters with init value.
    When f returns (reduced x), stops and returns @(reduced x).")
  (chunk-append-sb [c sb] "Append chunk contents to StringBuilder")
  (chunk-splice [c start end replacement] "Replace [start, end) with replacement chunk (may be nil for deletion)")
  (chunk-splice-split [c start end replacement half]
    "Like chunk-splice but returns [left-chunk right-chunk] split at position
    half in the spliced result. Avoids building the full intermediate chunk.
    Used by the fused splice overflow path."))

That would be awesome.

wip

Working with Bifurcan's Java code is a pain (for me). I assume an idiomatic clojure version would be a lot more flexible. I wouldn't be surprised if it ends up being faster, just because it's easier to change.

y, thats the entirety of the surface area for defining a new species of rope. And wrap it in a new collection deftype

I imagine you would need to have additional protocols if you want to index/slice by different indices (eg. byte, code unit, grapheme cluster, line, etc)?

yes i havent even started to think of what that looks like tbh

but, you can openly extend this protocol over any concrete type you want. so maybe adding some type of index indirection to the protocol could get us there. any problem in computer science can be solved with another layer of indirection, except for the problem of too many layers of indirection, as they say

https://github.com/danlentz/cl-ctrie

went nowhere but superb exercise

i went way, way, too general. which was fun, but no hope of being performant

"Pandoric Objects". lol. we were all young once

as far as this library, i needed some of this for work. so i donated https://github.com/danlentz/clj-wbtree and released it through them

this way i can get paid to work on it (although patience may be wearing thin lol)

i see it as just supporting "open source" in some minor way and they're aligned with that so all good

we've been using it in production for like 8 years

my early version had a dynamic balance parameter where you could turn into a red-black tree or any other balance strategy by binding n-join but it turns out all the other ones suck

@smith.adriane ctrie does have a memory-mapped on-disk persistence model, with hand written garbage collector so thats why i started thinking of all this.

it also could be a lightweight in memory object of function thats where i went wrong. but it was fun times

*went wrong with ctrie i mean.

i'm still pushing for generality+performance but this is a better approach

i'm takin another swing at it, baby

(what i've just explained to my wife about the new AI bills)

back to business, papering over losses at small sizes by supporting bare chunks makes us perflormant at every cardinality

that resolves the other guys question about if they're perforant at <10 nodes (almost)

hey @suskeyhose haven't you talked about wanting a ropes library?

https://github.com/IGJoshua/ropes

Yea I wrote one lol

but this is cool!

haha crap, i'm late to the party. yes, this is also very cool

It might be interesting to compare with options from https://github.com/phronmophobic/bifurcan

yeah. that wasn't in my radar but it should have been thanks

good for benchmark and equivalence testing

i could do a string specialized rope for next version. at some point i just had to cfut this off and get it out the door

yea, looks great!

I've been using a fork of Bifurcan's rope for my IDE's text editor, https://github.com/phronmophobic/clobber. If you want to chat about Rope use cases, I would be happy to.

For code editing, it's really nice to have slicing/indexing by: • byte (for compatibility with tree sitter) • code unit (for compatibility with java strings) • grapheme cluster (for editing text) Surprisingly, I haven't found a need to slice/index by code point.

rope bro's. ya i think i could learn a lot. i'm about done for today but dm me or i'll dm you

> 10–5000x faster than PersistentVector at scale. for what operations, all of them? What does "at scale" mean, e.g. for <10 items persistent vector is faster? Do you plan cljs support?

⏺️ ordered-collections 0.2.1 is out A follow-on to 0.2.0 focused on specialized ropes and a performance pass. New collection types - string-rope — persistent chunked text, implements CharSequence so it drops into re-find, clojure.string, http://java.io.*. EDN tag #string/rope. ~130× faster than String on structural edits at 500K chars. - byte-rope — persistent chunked binary with unsigned [0, 255] semantics and streaming MessageDigest. EDN tag #byte/rope. ~128× vs byte[] on remove at 500K. Rope kernel - One kernel now drives all three variants via a small PRopeChunk protocol. - Flat-mode for small ropes (≤ 1024 elements live as a bare PersistentVector / String / byte[], no tree). - Monomorphic nth / reduce hot paths per variant (~2–2.5× faster). Tree kernel tune-ups - Primitive rank for long-ordered- / string-ordered-. - O(n) bulk build for sorted-disjoint range-map input. - Non-allocating .iterator() for OrderedSet / OrderedMap (2× vs sorted-set, 3.6× vs data.avl). Bug fixes. Primitive specialization no longer silently downgrades on conj. Various small StringRope / ByteRope contract fixes (empty fold, non-integer keys, InputStream bounds, surrogate-pair chunking). No breaking changes. 695 tests, 471K assertions. Full details: https://github.com/dco-dev/ordered-collections/blob/master/CHANGES.md · Numbers: https://github.com/dco-dev/ordered-collections/blob/master/doc/report.txt

It may be worth a post in #releases

yup done. you will have to take a look at byte-rope. I still had to make some decisions on semantics that I'm not sure of. The way strings should behave seemed clearer.

the byte ropes and string ropes were a learning experience. You can be elegant and pass through ~5 layers of protocols, but leave a lot of easy performance wins on the table. Or you can be fast. I worked hard to factor as much for simplicity as possible, but where the two ideas were in conflict i went for fast.

as far as semantics, this was an example where i just had to pick a lane. maybe it should have binary protocols for both signed and unsigned semantics?

;; ByteRope — binary protocols, streaming digest
(def packet (oc/byte-rope [0x48 0x45 0x4C 0x4C 0x4F]))
(oc/byte-rope-get-int packet 0)  ;=> 1212501068