Kragen Javier Sitaker

My summary is that it's about one or two allocations per nanosecond on CF Bolz's machine, an AMD Ryzen 7 PRO 7840U, presumably on one core, and it's about 11 instructions per allocation. This is about 2–4× faster than my pointer-bumping arena allocator for C, kmregion†, which is a similar number of instructions on the (inlined) fast path. But possibly that's because I was testing on slower hardware. I was also testing with 16-byte initialized objects, but without a GC. It's about 10× the speed of malloc/free. I don't know that I'd recommend using kmregion, since it's never been used for anything serious, but it should at least serve as a proof of concept. ______ † http://canonical.org/~kragen/sw/dev3/kmregion.h http://canonical.org/~kragen/sw/dev3/kmregion.c http://canonical.org/~kragen/sw/dev3/kmregion_example.c

Reminds me of Bytebeats [1]. My favorite being echo "g(i,x,t,o) {return((3&x&(i*((3&i>>16?\"BY}6YB6%\":\"Qj}6jQ6%\")[t%8]+51)>>o))<<4);};main(i,n,s) {for(i=0;;i++)putchar(g(i,1,n=i>>14,12)+g(i,s=i>>17,n^i>>13,10)+g(i,s/3,n+((i>>11)%3),10)+g(i,s/5,8+n-((i>>10)%3),9));}"|gcc -xc -&&./a.out|aplay It's incredible how much musical variation you can get out of such a relatively small function. [1] http://canonical.org/~kragen/bytebeat/

Here's a Heighway dragon (it follows the same idea as your Koch snowflake). It could be shorter if 45 degree turns were possible. rrr@4[a rrr rrr rrr [[email protected]]f rrr [[email protected][b cf rrr df rrr rrr rrr cf rrr rrr rrr df rrr]]f rrr cf rrr rrr rrr df] http://canonical.org/~kragen/sw/dev3/skitch#!rrr@4[[email protected]… and a Lévy dragon [email protected][a rrr rrr rrr [[email protected]]f rrr bf bf rrr bf]

If you asked me what the 4 best documents regarding bootstrapping are i'd say: * Egg of the Phoenix (Blog post) - http://canonical.org/~kragen/eotf/ * The Cuniform Tablets of 2015 (Blue-sky academic research) - http://www.vpri.org/pdf/tr2015004_cuneiform.pdf * Preventing The Collapse of Civilization (Video) - https://www.youtube.com/watch?v=pW-SOdj4Kkk * Coding Machines (scifi story about trusting-trust attack) - https://www.teamten.com/lawrence/writings/coding-machines/

It's worth learning as the prima facie example of a high-level language on top of the register memory model. http://canonical.org/~kragen/memory-models/ Its perceived close relationship to the machine is precisely due to the fact that it exposes pointers & does not handle its own memory allocation with a garbage collector, both of which are direct consequences of the register model. Why not Assembly? Because it's not a language that encodes propositions first class, and that's the grounding for structured/procedural programming. The majority of software requires some structured element and so regressing towards the assembly model, where abstractions are implicit, doesn't get new programmers on the path to understanding how to write nearly all software.

You might enjoy http://canonical.org/~kragen/sw/urscheme/ -- it's by someone who'd just written his first compiler, with links to other sources he found inspiring (one of them mine). C89 I think has too much complexity for the amount of power it offers. lcc is a nice example: Norman Ramsey said he asked one of the authors what he learned in writing it, and got an answer like "Not to write a compiler in C." But anyway the book about it https://sites.google.com/site/lccretargetablecompiler/ is very good. http://www.cs.princeton.edu/~appel/modern/ is my favorite general text.

We're doing motivational posters here now? Okay, we can do that. I recommend: the Tao of Programming http://www.canonical.org/~kragen/tao-of-programming.html

I don't know if it qualifies as a joke, but I loved and learned from the Tao of Programming -- http://www.canonical.org/~kragen/tao-of-programming.html. Too long to paste here, but it's stood the test of time.

