1. 2

    I didn’t find any canonical name for the workflow used in Squeak Smalltalk so I called it JIT programming here.

    I know of this as “live coding”: it’s when you modify the code while the program is running, and the screen updates with the results of the code changes as you type. I checked Wikipedia, and the editors have chosen this name as the page title for the article. https://en.wikipedia.org/wiki/Live_coding. That’s my suggestion for the “canonical name” you were looking for.

    1. 2

      I think the Smalltalk development pattern is live coding, but it’s a specific kind of live coding that also embodies top-down implementation and is related to test-driven development. The idea in Smalltalk is that you start writing a method assuming that every other method that you need exists. As soon as some code that isn’t implemented is reached, you are presented with a class browser and asked to implement it before the program can continue. This implementation may, in turn, invoke methods that don’t exist and so you may not make much progress when you return. It’s an interesting workflow and one that guarantees that all of your required code paths are implemented first.

      1. 1

        From the wikipedia page and example, it seems that you’d need a mostly working program that’s then updated live for live coding, whereas for what I’m describing, more most of the session, you have a program that cannot even run to completion (without error).

        1. 2

          I know! That’s the central problem of live coding: how do you continue to provide useful output or feedback about program execution when the program contains errors? Live programming environments are very diverse, and there are lots of different (mostly partial) solutions to this problem. Your solution is very cool, thanks for showing it to us.

          Just to illustrate some of the diversity in the field, here are two radically different live coding environments:

          • Orca, a 2 dimensional language for live coding of music: https://hundredrabbits.itch.io/orca. It’s too weird to explain, just watch the video: https://www.youtube.com/watch?v=RaI_TuISSJE.
          • Hazel, a traditional-looking text based functional language designed by academic type theorists. How do they keep the live coding session running when there are errors? They use a projective editor to make it impossible to create syntax errors. They introduce the concept of “typed holes” to keep the program running when there are compile time type errors. https://hazel.org/

          If you tag your project as “live coding” then the live coding community will be able to find it more easily.

          1. 1

            “Live coding” does seem to be the consensus here, but like the sibling comment, I’m looking for something more specific. In my case, the answer to what output to provide on error is to halt.

            These are most definitely very interesting example (at different extremes) I wasn’t aware of before. Thanks for sharing. But they are also not example of the thing I’m looking for.

      1. 2

        This live-coding environment is extremely cool, and has the brilliant idea of visualizing the instruction pointer and stack. The tendency toward small squares of text is interesting - was it designed for PICO-8, by any chance?

        1. 1

          Yes! I was thinking of writing it in PICO-8 at first but then noticed that a full keyboard is needed. Even though, it is possible, it didn’t seem like the best first project anymore.

          I was thinking of just having a drop-down or pop-up of commands to select from and maybe a virtual keyboard, but that would discourage writing non-existing functions.

          I ended up using Pyxel with the PICO-8 palette.

        1. 6

          Believe it or not there are products that implement this: https://www.in10did.com/

          My use case was for terminal commands and using my phone as an audio terminal (termux and espeak).

          I recorded all my key presses on my laptop including non-printing commands like crtl, alt, esc, etc, built a key map based on weighted finger positions, flashed a new key map onto the thing and it nearly worked. Unfortunately anything more more complex than ed had too much state I needed to keep in mind when working, so I needed to look at the screen anyway.

          Which brought me to the solution that actually works: https://en.wikipedia.org/wiki/MessagEase along with emacs.

          I can enter all the weird symbols I want using software, and it’s kind of usable for entering text. Using that inside temux with emacs I have something that is good enough to edit files and run commands for any server that I could possibly want.

          If I wanted to take notes though both are terrible. I’d look into stenography, but with how good speech-to-text has become I’d just dictate to an app with a red button.

          1. 1

            Do you have longer write-ups of your set up and/or videos of it running? I am extremely interested in an audio terminal setup.

            1. 1

              Unfortunately no.

              The setup was always buggy as hell on regular bash+linux. I vaguely remember some sort of C monstrosity that dispatched espeak processes with each key press, and another one that killed whatever was running when a new key was pressed. I never managed to get anything that wasn’t a full text line to audio in termux.

              What did work for audio terminal is running a shell in emacspeak. That’s how I got to the point that I realized that it was too much mental overhead for me to use a chorded keyboard along with an audio only for emacs interface, and the only programs that worked well were the oldest unix utilities that used to output to actual teletypes, never was the terseness of ed more appreciated.

              Again that was on Linux only with the keyboard connected by bluetooth. Currently emacspeak does not compile for termux. If you know enough about emacs to compile it for termux that would help the project tremendously.

              That said I am one of the few people to genuinely use ed from a shell in emacs which is something I’m both proud and ashamed of.

              1. 1

                I’m actually more interested in your keybindings and how your interactions with it when it did work. For the audio output part, it sounds like your relied on the underlying utility, like ed, being nice about it’s output. But what of the keyboard input part? Did that work well?

                Currently emacspeak does not compile for termux.

                I’m a bit baffled by what this means and why it’s needed. What do you mean by “compile for”? Also, how important is it to use termux versus another shell or terminal?

                I’m make espeakui which has a Espeaker class that is IMO a better API for espeak. Would this help with the bash+linux approach? You can start, stop and pause speech easily without having to kill an espeak process. I use it to change speech rate mid sentence. It uses the same underlying speaklib library as espeak (but can also use espeak-ng with minimal change).

                1. 1

                  The key chords worked as expected. All the smart stuff was done on board the keyboard’s micro controller with only regular key presses being sent out by bluetooth. So the computer couldn’t tell the difference between it and a regular keyboard. I don’t have the map any more and I was trying naively to use the same key bindings as I did on a regular keyboard. The amount of mental state I needed to keep track of was extremely high.

                  For my use case emacspeak is a better fit than trying to use a terminal and when I finally got it working on my main machine all the projects I’d been trying to look at became pointless.

                  I’m a bit baffled by what this means and why it’s needed. What do you mean by “compile for”? Also, how important is it to use termux versus another shell or terminal?

                  Termux is an android terminal emulator and Linux environment, my use case was to try and build an audio only work station on mobile so I could use the same setup where ever I was. I did not succeed, I did get to the point where I had emacspeak + terminal working on my desktop along with a chorded keyboard. The combination was a lot less usable than I thought it would be.

                  Ultimately I moved to an eink android tablet + keyboard + battery. The setup lasts me weeks between charges and it is only marginally more difficult to carry around than a regular laptop. Since emacs works under termux I have the same setup on all my machines for on the go editing. It is rather pleasant to work outdoors in the bright sunshine and for ‘serious’ work I ssh into my home network.

                  I’m make espeakui which has a Espeaker class that is IMO a better API for espeak. Would this help with the bash+linux approach?

                  From a cursory look, no. You need to spawn a process for every letter press and every word. Basically have a look at what emacspeak does and you’ll see something I’m 90% happy with for coding on.

                  That said the use case for that software is mostly covered by the following line of bash:

                  TMP=$RANDOM; xsel | tr '\n' ' ' | espeak-ng -p 100 -s 950 -v male7 -w /tmp/$TMP.wav; mplayer /tmp/$TMP.wav
                  

                  I will give yours a try later since I never did manage to get espeak to display the text being read currently, and never cared enough to look into how to solve the problem.

                  Not sure if that’s any help at all.

                  1. 1

                    So key chords worked just as well as a keyboard? It wasn’t much slower to use one?

                    I’ve only looked at emacspeaks briefly and that was a long time ago. Isn’t it basically a screen reader with emacs? Any significant difference between using that and, say, yasr or espeakup (other than being inside emacs)?

                    The combination was a lot less usable than I thought it would be.

                    Ah, that’s unfortunate. It sounds like you were mostly going the “regular” terminal and screen reader route. I want to know if there’s some design that would specifically be good for audio linux with a keyboard (or other input) with fewer keys.

                    That said the use case for that software is mostly covered by the following line of bash:

                    Yes, you can do that (with mplayer -af scaletempo) but for large webpages the wave file takes quite some time to generate and there’s significant audio distortion at >2x speed (which might be why you set your intial speed to 950?). I do still use the pipe-to-mplayer method on a phone though.

                    But I was pointing at the library rather than the application. But it looks like you want a mostly completed screen reader, which indeed it isn’t. Its better suited for building “custom” audio applications.

            2. 1

              Huh, MessageEase looks interesting, thanks! Though I don’t know how much of a fit it is for non-keypad phones. Taking notes via speech recognition in a noisy environment would probably not be too great, and you’d need to summarize them later.

              1. 2

                Huh, MessageEase looks interesting, thanks! Though I don’t know how much of a fit it is for non-keypad phones.

                It works vastly better on touch screens. Typing one symbol at a time is still much slower than swiftkey like swipes for words but for accuracy in typing it beats anything I’ve tried, including phones with physical keyboards and chorded keyboards.

                Taking notes via speech recognition in a noisy environment would probably not be too great, and you’d need to summarize them later.

                What you can do with audio engineering today is out of this world: https://www.youtube.com/watch?v=hrQ_2JhEKpY

                The last time I played around with speech to text was when Mozilla released their audio thing way back when. Using it on a bunch of librevox recordings it averaged less than 1 error per thousand words.

            1. 13

              Author here. Ask me anything!

              1. 9

                just wanted to say congratulations on what you’ve got so far; it was interesting for sure, and I’m looking forward to future parts.

                it makes me wonder if you’re basically modeling parallel dataflow; linear types probably means each stack can be executed pretty safely in parallel, yes? the moving values into a new stack feels very “spawn a thread” to me.

                1. 5

                  Thanks!

                  Yes, that’s absolutely correct. Operations on separate stacks could trivially be parallelized by a properly designed runtime. Eventually, high-level Dawn code could be compiled to OpenCL or CUDA, similar to in Futhark. Alternatively, a compiler to assembly for a superscalar CPU could interleave operations on the different stacks to take advantage of instruction-level parallelism.

                2. 6

                  This looks very interesting! I’ll eagerly await the next installment and look forward to playing with the language.

                  Reading the post, I wondered how the stack names are scoped. In the example code, one can reasonably (I think?) guess that $x, $y, and $z are scoped to the function whose {spread} operation created them, or maybe they are bound to the current stack. But looking at the comment you linked to in an earlier discussion about I/O, it seemed like there were references to named stacks like $stdout from some external scope.

                  Perhaps I’m wrong to assume that “scope” is even a relevant concept. But presumably there has to be some way to avoid stack name collisions.

                  (Edit) …Huh, maybe I am wrong to assume that scope matters. I am still trying to wrap my brain around it, but maybe if the language can guarantee linearity across the whole application, you don’t even have to care about name collisions because if there is already a $x stack from some calling function, it doesn’t matter if you reuse it and push values onto it as long as you’re guaranteed to have removed them all by the time your caller looks at it again (assuming your caller wasn’t expecting you to leave behind a value on that stack, but then “leaves behind one value on $x” would be part of your function signature).

                  I’m not quite sure that actually works, but now I’m even more eager to read the next post.

                  1. 4

                    But presumably there has to be some way to avoid stack name collisions.

                    Yes, there is. Take for example the expression: {$a swap} where swap is defined as

                    {fn swap => $a<- $b<- $a-> $b->}
                    

                    Expanded, this becomes

                    {$a $a<- $b<- $a-> $b->}
                    

                    Or, equivalently,

                    {$a {$a push} {$b push} {$a pop} {$b pop}}
                    

                    Without some mechanism to handle the stack collision between the inner and outer $a stack, this would not behave properly. Since we want functions to behave the same way regardless of what stack context they are executed from, that would be unacceptable. So this is handled by checking for nested stack name collisions and renaming the inner stack. So the latter would effectively be rewritten to

                    {$a {$$a push} {$b push} {$$a pop} {$b pop}}
                    

                    In the existing type checker prototype, renamed stacks are distinguished by a prefix of more than one $. Then, if one of these temporary stack names escapes up to the inferred type for a user-defined function, an error is raised. This ensures expected behavior while ensuring we don’t need to monomorphize each function to operate on different stacks.

                  2. 4

                    Your introduction to Dawn was clear and compelling, really excited to follow along with Dawn’s development.

                    {spread $x $y $z} is syntactic sugar

                    Do you intend to expose a macro system to Dawn programmers?

                    Conceptually, these named stacks can be considered to be different parts of one big multi-stack.

                    How are Dawn’s named stacks represented internally? I don’t have much familiarity with stack-based languages, but it seems like it would be straightforward to understand how the machine runs a program just by reading the source. Is that lost with the introduction of named stacks, or is there a mental mapping that can be made?

                    Dawn is really exciting!

                    1. 2

                      And to answer your other questions, in the existing interpreter the named stacks are a Map String (Stack Val). The first compiler, which will be through translation to C, will use static analysis (basically the inferred types) to turn all stack slots, regardless of which stack they are on, into function parameters.

                      Eventually, I plan to write an assembler in/for Dawn, in which stack names will correspond to architecture-specific registers.

                      1. 2

                        Thanks!

                        I’m undecided on syntactic macros, but the plan is absolutely to provide meta-programming. I haven’t prototyped this at all yet, but I hope and expect for compiler passes to be implemented in something I’ve been calling meta-Dawn in my notes—a form of staged compilation. The plan is for Dawn to be its own intermediate representation. We’ll see how that works out in practice, of course.

                      2. 2

                        I’m looking forward to the rest of the series. Is there any change you could put an rss/atom feed on the site? It’s a much nicer experience than subscribing to a mailing list.

                          1. 1

                            Thanks!

                          2. 2

                            Thanks for the suggestion. I’ll take a look at what that entails.

                          3. 1

                            First of all, it’s a really interesting concept! One question about the linear typing aspect though: What happens if multiple functions want to access the same read-only data structure? I assume that for small values clone just copies by value, but what if the data structure is prohibitively expensive to copy? Are some values cloned by reference? If yes, don’t you need to track how many readers / writers access the data so that you know when to free the memory?

                            I guess another way of phrasing this question would be: How do you handle the more complex cases of borrowing data with the semantics described in the post? Rust’s borrow checker is of course useful even for simple cases of stack-allocated values, but it really shines (and this is where its complexity lies) in cases of more complex heap-allocated data structures. (And of course, even Rust with its borrow semantics needs Rc/RefCell as escape hatches for situations where these guarantees cannot be statically checked, is there something comparable in Dawn?)

                            1. 1

                              Great question! I’m going to get to that in a future post, but there is a solution, and it doesn’t require a separate borrow checker.

                            2. 1

                              Nice! Also looking forward to future parts.

                              a way to bind values to local named variables. Unfortunately, this breaks one of the primary advantages of concatenative notation: that functions can be trivially split and recombined at any syntactic boundary—i.e. their factorability.

                              You gave an example of how Dawn still has this but can you give an example of why Factor or Kitten do not? Or more generally, why a concatenative with bind values to local named variables cannot.

                              Here’s a example of Fibonnaci from Flpc (Disclaimer: I’m the author).

                                  [ 1 return2 ] bind: base-case
                                  [ newfunc1 assign: i
                                    pick: i pushi: 3 < pushf: base-case if
                                    pick: i 1 - fib pick: i 2 - fib + return1
                                    ] bind: fib
                              

                              Any part of the body can be split off. For example

                                  [ 1 return2 ] bind: base-case
                                  [ pick: i 1 - ] bind: one-less
                                  [ pick: i 2 - ] bind: two-less
                                  [ newfunc1 assign: i
                                    pick: i pushi: 3 < pushf: base-case if
                                    one-less fib two-less fib + return1
                                    ] bind: fib
                              
                                  [ 1 return2 ] bind: base-case
                                  [ pick: i s21 - ] bind: recurse-fib
                                  [ newfunc1 assign: i
                                    pick: i pushi: 3 < pushf: base-case if
                                    1 recurse-fib 2 recurse-fib + return1
                                    ] bind: fib
                              

                              For your example, this would be

                              [ newfunc3 assign: z assign: y assign: x
                                pick: y square pick: x square + pick: y abs - return1 ] bind: f
                              

                              (z needs not be dropped explicitly since return1 takes care of that.)

                              1. 1

                                In your example of splitting up fib, what happens if you reuse one-less in another function? Does the source essentially get inlined, so that pick: i refers to the assign: i? If so, then this appears to be similar to Dawn, but without the linearity restriction.

                                In Factor and Kitten, I don’t believe local variables work like that, though. I believe they behave more like they do in most existing languages, e.g. Python, where the pick: i in one-less would be an undefined variable error.

                                1. 2

                                  In your example of splitting up fib, what happens if you reuse one-less in another function? Does the source essentially get inlined, so that pick: i refers to the assign: i?

                                  Yes, that’s exactly right.

                                  In Factor and Kitten, I don’t believe local variables work like that, though. I believe they behave more like they do in most existing languages, e.g. Python, where the pick: i in one-less would be an undefined variable error.

                                  Oh I see. I’m wondering if it’s because of scoping. With what I’m doing and maybe what you’re doing, you can’t (easily) get lexical scoping whereas the other way you could.

                            1. 1

                              How well do online conferences work? I’ve read good things about how FOSDEM was organized but only after it was over and too late to attend!

                              Watching recordings of other conferences, quality seems to really vary but that’s still not the same as expericing the conference live.

                              1. 1

                                I attended two online conferences in 2020 & enjoyed both. You do miss out on the “meeting people in the hallway” aspect, but being able to dip in and out of talks & catch bits you’re interested in without having to leave the office is great. I can see a future for both remote and in-person conferences - the former are so much better for people with disabilities, or those of us who simply don’t have the time (or money!) to take days / a week for a conference.

                                The same goes for speakers too: you can get some great people to talk at your conference if they only need to show up for an hour or two & get the option to take in as much of your conference as they want instead of having to take days out of their schedule.

                              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.)