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)