We interrupt the irregularly scheduled philosophical posts for some
programming memes:
Over the last few days, the Internet has divided itself over what the
value of the expression 8÷2(2+2) should be. Some say it should be
evaluated as (8÷2)×(2+2) = 16. Some say it should be evaluated as
8÷(2×(2+2)) = 1.
At the risk of belaboring the obvious, the core dispute here is not
really mathematical. There is not some sequence of mathematical
operations that produces some number, where mathematicians disagree
about what number it produces. Instead, this is a dispute about
mathematical notation: what sequence of mathematical operations the
expression corresponds to the way it’s written. Specifically, it is a
dispute about whether multiplication written as juxtaposition (how “2”
is written right next to “(2+2)”) has strictly higher precedence than
division. It is closer to a linguistic or typographical dispute than a
purely mathematical one, and the correct answer to the dispute is that
whoever wrote the expression that way should learn to write math
better.
This debate is not even new. The internet had fun arguing over 48÷2(9+3) and 6÷2(1+2),
which are functionally identical ambiguous expressions, eight years ago.
I don’t know why the debate is resurging now and why we still haven’t
gotten tired of it.
But life is short, so since we’re here anyway, let’s make some
additional memes.
Asking the computer
Some of my coworkers had the idea to ask some programming languages
what the answer was. The results were underwhelming.
$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 8/2(2+2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable
--... ---.. ....- ..... ..--- ----- ....- ....- ...-- -.... ...-- -.... ...-- . ....- ....- ..--- ----- ....- ..... ...-- ----. ...-- -.... ....- ...-- ...-- -.... ..... -.... ....- ....- ..--- ----- ...-- ..-. ....- ----- ..--- ----- ...-- ..--- ...-- ..-. ....- ..... ...-- .- ...-- ..... ....- ----- ....- ..... ...-- -.... ..--- ----- ...-- --... ....- ----- ....- ...-- ..--- ----- ...-- ..--- ...-- ..-. ...-- ---.. ....- ....- ....- ..... ..--- ----- ...-- -.. ...-- .- ...-- -.-. ...-- -.... ..--- ----- ...-- --... ...-- .- ...-- ..-. ...-- ..... ...-- .- ...-- ..-. ...-- ---.. ..--- ----- ....- ....- ....- ----- ...-- . ...-- -.... ....- ..... ...-- ----. ...-- .- ...-- ..-. ...-- ---.. ..--- ----- ...-- ....- ....- ----- ....- ----- ...-- -.. ..--- ----- ...-- ..--- ...-- ..-. ...-- ..... ..--- ----- ...-- ..... ....- ----- ....- ---.. ...-- ..-. ..... -.-. ....- ..... ....- ----- ..... -.-. ...-- -.... ...-- ..--- ....- ...-- ....- ..... ...-- ----. ..... -... ..--- ----- ...-- ..--- ...-- ..-. ...-- ..... ..--- ----- ...-- ..... ....- ----- ...-- .- ...-- ..-. ...-- ---.. ..--- ----- ...-- .- ....- ..... ..... -..
..--- ..... ....- ----- ...-- ..... ...-- ..--- ....- .- ..--- ----- --... ---.. ..--- ----- ...-- ..... ...-- .- ...-- ..... ..--- ----- ...-- ..--- ..--- ----- ....- ..... ...-- ----. ...-- .- ...-- ..-. ...-- ---.. ..--- ----- --... ---.. ..--- ----- ....- ---.. ...-- ..--- ...-- ..-. ....- ..... ...-- -.... ...-- ..... ..--- ----- ....- ..... ....- ----- ..--- ----- ...-- ..... ....- ----- ..--- ----- ...-- --... ....- ----- ....- ...-- ..--- ----- ...-- ..--- ..--- ----- ...-- -.. ....- ----- ...-- ..-. ...-- ---.. ..--- ----- ....- ..... ...-- .- ...-- . ...-- -.... -.... ----. ..--- ----- --... ---.. ..--- ----- ...-- ....- ....- ----- ...-- . ....- .---- ...-- .- ...-- -.. ...-- -.... ...-- ..... ..--- -----
...-- ...-- ...-- ....- ....- ----- ...-- ..... ...-- -.... ....- ----.
..--- ----- ...-- --... ....- ...-- ....- ----- ...-- . ..--- ----- --... --... ...-- ..--- ....- ....- ...-- -.-. ...-- -.... ...-- -.. ...-- -.. ..--- ----- ....- ..... ....- ----- ..--- ----- --... ----. ...-- ..--- ....- --... ...-- ..--- ..--- ....- ...-- ....- ....- ...-- ...-- .- ....- .---- ....- ..... ..--- ----- ....- ....- ....- ----- ..--- ----- ...-- .- ....- ..... ..--- ----- ...-- ....- ....- ----- ....- -.... ...-- -.. ...-- ..... ..--- ----- ....- ...-- ....- -.... ...-- ..-. ..--- ----- ...-- .- ...-- ..-. ..--- ----- ...-- ..--- ...-- ..-. ....- .- ..--- ----- ...-- . ....- ----- ...-- ..... ...-- -.... ....- ...-- ...-- ..-. ..--- ----- ...-- ...-- ....- ...-- ....- ----- ....- ---.. ....- ....- ...-- -.... ....- ...-- ..... -.. ..--- -----
..--- .- ....- ----- ....- -.... ..--- ----- ...-- ....- ...-- ..--- ...-- ..-. ..--- ----- ....- ..... ....- ...-- ....- .- ..--- ----- ...-- .- ....- ..... ..--- ----- ...-- ----. ...-- -.... ....- ...-- ...-- -.... ..... -----
tl;dr: anybody want to add me on Line or tell/remind me about
other phone chat apps? betaveros as always.
Wow, talk about uninspired post titles.
I got a new phone today. Or, well, it’s second-hand, actually. I try
to make electronics last a long time, but I think this was justified
given the state of my last phone’s screen:
Besides, I’m going off to college and all. Anyway, the phone is
pretty cool. It’s a slick shade of red, it came with a cover and
everything, and it has one of those fancy 3x3-grid locks. How secure are
those again?
Well, we could just
find
the answer on StackOverflow, but that’s boring.
First Google Code Jam!
The format of this competition, allowing us to run programs on our
own machines, brought up a very interesting issue for me: what
programming language should I be using? (I had had similar
considerations for IPSC 2013, but GCJ’s problems are closer to the
traditional ACM-ICPC style.)
The obvious choice is C++, the language I use for roughly every other
competition, but its safety (or lack thereof) is not very appealing. I
need speed, but not that much speed. Unfortunately I still
haven’t gotten around to learning any other friendlier mid-level
languages (on the list: D, Go, or Rust), so I have no close substitutes
for C++ right now.
Python is certainly available for a reliable arbitrary-length integer
type, if nothing else.
As for non-candidates, Java has BigInteger and memory
safety, but all in all I decided the benefits are too minor and it’s too
ugly without operator overloading. Scala is probably way too slow. So I
don’t expect to be writing either language.
The only difficult choice I have to make is, of course, Haskell —
which can be quite fast, even while it’s ridiculously type-safe and
expressive and referentially transparent and easy to reason about, once
you’ve:
- figured out how to do the problem
- scrapped step 1 and actually figured out how to do the
problem functionally
- gotten the thing to compile
Even if I can handle step 1, step 2 is by no means a simple task, as
my struggle to implement a mere
Sieve of Eratosthenes
efficiently shows. That is fun, but not at all intuitive; I am doubtful
I can do this under contest conditions. It is extremely difficult to
transfer my skills in learning how to implement, say, a segment tree or
treap into this language.
But! Google links to the
programming language
breakdown for 2010 Qualification Round as an example, and much to my
surprise, Haskell ranks somewhere between sixth and tenth place in
popularity (depending on what you sort by), so there are functional
superprogrammers who can presumably do something like this.
As it happens, I ended up implementing all four solutions to the
qualification rounds in Haskell, because of the relaxed time limit and
lack of any involved algorithms and data structures. I think it was
worth it.
“I have been told that any encryption becomes safer if the underlying
algorithm is maximally obscured, what is most conveniently done by
coding it in Haskell.” – rankk
Functional programming is terribly addicting! Partly I think the
completely different way of thinking makes it feel like learning
programming, and falling in love with it, all over again. Partly there’s
this evil sense of satisfaction from using $s (and later
<$>s and =<<s and
&&&s) to improve readability for initiated
Haskellers and worsen it for everybody else. Partly it’s because
Learn You a Haskell for Great
Good! is such a fun read — there are too many funny bits to list
but my favorite so far is when the author analyzes the first verse of
Avril Lavigne’s Girlfriend.
Although I think my code in Haskell tends to be more readable than in
other languages, code obfuscation in Haskell is almost natural: all you
have to do is refactor the wrong function to be “pointfree”, which means
that even though it’s a function that takes arguments, you define it
without parameters by manipulating and joining a bunch of other
functions. Example (plus a few other tiny obfuscations):
isPrime = liftA2 (&&) (liftA2 ($) (all . ((.) (0 /=)) . rem) (flip
takeWhile [2..] . (flip (.) $ liftA2 (*) id id) . (>=))) ((<) 1)
QQ wordpress why no Haskell highlighting (Editor’s note from
2017: The migration should highlight this now!)
Also, for some reason, you can do this in Haskell:
ghci> let 2 + 2 = 5 in 2 + 2
5
(via Haskell for the
Evil Genius)
Okay, but seriously now. I wrote this about my journey to learn
functional programming in the
programming babble post half a
year ago:
The main obstacle I have is that it’s hard to optimize or get
asymptotics when computation is expensive (a big problem if you’re
trying to learn through Project Euler problems, particularly ones with
lots of primes).
Okay I don’t actually know how this pointless rambling got so long. I
know the longer it is the more people will just tend to skim, because I
do that all the time. So I went back and refactored—er, rewrote all the
somewhat tangential bits (wow these puns are too easy) into footnotes.
Manually. Obviously if I have to do this again I’ll write a script for
it. But the post is still really long, and I bet nobody will read the
whole thing. Oh well.
Life updates: I got out of the hospital Friday two-and-a-half weeks
ago, went to the preliminaries of NPSC (a national team programming
contest) with classmates, threw up a lot, went back into the hospital,
and came out again. I wrote a lot of stuff about the experience and how
much it sucked (hint: a lot) when I started this draft around
that time, but now putting so much detail in this post feels weird. I’m
mostly good now.
Three years ago NPSC was the only programming contest I really knew
of; now I’ve participated in quite a few more, both online and locally,
but it’s still the only contest I’ve entered that gives you real-time
verdicts. I believe it inherits this from being modeled after ACM-ICPC,
but that’s for college people and I’m less clear on how it works. All
the other contests, namely
TopCoder,
CodeForces,
USACO, and the other local individual
competition (there doesn’t appear to be an English name so for the
purpose of this post I’ll just call it “Nameless Local”; there’s a
nation-wide competition in one-and-a-half weeks!), have system tests
after the contest that don’t allow you to resubmit afterwards. They all give pretests that you get
to know about right away, just to catch super-silly non-algorithmic
mistakes like failing to remove the debug statements or reading input
from the wrong place, but these contain weak test cases and don’t
guarantee that the solution will pass the system tests and get full
score.
diagrams is a
nifty Haskell library for making vector diagrams. I keep coming back to
it to generate graphics for puzzles:
I got sick of relearning it every time, and I think there’s some
small chance other people will find it useful too, so I wrote something
up. This post is a sort of reference that tries to compromise between
the quick start
tutorial and manual on one
hand, and the API reference on the other, to try to be deeper and more
comprehensive than the former, but also flow better and be easier to
navigate than the latter. Some types are just really intimidating when
fully written out…
circle :: (TrailLike t, V t ~ V2, N t ~ n, Transformable t) => n -> t
To avoid unhelpfully generic types, I will deal concretely with
two-dimensional diagrams that measure everything in Double,
and will frequently abbreviate complex types with an asterisk, like I
will write V2* for V2 Double. I will introduce
these aliases along the way for easy greppability. They’re not legal
Haskell, of course.
This reference assumes basic-to-intermediate Haskell knowledge. Some
of the more intermediate stuff includes:
- Monoids, and that the Haskell
Monoid operator is
<>
- Typeclasses. I will sometimes write fake type signatures as
abbreviations for typeclass restrictions: for example,
TrailLike is a typeclass, and I might say or write that a
function returns TrailLike when I really mean
TrailLike t => t, any type t that is in
that typeclass.
van Laarhoven lenses may help, but mostly I’ll try to black-box
them.
