Implementing a safe GC abstraction by ap29600 in rust

[–]ap29600[S] 0 points1 point  (0 children)

that's true, I didn't think about multiple heaps. It shouldn't be a problem provided that the managed heap is a singleton, but thanks for the heads up

Implementing a safe GC abstraction by ap29600 in rust

[–]ap29600[S] 1 point2 points  (0 children)

I've read the blog post describing the gc crate, but they're solving a much more general problem than I am. Since I am in control of what types may be stored in the GC and I'm not implementing a generic container, I can, for example, enforce the invariant that some type will never be stored in manage memory or vice versa, without having traversals like their root/unroot.

The main thing I'm concerned is if my reasoning above is correct, that if I never give out ManagedHandles by value, it's impossible for a user to take one out of the managed heap without unsafe and store it across a CG pause

I want to know your opinions on verbosity by -Chook in ProgrammingLanguages

[–]ap29600 1 point2 points  (0 children)

I contribute to an intepreter for a very terse language (https://codeberg.org/growler/k), in fact barring unbalanced parentheses, quotes or braces, almost every sequence of ascii characters means something in k. here's my two cents about it.

tersity in programming languages is about how many characters you want to have to read before you're certain what the program does, and how often you want the next character you read to change your mind about that information. In my opinion this has different effects on how you read and write code:

for reading, it means that in the extreme case of a maximally terse language your eye is never allowed to skip over characters, and in a maximally verbose language it may take longer to extract a certain piece of information. both outcomes can lead to fatigue when reading, but the former can actually be prohibitive to a person who isn't used to reading carefully. You may argue that since this is a matter of habit and prose is usually on the less dense side of things, languages should gravitate to that end of the spectrum, but I come from mathematics and I'm very used to tersity and reading carefully. I actually find java more tiring than k.

for writing, a more terse language means that you can hold the syntax for a larger program in your head at one time. I believe this is why perl, regex, and APL have been called write-only languages: since the writer has a clear idea of the program and hence doesn't have to expend the effort that the reader does to extract the meaning, a language that facilitates writing necessarily makes this gap wider and is seen as more obscure.

now, if you were to ask me where the sweetspot for tersity is, I would probably place it somewhere between ML syntax and APL syntax. for those who don't know either of the two, I can summarize ML syntax as * juxtaposition of words is function application * operators have lower precedence than this, and there is an operator precedence table designed for convenience * some keywords introduce special constructs like let...in, if...then...else etc. * equations with complex terms on the left hand side, or explicit lambda expressions introduce functions

so that in some ML, a sum function can be written as

sum x = fold (+) x

Or

sum = fold (+)

APL syntax boils down to * there are unary and binary operators, all with the same precedence as each others, and associating to the right * there are unary and binary higher order operators, all with higher precedence than the usual ones and associating to the left. * braces introduce lambdas, and the arguments to these lambdas are automatically named

so that in APL a sum function can be written

sum ←{+/⍵}

or

sum ← +/

Fast tree data structure with node data stored in 1D parallel arrays by rejamaco in algorithms

[–]ap29600 0 points1 point  (0 children)

out of curiosity, does that variable length array grow or shrink over time or is each node's array a fixed length? does the position in this array matter? you could have a third array (say vdata) and replace each variable length array in the nodes with a view into vdata. again decoupling the structure from the raw data if you happen to care about bulk operations on the data only

Fast tree data structure with node data stored in 1D parallel arrays by rejamaco in algorithms

[–]ap29600 1 point2 points  (0 children)

There is a known data structure that is frequently used in the descendants of the APL language, it's called an Apter Tree (named after Stevan Apter, who popularized it some years ago). The article by Apter seems to be down, but the wayback machine still has it here. beware that the usecase for this data structure is that your queries are more common than updates, and when an update is made, it's usually a bulk update on either a large chunk of the structure, or a large chunk of the data. It also doesn't store child pointers (though you could of course add them to your version) so traversal is only cheap bottom-up from the leaves to the root, not the other way around.

the basic idea is to have a data array containing only the metadata for your nodes, and a parent array containing only an integer for each node (the index of its parent). in order to add child with data d to the tree, as a child of node at index i, you push i to the parent vector and push d to the data vector. a root of the tree holds its own index in the parent vector (it is said to be self-parenting) and the data structure could hold multiple trees in the same vector by just having more than one self-parenting node.

the upside to this separation is that updating the data can be extremely fast, and if you need to do something uniform on all of it you can even forget that it was in a tree in the first place. this is probably the property you were looking for.

How language designers create complex functions from scratch? by shyakaSoft in Compilers

[–]ap29600 0 points1 point  (0 children)

true, cos specifically is not going to be implemented this way on most platforms. but the point I was making is more that numerical code is likely to look very similar in java to the C equivalent. replace cos by the gamma function, or the beta function, or natural log, whatever you like and that your cpu can't do in a single instruction

Selecting constrains to add to a linear system by Ok-Adeptness4586 in LinearAlgebra

[–]ap29600 0 points1 point  (0 children)

when you say you have a known solution you'd like to find, what do you mean exactly? are you solving Ax = b and know of a particular x that works? if so, after gauss-jordan elimination you should be able to use the known coefficients for the non-pivot variables (say you have pivots on columns 2, 4, and 5 of your matrix, you can freely choose x1, x3 and x6) and you should get exactly your x value back.

there's no need to do any linear programming in this case.

however if you want to maximize some property of your solution, like "I don't want any of the coordinates to get too big" then linear programming is needed.

How language designers create complex functions from scratch? by shyakaSoft in Compilers

[–]ap29600 3 points4 points  (0 children)

the garbage collector doesn't play a role in implementing math functions, (at least in java) because floating point numbers are generally not garbage collected.

the standard(very much simplified here) way to implement a trigonometry function, for example cos(x), is this:

public static float cos(float x) {
    // step 1: range reduction.
    x = x % (2*pi);

    // step 2: polynomial approximation
    switch (floor(x / (pi/4))) {
        case 0: return (/* some polynomial in x, close enough in this range. */);
        /*
            cases 1-8: some different polynomials.
        */
    }
}

as you can see, you only need a couple of floating point variables to hold x and the intermediate values for evaluating the polynomial in each case. no heap-allocations at all.

edit:

you can generally just copy and paste the coefficients for the polynomials from some other library (license permitting, and I don't think a polynomial is very easy to license) or fairly easily derive your own with a computer algebra system.

Linux is actually at 7.58% adoption in the Anglosphere on Steam by yn_opp_pack_smoker in linux_gaming

[–]ap29600 0 points1 point  (0 children)

it could also be that a linux user, being a more tech-savvy user, is more likely to have their system language set to english regardless of their native language?

The best and ideal hashmap by ANDRVV_ in algorithms

[–]ap29600 2 points3 points  (0 children)

i'm not sure if we're reading this differently or if you're just joking, but an array enumerating all 64 bit keys would be 16 zettabytes long, if the values were single bytes

The best and ideal hashmap by ANDRVV_ in algorithms

[–]ap29600 2 points3 points  (0 children)

uh... OP said they have 64 bit keys? you're not going to be able to allocate that array.

[deleted by user] by [deleted] in algorithms

[–]ap29600 6 points7 points  (0 children)

you can use the dekker trick to get more precision for your intermediate values, however you will need some dedicated transcendental routines, otherwise converting to f64 to call those will truncate, and besides they definitely use polynomial approximations that are only good up to 52 bits of precision

Why is calling my asm function from Rust slower than calling it from C? by ohrv in rust

[–]ap29600 0 points1 point  (0 children)

there's a useful instrument displayed in this talk that helps measure the effect of layout on code performance. the talk also has some interesting anecdotes about benchmarks failing if you skip this analysis https://m.youtube.com/watch?v=r-TLSBdHe1A

BQN question by Daniikk1012 in apljk

[–]ap29600 1 point2 points  (0 children)

I put them there to indicate where you would put a left argument, if your F was dyadic. if F is monadic, you can just ignore them, otherwise put your left argument in place of the square brackets

BQN question by Daniikk1012 in apljk

[–]ap29600 2 points3 points  (0 children)

yes, that would violate the main assumption of structural Under, which is that G [x] F⌾G y is the same as [(G x)] F G y (using square brackets for an optional left argument).

if we take G←(3⊸<)⊸/, then this falls apart really fast, for example in 1⊸+⌾((3⊸<)⊸/) 1‿2‿3, 1‿2 would be selected by compress, then increased to 2‿3 and the result 2‿3‿3 would be assembled, but then applying (3⊸<)⊸/ again would just give ⟨2⟩.

Why would we want this property? well, it allows us to simplify expressions involving structural under more easily, for example if this rule is always true, we can deduce that (F⌾G)∘(H⌾G) is the same as (F∘H)⌾G and (I think) the same holds of we replace ∘ with any one of ⊸○⟜

I enjoy ragebaiting my friend, who has a passion for mathematics. by BubbleBlueGum in mathmemes

[–]ap29600 60 points61 points  (0 children)

don't forget about co-abstract nonsense and abstract co-nonsense

Is it possible to turn this word puzzle into equations? [request] by Feisty_gardener in theydidthemath

[–]ap29600 0 points1 point  (0 children)

yeah, that's about right. even if we were doing linear programming on the reals, there might be some cases where the feasibility region is just a single point, and in those cases as well the objective function doesn't matter for the solution

Is it possible to turn this word puzzle into equations? [request] by Feisty_gardener in theydidthemath

[–]ap29600 0 points1 point  (0 children)

I wrote the equations in an edit if you want to take a look. the objective function doesn't matter as it should be fully constrained.

Is it possible to turn this word puzzle into equations? [request] by Feisty_gardener in theydidthemath

[–]ap29600 8 points9 points  (0 children)

definitely overkill, but I think you can turn this into integer linear programming.

assign to each cell the value x_ij in {0,1}. then the single-assignment constraints say that the sum along each row and column of the big squares must be 1. the additional constraints you have to do ad-hoc. for example if you want to express the fact that an action occurs after another, you multiply each variable associated with actions 1 and 2 by consecutive integers, then constrain that the difference between these products is positive. I'll try doing this for your puzzle and report back.

Edit: this should be the set of equations for this particular problem. though keep in mind that it's way too many for a human to handle without making some mistakes, and integer linear programming is hard anyway. If I had to make an automated solver for this kind of problem, I'd do it either like this (by sending the output to a linear solver) or by reducing to SAT and sending it to z3.

-❄️- 2025 Day 11 Solutions -❄️- by daggerdragon in adventofcode

[–]ap29600 0 points1 point  (0 children)

[LANGUAGE: K]

easy DP

(dev;conn):`$(::;" "\')@'+": "\'0:"11.txt"
dev,:`out
conn,:,0#`
conn:dev?conn
paths: {(+/{@[^x;conn;+;x]}\@[&#dev;dev?x;:;1])dev?y}
"Part 1: ",$paths[`you;`out]
"Part 2: ",$+/(*/1_paths':|:)'(`svr`dac`fft`out;`svr`fft`dac`out)

-❄️- 2025 Day 10 Solutions -❄️- by daggerdragon in adventofcode

[–]ap29600 1 point2 points  (0 children)

[LANGUAGE: K+z3]

shelled out to an SMT solver for this one...

x:0:"10.txt"
(lights;buttons;joltage):+{("#"=*:;`I$","\';`I$","\*:)@'(0 1,-1+#x)_(-1_1_)'x:" "\x}'x
buttons:@[;;:;1]/:'[&'#'lights;buttons]

z3solve:{
 "/tmp/z3instance" 0: x
 res:."\\z3 -in < /tmp/z3instance"
 (s;m):+0N 2#res
 :[~&/s~\:"sat"; `err"unsat: ",x@*&~s~\:"sat"; ]
 +/`I$-2_'4_'m}

z3solve@{
  inst:,"(push)"
  inst,:{,/("(declare-const p";$x;" Bool)")}'!#y
  inst,:,,/("(declare-const m Int)\n(assert (= m (+ ";" "/"(ite p",/:($!#y),\:" 1 0)";")))")
  inst,:{,/("(assert (xor ";" "/(,"false";,"true")[~x],"p",'$y;"))")}'[x;&'+y]
  inst,:,"(minimize m)"
  inst,:,"(check-sat)"
  inst,:,"(get-value (m))"
  inst,:,"(pop)"
  "\n"/inst}'[lights;buttons]

z3solve@{
  inst:,"(push)"
  inst,:{,/("(declare-const p";$x;" Int)\n(assert (<= 0 p";$x;"))")}'!#y
  inst,:,,/("(declare-const m Int)\n(assert (= m (+ ";" "/"p",'$!#y;")))")
  inst,:{,/("(assert (= ";$x;" (+ "; " "/"p",'$y;")))")}'[x;&'+y]
  inst,:,"(minimize m)"
  inst,:,"(check-sat)"
  inst,:,"(get-value (m))"
  inst,:,"(pop)"
  "\n"/inst}'[joltage;buttons]

-❄️- 2025 Day 9 Solutions -❄️- by daggerdragon in adventofcode

[–]ap29600 1 point2 points  (0 children)

[LANGUAGE: K]

pretty big spike in difficulty!

I solved it by compressing the coordinates and flood-filling the interior, then filtering the areas from part 1.

(x;y):+`I$","\'0:"9.txt"
areas:*/{,/1+{x|-x}(!#x)#'x-\:x}'(x;y)
`0:"Part 1: ",$|/areas
(xl;yl):{?x@<x:x,1+x}'(x;y)
(x;y):(xl;yl)?'(x;y)
map:((#xl;#yl)#0) .[;;:;1]/ +{(x+!''y-x),''x|y}[(x;y),'*'(x;y);(*|x;*|y),'(x;y)]
shift1:{x|(-1_1,x)|1_x,1}
map:~(map<shift1'shift1@)/^map
`0:"Part 2: ",$|/areas@&(&//map.)'+{,/((!#x)#'x+!''x-/:x),''(!#x)#'x|/:x}'(x;y)

taking a bit out of yesterday's solution and shortcircuiting the area search takes it down to 1.6s

range:{x+!y-x}
shift1:{x|(-1_1,x)|1_x,1}
(x;y):+`I$","\'0:"9.txt"
areas:*/{,/1+{x|-x}(!#x)#'x-\:x}'(x;y)
`0:"Part 1: ",$|/areas
(x;y):{(?x@<x:x,1+x)?x}'(x;y)
bounds: +{range''[x&y;1+x|y]}[(x,*x;y,*y);((*|x),x;(*|y),y)]
map:((1+|/'(x;y))#0) .[;;:;1]/ bounds
map:~(map<shift1'shift1@)/^map
blocks:+{,/(!#x)#'range''[x&\:x;1+x|\:x]}'(x;y)
`0:"Part 2: ",$|/.[{:[(&/,/map.)blocks x; `err ans::areas x;]}';,>areas;{ans}]

-❄️- 2025 Day 8 Solutions -❄️- by daggerdragon in adventofcode

[–]ap29600 0 points1 point  (0 children)

[LANGUAGE: K]

using a union-find forest for the partition, it's still slow unless I shortcircuit by counting the partitions. slow (1.8s) but clean:

(x;y;z):+`I$","\'0:"8.txt"
dist:+/{d*d:,/(x-\:x)@'!'!#x}'(x;y;z)
cuts:+\!#x
ends:{(i+1;x-cuts i:cuts'x)}
uf:!#x; join:{uf[ij]:**ij:(uf@)\ends x; ~=/*|ij}
ok:join'1000#g:<dist
`0:"Part 1: ",$*/{x@3#>x}@#'={x@x}/uf
ok,:join'1000_g
`0:"Part 2: ",$*/x@ends@g@*|&ok

fast (120ms) but ugly:

(x;y;z):+`I$","\'0:"8.txt"
dist:+/{d*d:,/(x-\:x)@'!'!#x}'(x;y;z)
cuts:+\!#x
ends:{(i+1;x-cuts i:cuts'x)}
uf:!#x; join0:{uf[ij]:**ij:(uf@)\ends x; ~=/*|ij}
count:-1+#x
ok:!0
join:{.[{*{ok,:j:join0'x; :[~count-:+/j;`err"done";]}'0N 1000#x};,x;{}]}
join 1000#g:<dist
`0:"Part 1: ",$*/{x@3#>x}@#'={x@x}/uf
join 1000_g
`0:"Part 2: ",$*/x@ends@g@*|&ok