That “imperative escape hatch” is intriguing. I wonder if it’s actually syntactic sugar for a relation, between the old and new state. You could do some magic like update an array “imperatively”, then set its final state, and derive the initial state!
query:
Z = Zinit,
foreach (I in 1..Z.len)
Z[I] := Z[I] * 2
end,
{2, 4} ++ {6, 8} = Z.
expected result:
Zinit = {1,2,3,4}.
This would be kind of like DCGs in Prolog, which are supposed to be for parsing, but can be used to thread any old+new state through a bunch of clauses.
Mostly. If you have a source string S and normalize it with two different unicode versions A and B then the two normalisations will be identical if S contains only codepoints that are assigned in both A and B (with a few very rare exceptions).
It also looks like the address bar doesn’t update as you navigate. I guess you could use the history API like a SPA. I wonder if there’s any other way. Maybe it can use location.hash somehow?
Really cool! I like the right to left evaluation and the sort of currying behavior of parentheses. Using functions for boxing / ragged arrays is clever.
I am wondering how it decides whether to apply a function or push it. For example ‘f x’ applies f, but ‘each f x’ must push f to the stack so ‘each’ can call it? Maybe the evaluation rules for operators/adverbs are special?
I think that’s right: the evaluation rules for operators/adverbs are special. And built-in operators are sometimes parsed differently from user-defined functions. I haven’t actually used it, so someone correct me if I’m wrong.
I like having the function name before the arguments like this:
map (+10) [1,2,3]
add (square 3) (square 4)
In a stack based language, normally you evaluate left to right. But each word is separate, and expects its arguments to be on the stack already. So you put arguments first:
[1 2 3] (+10) each
3 square 4 square add
If you evaluate right to left instead, it looks more like nested expressions, even though it’s actually stack-oriented:
each (+10) [1 2 3]
add square 3 square 4
I would still read these left to right. Maybe I imagine the data sitting inert on the right, and then the functions kind of “attack” it, moving left to right toward the data. I think I also like seeing the root node of the expression first, because it can tell you the high-level structure while the arguments fill in details.
Functions don’t get pushed to the stack unless wrapped in parens. So f x just called f on x. If you wanted to put f on the stack, you would do (f). ! is call. So to put f on the stack and call it on x would be !(f) x.
Edit:
Modifiers are special and will grab a function defined after them in the source. They do not pull from the stack.
This isn’t an aliasing concern, unless you were to access the elements of the underlying array while the objects allocated “inside” it were still live (edit: and then there’s a carve-out to the aliasing rule anyway). There is indeed (also) a carve-out to let objects be allocated inside an unsigned char array providing storage (in C++, but not in C). I agree: the “laundering” isn’t necessary (if the array type in the example is changed to unsigned char).
You do, however, have to use placement new to create the objects in the storage provided by the array. That’s required regardless.
The problem something I’ve discussed with a couple of WG21 members in the past. Some allocators, in particular the .bss allocator (but also memory coming directly from mmap) guarantee that the memory is full of zeroes. But some C++ types (including arrays in structures) will force the object’s constructors to zero the memory. This first bit me when I created a type for a slab in a memory allocator and ended up with a memset that wrote 8 MiB of zeroes into zero-initialised memory (causing every single page to be faulted in as read-write and completely killing performance). There’s no way of avoiding this in C++. The thing that I want is something like a constructor overload that takes a tag type that guarantees that the memory is zeroed, so that allocators that make this guarantee can have simple constructors (the default constructor for many objects will be empty if the space is guaranteed to be zeroed first). If you’re lucky, the compiler will optimise out stores of zeroes if it inlines the constructor. LLVM is pretty good at doing this for globals, but you’re relying on a particular set of optimisations working, not something that’s part of the language.
Note that (as far as I am aware) the only way of actually changing the type of memory in C++ is to do a placement new into it, so this kind of laundering is probably UB.
That surprised me too, but maybe that carve-out is only for things like memcpy, where you view some object using a char pointer. The static array is kind of the opposite situation: it really contains char objects, and you’re trying to view it with some other pointer type.
“If a complete object is created (8.5.2.4) in storage associated with another object e of type “array of N
unsigned char” or of type “array of N std::byte” (21.2.1), that array provides storage for the created
object”
Note that, oddly enough, it has to be unsignedchar (or byte), regular char is not allowed.
Note that, oddly enough, it has to be unsigned char (or byte), regular char is not allowed.
Well, kind of. The char type is equivalent to either signed char or unsigned char, but that choice is implementation defined. This means that regular char might be allowed, depending on the target platform or compiler flags. I’ve seen this lead to some fun performance anomalies when code moved from char-is-signed targets to char-is-unsigned ones and suddenly the compiler became a lot more conservative about aliasing assumptions.
No, in C++ it’s a distinct type. It is either signed or unsigned, but it is not the same type as either signed char or unsigned char. See https://godbolt.org/z/9qM7T5K8b
Huh, interesting. I wonder if that cause strange behaviour in C interop. How does this interact with the promotion rules (is char always equivalent rank to one of the other two)?
I believe char, unsigned char and signed char all have the same rank. None of them will be promoted to any of the other. I’ve never known it to be an issue with C interop but there could be some edge cases I’ve not seen. Even C doesn’t specify (AFAIK) that char is actually the same type as either signed char or unsigned char, but in C I don’t think there’s any context where it matters, unlike C++ which has template specialisation and function overloads and so the distinct third type is visible.
However, reading the linked post again: I think it’s talking about C and not C++ at all (despite the C++ tag on this post). In that case, there’s no such allowance.
I always asked myself, ever since i got introduced to prolog at the early stages of my university module theoretical computer science and abstract datatypes - what would i use prolog for and why would i use it for that?
I know two use cases where prolog is used earnestly, both deprecated these days:
Gerrit Code Review allowed creating new criteria a change must fulfill before it can be submitted. Examples
SPARK, an Ada dialect, used prolog up to SPARK2005 (paper). Out of the formal verification annotations and the Ada code it created prolog facts and rules. With those, certain queries passed if (and only if) the requirements encoded in those annotations were satisfied. They since moved to third party SAT solvers, which allowed them to increase the subset of Ada that could be verified (at the cost of being probabilistic, given that SAT is NP-complete: a true statement might not be verified successfully, but a false statement never passes as true), so prolog is gone.
Datalog, which is essentially a restricted Prolog, has made a bit of a resurgence in program verification. There are some new engines like Soufflé designed specifically by/for that community. Not an example of Prolog per se, but related to your point 2.
A way I’ve been thinking about it is what if my database was more powerful & less boilerplate.
A big one for me is why can’t I extend a table with a view in the same way prolog can share the same name for a fact & a predicate/rule. Querying prolog doesn’t care about if what im querying comes from a fact (table) or a predicate (view).
This in practice i think would enable a lot of apps to move application logic into the database, I think this is a great thing.
move application logic into the database, I think this is a great thing
The industry as a whole disagrees with this vehemently. I’m not sure if you were around for the early days of RDBMS stored procedure hell, but there’s a reason they’re used fairly infrequently.
We actually do stored procedures at work & test them via rspec but it sucks. Versioning them also sucks to deal with. And the language is terrible from most perspectives, i think primarily it sucks going to a LSP-less experience.
I think to me though the root suckiness is trying to put a procedural language side by side a declarative one.
This wasn’t what I was saying with views.
I do think databases could be more debuggable & prolog helps here because you can actually debug your queries with breakpoints and everything. Wish i could do that with sql.
EDIT: but we continue to use stored procedures (and expand on them) because its just so much faster performance-wise than doing it in rails, and I don’t think any server language could compete with doing analysis right where the data lives.
Stored procedures can absolutely be the correct approach for performance critical things (network traversal is sometimes too much), but it also really depends. It’s harder to scale a database horizontally, and every stored procedure eats CPU cycles and RAM on your DB host.
I agree, prolog != SQL and can be really nice which may address many of the issues with traditional RDBMS stored procedures.
I do think databases could be more debuggable & prolog helps here because you can actually debug your queries with breakpoints and everything. Wish i could do that with sql.
Yeah. DBs typically have pretty horrible debugging experiences, sadly.
I feel that that this is a very US-coastal point of view, like one that is common at coastal start-ups and FAANG companies but not as common elsewhere. I agree with it for the most part, but I suspect there are lots of boring enterprise companies, hospitals, and universities, running SQL Server / mostly on Windows or Oracle stacks that use the stored procedure hell pattern. I would venture that most companies that have a job title called “DBA” use this to some extent. In any case I think it’s far from the industry as a whole
Nah, I started my career out at a teleco in the Midwest, this is not a SV-centric opinion, those companies just have shit practices. Stored procedures are fine in moderation and in the right place, but pushing more of your application into the DB is very widely considered an anti-pattern and has been for at least a decade.
To be clear, I’m not saying using stored procedures at all is bad, the issue is implementing stuff that’s really data-centric application logic in your database is not great. To be fair to GP, they were talking about addressing some of the things that make approaching thing that way suck
The industry as a whole disagrees with this vehemently. I’m not sure if you were around for the early days of RDBMS stored procedure hell, but there’s a reason they’re used fairly infrequently.
… in the same way prolog can share the same name for a fact & a predicate/rule. Querying prolog doesn’t care about if what im querying comes from a fact (table) or a predicate (view).
somewhat narrowly.
Sure we do not want stored procs, but
moving Query complexity to a database (whether it is an in-process-embedded database, or external database) is a good thing.
Queries should not be implemented manually using some form of a ‘fluent’ APIs written by hand. This is like writing assembler by hand, when optimizing compilers exists and work correctly.
These kinds of query-by-hand implementations within an app, often lack global optimization opportunities (for both query and data storage).
If these by-hand implementations do include global optimizations for space and time - then they are complex, and require maintenance by specialized engineers (and that increases overall engineering costs, and may make existing system more brittle than needed).
Also, we should be using in-process databases if the data is rather static, and does not need to be distributed to other processes (this is well served by embedding prolog)
Finally, prolog-based query also includes defining ‘fitment tests’ declaratively. Then prolog query responds finding existing data items that ‘fits’ the particular fitment tests. And that’s a very valuable type of query for applications that need to check for ‘existence’ of data satisfying a set of, often complex, criteria.
Databases can also be more difficult to scale horizontally. It can also be more expensive if you’re paying to license the database software (which is relatively common). I once had the brilliant idea to implement an API as an in-process extension to the DB we were using. It was elegant, but the performance was “meh” under load, and scaling was more difficult since the whole DB had to be distributed.
I have a slightly different question: does anybody use prolog for personal computing or scripts? I like learning languages which I can spin up to calculate something or do a 20 line script. Raku, J, and Frink are in this category for me, all as different kinds of “supercalculators”. Are there one-off things that are really easy in Prolog?
I’d say anything that solves “problems” like Sudoku or these logic puzzles I don’t know the name of “Amy lives in the red house, Peter lives next to Grace, Grace is amy’s grandma, the green house is on the left, who killed the mayor?” (OK, I made the last one up).
When I planned my wedding I briefly thought about writing some Prolog to give me a list of who should sit at which table (i.e. here’s a group of 3, a group of 5, a group of 7 and the table sizes are X,Y,Z), but in the end I did it with a piece of paper and bruteforcing by hand.
I think it would work well for class schedules, I remember one teacher at my high school had a huge whiteboard with magnets and rumour was he locked himself in for a week before each school year and crafted the schedules alone :P
The “classical” examples in my Prolog course at uni were mostly genealogy and word stems (this was in computer linguistics), but I’m not sure if that would still make sense 20y later (I had a feeling in this particular course they were a bit behind the time even in the early 00s).
I’d be interested to see a comparison like this. I don’t really know z3, but my impression is that you typically call it as a library from a more general-purpose language like Python. So I imagine you have to be aware of how there are two separate languages: z3 values are different than Python native values, and some operations like if/and/or are inappropriate to use on z3 values because they’re not fully overloadable. (Maybe similar to this style of query builder.)
By contrast, the CLP(Z) solver in Prolog feels very native. You can write some code thinking “this is a function on concrete numbers”, and use all the normal control-flow features like conditionals, or maplist. You’re thinking about numbers, not logic variables. But then it works seamlessly when you ask questions like “for which inputs is the output zero?”.
It’s really good for parsing thanks to backtracking. When you have configuration and need to check constraints on it, logic programming is the right tool. Much of classical AI is searching state spaces, and Prolog is truly excellent for that. Plus Prolog’s predicates are symmetric as opposed to functions, which are one way, so you can run them backwards to generate examples (though SMT solvers are probably a better choice for that today).
That subjectively resembles parser combinator libraries. I guess if you parse with a general-purpose language, even if the structure of your program resembles the structure of your sentences, you give up on getting anything for free; it’s impossible for a machine to say “why” an arbitrary program failed to give the result you wanted.
You can insert cuts to prevent backtracking past a certain point and keep a list of the longest successful parse to get some error information, but getting information about why the parse failed is hard.
I have used it to prototype solutions when writing code for things that don’t do a lot of I/O. I have a bunch of things and I want a bunch of other things but I’m unsure of how to go from one to the other.
In those situations it’s sometimes surprisingly easy to write the intermediary transformations in Prolog and once that works figure out “how it did it” so it can be implemented in another language.
Porting the solution to another language often takes multiple times longer than the initial Prolog implementation – so it is really powerful.
You could use it to define permissions. Imagine you have a web app with all kinds of rules like:
students can see their own grades in all courses
instructors and TAs can see all students’ grades in that course
people can’t grade each other in the same semester (or form grading cycles)
You can write down each rule once as a Prolog rule, and then query it in different ways:
What grades can Alice see?
Who can see Bob’s grade for course 123, Fall 2020?
Like a database, it will use a different execution strategy depending on the query. And also like a database, you can separately create indexes or provide hints, without changing the business logic.
For a real-world example, the Yarn package manager uses Tau Prolog–I think to let package authors define which version combinations are allowed.
When you have an appreciable level of strength with Prolog, you will find it to be a nice language for modeling problems and thinking about potential solutions. Because it lets you express ideas in a very high level, “I don’t really care how you make this happen but just do it” way, you can spend more of your time thinking about the nature of the model.
There are probably other systems that are even better at this (Alloy, for instance) but Prolog has the benefit of being extremely simple. Most of the difficulty with Prolog is in understanding this.
That hasn’t been my experience (I have written a non-trivial amount of Prolog, but not for a long time). Everything I’ve written in Prolog beyond toy examples has required me to understand how SLD derivation works and structure my code (often with red cuts) to ensure that SLD derivation reaches my goal.
This is part of the reason that Z3 is now my go-to tool for the kinds of problems where I used to use Prolog. It will use a bunch of heuristics to find a solution and has a tactics interface that lets my guide its exploration if that fails.
I don’t want to denigrate you, but in my experience, the appearance of red cuts indicates deeper problems with the model.
I’m really curious if you can point me to a largish Prolog codebase that doesn’t use red cuts. I always considered them unavoidable (which is why they’re usually introduced so early in teaching Prolog). Anything that needs a breadth-first traversal, which (in my somewhat limited experience) tends to be most things that aren’t simple data models, requires red cuts.
Unfortunately, I can’t point you to a largish Prolog codebase at all, let alone one that meets certain criteria. However, I would encourage you to follow up on this idea at https://swi-prolog.discourse.group/ since someone there may be able to present a more subtle and informed viewpoint than I can on this subject.
I will point out that the tutorial under discussion, The Power of Prolog, has almost nothing to say about cuts; searching, I only found any mention of red cuts on this page: https://www.metalevel.at/prolog/fun, where Markus is basically arguing against using them.
Because it lets you express ideas in a very high level, “I don’t really care how you make this happen but just do it” way, you can spend more of your time thinking about the nature of the model.
So when does this happen? I’ve tried to learn Prolog a few times and I guess I always managed to pick problems which Prolog’s solver sucks at solving. And figuring out how to trick Prolog’s backtracking into behaving like a better algorithm is beyond me. I think the last attempt involved some silly logic puzzle that was really easy to solve on paper; my Prolog solution took so long to run that I wrote and ran a bruteforce search over the input space in Python in the time, and gave up on the Prolog. I can’t find my code or remember what the puzzle was, annoyingly.
I am skeptical, generally, because in my view the set of search problems that are canonically solved with unguided backtracking is basically just the set of unsolved search problems. But I’d be very happy to see some satisfying examples of Prolog delivering on the “I don’t really care how you make this happen” thing.
How is that strange? It verifies that the bytecode in a function is safe to run and won’t underflow or overflow the stack or do other illegal things.
This was very important for the first use case of Java, namely untrusted applets downloaded and run in a browser. It’s still pretty advanced compared to the way JavaScript is loaded today.
I mean I can’t know from the description that it’s definitely wrong, but it sure sounds weird. Taking it away would obviously be bad, but that just moves the weirdness: why is it necessary? “Give the attacker a bunch of dangerous primitives and then check to make sure they don’t abuse them” seems like a bad idea to me. Sort of the opposite of “parse, don’t verify”.
Presumably JVMs as originally conceived verified the bytecode coming in and then blindly executed it with a VM in C or C++. Do they still work that way? I can see why the verifier would make sense in that world, although I’m still not convinced it’s a good design.
You can download a random class file from the internet and load it dynamically and have it linked together with your existing code. You somehow have to make sure it is actually type safe, and there are also in-method requirements that have to be followed (that also be type safe, plus you can’t just do pop pop pop on an empty stack). It is definitely a good design because if you prove it beforehand, then you don’t have to add runtime checks for these things.
And, depending on what you mean by “do they still work that way”, yeah, there is still byte code verification on class load, though it may be disabled for some part of the standard library by default in an upcoming release, from what I heard. You can also manually disable it if you want, but it is not recommended. But the most often ran code will execute as native machine code, so there the JIT compiler is responsible for outputting correct code.
As for the prolog part, I was wrong, it is only used in the specification, not for the actual implementation.
You can download a random class file from the internet and load it dynamically and have it linked together with your existing code. You somehow have to make sure it is actually type safe, and there are also in-method requirements that have to be followed (that also be type safe, plus you can’t just do pop pop pop on an empty stack). It is definitely a good design because if you prove it beforehand, then you don’t have to add runtime checks for these things.
I think the design problem lies in the requirements you’re taking for granted. I’m not suggesting that just yeeting some untrusted IR into memory and executing it blindly would be a good idea. Rather I think that if that’s a thing you could do, you probably weren’t going to build a secure system. For example, why are we linking code from different trust domains?
Checking untrusted bytecode to see if it has anything nasty in it has the same vibe as checking form inputs to see if they have SQL injection attacks in them. This vibe, to be precise.
…Reading this reply back I feel like I’ve made it sound like a bigger deal than it is. I wouldn’t assume a thing was inherently terrible just because it had a bytecode verifier. I just think it’s a small sign that something may be wrong.
Honestly, I can’t really think of a different way, especially regarding type checking across boundaries. You have a square-shaped hole and you want to be able to plug there squares, but you may have gotten them from any place. There is no going around checking if random thing fits a square, parsing doesn’t apply here.
Also, plain Java byte code can’t do any harm, besides crashing itself, so it is not really the case you point at — a memory-safe JVM interpreter will be memory-safe. The security issue comes from all the capabilities that JVM code can access. If anything, this type checking across boundaries is important to allow interoperability of code, and it is a thoroughly under-appreciated part of the JVM I would say: there is not many platforms that allow linking together binaries type-safely and backwards compatibly (you can extend one and it will still work fine).
Honestly, I can’t really think of a different way, especially regarding type checking across boundaries. You have a square-shaped hole and you want to be able to plug there squares, but you may have gotten them from any place. There is no going around checking if random thing fits a square, parsing doesn’t apply here.
Also, plain Java byte code can’t do any harm, besides crashing itself, so it is not really the case you point at — a memory-safe JVM interpreter will be memory-safe. The security issue comes from all the capabilities that JVM code can access. If anything, this type checking across boundaries is important to allow interoperability of code, and it is a thoroughly under-appreciated part of the JVM I would say: there is not many platforms that allow linking together binaries type-safely and backwards compatibly (you can extend one and it will still work fine).
Well, how is this different from downloading and running JS? In both cases it’s untrusted code and you put measures in place to keep it from doing unsafe things. The JS parser checks for syntax errors; the JVM verifier checks for bytecode errors.
JVMs never “blindly executed” downloaded code. That’s what SecurityManagers are for. The verifier is to ensure the bytecode doesn’t break the interpreter; the security manager prevents the code from calling unsafe APIs. (Dang, I think SecurityManager might be the wrong name. It’s been soooo long since I worked on Apple’s JVM.)
I know there have been plenty of exploits from SecurityManager bugs; I don’t remember any being caused by the bytecode verifier, which is a pretty simple/straightforward theorem prover.
In my experience, it happens when I have built up enough infrastructure around the model that I can express myself declaratively rather than procedurally. Jumping to solving the problem tends to lead to frustration; it’s better to think about different ways of representing the problem and what sorts of queries are enabled or frustrated by those approaches for a while.
Let me stress that I think of it as a tool for thinking about a problem rather than for solving a problem. Once you have a concrete idea of how to solve a problem in mind—and if you are trying to trick it into being more efficient, you are already there—it is usually more convenient to express that in another language. It’s not a tool I use daily. I don’t have brand new problems every day, unfortunately.
Some logic puzzles lend themselves to pure Prolog, but many benefit from CLP or CHR. With logic puzzles specifically, it’s good to look at some example solutions to get the spirit of how to solve them with Prolog. Knowing what to model and what to omit is a bit of an art there. I don’t usually find the best solutions to these things on my own. Also, it takes some time to find the right balance of declarative and procedural thinking when using Prolog.
Separately, being frustrated at Prolog for being weird and gassy was part of the learning experience for me. I suppose there may have been a time and place when learning it was easier than the alternatives. But it is definitely easier to learn Python or any number of modern procedural languages, and the benefit seems to be greater due to wider applicability. I am glad I know Prolog and I am happy to see people learning it. But it’s not the best tool for any job today really—but an interesting and poorly-understood tool nonetheless.
I have an unexplored idea somewhere of using it to drive the logic engine behind an always on “terraform like” controller.
Instead of defining only the state you want, it allows you to define “what actions to do to get there”, rules of what is not allowed as intermediary or final states and even ordering.
Datalog is used for querying some databases (datomic, logica, xtdb). I think the main advantages claimed over SQL are that its simple to learn and write, composable, and some claims about more efficient joins which I’m skeptical about.
I really like the way that Smalltalk handles integers, which (I believe) is adopted from Lisp. Integers are stored with a tag in the low bit (or bits on 64-bit platforms). If they overflow, they are promoted to big integer objects on the heap. If you do arithmetic that overflows the fast path in Smalltalk, then your program gets slower. This doesn’t mean that it can’t lead to security vulnerabilities, but they’re a less serious kind (an attacker can force you to allocate a huge amount of memory, they can’t access arrays out of bounds). It makes me sad that JavaScript, coming over twenty years after the techniques that made this fast were invented, just used doubles.
This is not possible in C because C has to work in situations where heap allocation is impossible. If you write a+b in a signal handler, you may deadlock if the thread that received a signal in the middle of malloc, if addition is allowed to allocate memory to create big integer objects. If you’re using C in a situation where memory allocation is always fine, you’re probably using the wrong language.
I’m pretty sure all Python objects are really pointers with their own object headers. “small” integers (-5 to 256, inclusive) are statically allocated and most ways of getting these values will share them. Most, but not all:
>>> 7 is 6+1
True
>>> 7 is int('7')
True
>>> 7 is int.from_bytes(b'\x07', 'big')
False
but in any case they’re still real objects which reside at real locations in memory. Python does use long arithmetic instead of its base-2**30 big integers when it can, but it doesn’t have any other tricks to avoid allocation, as far as I know.
Accurate, but the parent comment is mainly around underlying implementation rather than the fact that Python does object interning for the sake of efficiency. The interning Python (and some other languages) does has unintended consequences though: I recall spending a whole hour convincing a developer I used to work with that == and is are not interchangeable. I literally had to show you them the C source to show exactly where the interning of small integers was happening before they’d believe me.
Yeah, I went through all that, and that’s what was so frustrating about it. 1 << 10 gets interned because it evaluates to a constant, as you noted. Constants are interned in addition to small numbers, hence why I ended up having to point all this out in the Python source code before I was believed.
It makes me sad that JavaScript, coming over twenty years after the techniques that made this fast were invented, just used doubles.
Wasn’t JS famously developed during a weekend or something … snark aside, it is a bit sad that so many people just accept the limitations of C instead of looking at other solutions.
A basic Scheme interpreter is really easy to implement over a couple of days, especially when you’ve a full runtime to lean on for a bunch of the awkward bits. Converting the original LiveScript over to a C-like syntax probably took longer than the original interpreter.
I wonder if an APL-style interpreter would work here. If you put all the loops inside the primitives, then the interpreter overhead only happens outside the loops, so as the data grows the interpreter overhead should be constant.
If you don’t want an APL-style language, maybe you could have a traditional-looking language as the frontend but translate it to a more batch-oriented language internally. For example Dex uses comprehensions, so you can think one-element-at-a-time. For an even more imperative front-end, maybe you could translate any stateful loop to a foldl.
In imp I explored how much a relational language could be written in a scalar style while still being automatically translated to vectorized style. I could cover most of core SQL but still kept running into functions at the edges that are inherently scalar: custom aggregates, functions on strings/arrays, transitions in state machines etc.
I was imagining an example like:
result = 0
for elem in input:
result += sqrt(elem*2)
which you’d translate as:
foldl (\elem result -> result + sqrt(elem*2)) 0 input
and then break up into primitives:
foldl (+) 0 (map sqrt (map (* 2) input))
I don’t think it will be particularly fast unless you can do some optimising (often inlining).
That makes sense. If you can’t see the function body, you can’t split it up into separate loops.
Maybe you could use a calling convention where all arguments are implicitly lifted to an array. So you write this:
Maybe you could use a calling convention where all arguments are implicitly lifted to an array.
I think you might end up with something a bit like R? In R almost all the functions work over vectors and even “scalar” values are usually just vectors of length 1. It’s pretty fast, but in most implementations it doesn’t usually work well if you have generators (iterables of possibly unknown length that do some work to emit each value).
Custom aggregators (vector kernels) and while loops are kinda awkward and slow in R, too.
I wonder if transducers might be a nice basic building block instead of the broadcasting/vectorisation of R and numpy. Transducers compose very nicely, which might make it possible to compile a transducer pipeline cheaply, and they have good support for iterables of unknown length, early termination, etc.
This also reminds me of Aaron Hsu’s APL compiler in APL: instead of a tree of pointers, there’s a dense array of tree-nodes. The details must be different, and I think the APL compiler used several different kinds of array-encoded trees, maybe because some are smaller and some are better for random access.
One thing that’s mightily annoying in this area is a tension between dense IDs and stable-across-changes IDs.
As in, suppose now the code changes over time, and you want to capture that something refers to logically the same syntax node in the current version,as it was referring to in the previous version. One way to do this is to make sure that the ID of the syntax node stays the same. But if your ID is just position, than that’s not true!
Is that similar to the problem of tracking spans / cursors in a document while it’s being edited? If you insert a blob of text in the middle of a document, the numeric position of all the spans and cursors after that point has to change, to preserve their actual meaningful positions. So maybe a rope or gap buffer of tokens would be useful? Tokens in the unchanged parts don’t have to move.
I’m not sure! I’ve never worked on a text editor or language server.
I actually originally typed a looong comment here, which mentioned gap buffer, but then accidentaly closed the tab and re-entered a short version :)
yes, gap buffer I think could help for cheaply adapting the tokens/parse tree data structure for edints by human — just add some null tokens around the editing.
However, when you create a new gap, some token IDs shift. If you have backlinks from semantics to tokens, that means you now need to treat that semantic info as updated, which might be annoying.
Is “condenser” the opposite of “expander” as in macro-expander? :) Sounds similar to this comment the other day about hiding Go error boilerplate, but this is more for optimization than ease of reading.
It would be nice if you could use some kind of pattern matching like syntax-rules to define these rules.
Oh! which reminds me GHC lets you define rewrite rules, like for deforestation:
Guessing from the process of other JEPs, I believe they would let pattern matching be implemented in a separate tool, they would only fix the interfaces (which is the proper way imo). So someone might write some prolog/xpath-like tool on top of this.
Thanks for the pointer to GHC’s rewrite rules, were not familiar with it!
I don’t think this somehow negates this post’s conclusion in any way but I think claims like these:
Assume 70% of your code base is wrapped in unsafe: That is still 30% of your code base where you do not have to think about memory safety!
are oversimplifying and I wish the Rust community in general were less prone to embracing them. I don’t think it’s inaccurate but it doesn’t tell the story of just how much of a giant, finicky, bug-prone moving piece the safe-unsafe interface is.
A few years ago RUDRA identified a bunch of memory safety bug patterns in unsafe interfaces – straightforward enough that they actually lend themselves to automatic detection. Interfacing unsafe code correctly is extremely difficult, and its role is foundational to the point where a single incorrect interface has repercussions throughout the entire safe codebase (the same paper cites, for instance, a trivial bug in join() for [Borrow<str>]). I’m mentioning RUDRA because it’s easily reproducible, results are widely available and easy to replicate, and it cites several classes of bugs in one place so it’s a good starting point, but those aren’t the only types of bugs in unsafe interfaces.
That 30% isn’t 30% where you don’t have to think about memory safety, it’s 30% where you have to think about the memory safety of unsafe interfaces. If that’s, say, mostly code that manipulates very high-level, well-understood constructs in the standard library that sit several abstraction layers above the first unsafe block, it’s usually a day at the beach. But if that 30% is mostly code that uses the other 70% which you mostly wrote yourself, that 30% of the code probably exposes some of the hardest and most subtle bugs in your codebase.
I’ve heard arguments in terms of “we would have to use tons of unsafe anyway, so Rust would not help us”, too, and my main gripe with them is that they’re often either uselessly generic, organisational artefacts, or both.
First, there are extreme cases where it applies entirely (e.g. you whole program just pokes at some config registers, so it’s basically one giant unsafe block) or not at all (your whole program peeks at some config registers, so your unsafe wrappers are inherently infailible) but most real-life cases are nothing like that, making conclusions about safety drawn based on line counts alone about as useful as conclusions about producftivity drawn based on line counts alone.
And second, depending on what the codebase is, it can have an overwhelmingly positive impact on whatever system it’s integrated in. A device tree manipulation library, for instance, would likely end up with so much unsafe code it’s not even funny, but it would still be enormously helpful because most of the potential for bugs is clustered on the user end of the library, not in the library itself, so being able to integrate primitive manipulation idioms into safe manipulation constructs would matter way, way more than the unsafe block line count would suggest.
I have mixed feelings about RUDRA. On one hand they’ve shown that fully foolproof interfaces around unsafe code are hard. OTOH the majority of the types of unsoundness they’ve identified require evil implementations of traits, like Borrow borrowing a different thing each time. It’s possible in theory, but it’s not a typical code people would write.
The practical rough problem they’ve highlighted is panic safety. This is something that people writing/reviewing unsafe code need to pay extra attention to.
I dunno, I found RUDRA extremely useful back then. I’d just started learning Rust and of the three classes of bugs it proposed, the only one any of the code I’d written didn’t have was the one about Send/Sync propagation, mostly because the kind of code that would exhibit it was way more advanced than I could’ve written at the time. Hell it’s probably way more advanced than what I could write today.
It also highlighted a lot more good points about program correctness in general, not just about memory safety. One of the issues they found, a TOCTOU in join, in addition to being very practical (it’s not just code that people would write, it’s code they did literally write, it was in the standard library) was similar to several similar bugs I found in code of mine. They were probably unexploitable, they were just “plain bugs” that were obvious in hindsight, but I’d missed them during reviews because they were hidden behind macros. Now every time I see a macro in an unsafe block my heart skips a beat.
Some of their variants aren’t very practical but if you look at the bugs they found on the crates.io sample, a good chunk of them are in the oh God BUT WHY??! class. When I read them in isolation I like to think they’re not typical of the code I’d write but realistically they are representative of the bugs I wrote when I was cranky, sleep-deprived, under pressure and unchecked by well-meaning reviewers, which describes a good chunk of our industry, sadly.
FWIW I actually agree entirely with you here. My intent was not to oversimplify, but digging in on these details would have led the post down a very long rabbit hole and I was trying to make it a relatively approachable read, rather than a deeeeeep dive. (I think both are valuable.) And the two parts are really intended to hang together, because:
That 30% isn’t 30% where you don’t have to think about memory safety, it’s 30% where you have to think about the memory safety of unsafe interfaces.
…is exactly what the second half is getting at. That’s 100% true, but iff your safe wrappers do their jobs, that’s where that mental overhead all goes. And you have to put in all the rigor there, because otherwise this is exactly right:
But if that 30% is mostly code that uses the other 70% which you mostly wrote yourself, that 30% of the code probably exposes some of the hardest and most subtle bugs in your codebase.
The key, to my mind, is that that is also true of the other languages on onffer; they just don’t give you any handles for it.
Again, though, I overall agree with this response.
Right, I realise it’s probably impossible to go down that rabbit hole and keep the whole thing approachable. I think the trade-offs are worth it regardless of percentages, too – I actually agree with what you wrote entirely. I apologise if I wrote that in terms that were too adversarial. I’m not trying to challenge your point, just to explore that rabbit hole :-D.
My pet peeve about percentages with this sort of thing is that they tend to hide how hugely variable the difficulty of dealing with unsafe code is inside the very broad field we call “systems programming”. One of the first things I wrote to get the hang of unsafe Rust was a JIT binary translator. That pile of bugs was always like two RETs away from an unsafe block that could panic. The unsafe:safe code ratio was very small but the amount of time (and bugs) I got from interfacing them wasn’t similarly small at all. The interface itself was a very rewarding source of bugs.
No worries; I didn’t mistake you. I just wanted to be clear about what I was doing: it was either 1,200 words or 10,000.😂
I think the example you give there is actually the strongest form of the case for “just use Zig”. I still come down on “I would rather isolate to that interface” even though that interface may be hellish, because at least I know where it is, but you’re right that it doesn’t remotely make it easy.
When I was working on a JVM implementation in Rust, I had to use unsafe for manipulating Java objects on the heap and my biggest gripe was that the memory model of Rust was not well defined in many cases, effectively repeating what I would have had in C/C++’s case with regards to UBs. E.g. it is permissible in Java to data race.
Is there some improvements in this area since? (I haven’t touched Rust in 2 years unfortunately).
With that said, the tooling has greatly improved (for both C and C++, but of course for Rust as well) and with miri/valgrind/etc I could catch most bugs early in my unsafe blocks.
Sounds like an interesting project! How do you represent a Java heap in Rust’s type system? Is it a big array of words, or more structured, like: a Java reference is a Rust pointer; a Java object is a Rust struct, etc? I imagine the former since it’s a VM so the Java classes only exist at runtime.
It’s an array of 64bit words with a header that points to the class of the given object instance. The JVMs design is quite cool and the specification is written in a surprisingly accessible way with many great design decisions (though also with some historical baggage), for example having only single inheritance allows for appending the fields of a subclass to that of its superclass, allowing for subtyping already from the memory structure.
I don’t think so. I think the various initiatives, like the UCG, have made some progress but if anything major has made it to “official” status then I’ve missed it, too.
A device tree manipulation library, for instance, would likely end up with so much unsafe code it’s not even funny
As the author of FreeBSD’s dtc, I think you’ve picked a bad example here. The codebase is written in C++ currently and uses safe types (smart pointers, iterations) everywhere except around the file I/O layer. It needs to handle cross references and so would need to use the RC trait in Rust, which is unsafe internally, but I think that’s the only place where you’d need unsafe.
On the other hand, dtc takes trusted input and processes it, so the benefits from safety are limited to reliability guarantees in the presence of buggy inputs.
It’s a bad example today, you’re right. My “benchmark” for this comparison was, unfortunately, a similar library I wrote a while back, on a platform whose only C++ compiler was partially C++-03 compliant and… not stellar. C++-11 was already around so I had some idiomatic prior art to refer to for safe types but that was about it.
You’ve made me curious. Was your implementation ever released publicly? I wrote ours in 2013 as part of the removal of GPL’d components from the base system (the original dtc is GPL’d, so I wrote a permissively licensed version that was also intended to be usable as a library, though I don’t think anyone has ever embedded it in another project).
The original version had a lot of premature optimisation. It had a custom string class that referenced ranges in the input. I eventually moved it over to using std::string because the small-string optimisation in libc++ meant that this generally didn’t increase memory usage and made it much easier to reason about lifetimes (strings are always copied) and even where it did increase memory usage, it was on the order of KiBs for a large DTS file and no one cared.
No, my implementation was for a proprietary system that was barely more advanced than a fancy bare-metal task scheduler. The device tree compiler was okay. I made the same mistake of using range-referenced strings (in my defense we were pretty RAM-constrained) but it was mostly bump-free.
Device tree manipulation was the nasty part. We got confident and thought it was a good idea to get the few peripherals that were hotpluggable managed via the device tree as well, and have them dynamically inserted in the flattened device tree. There were a few restrictions that seemed to make that problem a lot more tractable than it was (e.g. we knew in advance which nodes in the tree could get new children, the only hotpluggable peripherals were developed in-house, so we didn’t have to reinvent all of the Open Firmware standard) but it was definitely a bad idea. This was all pre-C++-11 code (I think it was around 2012, 2013?), so no native unique_ptr/shared_ptr, no rvalue references and so on.
Leaderboards. Whenever you run a unit test, it records your name and a handful of performance counters (instructions, cache misses), and publishes it. It shows you the worldwide histogram, and how your LOBSTERS-LANG friends did on the same problem.
Two runs appear on the same leaderboard as long as the unit test is the same; the non-test code can be different. The most popular unit tests tend to use (deterministic) property testing, to make it harder to cheat by overfitting.
Greedy macro unexpansion, which automatically compares subsets of AST nodes to refactor them into un-hygienic, gensym containing defmacro style macros. The result is unprecedented expressiveness making it trivial to maintain LOBSTERS-LANG code bases.
Conceptually, this is something I actually really really want. I just can’t carve out the time to design and write it.
I write Go for work and enjoy it’s stripped down nature. But the vertical space bloat and boilerplate enforced by the ecosystem (context.Context, if err != nil) kill me. It’s so hard to see the intent when it’s surrounded by so many mechanics.
I want a macro compressor, entirely separate from the language. It could literally just be a presentation view in my editor. Open a Go file, highlight a block, and then “semantically compress” or “semantically expand” whatever I want.
ctx := context.Background()
manyObjs, err := superFaillible(ctx)
if err != nil {
return err
}
var fullObjs []FullObj
for _, o := range manyObjs {
full, err := inflate(ctx, o)
if err != nil {
return err
}
fullObjs = append(fullObjs, full)
}
No actual thought was put into that syntax, just filler to get the idea across. Realistically it’d be a lisp with some Go specific keywords and structures. It’s not about writing code at that level, it’s about being able to visually scan a file in Go. Since it’s not for writing, the syntax is unencumbered by ergonomics. It should just be immediately clear and unambiguously map to Go.
That reminds me of a feature I’ve seen in a Java IDE, maybe around the time they added lambdas. Lambdas desugar to an inner class with one method, so the IDE would recognize an inner class with one method and display it more like a lambda.
I agree with the need, but not the conclusion. You have a need for an abstraction that allows you to think clearly about the problem. For application-level programming, the programming language is this abstraction, and if it’s not the right level abstraction for the problem then you’re using the wrong tool. You wouldn’t use assembly language for application-level programming, and IMO you shouldn’t use Go either.
I mean…it’s just tooling? You wouldn’t say stop using Python because autocomplete is useful, or that C is inherently bad because someone uses GDB. Just because something has a pain point doesn’t mean it’s terrible.
I’m definitely not a Go fanboy, but for the work projects I’m referring to it really is the right tool for the job. It was chosen for a reason. Besides, not everyone who writes Go gets to tell their employer that they are rewriting their codebase into something they like better. I’d rather those people be equipped w/ tooling to make their day pleasant and their software better :)
All good points. I just feel like the readability of a language is pretty central, and it would be great if such a central aspect didn’t need a separate tool.
Suppose we’ve discovered that (a*2)/2 is equal to (a<<1)/2 and want to add it.
But wait! Once we know that they’re in the same e-class, we can now reason about their arguments being equal.
I think this is getting the right answer for the wrong reason. In this case we do know that (a*2) == (a<<1), but that’s because a rewrite rule told us directly. You want to tell the egraph (a*2) == (a<<1) and let it derive (a*2)/2 == (a<<1)/2, not the other way around. Once you know the arguments are equal, then you know the parent expressions are equal.
For example, if you start with two unrelated expressions 2*0 and x*0, and later learn that they’re equal (both zero), you wouldn’t want to infer that 2 and x are equal.
Ah that’s a good point. I wanted to introduce how equality can propagate throughout the e-graph in that section but I didn’t want to yet discuss applying rewrites directly.
I’m not sure whether I should drop the more compact e-graph where (a*2) == (a<<1)… some prior readers were confused by this translation (perhaps now because of what you’re saying) and we get to it in the next section anyway.
For example, if you start with two unrelated expressions 2*0 and x*0, and later learn that they’re equal (both zero), you wouldn’t want to infer that 2 and x are equal.
Didn’t you hear? A fix was released—all men are socrates now.
I’m pretty sure I read about 2,3 trees in Purely Functional Data Structures by Okasaki but didn’t really get it at the time. Apparently they’re a special case of btrees! (Unless there are two different things called 2,3 trees.)
3 seemed like such an arbitrary number—why is 2 not enough? Why is 4 not necessary? Now I can kind of see that you need enough elements to make each split balanced.
There’s also an interesting throwaway line near the end: apparently red black trees are really a,b trees in disguise!
It’s external, but Postgres has pluggable storage engines so that doesn’t matter all that much. Presumably it would have a chance of ending up in Postgres proper (perhaps in “contrib”) if it’s considered to be generally useful.
Read the comments - it’s an extension but requires patching Postgres core. The medium-term goal is to allow it to be a pure extension in Postgres 17. The goal long-term is to upstream.
Back in the day, MySQL did exactly this. Its own engine did not have foreign keys or transactions. You could use the SQL syntax for it, but it was just ignored.
The same InnoDB which let the user do both foreign keys and transactions. From the user’s perspective, the only difference was you told CREATE TABLE to create
it as an innodb table.
These days i believe innodb is the default for mysql.
Typically the storage engine provides an interface like: open a cursor on this table (or this index), seek to this key, get the next record, close the cursor. It looks a lot more like typed file descriptors than SQL. (Unlike file descriptors it does provide more guarantees about what happens when multiple threads read and write the same table.)
So the query layer needs to decide which tables or indexes to open, and where to seek to, how to check whether this row matches the query. It also decides how to process the data: should this group-by use hashing or sorting? etc.
There are also admin features like access control, or being able to see which commands are running and interrupt them.
Even though the storage engine interface is low level, it hides a lot of complexity. The query layer doesn’t know the structure of a btree (it’s just an ordered, seek-able thing), or that other threads’ edits to a table may need to be hidden or undone.
I have some experience implementing a simple language inside Julia as huge shortcut.
One thing you can do is give parametric types to the AST and then your tree-walking interpreter will compile and execute your code. It was an amazing shortcut to getting speed, GC, runtime safety, etc. For even more shortcut I just left the interface as the AST (you “write” code in a kind of Lispy form within Julia, serializable as JSON) and that meant I got to skip lexing, parsing and type checking.
A slight modification was to use Julia’s metaprogramming capability to transpile to Julia expressions and evaluate that.
In both cases I got exceptionally fast code. The reward to effort ratio was unreal!
It’s cool! Whenever you feel ready! (And if it’s not clear, you don’t have to be ready to release it publicly. It’s totally fine for it to be for yourself.)
Interesting, what did your AST type look like? For example would you distinguish Expr<int> vs Expr<float>, and then the interpreter is like T interp(Expr<T>), so it can return T without any union or boxing?
Does your language have user-defined types? I’m guessing Julia handles that well because it can specialize the interpreter for a new T at runtime.
Yes, the expression type is a part of it - that helps to construct well-typed expressions, though Julia can infer the the output type without needing a box or a big Union type to store it regardless.
For the “tree-walking interpretter” to be compiled statically by Julia, the subexpressions are also part of the type. Let’s say for simplicity your AST had a type of AST node for addition, then you’d have (a + b) + c be a type like Add{Add{Variable{:a, Int64}, Variable{:b}, Int64}, Variable{:c, Int64}}. Obviously the type gets bigger for more complex expressions. (The expression metaprogramming approach I mentioned doesn’t require this, so is a bit easier on the Julia compiler).
user-defined types?
The language is a simple (i.e. total functional) structurally typed language, but it does have a fair few types (collections, algebraic data types, a handful of primitive types). There is no mechanism to introduce nominal types. For what we want to use it for, that’s OK (think the kinds of expressions you’d evaluate in SQL, or even in Excel (the modern flavour, with collections and lambdas and so-on) - the language is part of a larger product).
Do you have generics? If you don’t (Java 5), then I think “just go and write naive type-checker” works. Basically, to compute type of expression, you compute types of subexpressions, and then figure the type of the whole. The code shape here is similar to evaluation.
If you have generics (Java 6), you probably need unification, and that’s where things get trickier, because your type inference is now a two-pass algorithm — a pass over AST gives you a set of equations, and then a separate algorithm solves the equations. I don’t know a good intro here, I would probably look into https://plzoo.andrej.com/language/miniml.html.
Since your language has quotations (lightweight syntax for functions -> pretty much lambda) I think you do need more than a simple bottom-up checker.
For example, if you can write the equivalent of items.map(x => x + 1), then you want to infer the type of the parameter x, based on the type of elements that are in items. One way to look at it is that x => x + 1 has a generic type: function from T to T.
to recognize that functions take the whole stack as their input and output, and
to think of the stack as being made of nested pairs.
For example a stack with an int on top, a string underneath that, and the rest unknown would have type pair<int, pair<string, S>>, where S is an unknown. The nesting lets you leave “the rest of the stack” unknown just like any other unknown type.
dup has a generic type: function<pair<X,S>, pair<X,pair<X,S>>>. X is the unknown type of the element being duplicated, and S the unknown type of the entire rest of the stack. But even though S is unknown, it’s the same S in the input and output, which is how the type checker knows that dup preserves all the stack-elements besides the duplicated one.
That “imperative escape hatch” is intriguing. I wonder if it’s actually syntactic sugar for a relation, between the old and new state. You could do some magic like update an array “imperatively”, then set its final state, and derive the initial state!
query:
expected result:
This would be kind of like DCGs in Prolog, which are supposed to be for parsing, but can be used to thread any old+new state through a bunch of clauses.
But:
So how stable is this normalization? Can I persist a normalized string, then upgrade ICU and trust that it will normalize the same way?
Mostly. If you have a source string S and normalize it with two different unicode versions A and B then the two normalisations will be identical if S contains only codepoints that are assigned in both A and B (with a few very rare exceptions).
See https://lobste.rs/s/bkavdb/unicode_overview#c_z7adlg
No, you should persist the string as it was entered, and normalize at the point of use as required.
Are you sure? I thought the normalization forms to be well-defined and standardized.
With this in mind, I would normalize at ingress because that makes all following code much simpler and removes a huge surface for bugs.
But now I’m curious as to how the normalization forms are inconsistent
It’s safe to store normalized text provided it contains no unassigned codepoints. https://www.unicode.org/faq/normalization.html#15
I don’t know if the usual NF* implementations ensure this: for instance, I can’t see anything in the ICU documentation that explains how it deals with unassigned codepoints. https://unicode-org.github.io/icu-docs/apidoc/released/icu4c/unorm2_8h.html
This is what I’d expect they have to do if they wanted to navigate between pages without an SPA. Bring back framesets?
It also looks like the address bar doesn’t update as you navigate. I guess you could use the history API like a SPA. I wonder if there’s any other way. Maybe it can use
location.hashsomehow?location.hash was how we used to do it so that’s definitely possible.
Really cool! I like the right to left evaluation and the sort of currying behavior of parentheses. Using functions for boxing / ragged arrays is clever.
I am wondering how it decides whether to apply a function or push it. For example ‘f x’ applies f, but ‘each f x’ must push f to the stack so ‘each’ can call it? Maybe the evaluation rules for operators/adverbs are special?
I think that’s right: the evaluation rules for operators/adverbs are special. And built-in operators are sometimes parsed differently from user-defined functions. I haven’t actually used it, so someone correct me if I’m wrong.
I’m learning Uiua a bit but I don’t yet see why right-to-left makes sense. Can you or anyone else share a perspective on that?
I like having the function name before the arguments like this:
In a stack based language, normally you evaluate left to right. But each word is separate, and expects its arguments to be on the stack already. So you put arguments first:
If you evaluate right to left instead, it looks more like nested expressions, even though it’s actually stack-oriented:
I would still read these left to right. Maybe I imagine the data sitting inert on the right, and then the functions kind of “attack” it, moving left to right toward the data. I think I also like seeing the root node of the expression first, because it can tell you the high-level structure while the arguments fill in details.
Functions don’t get pushed to the stack unless wrapped in parens. So
f xjust calledfonx. If you wanted to putfon the stack, you would do(f).!is call. So to putfon the stack and call it onxwould be!(f) x.Edit: Modifiers are special and will grab a function defined after them in the source. They do not pull from the stack.
Why is pointer laundering required here? I thought there was an explicit carve-out to let
charpointers alias anything.This isn’t an aliasing concern, unless you were to access the elements of the underlying array while the objects allocated “inside” it were still live (edit: and then there’s a carve-out to the aliasing rule anyway). There is indeed (also) a carve-out to let objects be allocated inside an
unsigned chararray providing storage (in C++, but not in C). I agree: the “laundering” isn’t necessary (if the array type in the example is changed tounsigned char).You do, however, have to use placement new to create the objects in the storage provided by the array. That’s required regardless.
The problem something I’ve discussed with a couple of WG21 members in the past. Some allocators, in particular the .bss allocator (but also memory coming directly from mmap) guarantee that the memory is full of zeroes. But some C++ types (including arrays in structures) will force the object’s constructors to zero the memory. This first bit me when I created a type for a slab in a memory allocator and ended up with a memset that wrote 8 MiB of zeroes into zero-initialised memory (causing every single page to be faulted in as read-write and completely killing performance). There’s no way of avoiding this in C++. The thing that I want is something like a constructor overload that takes a tag type that guarantees that the memory is zeroed, so that allocators that make this guarantee can have simple constructors (the default constructor for many objects will be empty if the space is guaranteed to be zeroed first). If you’re lucky, the compiler will optimise out stores of zeroes if it inlines the constructor. LLVM is pretty good at doing this for globals, but you’re relying on a particular set of optimisations working, not something that’s part of the language.
Note that (as far as I am aware) the only way of actually changing the type of memory in C++ is to do a placement new into it, so this kind of laundering is probably UB.
That surprised me too, but maybe that carve-out is only for things like memcpy, where you view some object using a char pointer. The static array is kind of the opposite situation: it really contains char objects, and you’re trying to view it with some other pointer type.
[intro.object]
“If a complete object is created (8.5.2.4) in storage associated with another object e of type “array of N unsigned char” or of type “array of N std::byte” (21.2.1), that array provides storage for the created object”
Note that, oddly enough, it has to be unsigned
char(or byte), regularcharis not allowed.Well, kind of. The char type is equivalent to either signed char or unsigned char, but that choice is implementation defined. This means that regular char might be allowed, depending on the target platform or compiler flags. I’ve seen this lead to some fun performance anomalies when code moved from char-is-signed targets to char-is-unsigned ones and suddenly the compiler became a lot more conservative about aliasing assumptions.
No, in C++ it’s a distinct type. It is either signed or unsigned, but it is not the same type as either signed char or unsigned char. See https://godbolt.org/z/9qM7T5K8b
Huh, interesting. I wonder if that cause strange behaviour in C interop. How does this interact with the promotion rules (is char always equivalent rank to one of the other two)?
I believe
char,unsigned charandsigned charall have the same rank. None of them will be promoted to any of the other. I’ve never known it to be an issue with C interop but there could be some edge cases I’ve not seen. Even C doesn’t specify (AFAIK) thatcharis actually the same type as eithersigned charorunsigned char, but in C I don’t think there’s any context where it matters, unlike C++ which has template specialisation and function overloads and so the distinct third type is visible.However, reading the linked post again: I think it’s talking about C and not C++ at all (despite the C++ tag on this post). In that case, there’s no such allowance.
Another reason to state things positively, is that the results make more sense when NaN is involved.
For example:
is wrong if
xis NaN. NaN is outside the number line, so it does not fall within, above, or below this interval.Rather than add separate NaN checks everywhere, phrase it positively:
I always asked myself, ever since i got introduced to prolog at the early stages of my university module theoretical computer science and abstract datatypes - what would i use prolog for and why would i use it for that?
I know two use cases where prolog is used earnestly, both deprecated these days:
Gerrit Code Review allowed creating new criteria a change must fulfill before it can be submitted. Examples
SPARK, an Ada dialect, used prolog up to SPARK2005 (paper). Out of the formal verification annotations and the Ada code it created prolog facts and rules. With those, certain queries passed if (and only if) the requirements encoded in those annotations were satisfied. They since moved to third party SAT solvers, which allowed them to increase the subset of Ada that could be verified (at the cost of being probabilistic, given that SAT is NP-complete: a true statement might not be verified successfully, but a false statement never passes as true), so prolog is gone.
Datalog, which is essentially a restricted Prolog, has made a bit of a resurgence in program verification. There are some new engines like Soufflé designed specifically by/for that community. Not an example of Prolog per se, but related to your point 2.
Yes, Datalog is heavily used for building state-of-the-art static analyzers, see https://arxiv.org/abs/2012.10086.
This is a great comment, I never knew about the Gerrit code review criteria.
A way I’ve been thinking about it is what if my database was more powerful & less boilerplate.
A big one for me is why can’t I extend a table with a view in the same way prolog can share the same name for a fact & a predicate/rule. Querying prolog doesn’t care about if what im querying comes from a fact (table) or a predicate (view).
This in practice i think would enable a lot of apps to move application logic into the database, I think this is a great thing.
The industry as a whole disagrees with this vehemently. I’m not sure if you were around for the early days of RDBMS stored procedure hell, but there’s a reason they’re used fairly infrequently.
What went wrong with them?
It’s nearly impossible to add tests of any kind to a stored procedure is the biggest one, IMO.
We actually do stored procedures at work & test them via rspec but it sucks. Versioning them also sucks to deal with. And the language is terrible from most perspectives, i think primarily it sucks going to a LSP-less experience.
I think to me though the root suckiness is trying to put a procedural language side by side a declarative one.
This wasn’t what I was saying with views.
I do think databases could be more debuggable & prolog helps here because you can actually debug your queries with breakpoints and everything. Wish i could do that with sql.
EDIT: but we continue to use stored procedures (and expand on them) because its just so much faster performance-wise than doing it in rails, and I don’t think any server language could compete with doing analysis right where the data lives.
Stored procedures can absolutely be the correct approach for performance critical things (network traversal is sometimes too much), but it also really depends. It’s harder to scale a database horizontally, and every stored procedure eats CPU cycles and RAM on your DB host.
I agree, prolog != SQL and can be really nice which may address many of the issues with traditional RDBMS stored procedures.
Yeah. DBs typically have pretty horrible debugging experiences, sadly.
I feel that that this is a very US-coastal point of view, like one that is common at coastal start-ups and FAANG companies but not as common elsewhere. I agree with it for the most part, but I suspect there are lots of boring enterprise companies, hospitals, and universities, running SQL Server / mostly on Windows or Oracle stacks that use the stored procedure hell pattern. I would venture that most companies that have a job title called “DBA” use this to some extent. In any case I think it’s far from the industry as a whole
Nah, I started my career out at a teleco in the Midwest, this is not a SV-centric opinion, those companies just have shit practices. Stored procedures are fine in moderation and in the right place, but pushing more of your application into the DB is very widely considered an anti-pattern and has been for at least a decade.
To be clear, I’m not saying using stored procedures at all is bad, the issue is implementing stuff that’s really data-centric application logic in your database is not great. To be fair to GP, they were talking about addressing some of the things that make approaching thing that way suck
@ngp, but I think you are interpreting
somewhat narrowly.
Sure we do not want stored procs, but moving Query complexity to a database (whether it is an in-process-embedded database, or external database) is a good thing.
Queries should not be implemented manually using some form of a ‘fluent’ APIs written by hand. This is like writing assembler by hand, when optimizing compilers exists and work correctly.
These kinds of query-by-hand implementations within an app, often lack global optimization opportunities (for both query and data storage). If these by-hand implementations do include global optimizations for space and time - then they are complex, and require maintenance by specialized engineers (and that increases overall engineering costs, and may make existing system more brittle than needed).
Also, we should be using in-process databases if the data is rather static, and does not need to be distributed to other processes (this is well served by embedding prolog)
Finally, prolog-based query also includes defining ‘fitment tests’ declaratively. Then prolog query responds finding existing data items that ‘fits’ the particular fitment tests. And that’s a very valuable type of query for applications that need to check for ‘existence’ of data satisfying a set of, often complex, criteria.
Databases can also be more difficult to scale horizontally. It can also be more expensive if you’re paying to license the database software (which is relatively common). I once had the brilliant idea to implement an API as an in-process extension to the DB we were using. It was elegant, but the performance was “meh” under load, and scaling was more difficult since the whole DB had to be distributed.
I have a slightly different question: does anybody use prolog for personal computing or scripts? I like learning languages which I can spin up to calculate something or do a 20 line script. Raku, J, and Frink are in this category for me, all as different kinds of “supercalculators”. Are there one-off things that are really easy in Prolog?
I’d say anything that solves “problems” like Sudoku or these logic puzzles I don’t know the name of “Amy lives in the red house, Peter lives next to Grace, Grace is amy’s grandma, the green house is on the left, who killed the mayor?” (OK, I made the last one up).
When I planned my wedding I briefly thought about writing some Prolog to give me a list of who should sit at which table (i.e. here’s a group of 3, a group of 5, a group of 7 and the table sizes are X,Y,Z), but in the end I did it with a piece of paper and bruteforcing by hand.
I think it would work well for class schedules, I remember one teacher at my high school had a huge whiteboard with magnets and rumour was he locked himself in for a week before each school year and crafted the schedules alone :P
The “classical” examples in my Prolog course at uni were mostly genealogy and word stems (this was in computer linguistics), but I’m not sure if that would still make sense 20y later (I had a feeling in this particular course they were a bit behind the time even in the early 00s).
This class of problems has a few different names: https://en.wikipedia.org/wiki/Zebra_Puzzle
Wonder if it would be good for small but intricate scheduling problems, like vacation planning. I’d compare with minizinc and z3.
I’d be interested to see a comparison like this. I don’t really know z3, but my impression is that you typically call it as a library from a more general-purpose language like Python. So I imagine you have to be aware of how there are two separate languages: z3 values are different than Python native values, and some operations like
if/and/orare inappropriate to use on z3 values because they’re not fully overloadable. (Maybe similar to this style of query builder.)By contrast, the CLP(Z) solver in Prolog feels very native. You can write some code thinking “this is a function on concrete numbers”, and use all the normal control-flow features like conditionals, or maplist. You’re thinking about numbers, not logic variables. But then it works seamlessly when you ask questions like “for which inputs is the output zero?”.
It’s really good for parsing thanks to backtracking. When you have configuration and need to check constraints on it, logic programming is the right tool. Much of classical AI is searching state spaces, and Prolog is truly excellent for that. Plus Prolog’s predicates are symmetric as opposed to functions, which are one way, so you can run them backwards to generate examples (though SMT solvers are probably a better choice for that today).
Prolog is both awesome and terrible for parsing.
Awesome: DCGs + backtracking are a killer combo
Terrible: If it fails to parse, you get a “No”, and nothing more. No indication of the row, col, falied token, nothing.
That subjectively resembles parser combinator libraries. I guess if you parse with a general-purpose language, even if the structure of your program resembles the structure of your sentences, you give up on getting anything for free; it’s impossible for a machine to say “why” an arbitrary program failed to give the result you wanted.
You can insert cuts to prevent backtracking past a certain point and keep a list of the longest successful parse to get some error information, but getting information about why the parse failed is hard.
And then your cuts are in the way for using the parser as a generator, thus killing the DCG second use.
I have used it to prototype solutions when writing code for things that don’t do a lot of I/O. I have a bunch of things and I want a bunch of other things but I’m unsure of how to go from one to the other.
In those situations it’s sometimes surprisingly easy to write the intermediary transformations in Prolog and once that works figure out “how it did it” so it can be implemented in another language.
Porting the solution to another language often takes multiple times longer than the initial Prolog implementation – so it is really powerful.
You could use it to define permissions. Imagine you have a web app with all kinds of rules like:
You can write down each rule once as a Prolog rule, and then query it in different ways:
Like a database, it will use a different execution strategy depending on the query. And also like a database, you can separately create indexes or provide hints, without changing the business logic.
For a real-world example, the Yarn package manager uses Tau Prolog–I think to let package authors define which version combinations are allowed.
When you have an appreciable level of strength with Prolog, you will find it to be a nice language for modeling problems and thinking about potential solutions. Because it lets you express ideas in a very high level, “I don’t really care how you make this happen but just do it” way, you can spend more of your time thinking about the nature of the model.
There are probably other systems that are even better at this (Alloy, for instance) but Prolog has the benefit of being extremely simple. Most of the difficulty with Prolog is in understanding this.
That hasn’t been my experience (I have written a non-trivial amount of Prolog, but not for a long time). Everything I’ve written in Prolog beyond toy examples has required me to understand how SLD derivation works and structure my code (often with red cuts) to ensure that SLD derivation reaches my goal.
This is part of the reason that Z3 is now my go-to tool for the kinds of problems where I used to use Prolog. It will use a bunch of heuristics to find a solution and has a tactics interface that lets my guide its exploration if that fails.
I don’t want to denigrate you, but in my experience, the appearance of red cuts indicates deeper problems with the model.
I’m glad you found a tool that works for you in Z3, and I am encouraged by your comment about it to check it out soon. Thank you!
I’m really curious if you can point me to a largish Prolog codebase that doesn’t use red cuts. I always considered them unavoidable (which is why they’re usually introduced so early in teaching Prolog). Anything that needs a breadth-first traversal, which (in my somewhat limited experience) tends to be most things that aren’t simple data models, requires red cuts.
Unfortunately, I can’t point you to a largish Prolog codebase at all, let alone one that meets certain criteria. However, I would encourage you to follow up on this idea at https://swi-prolog.discourse.group/ since someone there may be able to present a more subtle and informed viewpoint than I can on this subject.
I will point out that the tutorial under discussion, The Power of Prolog, has almost nothing to say about cuts; searching, I only found any mention of red cuts on this page: https://www.metalevel.at/prolog/fun, where Markus is basically arguing against using them.
So when does this happen? I’ve tried to learn Prolog a few times and I guess I always managed to pick problems which Prolog’s solver sucks at solving. And figuring out how to trick Prolog’s backtracking into behaving like a better algorithm is beyond me. I think the last attempt involved some silly logic puzzle that was really easy to solve on paper; my Prolog solution took so long to run that I wrote and ran a bruteforce search over the input space in Python in the time, and gave up on the Prolog. I can’t find my code or remember what the puzzle was, annoyingly.
I am skeptical, generally, because in my view the set of search problems that are canonically solved with unguided backtracking is basically just the set of unsolved search problems. But I’d be very happy to see some satisfying examples of Prolog delivering on the “I don’t really care how you make this happen” thing.
As an example, I believe Java’s class loader verifier is written in prolog (even the specification is written in a prolog-ish way).
class loader verifier? What a strange thing to even exist… but thanks, I’ll have a look.
How is that strange? It verifies that the bytecode in a function is safe to run and won’t underflow or overflow the stack or do other illegal things.
This was very important for the first use case of Java, namely untrusted applets downloaded and run in a browser. It’s still pretty advanced compared to the way JavaScript is loaded today.
I mean I can’t know from the description that it’s definitely wrong, but it sure sounds weird. Taking it away would obviously be bad, but that just moves the weirdness: why is it necessary? “Give the attacker a bunch of dangerous primitives and then check to make sure they don’t abuse them” seems like a bad idea to me. Sort of the opposite of “parse, don’t verify”.
Presumably JVMs as originally conceived verified the bytecode coming in and then blindly executed it with a VM in C or C++. Do they still work that way? I can see why the verifier would make sense in that world, although I’m still not convinced it’s a good design.
You can download a random class file from the internet and load it dynamically and have it linked together with your existing code. You somehow have to make sure it is actually type safe, and there are also in-method requirements that have to be followed (that also be type safe, plus you can’t just do pop pop pop on an empty stack). It is definitely a good design because if you prove it beforehand, then you don’t have to add runtime checks for these things.
And, depending on what you mean by “do they still work that way”, yeah, there is still byte code verification on class load, though it may be disabled for some part of the standard library by default in an upcoming release, from what I heard. You can also manually disable it if you want, but it is not recommended. But the most often ran code will execute as native machine code, so there the JIT compiler is responsible for outputting correct code.
As for the prolog part, I was wrong, it is only used in the specification, not for the actual implementation.
I think the design problem lies in the requirements you’re taking for granted. I’m not suggesting that just yeeting some untrusted IR into memory and executing it blindly would be a good idea. Rather I think that if that’s a thing you could do, you probably weren’t going to build a secure system. For example, why are we linking code from different trust domains?
Checking untrusted bytecode to see if it has anything nasty in it has the same vibe as checking form inputs to see if they have SQL injection attacks in them. This vibe, to be precise.
…Reading this reply back I feel like I’ve made it sound like a bigger deal than it is. I wouldn’t assume a thing was inherently terrible just because it had a bytecode verifier. I just think it’s a small sign that something may be wrong.
Honestly, I can’t really think of a different way, especially regarding type checking across boundaries. You have a square-shaped hole and you want to be able to plug there squares, but you may have gotten them from any place. There is no going around checking if random thing fits a square, parsing doesn’t apply here.
Also, plain Java byte code can’t do any harm, besides crashing itself, so it is not really the case you point at — a memory-safe JVM interpreter will be memory-safe. The security issue comes from all the capabilities that JVM code can access. If anything, this type checking across boundaries is important to allow interoperability of code, and it is a thoroughly under-appreciated part of the JVM I would say: there is not many platforms that allow linking together binaries type-safely and backwards compatibly (you can extend one and it will still work fine).
Honestly, I can’t really think of a different way, especially regarding type checking across boundaries. You have a square-shaped hole and you want to be able to plug there squares, but you may have gotten them from any place. There is no going around checking if random thing fits a square, parsing doesn’t apply here.
Also, plain Java byte code can’t do any harm, besides crashing itself, so it is not really the case you point at — a memory-safe JVM interpreter will be memory-safe. The security issue comes from all the capabilities that JVM code can access. If anything, this type checking across boundaries is important to allow interoperability of code, and it is a thoroughly under-appreciated part of the JVM I would say: there is not many platforms that allow linking together binaries type-safely and backwards compatibly (you can extend one and it will still work fine).
Well, how is this different from downloading and running JS? In both cases it’s untrusted code and you put measures in place to keep it from doing unsafe things. The JS parser checks for syntax errors; the JVM verifier checks for bytecode errors.
JVMs never “blindly executed” downloaded code. That’s what SecurityManagers are for. The verifier is to ensure the bytecode doesn’t break the interpreter; the security manager prevents the code from calling unsafe APIs. (Dang, I think SecurityManager might be the wrong name. It’s been soooo long since I worked on Apple’s JVM.)
I know there have been plenty of exploits from SecurityManager bugs; I don’t remember any being caused by the bytecode verifier, which is a pretty simple/straightforward theorem prover.
In my experience, it happens when I have built up enough infrastructure around the model that I can express myself declaratively rather than procedurally. Jumping to solving the problem tends to lead to frustration; it’s better to think about different ways of representing the problem and what sorts of queries are enabled or frustrated by those approaches for a while.
Let me stress that I think of it as a tool for thinking about a problem rather than for solving a problem. Once you have a concrete idea of how to solve a problem in mind—and if you are trying to trick it into being more efficient, you are already there—it is usually more convenient to express that in another language. It’s not a tool I use daily. I don’t have brand new problems every day, unfortunately.
Some logic puzzles lend themselves to pure Prolog, but many benefit from CLP or CHR. With logic puzzles specifically, it’s good to look at some example solutions to get the spirit of how to solve them with Prolog. Knowing what to model and what to omit is a bit of an art there. I don’t usually find the best solutions to these things on my own. Also, it takes some time to find the right balance of declarative and procedural thinking when using Prolog.
Separately, being frustrated at Prolog for being weird and gassy was part of the learning experience for me. I suppose there may have been a time and place when learning it was easier than the alternatives. But it is definitely easier to learn Python or any number of modern procedural languages, and the benefit seems to be greater due to wider applicability. I am glad I know Prolog and I am happy to see people learning it. But it’s not the best tool for any job today really—but an interesting and poorly-understood tool nonetheless.
I have an unexplored idea somewhere of using it to drive the logic engine behind an always on “terraform like” controller.
Instead of defining only the state you want, it allows you to define “what actions to do to get there”, rules of what is not allowed as intermediary or final states and even ordering.
All things that terraform makes hard rn.
Datalog is used for querying some databases (datomic, logica, xtdb). I think the main advantages claimed over SQL are that its simple to learn and write, composable, and some claims about more efficient joins which I’m skeptical about.
https://docs.datomic.com/pro/query/query.html#why-datalog has some justifications of their choice of datalog.
Datomic and XTDB see some real world use as application databases for clojure apps. Idk if anyone uses logica.
I really like the way that Smalltalk handles integers, which (I believe) is adopted from Lisp. Integers are stored with a tag in the low bit (or bits on 64-bit platforms). If they overflow, they are promoted to big integer objects on the heap. If you do arithmetic that overflows the fast path in Smalltalk, then your program gets slower. This doesn’t mean that it can’t lead to security vulnerabilities, but they’re a less serious kind (an attacker can force you to allocate a huge amount of memory, they can’t access arrays out of bounds). It makes me sad that JavaScript, coming over twenty years after the techniques that made this fast were invented, just used doubles.
This is not possible in C because C has to work in situations where heap allocation is impossible. If you write
a+bin a signal handler, you may deadlock if the thread that received a signal in the middle ofmalloc, if addition is allowed to allocate memory to create big integer objects. If you’re using C in a situation where memory allocation is always fine, you’re probably using the wrong language.This is how Python also works.
There was a proposal to add it to Go, but it never went anywhere because it would break existing code. https://github.com/golang/go/issues/19623
I’m pretty sure all Python objects are really pointers with their own object headers. “small” integers (-5 to 256, inclusive) are statically allocated and most ways of getting these values will share them. Most, but not all:
but in any case they’re still real objects which reside at real locations in memory. Python does use long arithmetic instead of its base-2**30 big integers when it can, but it doesn’t have any other tricks to avoid allocation, as far as I know.
Accurate, but the parent comment is mainly around underlying implementation rather than the fact that Python does object interning for the sake of efficiency. The interning Python (and some other languages) does has unintended consequences though: I recall spending a whole hour convincing a developer I used to work with that
==andisare not interchangeable. I literally had to show you them the C source to show exactly where the interning of small integers was happening before they’d believe me.Tricky: I thought using a big enough number would make this obvious:
but this one comes out True…
Ok, so I’ll try even bigger numbers, but I’ll factor out N first:
wat (:
Apparently it’s constant folding, and then sharing the constant:
Yeah, I went through all that, and that’s what was so frustrating about it.
1 << 10gets interned because it evaluates to a constant, as you noted. Constants are interned in addition to small numbers, hence why I ended up having to point all this out in the Python source code before I was believed.Wasn’t JS famously developed during a weekend or something … snark aside, it is a bit sad that so many people just accept the limitations of C instead of looking at other solutions.
From my vague recollections, it was originally meant to be Scheme with Java syntax, so not knowing how Lisp did numbers was a bit surprising.
A basic Scheme interpreter is really easy to implement over a couple of days, especially when you’ve a full runtime to lean on for a bunch of the awkward bits. Converting the original LiveScript over to a C-like syntax probably took longer than the original interpreter.
I wonder if an APL-style interpreter would work here. If you put all the loops inside the primitives, then the interpreter overhead only happens outside the loops, so as the data grows the interpreter overhead should be constant.
If you don’t want an APL-style language, maybe you could have a traditional-looking language as the frontend but translate it to a more batch-oriented language internally. For example Dex uses comprehensions, so you can think one-element-at-a-time. For an even more imperative front-end, maybe you could translate any stateful loop to a foldl.
APL-style is essentially the vectorised style they mention that numpy does (tho obviously an APL language has very different aesthetics).
Translation to
foldlis fine, but I don’t think it will be particularly fast unless you can do some optimising (often inlining).Oh, I missed this part:
I was imagining an example like:
which you’d translate as:
and then break up into primitives:
That makes sense. If you can’t see the function body, you can’t split it up into separate loops.
Maybe you could use a calling convention where all arguments are implicitly lifted to an array. So you write this:
but you really get this:
so that way the body can be vectorized separately from the call site:
This also makes sense. If the final
foldlstage uses an opaque function then how can you avoid doing a separate function call on each element…I think you might end up with something a bit like R? In R almost all the functions work over vectors and even “scalar” values are usually just vectors of length 1. It’s pretty fast, but in most implementations it doesn’t usually work well if you have generators (iterables of possibly unknown length that do some work to emit each value).
Custom aggregators (vector kernels) and
whileloops are kinda awkward and slow in R, too.I wonder if transducers might be a nice basic building block instead of the broadcasting/vectorisation of R and numpy. Transducers compose very nicely, which might make it possible to compile a transducer pipeline cheaply, and they have good support for iterables of unknown length, early termination, etc.
This also reminds me of Aaron Hsu’s APL compiler in APL: instead of a tree of pointers, there’s a dense array of tree-nodes. The details must be different, and I think the APL compiler used several different kinds of array-encoded trees, maybe because some are smaller and some are better for random access.
I think it was this talk: https://www.youtube.com/watch?v=Gsj_7tFtODk
One thing that’s mightily annoying in this area is a tension between dense IDs and stable-across-changes IDs.
As in, suppose now the code changes over time, and you want to capture that something refers to logically the same syntax node in the current version,as it was referring to in the previous version. One way to do this is to make sure that the ID of the syntax node stays the same. But if your ID is just position, than that’s not true!
Is that similar to the problem of tracking spans / cursors in a document while it’s being edited? If you insert a blob of text in the middle of a document, the numeric position of all the spans and cursors after that point has to change, to preserve their actual meaningful positions. So maybe a rope or gap buffer of tokens would be useful? Tokens in the unchanged parts don’t have to move.
I’m not sure! I’ve never worked on a text editor or language server.
I actually originally typed a looong comment here, which mentioned gap buffer, but then accidentaly closed the tab and re-entered a short version :)
yes, gap buffer I think could help for cheaply adapting the tokens/parse tree data structure for edints by human — just add some null tokens around the editing.
However, when you create a new gap, some token IDs shift. If you have backlinks from semantics to tokens, that means you now need to treat that semantic info as updated, which might be annoying.
Is “condenser” the opposite of “expander” as in macro-expander? :) Sounds similar to this comment the other day about hiding Go error boilerplate, but this is more for optimization than ease of reading.
It would be nice if you could use some kind of pattern matching like syntax-rules to define these rules.
Oh! which reminds me GHC lets you define rewrite rules, like for deforestation:
Guessing from the process of other JEPs, I believe they would let pattern matching be implemented in a separate tool, they would only fix the interfaces (which is the proper way imo). So someone might write some prolog/xpath-like tool on top of this.
Thanks for the pointer to GHC’s rewrite rules, were not familiar with it!
I don’t think this somehow negates this post’s conclusion in any way but I think claims like these:
are oversimplifying and I wish the Rust community in general were less prone to embracing them. I don’t think it’s inaccurate but it doesn’t tell the story of just how much of a giant, finicky, bug-prone moving piece the safe-unsafe interface is.
A few years ago RUDRA identified a bunch of memory safety bug patterns in
unsafeinterfaces – straightforward enough that they actually lend themselves to automatic detection. Interfacingunsafecode correctly is extremely difficult, and its role is foundational to the point where a single incorrect interface has repercussions throughout the entire safe codebase (the same paper cites, for instance, a trivial bug injoin() for [Borrow<str>]). I’m mentioning RUDRA because it’s easily reproducible, results are widely available and easy to replicate, and it cites several classes of bugs in one place so it’s a good starting point, but those aren’t the only types of bugs inunsafeinterfaces.That 30% isn’t 30% where you don’t have to think about memory safety, it’s 30% where you have to think about the memory safety of
unsafeinterfaces. If that’s, say, mostly code that manipulates very high-level, well-understood constructs in the standard library that sit several abstraction layers above the firstunsafeblock, it’s usually a day at the beach. But if that 30% is mostly code that uses the other 70% which you mostly wrote yourself, that 30% of the code probably exposes some of the hardest and most subtle bugs in your codebase.I’ve heard arguments in terms of “we would have to use tons of unsafe anyway, so Rust would not help us”, too, and my main gripe with them is that they’re often either uselessly generic, organisational artefacts, or both.
First, there are extreme cases where it applies entirely (e.g. you whole program just pokes at some config registers, so it’s basically one giant
unsafeblock) or not at all (your whole program peeks at some config registers, so yourunsafewrappers are inherently infailible) but most real-life cases are nothing like that, making conclusions about safety drawn based on line counts alone about as useful as conclusions about producftivity drawn based on line counts alone.And second, depending on what the codebase is, it can have an overwhelmingly positive impact on whatever system it’s integrated in. A device tree manipulation library, for instance, would likely end up with so much
unsafecode it’s not even funny, but it would still be enormously helpful because most of the potential for bugs is clustered on the user end of the library, not in the library itself, so being able to integrate primitive manipulation idioms into safe manipulation constructs would matter way, way more than theunsafeblock line count would suggest.I have mixed feelings about RUDRA. On one hand they’ve shown that fully foolproof interfaces around unsafe code are hard. OTOH the majority of the types of unsoundness they’ve identified require evil implementations of traits, like
Borrowborrowing a different thing each time. It’s possible in theory, but it’s not a typical code people would write.The practical rough problem they’ve highlighted is panic safety. This is something that people writing/reviewing unsafe code need to pay extra attention to.
I dunno, I found RUDRA extremely useful back then. I’d just started learning Rust and of the three classes of bugs it proposed, the only one any of the code I’d written didn’t have was the one about Send/Sync propagation, mostly because the kind of code that would exhibit it was way more advanced than I could’ve written at the time. Hell it’s probably way more advanced than what I could write today.
It also highlighted a lot more good points about program correctness in general, not just about memory safety. One of the issues they found, a TOCTOU in
join, in addition to being very practical (it’s not just code that people would write, it’s code they did literally write, it was in the standard library) was similar to several similar bugs I found in code of mine. They were probably unexploitable, they were just “plain bugs” that were obvious in hindsight, but I’d missed them during reviews because they were hidden behind macros. Now every time I see a macro in anunsafeblock my heart skips a beat.Some of their variants aren’t very practical but if you look at the bugs they found on the crates.io sample, a good chunk of them are in the oh God BUT WHY??! class. When I read them in isolation I like to think they’re not typical of the code I’d write but realistically they are representative of the bugs I wrote when I was cranky, sleep-deprived, under pressure and unchecked by well-meaning reviewers, which describes a good chunk of our industry, sadly.
FWIW I actually agree entirely with you here. My intent was not to oversimplify, but digging in on these details would have led the post down a very long rabbit hole and I was trying to make it a relatively approachable read, rather than a deeeeeep dive. (I think both are valuable.) And the two parts are really intended to hang together, because:
…is exactly what the second half is getting at. That’s 100% true, but iff your safe wrappers do their jobs, that’s where that mental overhead all goes. And you have to put in all the rigor there, because otherwise this is exactly right:
The key, to my mind, is that that is also true of the other languages on onffer; they just don’t give you any handles for it.
Again, though, I overall agree with this response.
Right, I realise it’s probably impossible to go down that rabbit hole and keep the whole thing approachable. I think the trade-offs are worth it regardless of percentages, too – I actually agree with what you wrote entirely. I apologise if I wrote that in terms that were too adversarial. I’m not trying to challenge your point, just to explore that rabbit hole :-D.
My pet peeve about percentages with this sort of thing is that they tend to hide how hugely variable the difficulty of dealing with unsafe code is inside the very broad field we call “systems programming”. One of the first things I wrote to get the hang of unsafe Rust was a JIT binary translator. That pile of bugs was always like two
RETs away from anunsafeblock that could panic. The unsafe:safe code ratio was very small but the amount of time (and bugs) I got from interfacing them wasn’t similarly small at all. The interface itself was a very rewarding source of bugs.No worries; I didn’t mistake you. I just wanted to be clear about what I was doing: it was either 1,200 words or 10,000.😂
I think the example you give there is actually the strongest form of the case for “just use Zig”. I still come down on “I would rather isolate to that interface” even though that interface may be hellish, because at least I know where it is, but you’re right that it doesn’t remotely make it easy.
When I was working on a JVM implementation in Rust, I had to use unsafe for manipulating Java objects on the heap and my biggest gripe was that the memory model of Rust was not well defined in many cases, effectively repeating what I would have had in C/C++’s case with regards to UBs. E.g. it is permissible in Java to data race.
Is there some improvements in this area since? (I haven’t touched Rust in 2 years unfortunately).
With that said, the tooling has greatly improved (for both C and C++, but of course for Rust as well) and with miri/valgrind/etc I could catch most bugs early in my unsafe blocks.
Sounds like an interesting project! How do you represent a Java heap in Rust’s type system? Is it a big array of words, or more structured, like: a Java reference is a Rust pointer; a Java object is a Rust struct, etc? I imagine the former since it’s a VM so the Java classes only exist at runtime.
It’s an array of 64bit words with a header that points to the class of the given object instance. The JVMs design is quite cool and the specification is written in a surprisingly accessible way with many great design decisions (though also with some historical baggage), for example having only single inheritance allows for appending the fields of a subclass to that of its superclass, allowing for subtyping already from the memory structure.
I don’t think so. I think the various initiatives, like the UCG, have made some progress but if anything major has made it to “official” status then I’ve missed it, too.
As the author of FreeBSD’s dtc, I think you’ve picked a bad example here. The codebase is written in C++ currently and uses safe types (smart pointers, iterations) everywhere except around the file I/O layer. It needs to handle cross references and so would need to use the RC trait in Rust, which is unsafe internally, but I think that’s the only place where you’d need unsafe.
On the other hand, dtc takes trusted input and processes it, so the benefits from safety are limited to reliability guarantees in the presence of buggy inputs.
It’s a bad example today, you’re right. My “benchmark” for this comparison was, unfortunately, a similar library I wrote a while back, on a platform whose only C++ compiler was partially C++-03 compliant and… not stellar. C++-11 was already around so I had some idiomatic prior art to refer to for safe types but that was about it.
You’ve made me curious. Was your implementation ever released publicly? I wrote ours in 2013 as part of the removal of GPL’d components from the base system (the original dtc is GPL’d, so I wrote a permissively licensed version that was also intended to be usable as a library, though I don’t think anyone has ever embedded it in another project).
The original version had a lot of premature optimisation. It had a custom string class that referenced ranges in the input. I eventually moved it over to using std::string because the small-string optimisation in libc++ meant that this generally didn’t increase memory usage and made it much easier to reason about lifetimes (strings are always copied) and even where it did increase memory usage, it was on the order of KiBs for a large DTS file and no one cared.
No, my implementation was for a proprietary system that was barely more advanced than a fancy bare-metal task scheduler. The device tree compiler was okay. I made the same mistake of using range-referenced strings (in my defense we were pretty RAM-constrained) but it was mostly bump-free.
Device tree manipulation was the nasty part. We got confident and thought it was a good idea to get the few peripherals that were hotpluggable managed via the device tree as well, and have them dynamically inserted in the flattened device tree. There were a few restrictions that seemed to make that problem a lot more tractable than it was (e.g. we knew in advance which nodes in the tree could get new children, the only hotpluggable peripherals were developed in-house, so we didn’t have to reinvent all of the Open Firmware standard) but it was definitely a bad idea. This was all pre-C++-11 code (I think it was around 2012, 2013?), so no native
unique_ptr/shared_ptr, no rvalue references and so on.Leaderboards. Whenever you run a unit test, it records your name and a handful of performance counters (instructions, cache misses), and publishes it. It shows you the worldwide histogram, and how your LOBSTERS-LANG friends did on the same problem.
Two runs appear on the same leaderboard as long as the unit test is the same; the non-test code can be different. The most popular unit tests tend to use (deterministic) property testing, to make it harder to cheat by overfitting.
Greedy macro unexpansion, which automatically compares subsets of AST nodes to refactor them into un-hygienic, gensym containing defmacro style macros. The result is unprecedented expressiveness making it trivial to maintain LOBSTERS-LANG code bases.
Conceptually, this is something I actually really really want. I just can’t carve out the time to design and write it.
I write Go for work and enjoy it’s stripped down nature. But the vertical space bloat and boilerplate enforced by the ecosystem (context.Context, if err != nil) kill me. It’s so hard to see the intent when it’s surrounded by so many mechanics.
I want a macro compressor, entirely separate from the language. It could literally just be a presentation view in my editor. Open a Go file, highlight a block, and then “semantically compress” or “semantically expand” whatever I want.
becomes something closer to
No actual thought was put into that syntax, just filler to get the idea across. Realistically it’d be a lisp with some Go specific keywords and structures. It’s not about writing code at that level, it’s about being able to visually scan a file in Go. Since it’s not for writing, the syntax is unencumbered by ergonomics. It should just be immediately clear and unambiguously map to Go.
That reminds me of a feature I’ve seen in a Java IDE, maybe around the time they added lambdas. Lambdas desugar to an inner class with one method, so the IDE would recognize an inner class with one method and display it more like a lambda.
Something like this:
vs
I agree with the need, but not the conclusion. You have a need for an abstraction that allows you to think clearly about the problem. For application-level programming, the programming language is this abstraction, and if it’s not the right level abstraction for the problem then you’re using the wrong tool. You wouldn’t use assembly language for application-level programming, and IMO you shouldn’t use Go either.
I mean…it’s just tooling? You wouldn’t say stop using Python because autocomplete is useful, or that C is inherently bad because someone uses GDB. Just because something has a pain point doesn’t mean it’s terrible.
I’m definitely not a Go fanboy, but for the work projects I’m referring to it really is the right tool for the job. It was chosen for a reason. Besides, not everyone who writes Go gets to tell their employer that they are rewriting their codebase into something they like better. I’d rather those people be equipped w/ tooling to make their day pleasant and their software better :)
All good points. I just feel like the readability of a language is pretty central, and it would be great if such a central aspect didn’t need a separate tool.
Really nice explanation and visuals!
There is one part I want to quibble with:
I think this is getting the right answer for the wrong reason. In this case we do know that
(a*2)==(a<<1), but that’s because a rewrite rule told us directly. You want to tell the egraph(a*2)==(a<<1)and let it derive(a*2)/2==(a<<1)/2, not the other way around. Once you know the arguments are equal, then you know the parent expressions are equal.For example, if you start with two unrelated expressions
2*0andx*0, and later learn that they’re equal (both zero), you wouldn’t want to infer that2andxare equal.Ah that’s a good point. I wanted to introduce how equality can propagate throughout the e-graph in that section but I didn’t want to yet discuss applying rewrites directly.
I’m not sure whether I should drop the more compact e-graph where
(a*2) == (a<<1)… some prior readers were confused by this translation (perhaps now because of what you’re saying) and we get to it in the next section anyway.Edit: Thanks. Fixed in an update to the post.
Didn’t you hear? A fix was released—all men are socrates now.
I’m pretty sure I read about 2,3 trees in Purely Functional Data Structures by Okasaki but didn’t really get it at the time. Apparently they’re a special case of btrees! (Unless there are two different things called 2,3 trees.)
3 seemed like such an arbitrary number—why is 2 not enough? Why is 4 not necessary? Now I can kind of see that you need enough elements to make each split balanced.
There’s also an interesting throwaway line near the end: apparently red black trees are really a,b trees in disguise!
I also found this Functional Pearls: On Constructing 2-3 Trees but haven’t read it yet. It mentions Okasaki right in the beginning and the diagrams look just like this video.
It’s not clear from the article, is this an external project or part of PostgreSQL? If it’s external, do it’s authors intend to upstream it?
It’s external, but Postgres has pluggable storage engines so that doesn’t matter all that much. Presumably it would have a chance of ending up in Postgres proper (perhaps in “contrib”) if it’s considered to be generally useful.
Read the comments - it’s an extension but requires patching Postgres core. The medium-term goal is to allow it to be a pure extension in Postgres 17. The goal long-term is to upstream.
What does a pluggable storage engine mean? What other parts of the DBMS are there? Sincere question.
The wire protocol, connection management, query planning/execution, the language, &c.
Back in the day, MySQL did exactly this. Its own engine did not have foreign keys or transactions. You could use the SQL syntax for it, but it was just ignored.
The same InnoDB which let the user do both foreign keys and transactions. From the user’s perspective, the only difference was you told CREATE TABLE to create it as an innodb table.
These days i believe innodb is the default for mysql.
Query planning, execution, session management…
Typically the storage engine provides an interface like: open a cursor on this table (or this index), seek to this key, get the next record, close the cursor. It looks a lot more like typed file descriptors than SQL. (Unlike file descriptors it does provide more guarantees about what happens when multiple threads read and write the same table.)
So the query layer needs to decide which tables or indexes to open, and where to seek to, how to check whether this row matches the query. It also decides how to process the data: should this group-by use hashing or sorting? etc.
There are also admin features like access control, or being able to see which commands are running and interrupt them.
Even though the storage engine interface is low level, it hides a lot of complexity. The query layer doesn’t know the structure of a btree (it’s just an ordered, seek-able thing), or that other threads’ edits to a table may need to be hidden or undone.
I have some experience implementing a simple language inside Julia as huge shortcut.
One thing you can do is give parametric types to the AST and then your tree-walking interpreter will compile and execute your code. It was an amazing shortcut to getting speed, GC, runtime safety, etc. For even more shortcut I just left the interface as the AST (you “write” code in a kind of Lispy form within Julia, serializable as JSON) and that meant I got to skip lexing, parsing and type checking.
A slight modification was to use Julia’s metaprogramming capability to transpile to Julia expressions and evaluate that.
In both cases I got exceptionally fast code. The reward to effort ratio was unreal!
Is the code open source? It would be interesting to take a look at it.
Sorry, sadly it is not. I’d like to talk/blog about it one day though.
It’s cool! Whenever you feel ready! (And if it’s not clear, you don’t have to be ready to release it publicly. It’s totally fine for it to be for yourself.)
This is basically why Lisps are so great for writing languages too. :D
Interesting, what did your AST type look like? For example would you distinguish
Expr<int>vsExpr<float>, and then the interpreter is likeT interp(Expr<T>), so it can return T without any union or boxing?Does your language have user-defined types? I’m guessing Julia handles that well because it can specialize the interpreter for a new T at runtime.
Yes, the expression type is a part of it - that helps to construct well-typed expressions, though Julia can infer the the output type without needing a box or a big
Uniontype to store it regardless.For the “tree-walking interpretter” to be compiled statically by Julia, the subexpressions are also part of the type. Let’s say for simplicity your AST had a type of AST node for addition, then you’d have
(a + b) + cbe a type likeAdd{Add{Variable{:a, Int64}, Variable{:b}, Int64}, Variable{:c, Int64}}. Obviously the type gets bigger for more complex expressions. (The expression metaprogramming approach I mentioned doesn’t require this, so is a bit easier on the Julia compiler).The language is a simple (i.e. total functional) structurally typed language, but it does have a fair few types (collections, algebraic data types, a handful of primitive types). There is no mechanism to introduce nominal types. For what we want to use it for, that’s OK (think the kinds of expressions you’d evaluate in SQL, or even in Excel (the modern flavour, with collections and lambdas and so-on) - the language is part of a larger product).
Do you have generics? If you don’t (Java 5), then I think “just go and write naive type-checker” works. Basically, to compute type of expression, you compute types of subexpressions, and then figure the type of the whole. The code shape here is similar to evaluation.
If you have generics (Java 6), you probably need unification, and that’s where things get trickier, because your type inference is now a two-pass algorithm — a pass over AST gives you a set of equations, and then a separate algorithm solves the equations. I don’t know a good intro here, I would probably look into https://plzoo.andrej.com/language/miniml.html.
Since your language has quotations (lightweight syntax for functions -> pretty much lambda) I think you do need more than a simple bottom-up checker.
For example, if you can write the equivalent of
items.map(x => x + 1), then you want to infer the type of the parameterx, based on the type of elements that are initems. One way to look at it is thatx => x + 1has a generic type: function from T to T.I feel like I’ve seen a talk about this, probably for Cat. Aha it’s mentioned on the README: https://github.com/cdiggins/cat-language#the-syntax-of-types). (EDIT: This was the talk I was thinking of, for a different language called Kitten: https://www.youtube.com/watch?v=_IgqJr8jG8M.)
I think the important part is:
For example a stack with an int on top, a string underneath that, and the rest unknown would have type
pair<int, pair<string, S>>, whereSis an unknown. The nesting lets you leave “the rest of the stack” unknown just like any other unknown type.duphas a generic type:function<pair<X,S>, pair<X,pair<X,S>>>.Xis the unknown type of the element being duplicated, andSthe unknown type of the entire rest of the stack. But even thoughSis unknown, it’s the sameSin the input and output, which is how the type checker knows thatduppreserves all the stack-elements besides the duplicated one.I guess in the context of stack-based languages, looking at WASM spec might be useful:
https://webassembly.github.io/spec/core/valid/instructions.html
In particular, I think call-to-lambda would roughly correspond to call_indirect?
https://webassembly.github.io/spec/core/valid/instructions.html#xref-syntax-instructions-syntax-instr-control-mathsf-call-indirect-x-y
and https://binji.github.io/posts/webassembly-type-checking/ seems a reasonable prose description of the spec.