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.
> 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.
Not sure how tracking references is different here than any other programming language. Passing objects around is pretty common in OO programming. An AVL tree is just the underlying abstraction used to implement the object. You don't have to implicitly supply the "this" parameter to each "object" predicate if you don't want to -- you could insert that yourself via compilation (with term/goal expansion)[4] or interpretation (via meta-interpreters) if you were really interested in that level of syntactic sugar.
> 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.
You could use global or local semantics as desirable. The blackboard has a global version that is persistent across application state or a local version that provides lexical context which unwinds on backtracking. Not sure how "passing a key around" is different than most other forms of programming, but if you wanted to compile it away, please review the techniques listed above.
> [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?
A "toy" meta-interpreter? Meta-interpreters are as fundamental to Prolog as for-loops are to Python. Certain applications, such as games, are run "entirely inside a loop", so I'm not sure how this criticism applies. You can run as much or as little of your application inside a meta-interpreter as you want. The value proposition of Prolog is that the simple homoiconic syntax allows for powerful meta-interpretation. I'd suggest checking out the video I linked to in [3] if you have doubts on that topic.
> One could also abuse DCG syntax, with the context being some state object instead of a DCG list.
State transitions (a sequence of states) are a great use for DCG syntax! I wouldn't call that "abuse".
> A more practical way would be Logtalk-like code generation. The most practical way would be actual Logtalk.
If you are willing to give up the most powerful features of Prolog, sure.
> Unfortunately, last I heard Scryer refused to host Logtalk for no real reason.
> 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.
>>>> 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.
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).
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".
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.
[...] 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 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.
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.
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.
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.