richard_shelton

I am building educational 16-bit game console for low-cost FPGA chips.

https://github.com/true-grue/Brus-16

A microlibrary in 52 LOC.

In some parallel world, Python is the perfect tool for language-oriented programming. Any decorated function is compiled by its own DSL compiler into the internal representation of the corresponding solver, and functions communicate with each other using rich Python data structures :)

Or you can use Python AST + Z3 :) Here is a toy implementation:

https://github.com/true-grue/python-dsls/blob/main/datalog/d...

It's funny how close it is to the title of my talk "Python already has a frontend for your compiler": https://github.com/true-grue/python-dsls

I hope someone will write an article about Gary Kildall's achievements in theory of compilation. For us, compiler writers, he is a legendary figure.

What I like about these notes is that a complex topic is described in a simple and very practical manner. By the way, a few years ago there was another project on creating a code generator using declarative constraint solving:

https://www.researchgate.net/profile/Peter-Sovietov/publicat...

Here are more real-world, compiler-related examples: https://github.com/true-grue/python-dsls/blob/main/python_ds...

By the way, there is a similar work to Unison project. Its basic idea is to automate the compiler backend generation with help of SMT solver. The article: https://link.springer.com/epdf/10.1134/S0361768821070082?sha...

Basically, yes, so I tried to make a simple implementation as possible. And I'm taking into account that students are already familiar with postfix notation and stack data structure. Of course, I use additional sources (like the popular Crafting Interpreters book) in the teaching process.

If you are familiar with Forth, Postscript, or Joy you should have no problems with programming in Fortik :)

Still, the idea of Fortik is to encourage students to learn how simple interpreters work and to extend the language.

The chip is closer to AsAP [1] and XMOS xCore [2]. I remember that these two chips-competitors already existed when I was programming the predecessor of Greenarrays GA144. By the way, it was very fun to program these Forth-based processor arrays!

[1] https://en.wikipedia.org/wiki/Asynchronous_array_of_simple_p...

[2] https://en.wikipedia.org/wiki/XMOS

Sure, my code is only a demonstration that you can fit everything in <100 lines. I remember that there were some sceptics in older HN discussions on this topic... :)

Again, thank you very much for all your education reverse engineering works!

Here is my simple port of VoxelSpace (74 sloc). Written in Python 3, no additional libraries required.

https://github.com/true-grue/terrain

Looks like Python+Tkinter is a good demoscene platform where you have performance of graphics close to 286/EGA :)

About Warren's article. I just returned it back, sorry for the inconvenience :) By the way, you may find basically the same description of the compiler in The Art of Prolog book.

And here is an another pattern matching implementation for Python [1]. It was made for compilers construction task and may look similiar for those who has an experience with Prolog, Stratego or Refal.

And here is a toy term rewriting system [2].

[1] https://github.com/true-grue/raddsl

[2] https://github.com/true-grue/code-snippets/blob/master/ttrs....

Thank you, really interesting reading!

It would be interesting to see how this rule ("x = (y + c1) + c2 => x = y + (с1 + с2)") was encoded in the compiler. I guess it has more complicated form than a (simple and declarative) term rewriting rule, which you may use on AST transform stage.

There is a quote from Muchnik's textbook: "Like constant folding, algebraic simplifications and reassociation are best structured in a compiler as a subroutine that can be called from any other phase that can make use of it".

But it seems that in some cases, on the later phases with lower IRs, you just can't use this "subroutine" as is.

I think there definitely is some similarity between Kuryokhin and Zoshchenko. "Stories about Lenin" by M. Zoshchenko have some absurd/satire elements. And these elements were almost invisible for many Soviet citizens. They started to notice these moments in the text only after the dissolution of USSR.

You almost made me think that "Wag the Dog" is a Russian movie [1].

[1] https://en.wikipedia.org/wiki/Wag_the_Dog

Thank you very much! I decided to place my DSL tools (they contain a tiny amount of code, but I've used them successfully in a number of compiler projects) on github and just started looking for some illustrative examples. And your solution for Halt Problem (never heard about this problem before -- I mean this reddit challenge, of course, not Rice's theorem) appeared just in a right time. Thank you! :)

As a side note. It would be interesting to investigate power of a Prolog-like language which has terms, term variables, pattern matching (maybe even without full unification) and only local backtracking. Plus an ability to make user-defined execution strategies (tree traversals etc) in the form of combinators. I already use most of these constucts in dsl_match module and I got my inspiration mostly from Stratego/XT. Still it would be good to see similiar general-purpose language and compare its expressiveness with Prolog.

In a general sense, yes, of course. Here are more examples.

1. BNF notation. Yes, it could be surprising, but in a BNF-like language we use function-level representation and white spaces here denote sequential composition of functions -- nonterminals.

2. In a some Lisp-like language one may use spaces to describe "abstract" composition. So, for sequential composition: "(seq func1 func2 func3)". And for parallel composition, for example: "(par func1 func2 func3)".

