by remywang.science

A canonical form for a language defines a representative among an equivalent class of terms. It can help identify equivalent terms in the language. Here I present a proof for the canonicity of the sum-over-product normal form for arithmetics, to demonstrate an interesting technique that I call induction over derivatives. A more catchy name I thought of is gradient induction.

Trevor Paglen - untitled reaper drone

untitled (reaper drone), trevor paglen, 2012, ICA/Boston

First let's clarify what we mean by canonical form: when two expressions in a language, considered as programs, evaluate to the same result on all possible inputs, we say they are semantically equivalent. We therefore hope to find a “standard way” to write such expressions, so that when we rewrite any two expressions to the standard form, we can immediately tell if they are semantically equivalent by just looking at them. Such a standard form is considered canonical – we say that two terms, e1 and e2, share the same canonical form if and only if they are semantically equivalent, where semantically equivalent means the terms always compute the same result given same inputs. Formally:

canonicalize(e1) ≡ canonicalize(e2) ⇔ ∀ x . eval(e1, x) = eval(e2, x)

Here ≡ denotes syntactic equality, and = denotes semantic (value) equality. In our case, the expressions are in the language of arithmetics (+, *, x, ℝ):

Definition. An arithmetic expression is either a variable, a constant, the sum of two expressions, or the product of two expressions.

And our normal form is essentially the standard polynomials:

Definition. The sum-over-product normal form of an arithmetic expression is the sum of products of literals, where a literal is either a variable or a constant. Furthermore, we combine monomials that only differ in their coefficients, e.g. 2xy + 3xy is rewritten into 5xy.

One can rewrite an expression to SoP with the standard laws (associativity, commutativity & distributivity). That is, we keep pulling + up and merge terms. For example, the SoP canonical form of (x + z) (x + y) is x2 + xy + xz + yz.

Proposition. The sum-over-product normal form is canonical: Csop(e1)Csop(e2) ⇔ ∀ x . eval(e1, x) = eval(e2, x)

Proof. The left-to-right direction can be proven by structural induction over the SoP normal form syntax, together with the fact that the standard rewrite rules we use preserve the semantics of arithmetics.

I now prove the contrapositive of the backward direction:

Csop(e1)Csop(e2) ⇒ ∃ x . eval(e1, x)eval(e2, x)

There are two cases for Csop(e1)Csop(e2): 1. e1 and e2 differ in their constant term (e.g. e1 = 2xy + 4 and e2 = 3yz + 7), and 2. otherwise (e.g. e1 = 2xy + 4 and e2 = 3yz + 4). Note that we only look at the lonely constants, not the coefficients in other terms.

Case 1 is simple, since if two expressions have different constants they evaluate to different results (i.e the constants themselves) on all-zero inputs.

To prove case 2, I break down the goal into two steps:

Csop(e1)Csop(e2) ⇒ ∃ y . ∂ e1 / ∂ y∂ e2 / ∂ y


y . ∂ e1 / ∂ y∂ e2 / ∂ y ⇒ ∃ x . eval(e1, x)eval(e2, x)

Recall that ≠ is semantic inequivalence.

The latter is simple: pick x1 and x2 that only differ in the y variable (from ∂ y above). Since the derivatives differ, we can always find a pair of x1 and x2 such that either eval(e1, x1)eval(e2, x1) or eval(e1, x2)eval(e2, x2).

