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.

              1. 0

                This is ill-advised.

                You cannot define 1/0 and still have a field. There’s no value that works. Even when you do things like the extended real numbers where x/0 = infinity, you’re really just doing a kind of shorthand and you acknowledge that the result isn’t a field.

                You can of course define any other algebraic structure you want and then say that operating on the expression 1/0 is all invalid because you didn’t define anything else and no other theorem applies, but this is not very helpful. You can make bad definitions that don’t generalise, sure, definitions that aren’t fields. But to paraphrase a famous mathematician, the difficulty lies not in the proofs but in knowing what to prove. The statement “1/0 = 0 and nothing else can be deduced from this” isn’t very interesting.

                1. 1

                  Could you explain why, formally, defining 1/0=0 means you no longer have a field?

                  1. 7

                    I want to make an attempt to clarify the discussion here because I think there is some substance I found interesting. I don’t have a strong opinion about this.

                    The article actually defines an algebraic structure with three operators: (S, +, *, /) with some axioms. It happens that these axioms makes it so (S, +, *) is a field (just like how the definition of a field makes (S, +) a group).

                    The article is right in saying that these axioms do not lead to a contradiction. And there are many non-trivial such structures.

                    However, the (potential) issue is that we don’t know nearly as much about these structures than we do about fields because any theorem about fields only apply to (S, +, *) instead of (S, +, *, /). So all the work would need to be redone. It could be said that the purpose of choosing a field in the first place is to benefit from existing knowledge and familiar expectations (which are no longer guarantteed).

                    I guess formally adding an operator means you should call it something else? (Just like how we don’t call fields a group even though it could be seen as a group with an added * operator.)

                    This has no bearing on the 1/0 = 0 question however, which still works from what’s discussed in the article.

                    1. 1

                      As I understand it, you’ve only defined the expression 1/0 but you are saying that /0 isn’t shorthand for the multiplicative inverse of 0 as is normally the case for /x being x^-1, by definition. Instead, /0 is some other kind of magical non-invertible operation that maps 1 into 0 (and who knows what /0 maps everything else into). Kind of curious what it has to do with 0 at all.

                      So I guess you can do this, but then you haven’t defined division by zero at all, you’ve just added some notation that looks like division by zero but instead just defined some arbitrary function for some elements of your field.

                      If you do mean that /0 is division by zero, then 1/0 has to be, by definition, shorthand for 1*0^-1 and the arguments that you’ve already dismissed apply.

                      1. 4

                        The definition of a field makes no statements about the multiplicative inverse of the additive identity (https://en.wikipedia.org/wiki/Field_(math)#Classic_definition). Defining it in a sound way does not invalidate any of the axioms required by the field, and, in fact, does define division by zero (tautologically). You end up with a field and some other stuff, which is still a field, in the same way that adding a multiplication operator on a group with the appropriate properties leaves you with a group and some other stuff.

                        The definition of the notation “a / b => a * b^-1” assumes that b is not zero. Thus, you may define the case when b is 0 to mean whatever you want.

                        That people want to hold on to some algebraic “identities” like multiplying by the denominator cancels it doesn’t change this. For that to work, you need the assumption that the denominator is not zero to begin with.

                        1. 1

                          In what way, whatever it is you defined /0 to be, considered to be a “division”? What is division? Kindly define it.

                          1. 3

                            Division, a / b, is equal to a * b^-1 when b is not zero.

                            1. 2

                              And when b is zero, what is division? That’s the whole point of this argument. What properties does an operation need to have in order to be worthy of being called a division?

                              1. 3

                                Indeed, it is the whole point. For a field, it doesn’t have to say anything about when you divide by zero. It is undefined. That doesn’t mean that you can’t work with and define a different, but still consistent, structure where it is defined. In fact, you can add the definition such that you still have the same field, and more.

                                edit: Note that this doesn’t mean that you’re defining a multiplicative inverse of zero. That can’t exist and still be a field.

                                1. 1

                                  In what way is it consistent? Consistent with what? As I understand it, you’re still saying that the expression 1/0 is an exception to every other theorem. What use is that? You still have to write a bunch of preconditions, even in Coq, saying how the denominator isn’t zero. What’s the point of such a definition?

                                  It seems to me that all of this nonsense is about not wanting to get an exception when you encounter division by zero, but you’re just delaying the problem by having to get an exception whenever you try to reason with the expression 1/0.

                                  1. 3

                                    I mean that the resulting structure is consistent with the field axioms. The conditions on dividing by zero never go away, correct. And yes, this is all about avoiding exceptions in the stack unwinding, programming language sense. The article is a response to the statements that defining division by zero in this way causes the structure to not be a field, or that it makes no mathematical sense. I am also just trying to respond to your statements that you can’t define it and maintain a field.

                                    1. 1

                                      It really doesn’t make mathematical sense. You’re just giving the /0 expression some arbitrary value so that your computer doesn’t raise an exception, but what you’re defining there isn’t division except notationally. It doesn’t behave like a division at all. Make your computer do whatever you want, but it’s not division.

                                      1. 5

                                        Mathematical sense depends on the set of axioms you choose. If a set of axioms is consistent, then it makes mathematical sense. You can disagree with the choices as much as you would like, but that has no bearing on the meaning. Do you have a proof that the resulting system is inconsistent, or even weaker, not a field?

                                        1. 1

                                          I don’t even know what the resulting system is. Is it, shall we say, the field axioms? In short, a set on which two abelian operations are defined, with two distinct identities for each abelian operation, such that one operation distributes over the other? And you define an additional operation on the distributing operation that to each element maps its inverse, except for the identity which instead is mapped to the identity of the distributed-over operation?

                                          1. 2

                                            It’s a field where the definition of division is augmented to include a definition when the divisor is zero. It adds no new elements, and all of the same theorems apply.

                                            1. 1

                                              I’m bailing out, this isn’t a productive conversation for either of us. Sorry.

                                              1. 1

                                                You are correct. The field axioms are all still true, even if we extend / to be defined on 0.

                                                The reason for this is that the axioms never “look at” any of the values x/0. They never speak of them. So they all hold regardless of what x/0 is.

                                                That said, even though you can define x/0 without violating axioms it doesn’t mean you should. In fact it seems like a very bad idea to me.

                          2. 1

                            That doesn’t make it not a field; you don’t have to have a division operator at all to be a field, let alone a division operator that is defined to be multiplication by the multiplicative inverse.

                            1. 1

                              What is division?

                              1. 1

                                zeebo gave the same answer I would give: a / b is a multiplied by the multiplicative inverse of b when b is not zero. This article is all about how a / 0 is not defined and so, from an engineering perspective, you can define it to be whatever you want without losing the property that your number representation forms a field. You claimed that defining a / 0 = 1 means that your numbers aren’t a field, and all I’m saying is that the definition of the division operator is 100% completely orthogonal to whether or not your numbers form a field, because the definition of a field has nothing to say about division.

                                1. 1

                                  What is an engineering perspective?

                                  Also, this whole “a field definition doesn’t talk about division” is a bit of misunderstanding of mathematical idioms. The field definition does talk about division since “division” is just shorthand for “multiplicative inverse”. The reason the definition is written the way it is (excluding 0 from having a multiplicative inverse) is that giving zero a multiplicative inverse results in contradictions. When you say “ha! I won’t let that stop me! I’m going to define it anyway!” well, okay, but then either (1) you’re not definining a multiplicative inverse i.e. you’re not defining division or (2) you are defining a multiplicative inverse and you’re creating a contradiction.

                                  1. 1

                                    (I had a whole comment here, but zeebo is expressing themselves better than I am, and there’s no point in litigating this twice, especially when I feel like I’m just quoting TFA)

                                    1. 1

                                      Me too, I’m tapping out.

                      1. 1

                        Great article!

                        I’m a bit late to the party because I wanted to try this one myself by just eyeballing and refactoring.

                        Java concurrency

                        The first thing that confused me was the concurrency model. The methods are supposed to be atomic because of synchonized but wait obviously make it non-atomic (the operation is broken between before the wait call and after). Then what does notify do? Does it pause the thread that called notify? Or is the woken up thread paused but next to execute?

                        Looking at the first few Google results didn’t get me a clear answer to this.

                        I assumed the former and this could make a lot of take thread wake each other up, block on notify and then all continue pushing occupied into the negatives and return invalid values.

                        I think your spec assumes the latter.

                        Concurrency and testing
                        if random.randint(0, 10000) == 1234:
                            cause_error
                        

                        would also be hard to test, need many runs and still have a chance of missing the error. This feels like a missing feature of the testing tool. For any non-deterministic part, the test should be allowed to pick the “random” values. In this case, the test should be allowed to pick which thread notify wakes up. And which thread runs next if there is a choice.

                        This is not saying anything about the difficulty in implementing such a testing tool but it also seems necessary if there’s going to be non-deterministic parts.

                        1. 3

                          Then what does notify do? Does it pause the thread that called notify? Or is the woken up thread paused but next to execute?

                          I assumed the former and this could make a lot of take thread wake each other up, block on notify and then all continue pushing occupied into the negatives and return invalid values.

                          I think your spec assumes the latter.

                          To my understanding it’s neither: notify wakes up a thread but does not execute it, nor does it guarantee it’ll be executed next. It just adds the woken thread into the scheduled pool.

                        1. 3

                          You may already be aware of this but here’s an example about composability, especially with respect to editing parents. Its not primarily “for making UIs”.

                          The Alto & Squeak environments get close, and so does Tcl/Tk’s ‘wish’ interpreter, but we’re not there yet.

                          For each of these, which of your items are missing?

                          The beginning of some work along these lines is here: https://github.com/enkiv2/misc/tree/master/kamui

                          Can you post some screenshots and/or describe and discuss your current implementation, even if not final? It would help clarify some of your implicit assumptions about the problem and model. (For example, what are things you would consider a widget and not a widget.)

                          Every object has a visual representation.

                          Why only one? Or do you mean at least one?

                          Every visual representation corresponds to an object.

                          Also why only one? What about visually nested things? (Is a representation something already rendered or an abstract description?)

                          Edit: Also, can you post some links to some examples of UIs on TV you consider good examples of what you want to do?

                          1. 6

                            For each of these, which of your items are missing?

                            I consider Smalltalk to have too high an initial learning overhead for this purpose (since my goal is to have the composability of graphical elements be an ‘invitation’ to programming in general for casual users).

                            Tk has a lower initial learning overhead but there are a lot of inconsistencies in how different widgets work (along with problems like a single-thread model), and no system has been written using Tk that does composability in the natural way smalltalk environments do. (I attempted a TCL/TK implementation many years ago. It’s briefly described here. It quickly became unmaintainable, and the widgets were not flexible enough for my liking.)

                            Can you […] describe and discuss your current implementation

                            Sure!

                            Io is an extremely simple homoiconic language with a prototype-based object system. It looks a lot like rebol. I chose it because an important part of making a language look understandable to non-programmers is conceptual simplicity, and Io’s pointfree style and message-passing-like behavior is a good fit for a context where a lot of the coding is glue between objects.

                            Because of certain features I wanted that stock Io didn’t have and certain behaviors that might be bugs (and because Io is not maintained), I decided to write my own implementation in a language with primitives that are a better match for the parts of Io I consider important for this task.

                            Since Io has a prototype-object system and not a class-object system, exploration through cloning a working object and modifying its guts is possible at run time. I expect this to be a normal pattern for experimentation.

                            I have defined the ‘widget’ object as having a position, size, and bitmap. Any widget inherits these properties. So, any widget has a visual representation, in the sense that it has a bitmap & that bitmap gets blitted to the display at render time. (Of course, it can be transparent, or whatever.) If you look at my implementation, I’ve also got some logic for visually nested things: children are positions at offset with respect to their parents, always at a higher layer, and their position affects the computed size of their parent.

                            The importance of widgets having a visual representation is that the expected method of modifying a widget is by selecting it in the interface and inspecting its implementation. So, ideally, every live object would be a widget whose visual representation indicates its state. (I don’t plan to make non-widget objects impossible, but it’s bad form, since they’re going to be harder to find and change.)

                            Unfortunately, I haven’t gotten to the point of having anything render. Stock Io’s various graphics bindings won’t build for me, & my reimplementation has a ways to go. Screenshots might be misleading, though: my goal is to have a system that’s extremely mutable in its form. Squeak’s smalltalk-based desktop is a good representation of the kind of thing I’m aiming for.

                            can you post some links to some examples of UIs on TV you consider good examples of what you want to do?

                            I’ll dig up some. Alternately, TVTropes has some lists.

                            Think along the lines of the way viruses are depicted in the movie Hackers – as graphical objects with apparent properties. Obviously, viruses have other reasons for not exposing their nature graphically – the whole point of them is to be hidden from & hostile to the end user – but having a graphical representation that matches the end user’s mental model of a task (as opposed to skeuomorphism, wherein it matches a programmer’s model of a device that used to accomplish a similar task, or the current norm, where the UI maps onto the structure of the programmer’s code) is desirable, even though it can’t be attained unless the end user writes it themselves. (The goal here is to minimize the artificial friction users encounter in making their computing environment a natural reflection of their mind.)

                            1. 3

                              Thanks, that’s a very interesting read and I understand better now.

                              I have defined the ‘widget’ object as having a position, size, and bitmap.

                              Does this mean everything will mainly be raster (as opposed to vector). What about other visual transformations? How (un)important are they? Or maybe my question actually is whether composition will mainly be on functionality or visual appearance as well?

                              (I don’t plan to make non-widget objects impossible, but it’s bad form, since they’re going to be harder to find and change.)

                              Hmm…what about overlays for viewing and editing widgets, like corners, text cursors and bounding boxes? I guess they could all be their own separate overlay widgets.

                              Unfortunately, I haven’t gotten to the point of having anything render.

                              That might not be an issue for prototyping, except possibly for testing speed. To try it out, you might have a mock “render” loop that just prints out everything that should be drawn (and where) for that frame.

                              And some random questions about the implementation you linked too.

                              I’m a bit concerned about calculateBbox and widgetLint’s potential resource (time) consumption.

                              For setParent, shouldn’t the current parent, if there is one, also remove “self” as a child?

                              What about user input? Do they just get passed up the tree from the child? What if you want to globally change keybindings afterwards? Does the prototype-object system help with this or makes it harder?

                              A lot of what I’ve written here is probably too early to think about (although something like vector vs raster is pretty hard to change later on).

                              I definitely agree with Squeak not being inviting enough. I haven’t used Tk all that much despite having made this but did find issues with its internal model a few times.

                              I guess if Io is simple enough, it can even be part of the thing that’s to be rewritten/customized.

                              I hope you go much further with these ideas!

                              1. 4

                                Does this mean everything will mainly be raster

                                In the particular system I’m writing, I’m only supporting raster, because I am lazy. I’m adopting the model from Menuet, because rendering becomes trivial: clear buffer, blit existing bitmaps onto buffer at given positions in Z order, flip. (I have the necessary information to later optimize out totally occuluded stuff, or keep a dirty bit in order to determine what parts of the display should be updated, if performance becomes a problem, but since unlike the Applet system in Java the user code doesn’t re-draw on visibility, it actually will be less of an issue, with the downside being the occasional half-drawn widget being rendered for one frame.)

                                whether composition will mainly be on functionality

                                Composition is performed through message-passing. My goal is to provide the GUI equivalent of unix pipes.

                                I guess they could all be their own separate overlay widgets.

                                Yeah. It cleans the system up conceptually if there are no “special” classes of widgets that don’t count as widgets.

                                To try it out, you might have a mock “render” loop that just prints out everything that should be drawn (and where) for that frame.

                                The stage I’m at in development is concerned with rewriting Io so that it can actually run my program.

                                I’m a bit concerned about calculateBbox and widgetLint’s potential resource (time) consumption.

                                This is a proof of concept system & so I’m not concerned with performance at all. If major performance problems appear, I’ll look at some of the low-hanging fruit (like the Io intepreter re-parsing and re-tokenizing the entire expression over and over) first.

                                What about user input? Do they just get passed up the tree from the child?

                                Yes, from the focused child.

                                What if you want to globally change keybindings afterwards?

                                That’s not a facility I’m supporting, though generally speaking you’d only be creating key bindings for widgets that use them, so having layers of conflicting triggers would be bad form.

                                Does the prototype-object system help with this or makes it harder?

                                It depends on how you use it. The inheritance hierarchy is distinct from the widget-packing hierarchy, and both are used for message-handling (of which input handling is a part). It’s definitely possible to make a huge mess with this.

                                A lot of what I’ve written here is probably too early to think about

                                I actually made a lot of these decisions before I started writing any code, so you’re absolutely right to ask these questions. Because I expect to have between zero and one users, performance isn’t a priority, and I’m ignoring it in favor of making everything structurally & conceptually straightforward.

                                if Io is simple enough, it can even be part of the thing that’s to be rewritten/customized.

                                Io is pretty bare-bones and I’m looking to write as much as possible in it, as opposed to Tk, where complex things like the text entry widget are basically exposed from FFI. I probably won’t expose the actual parser to be rewritten, though.

                                1. 1

                                  I’m curious – has there been any development on this since? Would you be interested in any volunteer work? I’ve got some time to kill, as I don’t start work for a while. PM me if you’re interested.

                                  1. 2

                                    I haven’t done any work on this for a while, no. I’d love somebody to pick up where I left off, or work on their own projects inspired by this.

                                    I’m likely to work on it very intermittently. I have a lot of side projects, and with the current load at work, I get a chance to commit to one maybe once every few weeks. This one is complicated, since I’m writing a whole programming language interpreter for it, so it’ll probably get less love than my simpler projects.

                                    1. 2

                                      I’ve started poking at it in https://github.com/tekknolagi/kamui (having filtered out the subfolder from your misc repository). I’m very new to Io and this idea, so we’ll see if I get anywhere at all.

                          1. 2

                            I’m going to give suggestions in a different direction and hope it helps anyways. I haven’t tried these Windows newer than 7 or in some case 8.

                            1. I don’t know if “Windows desktop workspace” is the same as a remote desktop connection. If yes, you can use a linux client like rdesktop to connect to it and run it in a window from your host (Mac or Linux). So you can work in your host and paste to/from Windows whose remote desktop’s window. At least for rdesktop, I remember clipboard across the two “just worked”.

                            2. If that’s not an option, at any time, Super+r (for run), wait a bit, type “magnify”, press enter. Click the + if needed.

                            You may need something with desktop effects (I forget the actual name, Aero?) enabled to work

                            This worked at least until Win 8. Same thing with “magnify” replaced by “narrator”.

                            1. You can copy the text from dialog boxes by selecting the box and pressing Ctrl-C.

                            2. From a regular Windows command line, you can “mark” and then copy/paste to them. “Mark” is one of the options if you click on the icon on the top left. It still annoying to use.

                            3. Even though it does less, I like Minimalist GNU for Windows better than Cygwin. (And possibly easier to setup with less permissions but its been a while.) I’d probably try to use ssh from the command line within MinGW.

                            1. 1

                              As I miss low-level Ring0 debuggers like SoftIce, I clicked this title way too fast.

                              Now I’m disappointed. Are we going to see any other software to interrupt your machine (and inspect/control however you like) in the future?

                              1. 1

                                As I miss low-level Ring0 debuggers like SoftIce,

                                It was hard to tell from the video what exactly was going on. The wikipedia page two links away describes it as

                                SoftICE is a kernel mode debugger for Microsoft Windows up to Windows XP. Crucially, it is designed to run underneath Windows such that the operating system is unaware of its presence. Unlike an application debugger, SoftICE is capable of suspending all operations in Windows when instructed. For driver debugging this is critical due to how hardware is accessed and the kernel of the operating system functions. Because of its low-level capabilities, SoftICE is also popular as a software cracking tool.

                                So, one main point for my project is to have a live editor for the process/program being “debugged”. I don’t know how machine-level inspection and control would help here.

                                Are we going to see any other software to interrupt your machine (and inspect/control however you like) in the future?

                                What do you mean by any other software? The idea was to make a debugger from scratch from syscalls and up (well, almost since a wrapper is used).

                                If instead you mean run multiple debuggers at once, currently ptrace prevent more than one from attaching to one process. I did think of attaching a debugger to the debugger itself though.

                                From your experience, is it quick to make machine level interrupts and inspectors? And then to get the desired macroscopic effects? (For me, assembly was already borderline

                              1. 3

                                I wasn’t aware of this project. Thanks for posting it here! (Also, welcome back.)

                                I will be writing weekly or semiweekly blog posts summarizing the progress since the last update.

                                Aside from the progress summary blog posts, I will try to distill what I cover on stream into standalone articles.

                                Did they manage to do this in the end? That would be the most interesting part to me.

                                The closest thing I’ve found is this but that’s more of a list/index than articles.

                                1. 10

                                  There are a lot of definition errors which may also be factual errors in this article. I feel this could lead to a lot of confusion (which leads to more articles including that confusion which would lead to more confused readers, …).

                                  tl;dr We’ve typically considered it a deal-breaker to discover that an algorithm we care about is NP-hard.

                                  Algorithms are not NP-hard, problems are. You can have more than one algorithm (quicksort, mergesort, bogosort) for the same problem (sorting).

                                  Algorithms have inherent complexity (worst-case running time among others). Problem have inherent difficulty. Algorithms do not have any associated notion of difficulty.

                                  If you make the substitution “algorithm is/isn’t NP-hard” with “problem is/isn’t NP-hard”, a lot of the sentences makes much more sense.

                                  A problem in NP is hard to solve

                                  No, not all problems in NP are hard. In fact, P is contained in NP (and we just said all of those problems are easy).

                                  NP-complete (which is not the same thing as NP) problems are (presumably) hard to solve. NP-hard (which is also not the same thing as NP and not the same thing NP-complete) problems are also (presumably) hard to solve, possibly harder than the NP-complete ones.

                                  NP problems are those which can be solve in polynomial time on a non-deterministic machine. If fact, its in the name “Non-deterministic polynomial”. A non-deterministic machine is a regular machine with an extra instruction: a special superfork() that make a copy of the machine (and puts a copy of the process in each forked machine like regular fork).

                                  NP-complete problems are problems in NP that are also “as hard as” any problem in NP.

                                  NP-hard problems are those that are at least “as hard as” any problem in NP but not (necessarily) known to be themselves in NP. (Or rather, being NP-hard makes no statement of whether the problem is in NP or not.)

                                  I would argue that there’s a third possibilty, which is to just…shrug. NP-hard is a worst-case bound on your algorithm. It might only apply to “pathological” inputs.

                                  This is a really bad conclusion.

                                  By analogy, you could also say “the library’s test don’t pass but people might not be using it in the manner of those pathological test cases”. Or “these asserts fail but maybe the program state fixes itself in all but the pathological cases”. The level of (un)certainty is comparable.

                                  Instead what you are supposed to do is exactly what’s discussed for the Go ecosystem.

                                  While researching this problem for the Go ecosystem, Russ Cox pointed out that you can simplify the problem by prohibiting certain kinds of negative dependencies

                                  You should describe the actual problem more accurately. Maybe this particular refinement of the problem statement now undershoot your needs (the original one probably overshot by a lot). But now the task is to refine it further (or refine from an earlier version).

                                  For example, at most 100 negative dependencies are allowed.

                                  There are actually many other things to try in the face of NP-hardness. And from experience, when those all fail, you’re never so “lucky” that the input you care about isn’t pathological. So this kind of luck can usually be explained so that you are once more certain instead of running your program and hoping for the best.

                                  1. 2

                                    No, not all problems in NP are hard. In fact, P is contained in NP (and we just said all of those problems are easy).

                                    Even this interpretation of P=easy is dubious. The class P is huge, and it contains very difficult problems that cannot be solved by algorithms that run faster than O(n^(googolplex)). The fact that a problem is in P does not mean that it can be solved in practice; and by the same reason a problem in NP does not mean that a candidate solution can be verified easily. It is true that many of the well-known polynomial algorithms run in linear or (at worst) quadratic time, but this is a limitation of our current knowledge, not of class P.

                                  1. 4

                                    In order to add a logout feature we had to add four more edges. This quickly gets untenable.

                                    I didn’t understand why this is really an issue though. It feels like increasing the size of a for-loop to me. I do like the nested representation and use nesting quite a bit.

                                    When you started drawing automata, I thought you were going to go the linear temporal logic or Computation tree logic route.

                                    This is from memory and Wikipedia and I could be getting it very wrong:

                                    is it possible to reach answers report without going through the students report?

                                    exists(always(not Student) and eventually(Answers))

                                    We can also ask it to give us an example where someone logs out and logs back in again:

                                    exists(eventually(Logout and eventually(Login)))

                                    (Not really an example.)

                                    finding deadlocks

                                    for all states s, always(next(Summary) implies eventually(s)) and always(next(s) implies eventually(Summary))

                                    “You can reach everything from Summary and you can reach Summary from everything.”

                                    1. 2

                                      I didn’t understand why this is really an issue though. It feels like increasing the size of a for-loop to me.

                                      Adding additional edges to an FSM makes it visually harder to parse. Since the point of an FSM is to convey information to humans, making it harder to parse makes it less useful as a specification.

                                      When you started drawing automata, I thought you were going to go the linear temporal logic or Computation tree logic route.

                                      My main spec language is TLA+, which can express the more sophisticated properties quite easily. The problem is that it doesn’t handle subtyping at all, when representing nested states as subtypes is a really elegant way to encode the spec.

                                      The reason Alloy can’t handle things like deadlocks or liveness is because it’s carefully designed to be as user-friendly as possible. Among other things, that means checking specs really really fast, which means using a SAT solver, which means no infinite traces. We’ve been thinking of changing it to use an SMT solver, but right now the costs are just too high to make switching worth it.

                                      1. 1

                                        Oh, right. I forgot Alloy isn’t TLA+. Thanks.

                                    1. 5

                                      Last week

                                      • Fiddled with different ways of attaching to processes and viewing their states.
                                      • Some other technical stuff that went well

                                      This was for the low level debugger I’m trying to make.

                                      So, from what I’ve read and seen, tools that attach and inspect other process tend to just use gdb under the hood. I was hoping for a more minimal debugger to read and copy.

                                      lldb almost does what I need because of its existing external Python interface but documentation for writing a stand-alone tool (started from outside the debugger rather than inside) is scattered. I haven’t managed to make it single step.

                                      Using raw ptrace and trying to read the right memory locations seems difficult because of things like address randomization. And getting more information involves working with even more memory mapping and other conventions.

                                      I wish all these conventions were written in some machine readable language agnostic way so I don’t have to human-read each one and try to implement it. Right now this is all implicit in the source code of something like gdb. This is a lot of extra complexity which has nothing to do with what I’m actually trying to accomplish.

                                      The raw ptrace approach would also likely only work for Linux. And possibly strong tied to C or assembly.

                                      The problem with the latter is that eventually I will want to do this to interpreters written in C or even interpreters written in interpreters written in C. Seems like even more incidental complexity in that way.

                                      An alternative is to log everything and have a much fancier log viewer after the fact. This way the debugged program only need to emit the right things to a file or stdout. But this loses the possibility for any interactivity.

                                      Plus, all of this would only be worth it if I can get some state visualization customizable to that specific program (because usually it will be an interpreter).

                                      Other questions: How to avoid duplicating the work when performing operations from “inside the program” and from “outside” through the eventual debugger?

                                      Other ideas: Try to do this with a simpler toy language/system to get an idea of how well using such a workflow would work in the first place.

                                      Some references

                                      This week

                                      • Well, now that I have a better idea of how deep this rabbit hole is, I need to decide what to do. Deciding is much harder than programming…
                                      • Or maybe I should do one of the other thousand things I want to and have this bit of indecision linger some more.
                                      1. 5

                                        I wrote a very simple PoC debugger in Rust if you are interested in the very basics: https://github.com/levex/debugger-talk

                                        It uses ptrace(2) under the hood, as you would expect.

                                        1. 1

                                          Thanks! I’ve a had a look at your slide and skimmed some of your code (don’t have Rust installed or running would be the first thing I’d do).

                                          I see that you’re setting breakpoints by address. How do you figure out the address at which you want to set a breakpoint though?

                                          How long did it take to make this? And can you comment on how hard it would be to continue from this point on? For example reading C variables and arrays? Or getting line numbers from the call stack?

                                          1. 2

                                            Hey, sorry for the late reply!

                                            In the talk I was setting breakpoints by address indeed. This is because the talked focused on the lower-level parts To translate line numbers into addresses and vice-versa you need access to the “debug information”. This is usually stored in the executable (as decribed by the DWARF file format). There are libraries that can help you with this (just as the disassembly is done by an excellent library instead of my own code).

                                            This project took about a week of preparation and work. I was familiar with the underlying concepts, however Rust and its ecosystem was a new frontier for me.

                                            Reading C variables is already done :-), reading arrays is just a matter of a new command and reading variables sequentially.

                                            1. 1

                                              Thanks for coming back to answer! Thanks to examples from yourself and others I did get some stuff working (at least on the examples I tried) like breakpoint setting/clearing, variable read/write and simple function calls.

                                              Some things from the standards/formats are still unclear, like why I only need to add the start of the memory region extracted from /proc/pid/maps if its not 0x400000.

                                              This project took about a week of preparation and work. I was familiar with the underlying concepts, however Rust and its ecosystem was a new frontier for me.

                                              A week doesn’t sound too bad. Unfortunately, I’m in the opposite situation using a familiar system to do something unfamiliar.

                                              1. 2

                                                I think that may have to do with whether the executable you are “tracing” is a PIE (Position-Independent Executable) or not.

                                                Good luck with your project, learning how debuggers work by writing a simple one teaches you a lot.

                                            2. 2

                                              For C/assembly (and I’ll assume a modern Unix system) you’ll need to read up on ELF (object and executable formats) and DWARF (debugging records in an ELF file) that contain all that information. You might also want to look into the GDB remote serial protocol (I know it exists, but I haven’t looked much into it).

                                              1. 1

                                                Well, I got some addresses out of nm ./name-of-executable but can’t peek at those directly. Probably need an offset of some sort?

                                                There’s also dwarfdump I haven’t tried yet. I’ll worry about how to get this info from inside my tracer a bit later.

                                                Edit: Nevermind, it might have just been the library I’m using. Seems like I don’t need an offset at all.

                                                1. 2

                                                  I might have missed some other post, but is there a bigger writeup on this project of yours? As to the specifics of digging up such information, take a look at ECFS - https://github.com/elfmaster/ecfs

                                                  1. 1

                                                    I might have missed some other post, but is there a bigger writeup on this project of yours?

                                                    I’m afraid not, at least for the debugger subproject. This is the context. The debugger would fit in two ways:

                                                    • Since I have a GUI maker, I can try to use it to make a graphical debugger. (Ideally, allowing custom visualizations created for each new debugging task.)
                                                    • A debugger/editor would be useful for making and editing [Flpc]((github.com/asrp/flpc) or similar. I want to be able to quickly customize the debugger to also be usable as an external Flpc debugger (instead of just a C debugger). In fact, it’d be nice if I could evolve the debugger and target (=interpreter) simultaneously.

                                                    Although I’m mostly thinking of using it for the earlier stages of development. Even though I should already be past that stage, if I can (re)make that quickly, I’ll be more inclined to try out major architectural changes. And also add more functionality in C more easily.

                                                    Ideally, the debugger would also be an editor (write a few instructions, set SIGTRAP, run, write a few more instructions, etc; write some other values to memory here and there). But maybe this is much more trouble than its worth.

                                                    Your senseye program might be relevant depending on how customizable (or live customizable) the UI is. The stack on which its built is completely unknown to me. Do you have videos/posts where you use it to debug and/or find some particular piece of information?

                                                    As to the specifics of digging up such information, take a look at ECFS - https://github.com/elfmaster/ecfs

                                                    I have to say, this looks really cool. Although in my case, I’m expecting cooperation from the target being debugged.

                                                    Hopefully I will remember this link if I need something like that later on.

                                                    1. 2

                                                      I have to say, this looks really cool. Although in my case, I’m expecting cooperation from the target being debugged.

                                                      My recommendation, coolness aside, for the ECFS part is that Ryan is pretty darn good with the ugly details of ELF and his code and texts are valuable sources of information on otherwise undocumented quirks.

                                                      Your senseye program might be relevant depending on how customizable (or live customizable) the UI is. The stack on which its built is completely unknown to me. Do you have videos/posts where you use it to debug and/or find some particular piece of information?

                                                      I think the only public trace of that is https://arcan-fe.com/2015/05/24/digging-for-pixels/ but it only uses a fraction of the features. The cases I use it for on about a weekly basis touch upon materials that are NDAd.

                                                      I have a blogpost coming up on how the full stack itself map into debugging and what the full stack is building towards, but the short short (yet long, sorry for that, the best I could do at the moment) version:

                                                      Ingredients:

                                                      Arcan is a display server - a poor word for output control, rendering and desktop IPC subsystem. The IPC subsystem is referred to as SHMIF. It also comes with a mid level client API: TUI which roughly correlates to ncurses, but with more desktop:y featureset and sidesteps terminal protocols for better window manager integration.

                                                      The SHMIF IPC part that is similar to a ‘Window’ in X is referred to as a segment. It is a typed container comprised of one big block (video frame), a number of small chunked blocks (audio frames), two ring buffers as input/output queue that carry events and file descriptors.

                                                      Durden act a window manager (Meta-UI).This mostly means input mapping, configuration tracking, interactive data routing and window layouting.

                                                      Senseye comes in three parts. The data providers, sensors, that have some means of sampling with basic statistics (memory, file, ..) which gets forwarded over SHMIF to Durden. The second part is analysis and visualization scripts built on the scripting API in Arcan. Lastly there are translators that are one-off parsers that take some incoming data from SHMIF, parses it and renders some human- useful human- level output, optionally annotated with parsing state metadata.

                                                      Recipe:

                                                      A client gets a segment on connection, and can request additional ones. But the more interesting scenario is that the WM (durden in this case) can push a segment as a means of saying ‘take this, I want you to do something with it’ and the type is a mapping to whatever UI policy that the WM cares about.

                                                      One such type is Debug. If a client maps this segment, it is expected to populate it with whatever debugging/troubleshooting information that the developer deemed relevant. This is the cooperative stage, it can be activated and deactivated at runtime without messing with STDERR and we can stop with the printf() crap.

                                                      The thing that ties it all together - if a client doesn’t map a segment that was pushed on it, because it doesn’t want to or already have one, the shmif-api library can sneakily map it and do something with it instead. Like provide a default debug interface preparing the process to attach a debugger, or activate one of those senseye sensors, or …

                                                      Hierarchical dynamic debugging, both cooperative and non-cooperative, bootstrapped by the display server connection - retaining chain of trust without a sudo ptrace side channel.

                                                      Here’s a quick PoC recording: https://youtu.be/yBWeQRMvsPc where a terminal emulator (written using TUI) exposes state machine and parsing errors when it receives a “pushed” debug window.

                                                      So what I’m looking into right now is writing the “fallback” debug interface, with some nice basics, like stderr redirect, file descriptor interception and buffer editing, and a TUI for lldb to go with it ;-)

                                                      The long term goal for all this is “every byte explained”, be able to take something large (web browser or so) and have the tools to sample, analyse, visualise and intercept everything - show that the executing runtime is much more interesting than trivial artefacts like source code.

                                                      1. 1

                                                        Thanks! After reading this reply, I’ve skimmed your lastest post submitted here and on HN. I’ve added it to my reading list to considered more carefully later.

                                                        I don’t fully understand everything yet but get the gist of it for a number of pieces.

                                                        I think the only public trace of that is https://arcan-fe.com/2015/05/24/digging-for-pixels/ but it only uses a fraction of the features.

                                                        Thanks, this gives me a better understanding. I wouldn’t minding seeing more examples like this, even if contrived.

                                                        In my case I’m not (usually) manipulating (literal) images or video/audio streams though. Do you think your project would be very helpful for program state and execution visualization? I’m thinking of something like Online Python Tutor. (Its sources is available but unfortunately everything is mixed together and its not easy to just extract the visualization portion. Plus, I need it to be more extensible.)

                                                        For example, could you make it so that you could manually view the result for a given user-input width, then display the edges found (either overlayed or separately) and finally after playing around with it a bit (and possibly other objective functions than edges), automatically find the best width as show in the video? (And would this be something that’s easy to do?) Basically, a more interactive workflow.

                                                        The thing that ties it all together - if a client doesn’t map a segment that was pushed on it, because it doesn’t want to or already have one, the shmif-api library can sneakily map it and do something with it instead.

                                                        Maybe this is what you already meant here and by your “fallback debug interface” but how about having a separate process for “sneaky mapping”? So SHMIF remains a “purer” IPC but you can an extra process in the pipeline to do this kind of mapping. (And some separate default/automation can be toggled to have it happen automatically.)

                                                        Hierarchical dynamic debugging, both cooperative and non-cooperative, bootstrapped by the display server connection - retaining chain of trust without a sudo ptrace side channel.

                                                        Here’s a quick PoC recording: https://youtu.be/yBWeQRMvsPc where a terminal emulator (written using TUI) exposes state machine and parsing errors when it receives a “pushed” debug window.

                                                        Very nice! Assuming I understood correctly, this takes care of the extraction (or in your architecture, push) portion of the debugging

                                                        1. 3

                                                          Just poke me if you need further clarification.

                                                          For example, could you make it so that you could manually view the result for a given user-input width, then display the edges found (either overlayed or separately) and finally after playing around with it a bit (and possibly other objective functions than edges), automatically find the best width as show in the video? (And would this be something that’s easy to do?) Basically, a more interactive workflow.

                                                          The real tool is highly interactive, it’s the basic mode of operation, it’s just the UI that sucks and that’s why it’s being replaced with Durden that’s been my desktop for a while now. This video shows a more interactive side: https://www.youtube.com/watch?v=WBsv9IJpkDw Including live sampling of memory pages (somewhere around 3 minutes in).

                                                          Maybe this is what you already meant here and by your “fallback debug interface” but how about having a separate process for “sneaky mapping”? So SHMIF remains a “purer” IPC but you can an extra process in the pipeline to do this kind of mapping. (And some separate default/automation can be toggled to have it happen automatically.)

                                                          It needs both, I have a big bag of tricks for the ‘in process’ part, and with YAMA and other restrictions on ptrace these days the process needs some massage to be ‘external debugger’ ready. Though some default of “immediately do this” will likely be possible.

                                                          I’ve so far just thought about it interactively with the sortof goal that it should be, at most, 2-3 keypresses from having a window selected to be digging around inside it’s related process no matter what you want to measure or observe. https://github.com/letoram/arcan/blob/master/src/shmif/arcan_shmif_debugif.c ) not finished by any stretch binds the debug window to the TUI API and will present a menu.

                                                          Assuming I understood correctly, this takes care of the extraction (or in your architecture, push) portion of the debugging

                                                          Exactly.

                                                          1. 2

                                                            Thanks. So I looked a bit more into this.

                                                            I think the most interesting part for me at the moment is the disassembly.

                                                            I tried to build it just to see. I eventually followed these instructions but can’t find any Senseye related commands in any menu in Durden (global or target).

                                                            I think I managed to build senseye/senses correctly.

                                                            Nothing obvious stands out in tools. I tried both symlinks

                                                            /path/to/durden/durden/tools/senseye/senseye
                                                            /path/to/durden/durden/tools/senseye/senseye.lua
                                                            

                                                            and

                                                            /path/to/durden/durden/tools/senseye
                                                            /path/to/durden/durden/tools/senseye.lua
                                                            

                                                            Here are some other notes on the build process

                                                            Libdrm

                                                            On my system, the include -I/usr/include/libdrm and linker flag -ldrm are needed. I don’t know cmake so don’t know where to add them. (I manually edited and ran the commands make VERBOSE=1 was running to get around this.)

                                                            I had to replace some CODEC_* with AV_CODEC_*

                                                            Durden

                                                            Initially Durden without -p /path/to/resources would not start saying some things are broken. I can’t reproduce it anymore.

                                                            Senseye
                                                            cmake -DARCAN_SOURCE_DIR=/path/to/src ../senses
                                                            

                                                            complains about ARCAN_TUI_INCLUDE_DIR and ARCAN_TUI_LIBRARY being not found:

                                                            Make Error: The following variables are used in this project, but they are set to NOTFOUND.
                                                            Please set them or make sure they are set and tested correctly in the CMake files:
                                                            ARCAN_TUI_INCLUDE_DIR
                                                            
                                                            Capstone

                                                            I eventually installed Arcan instead of just having it built and reached this error

                                                            No rule to make target 'capstone/lib/libcapstone.a', needed by 'xlt_capstone'.
                                                            

                                                            I symlinked capstone/lib64 to capstone/lib to get around this.

                                                            Odd crashes

                                                            Sometimes, Durden crashed (or at least exited without notice) like when I tried changing resolution from inside.

                                                            Here’s an example:

                                                            Improper API use from Lua script:
                                                            	target_disphint(798, -2147483648), display dimensions must be >= 0
                                                            stack traceback:
                                                            	[C]: in function 'target_displayhint'
                                                            	/path/to/durden/durden/menus/global/open.lua:80: in function </path/to/durden/durden/menus/global/open.lua:65>
                                                            
                                                            
                                                            Handing over to recovery script (or shutdown if none present).
                                                            Lua VM failed with no fallback defined, (see -b arg).
                                                            
                                                            Debug window

                                                            I did get target->video->advanced->debug window to run though.

                                                            1. 2

                                                              I’d give it about two weeks before running senseye as a Durden extension is in a usable shape (with most, but not all features from the original demos).

                                                              A CMake FYI - normally you can patch the CMakeCache.txt and just make. Weird that it doesn’t find the header though, src/platform/cmake/FindGBMKMS.cmake quite explicitly looks there, hmm…

                                                              The old videos represent the state where senseye could run standalone and did its own window management. For running senseye in the state it was before I started breaking/refactoring things the setup is a bit different and you won’t need durden at all. Just tested this on OSX:

                                                              1. Revert to an old arcan build ( 0.5.2 tag) and senseye to the tag in the readme.
                                                              2. Build arcan with -DVIDEO_PLATFORM=sdl (so you can run inside your normal desktop) and -DNO_FSRV=On so the recent ffmpeg breakage doesn’t hit (the AV_CODEC stuff).
                                                              3. Build the senseye senses like normal, then arcan /path/to/senseye/senseye

                                                              Think I’ve found the scripting error, testing when I’m back home - thanks.

                                                              The default behavior on scripting error is to shutdown forcibly even if it could recover - in order to preserve state in the log output, the -b arguments lets you set a new app (or the same one) to switch and migrate any living clients to, arcan -b /path/to/durden /path/to/durden would recover “to itself”, surprisingly enough, this can be so fast that you don’t notice it has happened :-)

                                                              1. 1

                                                                Thanks, with these instructions I got it compiled and running. I had read the warning in senseye’s readme but forgot about it after compiling the other parts.

                                                                I’m still stumbling around a bit, though that’s what I intended to do.

                                                                So it looks like the default for sense_mem is to not interrupt the process. I’m guessing the intended method is to use ECFS to snapshot the process and view later. But I’m actually trying to live view and edit a process.

                                                                Is there a way to view/send things through the IPC?

                                                                From the wiki:

                                                                The delta distance feature is primarily useful for polling sources, like the mem-sense with a refresh clock. The screenshot below shows the alpha window picking up on a changing byte sequence that would be hard to spot with other settings.

                                                                Didn’t quite understand this example. Mem diff seems interesting in general.

                                                                For example, I have a program that changes a C variable’s value every second. Assuming we don’t go read the ELF header, how can senseye be used to find where that’s happening?

                                                                From another part of the wiki

                                                                and the distinct pattern in the point cloud hints that we are dealing with some ASCII text.

                                                                This could use some more explanation. How can you tell its ASCII from just a point cloud??

                                                                Minor questions/remark

                                                                Not urgent in any way

                                                                • Is there a way to start the process as a child so ./sense_mem needs less permissions?
                                                                • Is there a way to view registers?
                                                                Compiling

                                                                Compiling senseye without installing Arcan with cmake -DARCAN_SOURCE_DIR= still gives errors.

                                                                I think the first error was about undefined symbols that were in platform/platform.h (arcan_aobj_id and arcan_vobj_id).

                                                                I can try to get the actual error message again if that’s useful.

                                                                1. 2

                                                                  Thanks, with these instructions I got it compiled and running. I had read the warning in senseye’s readme but forgot about it after compiling the other parts. I’m still stumbling around a bit, though that’s what I intended to do.

                                                                  From the state you’re seeing it, it is very much a research project hacked together while waiting at airports :-) I’ve accumulated enough of a idea to distill it into something more practically thought together - but not there quite yet.

                                                                  Is there a way to view/send things through the IPC?

                                                                  At the time it was written, I had just started to play with that (if you see the presentation slides, that’s the fuzzing bit, the actual sending works very much like a clipboard paste operation), the features are in the IPC system now, not mapped into the sensors though.

                                                                  So it looks like the default for sense_mem is to not interrupt the process. I’m guessing the intended method is to use ECFS to snapshot the process and view later. But I’m actually trying to live view and edit a process.

                                                                  yeah, sense_mem was just getting the whole “what does it take to sample / observe process memory without poking it with ptrace etc. Those controls and some other techniques are intended to be bootstrapped via the whole ipc-system in the way I talked about earlier. That should kill the privilege problem as well.

                                                                  Didn’t quite understand this example. Mem diff seems interesting in general.

                                                                  The context menu for a data window should have a refresh clock option. If that’s activated, it will re-sample the current page and mark which bytes changed. Then the UI/shader for alpha window should show which bytes those are.

                                                                  For example, I have a program that changes a C variable’s value every second. Assuming we don’t go read the ELF header, how can senseye be used to find where that’s happening?

                                                                  The intended workflow was something like “dig around in memory, look at projections or use the other searching tools to find data of interest” -> attach translators -> get symbolic /metadata overview.

                                                                  and the distinct pattern in the point cloud hints that we are dealing with some ASCII text. This could use some more explanation. How can you tell its ASCII from just a point cloud??

                                                                  See the linked videos on “voyage of the reverse” and the recon 2014 video of “cantor dust”, i.e. a feedback loop of projections + training + experimentation. The translators was the tool intended to make the latter stage easier.

                                                              2. 1

                                                                I’d give it about two weeks before running senseye as a Durden extension is in a usable shape (with most, but not all features from the original demos).

                                                                A CMake FYI - normally you can patch the CMakeCache.txt and just make. Weird that it doesn’t find the header though, src/platform/cmake/FindGBMKMS.cmake quite explicitly looks there, hmm…

                                                                The old videos represent the state where senseye could run standalone and did its own window management. For running senseye in the state it was before I started breaking/refactoring things the setup is a bit different and you won’t need durden at all. Just tested this on OSX:

                                                                1. Revert to an old arcan build ( 0.5.2 tag) and senseye to the tag in the readme.
                                                                2. Build arcan with -DVIDEO_PLATFORM=sdl (so you can run inside your normal desktop) and -DNO_FSRV=On so the recent ffmpeg breakage doesn’t hit (the AV_CODEC stuff).
                                                                3. Build the senseye senses like normal, then arcan /path/to/senseye/senseye

                                                                Think I’ve found the scripting error, testing when I’m back home - thanks.

                                                                The default behavior on scripting error is to shutdown forcibly even if it could recover - in order to preserve state in the log output, the -b arguments lets you set a new app (or the same one) to switch and migrate any living clients to, arcan -b /path/to/durden /path/to/durden would recover “to itself”, surprisingly enough, this can be so fast that you don’t notice it has happened :-)

                                            3. 3

                                              If you are looking for references on debuggers then the book How Debuggers Work may be helpful.

                                            1. 4

                                              Last week

                                              However, the more I try to do, the more conventions, file formats and Linux-specific knowledge is needed. I think I’ll reduce the scope and not try to make something too general.

                                              One example was trying to make a function call and break right after the call returns. That is, interrupt the current execution to make that call. In assembly, this would just be

                                              call func_name
                                              int3
                                              

                                              The simplest way is to just write these instructions below the current program counter, run and revert the write. But that wouldn’t work for recursive calls and if we’re near the end of the function, maybe we might write over something else that matters during the call to func_name?

                                              So now we could try to simulate the call by crafting a stack frame by hand but the program still wouldn’t break if it finishes. We can reserve some new memory with mmap (syscall #9) and write our instructions there, out of the way of anything else. But the parameter to most calls are relative and only take a 32 bit address difference as argument instead of 64. So I don’t know how to make a call that’s far and the mmaped chunk can be in a different segment as func_name.

                                              I ended up just writing func_name’s address into a register (rax) and ran call rax instead of call func_name.

                                              Maybe I should post about this. But its likely to be a lot of things you shouldn’t do…

                                              This week

                                              • Try to add enough to the debugger so the beginning of flpc is easier to make (if recreated from scratch).

                                              I probably have to look into dynamically adding functions to C at some point. Dynamically adding to assembly isn’t so bad since I mostly just have to find some empty space to write those bytes.

                                              I don’t know if I should go the dlopen way or if that’s more conventions and formats than its worth.

                                              1. 6

                                                Noodling around in Haskell: https://github.com/singpolyma/raw-materials

                                                1. 2

                                                  Thanks for trying it out! I think a couple of your snippets make good examples of the difference between code and specifications, and what makes specifications particularly nasty to write.

                                                  The system is required to prevent two trains from occupying the same track segment at the same time.

                                                  newtype Track = Track [TrackSegment]
                                                  data Train = Train
                                                  data TrackSegment = SegmentTrain Train | SegmentEmpty
                                                  

                                                  This type makes it impossible to have two trains in the track segment at the same time. I don’t think that’s our goal of this spec! When I see “the system is required to prevent X”, I infer two things:

                                                  1. X is a possible state, in that it can happen
                                                  2. X is an invalid state, in that it shouldn’t happen

                                                  In other words, it is possible for two trains to be on the same track segment, but our system should guarantee that, if everything follows the specification, our system will never cause two trains to overlap.

                                                  I don’t think Haskell’s type system is powerful enough to specify this, but you can probably do it in dependent types. Whether that’s the appropriate “raw material” for this specification is another question.

                                                  (Another possible issue is that the current type spec prevents anything else from being on the tracks except a train, like people. But whether that’s an issue dependents on what it is we’re specifying.)

                                                  The vending machine can prevent a coin-insertion event, but only the customer can cause it.

                                                  allowCoinInsert :: Signal (Maybe CoinInsert) -> Signal VendingMachineState -> Signal (Maybe CoinInsert)
                                                  allowCoinInsert coinInsertS stateS = runMaybeT $ do
                                                  	CoinsNotBlocked <- lift stateS
                                                  MaybeT coinInsertS
                                                  

                                                  We have here that the vending machine can prevent a coin-insert event, but we haven’t actually specified that only the customer can cause it. For all we know the vending machine spec is also allowed to trigger a CoinInsert.

                                                  We could add vending machine code and not have any CoinInsert functions, but that doesn’t quite work, either. Upon seeing that, all we know is that the code doesn’t have a means for the vending machine to insert a coin. But we don’t know if that’s intended functionality (perhaps for the next sprint), unplanned-but-okay if it does happen, or expressly forbidden. Similarly, we don’t know if any other parts of the system, whether the customer, a bypasser, or the snack-filler, are allowed to insert coins.

                                                  When a button is pressed, the machine should turn the lamp on within 250 milliseconds.

                                                  -- Hmm... I could use `timeout` to *check* if this happened,
                                                  -- but I don't think I could write anything that would
                                                  -- *guarentee* it always did.  It's unclear what the goal of
                                                  -- the expression is.
                                                  

                                                  It means that if you press the button, the light goes on within 250 milliseconds. :P

                                                  This is an example of hard real-time specification: you specify that the system must do something within a given time range. If your system takes 255 ms to flip the light, then your system is wrong. Hard time specifications are something I have zero experience in, nor have I ever used any specification languages that can express those properties.

                                                  The pipes and switches of the package routing machine form a binary tree.

                                                  data Pipe = EndPipe | Pipe Switch Switch
                                                  data Switch = EndSwitch | Switch Pipe Pipe
                                                  

                                                  This is a good example of how types can be used as a specification tool, which is something I tend to dismiss too easily.

                                                  1. 2

                                                    Hard time specifications are something I have zero experience in, nor have I ever used any specification languages that can express those properties.

                                                    Always happy to fix a problem like that. I did save a lot of design and verification papers on hard-real-time systems. I can try to dig up some examples for you if you want. If you did, I’m curious if you want just the general stuff or also some examples of custom stuff. They do a lot of purpose-built formalisms in that niche. I’m still not sure if that’s a good idea or not since benefits of people being on same page often outweigh benefits of new formalisms.

                                                    1. 2
                                                      data Pipe = EndPipe | Pipe Switch Switch
                                                      data Switch = EndSwitch | Switch Pipe Pipe
                                                      

                                                      My Haskell is rather poor but wouldn’t this also let you make cycles? What happens if you put the same value for both Pipes of a Switch?

                                                      The pipes and switches of the package routing machine form a binary tree.

                                                      From this description, I thought something like this would be valid? But how can it be expressed?

                                                          S
                                                         / \
                                                        S   \
                                                       /     \
                                                      S       S
                                                             / \
                                                            S   \
                                                                 S
                                                      

                                                      From this diagram, I’m also thinking that having two child switches for a pipe would be invalid.

                                                      Although really, I’d ask for the statement to be clarified first. There are a few other questions here.

                                                  1. 1

                                                    Interesting. The syntax is simple enough to be added to other shells.

                                                    I wish all the examples also provided sample outputs of the command being run.

                                                    The “Compression benchmark” example has inputs to cat shown in an arbitrary(?) order which was really confusing for me. The actual order is

                                                    printf file printf wc printf xz->wc printf bzip2->wc printf gzip->wc
                                                    
                                                    1. 3

                                                      Last week

                                                      • Prepared some presentation slides and demo
                                                      • Fiddled with lldb. Realized I might want a very different design.

                                                      This week

                                                      • Think about what’s actually needed for a debugger. Try different things. Still want the debugger to be general and work externally.
                                                      • Think of ways to sustain my activities.
                                                      1. 10

                                                        I have not read the entire paper. Just the first 5 pages and the conclusion.

                                                        I’d like to point out that there are significantly different ways for creating computer programs and this analysis seem to implicitly assume that the “static way” is the only way.

                                                        In the “static way”,

                                                        1. the programmers write large chunks of code in an editor (sometimes with some tests written beforehand),
                                                        2. the code is sent to a compiler which help point out errors,
                                                        3. if it compiles, the programs runs and the programmer observes the output
                                                        4. the programmers makes updates as needed. Eventually adding other large chunks of code.

                                                        (There are of course many variantions on this. Please correct me for a more accurate description.)

                                                        In the more “dynamic way” of programming, a programmer is not only created in small pieces but potential new lines are tried out in the interpreter before deciding to add them or not. It is typically characterized by a short feedback loop.

                                                        1. the programmers write a statement or line,
                                                        2. this is sent to the interpreter,
                                                        3. the programmer observes the result,
                                                        4. make modifications and go back to 1 and/or add/keep some that line for the final program.

                                                        Usually, there are lot of (language and IDE) features to make the 1-3 loop as fast as possible.

                                                        In the Samlltalk IDEs, its possible to even run programs with mostly missing methods and Classes and fill them in at runtime (without ever restarting). To make such workflows possible, “superfluous” dynamic features are absolutely needed but will never be seen in individual codebases in the final product.

                                                        The main reason I think this article assumes a strong static view is that they never discuss this aspect of dynamic languages (in the pages I’ve read).

                                                        We started our analysis by looking at all 1850 software projects stored in Squeaksource in a snapshot taken in early 2010.

                                                        They don’t look at dynamic feature use during the program creation phase at all, just the final product.

                                                        One issue is that its always possible to program in a more static way in a dynamic language and IDE. And the see the lack of help from the compiler as a hinderance. In one never uses the dynamic features then it is easy to conclude they are a hinderance. But these features aren’t there solely for the purpose of being included in the final program.

                                                        They found that the Python program in their corpus made a heavier usage of dynamic features during their startup phase, but that many of them also used some of these features during their entire lifetime.

                                                        Of course, to perform any kind of study, some kind of assumptions need to be made. But they don’t say that this aspect is ignored to simplify the study.

                                                        There are also things that can be done which can improve a language on one of the static/dynamic axis without regression on the other, especially at the beginning.

                                                        As a final note, I’d like to mention one last use of dynamic features: to learn about a new module. I’ll usually read the high level readme of a new module and then immediately start playing with its objects in the interpreter without reading the documentation for individual classes and functions.

                                                        Reflexive methods allow me to quickly find out what’s available and try things purely based on their names. I’ll send mock inputs to functions to try and figure out what their inputs and outputs are, observe the results and update my hypothesis about what they do.

                                                        I find this gives me a much better and certain understanding of foreign modules and its a lot of fun to just poke around instead of just reading!

                                                        Now I’m wondering if I should make a screencast of this.

                                                        1. 9

                                                          I completely agree with your point here, and I had the same reaction to the paper. I don’t program in Smalltalk anymore, but when I did, one of my favorite demos was what I called “debugger-driven development.” I’d start by just writing some code that would be what I wanted an API to look like–e.g., for a fortune program, maybe Fortune loadAll randomFortune–then execute DoIt, bringing up the debugger (since that class doesn’t even exist)–and then I’d add recursively add the missing methods until the original line completed. This leverages a whole swath of metaobject and reflective capabilities that the final code wouldn’t need, but without which, the entire Smalltalk development experience would be neutered beyond recognition.

                                                          My other common demo was pretty different, but also did a great job using metaprogramming and reflective capabilities during development not needed in prod: I’d find a web API that was pretty cleanly designed and relevant to the audience I was speaking to. Next, I’d show how to write a kind of generic catch-all implementation via #doesNotUnderstand:, like what you might do in Ruby or Python. But then I’d modify it to generate the missing methods on-the-fly, and then (using a deliberately-made mistake in my first implementation) show how things like method modification timestamps and reflection could find the improperly-generated methods and regenerate them. (Sometimes, I’d even demo regenerating them as-needed with #perform: if I felt like it.) Finally, when we were done, I’d delete the #doesNotUndestand: implementation, customize a route or two, and be done. The final product didn’t use reflection, metaclasses, #doesNotUnderstand, or any of that kind of stuff, but the entire development process did. And unsurprisingly, a lot of the code for development did use things like self basicNew, foo perform: (a, b) asSymbol, and so on, even though the final wouldn’t.

                                                        1. 2

                                                          How does this compare to other menus if its keyboard driven (both menu opening and item selection).

                                                          What about compared to some regexp search through the menu items?

                                                          1. 4

                                                            One good thing that my horrible ActiveX pie menus did handle nicely was keyboard navigation, shown in the following demo.

                                                            Four and eight item pie menus work very well with the numeric keypad and arrow keys, as well as joysticks and d-pads. You can also move to the next/previous item around the circle with tab / shift-tab, and type the name of an item to jump to it directly, hit escape to cancel the whole menu tree, backspace to peel back one submenu layer, etc, just like normal menu keyboard navigation.

                                                            It’s great to be able to navigate the same memorable menu trees with many kinds of input devices!

                                                            Terrible Example: ActiveX Pie Menus

                                                            This demo of an old OLE/ActiveX implementation of pie menus in Internet Explorer shows the weakness and complexity of the traditional desktop GUI MFC based approach to creating and editing pie menus with typical property sheets, scrolling lists and tree editors. It also has a weird way of paging between large numbers of items in pages of eight or fewer items each, which I was never very happy with. And programming complex user interfaces with XML/C++/ActiveX/OLE/MFC/Win32 is hell on earth.

                                                            https://www.youtube.com/watch?v=nnC8x9x3Xag

                                                            1. 1

                                                              Did you do any experiments specifically with joystick input? Because mouse drivers are intended to produce actual cursor position deltas, even trackpoint-style mice produce more information than is used in a pie menu (and while warping can make up for overshooting, it can be confusing for the user unless done carefully). On the other hand, while Mass Effect never nested their pie menus, they essentially made use of one of the two controller sticks as a pure direction-input device with good radial resolution (better than a d-pad, which has only four directions & thus can defeat the point of a pie menu if there are more than 4 options).

                                                              Using a dual-stick video game controller for a pair of pie menus that are statically placed means simultaneous navigation of two menus can be fast. Using fans instead of pies and orienting the fan such that the fan center is the center of the previous selection and the fan’s options are arrayed perpendicular to the swipe direction used to select it could make it possible to navigate and back out of many layers of menu pretty easily without extra selection gestures (the one complaint I had about the pie menus in The Sims 1)

                                                              1. 3

                                                                No, I haven’t done any joystick experiments myself.

                                                                Before he started spreading FUD about marking menus, Bill Buxton wrote an excellent paper on input devices in 1983, called “Lexical and Pragmatic Considerations of Input Structures”, which categorizes input devices and how their unique properties map to the problem domain, and discusses a lot of important concepts like pragmatics, chunking and closure, device independence, taxonomy of devices, and the nulling problem:

                                                                https://www.billbuxton.com/lexical.html

                                                                lexical: issues having to do with spelling of tokens (i.e., the ordering of lexemes and the nature of the alphabet used - symbolic or iconic, for example).

                                                                pragmatic: issues of gesture, space and devices.

                                                                Figure 1: Taxonomy of Input Devices. https://www.billbuxton.com/lexical1.gif

                                                                Continuous manual input devices are categorized. The first order categorization is property sensed (rows) and number of dimensions (columns). Subrows distinguish between devices that have a mechanical intermediary (such as a stylus) between the hand and the sensing mechanism (indicated by “M”), and those which are touch sensitive (indicated by “T”). Subcolumns distinguish devices that use comparable motor control for their operation.

                                                                Since you mentioned fans, I should point out that Simon Schneegans, the same guy who did the excellent Gnome-Pie, also did these amazing spoke-like and fan-out pies for his bachelor’s thesis:

                                                                The Coral-Menu: https://vimeo.com/51072812

                                                                The Trace-Menu: https://vimeo.com/51073078

                                                                Those are great on so many levels!

                                                                1. 2

                                                                  Thanks! A lot of food for thought here

                                                                  1. 1

                                                                    You’re welcome! I’m glad you’re hungry for it. ;)

                                                                    Enjoy some pizza: https://medium.com/@donhopkins/the-story-of-sun-microsystems-pizzatool-2a7992b4c797

                                                                    And some more pie too: https://www.youtube.com/watch?v=Xj1LFYSO2Kw

                                                              2. 1

                                                                Thanks!

                                                                Ignoring the thing its built on, that’s an interesting demo. I like that expert gesture-like mode. How well does it works in the end? Too bad this video doesn’t show keyboard or joystick use (or I missed it having skipped most of the editor portion).

                                                                1. 2

                                                                  It was very snappy because it was directly calling the Win32 API to manipulate windows and handle events (well, going through some layers of OLE/MFC, but not as squishy as a web browser). So mouse-ahead was quite reliable since it wasn’t polling for events and letting some of them slip through the cracks when the computer slows down (i.e. always), like some systems do.

                                                                  That was the great thing about NeWS: it had perfect, air tight, synchronous event handling, and never dropped one event on the floor, or sent a keystroke to the wrong window.

                                                                  Even my modern MacBook Pro always gets overheated, slows down, and when I open a new tab I have to stand back, be patient, and wait for the vehicle to stop moving completely before embarking with the mouse and keyboard.

                                                                  On Medium, I keep typing cmd-f to search before the page has settled down, and the first few characters of my search string that I type after cmd-f get inserted into the document somewhere at random, then the rest go into the search field! So I have to type cmd-f, sit back, take a breath, wait for a while, then type what I want to search for. Emacs on a 300 baud terminal was better than that!

                                                                  But I really hurt for an easy to use drawing API like cairo or canvas (i.e. I’m an old PostScript programmer, and it’s a huge pain in the ass carefully selecting resources in and out of the win32 GDI context absolutely perfectly every time without making the slightest mistake or else GDI memory would overflow and Windows would freeze up and the reset button would not work so you had to remove the laptop’s battery to reboot).

                                                                  But then again it was even worse programming on a Mac without any memory protection whatsoever! Those old Macs tend to freeze up instantly whenever you made the slightest programming mistake, instead of slowly grinding to a halt while glitching out the screen like Windows. To their credit, the PowerPC Macs could crash really really really quickly! You instantly knew when to reach for the “programmer’s switch”.