745 karma · joined June 12, 2019
But I wholeheartedly agree with the sentiment of "don't make the grammar look like Scala" <3
- If the parser is "the thing that comes after the lexer" then all of this is abstracted away by the lexer and you can just treat it as a span of bytes;
- If the parser is "everything that needs to be implemented to correctly transduce the input sequence into a tree", then you need to implement this yourself or have a lexer that handles this for you, usually done by having a tiny UTF-8 codepoint recognizing FSM in your lexer (UTF-8 is a self-synchronizing code, which makes this part easier) and ignoring the existence of graphemes.
Most people, however, shy away from implementing a parser "all the way down to the bytes" and properly handling UTF-8 as a formal language. Most lean on a lexer abstracting this away. Ditto for context-sensitivity.
Recently Rust's regex engine underwent a major overhaul, and burntsushi wrote a blog post[0] about doing the "all the way to the bytes" thing in the new regex engine, I highly recommend the read:
[0] https://blog.burntsushi.net/regex-internals/#nfa-optimizatio...
> People are terrified of parsers and parsing
And rightfully so. People who aren't afraid of them generally fail to understand all of the ways in which parsing can show fractal complexity, and will mostly stick to toy examples like this INI parser to justify their positions.
If you're gonna argue that parsing is simple, the bare minimum I'd want to see implemented is a context-sensitive grammar with unbounded lookaheads (or at the very least, that is capable of handling more than one token of lookahead), with proper support for Unicode, and actual error resilience (not what this article calls error resilience)
If you manage to do all that and can still call what you did "simple" without having completely deluded yourself, congratulations, I hope to be on your level some day.
PS1: I won't even go into the plethora of security issues originating from crappy parsers, especially those written in C
PS2: Let's also leave aside any matters related to correctness and validation of parsers, which are notoriously not by any means "simple".
PS3: Or generating decent errors for that matter.
GGML seems to be just one gigantic 10K LOC C file anyways...
Another annoying constraint but specific to wgpu (Rust's implementation of WebGPU) is that it does not support f16 yet (which IS in the spec), only through SPIR-V passthrough...
Cozo is looking like a top-contender for my project so far :)
By larger than RAM I mean the entire WikiData knowledge graph (~100GB), with something like 16GB of RAM.
Another question: any plans for supporting Parquet files with query pushdown? I honestly doubt Parquet's efficiency can be matched with RocksDB (but I'm happy to be proven wrong), and having to convert big datasets is always a pain...
That is truly maddening
TCL being stringly typed makes it dead on arrival for me, and I'm sure others feel the same.
I still feel like this trick has it's place though, as an example take a look at where I stole this trick from, by matklad [0] and tell me what you think :)
[0] https://github.com/rust-analyzer/rowan/blob/d2c7843858da9d9e...
I'm only speculating though, as this is a pretty common mistake
#[repr(u16)]
enum Foo { A = 0, B }
#[repr(u16)]
enum Bar { A = 3200, B }
struct FooOrBar(u16);
I'm not proud of this...
But hey! At least he went to Harvard right?...
[0] https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti...
[0] https://www.theverge.com/2021/5/7/22424367/sonova-buys-sennh...
Brazil uses a national standard called ABNT2 (which I consider to be an awful format), but to my advantage, I find the way Macs do accentuation (at least for latin alphabets) to be quite sensible (alt+vowel), and get angry whenever I have to use Linux because it doesn't have "Mac accents"
For your case though, I think the Nordic alphabet might be trickier on the US layout, since it shares less common ground and there's a lot more to it
It takes a bastardized definition of "trust" to make this statement true, and it's a definition that is most often seen in the wild when used to "sell" blockchain stuff as having technical capabilities they do not, in fact, possess. It is a dishonest and misleading definition.
There are several mechanisms of trust that exist, authorities are just one of them. Reputation is another, so are proofs, and so is consensus (which is the most interesting one for the case at hand). Blockchains are essentially "Paxos, but for a massive peer count, and with some mechanisms that allow it to operate in an adversarial networks", but it is fundamentally still just a consensus algorithm (in Bitcoin's case, one where people "agree" that John Doe has X amount of money).
Shifting to P2P essentially just means that:
- You will trust a bunch of random people instead of a centralized authority;
- You will trust that these random people don't have enough "power" to subvert the protocol;
- In this context "power" refers to computational power in the case of PoW and Sybil Attacks, or access to backdoors;
- You will trust that the protocol is sound, as well as the implementation of it;
There's plenty of trust going around in there, claiming to "do away with trust" is dishonest at best, and fraudulent at worst. To add insult to injury: PoW based peer networks that haven't achieved significant scale can likely be trivially overtaken by an adversarial actors, and making a system P2P tends to open it up to all kinds of forensic network analysis.
---
For the long version of the argument I'd recommend this post from Bruce Schneier:
https://www.schneier.com/blog/archives/2019/02/blockchain_an...
> Most blockchain enthusiasts have a unnaturally narrow definition of trust. They’re fond of catchphrases like “in code we trust,” “in math we trust,” and “in crypto we trust.” This is trust as verification. But verification isn’t the same as trust.
> What blockchain does is shift some of the trust in people and institutions to trust in technology. You need to trust the cryptography, the protocols, the software, the computers and the network. And you need to trust them absolutely, because they’re often single points of failure.
It could be the case that this protocol is the bee's knees, but seeing this makes me want to immediately write it off as bullshit. "Trustless" is not a thing that exists in real life, or rather, it only exists in the minds of people who fundamentally misunderstand "trust".
https://www.realworldtech.com/forum/?threadid=198497&curpost...
Sorry if it seems like it's just a floating comment, indeed the article made claims of the kind, and I really think the project (and others like it) is nice. My comment is directed towards the practical concerns and real-world feasibility of a ternary computer, especially with regards to comments that threads like this inevitably attract (as seen on this comment section) that "ternary computers would revolutionize X", and is partly fueled by me having had non-fuitful conversations with coworkers that insisted on this point in the past. Hopefully this helps contextualize my comment a bit better.
> That said, I don't understand how you arrived at [point 3b]. One can definitely create a circuit which will perform a ternary operation in a (some) constant time. The real question is: can you make a ternary computer which is somehow better than a binary one?
I think you and I are in agreement here, so let me try to clarify what I meant:
My point is precisely regarding the arbitrariness with which "constant time" is defined. Asymptotic analysis of algorithms always treats complexity in the "time" dimension as a measurement of discrete "ticks" on computational state, meaning: you can pick any encoding of data you want, and any set of operations you want, and have any "operation" execute instantly as a tick. When analysing "ticks", an algorithm might seem extremely efficient, however that might be a non-reifiable performance gain when you translate from ticks to milliseconds.
For example: assume a binary NAND gate takes 1ms to propagate a stable output signal. All other conditions being equal with respect to manufacturing technology, voltage, and other things you mentioned, I don't see how you could perform "more" computation at the same cost. Sure you can implement a ternary gate that runs in "constant time", but would that constant time still be 1ms? If yes, would it take up the same amount of die space? If yes, would it consume the same amount of power and dissipate the same amount of heat? etc
You'll eventually be tickling the Landauer limit [0] for whatever your manufacturing technology is at some point, no matter if you're doing binary or whatevernary logic, but getting "more compute" for free would be cheating thermodynamics. Improving manufacturing technology is, of course, a viable strategy for squeezing "more computation" into the same physical space, but switching bases will not immediately make Moore's law wither away.
A more succinct way of putting what I'm trying to say into words I guess would be that "all other things being equal, the choice of base is arbitrary with regards to computational and representational power"
Hopefully this helps clear things up :)
You might want to read it: https://news.ycombinator.com/item?id=25618303
I'd be interested in hearing a sophisticated counter-argument if anybody has a good one. Here's my take on this:
1. Binary is that smallest base in which we can encode Shannon information, and thus yields to "bits" a more elegant foundation for computation. Choosing any other base sounds like it would be a very arbitrary choice, and to the best of my knowledge, the only other canonical base for computation that inherently makes sense (as in, not arbitrary) aside from the `bit` is the `nat`[0], but since it uses Euler's constant (a transcendental number) it would be (ironically) very unnatural to express "computation" in it.
2. By theorem, all bases are equivalent in power with respect to their capabilities of encoding information and processing/computing said information, and binary logic can be used to bootstrap any other multi-valued logic system desirable (goes for ternary logic and 64-bit integer computation alike). Thus, the decision to make a base-3 falls back pretty much entirely on circuit efficiency ...
3. The claims of computational efficiency, as far as I've been able to observe, are fallaciously constructed by studying their performance characteristics in abstract computer models that are completely detached from computational thermodynamics:
3a. Turing-machines, for example, fail to adequately model real-world constraints due to information locality being one-dimensional (while the real world is 3D). Von-Neumann computers (and other RAM based machine models) are IMO the largest infractor of this — there is no such thing as "RAM" in the real world: you can't access any address space irrespective of locality in O(1), such a computer would violate relativistic physics and thermodynamical constraints, RAM can only exist by making all memory access equally inneficient and mitigating that as much as possible with L3 caches and what not. Semiconductor engineers and chip designers inherently understand this and are aware of die-locality, most computer scientists and software engineers are completely oblivious to this and get to ignore it most of the time [1]
3b. This means that even though anyone can theorize an abstract machine where every discrete "tick" of time will perform a ternary operation in constant time, that doesn't mean such a machine can be efficiently reified if you move it out of the realm of abstraction. We could just as easily theorize a computer that uses base-1T (one trillion), and assume that all "trilliernary" operations execute instantly in discrete ticks of O(1), and voila! We have a computation device that can rival all of Google's data-centers!
3c. In the real world however, there are thermodynamic constraints on how information can "flow" across spacetime, and I have seen absolutely zero evidence that a ternary, trilliernary, or whatevernary logic gate can be constructed without introducing many new voltage levels or other circuit fuckery to counteract this, in a way that wouldn't completely wreck any purported efficiency. It's either that, or we'd implement whatevernary logic using binary gates (which is exactly what 64-bit integer arithmetic already is!)
4. Bottom line and TLDR is this: You can't get more computation[2] for free. Welcome to the real world.
---
[0] https://en.wikipedia.org/wiki/Nat_(unit)
[1] This is especially painful to watch when they are forced to deal with it, and these optimistic-assumptions clash with reality, as evidenced by NUMA bottlenecks wrt RAM/RDMA/GPUs/Disk access, a collective failure of most engineers to understand the CAP theorem or other concepts related to networking, and so on...
[2] And by "computation" I mean it in the thermodynamical, relativistically-physical, information-theoretical kind of way. Physics is a thing we forget about way too often in computer science...
Also, relevant tool for similar applications (albeit not SQL based): https://github.com/cloud-custodian/cloud-custodian