Bookmarked "toread" -- it looks to be a really insightful look at byte-code that compares and analyzes a bunch of language implementations. What an interesting guy. He runs a blog masquerading as a mailing list (that's what this link is from: "Kragen-tol" is a mailing list for "Kragen thinking out loud") which looks to be full of lots of interesting and incredibly detailed essays across a wide range of subjects. His homepage (http://www.canonical.org/~kragen/) doesn't mention the mailing list at all (?), but it does have a bunch of other intriguing and random things, like a list of all the people he knows, for the purpose of telling search engines about it: http://www.canonical.org/~kragen/pik/

Ah, this one takes me back. It's almost a pity no one else has mentioned the classic Tao of Programming by Geoffrey James: http://www.canonical.org/~kragen/tao-of-programming.html A bit dated now, and it looks like ESR has improved on the concept considerably, but this little classic will always be my favorite: "Each language has its place within the Tao. But do not program in Cobol if you can avoid it."

The "Setting up more compose sequences" of http://canonical.org/~kragen/setting-up-keyboard.html is also helpful. (I don't use those exact sequences, some of them make little sense to me... but it's nice to see a bunch of examples on how to create your own.) The compose key is one of my favorite underutilized features in Linux.

Graydon Hoare's "One-Day Compilers" (http://www.venge.net/graydon/talks/mkc/html/mgp00001.html) presentation is worth a look. It uses OCaml to build a compiler for basic makefiles (using C as an intermediate language). Kragen Sitaker has a great collection of links for amateur compiler writers on his Ur-Scheme (http://www.canonical.org/~kragen/sw/urscheme/) page. This paper (http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf) by Abdulaziz Ghuloum is also very interesting - he shows step-by-step how to write a simple native-code Scheme-like compiler by writing small C functions, compiling them with gcc, and then saving the assembly output. ("Since we don’t know yet how to do that, we ask for some help from another compiler that does know: gcc.") Heavy theory about optimizing? Nope. Demystifying and inspiring? Heck yeah.

It's "connection timed out" for me, but if it's this: http://www.canonical.org/~kragen/tao-of-programming.html then it's old and damn good. Loved in on my fortunes...

> I don't think your revision of the "S-expression" grammar is in accordance with the normal use of the term; it says ()() is an S-expression, when conventionally it's considered to be two of them. If that's what you want, then adding the outer *() is fine, but you should probably drop the leading * on the recursive call *ex, because otherwise the grammar is ambiguous. You're totally right, sorry! It's an important aspect of S-exps that I overlooked. I forgot that a typical Lisp file is not a valid S-expression, but a concatenation of a bunch of them. Plus maybe some whitespace/comments prepended. So an S-expression syntax, as normally defined, is not closed under concatenation like Jevko. To solve that (assuming it's a desirable feature as I do) purely syntactically, without talking about the REPL, you'd need another top-level syntax. So why not simplify things and make one that meets this criterion by itself? Which makes me think of another aspect where Jevko is simpler. The restrictions Jevko puts on a unicode sequence are that the escape character must be followed by itself or a square bracket and that unescaped square brackets must be balanced. This is pretty much an exhaustive one-sentence description that would allow you to validate or generate a Jevko. A similarly simple description is impossible to state for S-expressions. I tried and I came up with (for your minimal defnition of S-exp): The restrictions S-expr puts on a unicode sequence are that it must…

A classic, from http://www.canonical.org/~kragen/tao-of-programming.html > There was once a programmer who was attached to the court of the warlord of Wu. The warlord asked the programmer: ``Which is easier to design: an accounting package or an operating system?'' > ``An operating system,'' replied the programmer. > The warlord uttered an exclamation of disbelief. ``Surely an accounting package is trivial next to the complexity of an operating system,'' he said. > ``Not so,'' said the programmer, ``when designing an accounting package, the programmer operates as a mediator between people having different ideas: how it must operate, how its reports must appear, and how it must conform to the tax laws. By contrast, an operating system is not limited by outside appearances. When designing an operating system, the programmer seeks the simplest harmony between machine and ideas. This is why an operating system is easier to design.'' > The warlord of Wu nodded and smiled. ``That is all good and well, but which is easier to debug?'' > The programmer made no reply.

You've mentioned this before, here:[1] https://news.ycombinator.com/item?id=5549627 (2013) There you link to writing of your own from 1997, "Real News": http://www.canonical.org/~kragen/real-news.html A book that explores some of these concepts (in terms of the Net's impact on traditional news media) is Andrew L. Shapiro's book The Control Revolution (1999).[2] What numerous prognosticators (yourself, Epic, Shapiro, and more) got right was that the traditional print media would be profoundly disrupted. What seems to have been broadly missed was that digital, algorithmic media would allow for individual targeting and manipulation, if not by the publishers or platforms themselves then by those who exploited them, either in partnership or as hostile attackers. ________________________________ Notes: 1. Not stalking, honest! I was looking for this particular comment to come back and respond to it. 2. Not to be confused with James Beniger's similarly-titled 1986 book. Shapiro does reference it, both are well worth reading. Shapiro's is far more politically-conscious. Shapiro's: https://www.worldcat.org/title/control-revolution-how-the-internet-is-… Beniger's: https://www.worldcat.org/title/ltltthegtgt-control-revolution-technolo…

