1. 6

    Whoa, so Flpc stands for “Forth Lisp Python Continuum”? That acronym’s hiding some major awesomeness.

    I went digging for more about your project, and found the repository’s README. Neato. In an old Reddit comment, you say that FLPC came from “wanting a Python with a Forth(-like) as its bytecode”. Is that also what FLPC ended up being, or did it take some turns along the way? That runtime grammar modification is looking very impressive.

    Congratulations on attaining self-hosting! Time for flag beer*! (Flag beer is how Dutch builders celebrate that though the building isn’t done yet, its highest point has been reached.)

    * or flag tea, flag lemonade, flag hot chocolate, flag tonic …. the point is the celebration.

    1. 2

      Thanks! I’m glad to see you liked it enough to try and find out more about FLPC. Unfortunately, there’s isn’t much more written right now.

      In an old Reddit comment, you say that FLPC came from “wanting a Python with a Forth(-like) as its bytecode”. Is that also what FLPC ended up being, or did it take some turns along the way?

      Yes, that’s what it ended up being. Or rather I haven’t (had to) change the bytecode semantics since that post.

      However, I found out (but don’t remember if it was before or after that Reddit post) that some Python’s own bytecode was already pretty Forth-like. I looked at some dis output and poked at it with cpyasm. Though there are things it definitely couldn’t do. I think it was either run-time gotos or writing to memory that was hard.

    1. 1

      I’d like to offer a differing opinion: Don’t slow down.

      For recorded videos, speed can be adjusted at read time instead of write time. All video players I’ve used (including online ones like Youtube) have an option to scale speed. I don’t think its such a big deal that I have to watch your talk at 1.3x instead of the usual 1.5x - 2x [1].

      For a live talk, I can only say often I wish there was a way to speed those up too. Maybe you were just catering to a niche audience. :) I don’t know.

      If there was needless or content-less talking, sure I’d say take some of that out. While anything can be more compact, I didn’t feel the videos you linked were wasteful.

      In fact, I’ve been thinking of ways to do the opposite. For talks where the speaker talks quickly but have too many long pauses, adjusting speed in the video player doesn’t work well since my attention isn’t there when the burst of speech comes. I’m hoping of finding a way to lengthen the spoken parts to fill the gaps of silence while keeping something like the midpoint constant.

      | talking 1 | silence 1 | talking 2 | silene 2 | talking 3 |
      | talking   1  |sil| talking         2 |sil| talking     3 |
      

      I know tools that can find regions of silences. They’re just not malleable enough (or I don’t know them well enough) to apply the transformation.

      [1] Unrelated side remark: there’s an oddity with every pitch-adjusting speeding up method that every video player uses which makes speeding up speech beyond 2x quickly incomprehensible. Applying the same speed up algorithm twice does not produce this issue. For example, write the output of a 1.5x speed up to a file and then apply another 1.5x speed up for a total of 2.25x makes the video comprehensible, but a straight 2.25x speed up does not.

      The sharp drop seems to be at exactly 2x. If anyone know what’s going on, please let me know.

      1. 2

        Nice intro.

        Used this tool once to “remote-control” a horrible Windows application that was not meant to be automated.

        Keeping the screenshots updated (making them, aligning, cropping etc) was horrible - but for a few hours of work we could automate a process and only had to touch/fix it once a month instead of someone having to do this daily. Not proud of it but if it gets the job done…

        1. 1

          Thanks for sharing!

          Yeah, automating Windows programs is exactly what I thought of when I learned of this workflow, unfortunately only fairly recently. I’m reassured by how widely this approach can be applied, if a bit slow and hacky to set up.

        1. 5

          I think this is something I’ve encountered. But if I understood your clarification correctly, I think the way you phrase the question is really confusing.

          So instead of answering the question, I’m going to suggest a better formulation of the question and hope that helps.

          What you want to know is:

          How can I alternate between calls to two functions A and B a number of times (or until some condition is met) but skip the last call to B. For example ABABABA.

          An explanation of my (and possibly others’) confusion: The part about even and odd is misleading. ABABA (odd A, even B) and ABABABAB (even A, odd B) are both equally interesting to you.

          The part where A changes (abcd) but B (,,,) doesn’t is equally misleading.

          1. 1

            Yes, you understood what I was looking for. Sorry for those misleading parts.. Thank you for your assistance!

          1. 1

            Its funny how the entire post and code make no mention of the 2d cell structure of a spreadsheet. For example, in a spreadsheet you can take the sum of a rectangle with =sum(A1:D3).

            This implementation of invalidate is pretty interesting. It effectively avoid re-invalidating the observers of a cell more than once and doesn’t immediately re-evaluate the invalidated cells. It makes them lazily evaluated again.

            I’ve tried implementing something similar and this feels more efficient than the different strategies I’ve tried.

            Its too bad they didn’t discuss this aspect of their design. I almost missed it if it weren’t for me trying to write this comment (where I first was first going to stated that their invalidation is inefficient). I wonder what other design decisions and trade-off went into this.

            1. 6

              This is a real gold mine of information. Some acronym expansion (I didn’t know what IR was):

              • IR: intermediate representation
              • AST: abstract syntax tree

              Can any one comment on the implementation and efficiency of Variation #5 (Only compile some functions, interpret the rest)? At first I thought this meant to write the fast versions by hand (like calling C routines from Python) but then the last bullet suggest that it should actually be automated.

              Then how does the compiler select which functions to compile (or is that decision made from user input)? I guess all compiled functions can’t be stepped into?

              Variation #6 (Partial Evaluation Tricks) is also pretty interesting but other than satisfying the formal definition of a compiler, isn’t a compiled program obtained through this Futamura Projection have pretty much keep the same speed as the original interpreter? (Same for compile programs obtained from a compiler obtained from a Futamura Projection.) Mainly because the interpreter wouldn’t do any compile time optimization (since its not expecting itself to be run as a compiler!). So it seems like a step back as you also lose the advantages of the interpreter.

              Hard to provide diagnostics, type- checking, optimization, really anything other than straight translations.

              That was kind of disheating to read that going the META route, there’s not much we can (or at least know how to) do.

              1. 4

                isn’t a compiled program obtained through this Futamura Projection have pretty much keep the same speed as the original interpreter?

                it can be faster, it can remove a layer of interpreter overhead.

                Suppose you have a good self applicable partial evaluator for language A written in language A.

                You write an interpreter for language B in language A. It executes programs in language B with the speed of an interpreter running on of top of the language A platform.

                Now you use the partial evaluator to produce a B->A compiler, compile your B program with it and you can run the resulting output with the full speed of a program written natively for the language A platform.

                the interpreter wouldn’t do any compile time optimization

                That’s the magic part. you don’t need to implement any optimizations*, but after all the interpreter overhead is dissolved away by the partial evaluation procedure, the optimizations of the host language implementation are applied.

                (* You do have to be kind of careful to write the interpreter in a way that will admit good specialization though)

                1. 2

                  Suppose you have a good self applicable partial evaluator for language A written in language A.

                  Ah, while reading the slide I was thinking of the trivial (lazy) partial evaluator that does nothing and just evalutes when the compiled program executes.

                  I see now. With a non-trivial partial evaluator, you can use it and gain in all three steps. Though now I’ve no idea how to write a useful partial evaluator.

                  1. 4

                    Though now I’ve no idea how to write a useful partial evaluator.

                    You might want to look at supercompilation, since this is the same idea but hard-coded in an otherwise-normal compiler. To get some idea of how partial-evaluation/supercompilation works, we can start with a naive compiler with no optimisations: it’s essentially doing find/replace of constructs in the source language with equivalents in the target language, with no evaluation.

                    “Constant folding” is probably the simplest form of partial evaluation, so we can add that to our compiler. This is a source-to-source optimisation pass, which looks for constant expressions like 1 + 2, performs the calculations and replaces those expression with their result (e.g. 3). ‘Performing the calculations’ just means we’re evaluating those expressions. Since we’re only evaluating some expressions, not the whole program, this is partial evaluation. This doesn’t need to be restricted to arithmetic: we can also do booleans like replacing true || false with true. In fact, if our language has short-circuiting, we can replace true || x with true even if x isn’t constant! We can do the same with branches, replacing if (true) { x } else { y } with x and likewise for false/y.

                    Another common form of partial evaluation is “function inlining”, where we replace a call to a known function with the body of that function. Again, this is a source-to-source transformation which performs evaluation (specifically: beta-reduction), but only on a sub-set of expressions. Combined with constant folding, this can remove a lot of indirection, specialising the code to our use-case before it gets compiled.

                    We can, in principle, make such source-to-source transformations for every language construct (“loop unrolling” is another example). This is actually a reasonable way to make an interpreter, known as a term rewriting system; since, at runtime, there are no unknowns, so we can treat everything as constants to be folded.

                    If we want a compiler rather than an interpreter, we need to make some decisions about when to stop the partial evaluation. This is because some constructs can get bigger and bigger, e.g. unrolling a loop with an unknown number of iterations, or inlining (mutually) recursive functions without knowing when we’ll hit the base case. This isn’t an insurmountable problem, since any choice will still result in a correct translation, but we might want some heuristics to strike a good balance between specialising-away indirection, and bloating the program with duplicate code.

                    1. 1

                      Thanks for your detailed explanation.

                      it’s essentially doing find/replace of constructs in the source language with equivalents in the target language, with no evaluation.

                      I don’t understand what you mean by this. I think of, say, source=python and target=C (or asm). There aren’t really obvious equivalent constructs (like no lists or dicts or even similar things have different semantics so they wouldn’t be equivalent).

                      I thought you’d start by modifying the first input (I) to use the second input (P) as a hard-coded value. E.g., a python interpreter with a fixed hard-coded program to interpret which can thus only interpret that particular program.

                      If the source and target are equal, I can see some of the optimization here would apply but otherwise, what you’ve described seems to only optimize the version of the emitted program (say the start program described above) where I and P are already combined, instead of treating them separately. Or maybe you meant this as a partial evaluator for a fixed I?

                      1. 1

                        I don’t understand what you mean by this. I think of, say, source=python and target=C (or asm). There aren’t really obvious equivalent constructs (like no lists or dicts or even similar things have different semantics so they wouldn’t be equivalent).

                        Heh, I was intending my example to be really, really dumb/naive, as a base-line to work from.

                        It is possible to convert Python expressions into equivalent chunks of C or ASM in a find/replace way; it’s just that those chunks will be huge in comparison. Given some Python like 1 + 2, we wouldn’t replace it with C like 1 + 2; we would replace it with C like setUpABunchOfContext(); setUpExceptionHandlingStack(); maybeAllocateABunchOfMemory(); messWithThreads(); ... and so on, then do the actual thing we care about, then do a bunch of clean up like maybeFreeABunchOfMemory(); tearDownExceptionHandlingStack(); tearDownABunchOfContext(); collectGarbage(); ..., etc.. In fact, we’d probably do all of that just to construct the value 1, then do it again for the 2, then again to look up the __add__ method (which is what + desugars to), then again to call that method. Of course, this would also require us to write all of this helper code (this is known as a “runtime system” or RTS; although most real RTS are much smaller and saner than this example!)

                        I thought you’d start by modifying the first input (I) to use the second input (P) as a hard-coded value

                        Yes, that’s called function inlining ;)

                        If the source and target are equal, I can see some of the optimization here would apply but otherwise, what you’ve described seems to only optimize the version of the emitted program

                        Constant folding, function inlining, loop unrolling, etc. are indeed source-to-source transformations rather than translations between languages, but there’s nothing stopping us from performing them as well as translating to a different language. Indeed, that’s what most optimising compilers do, like GCC/LLVM/GHC/etc. (usually by translating/compiling from the source to a some intermediate representation; then doing a bunch of source-to-source transformations in that IR language; then translating/compiling the IR into the target language).

                2. 2

                  Then how does the compiler select which functions to compile

                  One of the replies mentioned JIT compilers. That’s not the only scenario.

                  In my language, a function is compiled (into GLSL) if it needs to be executed on the GPU, otherwise it is interpreted. Since my system is designed for live coding and rapid prototyping, you want to minimize the latency from making a code change to running the code, so I don’t do any expensive compilation (LLVM would be too slow). Instead, I perform a fast compilation into IR then interpret the IR. But once code migrates to the GPU, then the requirements change, so I compile a subset of your code to GLSL, which the GPU driver then compiles to GPU machine code.

                  1. 2

                    Then how does the compiler select which functions to compile (or is that decision made from user input)?

                    It has heuristics, similarly to how compilers decide when to inline functions. Generally it’s a function of how often a function is called – it’s decided at runtime. Basically, you have a ‘function’ construct in your vm that contains a bunch of bytecode. Each time you call that function, the bytecode is interpreted. But it keeps track of how many times the function is called. If you call it a bunch of times, then that bytecode gets compiled to native code, and then that is what’s executed.

                    I guess all compiled functions can’t be stepped into?

                    Why not? You can step through c code, which is almost inevitably all compiled.

                    1. 1

                      Your description of the heuristic sounds like just-in-time compilation (which I also don’t know well). Is it the same here? I thought this was talking about something else just because the word wasn’t used.

                      Why not? You can step through c code, which is almost inevitably all compiled.

                      Right, sorry, I meant you can’t step through the original version of the source. For C, with no optimization, you can step through it but you can’t always step through code compiled with optimization (at least with the debuggers I know of which is gdb and lldb). You can still step through the assembly, but finding the lines it corresponds to the source C code is just not there (sometimes entirely removed, being optimized out).

                      1. 2

                        Your description of the heuristic sounds like just-in-time compilation (which I also don’t know well). Is it the same here? I thought this was talking about something else just because the word wasn’t used.

                        That’s what I assume. It specifically says it’s an interpreter which compiles some things, which is basically a description of JIT.

                        you can’t always step through code compiled with optimization

                        Fair enough. I’ll admit, I don’t know that much about JIT either so someone correct me if I’m wrong.

                  1. 6

                    In the general case, I have developed a deep and long-lasting skepticism of DSLs. I was a very heavy proponent of them during my grad studies, and investigated pretty thoroughly using a rules engine for Space Invaders Enterprise Edition and a runtime monitor for Super Mario World.

                    I went a little further down this path before I abandoned it for reasons unrelated to the DSL skepticism. That happened later. I just wanted to give context that I was actually naturally predisposed to liking them.

                    What has happened in my time on this earth as a software engineer is the feeling that it is axiomatic that all DSLs eventually tend towards something Turing complete. New requirements appear, features are added, the DSL heads further towards Turing completeness. Except the DSL does not have the fundamental mechanics to express Turing completeness, it is by fundamental design supposed to not do that. What you end up with is something very complex, where users are performing all sorts of crazy contortions to get behavior they want, and you can never roll that back. I feel like DSLs are essentially doomed from the outset.

                    I am much, much more optimistic about opinionated libraries as the means to solve the problems DSLs do (Ruby on Rails being the most obvious one). That way any of the contortions can be performed in a familiar language that the developer is happy to use and won’t create crazy syntax, and the library then called to do whatever limited subset of things it wants to support. For basic users, they’ll interact with the library only and won’t see the programming language. As things progress, the base language can be brought in to handle more complex cases as pre/post-processing by the caller, without infringing on the design of the library.

                    At Google, we have a number of DSLs to perform many different tasks which I won’t go into here. Each one requires a certain learning curve and a certain topping-out where you can’t express what you want. I was much happier with an opinionated library approach in Python, where I could do a great deal of what I wanted without peering behind the curtain of what was going to be performed.

                    1. 6

                      sklogic on Hacker News had a different view: you start with a powerful, Turing-complete language that supports DSL’s with them taking the place of libraries. He said he’ll use DSL’s for stuff like XML querying, Prolog where logic approach makes more sense, Standard ML when he wants it type-safe in simple form, and, if all else fails or is too kludgy, drops back into LISP that hosts it all. He uses that approach to build really complicated tools like his mbase framework.

                      I saw no problem with the approach. The 4GL’s and DSL’s got messy because they had to be extended toward powerful. Starting with something powerful that you constrain where possible eliminates those concerns. Racket Scheme and REBOL/Red are probably best examples. Ivory language is an example for low-level programming done with Haskell DSL’s. I have less knowledge of what Haskell’s can do, though.

                      1. 3

                        I think it’s a good approach, but it’s still hard to make sure that the main language hosting all the DSLs can accomodate all of their quirks. Lisp does seem to be an obvious host language, but if it were that simple then this approach would have taken off years ago.

                        Why didn’t it? Probably because syntax matters and error messages matter. Towers of macros produce bad error messages. And programmers do want syntax.

                        And I agree that syntax isn’t just a detail; it’s an essential quality of the language. I think there are fundamental “information theory” reasons why certain syntaxes are better than others.

                        Anything involving s-expressions falls down – although I know that sklogic’s system does try to break free of s-expression by adding syntax.

                        Another problem is that ironically by making it too easy to implement a DSL, you get bad DSLs! DSLs have to be stable over time to be made “real” in people’s heads. If you just have a pile of Lisp code, there’s no real incentive for stability or documentation.

                        1. 4

                          “but if it were that simple then this approach would have taken off years ago.”

                          It did. The results were LISP machines, Common LISP, and Scheme. Their users do little DSL’s all the time to quickly solve their problems. LISP was largely killed off by AI Winter in a form of guilt by association. It was also really weird vs things like Python. At least two companies, Franz and LispWorks, are still in Common LISP business with plenty of success stories on complex problems. Clojure brought it to Java land. Racket is heavy on DSL’s backed by How to Design Programs and Beautiful Racket.

                          There was also a niche community around REBOL, making a comeback via Red, transformation languages like Rascal, META II follow-ups like Ometa, and Kay et al’s work in STEPS reports using “IS” as foundational language. Now, we have Haskell, Rust, Nim, and Julia programmers doing DSL-like stuff. Even some people in formal verification are doing metaprogramming in Coq etc.

                          I’d say the idea took off repeatedly with commercial success at one point.

                          “Probably because syntax matters and error messages matter. Towers of macros produce bad error messages. And programmers do want syntax.”

                          This is a good point. People also pointed out in other discussions with sklogic that each parsing method had its pro’s and con’s. He countered that they can just use more than one. I think a lot of people don’t realize that today’s computers are so fast and we have so many libraries that this is a decent option. Especially if we use or build tools that autogenerate parsers from grammars.

                          So, IIRC, he would use one for raw efficiency first. If it failed on something, that something would get run through a parser designed for making error detection and messages. That’s now my default recommendation to people looking at parsers.

                          “Anything involving s-expressions falls down – although I know that sklogic’s system does try to break free of s-expression by adding syntax.”

                          Things like Dylan, Nim, and Julia improve on that. There’s also just treating it like a tree with a tree-oriented language to manipulate it. A DSL for easily describing DSL operations.

                          “nother problem is that ironically by making it too easy to implement a DSL, you get bad DSLs!”

                          The fact that people can screw it up probably shouldn’t be an argument against it since they can screw anything up. The real risk of gibberish, though, led (per online commenters) a lot of teams using Common LISP to mandate just using a specific coding style with libraries and no macros for most of the apps. Then, they use macros just handling what makes sense like portability, knocking out boilerplate, and so on. And the experienced people wrote and/or reviewed them. :)

                          1. 2

                            Probably because syntax matters and error messages matter. Towers of macros produce bad error messages. And programmers do want syntax.

                            Another problem is that ironically by making it too easy to implement a DSL, you get bad DSLs! DSLs have to be stable over time to be made “real” in people’s heads. If you just have a pile of Lisp code, there’s no real incentive for stability or documentation.

                            I’m so glad to see this put into words. Although for me, I find it frustrating that this seem to be universally true. I was pretty surprised the first time around when I felt my debugger was telling me almost nothing because my syntax was so uniform, I couldn’t really tell where I was in the source anymore!

                            Some possibilities for this not to be true that I’m hoping for: maybe its like goto statements and if we restrict ourselves to make DSLs in a certain way, they won’t become bad (or at least won’t become bad too quickly). By restricting the kind of gotos we use (and presenting them differently), we managed to still keep the “alter control flow” aspect of goto.

                            Maybe there’s also something to be done for errors. Ideally, there’d be a way to spend time proportional to the size of the language to create meaningful error messages. Maybe by adding some extra information somewhere that currently implicit in the language design.

                            I don’t know what to do about stability though. I mean you could always “freeze” part of the language I guess.

                            For this particular project, I’m more afraid that they’ll go the SQL route where you need to know so much about how the internals work that it mostly defeats the purpose of having a declarative language in the first place. I’d rather see declarative languages with well-defined succinct transformations to some version of the code that correspond to the actual execution.

                            1. 1

                              (late reply) Someone shared this 2011 essay with me, which has apparently been discussed to death, but I hadn’t read it until now. It says pretty much exactly what I was getting at!

                              http://winestockwebdesign.com/Essays/Lisp_Curse.html

                              In this essay, I argue that Lisp’s expressive power is actually a cause of its lack of momentum.

                              I said:

                              Another problem is that ironically by making it too easy to implement a DSL, you get bad DSLs!

                              So that is the “curse of Lisp”. Although he clarifieds that they’re not just “bad” – there are too many of them.

                              He mentions documentation several times too.

                              Thus, they will have eighty percent of the features that most people need (a different eighty percent in each case). They will be poorly documented. They will not be portable across Lisp systems.

                              Domain knowledge is VERY hard to acquire, and the way you share that is by developing a stable and documented DSL. Like Awk. I wouldn’t have developed Awk on my own! It’s a nice little abstraction someone shared with me, and now I get it.

                              The “bipolar lisp programmer” essay that he quotes also says the same things… I had not really read that one either but now I get more what they’re saying.

                              1. 1

                                Thanks for sharing that link again! I don’t think I’ve seen it before, or at least have forgotten. (Some of the links from it seem to be broken unfortunately.)

                                One remark I have is that I think you could transmit information instead of code and programs to work around this curse. Implicit throughout the article is that collaboration is only possible if everyone uses the same language or dialect of it; indeed, this is how version controlled open-source projects are typically structured: around the source.

                                Instead, people could collaboratively share ideas and findings so everyone is able to (re)implemented it in their own DSL. I say a bit more on this in my comment here.

                                In my case, on top of documentation (or even instead of it), I’d like to have enough instructions for rebuilding the whole thing from scratch.

                                To answer your comment more directly

                                Domain knowledge is VERY hard to acquire, and the way you share that is by developing a stable and documented DSL

                                I totally agree that domain knowledge is hard to acquire but I’m saying that this only one way of sharing that knowledge once found. The other way is through written documents.

                        2. 4

                          Since I like giving things names, I think of this as the internal DSL vs external DSL argument [1]. This applies to your post and the reply by @nickpsecurity about sklogic’s system with Lisp at the foundation. If there is a better or more common name for it, I’d like to know.

                          I agree that internal DSLs (ones embedded in a full programming language) are preferable because of the problems you mention.

                          The external DSLs always evolve into crappy programming languages. It’s “failure by success” – they become popular (success) and the failure mode is that certain applications require more power, so they become a programming language.

                          Here are my examples with shell, awk, and make, which all started out non Turing-complete (even Awk) and then turned into programming languages.

                          http://www.oilshell.org/blog/2016/11/14.html

                          Ilya Sher points out the same problems with newer cloud configuration languages.

                          https://ilya-sher.org/2018/09/15/aws-cloudformation-became-a-programming-language/

                          I also worked at Google, and around the time I started, there were lots of Python-based internal DSLs (e.g. the build system that became Blaze/Bazel was literally a Python script, not a Java interpreter for a subset of Python).

                          This worked OK, but these systems eventually got rewritten because Python isn’t a great language for internal DSLs. The import system seems to be a pretty significant barrier. Another thing that is missing is Ruby-style blocks, which are used in configs like Vagrantfile and I think Puppet. Ruby is better, but not ideal either. (Off the top of my head: it’s large, starts up slowly, and has version stability issues.)

                          I’m trying to address some of this with Oil, although that’s still a bit far in the future :-/ Basically the goal is to design a language that’s a better host for internal DSLs than Python or Ruby.

                          [1] https://martinfowler.com/bliki/InternalDslStyle.html

                          1. 3

                            If a programming language is flexible enough, the difference between DSL and library practically disappears.

                            1. 1

                              DSL’s work great when the domain is small and stays small and is backed by corporal punishment. Business Software is an astronomically large domain.

                            1. 4

                              return in a generator throws a StopIteration exception, which is a useful feature but not the same thing as yield from at all. That being said, yield from will also throw a StopIteration exception if the generator it’s yielding from throws one. StopIteration is nothing to be afraid of.

                              1. 1

                                StopIteration is nothing to be afraid of.

                                StopIteration is definitely nothing to be afraid of, but a big change in logic, from a subtle change in code is. Since returning the value doesn’t do anything other than stopping the iteration, I would much rather not even being able to actually return a value (empty return statements are okay). This can be caught by linting, but I can see it easily passing code review if the diff doesn’t include both the return val and the yield.

                                1. 2

                                  You’re right, but I think it’s worth also remembering that return to yield from is really no smaller a change in code than say if to while.

                                  1. 1

                                    Yeah that’s quite true.

                                  2. 1

                                    In Python 2, a non-empty return inside a generator (any def that yield) would give you a syntax error

                                    SyntaxError: 'return' with argument inside generator
                                    

                                    So it used to be the way you wanted it. I hadn’t noticed this change in Python 3.

                                    I have an implementation of an interpreter for (a subset of) Python and I think it would be clearer if a different keyword than def (like gen) was used for generators. This would also mean the interpreter doesn’t need to look inside the body to know if its a function or generator.

                                    1. 1

                                      I think the gen can be a good idea, since it would make it also a bit clearer, for the reader. In general I’ve barely had any issues from confusing generators and functions so I guess the main benefit would still be for the interpreter. Also really interesting project you’ve got, the link you posted is broken though and redirects to lobste.rs/github.com/.....

                                1. 3

                                  Your experience unfortunately matches mine with generic solvers of all kinds (well, except one): its too slow for any input that could interest me. I’m amazed at how clear the write-up is despite things not going that well. I might try some of the same things but would be mum if asked to explain it.

                                  What happens if, to break symmetry, you just said “there are at most # rooms (R) talks at any time”? And remove ROOMS entirely from the model.

                                  Like

                                  constraint forall(t in TIMES)(
                                      sum(talk_times[talk] == t) <= R);
                                  
                                  1. 2

                                    I just tried that, and it’s pretty nice! You can rip out sched entirely. I couldn’t find a good way to add symmetry on times, but that plus a crude constraint talk_time[talks[1]] = TIMES[1]; gives you another 5x speedup.

                                    This gave me an idea: what if we have a variable set of the talks for each time and link them via int_set_channel? In theory, this would give you another huge bonus.

                                    array[TIMES] of var set of talks: talks_per_time;
                                    
                                    constraint int_set_channel(talk_time, talks_per_time);
                                    
                                    constraint forall(t in TIMES)(
                                       card(talks_per_time[t]) = R);
                                    

                                    In practice, Chuffed can’t handle var sets :(

                                    1. 2

                                      Oh yeah, good idea. So you’re basically saying the talks are partitioned into TIMES sets, each of size at most R [1]. Looks like MiniZinc even has a builtin partition_set but Chuffed won’t handle that either.

                                      I couldn’t find a good way to add symmetry on times, but that plus a crude constraint talk_time[talks[1]] = TIMES[1]; gives you another 5x speedup.

                                      If instead of using partition_set, you wanted to do this by hand, you could continue along the same lines as the crude constraint and say “the lowest indexed talk scheduled at time i or later is always scheduled at time i” (for all i).

                                      [1] I think you still need “at most” instead of “equal” unless you happen to have (# rooms) * (# time slots) talks (or add dummy talks nobody likes to get this to be true).

                                    2. 1

                                      solvers of all kinds (well, except one)

                                      And that exception would be…?

                                      1. 1

                                        Solvers for problems with continuous valued variables (float values) with linear constraints and objective.

                                        This might be a somewhat disappointing answer since the problems you can specify are much less generic. Usually needs some work just translating the problem into the input format (if it can be done at all), which is opposite to MiniZinc’s interface improvement.

                                    1. 8

                                      I ended up away from my PC for a bit much sooner than I expected, so I didn’t get to take part in the discussion here, but I rather feel like most of the comments here missed the point.

                                      While I’m not disputing that no programming language in practice can be turing complete, the mistake is jumping into thinking about implementations when the article is considering instead the abstract specification of the C language. In particular, the reason why C is not turing complete is because the specification requires pointer semantics that bake in enough implementation details that instead of breaking turing completeness, it’s required that no C implementation could ever be turing complete, even in the face of changing basic rules about computing.

                                      In another thread of comments, there is the request as to a language that would satisfy the authors definition of turing completeness “in theory”: Brainfuck. If you consider brainfuck as “a bidirectional infinite tape with the following operators […]”, then we have a language specification that is turing complete, even if no implementation can be. One could argue of course that this means that the specification can never be fully and correctly implemented and that’s true, but you can also write specifications that equally state neither behaviours that force turing incompleteness (C), nor make explicit demands that are impossible to fulfill (brainfuck), and instead leave such details out entirely (imagine a language that deals only in objects and operations on them, without reference to their representation in any implementation whatsoever).

                                      1. 1

                                        Thanks for clarifying this a bit. I’m still confused.

                                        the specification requires pointer semantics that bake in enough implementation details

                                        If I understand, here you are saying there’s “too many details included in the spec”. But I don’t understand the next sentence fragment at all.

                                        that instead of breaking turing completeness, it’s required that no C implementation could ever be turing complete, even in the face of changing basic rules about computing.

                                        On its own, “it’s required that …” could make sense but the two sentence fragments don’t match and make no sense (to me) together.

                                        In another thread of comments, there is the request as to a language that would satisfy the authors definition of turing completeness “in theory”: Brainfuck. If you consider brainfuck as “a bidirectional infinite tape with the following operators […]”, then we have a language specification that is turing complete, even if no implementation can be.

                                        Could you say what the equivalent for C is here? Consider C as “a [???] with the following operations”?

                                        1. 3

                                          Could you say what the equivalent for C is here? Consider C as “a [???] with the following operations”?

                                          The problem is that what the gp said isn’t quite true. Brainfuck isn’t a bidirectional infinite tape with the following ops. Brainfuck has a bidirectional infinite tape, and the following operators. C has a declarations, expressions, control flow, functions, memory, macros, etc. etc. It’s tempting to say that brainfuck is the bidirectional infinite tape, but it’s not, it’s a programming language that has only a couple of things.

                                          1. 2

                                            Could you say what the equivalent for C is here? Consider C as “a [???] with the following operations”?

                                            The problem is that in C, there is required to be a maximum number of valid pointers and as a result there is required to be a maximum number of valid addressable bytes, of a maximum bit length. This means memory is bounded and the C specification describes a finite state machine.

                                            You can implement a turing machine in Brainfuck. You cannot implement a turing machine in C.

                                            1. 1

                                              A programming language specification can leave the harsh realities of the real world to the implementation, and if you were to find some bizarre reality where genuine turing completeness is possible, you could in essence be able to implement some languages in a way that exploits this new theory of computation and create a genuinely turing complete language implementation.

                                              In C, however, there are specific rules about how pointers must be implemented that mean even in this world, you’d have to choose between correctly implementing the spec, or being turing complete, as the rules themselves have implications that mean you could not exploit the new reality to achieve this. These restrictions aren’t apparent to us everyday because we don’t have a world where turing completeness is possible, but that doesn’t mean the specification has to reflect those limitations - by choosing to leave the details of representation to the implementation, implementors could choose to make it as strong as their current reality allows.

                                              So, overall, what I mean in that sentence is that in C, implementations do not lose potential for turing completeness as set out by the spec, limited by reality, but instead start from a spec where it is already by definition not permitted.

                                              As for what C “is” in comparison to brainfuck, really Elronnd has it. The language I used is a little bit of a red herring in that brainfuck isn’t the tape in the same way the closest thing that C would “be” is some abstract machine you could build from the spec. It’s easy to build a mental model where the only object is a tape/machine, but the language specs really instead have the machine and also have rules to about how they work and are manipulated. I can only apologise for being so relatively casual in a discussion where the language needs to be precise.

                                          1. 1

                                            The topic is interesting and perhaps the argument once I know what it is but the presentation is pretty bad. There are far too many implicit assumptions all over the place. I think that’s why we are confused. (For example, why are we looking at pointers? How is that relevant to Turing-completeness??)

                                            Can someone say what exactly “C is not Turing-complete” means here?

                                            Here’s what I have reconstructed from the comments at the moments. Please help me if you’d also like to get to the bottom of this.

                                            What this author is trying to show is:

                                            Considering an idealised C11 which guarantees only the minimum from its spec, it is not possible to implement a Turing machine with a tape of size N.

                                            The author does not say what N is but the intended difficulty is supposed to relate to size. At first, this makes no sense: we could just make a program of size N. But this feels like cheating in other context too. We should be only allowed one program and on a real machine, it would just crash when it runs out of memory.

                                            Ok, so let’s revise that to

                                            Considering an idealised C11 which guarantees only the minimum from its spec, for any implementation of a Turing machine, there’s a TM program this implementation is unable to simulate for every amount M of memory.

                                            But now if we have M memory, can’t we just allocate it all using malloc? Is that not in the spec? But the post talks about the heap! Some people are talking about bignum. Is the trouble that even if we can allocate the memory, we won’t be able to read/write to all of it because we are unable to store the address them?

                                            [Stuff to fill in.]

                                            And therefore, our simulator always has a tape of size N << M?

                                            1. 2

                                              Say you have an infinite heap, or better yet a heap that can grow with you as your usage grows. You can then yes use malloc to allocate as much as you want, but having an infinite tape is only one part of it, being able to process the tape is the more important part. How would you process that malloced memory? You’ll do that by using pointers, and if the size of pointers is statically known at compile time, what happens when your malloced memory has more bytes than your pointers can possibly represent? (remember your heap can grow infinitely but sizeof(T *) is known at compile time).

                                              1. 1

                                                (For example, why are we looking at pointers? How is that relevant to Turing-completeness??)

                                                Because if C is not capable of unbounded memory then the question of whether it’s Turing complete is very easy to answer: no.

                                              1. 2

                                                I keep a bunch of markdown files. Its not really a wiki like the one shown here. Its mostly notes on how to redo things I’ve figured out before or (I’m hoping) short amount of text I can read to quickly get back up to speed. They are disjoint and don’t link much to each other.

                                                I later made a web interface for it but then pretty much never used it.

                                                1. 4

                                                  I saw @rain1 post nand game here about a month ago and quite liked it. Then I made this. (Not too sure how to tag it though. The original was just ‘games’.)

                                                  1. 2

                                                    This all means that I think it’d be more useful to everybody if I posted a more comprehensive article on how I optimized my model rather than just give some highlights here. Then it might help other beginners out there. Said article is about 3000 words long and will be going up next week.

                                                    My thoughts exactly. Thanks for noticing this and writing the second article!

                                                    Also, I’m probably slow/too used to other things but just in case it helps others: in the MiniZinc syntax, the name of the variable (or parameter) is the rightmost token on a line (between : and ;).

                                                    1. 2

                                                      Can you say what some of the main conclusions are? Or is this primarily a survey? E.g.,

                                                      this article identifies game facet orchestration as the central challenge for AI-based game generation

                                                      In particular, we identify the different creative facets of games

                                                      Are these the six facets: audio, visuals, levels, rules, narrative and gameplay? But the intro also suggests that only music (audio?) will be looked at. Or maybe its only meant as linguistic metaphor.

                                                      we propose how orchestration can be facilitated in a top-down or bottom-up fashion,

                                                      How?

                                                      we conclude by discussing the open questions and challenges ahead.

                                                      I’m guessing this is

                                                      • Combinatorial Explosion
                                                      • Learning the Mapping Between Facets
                                                      • Orchestration with Human Designers
                                                      • Evaluating Orchestration

                                                      envisioned several high-level orchestration processes along a spectrum between purely hierarchical top-down generation and organic bottom-up generation.

                                                      What are some examples of these processes?

                                                      (I’m thinking this is just my unfamiliarity with the topic but the last two sentences of the abstract are saying almost the same thing.

                                                      I wish abstracts in general gave more information about their conclusion like key pieces of information the authors would have liked to know before starting the project. Stuff that would have helped speed things up a lot.

                                                      1. 4

                                                        I’d describe it as a forward-looking survey. The starting point is that there’s a large existing body of work on procedural content generation, but they’re systems that generate one kind of thing at a time, like level generators, pixel-art makers, or procedural audio. Can you get to full-game generation by just plugging these kinds of generators together in some way? We discuss different architectures for orchestrating these kinds of generators: top-down, bottom-up, pipelined, etc., and survey existing systems that have already done some version of that.

                                                        The six facets we propose are ones you mentioned, yeah. There are many other ways you could slice game design, so this isn’t necessarily the ultimate metaphysical truth about games, that they’re made of exactly six kinds of stuff. But it’s based on looking at what kinds of things existing procedural generators currently generate (level generators are probably the most common, but there’s work in the other five too).

                                                        Yeah, the “orchestrate”, “jam”, etc. terminology is just a musical metaphor. We don’t only focus on game music here, but we use analogies like top down orchestra-style scoring/conducting, where every element of the overall system is given its centrally written part, vs. bottom-up jazz improvisation where they coordinate less hierarchically, etc. I can see how that can get confusing, sorry.

                                                        The survey part of the paper is in the case study section, where we give an overview of nine existing systems that generate more than one kind of thing in tandem (e.g. rules, levels, and music). We translate what each of them does to our language of 6 facets and different orchestration strategies, to try to get an idea of how all the existing stuff relates to each other, and what it doesn’t do yet. The first author (A. Liapis) made some colorful triangle facet-orchestration diagrams for that section that I quite like. They summarize what each system is doing in a kind of pictogram language, showing which facets the system generates and how they interrelate (e.g. some systems have a pipeline, some scrape content off the web, some ask for user input at certain points, etc.).

                                                        edit: I also wrote a short twitter thread earlier today with a more concise version of this explanation, for people who like twitter threads (I know, I know).

                                                        1. 1

                                                          Thanks! The figures in the survey are indeed really nice. (It wasn’t obvious before reading your comment that the arrows was the information about the orchestration process.)

                                                      1. 1

                                                        I’d also like to know What are you using for speech recognition underneath?

                                                        Looks like its something generic since text replacement is used for postprocessing to improve accuracy.

                                                                "please tab": "previous tab",
                                                                "fort worth": "forward",
                                                        

                                                        or even

                                                                "ghost app": "close tab",
                                                                "collect a blonde": "select tab 1",
                                                        
                                                        1. 11

                                                          Similar to Fibonacci, a piece of code that enlightened me was the simple PEG implementation, which is represented as a pair of mutually recursive procedures. I used to think of parsers as really difficult to understand, and hard to write. But the simplicity of PEG was an eye opener.

                                                          def unify_key(key, text, at):
                                                             if key not in grammar:
                                                                 return (True, at + len(key)) if text[at:].startswith(key) else (False, at)
                                                             rules = grammar[key]
                                                             for rule in rules:
                                                                 res, l = unify_rule(rule, text, at)
                                                                 if res: return (res, l)
                                                             return (False, 0)
                                                          
                                                          def unify_rule(rule, text, at):
                                                              for token in rule:
                                                                    result, at = unify_key(token, text, at)
                                                                    if not result: return (False, at)
                                                              return (True, at)
                                                          

                                                          Given a grammar as below, we try to unify the input string with the starting key – here expr. If To unify a key with the given string (unify_key), we check if the key is in the grammar. If it was not, then it is a plain token match, and we do simple string match. If not, we get the production rules defined in the grammar corresponding to the key, and try each rule one by one using unify_rule. We return as soon as any rule succeeds. The unify_rule is also simple. It gets the parts of the rule, and tries to match them in sequence using unify_key. If any of these fails, then return failure.

                                                          grammar = {
                                                              'expr': [
                                                                  ['term', 'add_op', 'expr'],
                                                                  ['term']],
                                                              'term': [
                                                                  ['fact', 'mul_op', 'term'],
                                                                  ['fact']],
                                                              'fact': [
                                                                  ['digits'],
                                                                  ['(','expr',')']],
                                                              'digits': [
                                                                  ['digit','digits'],
                                                                  ['digit']],
                                                              'digit': [[str(i)] for i in list(range(10))],
                                                              'add_op': [['+'], ['-']],
                                                              'mul_op': [['*'], ['/']]
                                                          }
                                                          

                                                          A driver

                                                          import sys
                                                          res, till = unify_key('expr', sys.argv[1], 0)
                                                          assert(till == len(sys.argv[1]))
                                                          print(res)
                                                          

                                                          Using it:

                                                          $ python3 peg.py '1+10/(3+2)'
                                                          True
                                                          $ python3 peg.py '1+10/x(3+2)'
                                                          Assertion failure
                                                          

                                                          While this implementation can have really bad performance due to back tracking, all one needs to do to make it linear is to decorate the procedures with @functools.lru_cache(maxsize=None), which memoizes the parsing, and makes parsing linear. While this does not implement the complete PEG syntax, it implements enough to be complete in terms of the grammars that can be represented (see Ford 2004 for details).

                                                          Edit: Thanks @asrp for finding that the original had issues.

                                                          1. 2

                                                            Tried it with something like

                                                            print unify_rule(['expr'], '1+10/(3+2)', 0)
                                                            

                                                            There seems to be quite a few typos in here

                                                            -   if key not in grammar: return (text[at:].starts_with(key), len(rule))
                                                            +   if key not in grammar: return (text[at:].startswith(key), len(key))
                                                            
                                                            -      if not result: return False
                                                            +      if not result: return (False, 0)
                                                            
                                                            -  return (True, len)
                                                            +  return (True, l)
                                                            

                                                            There must be more errors since it still only matches the first character of the expression.

                                                            I found confusing for both rule names and string token to be encoded as strings. The same goes for concatenation and ordered choice to both be encoded lists.

                                                            Thanks for bringing up this example, though!

                                                            1. 2

                                                              Sorry about that, and thank you so much for taking time to run it. I took the code from an old presentation, and seems I made errors while typing it in.

                                                              I have fixed it.

                                                              1. 1

                                                                Thanks for the new version! I understand what its trying to do better now.

                                                            2. 1

                                                              Thanks for the example! While PEGs are not familiar to me (I’ll need to look into them), there’s a lot of potential for minds to be blown in the parser world. Playing a few times with parser combinators did exactly that to me - if that’s something that’s not as familiar to you, then here’s a nice example in Scala.

                                                              1. 1

                                                                The parser combinators are a way to represent PEG directly in code. So you will find them quite familiar. I love combinator based parsing, they are quite powerful and enlightning – A while back, I did a few posts (1, 2, 3, 4, 5, 6, 7) on building a small concatenate language using Parsec (The original monadic combinator library in Haskell) for parsing. You may find them interesting.

                                                            1. 2

                                                              Looks like they didn’t run bibtex enough times. Here’s a version with citations fixed:

                                                              https://profs.info.uaic.ro/~stefan.ciobaca/faoc2016.pdf

                                                              Can anyone comment on the generality and efficiency of their method? I’ve only skimmed it very quickly but didn’t find discussion about that.

                                                              1. 3

                                                                I can’t tell you that as a non-specialist. What I can tell you is it’s based on matching logic that Rosu et al use in the K Framework. They used that to make a C compiler, lots of language specs, and a static analysis tool with low, false positives. They’re interesting to me since they operate in their own bubble of rewriting logic instead of Coq, Isabelle/HOL, etc. They built on Maude.

                                                                1. 2

                                                                  Interesting. I pretty much don’t know anything here. Thanks for the links.

                                                              1. 3

                                                                This is pretty nice. I just finished it.

                                                                Up to the ALU, you could sort of see the components you are building will be useful. But afterwards, I didn’t always really follow the reasoning through. I wish it let you design the instructions, or at least let you think about them. That seems like the more interesting/difficult part.

                                                                That and maybe a “hard mode” where you have access to all your previous components.

                                                                Would something like this work at a decent speed on real hardware (if you don’t mind the size) or is there normally too much optimization going on?

                                                                1. 2

                                                                  it is kind of like the minimum most simple CPU. A lot of extra features to speed it up can be added. Like a pipeline.

                                                                  1. 2

                                                                    Right, but how many times slower do we expect if this is used unmodified?

                                                                    The follow up question would be: what optimization to do if you could only pick 1 or 2?

                                                                1. 3

                                                                  https://blog.asrpo.com/

                                                                  I write sporadically, about what I think needs to be written about. It mostly contains bootstrapping/recreating things from scratch things at the moment. There’s a sort-of overview here.

                                                                  Its also intended as a reverse search engine of sorts where I try to find people interested in the same things.