<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
 <!--
      loads the http over https ssl -
      welcome to my website!

	this theme is based off the Ice & Fire theme created by Lucas Gatsas
      https://www.twitter.com/LucasGatsas
      www.lucasgatsas.ch - switzerland.
  -->


<!-- Microsoft Internet Explorer documentMode compatMode setting IE Modus -->
<script type="text/javascript">
var IE = null;
if (window.navigator.appName == "Microsoft Internet Explorer") {
  if (document.documentMode) {

    IE = document.documentMode;
    } else {

        IE = 5;
          if (document.compatMode) {
      if (document.compatMode == "CSS1Compat")
      IE = 11;
      }
    }
  }
</script>

    <meta charset="utf-8">
    <!-- X-UA -->
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta http-equiv="X-UA-Compatible" content="IE=11" />
    <link rel="author" title="Ranjit Jhala" href="http://ranjitjhala.github.io" />

    <meta name="google" content="notranslate" />
    <!-- Viewport -->
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <!-- index ROBOTS follow -->
    <meta name="robots" content="index, follow" />
    <!-- Site Desciption -->
    <meta name="description" content="UCSD CSE 131">
    <!-- Site Desciption -->
    <meta name="keywords" content="Ranjit Jhala, ranjitjhala, haskell, compilers, type systems">
    <!-- Favicon -->
    <link rel="shortcut icon" href="https://ucsd-progsys.github.io/131-web/static/img/ico.jpg" type="image/x-icon" />
    <!-- Blog Title -->
    <title>cse131</title>

    <!--     <title>{% if page.title %}{{ page.title }} - {{ site.title }}{% else %}{{ site.title }}{% endif %}</title>