> This sounds really interesting! Cheers! > I'm happy my article was helpful to you. It was just the thing! Very helpful. Thank you for writing it. > I really like how your notebooks integrate (judiciously chosen) execution trace display with explanation. I think this is something literate programming benefits a lot from. Cheers again. I find those traces aesthetically pleasing in and of themselves. I can imagine a (strange, niche) art gallery that had large prints of them on display. Jupyter notebooks have so many good things going on. (Not that they're perfect, but they hit a sweet spot IMO.) > I wonder if there's a way to include a smooth gradient from specific examples like your V('80 P') to more general cases, either with abstract interpretation or a Bret-Victor-style overwhelming battery of data points. I'm sure there is, there are so many possibilities. Just the traces alone could be animated or made into (partial) graphs (have you seen http://pythontutor.com/ ?) Concerning abstract interpretation, if you squint a little, the Prolog code already does that. Markus Triska suggested using the CLP(FD) integer constraints for the math primitives, which was brilliant, so it's doing a kind of abstract interpretation. You can give it a completely general stack "type" (just a logic variable) and it will tell you, e.g. '+' is: int(A), int(B) -> int(A+B) and so on. It's also pretty easy to replace the main operators to get a different (but related)…

BTW I remember your "memory models" post from a few years ago, and I found it insightful! It got me thinking about many related things. http://canonical.org/~kragen/memory-models/ Around that time I'd noticed that the stringly-typed languages of shell, awk, and make have no garbage collection. They're value oriented and not reference oriented. The goal of Oil was basically to "upgrade" shell into something more like Python, and on the surface that looks straightforward, but the reference model vs. value model makes it pretty different. I've gone back and forth on that... whether I should just slap GC into a shell, or whether I should try to preserve the value model while making it less stringly-typed and more expressive. I have a more ambitious idea for a language where every value is essentially a pair (Go-like string slice, structured data), but I probably won't get to that in the near term. For a concrete example, I noticed from writing some HTML processors that both DOM and SAX APIs have a bunch of flaws for processing semi-structured text. ----- Also, on the other point, let's consider these two possibilities about Chez / Dybvig: 1) Dybvig is an average programmer who got "superpowers" from Lisp, i.e. got a 10x boost in productivity. 2) Dybvig and Chez are an outlier, e.g. like Fabrice Bellard and his recent QuickJS (and other projects), or Lattner and LLVM/Clang/Swift. The salient point is that these projects have nothing to do with Lisp. It's obviously…

You are against Easter Eggs, I gather? ;) More seriously, of these two implementation for Python's str.lower(), which is "minimal"?: for (i = 0; i < n; i++) { int c = Py_CHARMASK(s[i]); if (isupper(c)) s[i] = _tolower(c); } for (i = 0; i < n; i++) { int c = Py_CHARMASK(s[i]); s[i] = _tolower(c); } I suspect most would say the second is minimal, but the first is what Python uses, because it's measurably and distinctly faster than the second, and that extra performance is worth the extra maintenance overhead. That's one reason I believe that programming-as-art metaphors don't really apply. Minimalism as an art form not the same as minimizing the cost function of different uncertain factors. Anyway, this reminds me of a story from the Tao of Programming, http://www.canonical.org/~kragen/tao-of-programming.html : There was once a programmer who was attached to the court of the warlord of Wu. The warlord asked the programmer: ``Which is easier to design: an accounting package or an operating system?'' ``An operating system,'' replied the programmer. The warlord uttered an exclamation of disbelief. ``Surely an accounting package is trivial next to the complexity of an operating system,'' he said. ``Not so,'' said the programmer, ``when designing an accounting package, the programmer operates as a mediator between people having different ideas: how it must operate, how its reports must appear, and how it must…

