The most complete language/ecosystem that really showcases Racket's capabilities is Rosette IMO: https://github.com/emina/rosette/
Anarki, a divergent open source fork, can be found here[1].
For example, the "numerical definition" DSL within Elixir's Nx library (https://github.com/elixir-nx/nx/tree/main/nx#numerical-defin...).
Users using this "full" DSL are still using the host language — they're invoking its compiler/runtime and so forth — but they don't necessarily need to care about that. They can still technically access the power of a full-blown programming language, "tucked in" around the edges of the DSL — but you as the DSL's creator, don't have to document that power as being available. As long as users of the DSL can do everything they need to do without any need for "breaking out" of the DSL's little world, they don't need to be aware that they could e.g. make fully-namespaced calls to regular stdlib functions of your runtime.
It's kind of like those people who cobble together a Turing complete implementation of HTML+CSS or Magic: the Gathering game. You can kind of stumble into completeness.
"most of the time" is THE problem here. Once users approach a barrier (missing language feature) they will complain and push you until you implement that feature. After several such features some developer in basement of your building will say "ok, fine, I'll do it" and now you accidentally have a compiler.
Edit: I know because I've recently made a "almost universal data watcher" which can react to combination of measured values changed in different devices and execute actions. Simple solution, but I fear the day when someone needs to execute other recipes in response to data and creates loops.
[1] https://ericlippert.com/2015/04/27/wizards-and-warriors-part...
[2] https://ericlippert.com/2015/05/11/wizards-and-warriors-part...
The abstraction he offered, of having a tree and then visiting every node in that tree, made the most sense.
> One of the most common usages of this pattern is for the scenario where you’ve got a complex tree where tree nodes can be of many types, and you wish to traverse the tree — that is, visit every node in the tree — taking some actions or performing some computations as you go. The “double dispatch” part of it is that the actions you take as you visit nodes in the tree can depend on the runtime types of both the nodes in the tree, and the code performing the action.
That sounds like a parser. It accepts an AST and evaluates productions on its way through. Saying "actions you take ... depend on the runtime types of ... nodes ... and the code performing the action" sounds similar to sorting out how to mash tree-traversal and productions together.
In my compilers class we first wrote a code linter for our "Wombo" language (a simplified Java). Then we wrote something that built an AST. The core tree traversal code was the same, but the "productions" paired with nodes were different.
A DSL is a language with only a handful of users, each of which is usually in the normal path of employment (obvious exception: Chuck Moore). As soon as someone in a team that relies on a DSL leaves the loss of knowledge is immediate. Unlike any other language that you may have picked up in some other organization the DSL has instantly lost a sizeable fraction of those versed in it. It doesn't take many losses like to kill such a project.
Another problem is that even if the original authors hang around, the chances that they will stay fluent in their own DSL diminishes with increasing intervals between work on a particular project. If the code would be written in a 'normal' language then they would stay fluent.
So DSLs are not a good match for how we normally think about software, even though there is a 1:1 correspondence between the words in your typical DSL (say a FORTH word) and a function call. Functions tend to be written in terms of other functions, just like FORTH words are written in terms of other words, and yet, the standard library is never far away whereas with FORTH words it could easily be 30 words down before you hit the actual language.
I'd love to see something like a DSL based language but with longer term prospects, for a long time I hoped that Smalltalk would be that language but I have mostly given up on that.
Forth does less compile-time checking than any other language I could name. It doesn't have a type system of any sort, not even a dynamic one. This makes it very flexible, but ties its hands when it comes to easy/automatic correctness-checking of DSLs. You'd need to implement your own checker.
There are also valid criticisms of Forth's stack-oriented nature regarding readability and maintainability:
1 2 3 INITIALIZE REPEL_VOGONS FINISH
(For context, I rather like Forth as an interesting and very unusual kind of language, but I don't think it's the future of mainstream software development.)
> the standard library is never far away whereas with FORTH words it could easily be 30 words down before you hit the actual language
Forth famously encourages writing short words, but 30 still sounds extremely deep.
With a threaded-code interpreter, yes, Forth's overhead is considerable, but with a native-code Forth compiler, performance is generally only slightly worse than C.
This is presumably because modern optimising C compilers are incredibly sophisticated, whereas modern Forth engines tend to be essentially one-man projects, even the commercial ones.
I've built a couple of projects both in C and Forth, the latter usually to prototype and once I had a good understanding of the problem space the final version in C. Typically the C version outperformed the Forth version by 3:1 or better, and I would not have known how to bridge that gap.
Well written C is quite performant and Forth's overhead (which is relatively small, but it is there) translates into Forth's threaded interpreter executing a JMP instruction at least once per Forth word and that alone is probably enough to explain a good chunk of that gap. FWIW, my experience with Forth is limited to one implementation and a whole bunch of applications (after being introduced to the language by a veritable Forth wizard in 1985 or so, Hi, LS). Even the code of experienced Forth programmers was no match for my then 6 year old experience with C. Nowadays with far larger caches Forth might do better, I haven't really worked with it for years.
> Typically the C version outperformed the Forth version by 3:1 or better, and I would not have known how to bridge that gap.
With a threaded-code Forth interpreter I'd expect the C version to outperform it by something closer to 5:1, so 3:1 doesn't sound too bad. The only way you can close the gap is with good quality native-code compilation.
> Nowadays with far larger caches Forth might do better, I haven't really worked with it for years.
It's interesting how advances in CPU architecture change the relative performance of the different threading strategies. This has been nicely studied by the gforth folks. [0][1] Threaded-code interpreters still easily lose to optimising native-code compilers though, [2] and I expect they always will.
More on how Forth collides with low-level CPU matters: [3][4][5]
[0] https://www.complang.tuwien.ac.at/forth/threading/
[1] https://www.complang.tuwien.ac.at/forth/threaded-code.html
[2] https://github.com/ForthHub/discussion/issues/88#issuecommen...
[3] The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures - https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12...
[4] Branch Prediction and the Performance of Interpreters - Don't Trust Folklore https://hal.inria.fr/hal-01100647/document
[5] Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters - https://www.scss.tcd.ie/David.Gregg/papers/toplas05.pdf
sentence --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb, noun_phrase.
det --> [the].
det --> [a].
noun --> [cat].
noun --> [bat].
verb --> [eats].
I discovered DCGs at the end of my CS degree when I was working on my graduation project, a Magic: the Gathering expert system written in Prolog. I needed a way to script cards for my rules engine, to translate expressions in the M:tG ability text language to function calls in the engine. I really wanted to write a parser using the standard parser generator tools, but I thought it would be too much work for a graduate project. Then I found out about DCGs. With DCGs I could write grammar rules like this:
tap(X,Y) --> (['Tap'];[tap]), target(X,Y), (condition ; []), {permanent_Type(Y)}.
tap(X,Y) --> (['Tap'];[tap]), all(X,Y), (condition ; []).
[Edit: to be clear, the grammar rules above are already, by themselves, a parser for abilities that start with "tap". The Prolog interpreter executes those grammar rules as a program and instantiates their variables in the process. To integrate them with the engine all I had to do was write engine functions that called the nonterminals in the grammar and read the values of variables like X and Y in tap(X,Y).]
Admittedly, my grammar was limited because I didn't have the time to hand-code a grammar for the entirety of M:tG ability text, as it was at the time (I graduated 2011). In any case my rules engine was also limited (I had no planeswalkers and static effects were only partially implemented, if I remember correctly; because the rules for static effects are a bit arcane). But I managed to cover a good subset of the rules and cards, so it was possible to play a basic game with creatures with activated and triggered abilities and with non-creature spells [2].
The important detail is that DCGs are syntactic sugar for ordinary Prolog, so I could code my parser in the same language as my engine and my player. My biggest problem was really to draw an imaginary line between the parser and the other two components, because the easiest thing would be to allow them to know about each other and be infinitely entangled in a big ball of mess.
Anyway, yeah, there's something out there that is perfectly suited for creating DSLs, if you have the patience [3]. The tradeoff is that you have to learn Prolog. I suspect this is a cost too high for many who just want an easy-to-use tool.
Btw, you can't easily run my degree project unfortunately. Like an idiot I wrote it for a proprietary Prolog system and although I tried to port it to the free and open-source SWI-Prolog, it's been a nightmare of incompatibilities. The ported project is here but it breaks unexpectedly all the time:
https://github.com/stassa/Gleemin
________
[1] https://en.wikipedia.org/wiki/Definite_clause_grammar#Exampl...
[2] I also had an alpha-beta minimax AI player. Not that good though. I wanted to program a player with background knowledge of M:tG but I didn't have the time.
[3] Or you can learn them from examples... See Experiment 3 on page 19 of the pdf, here:
https://link.springer.com/article/10.1007/s10994-020-05945-w
Do you have any recommendations for good articles about Prolog? I really like the idea. I'm particularly interested in solving assignment problems using constraint logic programming.
For a practically-minded programmer, I'd recommend this longer tutorial that guides you through the creation of an old-skewl text-based adventure game:
https://amzi.com/AdventureInProlog/apreface.php
As far as I remember, the tutorial should run on most Prologs without (significant?) modification.
For a more in-depth, high-level, more computer-sciency view try Marcus Triska's pages:
https://www.metalevel.at/prolog
Marcus Triska is also the author of several constraint logic programming libraries, for example:
https://www.swi-prolog.org/man/clpfd.html
Then, there's a number of textbooks. The classics are Clockin and Mellish and Bratko:
Programming in Prolog (Fifth Edition):
https://www2.cs.arizona.edu/classes/cs372/spring15/Programmi...
Prolog programing for AI
https://archive.org/details/prologprogrammin0000brat
I personally really enjoyed this book by George Luger:
AI Algorithms, Data Structures and Idioms in Prolog, Lisp and Java
https://www.cs.fsu.edu/~cap5605/Luger_Supplementary_Text.pdf
For the theory behind DCGs, there's Pereira and Shieber:
Prolog and Natural Language Analysis
http://www.mtome.com/Publications/PNLA/prolog-digital.pdf
And for logic programming theory in general, the seminal source is J. W. Lloyd:
Foundations of logic progamming
https://link.springer.com/book/10.1007/978-3-642-83189-8
Unfortunately, I can't recommend any newer texbooks.
"My students and I had written several interactive tools for IC design, such as Magic and Crystal. Each tool needed to have a command language (in those days people tended to invoke tools by typing commands; graphical user interfaces weren't yet in widespread use). However, our primary interest was in the tools, not their command languages. Thus we didn't invest much effort in the command languages and the languages ended up being weak and quirky. Furthermore, the language for one tool couldn't be carried over to the next, so each tool ended up with a different bad command language. After a while this became tiresome and embarrassing."
Plus almost everything language has some kind of PEG or parser combinator library these days.
As others have said, embed something existing. I think this is especially true for programming languages. Even if Lua isn't quite what you want, it's probably going to deliver a lot more value than anything you could bash together on your own. And there are a few other options as well. There are several of these "complete toolkits for DSLs", it's just they do take a bit of work to correctly insert into your code base and then expose enough of what you're doing to make it useful. There isn't and as far as I can see can't be something you just install and it magically exposes everything and it's just awesome and takes no work, because even if you're in something like Python where you can just open an interpreter shell in the current context, thereby technically giving the user the power to do anything they want, you still need to create a safe interface for them, document it, test it, etc. (You may not do a lot of technical work to keep them out of where you haven't tested but you will need to provide them a supported area to get anywhere.)
For building your own: For small tasks, a parser is just a specialized sort of deserializer. Yea verily these 30 years ago, there wasn't a lot of generic deserializers available, and the ones that existed like asn.1 were completely unsuitable for human use, so "classic" compiler literature spends a lot of time on building your own parser. Now, if you don't have a specialized need, you should use a generic deserializer. I have quite a few JSON-based syntaxes lying around. (They feed "interpreters", but same principle.) Lisp S-expressions, if suitable for your environment, can be adapted. XML could be useful in some specialized circumstances where your input looks more like a document than conventional code. Etc. You should only build a custom parser if it's going to give you more bang for your buck across the whole usage cycle than a generic parser can give you. The reason why I have several things that input JSON is precisely that the amount of usage across all time was just going to be too low to justify doing anything specialized, because it was always a strictly internal tool.
(Hint: Just because your compiler accepts JSON as input doesn't mean that that's what the humans have to directly output or edit. My biggest interpreter took in JSON but I provided abundant function helpers that abstracted that away. It was a thin enough abstraction that it could be penetrated if need be, but it avoided most of the verbosity issues as far as the humans were concerned, and gave them the full power of the programming language to generate loops and such. If you squint, I basically borrowed an existing general-purpose programming language that everyone involved already knew to use as a macro language for my language, basically for free. This means the "core" language that I was implementing didn't have to do anything that the already-existing general-purpose language could do in macros, meaning the layer the humans used offered a lot of power for not much implementation cost on my side.)
For AST transforms, this is always where your secret sauce is and there's little help to give, beyond a suggestion that this is arguably the canonical case for a functional programming style, even if you are in an otherwise OO language.
For the final output, I would suggest that in modern times, the easy answer is, don't bother. You can probably interpret fast enough to solve your problems. If not, there are some options like LLVM that will help vs. what you used to have to do. But I would definitely consider just interpreting the final AST directly. If you intend to do that your AST transforms can be built with interpretation in mind.
The real value of a compiler and what distinguishes it from any ol' normal code that ingests something and emits something is the AST in the middle, and the complexity of that AST (probably through significant recursion) and the transforms you run on it, and the corresponding complex behaviors the input can invoke through the recursive input and complex AST transforms. Anything you can do to brush away the incidental details of a compiler by using existing serializations and if at all possible simply skipping the output step of the compiler will hugely increase the bang-for-the-buck you get. You might say, rather than "writing a compiler" consider "using compiler techniques" but not writing a compiler. But not in a way the article was talking about.
For the specific case mentioned there, go get an existing parser for your language, get the full AST tree. You can write your transform in terms of what you do understand and just pass through anything you don't. It's slightly harder, but will be fairly effective.
It is possible even today, of course, that you will be backed against a wall and be forced to go through the full classical compiler cycle. A programming language, for instance, just can't afford to use any existing parser, it's too much a vital part of the experience to try to use an existing one. Even a new Lisp will probably want its own spin on S-expressions enough that it can't just pick up an existing one unchanged. And maybe you've got something that you expect will be big enough that it just requires a new syntax, and you can afford all the support that goes with that. But the vast majority of the time, with the right toolset, you can indeed obtain most of the value of compiler-like techniques without the cost of the full classical compiler technology stack, because even if it was hypothetically possible to build a "real compiler" that had its own custom syntax rather than some slightly dodgy JSON and emitted LLVM code that resulted in an executable that runs all its tasks in .0003 seconds, the engineering effort for that is so much greater than the JSON input and interpreter that runs in .003 seconds that in most cases it's not worth it.
Ah, the JSON_IR!
As a programmer, you would include the libray, provide the binding to your program... and done ! In a way, it's a bit what is possible with java.scripting but they provide a Javascript engine but no BASIC for end-user
- either full blown programming language for IT guys
- "natural language" AI toolkits (not really usable yet for just simple automation by users)
- graphical language like State Machine or "no code", missing loops and requiring mouse and boxes
However, most of the time, user simply need some kind of BASIC (like visual basic used a lot in "shadow IT" by users)... but there's really few libraries providing that kind of functionalites