In this homework assignment, we asked you
to do a few optimizations. The very basic
optimizations you can do are very, very
simple optimizations on binary operations, on
basic arithmetic, and the ones we specifically
asked you to do are these right here as well as
replacing expressions with constants when
applicable. So we gave you this one right here
and then, to add in the others, we just do this
great big ‘else… if…’ statement. So the first
one, we check that the operation is times, we
check that A is a number and it’s a number
equal to one. And if it is, well, one times
anything is that second thing, is B. So we just
returned B. We don’t have to wait and run this
through once we’re interpreting. That would
take more effort than we need to. Now we do
the same thing with the next one if B is one
and A is something else. We can just return A.
Now we can do the same thing with addition
and 0. We just check if the operation is equal
to plus and that A is a number and it’s a
number equal to 0, then we return B. If B is a
number equal to zero, then we return A. And
finally, the last one that we asked you to
implement is a number minus itself is 0. So
that’s fairly straightforward too. Check if the
operation’s equal to minus and then if A
equals B – and remember, you can do that
because you can check if Python tuples are
equal to each other, not just numbers – then
we return a tuple of number and 0 to indicate
the number 0 in our abstract syntax tree. Now
the constant folding is a little bit more work,
but really not too much. First, we check that
the first element of the tuples A and B are
number. Then if the operation is addition, if
the operation equals plus, then we return
number and second element of A and B added
together. So that way, we don’t have to run
that operation later on when we are actually
running the program. And we can do the same
thing if we check if the operation is minus,
then we run – then we return tuple of number
and the second element of A and B subtracted
and similarly for multiplication. We can just
do the same thing for the second elements of
A and B, multiply together. And then once we
have hoped that the operations have been
optimized in some way, we wrap it back up in
a binary operation and a tuple of BinOp, AOP
and B, and return that. And if none of this
worked, if we didn’t even get a BinOp to
begin with, then we just return the expression
because those are all the optimizations that we
have done. So let’s try that with a few of these
test cases and these are the test cases that we
provided you with. So we have zero, one and
two, numbers equal to 0.0, 1.0 and 2.0, and a
few variables that are ancient kings and
queens of Persia and Macedonia – Xerxes,
Darius, Antiochus and Musa – and then we’re
going to define a plus operation, just so we
don’t have to keep writing this tuple out, and a
minus operation and a times operation
similarly, just to save some key strokes. And
then we’re going to check whether an
expression that we’ve said, which is times 2
and 0 is equal to 0. That is their optimization
actually ran. We’re going to do the same thing
with a minus operation and a slightly more
complicated operation. Expression three is
minus plus zero plus one plus two zero two.
That was a quite a big mouthful, so let’s go
through it just a bit more in-depth. Plus two
and zero, so two plus zero and then we wrap it
in this call to plus, so two plus zero plus one
and we wrap it again in a plus zero, and then
we wrap all of this up and subtract two from
whatever this is. So this really should just be
three minus two. Once you get past all of the
massive amounts of parentheses. So we print
out and make sure that that is indeed equal to
one. We do the same thing for these
expressions as well. So when we run this, we
see that we pass all of our test cases. And this
– our test cases involved a bunch of hand-
checking, where we just made all these up and
hand-checked that this is what they’re suppose
to be and then verified that the optimization
actually does what we think it’s going to do.
This isn’t necessarily how you would
normally do it, but it’s good enough to serve
our purposes right now.
宿題では最適化をいくつかやってもらいました
とても基本的で簡単にできる
算術二項演算に対しての最適化です
できる時には式を定数に
置き換えるというものでした
ここにあるものは与えられていたもので
他のものを加えるため長くelifを続けています
最初は演算が乗算かを確かめ
左側aが数値の1かどうか見ます
そうであれば1に何を掛けても右側のbとなるので
ここでbを返します
実行まで待つ必要はありません
必要以上の労力をかけることになります
同様に右側のbが1の時にaを返します
0を加算する場合にも同様のことを行います
演算が加算でaが数値0だとするとbを返し
bが数値0だとするとaを返します
最後に数値から同じ数値を引く場合です
これはわかりやすく
減算でaとbが等しいかどうか調べればいいのです
これができるのは数ではなく
Pythonのタプルが等しい時です
そして数値0を表すタプルを返し
抽象構文木に入れます
定数畳み込みはもう少し複雑ですが
大したことはありません
最初に両辺aとbのタプルが数値であるかを調べます
そして演算が加算なら数値を返し
その値はaとbの値を足したものになります
こうすればプログラムを実行する時に
あとで同じ演算をしなくて済みます
同様に減算の時はaからbを引いた
数値のタプルを返します
乗算についても同様で
aとbの2番目の要素をかけるだけです
そして演算が再帰的に最適化されれば
それを元のbinopのタプルに戻して
a、op、bを入れて返します
どの場合にも当てはまらず
binopも見つからなければ
これ以上の最適化はできないので
式をそのまま返します
よいテストケースを準備してきました
zero、one、twoがあり
それぞれ0.0、1.0、2.0に等しい数値のタプルで
さらにペルシャとマケドニアの
古代の王や女王の名から取った変数
xerxes、darius、antiochus、musaがあります
関数plusを定義して
このタプルを書かずに済むようにし
同様にminusとtimesも定義します
キーを打つ作業を少なくするためです
そして式が実際に最適化されているかを見るために
times(two,zero)が0と等しいかを出力し
等しければ最適化が動いたことになります
同様に減算や
もう少し複雑な計算の構文木も作っています
exp3はminus(plus(zero,plus
(one,plus(two,zero))),two)
舌をかみそうです
深く見るとplus(two,zero)はtwoになり
別のplusの中に入ってplus(one,two)となり
そのplus(one,two)がzeroに足され
さらに全体からtwoを引いています
つまり大量の括弧を乗り越えれば
3-2になります
これがoneになるかどうかを確かめます
同様のことを式についても確かめて実行してみると
すべてのテストでうまくいったとわかります
このテストケースは手作業で作られており
これを通れば最適化が
問題文のとおりにできているとわかります
普段からこれほどテストする必要はありませんが
今回はこれが最適でした
Neste exercício, nós pedimos que você
fizesse algumas otimizações. As otimizações básicas
que você pode fazer são otimizações muito, muito
simples, sobre operações binárias,
aritmética básica. E as que nós pedimos especificamente
que você fizesse são estas aqui, além de
substituir expressões por constantes, quando se aplica.
Então, nós demos a você esta aqui e depois,
para adicionar as outras, nós simplesmente fazemos
este grande comando if-then-else. Então, a primeira
é: nós verificamos se a operação é *,
verificamos se a é "number", e se é o número 1,
e, se for esse o caso, bem, 1 vezes
qualquer coisa é esta segunda coisa -- e isso é b.
Então, simplesmente retornamos b. Não teremos que executar
isso quando estivermos interpretando.
Isso gastaria mais eforço do que é necessário. Agora,
temos que fazer o mesmo para o próximo: se b é 1
e a é alguma outra coisa, simplesmente retornamos a.
Agora podemos fazer a mesma coisa para adição com 0.
Simplesmente verificamso se a operação é +
e se a é um "number" e é o número 0,
e então retornamos b. Se b for um
"number" e for 0, então retornamos a.
Finalmente, a última que pedimos que você fizesse é
implementar que um número menos ele próprio é 0.
Isso é muito fácil. Verificamos se
a operação é - e então se
a == b e, lembre-se, você pode fazer isso
porque você pode verificar, em Python, se tuplas são
iguais, não apenas para números. Então,
nós retornamos a tupla ("number",0), para
incluir o número 0 na nossa árvore de sintaxe abstrata.
Agora, a simplificação de constantes dá um pouco mais de trabalho,
mas não muito. Primeiro, verificamos se
os elementos da tupla -- a e b -- são ambos
do tipo "number". Então, se a operação é adição,
se a operação é +, nós retornamos
("number", a+b).
Desse modo, não teremos que executar
essa operação mais tarde, quando estivermos
executando o programa. E podemos fazer a mesma coisa,
se a operação for subtração.
Neste caso retornamos a tupla
("number", a-b).
E de modo análogo para multiplicação: fazemos
a mesma coisa para os elementos a e b --
multiplicamos os dois. E uma vez que nós
esperamos que essas operações sejam
otimizadas de algum modo, nós as encapsulamos
de novo em uma operação binária -- uma tupla ("binop",a,b) --
e depois retornamos isso. E se nenhuma dessas
funciona, se nós nem mesmo temos um "binop"
para começar, simplesmente retornamos a expressão,
porque tudo isso que estamos fazendo são otimizações.
Então, vamos tentar isso com alguns destes casos de teste.
Estes são os casos de teste que
fornecemos para você. Temos zero, one e two --
que são os números 0, 1 e 2 -- e
algumas variáveis, que são antigos reis e rainhas
da Pérsia e da Macedônia -- xerxes,
darius, antiochus e musa. E então vamos definir
um operação plus, apenas para que
não tenhamos que escrever esta tupla,
assim como uma operação minus e uma times,
simplesmente para econimizar digitação.
E, então, vamos verificar se
uma expressão tal como, digamos, times(two,zero)
é igual a zero, isto é, se a otimização realmente é feita.
Vamos fazer a mesma coisa
para a operação minus, e para outra operação,
ligeiramente mais complicada: a terceira expressão é
minus(plus(zero,plus(one,plus(two,zero)))),two).
Isso é bem longo, então vamos examinar
com um pouco mais de cuidado.
plus(two,zero) -- 2+0 -- e depois encapsulamos isso
nesta chamada a plus -- (2+0)+1 --
e depois usamos isso em um plus com zero e, depois,
de tudo isso, subtraímos com 2.
Portanto, isso realmente deve dar simplesmente 3-2,
se você conseguir passar por todos esses parênteses.
Então, imprimos isso e
nos certificamos de que, de fato, é igual a one.
Fazemos a mesma coisa para essas outras expressões.
Então, quando executamos isso,
vemos que passamos em todos os casos de teste.
E esses casos de teste envolvem um bocado de
trabalho, onde simplesmente fizemos tudo isso
para verificar que isso é o que deveria ser a resposta,
e depois verificar que a otimização
de fato faz o que pensamos que deve fazer.
Essa não é necessariamente a forma como você
faria normelmente, mas é suficientemente bom para
serir aos nossos propósitos.