Daniel Pocock: Understanding what lies behind Trump and Brexit
A new release of anytime is now on CRAN following the four releases in September and October.
anytime aims to convert anything in integer, numeric, character, factor, ordered, ... format to POSIXct (or Date) objects -- and does so without requiring a format string. See the anytime page for a few examples.
Release 0.1.0 adds several new features. New functions utctime() and utcdate() parse to coordinated universal time (UTC). Several new formats were added. Digit-only formats like 'YYYYMMDD' with or without 'HHMMSS' (or even with fractional secodns 'HHMMSS.ffffff') are supported more thoroughly. Some examples:
R> library(anytime)
R> anytime("20161107 202122") ## all digits
[1] "2016-11-07 20:21:22 CST"
R> utctime("2016Nov07 202122") ## UTC parse example
[1] "2016-11-07 14:21:22 CST"
R> NEWS file summarises the release:
Courtesy of CRANberries, there is a comparison to the previous release. More information is on the anytime page. For questions or comments use the issue tracker off the GitHub repo.Changes in anytime version 0.1.0 (2016-11-06)
- New functions
utctime()andutcdate()were added to parse input as coordinated universal time; the functionality is also available inanytime()andanydate()via a new argumentasUTC(PR #22)- New (date)time format for RFC822-alike dates, and expanded existing datetime formats to all support fractional seconds (PR #21)
- Extended functionality to support not only YYYYMMDD (without a separator, and not covered by Boost) but also with HHMM , HHMMSS and HHMMSS.ffffff (PR #30 fixing issue #29)
- Extended functionality to support HHMMSS[.ffffff] following other date formats.
- Documentation and tests have been expanded; typos corrected
- New (unexported) helper functions
setTZ,testOutput,setDebug- The
testFormat(andtestOutput) functions cannot be called under RStudio (PR #27 fixing issue #25).- More robust support for non-finite values such as
NA,NaNorInf(Fixing issue #16)
This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. Please report excessive re-aggregation in third-party for-profit settings.
I had mentioned previously that I had been forced to purchase a new laptop. I decided that I didn't want another Thinkpad. The Lenovo ones no longer have the high quality they had in the IBM days and while support is still pretty good by todays dismal standards it's not worth the premium price. (If I'm buying it with my own money that is.) I had heard good thing about Dells' Linux support so I looked into their offerings and ended up buying a Precision 7510. Mind you this model came with Windows 7 installed but I didn't mind. As I wanted to install Debian according to my own specs anyway, I was ok with just knowing that the hardware would be compatible. So I prepared a Jessie USB installation stick (This model doesn't have a CD/DVD drive.) and shrunk down the Windows installation (but not deleted it altogether for reasons to be explained below.)
At this point it is traditional to give a long, tortured account of how Heaven and Earth had to be moved to get Linux installed. But that is a thing of the past. The combination of good hardware and the excellent work of the debian-installer team, made the setup a breeze with only a couple of minor bumps in the road. One is that the kernel on the Jessie cd was not quite up to snuff. Downloading 4.6.0 from backports did the trick. Post-install, to get the most out of my nifty new 4K display, I needed the latest, alas non-free, nvidia-drivers. And for stable wifi (I always install over ethernet for this reason) I had to install the firmware-iwlwifi package. Everything else even my printer either "just worked" or needed only minor fiddling around.
Having used this machine for a while, the biggest problem I have is with the keyboard. It is nowhere near as tactile and comfortable to use as the old IBM Thinkpads. Even Lenovo Thinkpad keyboards are better. I'm a hunt-and-peck type myself but it is annoying. I think a real touch typist would hate it. The cursor and home, end, page up, page down etc. keys are in the wrong place and home and end are actually function keys. There is a pointer and a trackpad and two sets of mouse buttons which seems like a waste of space. In fact much space is wasted everywhere, space which could be used to improve the keyboard. Other than that I like it. The battery life is not the best but fairly good. It's a bit heavier than I was used to but I've gotten used to it. Although I didn't go with the SSD option, it is not that noisy; again you can get used to it. All in all, I think it is worth it for the price.
# mount /dev/mapper/vg00-root /mnt
# chroot /mnt
# grub-install /dev/sda
error: cannot find a device for /boot/grub (is /dev mounted?).
sigh
# mount /dev/sda5 /boot
special device /dev/sda5 does not exist.
Well, /dev is mounted but it does indeed not contain a device called sda5.
# /etc/init.d/udev start
udev requires a mounted procfs. not started.
Very well then.
# mount -t proc none /proc
# /etc/init.d/udev start
Nope. proc needs sysfs.
# mount -t sysfs none /sys
# /etc/init.d/udev start
Still no. You get a warning about how it is a bad idea to run udev from an interactive shell and there is still not /dev/sda5. Time to start googling again. It turns out what I should have done is open another shell from the installer environment and do...
# mount --bind /dev/ /mnt/dev
Now I can mount /boot/grub and reinstall grub and it should all work right?
I should be so lucky. Ok back to square one. I now did what I should have done in the first place and searched the Debian wiki. Sure enough there is a page which deals exactly with my predicament. Finally I get everything installed correctly and triumphantly reboot into Linux.
Of course now Windows doesn't work again...
apt-file list -I dsc <source-pkg> would fail to list all files in the source package if said file was also in other packages.apt-file search --filter-suites unstable lintian/checks/# echo 'apt-file::Search-Filter::Suite "unstable";' >> /etc/apt/apt-file.confFor the suite filter, either a code name ( sid ) or a suite name ( unstable ) will work. Please note that the filters are case-sensitive suites/code names generally use all lowercase, whereas origins appear to use title-case (i.e. unstable vs. Debian ).
gpg2 --gen-key. Create an additional signing subkey.
gpg2 --refresh-keys is parcimonie, which uses tor and refreshes keys one at a time.
.gnupg/random_seed
gpg2 --gen-key. Create an additional signing subkey.
gpg2 --refresh-keys is parcimonie, which uses tor and refreshes keys one at a time.
.gnupg/random_seed
This post is cross-posted on the MAMI Project blog
here.
In today s Internet we see an increasing deployment of middleboxes. While
middleboxes provide in-network functionality that is necessary to keep networks
manageable and economically viable, any packet mangling whether essential for
the needed functionality or accidental as an unwanted side effect makes it
more and more difficult to deploy new protocols or extensions of existing
protocols.
For the evolution of the protocol stack, it is important to know which network
impairments exist and potentially need to be worked around. While classical
network measurement tools are often focused on absolute performance values,
PATHspider performs A/B testing between two different protocols or different
protocol extensions to perform controlled experiments of protocol-dependent
connectivity problems as well as differential treatment.
PATHspider 1.0.1 has been released today and is now available from GitHub, PyPI and Debian unstable. This is
a small stable update containing a documentation fix for the example
plugin.
PATHspider now contains 3 built-in plugins for measuring path transparency to
explicit congestion notification, DiffServ code points and TCP Fast Open. It s
easy to write your own plugins, and if they re good enough, they may be
included in the PATHspider distribution at the next feature release.
We have a GitHub
repository you can fork that has a premade directory structure for new
plugins. You ll need to implement logic for performing the two connections, for
the A and the B tests. Once you ve verified your connection logic is working
with Wireshark, you can move on to writing Observer functions to analyse the
connections made in real time as PATHspider runs. The final step is to merge
the results of the connection logic (e.g. did the operating system report a
timeout?) with the results of your observer functions (e.g. was ECN
successfully negotiated?) and write out the final result.
We have dedicated a section of the
manual to the development of plugins and we really see plugins as
first-class citizens in the PATHspider ecosystem. While future releases of
PATHspider may contain new plugins, we re also making it easier to write
plugins by providing reusable library functions such as the tcp_connect()
function of the SynchronisedSpider that allows for easy A/B testing of TCP
connections with any globally configured state set. We also provide reusable
observer functions for simple tasks such as determining if a 3-way handshake
completed or if there was an ICMP unreachable message received.
Before proceeding, here is some context: When building new things, it is usually better to use the Elliptic Curve technology algorithm Ed25519 instead of RSA. There is also ECDSA which has had a comparatively slow uptake, for a number of reasons that is widely available and is a reasonable choice when Ed25519 is not available. There are also post-quantum algorithms, but they are newer and adopting them today requires a careful cost-benefit analysis.
First some background. RSA is an asymmetric public-key scheme, and relies on generating private keys which are the product of distinct prime numbers (typically two). The size of the resulting product, called the modulus n, is usually expressed in bit length and forms the key size. Historically RSA key sizes used to be a couple of hundred bits, then 512 bits settled as a commonly used size. With better understanding of RSA security levels, the common key size evolved into 768, 1024, and later 2048. Today s recommendations (see keylength.com) suggest that 2048 is on the weak side for long-term keys (5+ years), so there has been a trend to jump to 4096. The performance of RSA private-key operations starts to suffer at 4096, and the bandwidth requirements is causing issues in some protocols. Today 2048 and 4096 are the most common choices.
My preference for non-2048/4096 RSA key sizes is based on the simple and na ve observation that if I would build a RSA key cracker, there is some likelihood that I would need to optimize the implementation for a particular key size in order to get good performance. Since 2048 and 4096 are dominant today, and 1024 were dominent some years ago, it may be feasible to build optimized versions for these three key sizes.
My observation is a conservative decision based on speculation, and speculation on several levels. First I assume that there is an attack on RSA that we don t know about. Then I assume that this attack is not as efficient for some key sizes than others, either on a theoretical level, at implementation level (optimized libraries for certain characteristics), or at an economic/human level (decision to focus on common key sizes). Then I assume that by avoiding the efficient key sizes I can increase the difficulty to a sufficient level.
Before analyzing whether those assumptions even remotely may make sense, it is useful to understand what is lost by selecting uncommon key sizes. This is to understand the cost of the trade-off.
A significant burden would be if implementations didn t allow selecting unusual key sizes. In my experience, enough common applications support uncommon key sizes, for example GnuPG, OpenSSL, OpenSSH, FireFox, and Chrome. Some applications limit the permitted choices; this appears to be rare, but I have encountered it once. Some environments also restrict permitted choices, for example I have experienced that LetsEncrypt has introduced a requirement for RSA key sizes to be a multiples of 8. I noticed this since I chose a RSA key size of 3925 for my blog and received a certificate from LetsEncrypt in December 2015 however during renewal in 2016 it lead to an error message about the RSA key size. Some commercial CAs that I have used before restrict the RSA key size to one of 1024, 2048 or 4096 only. Some smart-cards also restrict the key sizes, sadly the YubiKey has this limitation. So it is not always possible, but possible often enough for me to be worthwhile.
Another cost is that RSA signature operations are slowed down. This is because the exponentiation function is faster than multiplication, and if the bit pattern of the RSA key is a 1 followed by several 0 s, it is quicker to compute. I have not done benchmarks, but I have not experienced that this is a practical problem for me. I don t notice RSA operations in the flurry of all of other operations (network, IO) that is usually involved in my daily life. Deploying this on a large scale may have effects, of course, so benchmarks would be interesting.
Back to the speculation that leads me to this choice. The first assumption is that there is an attack on RSA that we don t know about. In my mind, until there are proofs that the currently known attacks (GNFS-based attacks) are the best that can be found, or at least some heuristic argument that we can t do better than the current attacks, the probability for an unknown RSA attack is therefor, as strange as it may sound, 100%.
The second assumption is that the unknown attack(s) are not as efficient for some key sizes than others. That statement can also be expressed like this: the cost to mount the attack is higher for some key sizes compared to others.
At the implementation level, it seems reasonable to assume that implementing a RSA cracker for arbitrary key sizes could be more difficult and costlier than focusing on particular key sizes. Focusing on some key sizes allows optimization and less complex code.
At the mathematical level, the assumption that the attack would be costlier for certain types of RSA key sizes appears dubious. It depends on the kind of algorithm the unknown attack is. For something similar to GNFS attacks, I believe the same algorithm applies equally for a RSA key size of 2048, 2730 and 4096 and that the running time depends mostly on the key size. Other algorithms that could crack RSA, such as some approximation algorithms, does not seem likely to be thwarted by using non-standard RSA key sizes either. I am not a mathematician though.
At the economical or human level, it seems reasonable to say that if you can crack 95% of all keys out there (sizes 1024, 2048, 4096) then that is good enough and cracking the last 5% is just diminishing returns of the investment. Here I am making up the 95% number. Currently, I would guess that more than 95% of all RSA key sizes on the Internet are 1024, 2048 or 4096 though. So this aspect holds as long as people behave as they have done.
The final assumption is that by using non-standard key sizes I raise the bar sufficiently high to make an attack impossible. To be honest, this scenario appears unlikely. However it might increase the cost somewhat, by a factor or two or five. Which might make someone target a lower hanging fruit instead.
Putting my argument together, I have 1) identified some downsides of using non-standard RSA Key sizes and discussed their costs and implications, and 2) mentioned some speculative upsides of using non-standard key sizes. I am not aware of any argument that the odds of my speculation is 0% likely to be true. It appears there is some remote chance, higher than 0%, that my speculation is true. Therefor, my personal conservative approach is to hedge against this unlikely, but still possible, attack scenario by paying the moderate cost to use non-standard RSA key sizes. Of course, the QA engineer in me also likes to break things by not doing what everyone else does, so I end this with an ObXKCD.
This month s update falls onto a national holiday in Japan. My recent start as a normal company employee in Japan doesn t leave me enough time during normal days to work on Debian, so things have to wait for holidays. There have been a few notable changes in the current packages, and above all I wanted to fix an RC bug and on the way fixed also several other (sometimes rather old) bugs.
From the list of new packages I want to pick apxproof: I have written something myself for one of my rather long papers (with proofs about 60pp), where at times I had to factor out the proofs into an appendix. I did this my own way, but I would have preferred to have a nice package!
Another interesting change is the upstream merge of collection-mathextra (which translated to the Debian package texlive-math-extra) and collection-science (Debian: texlive-science) into a new collection collection-mathscience. Since introducing new packages and phasing out old ones is generally a pain in Debian, I decided to digress from the upstream naming convention and use texlive-science for the new collection-mathscience. In the end Mathematics is the most important science of all
Finally also a word about removals: Several ConTeXt packages have been removed due to the fact that they are outdated. These removals will find their way in an update of the Debian ConTeXt package in near future. The TeX Live packages lost voss-mathmode, which was retracted by the author due to various reasons. He is working on an updated version that will hopeful reappear in both TeX Live and Debian in near future.
Well, that s it for now. Here now the full list with links. Enjoy.
New packages
apxproof, bangorexam, biblatex-gb7714-2015, biblatex-lni, biblatex-sbl, context-cmscbf, context-cmttbf, context-inifile, context-layout, delimset, latex2nemeth, latexbangla, latex-papersize, ling-macros, notex-bst, platex-tools, testidx, uppunctlm, wtref, xcolor-material.
Removed packages
voss-mathmode.
Updated packages
apa6, autoaligne, babel-german, biblatex-abnt, biblatex-anonymous, biblatex-apa, biblatex-manuscripts-philology, biblatex-nature, biblatex-realauthor, bibtex, bidi, boondox, bxcjkjatype, chickenize, churchslavonic, cjk-gs-integrate, context-filter, cooking-units, ctex, denisbdoc, dvips, europasscv, fixme, glossaries, gzt, handout, imakeidx, ipaex-type1, jsclasses, jslectureplanner, kpathsea, l3build, l3experimental, l3kernel, l3packages, latexindent, latexmk, listofitems, luatexja, marginnote, mcf2graph, minted, multirow, nameauth, newpx, newtx, noto, nucleardata, optidef, overlays, pdflatexpicscale, pst-eucl, reledmac, repere, scanpages, semantic-markup, tableaux, tcolorbox, tetex, texlive-scripts, ticket, todonotes, tracklang, tudscr, turabian-formatting, updmap-map, uspace, visualtikz, xassoccnt, xecjk, yathesis.
Since some time everybody (read developer) want to run his new microservice stacks in containers. I can understand that building and testing an application is important for developers. docker command line client is something you can do, but there you leave the gap between dev and ops.
For the use cases, we are facing, Kubernetes and Mesos seems both like bloated beasts. Usman Ismail has written a really good comparison of Orchestration Engine options which goes into details.
To implement a patch, update the base image and then rebuild the application image. This will require systems and development teams to work closely together.So patching security issues in the container world changes workflow significant. In the old world operation teams mostly rolled security fixes for the base systems independent from development teams.
Here is my monthly update covering what I have been doing in the free software world (previously):
Whilst anyone can inspect the source code of free software for malicious flaws, most GNU/Linux distributions provide binary (or "compiled") packages to end users. The motivation behind the Reproducible Builds effort is to allow verification that no flaws have been introduced either maliciously and accidentally during this compilation process by promising identical binary packages are always generated from a given source.
Presented a talk entitled "Reproducible Builds" talk at Software Freedom Kosova, in Prishtina, Republic of Kosovo.
I filed my 2,500th bug in the Debian BTS: #840972: golang-google-appengine: accesses the internet during build.
In order to build packages reproducibly, one not only needs identical sources but also some external and sharable definition of the environment used for a particular build, stipulating such things such as the version numbers of the required build-dependencies. It is not currently clear how to handle these .buildinfo files after the archive software has processed them and how to make them available to the world so I started development on a proof-of-concept server to see what issues arise in practice. It is available at buildinfo.debian.net.
Chaired an IRC meeting and ran a poll to determine a regular time .
Submitted two design proposals to our wiki page.
Improvements to our tests.reproducible-builds.org testing framework:
TIFFTAG_* issues, all
the gory details in this email--lts flag for dch (see bug #762715).
It was difficult to get back to work after such a long pause, but I am
happy I was able to contribute a significant number of hours. It's a
bit difficult to find work sometimes in LTS-land, even if there's
actually always a lot of work to be done. For example, I used to be
one of the people doing frontdesk work, but those duties are now
assigned until the end of the year, so it's unlikely I will be doing
any of that for the forseable future. Similarly, a lot of packages
were assigned when I started looking at the available packages. There
was an interesting discussion on the internal mailing list regarding
unlocking package ownership, because some people had packages locked
for weeks, sometimes months, without significant activity. Hopefully
that situation will improve after that discussion.
Another interesting discussion I participated in is the question
of whether the LTS team should be waiting for unstable to be fixed
before publishing fixes in oldstable. It seems the consensus right now
is that it shouldn't be mandatory to fix issues in unstable before we
fix security isssues in oldstable and stable. After all, security
support for testing and unstable is limited. But I was happy to learn
that working on brand new patches is part of our mandate as part of
the LTS work. I did work on such a patch for tar which ended up
being adopted by the original reporter, although upstream ended up
implementing our recommendation in a better way.
It's coincidentally the first time since I start working on LTS that I
didn't get the number of requested hours, which means that there are
more people working on LTS. That is a good thing, but I am worried it
may also mean people are more spread out and less capable of focusing
for longer periods of time on more difficult problems. It also means
that the team is growing faster than the funding, which is
unfortunate: now is a good time as any to remind you to see if you can
make your company fund the LTS project if you are still running
Debian wheezy.
It all started last June when my son had his Janoi (Yagnopavita) ceremony -- the ritual by which a Brahmana boy becomes "twice-born" and eligible to study the Vedas. As well as a profound religious experience, it is also an important social occasion with a reception for as many friends and family as can attend. (I think our final guest total was ~250.) This meant new outfits for everyone which might be exciting for some people but not me. I still don't know why I couldn't just keep wearing the khes and pitambar from the puja but no, apparently that's a faux pas. So I relented and agreed to wear my "darbari" suit from my wedding. And it didn't fit. I knew I had gained some weight in the intermediate 17 years but the thing was sitcom levels of too small. I ended up having to purchase a new one, a snazzy (and shiny!) maroon number with gold stripes (or were they black stripes?) Problem having been solved, much was eaten, more weight was gained and then I forgot about the whole thing.
Tip 1: Actually Do Something.
I have over the years tried to improve my physical condition but it has never gotten very far. For instance I have a treadmill/coatrack and a couple of years ago I began using it in earnest. I got to the point where I actually ran a 10K race without dying. But I did not train systematically and I ended up in some pain which caused me to stop working out for a while and then I never got around to restarting. Diets have also failed because I don't have a clear idea of what and how much I am eating. All I know is that women go into the kitchen and when they come out they have food. By what eldritch process this occurs is a mystery, I just eat whats given to me thankful that the magic happens. Once I was moved to try and help but quickly fell afoul of the lack of well-defined algorithms in Gujarati home cooking.
"How much saffron should I add?"
"this much."
"How much is this much in SI units?"
"You're annoying me. Get out."Fast forward to March of this year. For my birthday, my wife got me a Fitbit fitness tracker. This is what I had needed all this time. It measure heart rate, distance travelled, time slept and several other pieces of info you can use to really plan a fitness regimen rationally. For example, I was chagrined to learn that sometimes when I'm at the computer, I am so immobile that the fitbit thought I was asleep. So I started planning to taken more frequent breaks. (A recent firmware upgrade has added the ability to nudge to walk atleast 250 paces each daytime hour which is handy for this.) Also by checking my heart rate I discovered that I went on the treadmill I ran too fast thereby stressing my body for little gain and ending up going too slow to get much aerobic effect. Now I can pace myself appropriately for maximum cardiac efficiency without ending up injuring myself and giving up. I also get a little more activity each day by simple changes such as taking the stairs instead of the lift and instead of getting off at the 14th street PATH I go all the way to 34th street and walk down. Tip 2: You must have data in order to see what you did right or wrong and to plan what you need to do moving forward. One caveat about these fitness trackers. They are not anywhere as accurate as a proper checkup from a doctor who specializes in such things. If you want to do any kind of pro or amateur athletics you probably should not rely on them but for the average shlub who just wants to avoid appearing on the news being winched off his sofa by the fire brigade they are good enough. Another practice I began was keeping a food diary. It can be a real eye-opener to see how much you are actually eating. It is probably much more than you thought. I am fortunate that my diet is pretty good to begin with. Vegetarian, (not vegan, Hindus eat dairy products,) mostly home-cooked with fresh ingredients, not fried or processed, and I don't drink alcohol. However there were a few optimizations I could make. I drink a lot of soda; atleast two cans a day. I really ought to stop altogether but in lieu of that I have atleast switched from Coke to Coke Zero thereby saving a lot of empty calories. I now eat 4 rotlis with my dinner instead of six. We as a family eat more green vegetables instead of potatos, skim milk instead of whole fat, canola oil instead of corn oil, and less rice and don't slather ghee on everything quite so much. One entirely new practice I've adopted that may seem faddish but works for me is intermittent fasting. The idea is to steadily train your body to need less food by eating all your days allowed amount pf calories during a 6-8 hour window and not eating at all during the remaining time. It's hard to get used to for many people but I fast atleast 2-3 times a month for religious reasons anyway so I adapted pretty quickly. The fitbit tells me how many calories I am expending and how many I can eat to maintain a healthy level of weight loss but other than that I don't bother with "food groups" or specific diets such as paleo, or low-carb etc. As long as what you eat is reasonably balanced and you are burning more calories than you are adding, it should be enough for weight loss. Indeed from the end of March to now, I've lost 3 stones (20Kg) even with the occasional "cheat" day. Tip 3: All published diets are bullshit without scientifically proven efficacy. Don't bother with them. Experiment instead and see what works for you and your metabolism. As long as you are getting all the proper nutrients (you shouldn't need a supplement unless you have an actual medical condition.) and you have a net calorie deficit, it's all good. If you eat food you enjoy, you are more likely to stick to your diet. The proper amount of sleep is one area of a healthy lifestyle I am still doing poorly in and the reasons are not all raven-related. I have always had problems with insomnia and was once actually diagnosed with sleep apnea. Losing weight has helped a lot but the fitbit is still reporting that I toss and turn a lot during the night. And that's when I'm in bed in the first place. I stay up much too late which can also lead to subsidiary bad behaviours such as midnight snacking. It's something I need to work on. Tip 4: Stop blogging at all hours of the night, It's not doing you any good. So that's what I'm doing. Moving forward, I need to deal with the sleep thing and I would also like to start some program of strength-training, I'm doing ok in terms of aerobic exercise but from what I've read, you also have to build up muscles to keep weight loss permanent. The difficulty is that it would involve joining a gym and then actually going to that gym so I've put it off for now. The immediate threat is Diwali (and Thanksgiving and Christmas...) My wife bought 4 lbs of sweets today and I can feel their presence in the fridge calling to me.
Nageru 1.4.0 is out (and on its way through
the Debian upload process right now), so now you can do live video mixing with multichannel
audio to your heart's content. I've already blogged about most of the
interesting new features, so instead, I'm trying to answer a question:
What took so long?
To be clear, I'm not saying 1.4.0 took more time than I really anticipated
(on the contrary, I pretty much understood the scope from the beginning,
and there was a reason why I didn't go for building this stuff into 1.0.0);
but if you just look at the changelog from the outside, it's not immediately
obvious why multichannel audio support should take the better part of three
months of develoment. What I'm going to say is of course going to be obvious
to most software developers, but not everyone is one, and perhaps my
experiences will be illuminating.
Let's first look at some obvious things that isn't the case: First of all,
development is not primarily limited by typing speed. There are about 9,000
lines of new code in 1.4.0 (depending a bit on how you count), and if it was
just about typing them in, I would be done in a day or two. On a good
keyboard, I can type plain text at more than 800 characters per minute but
you hardly ever write code for even a single minute at that speed. Just as
when writing a novel, most time is spent thinking, not typing.
I also didn't spend a lot of time backtracking; most code I wrote actually
ended up in the finished product as opposed to being thrown away. (I'm not
as lucky in all of my projects.) It's pretty
common to do so if you're in an exploratory phase, but in this case, I had a
pretty good idea of what I wanted to do right from the start, and that plan
seemed to work. This wasn't a difficult project per se; it just needed
to be done (which, in a sense, just increases the mystery).
However, even if this isn't at the forefront of science in any way (most code
in the world is pretty pedestrian, after all), there's still a lot of
decisions to make, on several levels of abstraction. And a lot of those
decisions depend on information gathering beforehand. Let's take a look at
an example from late in the development cycle, namely support for using MIDI
controllers instead of the mouse to control the various widgets.
I've kept a pretty meticulous TODO list; it's just a text file on my laptop,
but it serves the purpose of a ghetto bugtracker. For 1.4.0, it contains 83
work items (a single-digit number is not ticked off, mostly because I decided
not to do those things), which corresponds roughly 1:2 to the number of
commits. So let's have a look at what the ~20 MIDI controller items went into.
First of all, to allow MIDI controllers to influence the UI, we need a way
of getting to it. Since Nageru is single-platform on Linux, ALSA is the
obvious choice (if not, I'd probably have to look for a library to put
in-between), but seemingly, ALSA has two interfaces (raw MIDI and sequencer).
Which one do you want? It sounds like raw MIDI is what we want, but actually,
it's the sequencer interface (it does more of the MIDI parsing for you,
and generally is friendlier).
The first question is where to start picking events from. I went the simplest
path and just said I wanted all events anything else would necessitate a UI,
a command-line flag, figuring out if we wanted to distinguish between
different devices with the same name (and not all devices potentially even
have names), and so on. But how do you enumerate devices? (Relatively simple,
thankfully.) What do you do if the user inserts a new one while Nageru is
running? (Turns out there's a special device you can subscribe to that will
tell you about new devices.) What if you get an error on subscription?
(Just print a warning and ignore it; it's legitimate not to have access to
all devices on the system. By the way, for PCM devices, all of these answers
are different.)
So now we have a sequencer device, how do we get events from it? Can we do it in the main loop? Turns out
it probably doesn't integrate too well with Qt, but it's easy enough to put
it in a thread. The class dealing with the MIDI handling now needs locking;
what mutex granularity do we want? (Experience will tell you that you nearly
always just want one mutex. Two mutexes give you all sorts of headaches with
ordering them, and nearly never gives any gain.) ALSA expects us to poll()
a given set of descriptors for data, but on shutdown, how do you break out
of that poll to tell the thread to go away? (The simplest way on Linux is
using an eventfd.)
There's a quirk where if you get two or more MIDI messages right after each
other and only read one, poll() won't trigger to alert you there are more
left. Did you know that? (I didn't. I also can't find it documented. Perhaps
it's a bug?) It took me some looking into sample code to find it. Oh, and
ALSA uses POSIX error codes to signal errors (like nothing more is
available ), but it doesn't use errno.
OK, so you have events (like controller 3 was set to value 47 ); what do you do
about them? The meaning of the controller numbers is different from
device to device, and there's no open format for describing them. So I had to
make a format describing the mapping; I used protobuf (I have lots of
experience with it) to make a simple text-based format, but it's obviously
a nightmare to set up 50+ controllers by hand in a text file, so I had to
make an UI for this. My initial thought was making a grid of spinners
(similar to how the input mapping dialog already worked), but then I realized
that there isn't an easy way to make headlines in Qt's grid. (You can
substitute a label widget for a single cell, but not for an entire row.
Who knew?) So after some searching, I found out that it would be better
to have a tree view (Qt Creator does this), and then you can treat that
more-or-less as a table for the rows that should be editable.
Of course, guessing controller numbers is impossible even in an editor,
so I wanted it to respond to MIDI events. This means the editor needs
to take over the role as MIDI receiver from the main UI. How you do
that in a thread-safe way? (Reuse the existing mutex; you don't generally
want to use atomics for complicated things.) Thinking about it, shouldn't the
MIDI mapper just support multiple receivers at a time? (Doubtful; you don't
want your random controller fiddling during setup to actually influence
the audio on a running stream. And would you use the old or the new mapping?)
And do you really need to set up every single controller for each bus,
given that the mapping is pretty much guaranteed to be similar for them?
Making a guess bus button doesn't seem too difficult, where if you
have one correctly set up controller on the bus, it can guess from
a neighboring bus (assuming a static offset). But what if there's
conflicting information? OK; then you should disable the button.
So now the enable/disable status of that button depends on which cell
in your grid has the focus; how do you get at those events? (Install an event
filter, or subclass the spinner.) And so on, and so on, and so on.
You could argue that most of these questions go away with experience;
if you're an expert in a given API, you can answer most of these questions
in a minute or two even if you haven't heard the exact question before.
But you can't expect even experienced developers to be an expert in all
possible libraries; if you know everything there is to know about Qt,
ALSA, x264, ffmpeg, OpenGL, VA-API, libusb, microhttpd and Lua
(in addition to C++11, of course), I'm sure you'd be a great fit for
Nageru, but I'd wager that pretty few developers fit that bill.
I've written C++ for almost 20 years now (almost ten of them professionally),
and that experience certainly helps boosting productivity, but I can't
say I expect a 10x reduction in my own development time at any point.
You could also argue, of course, that spending so much time on the editor
is wasted, since most users will only ever see it once. But here's the
point; it's not actually a lot of time. The only reason why it seems
like so much is that I bothered to write two paragraphs about it;
it's not a particular pain point, it just adds to the total. Also,
the first impression matters a lot if the user can't get the editor
to work, they also can't get the MIDI controller to work, and is likely
to just go do something else.
A common misconception is that just switching languages or using libraries
will help you a lot. (Witness the never-ending stream of software that
advertises written in Foo or uses Bar as if it were a feature.)
For the former, note that nothing I've said so far is specific to my choice
of language (C++), and I've certainly avoided a bunch of battles by making
that specific choice over, say, Python. For the latter, note that most of these problems are actually related
to library use libraries are great, and they solve a bunch of problems
I'm really glad I didn't have to worry about (how should each button look?),
but they still give their own interaction problems. And even when you're a
master of your chosen programming environment, things still take time,
because you have all those decisions to make on top of your libraries.
Of course, there are cases where libraries really solve your entire problem
and your code gets reduced to 100 trivial lines, but that's really only when
you're solving a problem that's been solved a million times before. Congrats
on making that blog in Rails; I'm sure you're advancing the world. (To make
things worse, usually this breaks down when you want to stray ever so
slightly from what was intended by the library or framework author. What
seems like a perfect match can suddenly become a development trap where you
spend more of your time trying to become an expert in working around the
given library than actually doing any development.)
The entire thing reminds me of the famous essay
No Silver Bullet by Fred
Brooks, but perhaps even more so, this quote from
John Carmack's .plan has
struck with me (incidentally about mobile game development in 2006,
but the basic story still rings true):
To some degree this is already the case on high end BREW phones today. I have a pretty clear idea what a maxed out software renderer would look like for that class of phones, and it wouldn't be the PlayStation-esq 3D graphics that seems to be the standard direction. When I was doing the graphics engine upgrades for BREW, I started along those lines, but after putting in a couple days at it I realized that I just couldn't afford to spend the time to finish the work. "A clear vision" doesn't mean I can necessarily implement it in a very small integral number of days.In a sense, programming is all about what your program should do in the first place. The how question is just the what , moved down the chain of abstractions until it ends up where a computer can understand it, and at that point, the three words multichannel audio support have become those 9,000 lines that describe in perfect detail what's going on.
My plan for this week s lecture of the CIS 194 Haskell course at the University of Pennsylvania is to dwell a bit on the concept of Functor, Applicative and Monad, and to highlight the value of the Applicative abstraction.
I quite like the example that I came up with, so I want to share it here. In the interest of long-term archival and stand-alone presentation, I include all the material in this post.1
import Data.Char
import Data.Maybe
import Data.List
import System.Environment
import System.IO
import System.Exit
newtype Parser a = P (String -> Maybe (a, String))
runParser :: Parser t -> String -> Maybe (t, String)
runParser (P p) = p
parse :: Parser a -> String -> Maybe a
parse p input = case runParser p input of
Just (result, "") -> Just result
_ -> Nothing -- handles both no result and leftover input
noParserP :: Parser a
noParserP = P (\_ -> Nothing)
pureParserP :: a -> Parser a
pureParserP x = P (\input -> Just (x,input))
instance Functor Parser where
fmap f p = P $ \input -> do
(x, rest) <- runParser p input
return (f x, rest)
instance Applicative Parser where
pure = pureParserP
p1 <*> p2 = P $ \input -> do
(f, rest1) <- runParser p1 input
(x, rest2) <- runParser p2 rest1
return (f x, rest2)
instance Monad Parser where
return = pure
p1 >>= k = P $ \input -> do
(x, rest1) <- runParser p1 input
runParser (k x) rest1
anyCharP :: Parser Char
anyCharP = P $ \input -> case input of
(c:rest) -> Just (c, rest)
[] -> Nothing
charP :: Char -> Parser ()
charP c = do
c' <- anyCharP
if c == c' then return ()
else noParserP
anyCharButP :: Char -> Parser Char
anyCharButP c = do
c' <- anyCharP
if c /= c' then return c'
else noParserP
letterOrDigitP :: Parser Char
letterOrDigitP = do
c <- anyCharP
if isAlphaNum c then return c else noParserP
orElseP :: Parser a -> Parser a -> Parser a
orElseP p1 p2 = P $ \input -> case runParser p1 input of
Just r -> Just r
Nothing -> runParser p2 input
manyP :: Parser a -> Parser [a]
manyP p = (pure (:) <*> p <*> manyP p) orElseP pure []
many1P :: Parser a -> Parser [a]
many1P p = pure (:) <*> p <*> manyP p
sepByP :: Parser a -> Parser () -> Parser [a]
sepByP p1 p2 = (pure (:) <*> p1 <*> (manyP (p2 *> p1))) orElseP pure []
A parser using this library for, for example, CSV files could take this form:
parseCSVP :: Parser [[String]]
parseCSVP = manyP parseLine
where
parseLine = parseCell sepByP charP ',' <* charP '\n'
parseCell = do
charP '"'
content <- manyP (anyCharButP '"')
charP '"'
return content
cell = '"', not-quote , '"';
line = (cell, ',', cell ''), newline;
csv = line ;
It is straightforward to create a Haskell data type to represent an EBNF syntax description. Here is a simple EBNF library (data type and pretty-printer) for your convenience:
data RHS
= Terminal String
NonTerminal String
Choice RHS RHS
Sequence RHS RHS
Optional RHS
Repetition RHS
deriving (Show, Eq)
ppRHS :: RHS -> String
ppRHS = go 0
where
go _ (Terminal s) = surround "'" "'" $ concatMap quote s
go _ (NonTerminal s) = s
go a (Choice x1 x2) = p a 1 $ go 1 x1 ++ " " ++ go 1 x2
go a (Sequence x1 x2) = p a 2 $ go 2 x1 ++ ", " ++ go 2 x2
go _ (Optional x) = surround "[" "]" $ go 0 x
go _ (Repetition x) = surround " " " " $ go 0 x
surround c1 c2 x = c1 ++ x ++ c2
p a n a > n = surround "(" ")"
otherwise = id
quote '\'' = "\\'"
quote '\\' = "\\\\"
quote c = [c]
type Production = (String, RHS)
type BNF = [Production]
ppBNF :: BNF -> String
ppBNF = unlines . map (\(i,rhs) -> i ++ " = " ++ ppRHS rhs ++ ";")
RHS type directly, but we can do something more nifty: We create a data type that keeps track, via a phantom type parameter, of what Haskell type the given EBNF syntax is the specification:
newtype Grammar a = G RHS
ppGrammar :: Grammar a -> String
ppGrammar (G rhs) = ppRHS rhs
So a value of type Grammar t is a description of the textual representation of the Haskell type t.
Here is one simple example:
anyCharG :: Grammar Char
anyCharG = G (NonTerminal "char")
Here is another one. This one does not describe any interesting Haskell type, but is useful when spelling out the special characters in the syntax described by the grammar:
charG :: Char -> Grammar ()
charG c = G (Terminal [c])
A combinator that creates new grammar from two existing grammars:
orElseG :: Grammar a -> Grammar a -> Grammar a
orElseG (G rhs1) (G rhs2) = G (Choice rhs1 rhs2)
We want the convenience of our well-known type classes in order to combine these values some more:
instance Functor Grammar where
fmap _ (G rhs) = G rhs
instance Applicative Grammar where
pure x = G (Terminal "")
(G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2)
Note how the Functor instance does not actually use the function. How should it? There are no values inside a Grammar!
We cannot define a Monad instance for Grammar: We would start with (G rhs1) >>= k = , but there is simply no way of getting a value of type a that we can feed to k. So we will do without a Monad instance. This is interesting, and we will come back to that later.
Like with the parser, we can now begin to build on the primitive example to build more complicated combinators:
manyG :: Grammar a -> Grammar [a]
manyG p = (pure (:) <*> p <*> manyG p) orElseG pure []
many1G :: Grammar a -> Grammar [a]
many1G p = pure (:) <*> p <*> manyG p
sepByG :: Grammar a -> Grammar () -> Grammar [a]
sepByG p1 p2 = ((:) <$> p1 <*> (manyG (p2 *> p1))) orElseG pure []
Let us run a small example:
dottedWordsG :: Grammar [String]
dottedWordsG = many1G (manyG anyCharG <* charG '.')
*Main> putStrLn $ ppGrammar dottedWordsG
'', ('', char, ('', char, ('', char, ('', char, ('', char, ('',
Oh my, that is not good. Looks like the recursion in manyG does not work well, so we need to avoid that. But anyways we want to be explicit in the EBNF grammars about where something can be repeated, so let us just make many a primitive:
manyG :: Grammar a -> Grammar [a]
manyG (G rhs) = G (Repetition rhs)
With this definition, we already get a simple grammar for dottedWordsG:
*Main> putStrLn $ ppGrammar dottedWordsG
'', char , '.', char , '.'
This already looks like a proper EBNF grammar. One thing that is not nice about it is that there is an empty string ('') in a sequence ( , ). We do not want that.
Why is it there in the first place? Because our Applicative instance is not lawful! Remember that pure id <*> g == g should hold. One way to achieve that is to improve the Applicative instance to optimize this case away:
instance Applicative Grammar where
pure x = G (Terminal "")
G (Terminal "") <*> G rhs2 = G rhs2
G rhs1 <*> G (Terminal "") = G rhs1
(G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2)
Now we get what we want:
*Main> putStrLn $ ppGrammar dottedWordsG
char , '.', char , '.'
Remember our parser for CSV files above? Let me repeat it here, this time using only Applicative combinators, i.e. avoiding (>>=), (>>), return and do-notation:
parseCSVP :: Parser [[String]]
parseCSVP = manyP parseLine
where
parseLine = parseCell sepByP charG ',' <* charP '\n'
parseCell = charP '"' *> manyP (anyCharButP '"') <* charP '"'
And now we try to rewrite the code to produce Grammar instead of Parser. This is straightforward with the exception of anyCharButP. The parser code for that inherently monadic, and we just do not have a monad instance. So we work around the issue by making that a primitive grammar, i.e. introducing a non-terminal in the EBNF without a production rule pretty much like we did for anyCharG:
primitiveG :: String -> Grammar a
primitiveG s = G (NonTerminal s)
parseCSVG :: Grammar [[String]]
parseCSVG = manyG parseLine
where
parseLine = parseCell sepByG charG ',' <* charG '\n'
parseCell = charG '"' *> manyG (primitiveG "not-quote") <* charG '"'
Of course the names parse are not quite right any more, but let us just leave that for now.
Here is the result:
*Main> putStrLn $ ppGrammar parseCSVG
('"', not-quote , '"', ',', '"', not-quote , '"' ''), '
'
The line break is weird. We do not really want newlines in the grammar. So let us make that primitive as well, and replace charG '\n' with newlineG:
newlineG :: Grammar ()
newlineG = primitiveG "newline"
Now we get
*Main> putStrLn $ ppGrammar parseCSVG
('"', not-quote , '"', ',', '"', not-quote , '"' ''), newline
which is nice and correct, but still not quite the easily readable EBNF that we saw further up.
newtype Grammar a = G (BNF, RHS)
runGrammer :: String -> Grammar a -> BNF
runGrammer main (G (prods, rhs)) = prods ++ [(main, rhs)]
ppGrammar :: String -> Grammar a -> String
ppGrammar main g = ppBNF $ runGrammer main g
Now we have to adjust all our primitive combinators (but not the derived ones!):
charG :: Char -> Grammar ()
charG c = G ([], Terminal [c])
anyCharG :: Grammar Char
anyCharG = G ([], NonTerminal "char")
manyG :: Grammar a -> Grammar [a]
manyG (G (prods, rhs)) = G (prods, Repetition rhs)
mergeProds :: [Production] -> [Production] -> [Production]
mergeProds prods1 prods2 = nub $ prods1 ++ prods2
orElseG :: Grammar a -> Grammar a -> Grammar a
orElseG (G (prods1, rhs1)) (G (prods2, rhs2))
= G (mergeProds prods1 prods2, Choice rhs1 rhs2)
instance Functor Grammar where
fmap _ (G bnf) = G bnf
instance Applicative Grammar where
pure x = G ([], Terminal "")
G (prods1, Terminal "") <*> G (prods2, rhs2)
= G (mergeProds prods1 prods2, rhs2)
G (prods1, rhs1) <*> G (prods2, Terminal "")
= G (mergeProds prods1 prods2, rhs1)
G (prods1, rhs1) <*> G (prods2, rhs2)
= G (mergeProds prods1 prods2, Sequence rhs1 rhs2)
primitiveG :: String -> Grammar a
primitiveG s = G (NonTerminal s)
The use of nub when combining productions removes duplicates that might be used in different parts of the grammar. Not efficient, but good enough for now.
Did we gain anything? Not yet:
*Main> putStr $ ppGrammar "csv" (parseCSVG)
csv = ('"', not-quote , '"', ',', '"', not-quote , '"' ''), newline ;
But we can now introduce a function that lets us tell the system where to give names to a piece of grammar:
nonTerminal :: String -> Grammar a -> Grammar a
nonTerminal name (G (prods, rhs))
= G (prods ++ [(name, rhs)], NonTerminal name)
Ample use of this in parseCSVG yields the desired result:
parseCSVG :: Grammar [[String]]
parseCSVG = manyG parseLine
where
parseLine = nonTerminal "line" $
parseCell sepByG charG ',' <* newline
parseCell = nonTerminal "cell" $
charG '"' *> manyG (primitiveG "not-quote") <* charG '"
*Main> putStr $ ppGrammar "csv" (parseCSVG)
cell = '"', not-quote , '"';
line = (cell, ',', cell ''), newline;
csv = line ;
This is great!
parseCSVG and parseCSVP are! Would it not be great if we could implement that functionality only once, and get both a parser and a grammar description out of it? This way, the two would never be out of sync!
And surely this must be possible. The tool to reach for is of course to define a type class that abstracts over the parts where Parser and Grammer differ. So we have to identify all functions that are primitive in one of the two worlds, and turn them into type class methods. This includes char and orElse. It includes many, too: Although manyP is not primitive, manyG is. It also includes nonTerminal, which does not exist in the world of parsers (yet), but we need it for the grammars.
The primitiveG function is tricky. We use it in grammars when the code that we might use while parsing is not expressible as a grammar. So the solution is to let it take two arguments: A String, when used as a descriptive non-terminal in a grammar, and a Parser a, used in the parsing code.
Finally, the type classes that we except, Applicative (and thus Functor), are added as constraints on our type class:
class Applicative f => Descr f where
char :: Char -> f ()
many :: f a -> f [a]
orElse :: f a -> f a -> f a
primitive :: String -> Parser a -> f a
nonTerminal :: String -> f a -> f a
The instances are easily written:
instance Descr Parser where
char = charP
many = manyP
orElse = orElseP
primitive _ p = p
nonTerminal _ p = p
instance Descr Grammar where
char = charG
many = manyG
orElse = orElseG
primitive s _ = primitiveG s
nonTerminal s g = nonTerminal s g
And we can now take the derived definitions, of which so far we had two copies, and define them once and for all:
many1 :: Descr f => f a -> f [a]
many1 p = pure (:) <*> p <*> many p
anyChar :: Descr f => f Char
anyChar = primitive "char" anyCharP
dottedWords :: Descr f => f [String]
dottedWords = many1 (many anyChar <* char '.')
sepBy :: Descr f => f a -> f () -> f [a]
sepBy p1 p2 = ((:) <$> p1 <*> (many (p2 *> p1))) orElse pure []
newline :: Descr f => f ()
newline = primitive "newline" (charP '\n')
And thus we now have our CSV parser/grammar generator:
parseCSV :: Descr f => f [[String]]
parseCSV = many parseLine
where
parseLine = nonTerminal "line" $
parseCell sepBy char ',' <* newline
parseCell = nonTerminal "cell" $
char '"' *> many (primitive "not-quote" (anyCharButP '"')) <* char '"'
We can now use this definition both to parse and to generate grammars:
*Main> putStr $ ppGrammar2 "csv" (parseCSV)
cell = '"', not-quote , '"';
line = (cell, ',', cell ''), newline;
csv = line ;
*Main> parse parseCSV "\"ab\",\"cd\"\n\"\",\"de\"\n\n"
Just [["ab","cd"],["","de"],[]]
parseINIP :: Parser INIFile
parseINIP = many1P parseSection
where
parseSection =
(,) <$ charP '['
<*> parseIdent
<* charP ']'
<* charP '\n'
<*> (catMaybes <$> manyP parseLine)
parseIdent = many1P letterOrDigitP
parseLine = parseDecl orElseP parseComment orElseP parseEmpty
parseDecl = Just <$> (
(,) <*> parseIdent
<* manyP (charP ' ')
<* charP '='
<* manyP (charP ' ')
<*> many1P (anyCharButP '\n')
<* charP '\n')
parseComment =
Nothing <$ charP '#'
<* many1P (anyCharButP '\n')
<* charP '\n'
parseEmpty = Nothing <$ charP '\n'
Transforming that to a generic description is quite straightforward. We use primitive again to wrap letterOrDigitP:
descrINI :: Descr f => f INIFile
descrINI = many1 parseSection
where
parseSection =
(,) <* char '['
<*> parseIdent
<* char ']'
<* newline
<*> (catMaybes <$> many parseLine)
parseIdent = many1 (primitive "alphanum" letterOrDigitP)
parseLine = parseDecl orElse parseComment orElse parseEmpty
parseDecl = Just <$> (
(,) <*> parseIdent
<* many (char ' ')
<* char '='
<* many (char ' ')
<*> many1 (primitive "non-newline" (anyCharButP '\n'))
<* newline)
parseComment =
Nothing <$ char '#'
<* many1 (primitive "non-newline" (anyCharButP '\n'))
<* newline
parseEmpty = Nothing <$ newline
This yields this not very helpful grammar (abbreviated here):
*Main> putStr $ ppGrammar2 "ini" descrINI
ini = '[', alphanum, alphanum , ']', newline, alphanum, alphanum , ' '
But with a few uses of nonTerminal, we get something really nice:
descrINI :: Descr f => f INIFile
descrINI = many1 parseSection
where
parseSection = nonTerminal "section" $
(,) <$ char '['
<*> parseIdent
<* char ']'
<* newline
<*> (catMaybes <$> many parseLine)
parseIdent = nonTerminal "identifier" $
many1 (primitive "alphanum" letterOrDigitP)
parseLine = nonTerminal "line" $
parseDecl orElse parseComment orElse parseEmpty
parseDecl = nonTerminal "declaration" $ Just <$> (
(,) <$> parseIdent
<* spaces
<* char '='
<* spaces
<*> remainder)
parseComment = nonTerminal "comment" $
Nothing <$ char '#' <* remainder
remainder = nonTerminal "line-remainder" $
many1 (primitive "non-newline" (anyCharButP '\n')) <* newline
parseEmpty = Nothing <$ newline
spaces = nonTerminal "spaces" $ many (char ' ')
*Main> putStr $ ppGrammar "ini" descrINI
identifier = alphanum, alphanum ;
spaces = ' ' ;
line-remainder = non-newline, non-newline , newline;
declaration = identifier, spaces, '=', spaces, line-remainder;
comment = '#', line-remainder;
line = declaration comment newline;
section = '[', identifier, ']', newline, line ;
ini = section, section ;
const = digit, digit ;
spaces = ' ' newline ;
atom = const '(', spaces, expr, spaces, ')', spaces;
mult = atom, spaces, '*', spaces, atom , spaces;
plus = mult, spaces, '+', spaces, mult , spaces;
expr = plus;
The production of expr is recursive (via plus, mult, atom). We have seen above that simply defining a Grammar a recursively does not go well.
One solution is to add a new combinator for explicit recursion, which replaces nonTerminal in the method:
class Applicative f => Descr f where
recNonTerminal :: String -> (f a -> f a) -> f a
instance Descr Parser where
recNonTerminal _ p = let r = p r in r
instance Descr Grammar where
recNonTerminal = recNonTerminalG
recNonTerminalG :: String -> (Grammar a -> Grammar a) -> Grammar a
recNonTerminalG name f =
let G (prods, rhs) = f (G ([], NonTerminal name))
in G (prods ++ [(name, rhs)], NonTerminal name)
nonTerminal :: Descr f => String -> f a -> f a
nonTerminal name p = recNonTerminal name (const p)
runGrammer :: String -> Grammar a -> BNF
runGrammer main (G (prods, NonTerminal nt)) main == nt = prods
runGrammer main (G (prods, rhs)) = prods ++ [(main, rhs)]
The change in runGrammer avoids adding a pointless expr = expr production to the output.
This lets us define a parser/grammar-generator for the arithmetic expressions given above:
data Expr = Plus Expr Expr Mult Expr Expr Const Integer
deriving Show
mkPlus :: Expr -> [Expr] -> Expr
mkPlus = foldl Plus
mkMult :: Expr -> [Expr] -> Expr
mkMult = foldl Mult
parseExpr :: Descr f => f Expr
parseExpr = recNonTerminal "expr" $ \ exp ->
ePlus exp
ePlus :: Descr f => f Expr -> f Expr
ePlus exp = nonTerminal "plus" $
mkPlus <$> eMult exp
<*> many (spaces *> char '+' *> spaces *> eMult exp)
<* spaces
eMult :: Descr f => f Expr -> f Expr
eMult exp = nonTerminal "mult" $
mkPlus <$> eAtom exp
<*> many (spaces *> char '*' *> spaces *> eAtom exp)
<* spaces
eAtom :: Descr f => f Expr -> f Expr
eAtom exp = nonTerminal "atom" $
aConst orElse eParens exp
aConst :: Descr f => f Expr
aConst = nonTerminal "const" $ Const . read <$> many1 digit
eParens :: Descr f => f a -> f a
eParens inner =
id <$ char '('
<* spaces
<*> inner
<* spaces
<* char ')'
<* spaces
And indeed, this works:
*Main> putStr $ ppGrammar "expr" parseExpr
const = digit, digit ;
spaces = ' ' newline ;
atom = const '(', spaces, expr, spaces, ')', spaces;
mult = atom, spaces, '*', spaces, atom , spaces;
plus = mult, spaces, '+', spaces, mult , spaces;
expr = plus;
recNonTerminal and explicitly passing around the recursive call (i.e. the exp in the example). To implement that we have to adjust our Grammar type as follows:
newtype Grammar a = G ([String] -> (BNF, RHS))
The idea is that the list of strings is those non-terminals that we are currently defining. So in nonTerminal, we check if the non-terminal to be introduced is currently in the process of being defined, and then simply ignore the body. This way, the recursion is stopped automatically:
nonTerminalG :: String -> (Grammar a) -> Grammar a
nonTerminalG name (G g) = G $ \seen ->
if name elem seen
then ([], NonTerminal name)
else let (prods, rhs) = g (name : seen)
in (prods ++ [(name, rhs)], NonTerminal name)
After adjusting the other primitives of Grammar (including the Functor and Applicative instances, wich now again have nonTerminal) to type-check again, we observe that this parser/grammar generator for expressions, with genuine recursion, works now:
parseExp :: Descr f => f Expr
parseExp = nonTerminal "expr" $
ePlus
ePlus :: Descr f => f Expr
ePlus = nonTerminal "plus" $
mkPlus <$> eMult
<*> many (spaces *> char '+' *> spaces *> eMult)
<* spaces
eMult :: Descr f => f Expr
eMult = nonTerminal "mult" $
mkPlus <$> eAtom
<*> many (spaces *> char '*' *> spaces *> eAtom)
<* spaces
eAtom :: Descr f => f Expr
eAtom = nonTerminal "atom" $
aConst orElse eParens parseExp
Note that the recursion is only going to work if there is at least one call to nonTerminal somewhere around the recursive calls. We still cannot implement many as naively as above.
identifier = letter, letter digit '-' ;
spaces = ' ' newline ;
quoted-char = non-quote-or-backslash '\\', '\\' '\\', '\'';
terminal = '\'', quoted-char , '\'', spaces;
non-terminal = identifier, spaces;
option = '[', spaces, rhs, spaces, ']', spaces;
repetition = ' ', spaces, rhs, spaces, ' ', spaces;
group = '(', spaces, rhs, spaces, ')', spaces;
atom = terminal non-terminal option repetition group;
sequence = atom, spaces, ',', spaces, atom , spaces;
choice = sequence, spaces, ' ', spaces, sequence , spaces;
rhs = choice;
production = identifier, spaces, '=', spaces, rhs, ';', spaces;
bnf = production, production ;
This grammar is set up so that the precedence of , and is correctly implemented: a , b c will parse as (a, b) c.
In this syntax for BNF, terminal characters are quoted, i.e. inside ' ', a ' is replaced by \' and a \ is replaced by \\ this is done by the function quote in ppRHS.
If you do this, you should able to round-trip with the pretty-printer, i.e. parse back what it wrote:
*Main> let bnf1 = runGrammer "expr" parseExpr
*Main> let bnf2 = runGrammer "expr" parseBNF
*Main> let f = Data.Maybe.fromJust . parse parseBNF. ppBNF
*Main> f bnf1 == bnf1
True
*Main> f bnf2 == bnf2
True
The last line is quite meta: We are using parseBNF as a parser on the pretty-printed grammar produced from interpreting parseBNF as a grammar.
Applicative, and not Monad. Applicative is less powerful, so by giving less power to the user of our Descr interface, the other side, i.e. the implementation, can be more powerful.
The reason why Applicative is ok, but Monad is not, is that in Applicative, the results do not affect the shape of the computation, whereas in Monad, the whole point of the bind operator (>>=) is that the result of the computation is used to decide the next computation. And while this is perfectly fine for a parser, it just makes no sense for a grammar generator, where there simply are no values around!
We have also seen that a phantom type, namely the parameter of Grammar, can be useful, as it lets the type system make sure we do not write nonsense. For example, the type of orElseG ensures that both grammars that are combined here indeed describe something of the same type.
Applicative yesterday. <*> and <* the > point out where the arguments are that are being passed to the function on the left.
After the Debian Desktop Team made the
call for proposing themes,
a total of twelve choices
have been submitted, and any Debian contributor has received
the opportunity to vote on them in a survey.
We received 3,479 responses ranking the different choices,
and softWaves has been the winner among them.
We'd like to thank all the designers that have participated
providing nice wallpapers and artwork for Debian 9,
and encourage everybody interested in this area of Debian,
to join the Design Team.
It is being considered
to package all of them so they are easily available in Debian.
If you want to help in this effort, or package any other artwork
(for example, particularly designed to be accessibility-friendly),
please contact the Debian Desktop Team, but hurry up,
because the freeze for new packages in the next release of Debian
starts on January 5th, 2017.
This is the second time that Debian ships a theme by Juliette Belin,
who also created the theme "Lines"
that enhances our actual stable release, Debian 8.
Congratulations, Juliette, and thank you very much for your continued commitment to Debian!
| Publisher: | Basic Books |
| Copyright: | 2013 |
| ISBN: | 0-465-05065-4 |
| Format: | Trade paperback |
| Pages: | 298 |
The Referer header has
been a part of the web for a long time. Websites rely on it for a few
different purposes (e.g. analytics, ads, CSRF protection) but it can be
quite problematic from a privacy perspective.
Thankfully, there are now tools in Firefox to help users and developers
mitigate some of these problems.
Referer header to all outgoing HTTP
requests, revealing to the server on the other end the URL of the page you
were on when you placed the request. For example, it tells the server where
you were when you followed a link to that site, or what page you
were on when you requested an image or a script. There are, however, a few
limitations to this simplified explanation.
First of all, by default, browsers won't send a referrer if you place a
request from an HTTPS page to an HTTP page. This would reveal potentially
confidential information (such as the URL path and query string which could
contain session tokens or other secret identifiers) from a secure page over
an insecure HTTP channel. Firefox will however include a Referer header in
HTTPS to HTTPS transitions unless network.http.sendSecureXSiteReferrer
(removed in Firefox 52) is set to false in about:config.
Secondly, using the new
Referrer Policy specification web
developers can override the default behaviour for their pages, including on
a per-element basis. This can be used both to increase or reduce the amount
of information present in the referrer.
Referer header has been around for so long, a number of
techniques rely on it.
Armed with the Referer information, analytics tools can figure out:
Referer is useful is as a mitigation against
cross-site request forgeries.
In that case, a website receiving a form submission can reject that form
submission if the request originated from a different website.
It's worth pointing out that this CSRF mitigation might be better implemented
via a separate header that could
be restricted to particularly dangerous requests (i.e. POST and DELETE
requests) and only include the information required for that security check
(i.e. the origin).
privacy.trackingprotection.enabled to true in about:config,
which will prevent all network connections to known trackers, users can
control when the Referer header is sent by setting
network.http.sendRefererHeader to:
0 to never send the header1 to send the header only when clicking on links and similar elements2 (default) to send the header on all requests (e.g. images, links, etc.)network.http.referer.trimmingPolicy
to:
0 (default) to send the full URL1 to send the URL without its query string2 to only send the scheme, host and portnetwork.http.referer.XOriginTrimmingPolicy option (added in
Firefox 52) to only restrict the contents of referrers attached to
cross-origin requests.
Site owners can opt to share less information with other sites, but they
can't share any more than what the user trimming policies allow.
Another approach is to disable the Referer when doing cross-origin
requests (from one site to another). The
network.http.referer.XOriginPolicy preference can be set to:
0 (default) to send the referrer in all cases1 to send a referrer only when the base domains are the same2 to send a referrer only when the full hostnames matchnetwork.http.sendRefererHeader = 0,
you will most likely run into problems on a number of sites, for
example:
network.http.referer.spoofSource to true, an advanced setting
which always sends the destination URL as the referrer, thereby not leaking
anything about the original page.
Unfortunately, the last two are examples of the kind of breakage that can
only be fixed through a whitelist (an approach supported by the smart
referer add-on) or
by temporarily using a different browser
profile.
network.http.referer.XOriginPolicy = 2
or to sites which belong to the same organization (i.e. same
ETLD/public suffix)
using:
network.http.referer.XOriginPolicy = 1
This prevent leaks to third-parties while giving websites all of the
information that they can already see in their own server logs.
On the other hand, if you prefer a weaker but more compatible solution, you
can trim cross-origin referrers down to just the scheme, hostname and port:
network.http.referer.XOriginTrimmingPolicy = 2
I have not yet found user-visible breakage using this last configuration.
Let me know if you find any!
Next.