prog


What are you working on?

1 2018-12-22 22:05

This is the type of thread that you can write in every time you visit the site! You can do anything from use this as a personal log for your project, to sharing what you're hacking on at the moment, or to critique something some else did in the thread. I'm looking forward to hearing what you guys are up to!

Personally I've been working on a radix tree implementation in R7RS, it seems moderately efficient and not too bad to use, although I haven't finished many of the operations, and I'm not sure I will due to the awareness of a better way to do it if I only had the primitives (or even just a standardised FFI). Anyway thought I'd share it just because it's something to talk about. Due to the file limit I'm only posting the introduction, imports, exports, and type here, but a link to the full source can be found here: http://ix.io/1wB1.

; This is a implementation of a radix tree in the style of Clojure or
; Scala, meaning a not particularly good implementation. Ideally this
; would be a adaptive radix tree as described in the following paper:
; http://www-db.in.tum.de/~leis/papers/ART.pdf
; additionally it'd be nice to be able to have a variant for using SIMD
; functions on unboxed values if possible. Regardless scheme does not
; have the necessary primitives for implementing a adaptive radix tree
; to its full potential, namely access or abstractions of SIMD functions
; for the search function.

; much of this library may seem unidiomatic, this is simply because I'm
; trying quite hard to A) avoid allocations and B) factor out functions
; when they can be used in multiple situations, even if this means adding
; a bit of complexity.

; one of the goals of this library was to be exceedinly standard compliant,
; it's written entirely in R7RS small with SRFI 1 & 60. That being said
; this doesn't actually make this a particularly portable library due to
; the lack of upto date compliance with the standard and implementation
; of SRFI 60. To my knowledge the following implementations would likely
; be able to run this library: Foment, Gauche, Larceny, & Sagittarius.

(define-library (data radix)
  (export radix-ref radix-set radix->list radix->vector
          vector->radix list->radix radix radix-append
          radix-data radix-length radix-depth))

(import
  (scheme base)
  (srfi 1)   ; append! in radix->list
  (srfi 60)) ; bitwise operations

(define-record-type radix #t #f data length depth)
96


VIP:

do not edit these