I've had the same experience as Tesla, though not so extreme as to cause problems. For as long as I can remember I have enjoyed extremely detailed "daydreams" where I explore worlds and meet people inspired by the books I read. I suspect this is fairly common in children, but I did it right through high school, university, and several years in the workplace. The real question is: how much benefit does having a strong and well exercised imagination have for a technical career? (I assume it's very useful for artists). I've found that software development gets a large boost. The more of the design you can hold in your head on once, the better the coder is able to anticipate the consequences of their decisions. When debugging, the programmer is able to see the entire state of the application that must have predicated it, experiment with a range of fixes, all before writing any code. I love this quote from The Tao of Programming[1]: "Sometimes there are difficult problems. I see them coming, I slow down, I watch silently. Then I change a single line of code and the difficulties vanish like puffs of idle smoke." [1] http://www.canonical.org/~kragen/tao-of-programming.html

From The Tao of Programming, 3.1 (http://www.canonical.org/~kragen/tao-of-programming.html#book3) There once was a man who went to a computer trade show. Each day as he entered, the man told the guard at the door: ``I am a great thief, renowned for my feats of shoplifting. Be forewarned, for this trade show shall not escape unplundered.'' This speech disturbed the guard greatly, because there were millions of dollars of computer equipment inside, so he watched the man carefully. But the man merely wandered from booth to booth, humming quietly to himself. When the man left, the guard took him aside and searched his clothes, but nothing was to be found. On the next day of the trade show, the man returned and chided the guard saying: ``I escaped with a vast booty yesterday, but today will be even better.'' So the guard watched him ever more closely, but to no avail. On the final day of the trade show, the guard could restrain his curiosity no longer. ``Sir Thief,'' he said, ``I am so perplexed, I cannot live in peace. Please enlighten me. What is it that you are stealing?'' The man smiled. ``I am stealing ideas,'' he said.

Reminds me of the six programming language memory models: https://canonical.org/~kragen/memory-models/

See these past submissions - https://hn.algolia.com/?q=bytebeat And these longer explanations on what bytebeat is: - http://canonical.org/~kragen/bytebeat/ - https://countercomplex.blogspot.com/2011/10/algorithmic-symphonies-fro… - https://stellartux.github.io/websynth/guide.html

I view it as a shame that I haven't encountered more instances of prose in this (scientific/technical) context. I think it adds to the 'quality' of the piece. From a selfish point of view I would enjoy if I encountered more of this style of writing while being introduced to topics. Although, I'm also not contributing any writing of any quality to any corpus. So there is dissonance there. As a complete aside, I thought your writing here http://canonical.org/~kragen/memory-models/ was helpful. And I now know about BNF!

Thanks a lot, I appreciate the effort required to write in detail. I will work through it. I could not find your email in your HN bio. I wonder if you have any public "queue " people can send interesting things they are working on and perhaps seek for guidance/opinion. Edit: found loads of emails here, http://canonical.org/~kragen/about/ :)

That doesn't seem to be line-wrapped correctly either. How about this one? http://www.canonical.org/~kragen/tao-of-programming.html

An oldie, but a goodie: > Hardware met Software on the road to Changtse. Software said: ``You are Yin and I am Yang. If we travel together we will become famous and earn vast sums of money.'' And so they set forth together, thinking to conquer the world. > Presently they met Firmware, who was dressed in tattered rags and hobbled along propped on a thorny stick. Firmware said to them: ``The Tao lies beyond Yin and Yang. It is silent and still as a pool of water. It does not seek fame, therefore nobody knows its presence. It does not seek fortune, for it is complete within itself. It exists beyond space and time.'' > Software and Hardware, ashamed, returned to their homes. ...from The Tao of Programming [0] [0] http://canonical.org/~kragen/tao-of-programming.html

> it depends on what you're implementing them in, but in a term-rewriting language all you need is the two lines above Okay, so what do I type those two lines into to implement that? How many lines of code does that involve? > more recently i implemented a term-rewriting language in i386 assembly, it's about 800 bytes and 400 instructions: http://canonical.org/~kragen/sw/dev3/qfitzah.s but i haven't quite figured out how to handle arithmetic, i/o, and variadic lists Have you considered having a parameter stack that arithmetic operators pull their arguments from and push their results onto? Oh wait... ;-)

From the example http://canonical.org/~kragen/sw/netbook-misc-devel/rotcube.py how does this for expression work? cube = [(x, y, z) for x in -1, 1 for y in -1, 1 for z in -1, 1] My interpreter can't do it, and I don't really understand how this is supposed to work :) Thanks!

Somebody wrote down their thinking on exactly this subject: http://canonical.org/~kragen/eotf/