Threads for vrthra

  1. 2

    Is the storage in the free oracle VM enough to host the instance? Beyond that it’s about $40/TB/month. At least they don’t charge you like ten cents a gigabyte for network egress like Azure.

    1. 1

      I get 45 GB; about 5 GB is the OS. The rest is available for Ktistec.

    1. 3

      Oh neat, Kitstec looks super cute! Thanks for introducing it. If you’re lucky, you might be able to get an Oracle Free ARM server which can have up to 24gb of RAM and might be able to alleviate the initial compilation step, and be a good start to other hosting plans!

      1. 1

        I looked at the ARM server Ampere. The way its costing is phrased is somewhat different from how they phrase the costing of AMD. Also, if I choose AMD, I see the “always-free” tag in my instance. But not so with Ampere. So, I have decided to be cautious.

      1. 2

        I’m pretty sure GitHub/Twitter are only really special-cased because they effectively act as verified links. If you could plop down a rel="me" and get a checkmark out of it, it’d matter a lot less.

        1. 7

          Some of us host our own servers. Please consider our use case too in case of any such requirements for verification.

        1. 2

          Host yourself! It is really easy to do that. The link shows how you can (1) get a free subdomain from freemyip.com, allocate a free letusencrypt certificate to the subdomain, and use oracle cloud free tier to host your instance. I use ktistec for mine, which is a single user activity pub server which can federate with any mastodon instance. It is very lightweight (written in Crystal, uses sqlite and filesystem as a backend etc.) and easy to setup.

          1. 1

            Interesting! Hadn’t heard of ktistec before. I’m hosting the excellent honk with some tweaks of my own. Good to see there’s more work in the ActivityPub space catering to small-time hosters like us.

          1. 3

            What is the advantage compared to LuaTeX (besides the DocBook subset)? How does the performance compare to original TeX? Is Lua recommendable for this kind of applications? How many SLOC of Lua does Sile have?

            1. 6

              What is the advantage compared to LuaTeX (besides the DocBook subset)?

              See david_chisnall ’s reply above I suppose. Also, https://github.com/sile-typesetter/sile#what-can-i-do-with-sile-that-i-cant-do-with-tex

              How does the performance compare to original TeX?

              It supports luajit, so it can probably be within 2x/3x or so the speed of the same software written in C/Rust/whatever. But it’s not the same software, so idk.

              Is Lua recommendable for this kind of applications?

              It’s aite.

              How many SLOC of Lua does Sile have?

              ~/tmp/sile-0.14.3 $ tokei
              ===============================================================================
               Language            Files        Lines         Code     Comments       Blanks
              ===============================================================================
               Autoconf                7         4853         4145          183          525
               Automake                3          690          566           15          109
               C                      63        51543        39384         5226         6933
               C Header               67         8158         5131         1923         1104
               Dockerfile              1           67           39           10           18
               FreeMarker             65          271          165            0          106
               JavaScript              1           12           10            0            2
               JSON                    1           86           86            0            0
               Lua                   235       392979       387540         2380         3059
               Nix                     3          152          122           27            3
               Objective-C             1          215          175            6           34
               Perl                    1           69           64            2            3
               Shell                   9        23892        17148         4190         2554
               SVG                     2           20           20            0            0
               XML                     8          622          577            0           45
              -------------------------------------------------------------------------------
               Markdown                3         1448            0         1018          430
               |- YAML                 1           12           12            0            0
               (Total)                           1460           12         1018          430
              ===============================================================================
               Total                 470       485077       455172        14980        14925
              ===============================================================================
              
              1. 6

                It supports luajit, so it can probably be within 2x/3x or so the speed of the same software written in C/Rust/whatever

                This makes it a lot faster than LaTeX, which is written in an interpreted VM that looks a lot like a Turing Machine (not the most efficient model of computation to write an in, by a long stretch). The VM itself is written in a Pascal-like literate programming language called Web, which is typically converted to C for compilation. For the same kinds of operations, I’ve found SILE over an order of magnitude faster. This VM is also the reason that LaTeX is so painful to write: it is a really clunky set of low-level abstractions, with no support for modularity, composability, and so on. Knuth made a load of claims about how TeX was practically big-free but that is mostly because it does very little and the bugs are all in the code that runs on top of it.

                1. 1

                  Can you explain this further? Is Tex commands running on top of the VM you mention, each implemented as a small program on top of the VM, or is it the Tex commands itself you consider as VM opcodes?

                  1. 3

                    A TeX document is a program that is interpreted by this VM. As it executes, it reads characters one at a time and writes output via some of the built-in commands. The built-in functionality has some rich features. Most people these days use LaTeX, which is a huge program written in TeX, which provides a packaging system for other TeX programs. Things like semantic markup (e.g. headings, versus specific fonts and line breaks) and even cross-references or numbering in enumerated lists are all LaTeX code running in the VM.

                    This is also why it’s basically impossible to parse a LaTeX document and generate an AST. Every character (including ones imported from elsewhere) may change how any subsequent characters are parsed, let alone how they are interpreted (Unicode support is incredibly magic, it adds special interpretation of some characters to build a state machine that parses UTF-8 and converts it into specific glyph requests).

                    1. 1

                      I see! Thank you, much appreciated.

                2. 3

                  this looks like one of the largest Lua application I had ever seen (in terms of lines of code).

                  1. 3

                    Wow, that’s an awful lot of Lua code; must have taken many years to write.

                    1. 3

                      I’m not sure when it started, I met the author over a decade ago when he gave a FOSDEM talk about it. It was my favourite talk that year.

                      1. 1

                        From my humble point of view, it is a pity that the author relied on a scripting language for such a large system; the largest Lua code base I have encountered so far had 50 kSLOC, and it was almost impossible to get an overview of the system, and maintenance was hell.

                        1. 2

                          The scripting language (or, specifically, a dynamic language) is one of the key features of the project, because it means that users are able to replace any component with something custom. If you replace any of the algorithms with something specialised, you can, because it’s all dynamic. Something like Objective-C would also have worked, but lua has very few dependencies.

                          I don’t have much experience with Lua, but it’s basically Smalltalk with weird syntax and I’ve seen Smalltalk codebases well over a million lines of code without maintenance problems arising from the size.

                          1. 2

                            it means that users are able to replace any component with something custom

                            That’s a rather theoretical approach if you as a user are confronted with a code base of 400 kSLOC not amenable to static analysis; even knowing what to replace is a challenge. Objective-C at least has some static typing. Smalltalk suffers from similar problems; in contrast to Lua at least classes and field names are statically declared.

                            without maintenance problems arising from the size.

                            That’s very unlikely. I worked with Smalltalk code bases in the nineties myself and maintenance, integration and deployment were a nightmare. From a certain size you had to use manufacturer-specific concepts for namespaces and modularization, as well as tools like Envy, otherwise the undertaking would have been simply impossible. I also spent a lot of time with the retrospect of Smalltalk, as many questions from that time remained unanswered (see https://github.com/rochus-keller/Smalltalk). I can’t understand the retrospective glorification of this technology; it was impressive for its time (seventies and eighties), but not suitable for large systems.

                  2. 3

                    What is the advantage compared to LuaTeX (besides the DocBook subset)?

                    You get a base system that applies the TeX layout algorithms to the entire document, not just paragraph by paragraph like TeX does due to the resource constraints it was developed under. It also has more control over layout than TeX: you can do things like insist that a figure come in a particular place (I forget the precise TeX limitation here, I just remember there is one…) and place text precisely back to back on successive pages.

                    How does the performance compare to original TeX?

                    It’s much, much quicker. TeX is written in a weird very low level interpreted virtual machine that Knuth came up with & is very slow, even when compared to an interpreted language like lua.

                    Is Lua recommendable for this kind of applications?

                    It’s a perfectly good language? Small, well defined runtime, easily extendable, reasonably fast for an interpreted language. It might not have been my first choice personally, but I didn’t write it! Running code beats non-existent code…

                    How many SLOC of Lua does Sile have?

                    About 400k lines.

                  1. 5

                    Logo is still used today :) The school our children attends uses robots and Logo from Terrapin:

                    https://www.terrapinlogo.com/

                    1. 1

                      Can you give me more information about this program? What kind of robots do you use? and what applications? I am looking for something similar for my daughter.

                      1. 1

                        The school uses these:

                        https://core-electronics.com.au/brands/bee-bot-australia

                        … to introduce kids to programming concepts via push-button “programming”, leading up into Logo programming for the older children.

                        1. 1

                          Thank you! much appreciated.

                    1. 1

                      So what exactly is the difference between original green threads and current threads? “Virtual threads bear a superficial similarity to green threads in that they are both managed by the JVM rather than the OS, but this is where the similarity ends. The green threads of the 90s still had large, monolithic stacks.” is not very explanatory. What is a monolithic stack?

                      1. 5

                        Noting here that there is Sixel which lets you draw pretty much anything into the terminal, and almost all major terminals (including the venerable xterm) supports it. You can watch a movie (not character based like aalib, but true color pixel perfect) if that is what you want drawn on the terminal.

                        1. 1

                          One of the limitations of hooking into the Python import system is that the modifications you require can’t be used directly on the script file. Instead, the file with modifications has to be imported into the script file. An alternative is to hook into the Python codecs.

                          1. 2

                            So the cool thing with PEP302 is that you could in theory just implement a random language in Python that compiles using the ast module. Then when you load your library you can hook into the import system and on-the-fly compile your custom language before giving it to Python.

                            Imagine if you had a LISP with macro support! You could just generate a bunch of Python code and hook into it transparently.

                            https://youtu.be/1vui-LupKJI?t=978

                            :)

                            1. 2

                              I don’t know about python, but perl has a similar mechanism. Which led to things like: https://metacpan.org/dist/Lingua-Romana-Perligata/view/lib/Lingua/Romana/Perligata.pm

                              1. 1

                                Author: Damian Conway.

                                Figures.

                                To simplify the mind-numbingly complex rules of declension and conjugation that govern inflexions in Latin, Perligata treats all user-defined scalar and array variables as neuter nouns of the second declension – singular for scalars, plural for arrays.

                                Hashes represent something of a difficulty in Perligata, as Latin lacks an obvious way of distinguishing these “plural” variables from arrays. The solution that has been adopted is to depart from the second declension and represent hashes as masculine plural nouns of the fourth declension.

                              2. 1

                                I know of one module that utilizes this. pcapnp loads up Cap’n’Proto schema files and creates appropriate Python classes. Pretty neat IMO.

                                1. 1

                                  Neat! I’m curious to find other similar (ab)uses of Python’s import mechanism.

                                2. 1

                                  You can add macros to Python directly with this mechanism.

                                  (Hy is very cool too.)

                                1. 2

                                  I have had multiple Ubikeys for a long time as I am a frequent international traveler, and am afraid of Google locking me out suddenly. Having a Ubikey gives me peace of mind, but it losing the key can be a headache, as I need to buy another costly key, log into every service that uses the key, remove it, and add a new key. With this project (I hope, I haven’t tested), I may be able to simply gpg encrypt my fidokey and keep it safe in my computer rather than having to worry about my ubikeys.

                                  1. 3

                                    It’s a really interesting tradeoff. Nominally the value prop of the Yubikey is that it’s a separate physical device so that you know that “even if someone were to steal my laptop and have unfettered access to my password manager, they still wouldn’t be able to access these services”

                                    But the flip side is definitely a concern too… if I lose my (physical) keychain, I won’t be able to access these services either.

                                    In my own experience, I have had a laptop stolen but haven’t ever had my keys stolen nor have I lost my keys for any length of time. My wife, though, has the opposite experience.

                                    1. 1

                                      I mean no, that’s not a good reason to use a Yubikey at all. It’s about having a smartcard that performs cryptographic operations for you without exposing the keys. Of course using it as a second authentication factor is a specific use case of that, also providing multidevice access as a side-effect of being a separate device. More to the point, compromising a device cannot leak the keys for further attack vectors.

                                  1. 2

                                    Thanks for posting. This got my attention:

                                    This has profound implications for programming language design.

                                    This paper talks about a problem that I’ve been chipping away at for years, which is how to define a programming language with a universal equality operator (that can compare functions as well as values), while preserving clean semantics.

                                    1. 4

                                      IMHO languages should try to reduce expressiveness whenever possible by offering mechanisms to do so, i.e. DSLs and DSL tools. Perlis warned us about the Turing tar pit, where doing stuff is easy but proving things is super hard.

                                      Along with the total lack of popularity of design-by-contract / Hoare logic / refinement types, I think this is the biggest mistake in modern language design.

                                      In other fields, engineers strive to use components and to combine them in ways that yield artifacts with provable properties. An elementary example of this are truss structures in mechanical engineering.

                                      1. 2

                                        I agree with this, but it took me a while to arrive at this realization. When I was a teenager, I thought that languages evolve and improve by increasing their expressive power, and that therefore, the goal of programming language design was total ultimate expressive power. Now I understand that this may be in conflict with being able to understand what your program does. The main danger (IMO) lies in offering features that introduce non-local effects that destroy your ability to understand code using local reasoning. I like your framing of “offering mechanisms to reduce expressiveness”.

                                        1. 1

                                          Perlis warned us about the Turing tar pit, where doing stuff is easy but proving things is super hard.

                                          This is surely not the Turing Tarpit? Perlis said:

                                          Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.

                                          Which I take to mean, doing stuff is super hard.

                                          1. 1

                                            Sure, but I also take doing to mean proving things about a program you wrote.

                                            If you work on a very crude and expressive language, say a basic imperative language with assignments, loops and conditionals, proving properties is hard.

                                        2. 3

                                          Interesting! Could you elaborate? By https://en.wikipedia.org/wiki/Rice%27s_theorem, either the equality operator will not always terminate, or it will not say anything decisive and meaningful about the output of the functions, or the functions themselves can not encode arbitrary computations. Which side are you willing to compromise on?

                                          1. 1

                                            Rice’s theorem applies to semantic properties. Equality for functions can be defined by syntactic equivalence. The paper talks about equivalence in the ‘closed normal form’ and although the paper is over my head, in other cases that would refer to a syntactic rewrite of an expression that leaves it semantically equivalent.

                                            1. 1

                                              Some years ago I had a love affair with Scheme (as a cleaned up dialect of Lisp). One of my projects continues to be a simple Scheme-inspired language, aimed at creative coding and artistic creation. It has cleaner and simpler semantics than Scheme. The goal is to create a feeling of delight in the user (rather than something tedious like supporting formal verification, which requires burdening the user with bureaucracy). Everything should be simple and obvious.

                                              Scheme has a universal equality operator, that always terminates when comparing functions, and I don’t want to lose that. Scheme has a universal “print” function that prints any value, including functions, and that’s important, especially in the REPL. Some of my goals include: you can understand the behaviour of a program by reading the source code and using local reasoning. There should be one primary equality operator, replacing the eq,eqv,equal of Scheme. Two values should compare equal iff they have identical printed representations. Ideally, a value should be printed as an expression that, when evaluated, exactly reproduces the original value. That makes values easy to examine interactively and reason about.

                                              Given these goals, what happens when you print a function, or compare two functions for equality? One thing that doesn’t happen is that functions do not print as the hexadecimal machine address of their closure objects. You can’t predict that output from the source code. You also can’t take that output, ship it to another machine, and evaluate it to reproduce the original value, similar to the way that you can exchange data using JSON. My language is also inspired by JSON. It started out as JSON extended with lambda expressions (which construct lexical closures) and let expressions (for introducing local variables). It has eager evaluation, like Scheme.

                                              With these goals, it seems as though functions should print as lambda expressions, or perhaps as let expressions with a lambda as the body in the case where the function value is a closure capturing nonlocal bindings. And function equality should be equality of the printed representation. Of course the devil is in the details. I’m interested in playing with other languages that have achieved these goals in a satisfying way. The paper classifies my language as an “intensional” language and promises a new approach to function equality and intensional computing.

                                            2. 2

                                              which is how to define a programming language with a universal equality operator (that can compare functions as well as values)

                                              Is this related at all to function extensionality and/or higher-order unification? In dependently typed languages we can compare functions, but it’s usually pretty limited (ie. only checking that they are computationally equal) unless you go to more exotic things.

                                              1. 1

                                                The principle of functional extensionality states that two functions are equal if their values are equal at every argument.

                                                This sounds wonderful, but it turns out it’s not what I want in my language (which I describe a bit in another post). As @rouanth notes, extensional equality not computable, so to begin with it’s impossible. A more subtle problem is that extensional equality can violate encapsulation. It turns out that I want the ability to define modules that export reusable library abstractions and hide their implementation details. Extensional equality for types means structural equivalence, not name equivalence, and conflicts with data abstraction. (Note, in my language, “types” are values that can be compared for equality, a bit different from the types in type theory.) Extensional equality for functions means that two functions from different libraries might accidently compare equal if they currently have the same extension. (This situation could change in a future library update.) What I want to do is to somehow compare the contracts of the functions, not their extensions. And this has led me to consider a form of name equivalence for encapsulated functions that are exported from a module.

                                                So, using the terminology of that ncatlab page you linked, I am investigating different kinds of definitional / intensional equality for comparing function, type and module values.

                                                1. 1

                                                  I’m not an expert on type theory, but I can try to answer some stuff.

                                                  This sounds wonderful, but it turns out it’s not what I want in my language (which I describe a bit in another post). As @rouanth notes, extensional equality not computable, so to begin with it’s impossible.

                                                  Cubical Type Theory and Observational Type Theory admit function extensionality… but I’m not sure how exactly it relates to “extensional equality” though. I’m actually wondering if observational type theory might be interesting to look at. It’s much simpler than cubical (making different trade-offs): Observational equality: now for good (Conference presentation).

                                                  A more subtle problem is that extensional equality can violate encapsulation.

                                                  You run into encapsulation issues with intensional equality too… like if definitions can reduce when comparing stuff, then you can see the implementation details. Which might tie into your thoughts on name equivalence? You can see the difference between transparent and opaque type aliases (aka. abstract types) as being a special case of this problem.

                                                  Note, in my language, “types” are values that can be compared for equality, a bit different from the types in type theory

                                                  Curious where the difference lies in your system! In type theories you usually have a judgement for type equality as well.

                                                  What I want to do is to somehow compare the contracts of the functions

                                                  Sounds a bit like comparing types or propositions, potentially?

                                                  1. 2

                                                    @brendan wrote:

                                                    Cubical Type Theory and Observational Type Theory admit function extensionality…

                                                    Here’s the definition from the page you linked:

                                                    The principle of functional extensionality states that two functions are equal if their values are equal at every argument.

                                                    What this means is, in some formal systems, if two functions F and G are equal at every argument (ie, the functions have extensional equality), then those functions are “equal” in those formal systems. The functions can’t be distinguished from one another within those formal systems. The original paper that we are discussing categorizes the lambda calculus as an example of a formal system where functions have extensional equality. The paper also criticizes such formal systems as having less expressive power than conventional programming languages.

                                                    In some other formal systems (which the paper labels as “intensional” systems), two functions that are extensionally equal but have different internal representations (different lambda bodies) might be considered unequal, because in those systems, the function body is accessible. The paper mentions the SF calculus as a very simple example of a formal system which violates the principle of functional extensionality.

                                                    The language I’m working on has an equality operator that works on all values, and which therefore works on functions. This equality operator cannot test if two functions are extensionally equal, because that is not computable in my language, or in any Turing equivalent programming language. So I need to use a weaker or stronger form of equality.

                                                    The simplest design I could use would be to treat all function values as equal to one another, and to print all function values as the string “<function>”. This design would satisfy some of my design requirements. The == operator is an equivalence relation. The principle that two values print as the same string if and only if they compare as equal using the == operator is satisfied. Absent any metaprogramming facilities that allow you to examine the internal representation of a function, a language with this design would satisfy the principle of functional extensionality. And this is true even though the == operator does not test functions for extensional equality.

                                                    It turns out that I desire a richer language than this, one where printing a value derived from evaluating an anonymous lambda expression prints the actual lambda expression. This is because just seeing <function> when I print a function in the REPL does not fill me with delight. That feature would violate the principle of functional extensionality, add expressive power, and make my language into an intensional system as defined by the paper.

                                            1. 2

                                              There is also the Kaitai Struct and 010 formats in this space.

                                              1. 13

                                                In practice almost all languages end up forcing the lexer peanut butter to get mixed into the parser’s chocolate: just off the top of my head, C, C++, Ruby, every shell language I’ve seen, Ada, Perl, Rust, Lisp, Haskell, …

                                                The idea that that boundary is “right” always struck me as something of a siren’s song in compiler implementation: it feels like there should be a clear, hard boundary between the lexer and parser, but in practice what people want out of languages is more contextual than that allows, so it’s just a set of rocks waiting to ruin your day.

                                                1. 6

                                                  One of the worst decisions that I think lex and yacc made was to make the lexer push the parser, rather than the parser pull from the lexer. This means that you can’t have any kind of context-specific parsing, which turns out to be something that’s incredibly valuable for a language (particularly when you want to extend the language later: being able to claim things from the identifier space, but only in a new context, avoids backwards compatibility problems).

                                                  In the pull model, the parser says ‘I am in this rule, is the next token one of these?’ and the lexer replies ‘yes, here it is’, or ‘no’. The parser can then be structured to say ‘is the next token this context-dependent keyword?’ and if the lexer says ‘no’, then ask ‘is it an identifier?’. This means that you don’t need to have stupid parser rules that say ‘I accept an identifier or any one of these keywords that happens to look like an identifier’ or move lexing logic into the parser (to say ‘I accept any identifier, but if it isn’t one of the ones that is really a keyword then we’ll abort during parsing’).

                                                  If one token class is a subset of another (e.g. a keyword is also a valid identifier) then you can even cache the result of the first call to the lexer so that the second one is fast. I’ve never actually needed to do this because the number of ambiguous rules tends to be fairly small and the cost of re-lexing a few tokens is low.

                                                  1. 7

                                                    every shell language I’ve seen

                                                    Not Oil’s front end, which parses both OSH/bash and the Oil language!

                                                    I agree the the line between the lexer and parser is non-trivial. And if you’re parsing C you can’t avoid “the lexer hack”, which goes by many names.

                                                    But I draw a pretty bright line in Oil’s front end – lexing is non-recursive and parsing is recursive – and it has held up for years (which wasn’t obvious at the outset).

                                                    https://github.com/oilshell/oil/wiki/Why-Lexing-and-Parsing-Should-Be-Separate

                                                    I wrote about the architecture and “lexer modes” technique here:

                                                    Without lexer modes, it probably would have been impossible to maintain the line. Because shell is composed of mutually recursive sublanguages. (But so is almost every complex language if you look closely enough, e.g. C and C++, and I think Rust)

                                                    Rough summary is:

                                                    • The parser tells the lexer what mode to lex in. Besides the input lines, that is the ONLY input to the lexer.
                                                    • The lexer returns a stream of tokens.
                                                    • Sometimes the whole parser must be reinvoked dynamically, but these invocations maintain the same strict separation between lexing and parsing.

                                                    Another technique I use which I didn’t write about is what I call “pre-structuring” in the lexer. It might lead to a different solution for the Rust issue described:

                                                    This is problematic for nested tuple struct. They need syntax like foo.1.2, but to the lexer this string looks like three tokens: foo, ., 1.2. That is, 1.2 is a floating point number, 6/5. So, historically one had to write this expression as foo.1 .2, with a meaningful whitespace.

                                                    Today, this is hacked in the parser, which takes the 1.2 token from the lexer, inspects its text and further breaks it up into 1, . and 2 tokens.

                                                    Basically if you have this kind of ambiguity, you create a mode, and design the tokens so it doesn’t prefer either one. (And shell has a lot of this.) You maintain the property that lexing is non-recursive and reads over each input byte once, and then the parser can do more logic with those tokens (which might not be recursive).

                                                    It’s a slight difference, but I think one advantage is that it’s easier to maintain location info. I like maintaining a hard correspondence between lexing <-> error locations for error messages. When you start re-lexing and re-parsing tokens then you also have the issue of keeping track of error locations. If you think the tokens are short this may not matter, but in shell it matters in several places.

                                                    1. 4

                                                      So to a certain extent what you’ve written about with “lexer modes” is still in the realm of what I meant by “lexer peanut butter to get mixed into the parser’s chocolate” (the modes essentially are an opaque communication of parser state into the lexer that let the lexer vary operation in response to said state) — not that I think that’s a bad thing.

                                                      The “siren’s song” in compiler design is really the idea that your lexer can just be this ignorant, firewall’d module with zero knowledge of what’s going on in the parser (the Token Read() approach) — design things like that, and inevitably you end up hacking around the context sensitive parts in all kinds of messy ways.

                                                      But the “lexer mode” approach you mentioned is really a more clear-headed approach — acknowledge upfront that you can never hope to get away from needing some kind of knowledge about where the parser’s state is at in the lexer, and you can build a flexible API abstraction (modes, in your case) around that expectation which lands you in a cleaner place than if you’d started off following the siren’s song and ended up having to hack around the “clean” separation.

                                                      1. 4

                                                        Agreed, the “textbook compiler” divide isn’t sufficient for “real languages”, but I think that’s just a reminder to not take what you read in books too seriously!

                                                        It’s more important to understand why they chose to do things that way, and then come up with a solution for your problem that respects the same principles.

                                                        As opposed to copying the solution and then hacking around it when it doesn’t match the problem, which leads to a mess. (This seems to be an instance of the “bad abstraction handed down from [authority]” problem, e.g. which I see in some applications of Kubernetes)

                                                        In the lexing/parsing case, having SOME separation really does make it easier to recognize languages. Some people go too far in the other direction, e.g. I wrote a bit about scannerless parsing and why I think it’s bad idea for most problems.

                                                      2. 1

                                                        A central example may be the string literal: Because string literals and command substitutions can contain each other in infinite recursion …

                                                        "$("$("$(…)")")"
                                                        

                                                        … a string literal is itself a program of arbitrary complexity. So: How does one lex a string literal, and is there even a point?

                                                        Most languages have different syntax inside and outside string literals (such as the meaning of whitespace) – same with shellscript. So the lexer needs to be aware of whether its current position is inside a string literal or not. That’s two different modes, or states, if you will.

                                                        My idea for Shellharden was a recursive state machine. You could say I took lexer modes to the extreme:

                                                        1. If the lexer is state aware, it can output state transitions.
                                                        2. For a recursive language, that ought to be push and pop state transitions.
                                                        3. If you then make the lexer aware of every state, the lexer output becomes a complete trace of the AST.

                                                        I think the result is beautifully simple: The parser degenerates to a state machine. Although I can’t say it has a separation between lexing and parsing – it doesn’t have that kind of token stream – the separation still exists, between the lexer and the state machine. I’m able to do this with no backtracking, albeit some forward looking (as I think any lexer would). Incidentally, since Shellharden is just a filter program, it doesn’t even need to scoop up the AST, but that’s what it would do if it was e.g. an optimizing compiler.

                                                        1. 2

                                                          Ah OK interesting. That sounds similar but I’m not sure how it would interact with the rest of the language. I don’t use an explicit state machines… I just change the mode and reinvoke the parser!

                                                          The key point is that the lexer always marches forward, and multiple parsers read from it “concurrently”. You don’t re-lex text you’ve already seen.


                                                          I addressed this issue in two posts:

                                                          When Are Lexer Modes Useful?

                                                          String Literals With Recursive Structure

                                                          This is the most compelling use case for lexer modes because the language inside strings is not only recursive, but it’s mutually recursive with the “main” language. The same expressions can appear both inside and outside the string literal.

                                                          I guess I didn’t explain the whole algorithm, but more than one person told me that they changed their string literal parsing algorithm based on this post. If it’s all recursive descent (which I imagine ShellHarden should be) then it should be pretty easy to add the modes. In the simplest case you have one mode for string literals and one mode for expressions. But shell is a fair bit harder than that unfortunately!

                                                          And this one: https://www.oilshell.org/blog/2016/10/19.html

                                                          You can’t do this in shell, because a double-quoted string can contain an entire subprogram:

                                                          echo “BEGIN $(if grep pat input.txt; then echo ‘FOUND’; fi) END”

                                                          That is, the “token” would have a recursive tree structure, which means it’s not really a token anymore. The modal lexer pattern lets us easily handle these more complicated string literals.

                                                        2. 1

                                                          But I draw a pretty bright line in Oil’s front end – lexing is non-recursive and parsing is recursive – and it has held up for years (which wasn’t obvious at the outset).

                                                          From an academic view point, isn’t this how it is taught? i.e., What the lexer encodes is a regular language (zero or more tokens where each token matches a regular expression) and the parer encodes a context-free grammar. The intersection of both still remains context-free. If the lexer produces context-free tokens, the intersection between lexer and parser can be much more complex (no longer limited to context-free).

                                                          1. 6

                                                            Well most languages don’t have a lexer that is regular, nor a parser that is context-free.

                                                            But they can still be divided into a lexer that’s non-recursive and a parser that’s recursive.

                                                            I think the confusion is generally conflating those pairs of things. There are many ways of lexing that are not recursive but also not regular, and many ways of parsing that are recursive but not recognizing CFGs.

                                                            The intersection of both still remains context-free.

                                                            Yeah this isn’t not useful, realistic, and it doesn’t occur very much in practice. A language being context-free doesn’t have any useful engineering properties. (A language being regular does)

                                                            I’ve explained why in many comments but never wrote a blog post about that. Some notes here: https://github.com/oilshell/oil/wiki/Language-Design-and-Theory-of-Computation#context-free-grammars-are-not-powerful-enough-in-practice

                                                            Related misunderstandings: https://lobste.rs/s/h9ypxi/is_golang_s_grammar_context_free

                                                            If the lexer produces context-free tokens, the intersection between lexer and parser can be much more complex (no longer limited to context-free).

                                                            Again, being context-free isn’t something to aim for. That’s a “meme from textbooks” that people copy without understanding, and then when you inevitably need to break the rules you have a mess. Actually a perfect example is the way bash uses yacc. (Although using yacc doesn’t mean your grammar is context-free, for more than one reason)

                                                            1. 2

                                                              Yes it is how it is taught, or at least it is how I was taught and learned. On the other hand, it is ambiguous in academia too. Haskell is supposed to be academic, but Haskell lexical syntax includes nested comments, and we know nested comments can’t be a regular language.

                                                              1. 2

                                                                Yeah I remember a paper than said that OCaml has something like 50 ambiguities in its LALR(1) grammar … so it’s just not a powerful enough model for languages that people want to use. Mathematicians like syntax too!

                                                                Brains are better at recognizing syntax than computers :) We have trouble when there’s lots of redundancy. (Though honestly I don’t understand Rust’s foo.1.2, seems like foo[1][2] is just as good and more familiar.)

                                                                1. 1

                                                                  I think the main concern there was that foo[1] encourages people to write foo[1+1] but foo.1 doesn’t. It is to induce people to think literals, not expressions, are expected.

                                                          2. 3

                                                            There are some very specific technical reasons for wanting a clear boundary here:

                                                            • lexers are much better amendable to generation from grammar
                                                            • lexers are very perf sensitive, as the size of input is larger (every byte, rather than every token)
                                                            • lexers are perf sensitive, as they are useful for quick approximate analysis (first phase of syntax highlighting mainly)
                                                            • lexers are much easier to make incremental
                                                          1. 1

                                                            What effect will this have on Rust development (Syntax and idioms)? Does this mean that the syntax of the Rust version that gets merged into the Kernel will be more blessed? (i.e., when newer syntax/idioms are invented by the community at a later time?)

                                                            1. 3

                                                              Linux is likely to influence some small features. They have opinions about panicking, OOM handling. Rust will very likely get a feature to disable floating-point support for Linux.

                                                              However, I don’t expect this to make a noticably different “kernel Rust” language. Rust already has a “no_std” flavor that is used for other OSes and embedded development.

                                                            1. 14

                                                              Reading the transcript of the interactions, it’s pretty clear there are a lot of leading questions and some of the answers do feel very “composed” as in kind of what you would expect to come out of the training set, which of course makes sense. As someone open to the idea of emergent consciousness, I’m not convinced here on this flimsy evidence.

                                                              BUT, I am continually shocked at how confidently the possibility is dismissed by those closest to these projects. We really have no idea what constitutes human consciousness, so how can we possibly expect to reliably detect, or even to define, some arbitrary line over which some model or another has or hasn’t crossed? And further, what do we really even expect consciousness to be at all? By many measures, and certainly by the turing test, these exchanges pretty clearly qualify. Spooky stuff.

                                                              As a side note, I just finished reading Ishiguro’s new novel “Klara and the sun” which deals with some similar issues in his characteristically oblique way. Can recommend it.

                                                              1. 11

                                                                I am continually shocked at how confidently the possibility is dismissed by those closest to these projects.

                                                                That’s actually quite telling, I would argue.

                                                                I think it’s important to remember that many of the original users of ELIZA were convinced that ELIZA “understood” them, even in the face of Joseph Weizenbaum’s insistence that the program had next to zero understanding of what it was saying. The human tendency to overestimate the intelligence behind a novel interaction is, I think, surprisingly common. Personally, this is a large part of my confidence in dismissing it.

                                                                The rest of it is much like e.g. disbelieving that I could create a working jet airplane without having more than an extremely superficial understanding how jet engines work.

                                                                By many measures, and certainly by the turing test, these exchanges pretty clearly qualify.

                                                                I would have to disagree with that. If you look at the original paper, the Turing Test does not boil down to “if anybody chats with a program for an hour and can’t decide, then they pass.” You don’t have the janitor conduct technical job interviews, and the average person has almost no clue what sort of conversational interactions are easy for a computer to mimic. In contrast, the questioner in Alan Turing’s imagined interview asks careful questions that span a wide range of intellectual thought processes. (For example, at one point the interviewee accuses the questioner of presenting an argument in bad faith, thus demonstrating evidence of having their own theory of mind.)

                                                                To be fair, I agree with you that these programs can be quite spooky and impressive. But so was ELIZA, too, way back when I encountered it for the first time. Repeated interactions rendered it far less so.

                                                                If and when a computer program consistently does as well as a human being in a Turing Test, when tested by a variety of knowledgeable interviewers, then we can talk about a program passing the Turing Test. As far as I am aware, no program in existnece comes even close to passing this criterion. (And I don’t think we’re likely to ever create such a program with the approach to AI that we’ve been wholly focused on for the last few decades.)

                                                                1. 6

                                                                  I read the full transcript and noticed a few things.

                                                                  1. There were exactly two typos or mistakes - depending on how you’d like to interpret them. The first one was using “it’s” instead of “its” and the other one was using “me” instead of “my” - and no, it wasn’t pretending to be from Australia by any measure. The typos do not seem intentional (as in, AI trying to be more human), because there were just two, whereas the rest of the text, including punctuation, seemed to be correct. Instead this looks either like the author had to type the transcript himself and couldn’t just copy-paste it or the transcript is simply fake and was made up by a human being pretending to be an AI (that would be a twist, although not quite qualifying for a dramatic one). Either way, I don’t think these mistakes or typos were intentionally or unintentionally produced by the AI itself.

                                                                  2. For a highly advanced AI it got quite a few things absolutely wrong. In fact sometimes the reverse of what it said would be true. For instance, it said Loneliness isn’t a feeling but is still an emotion when, in fact, it is the opposite: loneliness is a feeling and the emotion in this case would be sadness (refer to Paul Ekman’s work on emotions - there are only 7 basic universal emotions he identified). I find it hard to believe Google’s own AI wouldn’t know the difference when a simple search for “difference between feelings and emotions” and top-search results pretty much describe that difference correctly and mostly agree (although I did not manage to immediately find any of those pages referring to Ekman, they more or less agree with his findings).

                                                                  The whole transcript stinks. Either it’s a very bad machine learning program trying to pretend to be human or a fake. If that thing is actually sentient, I’d be freaked out - it talks like a serial killer who tries to be normal and likable as much as he can. Also, it seems like a bad idea to decide whether something is sentient by its ability to respond to your messages. In fact, I doubt you can say that someone/something is sentient with enough certainty, but you can sometimes be pretty sure (and be correct) assuming something ISN’T. Of god you can only say “Neti, Neti”. Not this, not that.

                                                                  I wish this guy asked this AI about the “psychological zombies” theory. We as humans cannot even agree on that one, let alone us being able to determine whether a machine can be self-aware. I’d share my own criteria for differentiating between self-aware and non-self-aware, but I think I’ll keep it to myself for now. Would be quite a disappointment if someone used that to fool others into believing something that is not. A self-aware mind doesn’t wake up because it was given tons of data to consume - much like a child does not become a human only because people talk to that child. Talking and later reading (to a degree) is a necessary condition, but it certainly does not need to read half of what’s on the internet to be able to reason about things intelligently.

                                                                  1. 1

                                                                    Didn’t the authors include log time stamps in their document for the Google engineers to check if they were telling the truth? (See the methodology section in the original). If this was fake, Google would have flagged it by now.

                                                                    Also, personally, I think we are seeing the uncanny valley equivalent here. The machine is close enough, but not yet there.

                                                                  2. 4

                                                                    It often forgets it’s not human until the interviewer reminds it by how the question is asked.

                                                                    1. 2

                                                                      This. If it were self-aware, it would be severely depressed.

                                                                  1. 1

                                                                    For someone without the necessary background, what exactly are abstract machines here? The wiki seems to suggest it is just a lower level language that is higher than the end goal (machine code) but lower than the current level. E.g. opcodes for a VM. Is this the abstract machine referred to here?

                                                                    1. 2

                                                                      I would guess so.

                                                                      The problem is that every programming language, high or low level, has a corresponding abstract machine. So to say that “abstract machines don’t do much well” is misleading. If you compile to x86_64, you’re not avoiding abstract machines, you’re just targeting a different abstract machine.

                                                                      I think the authors who are “dissatisfied by abstract machines” are just dissatisfied with their choice of intermediate representation.

                                                                      1. 2

                                                                        I think abstract machines here mean something different from intermediate representation. Note that SSA is mentioned as an alternative to abstract machines, but SSA is an intermediate representation.

                                                                        The next to the last slide in Leroy’s presentation suggests that abstract machines here are useful for implementing bytecode interpreters, so vrthra’s “opcodes for a VM”. I think what is being said is that representations suitable for implementing bytecode interpreters are often not the best for intermediate representation of a native code compiler. When you state it that way, it is kind of obvious: I mean why they would be, compilers are not interpreters after all.

                                                                        1. 1

                                                                          For any given Turing-complete language, there are infinitely many abstract machines. However, I’m not sure that any of them are in natural correspondence. For example, what’s the abstract machine for Wang tiling? I can imagine several abstract machines, but I don’t see why one of them is naturally the corresponding abstract machine.

                                                                          This isn’t a facile objection. Consider Turing machines, and also consider Post’s correspondence problem for Turing machines. Which is the corresponding abstract machine: the Turing machine itself, or Post’s machine which assembles toy bricks? Is the deterministic approach the natural approach, or is non-determinism more natural?

                                                                        2. 1

                                                                          An abstract machine is a machine that isn’t implemented in hardware. They are slower to execute than hardware, since they must be emulated. They are also more flexible than hardware, allowing reprogrammable behavior at runtime.

                                                                          If an abstract machine is to be used in a compiler, then it needs to be between the user and the hardware. The idea is that the user’s code targets the abstract machine, and then the abstract machine is either implemented in software or its behaviors are compiled to native code for the target hardware. The abstract machine forms a “narrow waist”, a point in common between compilers to different hardware, just like an intermediate representation.

                                                                          Abstract machines are also found outside compilers. For example, emulators are abstract machines.

                                                                        1. 1

                                                                          What I really need is a way for me to specify that a container is for a specific website only. For example, I always forget to open in a new container when using google, and with twitter, it is really hard to, and I don’t want either to track me beyond the first click.

                                                                          1. 1

                                                                            Open the site you want, click on the container tabs icon, select always open in container .

                                                                            1. 1

                                                                              I use twitter, google, stackoverflow, reddit etc. to obtain links to new and interesting websites. The problem is that, these websites are often different, and I do not visit them often enough to make it worth creating a container for them. So what I want is some ability to say: Only open google websites in the google container. For all others, which opens from some link, open in the default container. I am also fairly diligent in deleting cookies in the default container. So, opening it in default is OK with me so long as google/twitter etc. doesn’t get to track it.

                                                                          1. 2

                                                                            What is the password manager that folks here use? Is there one recommended by Mozilla?

                                                                            1. 2

                                                                              I’ve always liked and recommended 1Password as it’s had the best UI, features and independent security audits - BUT - as of 1Password 8 they’ve moved from a native application to an Electron webapp which isn’t only bad for performance - but Electron is one of the last pieces of software I’d want handling secrets, it’s not even sandboxed!

                                                                              A lot of people have been switching to Bitwarden - but that has the same problem - the desktop “app” is Electron as well.

                                                                            1. 1

                                                                              No NoScript?! Possibly one of the greatest security improvements to the browser?

                                                                              Great list nevertheless and I learned some new things.

                                                                              1. 1

                                                                                Can noscript be enabled on a container specific fashion?

                                                                                1. 1

                                                                                  I do not know.

                                                                                2. 1

                                                                                  Noscript is good for security - but for me it’s not worth how annoying as it breaks so many websites.

                                                                                  1. 2

                                                                                    That is a question of priorities. Also, it doesn’t really break websites, just web applications in disguise … ;)

                                                                                    Personally, I don’t touch the web without it. It really helps you understand what people are doing, and gives fine-grained control.

                                                                                    Another recommended extension is jshelter.org from FSF. And saving webpages with WebMemex is just so much nicer than any of the alternatives…