But in the case of real concatenative programming, which has its origin in Forth, you mostly deal with stacks and stack machines.

So called concatenative language is also a combinator-oriented language in a somewhat restricted form. Here are some historic examples of combinator-oriented languages: APL family and Backus's FP/FL (direct inspiration for the author of Joy). The fact that you denote composition of the functions with a white spaces is just a syntactic sugar. In the case of combinator-oriented language you work with various functional forms -- combinators, not just with composition, so you need to use more symbols to denote that. And in practice it's hard to find a concatenative language which would be used seriously, not just in a few hobby projects. In the same time there are impressive examples of modern combinator-oriented languages like Faust [1] and Spiral [2].

Still, the whole "concatenative" movement is interesting as a try to formalize the semantics and "improve" Forth language. See also Postscript and Henry Backer's articles [3].

[1] http://faust.grame.fr/

[2] http://www.spiral.net/

[3] http://home.pipeline.com/~hbaker1/ForthStack.html

it's interesting to mention that both Alan Kay (see "The early history of Smalltalk") and John McCarthy (see "advice taker") have very high opinion of logic programming.

Thanks for showing your code! I just placed my minimalist DSL tools and decided to use "Halt Problem" as an example. Here is my code: https://github.com/true-grue/dsl-tools

Thanks for the link!

There is a good reason for using Prolog-like language in a compiler-related project. Prolog was used for rapid prototyping of compilers since the end of 70s and it's still ahead of the time. And if you take a look at a code from old Warren article [1], for example, you'll see that even today almost nobody uses so high-level description of a compiler. The main power of Prolog is not in parsing. Prolog is unbeatable in a program analysis and transformations. See Datalog (you may find it even in a Dragon book nowadays!), see Stratego/XT, they all inspired by good old Prolog.

By the way, Prolog is also good in describing formal semantics of PLs. Good PL reference or a standard should include clean formal notation for semanics of the language, not some bureaucratic English text... Because it's already 2018, we need it for compiler developers and for deeper understanding of a language.

[1] http://sovietov.com/tmp/warren1980.pdf (this is excellent article, but, sadly, almost unknown one)

I have more uses for Python than the author, but one of these uses is really obvious: Python as C code generator. Python + C is a very powerful combination: metaprogramming, special constructs etc. Basically, with Python you can get rid of preprocessor hacks and messing with templates.

Thank you! I agree that just using of pattern matching may be not enough. But, instead of Visitor Pattern, I would use generic traversal "strategies" (combinators). My ideal is a DSL with first-class term rewriting rules + user definable strategies which take these rules as arguments. In fact, I already use such DSL for compiler writing :)

Well, it's another "Java-related compiler textbook". And this edition has a coauthor (Jens Palsberg) who is responsible for all OOP/Java-related things in the book. I recommend to read original ML edition even for Java developers. And I'm not the only one who recommends it.

"Comment by Vladimir N. Makarov: Another good book to start to study compilers from parser to code generation and basic optimizations. I especially like the version in ML (Modern compiler implementation in ML).

Comment by Steven Bosscher: The version in ML is the best of the three. The other two look too much like "had to do this"-books where algorithms are translated from ML, which makes them look very unnatural in C/Java." [1]

[1] http://gcc.gnu.org/wiki/ListOfCompilerBooks

I guess things you've mentioned are widespread inside the Java community. But let's consider the things that have more global impact to compiler writers. For example, Scala LMS is a very interesting and promising recent project. Take a look at its source code -- no Visitor pattern inside. Visitor pattern may be necessary part of "Java culture", but for Scala I see no real reason to keep using it.

P.S. Thanks for the real perfomance data!

In fact, it's a rather old question: what is better 1) a declarative approach with pattern matching or 2) Visitor pattern from OOP world.

Ok, better for what? Let's take a practical example: AST transformations inside a compiler. You may find Visitor pattern use only in a few Java-related compiler textbooks. For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc.

Ok, but the real point of the article is not that "visitors" are more readable and easy to use, but they are more perfomant, right? Do we have any profiling here? Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed? We remember the words about "premature optimization", and any "manual optimization" which makes the algorithm structure foggy is evil so (necessary evil -- in some rare cases). In some declarative languages pattern matching constructs are converted to a fast decision trees by compiler. There are some "lazy" approaches to pattern matching.

Or you can just provide a list of transforming (maybe some composition of transformations) functions to your generic pattern matching function. It's almost the same as using "visitors", but you don't need to call "The Team Architect™, for supervising the object oriented quality of your software" :)

if I understand correctly, you're the author of decompiler for StarFlight game. The most famous game written in Forth. And maybe most popular piece of Forth software of all times. So I think you surely know more about Forth than many modern Forthers do :)

Sorry, if I reveal this link too early, but this is very impressive work of you and StarFlight game/engine really deserves more popularity!

https://github.com/s-macke/starflight-reverse