.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/vm/foundations/plot_01_reverse_polish.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_vm_foundations_plot_01_reverse_polish.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_vm_foundations_plot_01_reverse_polish.py:


Reverse Polish notation: the stack's natural order (Łukasiewicz 1924, Hamblin 1957)
===================================================================================

Łukasiewicz wrote logic with operators before their operands, which needs no
parentheses. Hamblin reversed it for computers: in reverse Polish notation,
``(1 + 2) * 3`` is ``1 2 + 3 *``, and a machine evaluates it by pushing each
number and letting each operator replace the top two values with the
result. Dijkstra's shunting-yard algorithm (1961) translates ordinary
notation into that order. Every stack virtual machine, from Forth to the
EVM, runs programs in this form.

What to look for
----------------

The compiled program is just the RPN sequence, one instruction per token, and
its result matches Python's. The stack height rises with each pending
operand and falls with each operator.

The history behind this experiment: :doc:`/history/vm_breakthroughs`.
See :doc:`/exercises/vm` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 25-27

Infix to RPN to instructions
----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-42

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.vm.visualizers import plot_execution_trace

    expression = "(1 + 2) * 3 - 8 / (4 - 2)"
    rpn = bk.vm.to_rpn(expression)
    program = bk.vm.compile_expression(expression)
    print(" ".join(rpn))
    for instruction in program:
        print(instruction)
    result = bk.vm.execute(program, trace=True)
    assert result.stack == ((1 + 2) * 3 - 8 // (4 - 2),)
    assert len(program) == len(rpn)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    1 2 + 3 * 8 4 2 - / -
    ('PUSH', 1)
    ('PUSH', 2)
    ('ADD', None)
    ('PUSH', 3)
    ('MUL', None)
    ('PUSH', 8)
    ('PUSH', 4)
    ('PUSH', 2)
    ('SUB', None)
    ('DIV', None)
    ('SUB', None)




.. GENERATED FROM PYTHON SOURCE LINES 43-46

Arithmetic is the machine's
---------------------------
Results wrap modulo 2**256, and / is floor division.

.. GENERATED FROM PYTHON SOURCE LINES 46-52

.. code-block:: Python

    assert bk.vm.execute(bk.vm.compile_expression("0 - 1")).stack == (2**256 - 1,)

    fig, ax = plt.subplots(figsize=(9, 4.5))
    plot_execution_trace(result.trace, ax=ax)
    fig.tight_layout()




.. image-sg:: /api/gallery/vm/foundations/images/sphx_glr_plot_01_reverse_polish_001.png
   :alt: State after each instruction
   :srcset: /api/gallery/vm/foundations/images/sphx_glr_plot_01_reverse_polish_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 53-58

Exercise
--------
Write ``2 * (3 + 4)`` in Polish (prefix) notation and in RPN by hand. Why
can an RPN evaluator scan left to right with one stack, while a prefix
evaluator naturally scans right to left?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.199 seconds)


.. _sphx_glr_download_api_gallery_vm_foundations_plot_01_reverse_polish.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/vm/foundations/plot_01_reverse_polish.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_reverse_polish.ipynb <plot_01_reverse_polish.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_reverse_polish.py <plot_01_reverse_polish.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_reverse_polish.zip <plot_01_reverse_polish.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_