gergo_barany

> You don't have to implicitly supply the "this" parameter to each "object" predicate if you don't want to [...] if you were really interested in that level of syntactic sugar.

Given that the original "feature request" (https://news.ycombinator.com/item?id=42829985) was this:

>>>> There is no concept of "current maze", like in OO you would have with this.maze, or in Haskell you would do with a reader monad. As a result, all the "internal" predicates in a module get full of parameters all they do is pass around until some final predicate uses it to do some calculation.

I would say that yes, the OP wanted exactly that level of syntactic sugar and your previous suggestions [1] and [2] were addressing something else entirely.

> you could insert that yourself via compilation (with term/goal expansion)[4]

Yes, that's why I meant above by "Logtalk-like code generation". Suggesting that I study the thing that I suggested feels a little condescending.

Could you elaborate on all of these?

For [1], you would either need to pass the AVL tree around or to have it as a global (which is not wanted), and instead pass the key (the "this" context which is different for different mazes) for the context around.

For [2] again you have a global table (with copying semantics as for assert/retract? or maybe without copying? the docs don't say). But again you would need to pass a key around.

[3] is... yeah. I mean, sure, you could demonstrate this with a toy metainterpreter on a toy example. But do you really want to run your whole application inside a metainterpreter?

One could also abuse DCG syntax, with the context being some state object instead of a DCG list.

A more practical way would be Logtalk-like code generation. The most practical way would be actual Logtalk. Unfortunately, last I heard Scryer refused to host Logtalk for no real reason.

If this is one of the main things you want to demonstrate, wouldn't it be better to focus on this one goal first, instead of the whole pipeline from a C preprocessor to directly linked executables?

Essentially, if you say that LLVM's mid-end in particular is slow, I would expect you to present a drop-in replacement for LLVM's mid-end opt tool. You could leave C-to-LLVM-bitcode to Clang. You could leave LLVM-bitcode-to-machine-code to llc. Just like opt, take unoptimized LLVM bitcode as input and produce optimized LLVM bitcode as output. You would get a much fairer apples to apples comparison of both code quality and mid-end compiler speed (your website already mentions that you aren't measuring apples-to-apples times), and you would duplicate much less work.

Alternatively, look into existing Sea of Nodes compilers and see if you can build your demonstrator into them. LibFIRM is such a C compiler: https://libfirm.github.io/ There may be others.

It just seems like you are mixing two things: On the one hand, you are making some very concrete technical statements that integrated optimizations are good and the Sea of Nodes is a great way to get there. A credible demonstrator for this would be very welcome and of great interest to the wider compiler community. On the other hand, you are doing a rite-of-passage project of writing a self-hosting C compiler. I don't mean this unkindly, but that part is less interesting for anyone besides yourself.

EDIT: I also wanted to mention that the approach I suggest is exactly how LLVM became well-known and popular. It was not because of Clang; Clang did not even exist for the first eight years or so of LLVM's existence. Instead, LLVM focused on what it wanted to demonstrate: a different approach to mid-end optimizations compared to the state of the art at the time. Parsing C code was not part of that, so LLVM left that to an external component (which happened to be GCC).

Also, for a different notion of "cruft", informally it seems to me like new SSA-based compilers tend to choose an SSA representation with basic block arguments instead of the traditional phi instructions. There are probably reasons for this! I'm not aware of a Sea of Nodes compiler with (some notion corresponding to) block arguments, but it might be fun to explore this when designing a new compiler from the ground up. Might be too late for TB, though.

> a decent linear scan allocator which will eventually be replaced with graph coloring for optimized builds.

Before setting out to implement 1980s-style graph coloring, I would suggest considering SSA-based register allocation instead: https://compilers.cs.uni-saarland.de/projects/ssara/ , I find the slides at https://compilers.cs.uni-saarland.de/projects/ssara/hack_ssa... especially useful.

Graph coloring is a nice model for the register assignment problem. But that's a relatively easy part of overall register allocation. If your coloring fails, you need to decide what to spill and how. Graph coloring does not help you with this, you will end up having to iterate coloring and spilling until convergence, and you may spill too much as a result.

But if your program is in SSA, the special properties of SSA can be used to properly separate these subphases, do a single spilling pass first (still not easy!) and then do a coloring that is guaranteed to succeed.

I haven't looked at LLVM in a while, but 10-15 years ago it used to transform out of SSA form just before register allocation. If I had to guess, I would guess it still does so. Not destroying SSA too early could actually be a significant differentiator to LLVM's "cruft".

What they're "alluding to" is a standard combinator that has existed under the name "paramorphism" for a long time. Here is Jeremy Gibbons's "Origami programming" https://www.cs.ox.ac.uk/jeremy.gibbons/publications/origami.... from 2003:

    [...] capture this modified recursion pattern explicitly as a higher-order operator; in this case, the operator is known as a paramorphism [92]. In the case of lists, we could define
    
    paraL :: (α → (List α, β) → β) → β → List α → β
    paraL f e Nil = e
    paraL f e (Cons x xs) = f x (xs, paraL f e xs)

I don't know of an older source for this particular syntactic presentation, though apparently if you put in the work to translate Squiggol to Haskell, you can read this concrete syntax out of Meijer et al.'s Bananas paper from 1991.

I think what you're criticising is that the name "paramorphism" was adopted from category-theory-on-a-blackboard to functional-programming-that-actually-runs-on-a-computer. That ship sailed 30 years ago; this paper from 2024 is not what caused it to sail. I also think that you're incorrect to criticize this. Analogies are often very helpful.

You are right that the people who pointed you to Meertens's paper were not helpful in clearing up the confusion, since your confusion is exactly that Meertens's paper talks about the other meaning of the term "paramorphism".

> let's drop the charade that everything is above board here.

OK. Since you're opposed to merely alluding to things (your italics, which I find funny), could you please state explicitly the misconduct you are alleging?

The nodes are adjacent in sum1.

The nodes are adjacent in sum2, and sum2 executes more instructions than sum1, and sum2 is faster than sum1.

The nodes are adjacent in sum3, and sum3 executes more instructions than sum1, and sum3 is faster than sum1.

The LLVM project has a tool called llvm-mca that does this. Example: https://gcc.godbolt.org/z/7zcova1ce

The version in the Compiler Explorer wouldn't work on AArch64 without an -mcpu flag and I didn't know what to pass, so I copied -mcpu=cyclone from https://djolertrk.github.io/2021/11/05/optimize-AARCH64-back.... You'd have to look up the correct one for your Mac's CPU.

I see, that's indeed an important distinction. Thanks!

This is similar to my symptoms. So far I haven't found any over the counter painkiller that helps me reliably. At least not in the doses you're supposed to take.

A few years ago I read something about a theory that migraines have to do with the body's heat regulation, and it was suggested to try a hot shower. That does seem to help me. So nowadays when I get a migraine (thankfully only about five times per year or so) I run a hot bath and stay in the tub for two to three hours. It's not fun, and for the first few minutes the headache gets worse and really starts pounding (blood pressure changes due to the heat maybe? I don't know). But then the heat does seem to take a lot of the edge off, and after a while the pain actually stops. Which it doesn't reliably do with painkillers only. Much better than lying around in bed, unable to sleep.

Not medical advice, your mileage will vary. But might be something others would want to try. If you're going to suffer and wait for it to stop, you might as well consider doing that in the bath.

What is "the above"? The context was (https://news.ycombinator.com/item?id=40844208):

    > The one-sided pattern matching seems to be a peculiarity of Elixir.

    And Erlang. And Haskell. And OCaml. And F#. And...

All of these "languages mentioned above" have one-sided pattern matching. This was the claim. Not more, not less. Are you disagreeing with this claim? Are you trying to say something about "one-sided pattern matching"? Or are you trying to say something about something other than "one-sided pattern matching"? You are not being clear.

You're right that you can't override __add__ for numbers, but the bytecode doesn't say this. The bytecode isn't specialized to numbers. It will call the __add__ operation on whatever object you give it. The interpreter will probably have a fast path in its implementation of the BINARY_OP instruction that checks for numbers. But that doesn't mean that the BINARY_OP instruction can only handle numbers.

Example:

    >>> class foo(object):
    ...     def __add__(x, y):
    ...         print(f'"adding" {x} and {y} by returning {y}+1', x, y, y)
    ...         return y + 1
    ... 
    >>> f = foo()
    >>> f + 3
    "adding" <__main__.foo object at 0x725f470c4e90> and 3 by returning 3+1 <__main__.foo object at 0x725f470c4e90> 3 3
    4
    >>> add_five(f)
    "adding" <__main__.foo object at 0x725f470c4e90> and 5 by returning 5+1 <__main__.foo object at 0x725f470c4e90> 5 5
    6

(Not sure why there's extra garbage printed, my Python is a bit rusty.)

> Because Picat is a research language it's a little weird with putting expressions inside structures. If we did $state(1 + 1) it would store it as literally $state(1 + 1), not state(2).

> Also you have to use dollar signs for definitions but no dollar signs for pattern matching inside a function definition. I have no idea why.

I've heard of Picat before but haven't played with it. But from contrasting to Prolog I think I can guess what's going on.

In Prolog, everything is an uninterpreted term. If you want arithmetic "expressions" to be "evaluated", you must explicitly ask for that with the is/2 predicate. Also, there are no "functions" to be "applied". So in Prolog you would write:

    action(state(A, Clipboard), To, Action, Cost) :-
        NewA is A + Clipboard,        % I want the number 2, not the term 1 + 1
        To = state(NewA, Clipboard),  % I want a data structure called state, not to apply a hypothetical "state" function
        Action = ("P", To),
        Cost = 1.

Picat turns these things around. There are expressions, there are functions, and the = operator does evaluate its right-hand side. So now if you write state(NewA, Clipboard) on the RHS of an = operator, the default would be to interpret this as a function call to the "state" function. There is no such function, and if there were, you wouldn't want to call it here. You want a structure called "state". So you mark it as a structure construction rather than a function call.

This has nothing to do with being "a research language", just having to do with having to be explicit about interpreting things as data vs. code. It's the same as quote in Lisp: sometimes you want (f a b) to be a function application, and sometimes you want to build a list containing f, a, and b. In Picat as in Lisp, you need to use a quoting mechanism in the latter case.

What's not the same as what? Based on your examples it looks like you're saying that unification is not the same as pattern matching. But nobody said it was.

> I'd say that "pattern matching" is unification, where there are no free variables on the right side and the left side is the "pattern" to match.

Plus the restriction that the left hand side must be linear, that is, must not contain any variable more than once. So you usually can't write a pattern match like

    match list with
    | [x, y, x] -> ...

but languages with pattern matching usually allow you to add side conditions like this:

    match list with
    | [x, y, x'] if x = x' -> ...

> Now, unification is Turing-complete pattern matching

No. First-order syntactic unification is not Turing complete. The combination of unification and resolution is Turing complete.

> For instance, in Prolog, you can unify a variable with an entire Prolog program and call the program at runtime, etc.

Lots of languages allow you to do this. Lisp had "eval" ten years before Prolog existed. Unification is not necessary for this.

Prolog is great, unification is great. Some other things are great too.

I don't see why it would be. The native image static analysis decides on the level of individual classes, methods, and even class fields what to include in the image and what not. It doesn't compile entire packages or modules into the image, only parts it considers reachable. And the module system shouldn't influence this reachability analysis I think.

WebAssembly fans might say that it's the kind of universal low-level but portable IR that you envision. It would certainly make sense for a Scheme compiler to consider a WebAssembly target.

I was in Paris in March and had a ticket for this. I was at the museum an hour before my booked time slot. The square in front of the entrance was one gigantic queue, and when I asked at the front I was told that they were still processing people who had booked a time slot an hour before that. I decided not to stand around in the rain for two hours for a very dubious chance to get what I had paid for. There are no refunds for any reason ever, of course.

It's a shame because when I lived in Paris the Musée d'Orsay was one of my favorites. Apparently management changed sometime in the last few years, and ticket sales are higher than ever. But only because it has turned into yet another tourist trap.

Unfortunately this doesn't answer the OP's question. OK, it may not result in better code. But in which cases, and for what reason? EDIT: And for that matter, does "not better" mean "neutral" or "actually worse"? To be clear, this is a flaw in the article, not a criticism of your response to the OP.

C has had fixed-size integers since C99: https://en.m.wikibooks.org/wiki/C_Programming/inttypes.h

Targeting LLVM IR has the drawback that it is not platform independent: Details of calling conventions must be modeled in the IR, so the compiler must know what ABI it is targeting and emit the appropriate code. Compiling to C doesn't have this problem, since the C compiler will handle calling conventions for you.

That said, LLVM would indeed have some advantages. Scheme has guaranteed tail call optimization, which you cannot guarantee with C. But LLVM does allow you to annotate calls as tail calls, and it can transform tail self-recursion into a loop for you.

You can build GraalVM native images from modularized code, but you can also build them from non-modularized code.

Yes, the kind of test case reduction that C-Reduce does is analogous to QuickCheck's shrinking. Some of C-Reduce's transformations are purely "on strings", e.g., "delete a physical line from the file", others are a bit more syntax-aware, e.g., "delete N tokens", and some actually build an AST using Clang and do some semantic transformations like "replace function parameter by global variable".

And yes, this is used alongside fuzzing, once a fuzzer (like Csmith from the same group as C-Reduce) has found a file that provokes a bug.

A reducer is not a fuzzer itself, although with some ingenuity it can be made to behave like a fuzzer in certain contexts: https://blog.regehr.org/archives/1284

That Coq proof is not "without computer assistance". No Coq proof is, as Coq is literally an "assistant" that runs on a computer.

And those many jobXtoY.v and taskXtoY.v files sure look like they also do the same as the Appel and Haken proof, namely enumerate lots and lots of cases that are then machine-checked. So I don't think the computerized Coq proof is really qualitatively different from other computerized proofs that enumerate so many cases that a manual check would be impractical.

Forths do have local variables. (Cue debates on what makes a stack-based Forth-like language a "Forth".) Here is the description of Gforth's support for its own extended locals and the Standard Forth locals: https://gforth.org/manual/Locals.html (Cue debates on whether Standard Forth is a Forth and whether it is standard.)

When I learned Forth about 15 years ago, we used the { } syntax described here, not the newer(?) {: :} syntax: https://gforth.org/manual/Local-Variables-Tutorial.html

The main problem with the Pirate Party is that they're perceived by many as a one-issue party.

Here is their actual common EU election program, which includes much more than "just digital rights": https://european-pirateparty.eu/programme/

The use case in the article here is for a single 8-byte (one size_t) popcount at a time. The comparison in your source is for when you want to compute many popcounts in parallel. The smallest size it compares is 32 bytes, where the scalar popcount instruction beats even the fastest other variants by a factor of almost 2x. The AVX2 lookup variant only starts beating it starting at 256 or 512 bytes, depending on the exact CPU. And even then, that variant is not equivalent to (a parallel version of) the scalar code shown in this article.

So, good that the parallel version exists, but it's really apples and oranges compared to this article's problem.

https://cdrdv2-public.intel.com/819723/325462-sdm-vol-1-2abc..., Vol. 2A page 3-598 (physical page 1191): "LEA—Load Effective Address"

https://cdrdv2-public.intel.com/819723/325462-sdm-vol-1-2abc..., Vol. 2B page 4-42, (physical page 1263): "MOV—Move to/from Debug Registers ... At the opcode level, the reg field within the ModR/M byte specifies which of the debug registers is loaded or read. The two bits in the mod field are ignored. The r/m field specifies the general-purpose register loaded or read."

https://www.felixcloutier.com/x86/lea: "LEA — Load Effective Address"

https://www.felixcloutier.com/x86/mov-2: "MOV — Move to/from Debug Registers ... At the opcode level, the reg field within the ModR/M byte specifies which of the debug registers is loaded or read. The two bits in the mod field are ignored. The r/m field specifies the general-purpose register loaded or read."