-->
    <!-- Property Metas -->
    <meta property="og:image" content="https://ucsd-progsys.github.io/131-web/static/img/ix.png" />
    <meta property="og:title" content="UCSD CSE 131" />
    <meta property="og:site_name" content="UCSD CSE 131" />
    <!-- Canonical -->
    <link rel="canonical" href="{{ page.url | replace:'index.html','' | prepend: site.baseurl | prepend: site.url }}">
    <!-- StyleSheet -->
    <link rel="stylesheet" href="https://ucsd-progsys.github.io/131-web/static/css/bootstrap.min.css">
    <link rel="stylesheet" href="https://ucsd-progsys.github.io/131-web/static/css/spaceg.stylesheets.css">
    <link rel="stylesheet" href="https://ucsd-progsys.github.io/131-web/static/css/syntax.css">
    <!-- Fonts -->
    <link href="https://fonts.googleapis.com/css?family=Merriweather:400,300,300italic,400italic,700,700italic,900,900italic" rel="stylesheet" type="text/css">
    <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.2.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">
    <link href="https://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic" rel="stylesheet" type="text/css">
    <link href="https://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800" rel="stylesheet" type="text/css">
    <link href="https://fonts.googleapis.com/css?family=Playfair+Display:400,700,900,400italic,700italic,900italic" rel="stylesheet" type="text/css">
    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>
        <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
        <script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
    <![endif]-->
    <style>
	#preloader {position:fixed;top:0;left:0;right:0;bottom:0;background-color:#fff; /* change if the mask should have another color then white */z-index:99; /* makes sure it stays on top */}
	#status {width:200px;height:200px;position:absolute;left:50%; /* centers the loading animation horizontally one the screen */top:50%; /* centers the loading animation vertically one the screen */background-image:url("/static/img/preloader.gif"); /* path to your loading animation */background-repeat:no-repeat;background-position:center;margin:-100px 0 0 -100px; /* is width and height divided by two */}
	ul, ol {margin-top: 0;margin-bottom: 10px;}
	.navbar-inverse {background-color: #FFF;border-color: #FFFFFF;}
</style>
<!--link rel="stylesheet" href="https://ucsd-progsys.github.io/131-web/static/css/prettify.css"-->
<style>
	header.intro-header {background: #6f5499;background: no-repeat center center;background-attachment: scroll;-webkit-background-size: cover;-moz-background-size: cover;background-size: cover;-o-background-size: cover;}
	/* Preloader */#preloader {position:fixed;top:0;left:0;right:0;bottom:0;background-color:#fff; /* change if the mask should have another color then white */z-index:99; /* makes sure it stays on top */}
	#status {width:200px;height:200px;position:absolute;left:50%; /* centers the loading animation horizontally one the screen */top:50%; /* centers the loading animation vertically one the screen */background-image:; /* path to your loading animation */background-repeat:no-repeat;background-position:center;margin:-100px 0 0 -100px; /* is width and height divided by two */}
	li {list-style: none;}
            body.modal-open
            {overflow: hidden;padding-right: 0px;
        }
	article li {list-style: inherit;}
	article .figure {text-align: center}
    </style>
    <!-- end Loading front stylesheet here -->
    </head>

    <body>
	<div id="preloader">
	    <div id="status">

	    </div>

	</div>  
	<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1" aria-expanded="false">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="https://ucsd-progsys.github.io/131-web" id="blog-title-left-top">cse131</a>
        </div>
        <!-- Collect the nav links, forms, and other content for toggling -->
        <div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
            <ul class="nav navbar-nav navbar-right">
                <!-- <li class="dropdown">
                    <a href="#portfolioModal2" data-toggle="modal"><i class="fa fa-random" id="icon-top"></i></a>
                <ul class="dropdown-menu"></ul>
                </li>-->
                
                <li><a href="https://ucsd-progsys.github.io/131-web/calendar.html">Calendar</a></li>
                <li><a href="https://ucsd-progsys.github.io/131-web/contact.html">Contact</a></li>
                <li><a href="https://ucsd-progsys.github.io/131-web/grades.html">Grades</a></li>
                <li><a href="https://ucsd-progsys.github.io/131-web/lectures.html">Lectures</a></li>
                <li><a href="https://ucsd-progsys.github.io/131-web/assignments.html">Assignments</a></li>
                <li><a href="https://ucsd-progsys.github.io/131-web/links.html">Links</a></li>
                <li><a href="https://www.piazza.com/ucsd/fall2018/cse131/home" id="roundbutton" target="_blank"><i class="fa fa-twitter"></i>Piazza</a></li>
                <!--
                <li><a href="https://ucsd-progsys.github.io/131-web/archive.html">Archive</a></li>
                <li><a href="https://www.twitter.com/ranjitjhala" id="roundbutton" target="_blank"><i class="fa fa-twitter"></i>RanjitJhala</a></li>
                -->
            </ul>
        </div>
        <!-- /.navbar-collapse -->
    </div>
    <!-- /.container -->
</nav>
<!-- Portfolio Modals -->
    <div class="portfolio-modal modal fade" id="portfolioModal1" tabindex="-1" role="dialog" aria-hidden="true" style="padding-right:0px; overflow: hidden;">
        <div class="modal-content">
            <div class="close-modal" data-dismiss="modal">
                <div class="lr">
                    <div class="rl">
                    </div>
                </div>
            </div>
            <div class="container">
                <div class="row">
                    <div class="col-lg-8 col-lg-offset-2">
                        <div class="modal-body">
                            <h1 class="font-style-inline-small-h1">Ranjit Jhala</h1>
                            <hr class="star-primary">
                            <img src="https://ucsd-progsys.github.io/131-web/static/img/kc.jpg" class="img-responsive img-centered" alt title>
                            <p class="font-style-inline-small">
                                <a href="https://www.twitter.com/ranjitjhala" target="_blank">follow me</a>. <br>
                                <a href="https://www.github.com/ucsd-progsys/131-web" target="_blank">    <i class="fa fa-github" id="spaceg-social-modal"></i> </a>
                                <a href="https://www.twitter.com/ranjitjhala" target="_blank"><i class="fa fa-twitter" id="spaceg-social-modal"></i> </a>
                                <a href="https://plus.google.com/u/0/106612421534244742464" target="_blank"> <i class="fa fa-google-plus" id="spaceg-social-modal"></i></a>
                            </p>
                            <button type="button" class="btn btn-default" data-dismiss="modal"><i class="fa fa-times"></i> Close</button>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </div>
<!-- Menu Modals Add New Sa.21.Feb.2015 03:22:25 -->
    <div class="portfolio-modal modal fade" id="portfolioModal2" tabindex="-1" role="dialog" aria-hidden="true" style="padding-right:0px; overflow: hidden;">
        <div class="modal-content">
            <div class="close-modal" data-dismiss="modal">
                <div class="lr">
                    <div class="rl">
                    </div>
                </div>
            </div>
            <div class="container">
                <div class="row">
                    <div class="col-lg-8 col-lg-offset-2">
                        <div class="modal-body">
                            <h1 class="font-style-inline-small-h1">Ranjit Jhala</h1>
                            <hr class="star-primary">
                            <p class="font-style-inline-small">
                        <a href="https://www.twitter.com/ranjitjhala" target="_blank">follow</a>. <br>
                        <a href="https://www.github.com/ucsd-progsys/131-web" target="_blank">    <i class="fa fa-github" id="spaceg-social-modal"></i> </a>
                        <a href="https://www.twitter.com/ranjitjhala" target="_blank"><i class="fa fa-twitter" id="spaceg-social-modal"></i> </a>
                        <a href="https://plus.google.com/u/0/106612421534244742464" target="_blank"> <i class="fa fa-google-plus" id="spaceg-social-modal"></i></a>  <br>
                    <li><a href="https://ucsd-progsys.github.io/131-web/">Home</a></li>
                    <li><a href="https://ucsd-progsys.github.io/131-web/about.html">About Me</a></li>
                    <li><a href="https://ucsd-progsys.github.io/131-web/archive.html/">Archive</a></li>
                            </p>

                            <button type="button" class="btn btn-default" data-dismiss="modal"><i class="fa fa-times"></i> Close</button>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </div>


        <div id="content">
            <!-- Post Header -->
<header class="intro-header" style="background-image: url('https://ucsd-progsys.github.io/131-web/static/img/egg-eater.jpg')" alt title>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                <div class="post-heading">
                    <h1>Data on the Heap</h1>
                    
                    <span class="meta">
		    
		    </span>
                </div>
            </div>
        </div>
    </div>
</header>

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
			<p>Next, lets add support for</p>
<ul>
<li><strong>Data Structures</strong></li>
</ul>
<p>In the process of doing so, we will learn about</p>
<ul>
<li><strong>Heap Allocation</strong></li>
<li><strong>Run-time Tags</strong></li>
</ul>
<h2 id="creating-heap-data-structures">Creating Heap Data Structures</h2>
<p>We have already support for <em>two</em> primitive data types</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb1-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Ty</span></a>
<a class="sourceLine" id="cb1-2" data-line-number="2">  <span class="fu">=</span> <span class="dt">TNumber</span>     <span class="co">-- e.g. 0,1,2,3,...</span></a>
<a class="sourceLine" id="cb1-3" data-line-number="3">  <span class="fu">|</span> <span class="dt">TBoolean</span>    <span class="co">-- e.g. true, false</span></a></code></pre></div>
<p>we could add several more of course, e.g.</p>
<ul>
<li><code>Char</code></li>
<li><code>Double</code> or <code>Float</code></li>
<li><code>Long</code> or <code>Short</code></li>
</ul>
<p>etc. (you should do it!)</p>
<p>However, for all of those, the same principle applies, more or less</p>
<ul>
<li>As long as the data fits into a single word (4-bytes)</li>
</ul>
<p>Instead, we're going to look at how to make <strong>unbounded data structures</strong></p>
<ul>
<li>Lists</li>
<li>Trees</li>
</ul>
<p>which require us to put data on the <strong>heap</strong> (not just the <em>stack</em>) that we've used so far.</p>
<figure>
<img src="../static/img/memory-layout.png" alt="Stack vs. Heap" /><figcaption>Stack vs. Heap</figcaption>
</figure>
<h2 id="pairs">Pairs</h2>
<p>While our <em>goal</em> is to get to lists and trees, the journey of a thousand miles, etc., and so, we will <em>begin</em> with the humble <strong>pair</strong>.</p>
<h3 id="semantics-behavior">Semantics (Behavior)</h3>
<p>First, lets ponder what exactly we're trying to achieve. We want to enrich our language with <em>two</em> new constructs:</p>
<ul>
<li><p><strong>Constructing</strong> pairs, with a new expression of the form <code>(e0, e1)</code> where <code>e0</code> and <code>e1</code> are expressions.</p></li>
<li><p><strong>Accessing</strong> pairs, with new expressions of the form <code>e[0]</code> and <code>e[1]</code> which evaluate to the first and second element of the tuple <code>e</code> respectively.</p></li>
</ul>
<p>For example,</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb2-1" data-line-number="1"><span class="kw">let</span> t <span class="fu">=</span> (<span class="dv">2</span>, <span class="dv">3</span>) <span class="kw">in</span>  </a>
<a class="sourceLine" id="cb2-2" data-line-number="2">  t[<span class="dv">0</span>] <span class="fu">+</span> t[<span class="dv">1</span>]</a></code></pre></div>
<p>should evaluate to <code>5</code>.</p>
<h2 id="strategy">Strategy</h2>
<p>Next, lets informally develop a strategy for extending our language with pairs, implementing the above semantics. We need to work out strategies for:</p>
<ol type="1">
<li><strong>Representing</strong> pairs in the machine's memory,</li>
<li><strong>Constructing</strong> pairs (i.e. implementing <code>(e0, e1)</code> in assembly),</li>
<li><strong>Accessing</strong> pairs (i.e. implementing <code>e[0]</code> and <code>e[1]</code> in assembly).</li>
</ol>
<h3 id="representation">1. Representation</h3>
<p>Recall that we <a href="05-cobra.md/#option-2-use-a-tag-bit">represent all values:</a></p>
<ul>
<li><code>Number</code> like <code>0</code>, <code>1</code>, <code>2</code> …</li>
<li><code>Boolean</code> like <code>true</code>, <code>false</code></li>
</ul>
<p>as a <strong>single word</strong> either</p>
<ul>
<li>4 bytes on the stack, or</li>
<li>a single register <code>eax</code>.</li>
</ul>
<p><strong>EXERCISE</strong></p>
<p>What kinds of problems do you think might arise if we represent a pair <code>(2, 3)</code> on the <em>stack</em> as:</p>
<pre><code>|     |
-------
|  3  |
-------
|  2  |  
-------
| ... |
-------</code></pre>
<p><strong>QUIZ</strong></p>
<p>How many words would we need to store the tuple</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb4-1" data-line-number="1">(<span class="dv">3</span>, (<span class="dv">4</span>, <span class="dv">5</span>))</a></code></pre></div>
<ol type="1">
<li><code>1</code> word</li>
<li><code>2</code> words</li>
<li><code>3</code> words</li>
<li><code>4</code> words</li>
<li><code>5</code> words</li>
</ol>
<!--  
### Pairs vs. Primitive Values

The main difference between pairs and primitive values
like `number` and `boolean` is that there is no _fixed_
or _bounded_ amount of space we can give to a pair.
For example:

* `(4, 5)` takes at least 2 words,
* `(3, (4, 5))` takes at least 3 words,
* `(2, (3, (4, 5)))` takes at least 4 words  and so on.

Thus, once you start _nesting_ pairs we can't neatly tuck
all the data into a fixed number of 1- or 2- word slots.

-->
<h3 id="pointers">Pointers</h3>
<blockquote>
<p>Every problem in computing can be solved by adding a level of indirection.</p>
</blockquote>
<p>We will <strong>represent a pair</strong> by a <strong>pointer</strong> to a block of <strong>two adjacent words</strong> of memory.</p>
<figure>
<img src="../static/img/heap-pairs.png" alt="Pairs on the heap" /><figcaption>Pairs on the heap</figcaption>
</figure>
<p>The above shows how the pair <code>(2, (3, (4, 5)))</code> and its sub-pairs can be stored in the <strong>heap</strong> using pointers.</p>
<p><code>(4,5)</code> is stored by adjacent words storing</p>
<ul>
<li><code>4</code> and</li>
<li><code>5</code></li>
</ul>
<p><code>(3, (4, 5))</code> is stored by adjacent words storing</p>
<ul>
<li><code>3</code> and</li>
<li>a <strong>pointer</strong> to a heap location storing <code>(4, 5)</code></li>
</ul>
<p><code>(2, (3, (4, 5)))</code> is stored by adjacent words storing</p>
<ul>
<li><code>2</code> and</li>
<li>a <strong>pointer</strong> to a heap location storing <code>(3, (4, 5))</code>.</li>
</ul>
<h3 id="a-problem-numbers-vs.pointers">A Problem: Numbers vs. Pointers?</h3>
<p>How will we tell the difference between <em>numbers</em> and <em>pointers</em>?</p>
<p>That is, how can we tell the difference between</p>
<ol type="1">
<li>the <em>number</em> 5 and</li>
<li>a <em>pointer</em> to a block of memory (with address <code>5</code>)?</li>
</ol>
<p>Each of the above corresponds to a <em>different</em> tuple</p>
<ol type="1">
<li><code>(4, 5)</code> or</li>
<li><code>(4, (...))</code>.</li>
</ol>
<p>so its pretty crucial that we have a way of knowing <em>which</em> value it is.</p>
<h3 id="tagging-pointers">Tagging Pointers</h3>
<p>As you might have guessed, we can extend our <a href="05-cobra.md/#option-2-use-a-tag-bit">tagging mechanism</a> to account for <em>pointers</em>.</p>
<table>
<thead>
<tr class="header">
<th style="text-align: right;">Type</th>
<th style="text-align: right;">LSB</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: right;"><code>number</code></td>
<td style="text-align: right;">xx0</td>
</tr>
<tr class="even">
<td style="text-align: right;"><code>boolean</code></td>
<td style="text-align: right;">111</td>
</tr>
<tr class="odd">
<td style="text-align: right;"><code>pointer</code></td>
<td style="text-align: right;">001</td>
</tr>
</tbody>
</table>
<p>That is, for</p>
<ul>
<li><code>number</code> the <strong>last bit</strong> will be <code>0</code> (as before),</li>
<li><code>boolean</code> the <strong>last 3 bits</strong> will be <code>111</code> (as before), and</li>
<li><code>pointer</code> the <strong>last 3 bits</strong> will be <code>001</code>.</li>
</ul>
<p>(We have 3-bits worth for tags, so have wiggle room for other primitive types.)</p>
<h3 id="address-alignment">Address Alignment</h3>
<p>As we have a <strong>3 bit tag</strong>, leaving <strong>32 - 3 = 29 bits</strong> for the actual address. This means, our actual available addresses, written in binary are of the form</p>
<table>
<thead>
<tr class="header">
<th style="text-align: right;">Binary</th>
<th style="text-align: right;">Decimal</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: right;">0b00000000</td>
<td style="text-align: right;">0</td>
</tr>
<tr class="even">
<td style="text-align: right;">0b00001000</td>
<td style="text-align: right;">8</td>
</tr>
<tr class="odd">
<td style="text-align: right;">0b00010000</td>
<td style="text-align: right;">16</td>
</tr>
<tr class="even">
<td style="text-align: right;">0b00011000</td>
<td style="text-align: right;">24</td>
</tr>
<tr class="odd">
<td style="text-align: right;">0b00100000</td>
<td style="text-align: right;">32</td>
</tr>
<tr class="even">
<td style="text-align: right;">…</td>
<td style="text-align: right;"></td>
</tr>
</tbody>
</table>
<p>That is, the addresses are <strong>8-byte aligned</strong>. Which is great because at each address, we have a pair, i.e. a <strong>2-word = 8-byte block</strong>, so the <em>next</em> allocated address will also fall on an 8-byte boundary.</p>
<h3 id="construction">2. Construction</h3>
<p>Next, lets look at how to implement pair <strong>construction</strong> that is, generate the assembly for expressions like:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb5-1" data-line-number="1">(e1, e2)</a></code></pre></div>
<p>To <strong>construct</strong> a pair <code>(e1, e2)</code> we</p>
<ol type="1">
<li><strong>Allocate</strong> a new 2-word block, and getting the starting address at <code>eax</code>,</li>
<li><strong>Copy</strong> the value of <code>e1</code> (resp. <code>e2</code>) into <code>[eax]</code> (resp. <code>[eax + 4]</code>).</li>
<li><strong>Tag</strong> the last bit of <code>eax</code> with <code>1</code>.</li>
</ol>
<p>The resulting <code>eax</code> is the <strong>value of the pair</strong></p>
<ul>
<li>The last step ensures that the value carries the proper tag.</li>
</ul>
<p>ANF will ensure that <code>e1</code> and <code>e2</code> are both <a href="04-boa.md/#idea-immediate-expressions">immediate expressions</a> which will make the second step above straightforward.</p>
<p><strong>EXERCISE</strong> How will we do ANF conversion for <code>(e1, e2)</code>?</p>
<h3 id="allocating-addresses">Allocating Addresses</h3>
<p>We will use a <strong>global</strong> register <code>esi</code> to maintain the address of the <strong>next free block</strong> on the heap. Every time we need a new block, we will:</p>
<ol type="1">
<li><strong>Copy</strong> the current <code>esi</code> into <code>eax</code></li>
</ol>
<ul>
<li>set the last bit to <code>1</code> to ensure proper tagging.</li>
<li><code>eax</code> will be used to fill in the values</li>
</ul>
<ol start="2" type="1">
<li><strong>Increment</strong> the value of <code>esi</code> by <code>8</code></li>
</ol>
<ul>
<li>thereby "allocating" 8 bytes (= 2 words) at the address in <code>eax</code></li>
</ul>
<p>Note that <em>if</em></p>
<ul>
<li>we <em>start</em> our blocks at an 8-byte boundary, and</li>
<li>we <em>allocate</em> 8 bytes at a time,</li>
</ul>
<p><em>then</em></p>
<ul>
<li>each address used to store a pair will fall on an 8-byte boundary (i.e. have last three bits set to <code>0</code>).</li>
</ul>
<p>So we can safely turn the address in <code>eax</code> into a <code>pointer</code> + by setting the last bit to <code>1</code>.</p>
<p><strong>NOTE:</strong> In your assignment, we will have blocks of varying sizes so you will have to take care to <em>maintain</em> the 8-byte alignment, by "padding".</p>
<h3 id="example-allocation">Example: Allocation</h3>
<p>In the figure below, we have</p>
<ul>
<li>a source program on the left,</li>
<li>the ANF equivalent next to it.</li>
</ul>
<figure>
<img src="../static/img/example-pair-code.png" alt="Example of Pairs" /><figcaption>Example of Pairs</figcaption>
</figure>
<p>The figure below shows the how the heap and <code>esi</code> evolve at points 1, 2 and 3:</p>
<figure>
<img src="../static/img/example-pair-heaps.png" alt="Allocating Pairs on the Heap" /><figcaption>Allocating Pairs on the Heap</figcaption>
</figure>
<p><strong>QUIZ</strong></p>
<p>In the ANF version, <code>p</code> is the <em>second (local) variable</em> stored in the stack frame. What <em>value</em> gets moved into the <em>second stack slot</em> when evaluating the above program?</p>
<ol type="1">
<li><code>0x3</code></li>
<li><code>(3, (4, 5))</code></li>
<li><code>0x6</code></li>
<li><code>0x9</code></li>
<li><code>0x10</code></li>
</ol>
<h3 id="accessing">3. Accessing</h3>
<p>Finally, to <strong>access</strong> the elements of a pair, i.e. compiling expressions like <code>e[0]</code> (resp. <code>e[1]</code>)</p>
<ol type="1">
<li><strong>Check</strong> that immediate value <code>e</code> is a pointer</li>
<li><strong>Load</strong> <code>e</code> into <code>eax</code></li>
<li><strong>Remove</strong> the tag bit from <code>eax</code></li>
<li><strong>Copy</strong> the value in <code>[eax]</code> (resp. <code>[eax + 4]</code>) into <code>eax</code>.</li>
</ol>
<h3 id="example-access">Example: Access</h3>
<p>Here is a snapshot of the heap after the pair(s) are allocated.</p>
<figure>
<img src="../static/img/example-pair-heap.png" alt="Allocating Pairs on the Heap" /><figcaption>Allocating Pairs on the Heap</figcaption>
</figure>
<p>Lets work out how the values corresponding to <code>x</code>, <code>y</code> and <code>z</code> in the example above get stored on the stack frame in the course of evaluation.</p>
<table>
<thead>
<tr class="header">
<th style="text-align: right;">Variable</th>
<th style="text-align: right;">Hex Value</th>
<th style="text-align: right;">Value</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td style="text-align: right;"><code>anf0</code></td>
<td style="text-align: right;"><code>0x001</code></td>
<td style="text-align: right;"><code>ptr 0</code></td>
</tr>
<tr class="even">
<td style="text-align: right;"><code>p</code></td>
<td style="text-align: right;"><code>0x009</code></td>
<td style="text-align: right;"><code>ptr 8</code></td>
</tr>
<tr class="odd">
<td style="text-align: right;"><code>x</code></td>
<td style="text-align: right;"><code>0x006</code></td>
<td style="text-align: right;"><code>num 3</code></td>
</tr>
<tr class="even">
<td style="text-align: right;"><code>anf1</code></td>
<td style="text-align: right;"><code>0x001</code></td>
<td style="text-align: right;"><code>ptr 0</code></td>
</tr>
<tr class="odd">
<td style="text-align: right;"><code>y</code></td>
<td style="text-align: right;"><code>0x008</code></td>
<td style="text-align: right;"><code>num 4</code></td>
</tr>
<tr class="even">
<td style="text-align: right;"><code>z</code></td>
<td style="text-align: right;"><code>0x00A</code></td>
<td style="text-align: right;"><code>num 5</code></td>
</tr>
<tr class="odd">
<td style="text-align: right;"><code>anf2</code></td>
<td style="text-align: right;"><code>0x00E</code></td>
<td style="text-align: right;"><code>num 7</code></td>
</tr>
<tr class="even">
<td style="text-align: right;">result</td>
<td style="text-align: right;"><code>0x018</code></td>
<td style="text-align: right;"><code>num 12</code></td>
</tr>
</tbody>
</table>
<h2 id="plan">Plan</h2>
<p>Pretty pictures are well and good, time to build stuff!</p>
<p>As usual, lets continue with our recipe:</p>
<ol type="1">
<li>Run-time</li>
<li>Types</li>
<li>Transforms</li>
</ol>
<p>We've already built up intuition of the <em>strategy</em> for implementing tuples. Next, lets look at how to implement each of the above.</p>
<h2 id="run-time">Run-Time</h2>
<p>We need to extend the run-time (<code>c-bits/main.c</code>) in two ways.</p>
<ol type="1">
<li><p><strong>Allocate</strong> a chunk of space on the heap and pass in start address to <code>our_code</code>.</p></li>
<li><p><strong>Print</strong> pairs properly.</p></li>
</ol>
<h3 id="allocation">Allocation</h3>
<p>The first step is quite easy we can use <code>calloc</code> as follows:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode c"><code class="sourceCode c"><a class="sourceLine" id="cb6-1" data-line-number="1"><span class="dt">int</span> main(<span class="dt">int</span> argc, <span class="dt">char</span>** argv) {</a>
<a class="sourceLine" id="cb6-2" data-line-number="2">  <span class="dt">int</span>* HEAP = calloc(HEAP_SIZE, <span class="kw">sizeof</span> (<span class="dt">int</span>));</a>
<a class="sourceLine" id="cb6-3" data-line-number="3">  <span class="dt">int</span> result = our_code_starts_here(HEAP);</a>
<a class="sourceLine" id="cb6-4" data-line-number="4">  print(result);</a>
<a class="sourceLine" id="cb6-5" data-line-number="5">  <span class="cf">return</span> <span class="dv">0</span>;</a>
<a class="sourceLine" id="cb6-6" data-line-number="6">}</a></code></pre></div>
<p>The above code,</p>
<ol type="1">
<li><strong>Allocates</strong> a big block of contiguous memory (starting at <code>HEAP</code>), and</li>
<li><strong>Passes</strong> this address in to <code>our_code</code>.</li>
</ol>
<p>Now, <code>our_code</code> needs to, at the beginning start with instructions that will copy the parameter into <code>esi</code> and then bump it up at each allocation.</p>
<h3 id="printing">Printing</h3>
<p>To print pairs, we must recursively traverse the pointers until we hit <code>number</code> or <code>boolean</code>.</p>
<p>We can check if a value is a pair by looking at its last 3 bits:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode c"><code class="sourceCode c"><a class="sourceLine" id="cb7-1" data-line-number="1"><span class="dt">int</span> isPair(<span class="dt">int</span> p) {</a>
<a class="sourceLine" id="cb7-2" data-line-number="2">  <span class="cf">return</span> (p &amp; <span class="bn">0x00000007</span>) == <span class="bn">0x00000001</span>;</a>
<a class="sourceLine" id="cb7-3" data-line-number="3">}</a></code></pre></div>
<p>We can use the above test to recursively print (word)-values:</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode c"><code class="sourceCode c"><a class="sourceLine" id="cb8-1" data-line-number="1"><span class="dt">void</span> print(<span class="dt">int</span> val) {</a>
<a class="sourceLine" id="cb8-2" data-line-number="2">  <span class="cf">if</span>(val &amp; <span class="bn">0x00000001</span> ^ <span class="bn">0x00000001</span>) { <span class="co">// val is a number</span></a>
<a class="sourceLine" id="cb8-3" data-line-number="3">    printf(<span class="st">&quot;%d&quot;</span>, val &gt;&gt; <span class="dv">1</span>);</a>
<a class="sourceLine" id="cb8-4" data-line-number="4">  }</a>
<a class="sourceLine" id="cb8-5" data-line-number="5">  <span class="cf">else</span> <span class="cf">if</span>(val == <span class="bn">0xFFFFFFFF</span>) {       <span class="co">// val is true</span></a>
<a class="sourceLine" id="cb8-6" data-line-number="6">    printf(<span class="st">&quot;true&quot;</span>);</a>
<a class="sourceLine" id="cb8-7" data-line-number="7">  }</a>
<a class="sourceLine" id="cb8-8" data-line-number="8">  <span class="cf">else</span> <span class="cf">if</span>(val == <span class="bn">0x7FFFFFFF</span>) {       <span class="co">// val is false</span></a>
<a class="sourceLine" id="cb8-9" data-line-number="9">    printf(<span class="st">&quot;false&quot;</span>);</a>
<a class="sourceLine" id="cb8-10" data-line-number="10">  }</a>
<a class="sourceLine" id="cb8-11" data-line-number="11">  <span class="cf">else</span> <span class="cf">if</span>(isPair(val)) {            </a>
<a class="sourceLine" id="cb8-12" data-line-number="12">    <span class="dt">int</span>* valp = (<span class="dt">int</span>*) (val - <span class="dv">1</span>);    <span class="co">// extract address  </span></a>
<a class="sourceLine" id="cb8-13" data-line-number="13">    printf(<span class="st">&quot;(&quot;</span>);</a>
<a class="sourceLine" id="cb8-14" data-line-number="14">    print(*valp);                 <span class="co">// print first element</span></a>
<a class="sourceLine" id="cb8-15" data-line-number="15">    printf(<span class="st">&quot;, &quot;</span>);</a>
<a class="sourceLine" id="cb8-16" data-line-number="16">    print(*(valp + <span class="dv">1</span>));           <span class="co">// print second element</span></a>
<a class="sourceLine" id="cb8-17" data-line-number="17">    printf(<span class="st">&quot;)&quot;</span>);</a>
<a class="sourceLine" id="cb8-18" data-line-number="18">  }</a>
<a class="sourceLine" id="cb8-19" data-line-number="19">  <span class="cf">else</span> {</a>
<a class="sourceLine" id="cb8-20" data-line-number="20">    printf(<span class="st">&quot;Unknown value: %#010x&quot;</span>, val);</a>
<a class="sourceLine" id="cb8-21" data-line-number="21">  }</a>
<a class="sourceLine" id="cb8-22" data-line-number="22">}</a></code></pre></div>
<h2 id="types">Types</h2>
<p>Next, lets move into our compiler, and see how the <strong>core types</strong> need to be extended.</p>
<h3 id="source">Source</h3>
<p>We need to extend the <em>source</em> <code>Expr</code> with support for tuples</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb9-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Expr</span> a</a>
<a class="sourceLine" id="cb9-2" data-line-number="2">  <span class="fu">=</span> <span class="fu">...</span></a>
<a class="sourceLine" id="cb9-3" data-line-number="3">  <span class="fu">|</span> <span class="dt">Pair</span>    (<span class="dt">Expr</span> a) (<span class="dt">Expr</span> a) a   <span class="co">-- ^ construct a pair</span></a>
<a class="sourceLine" id="cb9-4" data-line-number="4">  <span class="fu">|</span> <span class="dt">GetItem</span> (<span class="dt">Expr</span> a) <span class="dt">Field</span>    a   <span class="co">-- ^ access a pair's element</span></a></code></pre></div>
<p>In the above, <code>Field</code> is</p>
<div class="sourceCode" id="cb10"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb10-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Field</span></a>
<a class="sourceLine" id="cb10-2" data-line-number="2">  <span class="fu">=</span> <span class="dt">First</span>     <span class="co">-- ^ access first element of pair</span></a>
<a class="sourceLine" id="cb10-3" data-line-number="3">  <span class="fu">|</span> <span class="dt">Second</span>    <span class="co">-- ^ access second element of pair</span></a></code></pre></div>
<p><strong>NOTE:</strong> Your assignment will generalize pairs to <strong>n-ary tuples</strong> using</p>
<ul>
<li><code>Tuple [Expr a]</code> representing <code>(e1,...,en)</code></li>
<li><code>GetItem (Expr a) (Expr a)</code> representing <code>e1[e2]</code></li>
</ul>
<h3 id="dynamic-types">Dynamic Types</h3>
<p>Let us extend our <strong>dynamic types</strong> <code>Ty</code> <a href="05-cobra.md/#types">see</a> to include pairs:</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb11-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Ty</span> <span class="fu">=</span> <span class="dt">TNumber</span> <span class="fu">|</span> <span class="dt">TBoolean</span> <span class="fu">|</span> <span class="dt">TPair</span></a></code></pre></div>
<h3 id="assembly">Assembly</h3>
<p>The assembly <code>Instruction</code> are changed minimally; we just need access to <code>esi</code> which will hold the value of the <em>next</em> available memory block:</p>
<div class="sourceCode" id="cb12"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb12-1" data-line-number="1"><span class="kw">data</span> <span class="dt">Register</span></a>
<a class="sourceLine" id="cb12-2" data-line-number="2">  <span class="fu">=</span> <span class="fu">...</span></a>
<a class="sourceLine" id="cb12-3" data-line-number="3">  <span class="fu">|</span> <span class="dt">ESI</span></a></code></pre></div>
<h2 id="transforms">Transforms</h2>
<p>Our code must take care of three things:</p>
<ol type="1">
<li><strong>Initialize</strong> <code>esi</code> to allow heap allocation,</li>
<li><strong>Construct</strong> pairs,</li>
<li><strong>Access</strong> pairs.</li>
</ol>
<p>The latter two will be pointed out directly by GHC * They are new cases that must be handled in <code>anf</code> and <code>compileExpr</code></p>
<h3 id="initialize">Initialize</h3>
<p>We need to <strong>initialize</strong> <code>esi</code> with the <strong>start position</strong> of the heap, that is <a href="#fixme">passed in by the run-time</a>.</p>
<p>How shall we get a hold of this position?</p>
<p>To do so, <code>our_code</code> starts off with a <code>prelude</code></p>
<div class="sourceCode" id="cb13"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb13-1" data-line-number="1"><span class="ot">prelude ::</span> [<span class="dt">Instruction</span>]</a>
<a class="sourceLine" id="cb13-2" data-line-number="2">prelude <span class="fu">=</span></a>
<a class="sourceLine" id="cb13-3" data-line-number="3">  [ <span class="dt">IMov</span> (<span class="dt">Reg</span> <span class="dt">ESI</span>) (<span class="dt">RegOffset</span> <span class="dv">4</span> <span class="dt">ESP</span>)        <span class="co">-- copy param (HEAP) off stack</span></a>
<a class="sourceLine" id="cb13-4" data-line-number="4">  , <span class="dt">IAdd</span> (<span class="dt">Reg</span> <span class="dt">ESI</span>) (<span class="dt">Const</span> <span class="dv">8</span>)                <span class="co">-- adjust to ensure 8-byte aligned</span></a>
<a class="sourceLine" id="cb13-5" data-line-number="5">  , <span class="dt">IAnd</span> (<span class="dt">Reg</span> <span class="dt">ESI</span>) (<span class="dt">HexConst</span> <span class="bn">0xFFFFFFF8</span>)    <span class="co">-- add 8 and set last 3 bits to 0</span></a>
<a class="sourceLine" id="cb13-6" data-line-number="6">  ]</a></code></pre></div>
<ol type="1">
<li><strong>Copy</strong> the value off the (parameter) stack, and</li>
<li><strong>Adjust</strong> the value to ensure the value is <em>8-byte aligned</em>.</li>
</ol>
<p><strong>QUIZ</strong></p>
<p>Why add <code>8</code> to <code>esi</code>? What would happen if we <em>removed</em> that operation?</p>
<ol type="1">
<li><code>esi</code> would not be 8-byte aligned?</li>
<li><code>esi</code> would point into the stack?</li>
<li><code>esi</code> would not point into the heap?</li>
<li><code>esi</code> would not have enough space to write 2 bytes?</li>
</ol>
<h3 id="construct">Construct</h3>
<p>To <em>construct</em> a pair <code>(v1, v2)</code> we directly implement the <a href="07-egg-eater.md/#2-construction">above strategy</a>:</p>
<div class="sourceCode" id="cb14"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb14-1" data-line-number="1">compileExpr env (<span class="dt">Pair</span> v1 v2)</a>
<a class="sourceLine" id="cb14-2" data-line-number="2">  <span class="fu">=</span> pairAlloc                        <span class="co">-- 1. allocate pair, resulting addr in `eax`</span></a>
<a class="sourceLine" id="cb14-3" data-line-number="3"> <span class="fu">++</span> pairCopy <span class="dt">First</span>  (immArg env v1)  <span class="co">-- 2. copy values into slots</span></a>
<a class="sourceLine" id="cb14-4" data-line-number="4"> <span class="fu">++</span> pairCopy <span class="dt">Second</span> (immArg env v2)  </a>
<a class="sourceLine" id="cb14-5" data-line-number="5"> <span class="fu">++</span> setTag   <span class="dt">EAX</span>     <span class="dt">TPair</span>           <span class="co">-- 3. set the tag-bits of `eax`</span></a></code></pre></div>
<p>Lets look at each step in turn.</p>
<h4 id="allocate">Allocate</h4>
<p>To allocate, we just copy the current pointer <code>esi</code> and increment by <code>8</code> bytes,</p>
<ul>
<li>accounting for two 4-byte (word) blocks for each pair element.</li>
</ul>
<div class="sourceCode" id="cb15"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb15-1" data-line-number="1"><span class="ot">pairAlloc ::</span> <span class="dt">Asm</span></a>
<a class="sourceLine" id="cb15-2" data-line-number="2">pairAlloc</a>
<a class="sourceLine" id="cb15-3" data-line-number="3">  <span class="fu">=</span> [ <span class="dt">IMov</span> (<span class="dt">Reg</span> <span class="dt">EAX</span>) (<span class="dt">Reg</span> <span class="dt">ESI</span>)   <span class="co">-- copy current &quot;free address&quot; `esi` into `eax`</span></a>
<a class="sourceLine" id="cb15-4" data-line-number="4">    , <span class="dt">IAdd</span> (<span class="dt">Reg</span> <span class="dt">ESI</span>) (<span class="dt">Const</span> <span class="dv">8</span>)   <span class="co">-- increment `esi` by 8</span></a>
<a class="sourceLine" id="cb15-5" data-line-number="5">    ]</a></code></pre></div>
<h4 id="copy">Copy</h4>
<p>We copy an <code>Arg</code> into a <code>Field</code> by * saving the <code>Arg</code> into a helper register <code>ebx</code>, * copying <code>ebx</code> into the field's slot on the heap.</p>
<div class="sourceCode" id="cb16"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb16-1" data-line-number="1"><span class="ot">pairCopy ::</span> <span class="dt">Field</span> <span class="ot">-&gt;</span> <span class="dt">Arg</span> <span class="ot">-&gt;</span> <span class="dt">Asm</span></a>
<a class="sourceLine" id="cb16-2" data-line-number="2">pairCopy fld a</a>
<a class="sourceLine" id="cb16-3" data-line-number="3">  <span class="fu">=</span> [ <span class="dt">IMov</span> (<span class="dt">Reg</span> <span class="dt">EBX</span>)    a</a>
<a class="sourceLine" id="cb16-4" data-line-number="4">    , <span class="dt">IMov</span> (pairAddr f) (<span class="dt">Reg</span> <span class="dt">EBX</span>)</a>
<a class="sourceLine" id="cb16-5" data-line-number="5">    ]</a></code></pre></div>
<p>The field's slot is either <code>[eax]</code> or <code>[eax + 4]</code> depending on whether the field is <code>First</code> or <code>Second</code>.</p>
<div class="sourceCode" id="cb17"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb17-1" data-line-number="1"><span class="ot">pairAddr ::</span> <span class="dt">Field</span> <span class="ot">-&gt;</span> <span class="dt">Arg</span></a>
<a class="sourceLine" id="cb17-2" data-line-number="2">pairAddr fld <span class="fu">=</span> <span class="dt">Sized</span> <span class="dt">DWordPtr</span> (<span class="dt">RegOffset</span> (<span class="dv">4</span> <span class="fu">*</span> fieldOffset fld) <span class="dt">EAX</span>)</a>
<a class="sourceLine" id="cb17-3" data-line-number="3"></a>
<a class="sourceLine" id="cb17-4" data-line-number="4"><span class="ot">fieldOffset ::</span> <span class="dt">Field</span> <span class="ot">-&gt;</span> <span class="dt">Int</span></a>
<a class="sourceLine" id="cb17-5" data-line-number="5">fieldOffset <span class="dt">First</span>  <span class="fu">=</span> <span class="dv">0</span></a>
<a class="sourceLine" id="cb17-6" data-line-number="6">fieldOffset <span class="dt">Second</span> <span class="fu">=</span> <span class="dv">1</span></a></code></pre></div>
<h4 id="tag">Tag</h4>
<p>Finally, we set the tag bits of <code>eax</code> by using <code>typeTag TPair</code> which is defined</p>
<div class="sourceCode" id="cb18"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb18-1" data-line-number="1"><span class="ot">setTag ::</span> <span class="dt">Register</span> <span class="ot">-&gt;</span> <span class="dt">Ty</span> <span class="ot">-&gt;</span> <span class="dt">Asm</span></a>
<a class="sourceLine" id="cb18-2" data-line-number="2">setTag r ty <span class="fu">=</span> [ <span class="dt">IAdd</span> (<span class="dt">Reg</span> r) (typeTag ty) ]</a>
<a class="sourceLine" id="cb18-3" data-line-number="3"></a>
<a class="sourceLine" id="cb18-4" data-line-number="4"><span class="ot">typeTag ::</span> <span class="dt">Ty</span> <span class="ot">-&gt;</span> <span class="dt">Arg</span></a>
<a class="sourceLine" id="cb18-5" data-line-number="5">typeTag <span class="dt">TNumber</span>  <span class="fu">=</span> <span class="dt">HexConst</span> <span class="bn">0x00000000</span>    <span class="co">-- last 1 bit  is  0</span></a>
<a class="sourceLine" id="cb18-6" data-line-number="6">typeTag <span class="dt">TBoolean</span> <span class="fu">=</span> <span class="dt">HexConst</span> <span class="bn">0x00000007</span>    <span class="co">-- last 3 bits are 111</span></a>
<a class="sourceLine" id="cb18-7" data-line-number="7">typeTag <span class="dt">TPair</span>    <span class="fu">=</span> <span class="dt">HexConst</span> <span class="bn">0x00000001</span>    <span class="co">-- last 1 bits is  1</span></a></code></pre></div>
<h3 id="access">Access</h3>
<p>To access tuples, lets update <code>compileExpr</code> with the <a href="#3-accessing">strategy above</a>:</p>
<div class="sourceCode" id="cb19"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb19-1" data-line-number="1">compileExpr env (<span class="dt">GetItem</span> e fld)</a>
<a class="sourceLine" id="cb19-2" data-line-number="2">  <span class="fu">=</span> assertType env e <span class="dt">TPair</span>              <span class="co">-- 1. check that e is a (pair) pointer</span></a>
<a class="sourceLine" id="cb19-3" data-line-number="3"> <span class="fu">++</span> [ <span class="dt">IMov</span> (<span class="dt">Reg</span> <span class="dt">EAX</span>) (immArg env e) ]   <span class="co">-- 2. load pointer into eax</span></a>
<a class="sourceLine" id="cb19-4" data-line-number="4"> <span class="fu">++</span> unsetTag <span class="dt">EAX</span> <span class="dt">TPair</span>                  <span class="co">-- 3. remove tag bit to get address</span></a>
<a class="sourceLine" id="cb19-5" data-line-number="5"> <span class="fu">++</span> [ <span class="dt">IMov</span> (<span class="dt">Reg</span> <span class="dt">EAX</span>) (pairAddr fld) ]   <span class="co">-- 4. copy value from resp. slot to eax</span></a></code></pre></div>
<p>we remove the tag bits by doing the opposite of <code>setTag</code> namely:</p>
<div class="sourceCode" id="cb20"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb20-1" data-line-number="1"><span class="ot">unsetTag ::</span> <span class="dt">Register</span> <span class="ot">-&gt;</span> <span class="dt">Ty</span> <span class="ot">-&gt;</span> <span class="dt">Asm</span></a>
<a class="sourceLine" id="cb20-2" data-line-number="2">unsetTag r ty <span class="fu">=</span> <span class="dt">ISub</span> (<span class="dt">Reg</span> <span class="dt">EAX</span>) (typeTag ty)</a></code></pre></div>
<h2 id="n-ary-tuples">N-ary Tuples</h2>
<p>Thats it! Lets take our compiler out for a spin, by using it to write some interesting programs!</p>
<p>First, lets see how to generalize pairs to allow for</p>
<ul>
<li>triples <code>(e1,e2,e3)</code>, —&gt; (e1, (e2, e3))</li>
<li>quadruples <code>(e1,e2,e3,e4)</code>, –&gt; (e1, (e2, (e3, e4)))</li>
<li>pentuples <code>(e1,e2,e3,e4,e5)</code></li>
</ul>
<p>and so on.</p>
<p>We just need a library of functions in our new <code>egg</code> language to</p>
<ul>
<li><strong>Construct</strong> such tuples, and</li>
<li><strong>Access</strong> their fields.</li>
</ul>
<h3 id="constructing-tuples">Constructing Tuples</h3>
<p>We can write a small set of functions to <strong>construct</strong> tuples (upto some given size):</p>
<div class="sourceCode" id="cb21"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb21-1" data-line-number="1"><span class="kw">def</span> tup3(x1, x2, x3):</a>
<a class="sourceLine" id="cb21-2" data-line-number="2">  (x1, (x2, x3))</a>
<a class="sourceLine" id="cb21-3" data-line-number="3"></a>
<a class="sourceLine" id="cb21-4" data-line-number="4"><span class="kw">def</span> tup4(x1, x2, x3, x4):</a>
<a class="sourceLine" id="cb21-5" data-line-number="5">  (x1, (x2, (x3, x4)))</a>
<a class="sourceLine" id="cb21-6" data-line-number="6"></a>
<a class="sourceLine" id="cb21-7" data-line-number="7"><span class="kw">def</span> tup5(x1, x2, x3, x4, x5):</a>
<a class="sourceLine" id="cb21-8" data-line-number="8">  (x1, (x2, (x3, (x4, x5))))</a></code></pre></div>
<h3 id="accessing-tuples">Accessing Tuples</h3>
<p>We can write a single function to access tuples of any size.</p>
<p>So the below code</p>
<div class="sourceCode" id="cb22"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb22-1" data-line-number="1">let yuple <span class="op">=</span> (<span class="dv">10</span>, (<span class="dv">20</span>, (<span class="dv">30</span>, (<span class="dv">40</span>, (<span class="dv">50</span>, false))))) <span class="kw">in</span> </a>
<a class="sourceLine" id="cb22-2" data-line-number="2"></a>
<a class="sourceLine" id="cb22-3" data-line-number="3">get(yuple, <span class="dv">0</span>) <span class="op">=</span> <span class="dv">10</span></a>
<a class="sourceLine" id="cb22-4" data-line-number="4">get(yuple, <span class="dv">1</span>) <span class="op">=</span> <span class="dv">20</span></a>
<a class="sourceLine" id="cb22-5" data-line-number="5">get(yuple, <span class="dv">2</span>) <span class="op">=</span> <span class="dv">30</span></a>
<a class="sourceLine" id="cb22-6" data-line-number="6">get(yuple, <span class="dv">3</span>) <span class="op">=</span> <span class="dv">40</span></a>
<a class="sourceLine" id="cb22-7" data-line-number="7">get(yuple, <span class="dv">4</span>) <span class="op">=</span> <span class="dv">50</span></a>
<a class="sourceLine" id="cb22-8" data-line-number="8"></a>
<a class="sourceLine" id="cb22-9" data-line-number="9"></a>
<a class="sourceLine" id="cb22-10" data-line-number="10"></a>
<a class="sourceLine" id="cb22-11" data-line-number="11"></a>
<a class="sourceLine" id="cb22-12" data-line-number="12"><span class="kw">def</span> tup3(x1, x2, x3):</a>
<a class="sourceLine" id="cb22-13" data-line-number="13">  (x1, (x2, x3))</a>
<a class="sourceLine" id="cb22-14" data-line-number="14"></a>
<a class="sourceLine" id="cb22-15" data-line-number="15"><span class="kw">def</span> tup5(x1, x2, x3, x4, x5):</a>
<a class="sourceLine" id="cb22-16" data-line-number="16">  (x1, (x2, (x3, (x4, x5))))</a>
<a class="sourceLine" id="cb22-17" data-line-number="17"></a>
<a class="sourceLine" id="cb22-18" data-line-number="18">let t  <span class="op">=</span> tup5(<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>, <span class="dv">5</span>) <span class="kw">in</span></a>
<a class="sourceLine" id="cb22-19" data-line-number="19">  , x0 <span class="op">=</span> <span class="bu">print</span>(get(t, <span class="dv">0</span>))</a>
<a class="sourceLine" id="cb22-20" data-line-number="20">  , x1 <span class="op">=</span> <span class="bu">print</span>(get(t, <span class="dv">1</span>))</a>
<a class="sourceLine" id="cb22-21" data-line-number="21">  , x2 <span class="op">=</span> <span class="bu">print</span>(get(t, <span class="dv">2</span>))</a>
<a class="sourceLine" id="cb22-22" data-line-number="22">  , x3 <span class="op">=</span> <span class="bu">print</span>(get(t, <span class="dv">3</span>))</a>
<a class="sourceLine" id="cb22-23" data-line-number="23">  , x4 <span class="op">=</span> <span class="bu">print</span>(get(t, <span class="dv">4</span>))</a>
<a class="sourceLine" id="cb22-24" data-line-number="24"><span class="kw">in</span></a>
<a class="sourceLine" id="cb22-25" data-line-number="25">  <span class="dv">99</span></a></code></pre></div>
<p>should print out:</p>
<pre><code>0
1
2
3
4
99</code></pre>
<p>How shall we write it?</p>
<div class="sourceCode" id="cb24"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb24-1" data-line-number="1"><span class="kw">def</span> get(t, i):</a>
<a class="sourceLine" id="cb24-2" data-line-number="2">  TODO<span class="op">-</span>IN<span class="op">-</span>CLASS</a></code></pre></div>
<h3 id="quiz">QUIZ</h3>
<p>Using the above "library" we can write code like:</p>
<div class="sourceCode" id="cb25"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb25-1" data-line-number="1"><span class="kw">let</span> quad <span class="fu">=</span> tup4(<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>) <span class="kw">in</span></a>
<a class="sourceLine" id="cb25-2" data-line-number="2">  get(quad, <span class="dv">0</span>) <span class="fu">+</span> get(quad, <span class="dv">1</span>) <span class="fu">+</span> get(quad, <span class="dv">2</span>) <span class="fu">+</span> get(quad, <span class="dv">3</span>)</a></code></pre></div>
<p>What will be the result of compiling the above?</p>
<ol type="1">
<li>Compile error</li>
<li>Segmentation fault</li>
<li>Other run-time error</li>
<li><code>4</code></li>
<li><code>10</code></li>
</ol>
<h3 id="quiz-1">QUIZ</h3>
<p>Using the above "library" we can write code like:</p>
<div class="sourceCode" id="cb26"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb26-1" data-line-number="1"></a>
<a class="sourceLine" id="cb26-2" data-line-number="2"></a>
<a class="sourceLine" id="cb26-3" data-line-number="3">def get(t, i)<span class="fu">:</span></a>
<a class="sourceLine" id="cb26-4" data-line-number="4">  <span class="kw">if</span> i <span class="fu">==</span> <span class="dv">0</span><span class="fu">:</span></a>
<a class="sourceLine" id="cb26-5" data-line-number="5">    t[<span class="dv">0</span>]</a>
<a class="sourceLine" id="cb26-6" data-line-number="6">  <span class="kw">else</span><span class="fu">:</span></a>
<a class="sourceLine" id="cb26-7" data-line-number="7">    get(t[<span class="dv">1</span>],i<span class="fu">-</span><span class="dv">1</span>)</a>
<a class="sourceLine" id="cb26-8" data-line-number="8"></a>
<a class="sourceLine" id="cb26-9" data-line-number="9">get(t, <span class="dv">2</span>) <span class="fu">===&gt;</span> get(t[<span class="dv">1</span>], <span class="dv">1</span>) <span class="fu">===&gt;</span> get(t[<span class="dv">1</span>][<span class="dv">1</span>], <span class="dv">0</span>)</a>
<a class="sourceLine" id="cb26-10" data-line-number="10"></a>
<a class="sourceLine" id="cb26-11" data-line-number="11"></a>
<a class="sourceLine" id="cb26-12" data-line-number="12">def tup3(x1, x2, x3)<span class="fu">:</span></a>
<a class="sourceLine" id="cb26-13" data-line-number="13">  (x1, (x2, (x3, false)))</a>
<a class="sourceLine" id="cb26-14" data-line-number="14"></a>
<a class="sourceLine" id="cb26-15" data-line-number="15"><span class="kw">let</span> quad <span class="fu">=</span> tup3(<span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>) <span class="kw">in</span></a>
<a class="sourceLine" id="cb26-16" data-line-number="16">  quad <span class="fu">=</span> (<span class="dv">1</span>, (<span class="dv">2</span>, <span class="dv">3</span>))</a>
<a class="sourceLine" id="cb26-17" data-line-number="17">  quad[<span class="dv">1</span>] <span class="fu">=</span> (<span class="dv">2</span>, <span class="dv">3</span>)</a>
<a class="sourceLine" id="cb26-18" data-line-number="18">  quad[<span class="dv">1</span>][<span class="dv">1</span>] <span class="fu">=</span> (<span class="dv">3</span>, false)</a>
<a class="sourceLine" id="cb26-19" data-line-number="19">  quad[<span class="dv">1</span>][<span class="dv">1</span>][<span class="dv">1</span>] <span class="fu">=</span> false</a>
<a class="sourceLine" id="cb26-20" data-line-number="20"></a>
<a class="sourceLine" id="cb26-21" data-line-number="21">  get(quad, <span class="dv">0</span>) <span class="fu">+</span> get(quad, <span class="dv">1</span>) <span class="fu">+</span> get(quad, <span class="dv">2</span>) <span class="fu">+</span> get(quad, <span class="dv">3</span>)</a></code></pre></div>
<p>What will be the result of compiling the above?</p>
<ol type="1">
<li>Compile error</li>
<li>Segmentation fault</li>
<li>Other run-time error</li>
<li><code>4</code></li>
<li><code>10</code></li>
</ol>
<h2 id="lists">Lists</h2>
<p>Once we have pairs, we can start encoding <strong>unbounded lists</strong>.</p>
<h3 id="construct-1">Construct</h3>
<p>To build a list, we need two constructor functions:</p>
<p>```python def empty(): false</p>
<p>def cons(h, t): (h, t) ``</p>
<p>We can now encode lists as:</p>
<div class="sourceCode" id="cb27"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb27-1" data-line-number="1">cons(<span class="dv">1</span>, cons(<span class="dv">2</span>, cons(<span class="dv">3</span>, cons(<span class="dv">4</span>, empty()))))</a></code></pre></div>
<h3 id="access-1">Access</h3>
<p>To <strong>access</strong> a list, we need to know</p>
<ol type="1">
<li>Whether the list <code>isEmpty</code>, and</li>
<li>A way to access the <code>head</code> and the <code>tail</code> of a non-empty list.</li>
</ol>
<div class="sourceCode" id="cb28"><pre class="sourceCode haskell"><code class="sourceCode haskell"><a class="sourceLine" id="cb28-1" data-line-number="1">def isEmpty(l)<span class="fu">:</span></a>
<a class="sourceLine" id="cb28-2" data-line-number="2">  l <span class="fu">==</span> empty()</a>
<a class="sourceLine" id="cb28-3" data-line-number="3"></a>
<a class="sourceLine" id="cb28-4" data-line-number="4">def head(l)<span class="fu">:</span></a>
<a class="sourceLine" id="cb28-5" data-line-number="5">  l[<span class="dv">0</span>]</a>
<a class="sourceLine" id="cb28-6" data-line-number="6"></a>
<a class="sourceLine" id="cb28-7" data-line-number="7">def tail(l)<span class="fu">:</span></a>
<a class="sourceLine" id="cb28-8" data-line-number="8">  l[<span class="dv">1</span>]</a></code></pre></div>
<h3 id="examples">Examples</h3>
<p>We can now write various functions that build and operate on lists, for example, a function to generate the list of numbers between <code>i</code> and <code>j</code></p>
<div class="sourceCode" id="cb29"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb29-1" data-line-number="1"><span class="kw">def</span> <span class="bu">range</span>(i, j):</a>
<a class="sourceLine" id="cb29-2" data-line-number="2">  <span class="cf">if</span> (i <span class="op">&lt;</span> j):</a>
<a class="sourceLine" id="cb29-3" data-line-number="3">    cons(i, <span class="bu">range</span>(i<span class="op">+</span><span class="dv">1</span>, j))</a>
<a class="sourceLine" id="cb29-4" data-line-number="4">  <span class="cf">else</span>:</a>
<a class="sourceLine" id="cb29-5" data-line-number="5">    emp()</a>
<a class="sourceLine" id="cb29-6" data-line-number="6"></a>
<a class="sourceLine" id="cb29-7" data-line-number="7"><span class="bu">range</span>(<span class="dv">1</span>, <span class="dv">5</span>)</a></code></pre></div>
<p>which should produce the result</p>
<p><code>(1,(2,(3,(4,false))))</code></p>
<p>and a function to sum up the elements of a list:</p>
<div class="sourceCode" id="cb30"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb30-1" data-line-number="1"><span class="kw">def</span> <span class="bu">sum</span>(xs):</a>
<a class="sourceLine" id="cb30-2" data-line-number="2">  <span class="cf">if</span> (isEmpty(xs)):</a>
<a class="sourceLine" id="cb30-3" data-line-number="3">    <span class="dv">0</span></a>
<a class="sourceLine" id="cb30-4" data-line-number="4">  <span class="cf">else</span>:</a>
<a class="sourceLine" id="cb30-5" data-line-number="5">    head(xs) <span class="op">+</span> <span class="bu">sum</span>(tail(xs))</a>
<a class="sourceLine" id="cb30-6" data-line-number="6"></a>
<a class="sourceLine" id="cb30-7" data-line-number="7"><span class="bu">sum</span>(<span class="bu">range</span>(<span class="dv">1</span>, <span class="dv">5</span>))</a></code></pre></div>
<p>which should produce the result <code>10</code>.</p>
<h2 id="recap">Recap</h2>
<p>We have a pretty serious language now, with:</p>
<ul>
<li><strong>Data Structures</strong></li>
</ul>
<p>which are implemented using</p>
<ul>
<li><strong>Heap Allocation</strong></li>
<li><strong>Run-time Tags</strong></li>
</ul>
<p>which required a bunch of small but subtle changes in the</p>
<ul>
<li>runtime and compiler</li>
</ul>
<p>In your assignment, you will add <em>native</em> support for n-ary tuples, letting the programmer write code like:</p>
<div class="sourceCode" id="cb31"><pre class="sourceCode python"><code class="sourceCode python"><a class="sourceLine" id="cb31-1" data-line-number="1">(e1, e2, e3, ..., en)  <span class="co"># constructing tuples of arbitrary arity</span></a>
<a class="sourceLine" id="cb31-2" data-line-number="2"></a>
<a class="sourceLine" id="cb31-3" data-line-number="3">e1[e2]                 <span class="co"># allowing expressions to be used as fields</span></a></code></pre></div>
<p>Next, we'll see how to</p>
<ul>
<li>use the "pair" mechanism to add <strong>higher-order functions</strong> and</li>
<li>reclaim unused memory via <strong>garbage collection</strong>.</li>
</ul>
<pre><code>data List = Node Int List         -- (Int, List)
          | Empty                 -- false

1:2:3:4:5:6:7:8:[]
(1,(2,(3,(4,(5,(6,(7,(8,false))))))))

def isEmpty(l):
  l == false

def cons(h, t):
  (h, t)

def head(e):
  e[0]

def tail(e):
  e[1]

def length(l):  
  if isEmpty(l):
    0
  else:
    1 + length(tail(l))

data Tree = Node Int Tree Tree    -- (Int, Tree, Tree)
          | Leaf                  -- False

def node(n, l, r):  
  return (n, l, r)

def isLeaf(t):
  t == false

def nodeVal(t)::
  t[0]

def nodeLeft(t)::
  t[1]

def nodeRight(t)::
  t[2]</code></pre>	
                <hr>
            </div>
        </div>
    </div>
</article>

        </div>
        <div id="footer">
        </div>
      <!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                <ul class="list-inline text-center">
                    <li>
                        <a href="https://ucsd-progsys.github.io/131-web/feed.xml" data-datatype="json" data-type="GET" data-target="#frame" class="reload" id="clickme">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-rss fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                    
                    <li>
                        <a href="https://twitter.com/ranjitjhala" data-datatype="json" data-type="GET" data-target="#frame" class="reload" id="clickme" target="_blank">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-twitter fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                    
                    
                    <li>
                        <a href="https://plus.google.com/u/0/106612421534244742464" data-datatype="json" data-type="GET" data-target="#frame" class="reload" id="clickme" target="_blank">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-google-plus fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                     
                     
                    <li>
                        <a href="https://github.com/ucsd-progsys/131-web" target="_blank">
                            <span class="fa-stack fa-lg">

                              <i class="fa fa-arrow-circle-o-down"></i>
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-github fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                    
		    
                </ul>
                <p class="copyright text-muted">Copyright &copy; Ranjit Jhala
                2016-18. Please suggest fixes <a href="http://github.com/ucsd-progsys/131-web">here.</a><br><br> 
                </p>
<div class="col-md-12">
     <p class="copyright text-muted">
     Site generated by <a href="http://jaspervdj.be/hakyll">Hakyll</a>, using
     a theme by <a href="http://katychuang.com/hakyll-cssgarden/gallery/" target="_blank">Katy Chuang.</a>
     </p>
</div>
    
            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="https://ucsd-progsys.github.io/131-web/static/js/jquery.min.js"></script>
<script src="https://ucsd-progsys.github.io/131-web/static/js/spaceg.stylesheets.min.js"></script> 
<script src="https://ucsd-progsys.github.io/131-web/static/js/bootstrap.min.js"></script>
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js"></script>
<script src="https://ucsd-progsys.github.io/131-web/static/js/scripts.js"></script>



    </body>
</html>
