Threads for silentbicycle
-
Am I the only one who finds “Felleisen is abusive” to be the less important takeaway? January 2020 was 16 months ago – given that Matthew B is posting this now, has the Racket community really spent 16 months making excuses for abusive behavior?
-
Probably much, much longer than 16 months.
My only impression of Felleisen is from a talk at Strange Loop, where he was extremely That Confrontational Guy In The Audience during questions. I find it very easy to believe he’s a bully in general.
Edit: It was yomimono’s talk, which was from nearly six years ago.
-
Is there a video of this situation?
-
Very likely, but I don’t remember what talk it was. Someone else might.
Edit: Linked above.
-
-
That’s right, it was your talk. 😬
-
Thanks. I’ve skimmed the video and the presentation seems to be well done.
But the short answer to the question whether there is a video of the situation is: “no”.
-
It still happened, though, and there were plenty of people in the room. Are you assuming that everybody for years who has independently had the experience of him being a bully is lying unless there’s a video?
-
No, I’m not assuming anyone is lying. But sometimes a person can say the truth that happens to be incorrect. I simply don’t know that until I see it. You might be really well informed since you’ve been there and you saw it on your own eyes, but I didn’t. I simply wanted to check for myself how a “confrontational guy” sounds and behaves. Is that so bad I’m not taking it on faith?
-
-
Thanks. I’ve skimmed the video and the presentation seems to be well done.
Aw, thanks!
Some years ago I went looking for the video of this Q&A to try to get a more objective view of what the questions/comments had been, which is why I knew offhand that it wasn’t attached to the talk video. My own memory of the experience is a blur (as it is for most talks), so I myself rely mostly on other folks’ recollections. I will say that Q&A experience was more “difficult” than most I’ve been through, including presentations at academic conferences where difficult questions are encouraged.
I don’t think this is particularly good “evidence” either, for what it’s worth. I think even if it had been posted, it wouldn’t be very illustrative, because IIRC none of the audience questions were on-mic, and most of Matthias’s questions and comments were long enough that I had trouble summarizing and repeating them on-mic.
-
-
-
-
-
-
-
When I was a student at Northeastern, Felleisen was well known for being “scary”. I was never actually clear on what that entailed, and wasn’t sure if it was just that he was intense, or gave hard assignments, or was outright abusive, or had a German accent, or what. I never actually took his classes, since he was mostly teaching grad students at the time. This was in 2009 to 2011.
I think this piece gives me a better understanding of what other students were talking about.
-
-
This same article is posted on HN and there is a flurry of comments saying that this kind of usage of Lua is bad because the configuration file can take over the program and other security concerns. From reading a bunch of such comments, all spoken with the tone of “I’m an expert!”, I came to realize that these people don’t know Lua at all.
It is a very common pattern for programs embedding Lua like this to create clamped-down environments that expose only a selected part of the language and it’s libraries to the running script. You can craft an environment with the exact functions and access you desire, and if the script tries to access something that isn’t there, well, it is an error because that function doesn’t exist.
This is a built-in feature of the language, even though it changed API between Lua 5.1 and the more recent versions, it is still there.
Lua is not too powerful for this, Lua has the exact power you need.
-
Not only is it a built-in feature of the language, it’s an important part of Lua’s origins – See the paper The Evolution of Lua, particularly the section 3 about SOL and DEL.
-
If anyone’s curious as to whether this is an exaggeration; here’s the actual code needed to sandbox the loading of a file like this so it only has access to a limited number of safe functions in LuaJIT:
local chunk = loadfile("config.lua") setfenv(chunk, {add_bodies = sandbox.add_bodies, other_fn = sandbox.other_fn}) chunk()In this case the worst you could do with malicious code is loop forever and chew up CPU. (There are ways to solve that too, but they’re not quite as trivial as the sandboxing.)
-
That works for Lua 5.1. Lua 5.2 (or higher) changed how environments work, so there you do:
local chunk = loadfile("config.lua","t",{ add_bodies = sandbox.add_bodies , other_fn = sandbox.other_fn }) chunk()The “t” parameter disalllows pre-compiled Lua code (malicious bytecode is a problem in Lua).
-
Also, if you are bullish about in process sandboxing, WASM LUA exists: https://github.com/vvanders/wasm_lua
WASM has good capabilities to restrict memory use and you can restrict the maximum runtime.
-
-
posted on HN and there is a flurry of comments […] all spoken with the tone of “I’m an expert!”
So on-brand for the orange site.
This is a built-in feature of the language, even though it changed API between Lua 5.1 and the more recent versions, it is still there.
Do you know what’s the status of LuaJIT on that?
-
Do you know what’s the status of LuaJIT on that?
The old API can be implemented in terms of the new API: https://leafo.net/guides/setfenv-in-lua52-and-above.html
But I’m not sure about vice versa. LuaJIT does not implement the new
_ENVsystem of 5.2, tho it offers many other 5.2 features backported. -
-
-
-
-
Interesting read, but I don’t understand one detail of the argument: what makes Perl more secure than the other scripting languages mentioned?
-
Taint checking comes to mind, and Perl has it. I think OpenBSD folks prefer tech where it’s easier to do the right thing; doing the right thing in shell or php can require more effort, with painstaking, error-prone effort to avoid pitfalls.
-
-
Ruby code ages poorly compared to perl, though. I’ve been on too many projects where code written in ruby a year or two earlier at most had already been broken by language or dependency changes.
-
-
-
We may be talking past each other here. I said that they could keep a check on the dependency changes, by which I meant that they would author code in such a way that it does not require external dependencies (or at least not few enough that they couldn’t vendor them), which wouldn’t be any different from what they’re doing with Perl already. This means that this downside of the Ruby ecosystem could be mitigated. And language changes they’d just have to accept and roll with, but I hold that Ruby rarely introduces breaking changes.
OpenBSD will have to vendor $language_of_choice in any case because that’s how the BSDs’ whole-OS approach works.
-
-
-
-
-
-
-
-
-
-
What would bring any security then, as opposed to just helping catch bugs? Barring “legitimate” cases of correct algorithms outliving their usefulness (e.g. the math behind crypto algorithms getting “cracked” to the point where it’s feasible to mount attacks on reasonably-priced hardware) virtually all security issues are bugs. Things like shell injections are pretty easy to miss when writing shell code, no matter how careful you are.
-
Probably the taint mode that the other commenter mentioned
-
But that’s exactly what taint checking does: it helps you catch bugs that occur due to executing stuff that’s under the user’s control. Some of these can be exploited for security reasons, but security isn’t the only reason why you want this – it’s just as good at preventing a user enumeration attack as it is at preventing accidental “rm -rf /”
-
-
-
-
-
-
-
Is there a way to add new languages? There’s a couple idioms in k I’d like to add.
-
There doesn’t seem to be :|
Supported languages are Ada, C, Caml, Clojure, Cobol, C++, C#, D, Dart, Elixir, Erlang, Fortran, Go, Haskell, JS, Java, Kotlin, Lisp, Lua, Obj-C, PHP, Pascal, Perl, Prolog, Python, Ruby, Rust, Scala, Scheme, VBThere are pull requests (https://github.com/Deleplace/programming-idioms/issues/93) but not sure how quick they’re being answered to.
-
-
While I don’t own them, I have access to servers with 40+ cores. They’re fantastic for running fuzzers. Since it’s ultimately a search problem, fuzzing benefits a lot from parallelism.
-
I can really recommend UNIX Network Programming, Volume 1: The Sockets Networking API (3rd Edition)
It’s from 2003 but still relevant today. It’s very concise and complete in my opinion and more to the point than Advanced Programming in the Unix Environment when it comes to socket programming.
-
It’s older than that, isn’t it? I have a copy on my shelf and I’m almost positive I bought it in 1998. I still go to it on an irregular basis… it’s no stretch to call it my longest-lived useful tech book right next to Cormen/Leiserson/Rivest’s algorithms text.
-
-
It is indeed a huge book, but has concise coverage of a zillion different Unix APIs.
-
Those statements are not mutually exclusive.
I did this stuff in my first professional programming job (working on the DPOP mail server, mostly, in C) and it’s a deep and broad field.
-
-
-
silentbicycle
3 years ago
|
link
| on:
What resources would you recommend to learn socket programming ?
At the same time you learn about socket programming, learn to use wireshark – wireshark is a network protocol analyzer, it will capture traffic and let you see what messages are going back and forth (including protocol headers). Use netcat and/or your preferred language’s socket library to do various things on the network, and see what the traffic looks like. That should complement reading about the protocols, it’ll help to verify whether your socket library is doing what you want, and wireshark is a great tool for investigating all kinds of network issues.
I learned from beej’s network guide (C-based), followed by Steven’s Advanced Programming in the Unix Environment and The Linux Programming Interface. There’s a lot of overlap between those two (the latter has more coverage of Linux-specific extensions), but you may find one or the other clicks with you better.
-
I remember using Wireshark during my studies… Thanks for the idea, I will use it !
-
-
What does the expression at the end mean?
Looking at the manual it looks like
|is Max/Or. I also saw that |/ is defined as “Max-Over”?-
-
Ah, for some reason I thought it was a pun to the effect of “hah, you noobs”.
-
-
| is max. It’s also boolean or. If you wanted the minimum, it’d be
&/, because&is min/boolean and.The APLs have teased apart lots of common operations into atomic parts that combine cleanly, sometimes unpacking them further than other languages go. The single-argument form of & (“where”) is a good example:
&1 2 3 0 1 1 2 2 2It counts up, repeating each successive number based on the next number in the argument.
&5 5 5 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2Okay, so that makes the pattern clearer. By why is that useful?
& 0 0 0 1 0 1 1 0 1 0 3 5 6 8Ah ha – “what are the offsets of the 1s?”
x:10?!1000 / draw 10 random numbers 0 to 999 x / print them 379 998 594 106 191 686 123 845 495 700 x < 500 / what values are less than 500 1 0 0 1 1 0 1 0 1 0 x[&x<500] / slice x by indices where x is less than 500 379 106 191 123 495So it combines with a conditional to become a sort of SELECT, but it also combines with other operators in a predictable way, and the implementation is straightforward.
-
-
-
If you’re doing popcount over large, constant bit arrays, then one practical approach is to precompute the total in fairly large blocks (say, every 64 or 256 KB), and also individual counts in smaller blocks (perhaps 4 or 16 KB). Use the total from the last large block before the offset, add the smaller blocks, and then only do popcount for the few remaining words – this can give you a count (rank) in constant time, and it’s especially useful when all of the words are compressed and would need conversion to popcount.
Many succinct data structures are built on top of these operations, so making them fast is critical.
-
Comments that have typos or are otherwise sloppy seem more likely to have bugs near them, either nearby in the code or in the same commits.
Code pushed by people just before going on vacation should get extra scrutiny.
If you’re converting/compressing and transferring something, multiple layers of checksums can help figure out which layer is screwing it up. It’s easier to add them and then disable them once everything is working properly.
Sometimes starting from scratch and rewriting a prototype of something from memory is a good way to rethink the core design.
-
Comments that have typos or are otherwise sloppy seem more likely to have bugs near them, either nearby in the code or in the same commits.
I agree with this in principle, except that there’s too much noise in this signal from people who are just bad at spelling and/or grammar. The real signal is when someone is being uncharacteriscally sloppy, which requires you to be familiar with that person’s language habits.
Code pushed by people just before going on vacation should get extra scrutiny.
Oh good grief yes, a thousand times. I’d go even further, and say that people should not be permitted to push code right before a vacation, at all.
-
Yes, when somebody whose general writing voice you know is being uncharacteristically sloppy. That’s a great way of putting it.
I’m thinking of someone at a previous job who usually wrote well, but typos in comments often correlated with bugs – using the wrong constant for some calibration value, for example – and I realized it could have been a sign he was mentally exhausted but hadn’t realized it yet.
-
-
Comments that have typos or are otherwise sloppy seem more likely to have bugs near them, either nearby in the code or in the same commits.
This is generally true, but not always. I have a colleague that everybody recognizes as a “superproductive programmer” who is unable to write a sentence without a few orthography or grammar errors. Even worse, he uses inconsistent formatting and spacing in his code, and he does not care. Yet, I have never seen anybody else able to write a continuous stream of useful and working code without bugs and very well-organized overall. Some people seem to just think at a higher level (and not at a lower level at the same time). This is not a matter of typing speed, he also types quite slowly.
-
-
Does Lua have a good package manager? I tried LuaRocks but it has… problems:
-
Keep in mind that maybe half the people using Lua are using it inside of some other system that may already have its own package manager (or strong opinions about packaging that don’t apply elsewhere). It’s designed for embedding as well as standalone use.
-
-
Lua libraries fall into two categories: single-file, zero-dependency (in which case I just plop it in the repo for the application I’m using) or libraries with really complex builds that interop with C code, in which case I use apt-get for them because they tend to be very mature and stable, and I never need the latest version. In your case
luasocketfalls into the latter camp, and it ships with an HTTP client.-
luasocketdoesnt appear to be useful for larger files-
I wonder if this is a platform-specific issue or something; I can’t reproduce any problem with the snipped you pasted using the 100MB file.
-
-
-
-
-
-
-
-
It looks like you are trying to use LuaRocks on Windows with some “non-classical” setting.
I haven’t used Windows for about a year, but last time I did https://github.com/Tieske/luawinmulti was the best option. LuaRocks 3 supposedly makes it better but there may still be issues because afaik none of the core devs really uses Windows…
-
-
There was also a Strange Loop talk about this in 2018.
It is (was?) built on top of lpeg, but trying to address some usability issues with PEGs.
-
Thanks for sharing, this is a handy reference.
Aside: IMO logical expressions with
==should bebooland notint.-
This depends on the C standard –
boolisn’t in C89, so it can become a portability issue.-
-
Indeed, and I’m inclined to agree otherwise.
I’ve worked on a couple projects that needed C89 compatibility (mostly in embedded), and I begrudgingly keep greatest to
-std=c89just so that it’s always an option. There are some features that are only available when it’s built with >= C99 though.
-
-
-
-
Anyone have recommendations for other types of testing for C? Like property testing and mutation testing, etc.
-
For property-based testing, look at theft.
-
-
The comment field there doesn’t permit editting and correcting typos…..
So let me try again here…
In a galaxy far far away….
Larry Wall wondered why he needed to learn 3 pretty bad languages, sh, awk, sed…., and devised perl as the Grand Unifying Language.
Perl sadly borrowed too much from it’s inspirations, and wasn’t much more readable.
Then Matz came along and resolved to borrow the best from perl and scheme and ….. and make something more powerful than them all, yet more readable.
It’s called Ruby.
And yes, you can do everything in Ruby, in one line if you must, that you can do in bash, awk, sed, jq, perl…. but in a more powerful and maintainable form.
All this has been available for decades, why are we (still) bashing (pun intended) our heads against the Lowest Common Denominator?
-
-
Relevant links:
https://nithinbekal.com/posts/ruby-sed-awk/
https://tomayko.com/blog/2011/awkward-ruby (ruby’s awk history)
-
-
Compare:
# Official way of naming Go-related things: $ grep -i ^go /usr/share/dict/* | cut -d: -f2 | sort -R | head -n1 goldfishVersus Ruby:
puts(Dir['/usr/share/dict/*-english'].map do |f| File.open(f) .readlines .select { |l| l[0..1].downcase == 'go' } end.flatten.sample.chomp)Simple example, but I think it demonstrates that doing various basic and common tasks are quite a bit more complex to do in Ruby than in the shell.
That doesn’t mean I’m always in favour of shell scripts – I got that example from an article I wrote saying you shouldn’t use shell scripts – but there are definitely reasons shell scripting persists, even though we have things like Perl and Ruby.
In that article I wrote “I regret writing most shell scripts [..] and my 2018 new year’s pledge will be to not write any more”. I’ve mostly failed at that new years’ pledge, and have happily continued shelling about. I have started rewritting shell script prototypes to other languages at the first sign of getting hairy though, and that seems like a middle ground that is working well for me (I should update/ammend that article).
-
To be fair, it looks like most of the additional complexity in the Ruby code comes from reading files: the first command in the pipeline,
grep -i ^re glob, is what becomesDir[glob].map do |f| File.open(f) .readlines .select { |l| l[0..1].downcase == re } end.flattenThe rest of the script contributes very little to the Ruby code.
I suspect this is a recurring theme when trying to replace shell pipelines with programs. Only Perl avoids some of this additional complexity for reading files, I think.
-
puts Dir['/usr/share/dict/*-english']. flat_map { |f| File.readlines(f).grep(/^go/i) }. sample -
-
Actually you used very little shell there in your first example.
You also used grep, cut, sort and head.
Why do you assume the
backtickoperator and the | operator for io doesn’t exist in ruby? In fact why do people assume shell and jq do not exist if you use ruby?Personally I tend to reduce the number of tools involved to reduce the cognitive load of needing to understand each tool to understand the one liner.
I balance that against considerations like going IO.read(”|sort -u fileName”) can be a huge performance boost
Anyhoo… some examples of ruby onliners
http://reference.jumpingmonkey.org/programming_languages/ruby/ruby-one-liners.html
-
-
Because code in sed or awk that worked a decade ago (or, hell, two years) still works. Ruby code seems to bit rot faster than any other language I’ve use for nontrivial work.
Also, with awk, I could put it down for a year, then use it again, and everything I’d need to be productive fits in a small man page. (The same seems to be true of sed, though I don’t use it much.) The Ruby ecosystem moves a lot faster, and if you haven’t been following it closely, catching up will add extra work. (Whether it’s actually going anywhere is neither here nor there.)
Yes, awk is a more limited language, but that’s a trade-off – there are upsides, and I know which I’d prefer.
-
Not true.
The awk scripts I wrote decades ago with in Solaris awk which is not quite the same thing as gnu awk.
Well thought out growth in a language is good.
I find the maintenance burden in ruby rolling forward with language versions is very low.
Doubly so since rubocop will often autocorrect stuff.
-
-
I don’t know Ruby. But for me these are the reasons why I am writing more and more bash programs:
-
Bash is my command line. So I am doing a lot of small steps, file modifications, comparing, searching analysing. At some point I can see that some of the steps can be composed and I pull them out of the history, try them out on the console and at some point put them into a script. If Ruby would have a REPL in which I can do all the operations that I am doing on the command line with less typing and more comfort, I would maybe give it a try.
-
Bash is on every Linux box. Ruby is not.
-
Ruby does have a REPL. It’s called IRB and it comes with every Ruby installation. I use it exactly as you describe, for composing small programs iteratively.
-
Are you using the Ruby REPL as your daily all-time console or just when you have in mind to create a program? I am asking honestly because I do not know anything about Ruby or their REPL and I am quite interested how good this REPL is as a replacement for the daily life?
My point is that shell scripts are a by-product of using the shell for doing manual tasks. And I get better and better at my shell usage, and even after 20 years of shell usage I am still discovering new features or ways to do something in a more efficient way. While the shell language is really ugly, but being very succinct plus the composition of unix commands, the history, the prompt customization, the possibility to have vi mode for editing (and I probably forgot a lot of features), all this makes using shell such an efficient tool.
-
Well, no, not as my daily shell. I dislike shell scripting enough that I switch to Ruby pretty quickly if I’m having to spend any amount of time or effort on a task, but it’s not meant to be a replacement for bash/zsh/fish.
-
-
-
-
Bash is on every Linux box. Ruby is not.
So is ed.
However sudo apt install ruby solves that problem.
And yes, ruby does have a REPL.
-
-
Have fun with ed then, it’s the Standard!
-
-
-
-
-
Mostly, because picking up enough jq, awk and sed to be useful is faster than learning the ins and outs of Ruby?
I suppose you could make a similar argument about learning Ruby one-liners, but by the time I’m writing a very long bash script, I’m probably writing a larger program anyway, either in Go or Python. Ruby as a language doesn’t have much appeal to me, at least at the moment.
Awk, at least, fits very nicely into a small space right next to regex. jq is a bit fiddilier to pick up, but very nice for basic stuff. Sed, I still don’t have down very well, but also is nicely regex adjacent.
-
I regularly write sed one liners to do refactorings on my Ruby code. Usually the sed call is fed by the result of grep or find. I could write a Ruby one liner to do the same, but it would be a much longer line and escaping would be much more difficult. Ruby is simply not a replacement for the convenience of sed.
And maintainability is a red herring here: the whole point of something like sed is that you use it for one-off commands.
-
I’m not that experienced with jq, but when it comes to awk (and sed), one of their benefits is that you can easily write a program in the shell, since they act as glue between pipe operations.
For example, to filter out all lines that have less than 4 characters, all you have to write is
... | awk 'length >= 5' | ...no imports or types required. It was made for stuff like this, which makes it easy to use. I’ve only read a book about Ruby a few years ago, but to process stdin/out this was should require a bit more overhead, shouldn’t it?
-
One part of your history lesson is missing: Paul McCarthy and Steve Russell saw what was going to happen and pre-emptively invented Lisp. And yes, you can do everything in Lisp, in one line if you must, that you can do in bash, awk, sed, jq, perl… but in a more powerful and maintainable form.
;)
-
-
It was Yoko’s fault.
-
-
Ruby equivalents of the basic
awkandsedexamples from the article, as examples of Ruby one-liner structure:- AWK:
awk '{print $1}' logs.txt- Ruby:
cat logs.txt | ruby -ne 'puts $_.split[0]' - Ruby:
cat logs.txt | ruby -ane 'puts $F[0]'
- Ruby:
- sed:
sed 's/^[^ ]*//' logs.txt |sed 's/"[^"]*"$//'- Ruby:
cat logs.txt | ruby -ne 'puts $_.gsub(/^[^ ]*/, "").gsub(/"[^"]*"$/, "")'
- Ruby:
- AWK:
-
-
This was a nice review. I admit I wasn’t able to finish the book, as I constantly got stuck on the confusing PlusCal syntax.
At the time of reading it, I was getting some weird edge cases in a distributed protocol at work, and trying to come up with a minimal example that could be reproduced was proving to be quite difficult. I got the book after reading a couple of Hillel’s posts and seeing the announcement here, with the idea of using TLA+ to solve our issue.
I already had a written specification (although in pseudocode form, and quite loose), and some intuition of where the problem was coming from, so I thought it would be a simple task. Nevertheless, I was never able to do it. Trying to reduce the real implementation to a model that TLA could understand, and figuring out the right level of detail, proved to be too time consuming, plus I had other, more urgent things to do, and in any case the problem was rare enough to be able to postpone finding a solution for a bit.
Fast forward a couple of months, and I finally decided to come back to the problem. This time, though, I implemented a simplified version of the system, in real code, and ran it through a property-based test (poor man’s model checker) that would execute actions against the system, and specified that the edge case would never happen. I didn’t get the prettiest execution on the first try, but I managed to refine it iteratively and armed with existing knowledge of the domain. The final execution was maybe 10 lines long as easily explainable in a whiteboard, which I consider a great success.
The whole thing took maybe a week of work (counting reading about model-checking, property tests and learning to use the testing library) and proved much simpler than trying to tackle a real TLA spec. I’m not saying my approach was better, TLA can express so much in terms of temporal properties that trying to model that some other way will be painful. But sometimes, the simplest approach works best.
-
I’ve also had a lot of success using property-based testing as a sort of model checker, but there are trade-offs to keep in mind. I’ve been learning TLA+, off and on, and don’t feel it’s at all redundant with property-based testing.
TLA+ will check the model exhaustively, whereas every property testing library I’m aware of is probabilistic – because they’re semi-randomly exploring, it’s never certain when they’ve checked all meaningful cases, and some are better than others about avoiding redundant checks. Sometimes the partiality is fine, and just random stress testing is a good way to feel out an implementation, but total state-space coverage is compelling.
Where TLA+ checks a model of the code, a property testing library will check the implementation (or perhaps a subset). It’s often worth doing both! I mostly work in C these days (and use my theft library for property-based testing), so testing for mistakes in the implementation details is pretty important, but a non-code model checker could still be really valuable during system design.
-
TLA+ will check the model exhaustively, whereas every property testing library I’m aware of is probabilistic.
For sure! A naïve property might not find the example you’re looking for. I know I didn’t get anything on my first try. I had to play a lot with the model generator and the shrinking procedure, to the point that I ended up defining explicitly certain parameters of the generator (number of concurrent processes, number of operations a process is able to execute, etc).
It’s often worth doing both!
Won’t disagree here, if I had already known TLA or any other specification language, I would’ve use that for sure (and if I ever get the time I plan to come back to the book and work through it, plus Lamport’s book), but when you’re facing constraints in the available time you have, going for a simpler solution can get you far enough.
-
-
-
Working on wrapping up and releasing some personal projects I’ve had mostly ready for a while.
I just pushed skiparray, an unrolled skip list library for C. It has roughly the same relation to a regular skip list as a B-Tree has to a basic balanced binary tree.
Aside from that, getting back to learning TLA+, working through hwayne’s book.
-
I usually turn to this blog post when I need a reference for the Fisher-Yates shuffle.
It’s a good algorithm to have on hand, whether you’re shuffling a data structure or just indices into it. I’ve found a couple really elusive bugs by running tests shuffled multiple ways.
-
The author has a pretty explicit bias toward Earley parsing, and using
LL(k)overLR(k)methods (which I mostly share). There’s a wealth of information here, but he’s missing a couple other significant strands of generalized parsing research outside of Marpa’s particular Earley variant (perhaps because they don’t fit within his narrative).GLR (Generalized LR):
- Tomita, LR parsers for natural languages, 1984.
- Tomita, Efficient parsing for natural language, 1986.
- Scott and Johnstone, Generalised bottom up parsers with reduced stack activity, 2005. This segues into their later work with Earley and GLL.
GLL (Generalized LL):
- Scott and Johnstone, GLL Parsing, 2010.
- Afroozeh and Izmaylova, Faster, Practical GLL Parsing, 2015.
Outside of Earley, GLL seems like a very practical generalized parsing approach. Instaparse is one implementation.
Earley / Shared Packed Parse Forests:
- Scott, SPPF-style parsing from Earley recognisers, 2008 (and several related papers by Scott and Johnstone). Note: I’ve never been able to get the approach described in the paper implemented correctly, and not for lack of trying.
Earley Intersection Parsing (not sure if there’s a canonical name for this):
- Bar-Hillel, Perles, and Shamir, On formal properties of simple phrase structure grammars in Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 1961. Proves some important results about intersecting automata and context free grammars.
- Chapter 13 (“Parsing as Intersection”) of Grune and Jacobs (also cited elsewhere in his timeline), particularly 13.4 (pgs. 437-439): This describes Bar-Hillel’s Intersection Parsing approach using contemporary CS & parsing terminology, and then suggests combining it with Earley parsing. While the basic intersection parsing method produces an astonishing amount of dead-end nodes to garbage-collect later, Earley parsers limit searching to productions reachable from the start symbol. If the completer is modified to produce non-terminals in the intersection parsing format (which is easy), intersection parsing nicely handles producing the parse forest (with structural sharing, when ambiguity produces multiple derivations).
I’ve been working on a C library for Earley Intersection parsing, and an awk-like, pattern-match-directed language based on it, but working on testing them thoroughly tends to lead me to working on theft instead.
-
Thanks for details about alternatives.
I have played around with Bison’s GLR option and have almost managed to create a C parser that does not require special handling of typedefs in the lexer (ambiguities still appearing at runtime for a few constructs).
Grune and Jacobs’ Parsing Techniques - A Practical Guide is sitting in a pile waiting to be read (the first edition was manageable, the second looks daunting)
-
I have a print copy of the second, and it’s never struct me as daunting – reading it cover to cover, perhaps, but it’s well suited to dipping into for just specific techniques, with a well-curated bibliography for further details.
-
-
-
-
Not sure, sorry.
-
-
-
I’m particularly interested in Earley parsers because some use cases of mine assume ambiguity (reverse-engineering binaries, scraping damaged data), and the chart that Earley parsers build up supports several operations beyond just recognizing & building parse trees:
- what terminals/nonterminals would advance the current parse(s) in progress? (i.e., autocomplete)
- if we don’t assume where the starting position is, what overlapping instruction encodings are there?
- if we inserted a fake nonterminal here, would enough of the parse have completed to match any instances of (some structure) between here and there?
- incremental re-parsing of changing input, since earlier columns in the chart are constant once the parser has moved on.
-
Here’s the feature I wish awk had: regex groups.
Awk has deep support for regexes, allowing a script to grab lines matching subtle patterns and process them.
Awk has deep support for tabular data, allowing a script to pick out individual columns, process them, and spit out new columns in response.
For some reason, Awk doesn’t let you write a regex that matches interesting parts of a line, and then process them. The best you can do is write a regex that matches all the interesting parts of a line, then write a bunch of
gsub()calls with regexes that match each individual part. Those regexes are similar to the original, but each is different in small, easy-to-get-wrong ways.I get it, it’s an old language, I shouldn’t judge it against my modern perspective. But still, writing a regex to pick out parts of a line, and then a block of code to process them, feels like the awkiest thing ever, and it baffles me that it doesn’t work like that.
If you have
gawk, you can usematch()function and access matched portions via array. You’d still need a loop if there are multiple matches:The reason awk (nawk) doesn’t is because its regex implementation is based on automata, and adding capture groups to automata is essentially an open research problem. It certainly wasn’t well understood back then, and it still doesn’t seem to be now, in 2021. I’ve been chipping away at it for a while. The interactions with anchoring get incredibly gnarly.
If you look at implementations that do support captures, such as PCRE, they tend to use a completely different operational model. PCRE is interpreted, with a JIT compiler to close some of the performance gaps, but it’s still really easy to write regexes that would cause PCRE to block for weeks due to backtracking. It has resource limits in place to prevent DoS attacks, but then the matches just fail with an error code indicating which resource (stack depth, etc.) limit was exceeded.
Something awk-like could be based on a more feature-ful regex implementation, but it would change the cost model considerably. (It sounds like gawk does; I’m only familiar with nawk.) At that point, I’d like to see it also have support for more sophisticated parser tooling.
Yeah this is exactly why I use
gawk, because you can capture groups with thematch()function. It might be the only reason I use gawk!FWIW Bash actually lets you capture groups with
[[ $x =~ $pat ]]and${BASH_REMATCH[1]}, etc. If for some reason you’re using bash but not gawk.Oil makes this a little nicer with
(x ~ pat)and_match(1)or_match('name')I agree this feature is missing from the traditional tools in the POSIX spec.
Quick random idea. What if we combined structural regular expressions + awk? That would be something! I haven’t seen structural regexes used in practice at all.
If I recall correctly, the structural regex paper includes a psuedocode example for an awk-like language based on structural regexes. Just looking at it, it seemed like the Obvious Right Thing To Do, and it makes me sad that nobody (including myself) seems to have implemented such a thing.