To prove Csop(e1)Csop(e2) ⇒ ∃ y . ∂ e1 / ∂ y∂ e2 / ∂ y, we perform induction over the derivatives of the expressions, with our original proof goal as the inductive hypothesis: Csop(e1)Csop(e2) ⇔ ∀ x . eval(e1, x) = eval(e2, x). Since Csop(e1)Csop(e2), we know ∃ y . ∂ e1 / ∂ y∂ e2 / ∂ y (syntactically). Since the derivative of a canonical form is also canonical (not that obvious, but you'll see it after thinking a little harder), by our inductive hypothesis, ∃ y . ∂ e1 / ∂ y∂ e2 / ∂ y (semantically).

The preceding induction is sound because taking the derivative makes any expression simpler, eventually bringing it to a constant. □

The main takeaway here is that, when we want to perform an inductive proof, we need every inductive step to make the terms simpler. Usually this is done by structural induction over the language definition; but when the language is differentiable, the derivative is another tool for inductively simplifying the terms. This can come handy for the PL researcher, since we now know a wide range of languages are differentiable – not just polynomials!

p.s. Haotian Jiang & Sorawee Porncharoenwase pointed out a much simpler proof: given two semantically equivalent arithmetic expressions, their difference is always zero. Therefore, the expression that represents the difference has infinitely many roots. According to the fundamental theorem of algebra, the two expressions must be the same polynomial, since otherwise their difference would be a none-zero polynomial and has finitely many roots.

by 汪曾祺 trans. KW

It's been 4 years since Ming Hai left home.

He came here when he was 13.

The name of this place is a bit odd, called An Zhao Village. Zhao is the surname of most residents here. Village because the homes are scattered. Over here you see two, three homes, and over there two, three homes. You can see your neighbors from your doorstep, but it takes a while to get to them. That's because there isn't a road, but only winding trails that pass through the farm lands. An, because there is a nunnery (An). It's named Budda An, but over the generations people started calling it the pudding An. Even the monks here call it the pudding An. “Where's your residence?” “pudding An”. An's are for nuns – monasteries for monks, nunneries for nuns. But the pudding An houses monks. Perhaps because it's small – big monasteries, small nunneries.

His family call Ming Hai “Sunny” at home. He knew since little he'd be leaving home one day. Where he's from, people don't say “leave home”, but “to become a monk”. Where he's from exports lots of monks. Just like some places export butchers, some places export basket weavers, some place export barrel makers, some places export musicians, some places export painters, and some places export whores, his place exports monks. A family with a lot of sons would send one to become a monk. Becoming a monk also needs networking. Monks from here travel far: some go to the Temple of Hermits in Hang Zhou, some to the Temple of Calm in Shanghai, some to the Golden Mountain Temple in Zhen Jiang, some go to the Temple of Peace in Yang Zhou. But most of them stay around town. Sunny's family doesn't have a lot of farm land, so his three brothers are just enough to take care of it. He's the youngest. When he was 7, his uncle – also a monk – visited.

He discussed with Sunny's mom and dad for him to become a monk. Sunny was there too, and he thought it all made sense. It's good to become a monk: first, you get fed. Every temple feeds their monks. Second, you can save up some money. As soon as you learn to do the funeral ceremonies and the prayers, you'll get paid. Save up enough money, you can then quit and get married. If you don't want to quit, you can go buy some farm land with that money. But it's not easy either to become a monk. First, one must look handsome – eyes still as the full moon; then one must sound good – voice bright as the morning bell; finally you must be smart and have a good memory. His uncle took a good look at Sunny, told him to walk around and shout out some cowboy hollers, then decided: “Sunny for sure will be a good monk, I'll take him!” To become a monk, you need to invest – study for a few years. What kind of monk can't read! So Sunny started school, reading the Scripture of the Triplets, the Names of the Centurions, the Collection of Proses, the Classics for the Young, Confucian, Meng... Everyday he would write a page of copies. People all say he writes well – every stroke dark against the pearl white paper.

Uncle returns as promised, with a Monk's Shirt of his that he asked Sunny's mom to trim short for Sunny. Sunny puts on the shirt, together with the purple pants he wore at home as well as a pair of new shoes. He kneeled for his mom and dad, and then left with his uncle.

When he was at school he got a School Name, called Ming Hai (Clear Sea). His uncle said it will do as a Monk's Name too.

They sail across a lake. What a big lake! They walk through a town. A busy town: spice shops, tax offices, butcheries with slices of pork, a donkey in the sesame mill (the smell of sesame spills onto the street), a clothes shop, people selling flower seeds, a barber, someone selling embroidery and threads, a man with medicines, someone blowing out figures from syrup, a woman with a snake... Sunny wants to see them all. Uncle has to push him: “let's go!”

They come to a creek. Here a boat awaits them, and onboard stands a skinny old grandpa in his 60s, and a girl Sunny's age sits in front. She's peeling a lotus flower to eat the seeds. Once Sunny and Uncle sit down, the boat slowly begins to move.

Sunny hears someone talking to him. It's the girl. “Are you the one going to the pudding An to become a monk?” Sunny nods. “They have to burn tattoos onto your head! Aren't you scared?” Sunny's not sure how to answer, so he shakes his head. “What's your name?” “Ming Hai.” “No, I mean what do they call you at home?” “They call me Sunny” “Sunny! I'm Dandelion! We'll be neighbors. Grandpa and I live next to the pudding An. Here you go!” Dandelion tosses the rest of the lotus flower to Sunny, who takes over and peels out the seeds to eat.

Grandpa rows stroke by stroke. You can only hear the oar hitting the water: “Hoo-Shoo! Hoo-Shoo!”

... ...

The pudding An sits on a nice spot on top of a hill. The hill overlooks the area, so it was picked by those building the nunnery. A creek flows pass before the gate. Outside the gate there's a large wheat field, surrounded by tall willows on three sides. Behind the gate lies a yard, where a Buddha statue sits. Someone famous wrote a pair of proses hugging the gate:

a big belly withholds what's hard to bear a hearty laugh serves those funny to meet

Behind the Buddha stands the Sacred Carrier, and past the yard is a skylit garden, where two apricot trees grow. Each side of the garden hosts three rooms, and past the garden is the temple, homing the Buddha of the Three Worlds. Even with the frame the Buddha is only just over four feet tall. To the east lies the Head Residence, and to the west is the storage. A hexagonal doorway opens up eastwards to the outside, with white doors and green characters that read:

one flower conceals an entire world look thrice and you will see three Buddhas inside

Inside the doorway is a thin, long stretch of garden – some rocks to form a bonsai mountain, a few pots of flowers, and three small rooms.

The young monk has an easy life. Every morning he wakes up, opens the gate, and sweeps the floor. The floor in the nunnery is made of smooth bricks, so it's really easy to sweep. Then he burns some incense for the Buddha and the Sacred Carrier, as well as for the Buddha of the Three Worlds in the temple. He kneels thrice, chants Namu Amida Butsu thrice, and sounds the bell thrice. The monks here don't care about morning and evening prayers, so the three bells by Sunny would suffice. Then he goes on to get the water and feed the pigs. At last he waits for the Head Monk, who is Sunny's uncle, to teach him to read the Scripts.

to be continued

purple haze

lyrics by Wild Children 野孩子 translation by R.W.

Wild Children was formed in Feb. 1995 in Hang Zhou, by Zhang Quan (张佺) & Xiao Suo (小索). In May, they returned to their birth place Lan Zhou and spent a year working among folk musicians in North West China. As they traveled along the Yellow River on foot from Yan An to Inner Mongolia, they wrote a number of songs.

1 Wild Children 野孩子

They told me about your dirty face Told me about your never ending tears They told me about your home in the woods Told me about your songs that no one hears

他们说你的脸上沾满灰 他们说你的泪在天上飞 他们说你的家在山野里 他们说你的歌有谁来听

Don't you ask me who I am, I'm from far away over the mountains Don't you ask me who I believe, I stand right here under the sun Don't you ask me who I hate, when I'm cold and hungry Don't you ask me who I love, once the flowers have bloomed and fallen again

不要问山高路远我是谁 不要管太阳下面我信谁 不要说冷了饿了我恨谁 不要等花开花落我爱谁

2 Don't You Know 你可知道

You like the rhododendrons on the mountain top, Red as flame – Don't you know how long they have grown? You ask the riders on the horsebacks along the road – How many rivers have they crossed?

你说那山上的杜鹃花儿红 你可知道,它长了多少年? 你问那大路上骑马走过的人 趟过的河,它有多少?

You hear the chirps of the cuckoo birds; Don't you know how far away they live? Won't you think about those exiled ones – How long have they walked, step by step?

你听那飞过的杜鹃鸟儿叫 你可知道,它家在哪里? 你猜那远方背井离乡的人 走过的路,它有多少?

3 Had They Known 早知道

Had they known the Yellow River would dry, Wouldn't have built the goddamn bridge Had they know those by the river would leave, Wouldn't have sung the goddamn song

早知道黄河的水呀干了 修他妈的那个铁桥了是做啥呢 早知道河沿上的人呀走了 唱他妈的那个歌儿了是做啥呢

Had they known the Yellow River would dry, Wouldn't have blown the suede raft Had I known my girl's heart would change, Wouldn't have told her I loved her so

早知道黄河的水呀干了 吹他妈的那个羊皮了是做啥呢 早知道尕妹妹的心呀变了 谈他妈的那个恋爱了是做啥呢

4 Ballad of The Yellow River

Where I lived flows a great river that runs through my city. I cannot forget about the river, nor about the many people who lived in the city and the many things that happened there. Today I want to sing a song; I want you to come with me, to that river, and to that city.


The Yellow River flows without a break It flows through my hometown, Lan Zhou Beloved ones who are far away, Listen to this Ballad of the Yellow River The Sun travels without a stop It passes Home, passes Lan Zhou The Moon is shining upon the bridge, And I'm singing by the Yellow River

黄河的水不停地流 流过了家流过了兰州 远方的亲人哪 听我唱支黄河谣 日头总是不歇地走 走过了家走过了兰州 月亮照在铁桥上 我就对着黄河唱

Every time I wake up in the morning, Thinking about Lan Zhou, thinking about Home Thinking about the scent of the pagoda trees Thinking about my sweet girl far away The Yellow River flows without a break It flows through my hometown, Lan Zhou The vagabond keeps singing the song, This song about the Yellow River

每一次醒来的时候 想起了家想起了兰州 想起路边槐花儿香 想起我的好姑娘 黄河的水不停地流 流过了家流过了兰州 流浪的人不停地唱 唱着我的黄河谣

5 Four Seasons 四季歌

Those who love Spring have the purest souls Just like the blooming violets, like my dearest friends

爱春天的人们 是心地纯洁的人 像那盛开的紫罗兰 像我的朋友一样

Those who love Summer have the strongest will Just like the roaring waves, like my dearest father

爱夏天的人们 是意志坚强的人 像那冲击岩石的波涛 像我的父亲一样

Those who love Autumn hold the deepest compassion Just like the Moon that lights up the night, like my dearest lover

爱秋天的人们 是一往情深的人 像那照亮黑夜的月亮 像我的爱人一样

Those who love Winter have the warmest hearts Just like the Land that melts the snow, like my dearest mother

爱冬天的人们 是胸怀宽广的人 像那融化冰雪的大地 像我的母亲一样


definitely the best dish I've ever cooked – great looking, tasty, and healthy

It was the most gruesome murder anyone has seen. Even though the screen was blurred out, you can still make out the shredded body and its terrifying state. Every inch of muscle is exposed and torn apart, as if some mad animal came upon it and unleashed all its rage onto it. You could see it swing the victim up and down and around with its mouth, and mauling him with fearsome claws – aiming not to consume him as food, but for total destruction. And what was left of him was discarded here, in his own house, as a memento for the unimagined pain he suffered through. Of course the killer is not an animal, and there is no question who he is. He had killed dozens like this, and there was nothing anyone could do to stop him.

And I know he's coming for me. There was nothing I could do – he would come nevertheless. This numbing fear captivated me for the past weeks since the last murder, so intense the desperation that I am no longer affected by it. I have returned to my normal sleep schedule, gained back my appetite, and could focus on work even better than before. This desperation has dragged my soul down into the deepest crevice of the glacier and froze it there, and what remained of me is now just a cold machine, keeping its operation on the empty assembly line until the blow comes. It was only when the night was deep or when the dawn was thin, that I could still feel the trembling fear that this day could be the day he came.

This morning was no different, and I open my eyes with same sensation of fear. It takes long before I climb out of my bed, as if I am convinced that as long as I stay in bed, he would leave me alone. But as the sun rises and the noise of the machines loom near, the fear once again sank into the depths. As usual, the water boiler just started to make noise as I open my bedroom door. I freeze just as I walk pass the apartment door – the one sitting at the table is not S., but him. He sits with his back to the kitchen door, in a dark blue suit. No one has ever seen him alive, but I know it's him, just as anyone would recognize him without having seen his picture or heard any description of him. Without turning, he flatly said: “do you want it to hurt, or do you want it slow?”

By an ancient instinct, I open the apartment door with some struggle and sprinted out without my shoes. For a good while, I am no longer conscious of the passage of time, but just run as fast as I can, faster than I ever could. I know perfectly well, that this is all futile, that no matter how fast I go, by foot or by plane, it's always too slow for him. He didn't come out and follow after me, which makes my desperation all the worse. Because I know running like this is no different from stopping, dropping on the ground, or even going back to the apartment to hand over my life. Even if by miracle I get onto a plane and fly across the continents, he would walk up to me the moment I land. But I can't tell my body to stop. After a while, I realize I'm running along the exact same route that leads to work, the one I take every morning. What a stupid escape route! But what else could I do? Where I run to doesn't matter to him. And so I kept on running.

It was already 9 in the morning, but everywhere was surprisingly quiet. I can even hear the birds chirping – the early ones, not the chatty ones that yell across the streets in late afternoon. And bit by bit, I start hearing a classic rock song playing from a car radio. Now I see where it comes from: a bright colored jeep with four college students loading some bags. They seem ready for a BBQ on this sunny day – it finally has come to me that today's weather is gorgeous. One of them saw me running, disheveled and bare foot, so comes up and asks if I need help. For a minute or two, I struggle with breathing, and finally make it clear to him that I want a ride. With great irony, I request to be driven along, still, my exact morning route. The students hop on with me, the car moves without urgency, and the rock song plays on.

Collapsing on the back seat, I come to a deeper desperation: for the rest of my life, I will have to keep running like this. I will have to flee every second I breath, exhausted and hunted, and the moment I stop, he will show up with a pitying smile, standing atop my succumbed body and end my life with a single strike...

Perhaps shaken by this deepest desperation, I woke up – this time for real, jerking out of the nightmare. I lay soaked in sweat, arms and legs twisted, almost strangling myself with the blanket. Of course, I am overcome with relief. But at the same time, I come to a calm conclusion. That this Most Brutal Murderer exist. Or rather, Most Brutal Murderers exist. There are billions of them, one in each every household, sitting by the breakfast table waiting for the house to wake up. Their mere presence convince you of certain death. But in reality, no one should really fear them as people do. After the initial trauma, you come home and realize he is still there, reading a newspaper and shows no sign of slaying even an insect. The next morning, you wake up and he already made a cup of hot coffee, leaving it by the seat opposite to his and kept on reading his newspaper. As time goes on, this strange guy who doesn't eat or change clothes becomes a member of the household – something like a family ghost, and everyone treats him just like an uncle who came back from the war and acts strange. Then finally one day, he would say to you: “Excuse me, but I will have to take your life now. Please don't take it personally.” To which you reply: “I understand, please make sure I get what I deserve and no more. And please make sure to feed the dog and water the plants after.”

K.W. March 2018

Your letter came at a very special time. It is now exactly a year since we both visited UW as prospective students. The new admits for this year will be here the coming week, and I am very honored to take part in organizing and hosting their visit. L will come a bit later at the end of month.

That was how I started drafting this response in March, right after receiving your letter. It wasn't easy to write – I had so much to tell you! So much that I had to give up finishing it in the middle of deadlines and travels. Now it is in late June, and the days are getting shorter, but I finally got myself together and ready to try again.

It's been about 3 quarters of a year for me in Seattle, and I've had my up and downs. My time in grad school has been transformative – I have learned and unlearned an unbelievable amount in such a short time. But one thing has not changed a bit, and that is my reason to devote myself in science. I had almost forgotten about it, until I read the article Mathematics, Art, Civilization by Yuri Manin. I will not attempt to emulate what he says here, and the exact details do not matter. What touched me was how Manin demonstrated the most beautiful facets of mathematics – its simplicity, generality, and reality. The great polymath has captured stunning snippets of our universe (physics) and of ourselves (logic and languages) with just a few sketches on paper. It was exactly this beauty that drew me to maths when I was a little kid, and once again it drew me to computer science in college and into grad school.

Many researchers see science as a means towards technology, something that affects society in a corporeal, physical way. But some forget about the virtue of science itself, that it brings the most intimate joy to those who practice it. I have my doubts about technology and its promise to “make our lives better”. Those doubts are perhaps best expressed by James Suzman, an anthropologist who studies the hunter-gatherer San. The South African Bushmen became the longest-lasting civilization in the history of modern Homo Sapiens with their frugal technology. I respect those who help the afflicted with technology, but personally I believe in the power of science itself, as I have experienced it myself and have shared the experience with my fellow researchers.


I have learned countless lessons about the technicalities of how to do research, but I would not be so pompous as to lecture others about them. Those lessons are the point of grad school anyways, and a student will learn them eventually. The honest reason I'm sharing my thoughts above is really that I had a wonderful evening thinking them, and I bet they might bring you joy as well – just as the origami rose box you had sent me.


Remy, June 20 2018, Seattle

crazy diamond

txti.es used to host my personal page, and I still think it's telling the truth: it provides “Fast web pages for everybody” – that is, it takes no time to make a page that loads instantly even on a flip phone.

But txti doesn't support styling. After some time I finally found a way to get a good looking page with minimal effort. You can see the result at remywang.me and the source here.

I use markdown styles, which simply takes a markdown file and spits out the html. In the command that compiles the page, change jasonm23-foghorn to your favorite theme from markdown styles.

If you have images and want them to automatically resize on phone screens, make sure to use html for the image instead:

<img src="wishtree.jpg" alt="wishtree" style="max-width:100%;height:auto;">