Excellent! I had been thinking of building something along the same lines when I switched from `zsh` to `fish`, as I had been missing `zsh_stats`. Now I don't have to and can focus on my other side project!
I think one thing that would definitely help the mold project is to have a clearer price and licensing model. The only thing I can find is https://opencollective.com/mold-linker.
It would be much easier to be able to go to my manager with that kind of information. Right now the conversation goes:
"Hey, this linker could save us quite a bit of time on our enormous executable."
"Okay, how much will it cost us?"
"Well, there is this site where you can donate on a regular basis."
If interested in supporting recursion, the SICP tutorial does a great job supporting it! I chose not to include this for the essay, but it's fun to hack. If you end up doing this, here's a reference Clojure implementation:
No, Datalog always has a finite (though potentially exponentially large) grounding, since no rule can introduce new values to the database (i.e., it has no “value invention”/“function terms”/“existential quantification”).
Some form of stratification is usually required when you add Negation (which the demo also doesn't seem to have). But even here it's not because the language would become Turing complete, but rather to ensure that it has a consistent semantics. Consider, e.g., a program with two rules: `A :- not B`, `B :- not A`. Unlike Datalog programs, this does not have a unique minimal model, since both `{A}` and `{B}` are minimal models. Stratification is then a syntactic restriction that prevents such situtations.
For a Datalog program and a specific database, there is always a finite set of facts the program can possibly derive (that is the “finite grounding” from above), obtained in the following way: for every predicate that appears in the “head” of a rule (i.e., any predicate for which facts are potentially derived by the program), instantiate it with all combinations of values that occur in the database or (as constants) in the program (the so-called “active domain”). In general, this will be exponentially many facts (with respect to the size of the program), and polynomially many facts (with respect to the size of the database).
Entailment in Datalog is monotonic in the sense that once a fact has been derived by the program, no further rule application can invalidate this fact (this is no longer true when adding negation, and is indeed what we recover by stratifying).
Taken together, this means that you can always compute all facts derived by a Datalog program on a database by computing the least fixed point under immediate consequences (roughly “apply all rules and add the derived facts”; this approach is called “naive evaluation” in the literature, in practice, more optimised evaluation strategies are useful), and you are guaranteed to obtain this after polynomially many (with respect to the database) or exponentially many (with respect to the program) steps – every step derives at least one fact; once you have reached a state where there are no more immediate consequences, you have derived every fact that you will ever derive and can stop.
Anything involving transitive closure, for example. Say you have a directed graph, encoding an edge from `x` to `y` as `edge(x, y)` (or as a triple `(x, edge, y)`, and you want to find all vertices reachable from `a`. In standard Datalog, you'd have two rules `reachable(x, y) :- edge(x, y)` and `reachable(x, z) :- reachable(x, y), edge(y, z)`, with the second being the recursive rule.
And still folks think that if side loading is forced on Apple, that companies will not force us to start side loading their apps to escape this "apocalypse".
I agree. We only have to look 3 years ago to see exactly what happens when those same companies get sideload access. Facebook did something very similar, using their Apple App Store Developer certificate to enroll users as "employees," allowing them to defacto sideload their market research application.
Those instances show that Facebook is willing to do that to small incentivized groups of users- in that case, volunteers offered monetary benefit via gift cards, but difficult to say such a model is accomplishable on a wide scale. This is a situation where the users were self-selecting.
Certainly, companies will misuse and abuse the freedoms associated with sideloading, but I disagree that it’s as an easy task as people think. First they actually have to build competing app stores that are compelling enough for users to overcome the friction of switching. I don’t think these companies, other than game platforms like Epic, and perhaps tech companies in politically sensitive markets such as China or Russia, have it in them:
I don't understand why you think building alternative app stores is somehow a limiting factor. If you want to use some software, and the company wants to bypass Apple's protections, they'll just put a download link on their website. Why go through the hassle of registering with any "app store" at all?
Because Apple still wields control over iOS, which means they can also curate how the sideloading experience. I don't believe that even if legislation and regulator action forces iOS to permit sideloading, that it necessitates sideloading to be done in as casual a process as it is to download and install software on macOS, Windows, or desktops in general. Apple will still be able to determine how sideloading is done. And they can make the process very guarded, with multiple disclaimer screens and agreement menus that the user must assent to before they are allowed to sideload. Even on Android today, enabling sideloading is a multiple step process:
Furthermore, I believe that Apple can choose to shape the experience even after sideloading is enabled. They can add badge icons that single out sideloaded apps. They can force sideloaded apps to be on specifically marked pages on the springboard. They can add alerts and popovers galore that ask the user "Do you really want to do that?" wrt the sideloaded apps. Apple is a master of UX and branding - if they can influence millions of users via the blue iMessage bubble vs. the green SMS chat bubble dichotomy, they can find a way to subtly single out sideloaded apps as worthy of concern. Emergent user behavior then follows.
Finally, as I have mentioned in the previous link, Apple still controls the operating system that all apps, whether sideloaded or not, exist on. If they wanted to harden its security and strengthen entitlements in such a way that even sideloaded apps cannot bypass certain privacy or security safeguards, they can probably find a way. At they very least, they can introduce a similar notarization process that they already do on macOS on non-Mac App Store apps.
Everyone seems to keep forgetting, there is already an option on iOS for developers not wanting to go through the App Store: web apps. I believe WASM can even be used these days. Except that Safari doesn't offer developers some privacy sensitive APIs other browsers do. The current side loading pressure has very little to do avoiding Apple's cut and everything to do with bypassing Apple's restrictions.
So I expect should Apple introduce a heavily sandboxed side-loading experience, we'd be seeing developers complain they are not adhering to the spirit or the law or lawsuit.
PWAs have long failed to reach adoption on mobile- not just iOS, but also on Android- because of technical limitations that they have compared to native. And perhaps, lack of sufficient interest both from independent developers and from larger tech corporations. That interest is probably orthogonal to the sideloading battle.
Seeing as how Epic was the first company to launch a lawsuit against Apple's control of the App Store, and they certainly care more about avoiding Apple's cut, and little about privacy restrictions, that would seem to contradict your point. We haven't exactly seen Meta or Google throw in with Sweeney's crusade. Instead, the companies who have publicly supported the suit have all been companies that want to bypass the 30% cut, such as Spotify or Tinder.
Finally, if Apple introduces a heavily sandboxed sideloading experience (hopefully they will also introduce more privacy sensitive APIs to Safari as well!), then perhaps the courts will recognize that as a reasonable action and beneficial to consumers and the public interest, and will not press the matter further. There's only so much back and forth this sort of thing can wage on in the public, anyway. Lawsuits are costly in time, in attention, and in fees. If Apple does something in good faith, unlike what they've been doing in response to Dutch legislation (0), then presumably our systems of democracy will appreciate it.
If side-loading or alternate app stores are allowed I fully expect a "Facebook Store" to appear which includes (and mandates) Facebook malware in every app and most mainstream apps eventually moving over to it.
I think if this was a decade ago, when Facebook was younger (newly post-IPO!), hungrier, and had a better reputation with the public, that might have happened.
But nowadays Meta is older and much more disreputable, many of their new products seem to be clones of other things that exist, from Clubhouse to HQ Trivia, and users are far more jaded towards the company.
Not to mention, mobile and tech in general has matured to a state that a brand new app store, at least from a tech giant everyone knows about, coming to iOS isn't as exciting as it used to be. What does another mobile app store offer the average consumer? They barely download as many new apps from the actual official App Store. Having to deal with another platform account, even if expedited through Facebook login would be another friction point for users, another set of confusing permissions to juggle, another payment system to hook up to, another downloads history to keep track. Users are already getting burned out by having to deal with so many video streaming platforms that piracy is making a comeback, why would they be willing to put up with a Facebook Store just to get Instagram? At least signing up for Paramount+ lets you watch the Halo television show, what does signing up to the Facebook Store do besides let you use Facebook- which you already can?
No, I believe that even if Meta really does launch such a store, they would not be willing to pull their official apps away from the actual App Store. They will hedge their bets because it is unlikely that all, or maybe even most, Facebook users will switch to their app store. If forced to have to use a whole new store for no good reason, many consumers will just stop using Facebook, and find substitutes to Instagram instead.
Yes, and they would be angry at the people who make their apps for doing that for no apparent reason, the users who are more tech savvy will recognize that this is a ploy to harvest their data by forcing migration to platforms with fewer privacy restrictions, there will be big public backlashes on social media, people will boycott these new app stores simply because of the hassle, the companies will be forced to reverse their decision and put their apps back onto the App Store, and it would be an expensive waste of time.
One can even imagine that if the app getting moved is sufficiently widely used and utility-like, such as WhatsApp or Messenger, or even Facebook itself, the courts might start antitrust investigation into Meta, and that company would face pressure to keep those apps available on both their own Facebook Store and on the official App Store (where the majority of users are). After all, antitrust provisions apply not only to Apple, but to all companies.
It seems misleading to call this "Datalog". The GitHub repo even says "among database theoreticians Datalog and SQL are known to be equivalent", which is absolutely wrong without qualification. Some flavors of SQL will have recursive extensions so that they could be considered equivalent, but that is not true in general.
I can't find any mention of recursion on the original blog post or the GitHub page. Without recursion it isn't Datalog.
A major difference between Datalog and SQL is that Datalog uses set semantics, whereas SQL uses bag semantics. For those not aware, that means facts in datalog are unique. SQL’s equivalent to facts (records) are not unique, and relations can contain duplicates.
Fair enough, but to a database theoretician SQL means "non-recursive conjunctive queries". And I skimmed the tutorial and there is not a single example of using Logica to compute something recursively. Transitive closure is the canonical example for showing off Datalog.
SQL 99 only requires support for linear recursion, i.e. "each FROM has at most one reference to a recursively-defined relation". Datalog doesn't have such a restriction
I've found that Typed Racket is still fairly hard to use. For example, type classes aren't there, and type polymorphism interacts poorly with general-purpose functions like "equal?". I would guess that ML or Haskell code translates fairly naturally, but there aren't the guide-rails those languages have to keep you in the subset of the language that type-checks well.
when i went through the coursera course "programming languages", i did part a in standard ml (what the course uses) but also in f# and in typed racket (using racket's pattern matching). the code was practically identical across all three languages. now, that's for someone simple programs, but i was surprised that the translation from two MLs was basically trivial to typed racket.
Hackett could really use some people who are excited about the intersection of lisp and haskell and want to build languages to join in on hacking on it :)
I think there are quite a few of those people... maybe that gives some hope for contributions
You are probably underestimating yourself. Imposter syndrome again? Building a language is a major undertaking and I’m sure the help would be appreciated.
I dunno, given https://github.com/lexi-lambda/hackett/issues/98#issuecommen... (saw this when it was sent initially because watching the repo). Knowing one's limits is not necessarily imposter syndrome. If I were to acquire the knowledge (say by reading my recently acquired copy of TAPL), I'll revisit this.
Hackett pushes the boundaries of the Racket macro system, and IIRC through its development has found a number of deficiencies/bugs (I may be misremembering this, however, so don't take it as absolutely true). Besides that, Haskell is a rather complex language, so undertaking the creation of such a thing is no small task. And then we have the issue of
what my own personal knowledge is.
I really hope development once again takes off! Its such a cool project. But I know I wouldn't have the first clue of the right way to do certain things that I know are outstanding.
Probably fifteen years ago I discussed runtime code generation with some computer architects and they did indeed raise concerns about caching at the time. But now I am not as convinced this is as much of a worry as people seem to think. Sure if you were generating new code ever time you opened a file and did a write perhaps you would blow out the instruction cache with excessive amounts of freshly generated code. But if you waited to generate an optimized version of write until you see it is "hot spot" it seems like you would probably be okay.
I can only speculate, so maybe someone who knows better can correct me, but I would be surprised if many kernel syscall implementations would actually stay in cache after a dwq context switches. Especially with recent timing channel mitigations. But I'm just guessing.
And even if there are architectural issues, with processors seeing less benefit from Moore's Law I would expect computer architects to be looking for ways to eek out more performance such that they'd find solutions.
