--- /dev/null
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+
+<svg
+ xmlns:dc="http://purl.org/dc/elements/1.1/"
+ xmlns:cc="http://creativecommons.org/ns#"
+ xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+ xmlns:svg="http://www.w3.org/2000/svg"
+ xmlns="http://www.w3.org/2000/svg"
+ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+ xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+ width="212.50002mm"
+ height="500.26459mm"
+ viewBox="0 0 212.50002 500.26459"
+ version="1.1"
+ id="svg8"
+ inkscape:export-filename="/home/marius/uite.png"
+ inkscape:export-xdpi="327.45166"
+ inkscape:export-ydpi="327.45166"
+ sodipodi:docname="module.svg"
+ inkscape:version="0.92.1 r15371">
+ <defs
+ id="defs2" />
+ <sodipodi:namedview
+ id="base"
+ pagecolor="#ffffff"
+ bordercolor="#666666"
+ borderopacity="1.0"
+ inkscape:pageopacity="1"
+ inkscape:pageshadow="2"
+ inkscape:zoom="0.70710678"
+ inkscape:cx="713.73344"
+ inkscape:cy="448.37787"
+ inkscape:document-units="mm"
+ inkscape:current-layer="g4201"
+ showgrid="true"
+ inkscape:snap-page="true"
+ showguides="false"
+ inkscape:window-width="1364"
+ inkscape:window-height="726"
+ inkscape:window-x="0"
+ inkscape:window-y="20"
+ inkscape:window-maximized="1"
+ fit-margin-top="10"
+ fit-margin-left="10"
+ fit-margin-bottom="10"
+ fit-margin-right="10"
+ inkscape:pagecheckerboard="true"
+ borderlayer="false"
+ inkscape:showpageshadow="false"
+ showborder="true">
+ <inkscape:grid
+ type="xygrid"
+ id="grid3686"
+ units="mm"
+ spacingx="2.5"
+ spacingy="2.5"
+ empcolor="#ff0000"
+ empopacity="0.25098039"
+ dotted="false"
+ empspacing="6"
+ originx="-122.5"
+ originy="25.132279" />
+ </sodipodi:namedview>
+ <metadata
+ id="metadata5">
+ <rdf:RDF>
+ <cc:Work
+ rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type
+ rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+ <dc:title />
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g
+ inkscape:label="Layer 1"
+ inkscape:groupmode="layer"
+ id="layer1"
+ transform="translate(-122.5,178.13229)">
+ <g
+ id="g3866"
+ transform="translate(0,15)"
+ inkscape:export-xdpi="327.45166"
+ inkscape:export-ydpi="327.45166">
+ <text
+ id="text3789"
+ y="291.99997"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3791"
+ style="stroke-width:0.26458332"
+ y="291.99997"
+ x="150"
+ sodipodi:role="line">clk</tspan></text>
+ <text
+ id="text3797"
+ y="276.99997"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="276.99997"
+ x="150"
+ id="tspan3795"
+ sodipodi:role="line">addr</tspan></text>
+ <text
+ id="text3801"
+ y="262"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="262"
+ x="150"
+ id="tspan3799"
+ sodipodi:role="line">din</tspan></text>
+ <text
+ id="text3805"
+ y="247"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="247"
+ x="150"
+ id="tspan3803"
+ sodipodi:role="line">we</tspan></text>
+ <text
+ id="text3809"
+ y="267"
+ x="180"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3819"
+ style="stroke-width:0.26458332"
+ y="267"
+ x="180"
+ sodipodi:role="line">GCRAM</tspan></text>
+ <text
+ id="text3813"
+ y="267"
+ x="227.51352"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3815"
+ style="stroke-width:0.26458332"
+ y="267"
+ x="227.51352"
+ sodipodi:role="line">do</tspan></text>
+ <rect
+ y="237"
+ x="145"
+ height="60"
+ width="100"
+ id="rect3823"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3833"
+ d="M 145,244.5 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3835"
+ d="M 145,259.5 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3837"
+ d="M 145,274.49999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3839"
+ d="M 145,289.49999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3841"
+ d="m 245,264.5 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path3845"
+ d="m 145,284.5 5,4.99999 -5,5.00002"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ </g>
+ <text
+ xml:space="preserve"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ x="200"
+ y="187"
+ id="text3906"><tspan
+ sodipodi:role="line"
+ x="200"
+ y="196.36377"
+ style="stroke-width:0.26458332"
+ id="tspan3908" /></text>
+ <text
+ xml:space="preserve"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ x="150"
+ y="24.5"
+ id="text4073"><tspan
+ sodipodi:role="line"
+ id="tspan4071"
+ x="150"
+ y="33.86377"
+ style="stroke-width:0.26458332" /></text>
+ <text
+ xml:space="preserve"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ x="257.5"
+ y="52"
+ id="text4089"><tspan
+ sodipodi:role="line"
+ id="tspan4087"
+ x="257.5"
+ y="61.36377"
+ style="stroke-width:0.26458332" /></text>
+ <g
+ id="g4201">
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3870"
+ y="234.49998"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3872"
+ style="stroke-width:0.26458332"
+ y="234.49998"
+ x="150"
+ sodipodi:role="line">clk</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3878"
+ y="219.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3880"
+ style="stroke-width:0.26458332"
+ y="219.5"
+ x="150"
+ sodipodi:role="line">cen</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3894"
+ y="204.18437"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="204.18437"
+ x="150"
+ id="tspan3892"
+ sodipodi:role="line">Ein</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3898"
+ y="189.18437"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="189.18437"
+ x="150"
+ id="tspan3896"
+ sodipodi:role="line">gcop</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3902"
+ y="174.18437"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="174.18437"
+ x="150"
+ id="tspan3900"
+ sodipodi:role="line">ram_do</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3914"
+ y="234.49998"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan3916"
+ style="stroke-width:0.26458332"
+ y="234.49998"
+ x="237.5"
+ sodipodi:role="line">ostate</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3922"
+ y="219.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="219.5"
+ x="237.5"
+ id="tspan3920"
+ sodipodi:role="line">conn_ea</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3926"
+ y="204.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="204.5"
+ x="237.5"
+ id="tspan3924"
+ sodipodi:role="line">conn_et</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3930"
+ y="189.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan4021"
+ style="stroke-width:0.26458332"
+ y="189.5"
+ x="237.5"
+ sodipodi:role="line">Eout</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3938"
+ y="159.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="159.5"
+ x="237.5"
+ id="tspan3936"
+ sodipodi:role="line">ram_di</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3942"
+ y="144.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="144.5"
+ x="237.5"
+ id="tspan3940"
+ sodipodi:role="line">ram_addr</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3946"
+ y="129.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="129.5"
+ x="237.5"
+ id="tspan3944"
+ sodipodi:role="line">ram_we</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3950"
+ y="174.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="174.5"
+ x="237.5"
+ id="tspan3948"
+ sodipodi:role="line">step_eval</tspan></text>
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3954"
+ y="182"
+ x="200"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="182"
+ x="200"
+ id="tspan3952"
+ sodipodi:role="line">GC</tspan></text>
+ <rect
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ ry="0"
+ y="102"
+ x="145"
+ height="137.5"
+ width="147.5"
+ id="rect3956"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332" />
+ <text
+ inkscape:export-ydpi="327.45166"
+ inkscape:export-xdpi="327.45166"
+ id="text3960"
+ y="114.5"
+ x="237.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="114.5"
+ x="237.5"
+ id="tspan3958"
+ sodipodi:role="line">Pout</tspan><tspan
+ id="tspan3962"
+ style="stroke-width:0.26458332"
+ y="127.72916"
+ x="237.5"
+ sodipodi:role="line" /></text>
+ <path
+ inkscape:connector-curvature="0"
+ id="path4025"
+ d="M 145,187 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4027"
+ d="M 145,172 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4031"
+ d="M 145,202 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4033"
+ d="M 145,217 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4035"
+ d="M 145,232 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4037"
+ d="m 292.49999,232 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4039"
+ d="m 292.49999,217 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4041"
+ d="m 292.49999,202 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4043"
+ d="m 292.49999,187 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4045"
+ d="m 292.49999,172 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4047"
+ d="m 292.49999,157 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4049"
+ d="m 292.49999,142 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4051"
+ d="m 292.49999,127 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4053"
+ d="m 292.49999,112 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4117"
+ d="m 145,227 5,5 -5,5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ </g>
+ <g
+ id="g4149">
+ <text
+ id="text4057"
+ y="84.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="84.5"
+ x="150"
+ id="tspan4055"
+ sodipodi:role="line">clk</tspan></text>
+ <text
+ id="text4061"
+ y="69.500008"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="69.500008"
+ x="150"
+ id="tspan4059"
+ sodipodi:role="line">cen</tspan></text>
+ <text
+ id="text4065"
+ y="54.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="54.5"
+ x="150"
+ id="tspan4063"
+ sodipodi:role="line">rx_byte</tspan></text>
+ <text
+ id="text4069"
+ y="39.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="39.5"
+ x="150"
+ id="tspan4067"
+ sodipodi:role="line">rx_signal</tspan></text>
+ <text
+ id="text4077"
+ y="61.999996"
+ x="202.49998"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="61.999996"
+ x="202.49998"
+ id="tspan4075"
+ sodipodi:role="line">READER</tspan></text>
+ <text
+ id="text4081"
+ y="84.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="84.5"
+ x="257.5"
+ id="tspan4079"
+ sodipodi:role="line">active</tspan></text>
+ <text
+ id="text4085"
+ y="69.500008"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="69.500008"
+ x="257.5"
+ id="tspan4083"
+ sodipodi:role="line">ram_di</tspan></text>
+ <text
+ id="text4093"
+ y="54.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="54.5"
+ x="257.5"
+ id="tspan4091"
+ sodipodi:role="line">ram_addr</tspan></text>
+ <text
+ id="text4097"
+ y="39.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="39.5"
+ x="257.5"
+ id="tspan4095"
+ sodipodi:role="line">ram_we</tspan></text>
+ <rect
+ y="27"
+ x="145"
+ height="62.5"
+ width="167.5"
+ id="rect4099"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4101"
+ d="m 312.50001,81.999999 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4103"
+ d="m 312.50001,67 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4105"
+ d="m 312.50001,51.999999 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4107"
+ d="m 312.50001,37 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4109"
+ d="M 145,37 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4111"
+ d="M 145,51.999999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4113"
+ d="M 145,67 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4115"
+ d="M 145,81.999999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4119"
+ d="m 145,76.999998 5,5.000001 L 145,87"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ </g>
+ <g
+ id="g4427">
+ <text
+ id="text4205"
+ y="9.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="9.5"
+ x="150"
+ id="tspan4203"
+ sodipodi:role="line">clk</tspan></text>
+ <text
+ id="text4209"
+ y="-5.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-5.5"
+ x="150"
+ id="tspan4207"
+ sodipodi:role="line">cen</tspan></text>
+ <text
+ id="text4213"
+ y="-20.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-20.5"
+ x="150"
+ id="tspan4211"
+ sodipodi:role="line">tx_busy</tspan></text>
+ <text
+ id="text4217"
+ y="-35.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-35.5"
+ x="150"
+ id="tspan4215"
+ sodipodi:role="line">P</tspan></text>
+ <text
+ id="text4221"
+ y="-50.499996"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-50.499996"
+ x="150"
+ id="tspan4219"
+ sodipodi:role="line">ram_do</tspan></text>
+ <text
+ id="text4225"
+ y="-20.5"
+ x="202.49998"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-20.5"
+ x="202.49998"
+ id="tspan4223"
+ sodipodi:role="line">WRITER</tspan></text>
+ <text
+ id="text4229"
+ y="-5.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-5.5"
+ x="257.5"
+ id="tspan4227"
+ sodipodi:role="line">tx_byte</tspan></text>
+ <text
+ id="text4233"
+ y="-20.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-20.5"
+ x="257.5"
+ id="tspan4231"
+ sodipodi:role="line">tx_signal</tspan></text>
+ <text
+ id="text4237"
+ y="-35.5"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-35.5"
+ x="257.5"
+ id="tspan4235"
+ sodipodi:role="line">finished</tspan></text>
+ <text
+ id="text4241"
+ y="-50.499996"
+ x="257.5"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-50.499996"
+ x="257.5"
+ id="tspan4239"
+ sodipodi:role="line">ram_addr</tspan></text>
+ <rect
+ y="-62.999996"
+ x="145"
+ height="77.5"
+ width="167.5"
+ id="rect4243"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4291"
+ d="M 145,12 150,6.9999999 145,2"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4295"
+ d="M 145,6.9999999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4297"
+ d="M 145,-7.9999998 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4299"
+ d="M 145,-23 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4301"
+ d="M 145,-38 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4303"
+ d="M 145,-52.999999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4305"
+ d="m 312.50001,-52.999999 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4307"
+ d="m 312.50001,-38 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4309"
+ d="m 312.50001,-23 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4311"
+ d="m 312.50001,-7.9999998 h 12.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ </g>
+ <g
+ id="g4362">
+ <text
+ id="text4247"
+ y="-80.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ id="tspan4249"
+ style="stroke-width:0.26458332"
+ y="-80.5"
+ x="150"
+ sodipodi:role="line">clk</tspan></text>
+ <text
+ id="text4255"
+ y="-95.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-95.5"
+ x="150"
+ id="tspan4253"
+ sodipodi:role="line">cen</tspan></text>
+ <text
+ id="text4259"
+ y="-110.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-110.5"
+ x="150"
+ id="tspan4257"
+ sodipodi:role="line">rst</tspan></text>
+ <text
+ id="text4263"
+ y="-125.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-125.5"
+ x="150"
+ id="tspan4261"
+ sodipodi:role="line">Ein</tspan></text>
+ <text
+ id="text4267"
+ y="-140.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-140.5"
+ x="150"
+ id="tspan4265"
+ sodipodi:role="line">conn_ea</tspan></text>
+ <text
+ id="text4271"
+ y="-155.5"
+ x="150"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-155.5"
+ x="150"
+ id="tspan4269"
+ sodipodi:role="line">conn_et</tspan></text>
+ <text
+ id="text4275"
+ y="-120.5"
+ x="202.49998"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-120.5"
+ x="202.49998"
+ id="tspan4273"
+ sodipodi:role="line">EVAL</tspan></text>
+ <text
+ id="text4279"
+ y="-95.5"
+ x="240"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-95.5"
+ x="240"
+ id="tspan4277"
+ sodipodi:role="line">ostate</tspan></text>
+ <text
+ id="text4283"
+ y="-110.5"
+ x="240"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-110.5"
+ x="240"
+ id="tspan4281"
+ sodipodi:role="line">gcop</tspan></text>
+ <text
+ id="text4287"
+ y="-125.5"
+ x="240"
+ style="font-style:normal;font-weight:normal;font-size:10.58333302px;line-height:1.25;font-family:sans-serif;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332"
+ xml:space="preserve"><tspan
+ style="stroke-width:0.26458332"
+ y="-125.5"
+ x="240"
+ id="tspan4285"
+ sodipodi:role="line">Eout</tspan></text>
+ <rect
+ y="-168"
+ x="145"
+ height="92.500084"
+ width="132.5"
+ id="rect4289"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4293"
+ d="m 145,-88 5,5 -5,5.000001"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4313"
+ d="M 277.5,-97.999999 H 290"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4315"
+ d="M 277.5,-113 H 290"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4317"
+ d="M 277.5,-128 H 290"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4319"
+ d="M 145,-83 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4321"
+ d="M 145,-97.999999 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4323"
+ d="M 145,-113 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4325"
+ d="M 145,-128 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4327"
+ d="M 145,-143 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path4329"
+ d="M 145,-158 H 132.5"
+ style="fill:none;stroke:#000000;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ </g>
+ </g>
+</svg>
--- /dev/null
+\documentclass[a4paper,12pt]{report}
+\usepackage{color}
+\usepackage[cm]{fullpage}
+\usepackage{graphicx}
+\usepackage{hyperref}
+\usepackage{listings}
+\usepackage{pdfpages}
+
+\title{YULE: Yet Unnamed Lisp Evaluator}
+\author{Marius Gavrilescu}
+\date{May 2018}
+
+\begin{document}
+% title page does not need anchors
+\hypersetup{pageanchor=false}
+\maketitle
+\hypersetup{pageanchor=true}
+\lstset{language=Perl, frame=leftline, framexleftmargin=5pt,
+ showstringspaces=false, showspaces=false, breaklines=true,
+ postbreak=\mbox{\textcolor{red}{$\hookrightarrow$}\space}}
+
+\chapter*{Abstract}
+Lisp machines are computers designed to run Lisp programs efficiently.
+They were first developed in the 1970s, and they have special hardware
+support for Lisp. This usually comprises a tagged architecture (each
+pointer has a ``type'' field), garbage collection implemented in
+hardware, and an instruction set that lends itself well to evaluating
+Lisp expressions.
+
+Between 1975 and 1980, Guy L. Steele and Gerald Jay Sussman wrote a
+series of memos on lambda calculus, the Lisp language and its
+implementation known collectively as the ``Lambda Papers''. One of
+these papers, ``Design of LISP-Based Processors (1979)'' describes how
+to implement a Lisp machine processor. If this processor is connected
+to a RAM that contains a program, it executes that program and places
+the result back into the RAM.
+
+The aim of YULE is to take the design from the 1979, implement it
+today using modern technology and techniques, and bundle it up in a
+form that is both easy to use and extend. By going through this
+modernisation process, future developers can easily integrate the Lisp
+processor into their own design, modifying it as they please.
+
+The end result of YULE is a small device that can be plugged into a
+USB port, and an associated computer program. Running the program
+presents a simplified Lisp listener. The user can type a Lisp
+expression into the listener, and the listener will respond with the
+value of the expression. Under the hood, the listener evaluates Lisp
+by sending the expression over USB to the small device and getting
+back the result.
+
+YULE comes with the design files for the hardware, and source code for
+the software. All of these are released under a free software license
+and published online, which makes it very easy (from both a practical
+and a legal standpoint) for future developers to use in their own
+projects and modify to fit their purposes better.
+\tableofcontents
+
+\chapter{Introduction}
+\section{Motivation}
+Lisp machine processors are quite unlike modern processors. Modern
+instruction sets are designed for imperative programming. Each
+instruction makes the processor execute some operation, such as
+loading a register or storing a value in memory. In contrast, a Lisp
+machine processor reads an expression from memory, determines its
+type, and recursively evaluates it. This operation lends itself to
+declarative programming, where the programmer declares an arbitrarly
+complicated expression and asks the computer to evaluate it.
+
+Another common feature of Lisp machine processors is the use of tagged
+pointers. Each memory location is a tagged union of two elements: the
+value itself, and a tag representing the type of that data. Tagged
+architectures are not common today, although some programs still
+use tagged pointers by exploiting pointer alignment (if every pointer
+is a multiple of 8, then the bottom 3 bits can be used to store a
+tag). These tags can be used to store an object's reference count (as
+in Objective-C on certain versions of iOS), or information about a
+data structure (as in certain implementations of kd-trees).
+
+The ``Design of LISP-Based Processors (1979)'' paper by Guy L. Steele
+and Gerald Jay Sussman \cite{lambda} presents the design of a
+relatively simple Lisp machine processor, which is made from two
+read-only memories, two buses, and several registers. If this
+processor is connected to a RAM containing a Lisp expression in a
+certain binary format, the processor will evaluate the expression and
+place the result back in memory.
+
+This processor features both a tagged architecture (the top 3 bits of
+each word in memory represent the value's type) and the declarative
+nature mentioned above. It is therefore interesting to study and to
+bring this processor into today's world by using technology such as
+hardware description languages (that allow us to describe a circuit
+formally) and FPGAs (that allow us to synthesise any circuit quickly
+and at low cost). By building a HDL implementation of the processor
+not only can it be used easily on its own (by synthesising it to a
+FPGA and connecting it to RAM), but a future circuit designer can take
+this processor and include it in their more complicated design.
+
+The processor presented in the original paper is a somewhat barebones
+implementation of Lisp. Arithmetic primitives are not available, nor
+are there any input or output routines. Due to time constraints the
+paper's writers have not included a equality primitive. Additionally
+the ATOM primitive has a bug that makes it consider NIL not atomic.
+All these deficiencies can be rectified given time and effort, but it
+is difficult for one to fix them given only a paper describing the
+processor. Having a HDL implementation of the processor with a proper
+test suite allows a future circuit designer to more easily make
+changes to the processor while using the test suite to prevent
+regressions and using a FPGA to quickly obtain a hardware version of
+the changed processor that can be manually tested and used in any
+desired application.
+
+\section{Challenges}
+While \cite{lambda} is part of the well-known Lambda Papers series and
+has been read by many over the years, there are no published
+implementations of the processor described in the paper. Therefore
+\cite{lambda} was the only source used in the building of this
+project, and several of the limitations of the processor were not easy
+to see before the implementation phase was well underway. Furthermore,
+the original paper has several shortcomings.
+
+For one, while the microcode (the values of the two read-only
+memories) is provided in both source and compiled form, the microcode
+compiler is not provided. This makes it difficult to alter the
+microcode to fix bugs or introduce new instructions. One needs to
+either work on the already-compiled code (hard and error-prone) or
+reimplement the microcode compiler, which takes a reasonable amount of
+effort.
+
+Moreover, the paper does not concern itself at all with how the user
+gets a program into memory or how the user gets the result back. This
+makes the processor as-described very difficult to use.
+
+To implement the processor in Verilog, no source other than the paper
+was used. There were no previous implementations of the processor that
+could be consulted to resolve unclarities in the original paper.
+
+In addition, there was no software available for interacting with the
+processor. A compiler and assembler had to be written from scratch,
+and so the processor could not be easily debugged until after the
+software was functional.
+
+\section{Contribution}
+YULE is a modern-day implementation of a Lisp machine processor using
+the ideas and techniques presented in \cite{lambda}.
+
+The main contribution of YULE is a Verilog implementation of the
+processor which allows future circuit designers to use it in their own
+design and modify it as they please.
+
+As the processor as described has no way to input a program or extract
+a result from memory, YULE includes more circuitry around the
+processor that lets it communicate with the external word. This
+consists of a serial UART and two modules, a reader and a writer. When
+the processor is idle, the reader waits for a program to be sent over
+the UART. Once a program has been received, it is placed into memory
+and the processor starts to evaluate it. Once evaluation is done, the
+writer transmits the new contents of the memory over the UART.
+
+Besides the hardware chip, YULE also includes three pieces of
+software:
+
+\begin{itemize}
+\item a compiler, which takes Lisp source code and produces an
+ intermediate representation of the program.
+\item an assembler, which takes a program in the intermediate
+ representation and produces the binary representation of the program
+ that the processor can understand.
+\item a REPL, in which users can type expressions. When an expression
+ is submitted, the REPL compiles it, assembles it, and sends it to
+ the processor. The processor evaluates the expression and sends back
+ a memory dump. The REPL then reads the memory dump, interprets it,
+ and prints the value of the expression in a human-readable format.
+\end{itemize}
+
+The REPL is therefore the entry point of YULE as a whole. An end-user
+who does not intend to extend YULE can plug in an iCEstick with the
+processor, and run the REPL. Then the user can write expressions in
+the REPL and get their values back. Besides being the entry point, the
+REPL serves as a convenient way to test that the entire system is
+working. An expression typed in the REPL goes through the compiler and
+assembler, and then is sent to the processor. It goes through the
+three stages of the processor (reading the expression into memory,
+evaluating the contents of the memory, writing a memory dump).
+
+The hardware and software components of YULE have been tested to
+ensure they function correctly. There is an automated test suite
+containing 48 unit tests for the compiler and assembler, and 21
+functional tests that engage all parts of the system (both the
+software and the hardware). The unit tests ensure that the various
+small parts of the compiler and assembler work properly, while the
+functional tests consist of pairs of short Lisp expressions and their
+correct values. The expressions are written to the REPL, and the
+REPL's output is compared to the correct values.
+
+To make it easier for future circuit designers and programmers to use
+this project, YULE has been released under an open source license.
+Prospective users can find all the source files (for both hardware and
+software) online, and are free to use, modify, and redistribute them
+under the same terms as Perl itself. The files can be accessed at this
+URL: \url{https://git.ieval.ro/?p=yule.git}.
+
+\section{Layout of this report}
+This report begins by describing the background of YULE, the
+technologies that made this project possible and a more in-depth
+description of the 1979 paper. Then the components that YULE comprises
+are examined in turn, followed by a chapter on how everything was
+tested, which includes a worked example of the system in action. The
+report ends with a list of ideas for future work based on YULE, and a
+section on reflections.
+
+\chapter{Background}
+
+\section{Field-programmable gate array}
+An FPGA is a configurable integrated circuit. A designer can define a
+circuit using a hardware description language (explained in the next
+section) and compile it to some binary format called a configuration.
+This configuration describes how the different components of the FPGA
+should be connected to each other. The configuration can then be
+uploaded to the FPGA, and the FPGA will connect its internal
+components as requested.
+
+An FPGA can therefore replace any digital custom circuit (ASIC). While
+an FPGA consumes more energy, uses more space, and runs at slower
+clock rates than an ASIC, the FPGA permits rapid prototyping: the time
+between finishing to write a design and having a working part is mere
+seconds (compilation time + uploading the configuration to the FPGA),
+and if a bug is discovered the buggy part need not be thrown away. The
+design can be modified and the fixed configuration can be uploaded to
+the FPGA.
+
+The hardware aspect of YULE is designed to run on the Lattice
+iCE40HX-1k FPGA, but with small modifications it can run on other
+FPGAs as well.
+
+\subsection*{iCEstick}
+\begin{figure}
+ \centering
+ \includegraphics[height=4cm]{icestick.png}
+ \caption{Lattice iCEstick Evaluation Kit}
+\end{figure}
+
+The Lattice iCEstick Evaluation Kit is a development board for the
+iCE40HX-1k FPGA. It contains the FPGA, a USB connector, a FTDI chip
+and 5 LEDs. The form factor is very convenient. It is similar to a USB
+memory stick (albeit bigger) that can be plugged into a computer,
+avoiding the need for jumper wires and GPIO that traditional
+development boards require.
+
+The FTDI chip implements the USB protocol, allowing the FPGA to be
+programmed by the computer and letting the FPGA talk to the computer
+using a very simple serial UART interface on the FPGA side, and a
+standard USB serial port on the computer side. This makes
+communication very easy. The FPGA can use any off-the-shelf UART
+implementation (this project uses \texttt{osdvu} from
+Opencores \cite{osdvu}), and the computer can use standard serial
+console tools such as \texttt{minicom}.
+
+\section{Verilog}
+Verilog is a hardware description language. It is used to model
+digital circuits at register-transfer level of abstraction. In Verilog
+one defines several modules, with one of them (the ``toplevel''
+module) representing the entire design. Each module has several inputs
+and outputs, can contain internal wires, can contain instances of
+other modules, and can contain combinational and sequential logic
+blocks that drive internal wires and outputs.
+
+Verilog has many more complicated features that are not used in YULE.
+These include tristate buffers, delays, functions, tasks, loops, and
+strength declarations.
+
+A subset of Verilog can be \textit{synthesised}; that is converted to
+a netlist (a list of transistors or FPGA components used and
+connections between them) that can then be used to build an ASIC
+(custom integrated circuit), or can be further converted to the
+internal representation of the FPGA and uploaded to the FPGA. The FPGA
+workflow and the programs that are part of it are described in the
+next section.
+
+A verilog project can also be run through a simulator, which simulates
+the design clock edge by clock edge and records the values on each
+wire in the design. This record can later be read in and visualised
+with a wave viewer, which allows a circuit designer to better
+understand why the circuit is not working correctly. One such program,
+GTKWave \cite{gtkwave}, was used to debug YULE.
+
+\section{icestorm}
+Project IceStorm \cite{icestorm} is a set of open source reverse
+engineered tools for programming Lattice iCE40 FPGAs. There exists a
+fully open source Verilog-to-Bitstream flow which comprises:
+
+\begin{enumerate}
+\item Yosys, a Verilog synthetizer.
+\item Arachne-pnr, a tool that implements placing and routing for
+ iCE40 FPGAs.
+\item icepack, which converts Arachne-pnr's output to iCE40 bitstream.
+\item iceprog, which programs the iCEstick with the output of icepack.
+\end{enumerate}
+
+\section{Design of LISP-Based Processors (1979)}
+Design of LISP-Based Processors (1979) \cite{lambda} is one of the
+``Lambda papers''; a series of memos by Sussman and Steele about the
+Lisp language and its implementation. The paper describes SIMPLE, a
+microprocessor designed to run Lisp.
+
+This processor is made of two read-only memories called EVAL and GC.
+Each read-only memory is paired with state registers to form a state
+machine. The contents of the state registers are fed into the
+read-only memory, and the output of the read-only memory determines
+the next state and other signals.
+
+Each state machine also has an internal bus (called the E and G buses
+respectively) and several registers connected to that bus. Each of
+these registers stores a tagged pointer, which is an 11-bit value (the
+top 3 bits represent the type, and the bottom 8 bytes represent the
+value).
+
+The signals coming out of each state machine can cause a register to
+be read onto the machine's internal bus, a register to be loaded from
+the internal bus, or write a constant value onto the internal bus.
+
+The GC state machine represents the processor's memory system. It is
+connected to an external RAM, which it controls through several
+signals. It knows how to execute certain ``GC operations'', which
+represent common Lisp memory management actions. Examples of these are
+\texttt{CAR} and \texttt{CDR} (``given a pointer to a cons cell,
+return either the CAR or the CDR of that cons cell'') or \texttt{CONS}
+(``given two pointers, allocate a new cons cell, copy them into it,
+and return a pointer to the new cons cell''). The existence of the GC
+isolates the rest of the processor from the particularities of the
+memory used.
+
+The EVAL state machine evaluates Lisp expressions. Signals coming out
+of it control the GC by selecting what operation the GC should perform
+and connecting the E and G buses to supply arguments to the GC and
+read results back. The EVAL reads expressions from memory via the GC
+and evaluates them, putting results back into memory.
+
+The overall operation of the processor is to read an expression from
+the magic location ``5'' in memory, evaluate it, and place the result
+into the magic location ``6'' in memory. Other memory locations are
+used to store subexpressions of the input expression, and to store any
+intermediate results. Despite its name, GC does not perform any
+garbage collection, so at the end of the processor's operation the
+memory will still contain all intermediate results produced during
+evaluation.
+
+The processor is intended as a proof of concept and not a
+production-ready hardware implementation of Lisp. Therefore it has
+several important limitations, for example there is no primitive
+operation that implements equality of objects (making it impossible to
+distinguish between symbols), there are no primitive arithmetic
+operations (so one needs to use Church numerals if numbers are
+needed), and the processor includes a known bug (``the ATOM bug'').
+The bug is that the ATOM primitive considers NIL to be non-atomic,
+which is incorrect.
+
+The Lisp expressions mentioned here are in textual form (Lisp source
+code), but instead in a special tagged pointer format. Each memory
+value is a union of two values: a 8-bit pointer and a 3-bit type. We
+can use pairs of consecutive memory locations to represent cons cells
+and build linked lists out of them. If a list is at location X, that
+means that (X, X+1) is the first cons cell of the list, with X+1 being
+the CAR (the value of the first element) and X being the CDR (a
+pointer to the next cons cell). A discussion of the different ways to
+represent Lisp expressions (source code, this tagged pointer format,
+and an intermediate representation) can be found in \ref{sec:formats}.
+
+The next page shows a diagram of how the processor in the paper is
+structured. The two read-only memories can be seen, with their
+registers, state registers, and the interconnection between the E and
+G buses.
+
+\begin{figure}
+\centering\includegraphics[width=18.5cm]{AIM-514-design.pdf}
+\caption{Design diagram of processor from \cite{lambda}}
+\end{figure}
+
+\chapter{A Lisp Machine processor on a USB drive}
+The project comprises a hardware part written in Verilog and a
+software part written in Perl.
+
+The hardware part is a Lisp machine processor with associated
+circuitry that can read a program from the iCEstick UART and that can
+write the result of running a program to the UART. The normal
+operation of this part is to:
+
+\begin{enumerate}
+\item Wait for a program to be supplied via UART
+\item Run the program on the processor
+\item Write a memory dump to the UART
+\item Go back to step 1
+\end{enumerate}
+
+The software part includes:
+
+\begin{itemize}
+\item A compiler, which takes Lisp source code and puts it in the
+ linked list format understood by the SIMPLE processor
+\item An assembler, which takes the result of the compiler and
+ converts it to the SIMPLE in-memory binary format.
+\item A REPL, which repeatedly reads a program from the user, compiles
+ it, assembles it, sends it to YULE, reads the memory dump from YULE,
+ and prints the result for the user to see.
+\end{itemize}
+
+\clearpage
+\section{Hardware}
+The hardware part is built from 8 modules:
+
+\begin{enumerate}
+\item The \textbf{READER}, which implements step 1 of the normal operation described above.
+\item The \textbf{WRITER}, which implements step 3 of the normal operation described above.
+\item The \textbf{GCRAM}, a single-port RAM.
+\item The \textbf{GC}, corresponding to the GC PLA in the original implementation.
+\item The \textbf{EVAL}, corresponding to the EVAL PLA in the original implementation.
+\item The \textbf{CTRL}, which advances the operation from one step to the next one.
+\item The \textbf{UART}, which implements transmission and reception of bytes via UART.
+\item The \textbf{CPU}, which instantiates every module above and wires them together.
+\end{enumerate}
+
+\subsection{Clocks}
+To avoid timing problems, a single 48 MHz clock is used. The iCEstick
+has a 12 MHz oscillator, and the phase-locked loop circuitry on the
+FPGA multiplies this signal by 4.
+
+Every flip-flop updates on the positive edge of the clock, except for
+the RAM which updates on the negative edge. This way the rest of the
+circuit perceives the RAM to be combinational (it ``updates
+immediately''): if on a positive edge the RAM's address input changes,
+the RAM will update its output on the following negative edge and the
+changed output will be visible on the next positive edge. If the RAM
+updated on a positive edge, then if the input changed on positive edge
+$i$ the changed output will only be visible on positive edge $i+2$.
+
+The design is intended to be run on a FPGA, which has a fixed clock
+tree. This typically consists of a small number of special nets called
+global buffers that can distribute signals with minimal skew to every
+logic cell. The FPGA on the iCEstick has 8 such global buffers.
+
+
+There are 4 components in the design (GC, EVAL, READER, WRITER) that
+need to be enabled/disabled at different times. One way to achieve
+this is to AND the master 48 MHz clock with several signals, thus
+creating a separate clock for each component. This is known as
+\textit{clock gating}. However, on a FPGA clock gating involves
+routing the clock from a global buffer to a logic cell and then back
+to another global buffer. This can introduce glitches in the clock and
+would delay each of the clocks by some amount (dependent on the
+signals it is ANDed with). It is therefore possible that the 4 output
+clocks would not be aligned, causing problems when data is
+communicated by one component to another. As such, clock gating is not
+recommended on FPGAs.
+
+\begin{figure}
+ \centering\includegraphics[height=3cm]{gating.eps}
+ \caption{Gated clock on the left, clock enable on the right}
+\end{figure}
+
+To avoid this problem, the design used here does not use clock gating
+and instead uses 4 clock enable signals supplied by the controller to
+each of the GC, EVAL, READER and WRITER. At any point the clock is
+enabled for exactly one of the READER, GC, and WRITER. The EVAL clock
+is enabled if and only if the GC clock is enabled and the GC's
+\texttt{step\_eval} output is high.
+
+\clearpage
+\subsection{GC}
+\begin{figure}
+ \centering\includegraphics[height=4.88cm]{gc.eps}
+ \caption{GC module}
+\end{figure}
+
+The GC module is connected to the GCRAM (via the \texttt{ram\_do,
+ ram\_we, ram\_addr, ram\_di} signals), to the EVAL (via the
+\texttt{Ein, Eout, gcop, step\_eval, conn\_et, conn\_ea} signals) and
+to the controller. It also provides the value of its P register (the
+free storage pointer) to the WRITER, so the writer can know when to
+stop dumping the memory.
+
+It is implemented as a combinational ROM, some combinational logic to
+drive the internal G bus, sequential logic to advance to the next
+state respecting dispatch rules, and sequential logic to update
+registers. The clock enable signal acts as an active low synchronous
+reset: when the clock is disabled, the state register is set to the
+initial state.
+
+This module represents one half of the original design presented in
+\cite{lambda}, and the ROM's contents are those from the paper with a
+bugfi (the original design sets the ADR line low in two states when it
+should be high).
+
+\subsection{EVAL}
+\begin{figure}
+ \centering\includegraphics[height=3.29cm]{eval.eps}
+ \caption{EVAL module}
+\end{figure}
+
+The EVAL module is connected to the GC (via the \texttt{conn\_et,
+ conn\_ea, Ein, Eout, gcop} signals) and to the controller.
+
+The implementation of the EVAL is very similar to that of the GC.
+There is a combinational ROM, combinational logic to drive the E bus,
+sequential logic to advance to the next state respecting dispatch
+rules, and sequential logic to update registers. A synchronous reset
+is available. When the reset line is held high for one clock cycle,
+the state register is set to the initial state. It is necessary to
+separate the reset from the clock enable because the GC often pauses
+the EVAL to do work and the EVAL should not be reset every time this
+happens.
+
+This module represents the other half of the original design presented
+in \cite{lambda}, and the ROM's contents are the same as those in the
+paper except that the ROM is widened by one bit to indicate whether
+the EVAL is finished evaluating the expression.
+
+\clearpage
+\subsection{Writer}
+\begin{figure}
+\centering\includegraphics[height=2.26cm]{writer.eps}
+\caption{WRITER module}
+\end{figure}
+
+The WRITER module is connected to the UART (via the \texttt{tx\_busy,
+ tx\_signal, tx\_byte} signals), the GC (via the \texttt{P} signal),
+the RAM (via the \texttt{ram\_addr, ram\_do} signals), and to the
+controller.
+
+Its purpose is to dump the memory to the UART starting with position 4
+(since positions 0, 1, 2, 3 are constant) and finishing with position
+$P - 1$, the last used cell in memory. It is implemented as a state
+machine with 7 states and an extra register (\texttt{current\_index})
+that stores the current index in the memory.
+
+The memory is 16-bit wide, but the UART sends and receives bytes. The
+writer dumps memory word in network byte order (big-endian), meaning
+the significant byte is sent before the least significant byte.
+
+The states are, in order:
+\begin{description}
+\item[START] which initializes \texttt{current\_index} to 4
+\item[WRITE1\_WAIT] which waits for \texttt{tx\_busy} to become low
+\item[WRITE1] in which transmission of the upper byte starts
+\item[WRITE2\_WAIT] which waits for \texttt{tx\_busy} to become low
+\item[WRITE2] in which transmission of the lower byte starts
+\item[INCREMENT] in which \texttt{current\_index} is incremented,
+ jumping back to WRITE1\_WAIT if it is still lower than
+ \texttt{freeptr}.
+\item[FINISHED] in which \texttt{finished} is driven high
+\end{description}
+
+This module is not part of the original design in \cite{lambda}, as
+that paper did not concern itself with input and output.
+
+\clearpage
+\subsection{Reader}
+\begin{figure}
+\centering\includegraphics[height=2.22cm]{reader.eps}
+\caption{READER module}
+\end{figure}
+
+The READER module is connected to the UART (via the
+\texttt{rx\_signal, rx\_byte} signals), the RAM (via the
+\texttt{ram\_we, ram\_addr, ram\_di} signals), and to the controller.
+
+Its purpose is to read a program from the UART and overwrite the GCRAM
+with this program. It is implemented as a state machine with two extra
+registers (\texttt{total\_words} and \texttt{current\_index}) to store
+the size of the incoming program and the current position within it.
+
+The reader expects to receive a 13-bit \texttt{length} value, followed
+by \texttt{length} 16-bit values that represent the desired memory
+contents. Each of these values is sent in network byte order
+(big-endian), meaning the most significant byte is sent before the
+least significant byte.
+
+The states are, in order:
+\begin{description}
+\item[IDLE] which waits for \texttt{rx\_signal}, puts the read byte at the top of \texttt{total\_words}.
+\item[LENGTH] which waits for \texttt{rx\_signal}, puts the read byte at the bottom of \texttt{total\_words}
+\item[READ1] which waits for the \texttt{rx\_signal}, puts the read byte at the top of \texttt{ram\_di} and increments \texttt{current\_index}
+\item[READ2] which waits for the \texttt{rx\_signal}, puts the read byte at the bottom of \texttt{ram\_di}
+\item[WRITE] in which \texttt{ram\_we} is high, jumping back to READ1 if \texttt{current\_index + 1 < total\_words}
+\item[FINISHED] in which \texttt{finished} is high
+\end{description}
+
+This module is not part of the original design in \cite{lambda}, as
+that paper did not concern itself with input and output.
+
+\clearpage
+\subsection{Putting the hardware together}
+The components described above are managed by the controller, which
+provides them with clock enable signals. The controller is a state
+machine with three states:
+\begin{description}
+\item[STATE\_READ] in which only the READER clock is enabled
+\item[STATE\_RUN] in which the GC and EVAL clocks are enabled
+\item[STATE\_WRITE] in which only the WRITER clock is enabled
+\end{description}
+
+In STATE\_READ and STATE\_WRITE, the EVAL's reset line is high.
+
+Whenver the component corresponding to the current state indicates it
+is finished, the controller advances to the next state.
+
+The controller also includes three multiplexers that control which
+lines are connected to the GCRAM. If the READER is active, all three
+GCRAM lines are connected to the READER. If the WRITER is active, the
+address line is connected to the writer (and the other lines are
+connected to the GC). If the GC is active, all lines are connected to
+the GC.
+
+The controller also includes logic to drive the 5 LEDs on the
+iCEstick. Three LEDs indicate the current state, while the other two
+indicate if the UART is currently transmitting or receiving.
+
+\section{Representing a Lisp program}
+\label{sec:formats}
+The processor described above evaluates a Lisp program received via
+UART. This section talks about three representations of such a
+program: the Lisp source code (a S-expression), the intermediate form
+(also a S-expression), and the in-memory form (a binary string).
+
+The first representation is obtained by parsing the user input, the
+compiler converts this into the second, and the assembler converts the
+second into the third.
+
+\subsection{Lisp source code}
+Recall that a S-expression is either an atom or a cons cell.
+
+An atom is a sequence of letters, digits, and certain symbols. There
+are two special atoms named \texttt{T} and \texttt{NIL} representing
+the boolean true and false respectively.
+
+A cons cell is a pair of two S-expressions called the ``car'' and the
+``cdr''. We write them as \texttt{(car . cdr)}, for example \texttt{(5
+ . 7)} is a cons cell with car \texttt{5} and cdr \texttt{7}.
+
+We can use cons cells to represent linked lists. A linked list is a
+sequence of cons cells where the cdr of one cell is the next cell, and
+the cdr of the last cell is \texttt{NIL}. For example the list
+\texttt{1,2,3} can be written as \texttt{(1 . (2 . (3 . NIL)))}.
+We can also write this list more concisely as \texttt{(1 2 3)}, and we
+write \texttt{()} to mean the atom \texttt{NIL}.
+
+Using these syntax elements we can encode several types of logical
+expressions:
+
+\begin{itemize}
+\item Numbers are encoded as numeric atoms, e.g. \texttt{5}
+\item Variables are encoded as non-numeric atoms, e.g. \texttt{my-var}
+\item Conditional statements are encoded as 4-element lists, e.g.
+ \texttt{(if is-odd 5 6)} which has value 5 if the variable
+ \texttt{is-odd} is not \texttt{NIL} and value 6 otherwise
+\item Symbols are encoded as non-numeric atoms preceded by a single
+ quote, e.g. \texttt{'my-symbol}. This can also be written
+ \texttt{(quote my-symbol)}
+\item Constant lists are encoded as lists preceded by a single quote,
+ e.g. \texttt{'(1 2 (3 4 5))}. This can also be written
+ \texttt{(quote (1 2 (3 4 5)))}
+\item Functions (lambda abstractions) are encoded as 4-element lists,
+ e.g. \texttt{(lambda first (a b) a)} in which the second element is
+ the function name, the third element is a list of function
+ arguments, and the fourth element is the function body.
+\item Function calls are encoded as lists, with the function as the
+ first element and the arguments as the other elements, e.g.
+ \texttt{(atom 5)} calls the function \texttt{atom} with argument
+ \texttt{5}.
+\end{itemize}
+
+\subsection{In-memory representation}
+The memory is an array of 16-bit integer values. We interpret these as
+tagged pointers: the top 3 bits indicate the ``type'' of this pointer,
+while the other 13 bits represent another memory location. A pointer
+therefore has a type and a value.
+
+We represent each Lisp expression as a tagged pointer. To evaluate it,
+the processor looks at the type of the pointer. Here is what a pointer
+of value $v$ means based on its type. We use the syntax $mem[a]$ to
+mean ``the contents of the memory location $a$'' (that is, a tagged
+pointer) and $memval[a]$ to mean ``the value at the memory location
+$a$'' (that is, the value of the tagged pointer $mem[a]$).
+
+\begin{enumerate}
+\setcounter{enumi}{-1}
+\item is a constant list, whose cdr is $mem[v]$ and car is $mem[v+1]$.
+\item is a constant symbol.
+\item is a variable reference, where $v$ indicates the position in the
+ environment of the referenced variable.
+\item is a constant closure, that is the result of evaluating a lambda
+ abstraction. Values of this type do not normally appear in the input
+ code, but instead are created during evaluation of other forms.
+\item is a procedure (lambda abstraction), whose body is $mem[v]$.
+\item is a conditional, where $mem[v+1]$ is the condition,
+ $mem[memval[v]+1]$ is the ``then'' branch, and $mem[memval[v]]$ is the
+ ``else'' branch.
+\item is a procedure call, which points to a special kind of linked
+ list. The CDR of each cell (other than the last one) points to the
+ next cell and has type 0, while the CDR of the last cell has value 0
+ and its type indicates the primitive to be called. The CARs of these
+ cells indicate the arguments for the procedure, in reverse order.
+
+ To call a user-defined procedure, we use the primitive
+ \texttt{funcall} and put the user-defined procedure as the CAR of
+ the last cell (in other words, the user-defined procedure is the
+ first argument to \texttt{funcall}).
+\item is a quoted constant, representing the object at $mem[v]$.
+\end{enumerate}
+
+The booleans \texttt{NIL} and \texttt{T} are compiled to a list
+pointing to 0, and a symbol with value 2 respectively.
+
+The memory has a peculiar fixed layout. Locations 0 and 1 are the CDR
+and CAR of NIL, locations 2 and 3 are the CDR and CAR of T, location 4
+holds the first unused location in memory (this tells the processor
+where it can start to place intermediate expressions), location 5
+holds the expression to be evaluated, and location 6 is where the
+processor will place the value of the expression.
+
+\subsection{The intermediate form}
+To facilitate conversion from the former format to the latter, an
+intermediate form is used. Here we represent tagged pointers as lists
+of one of three types:
+
+\begin{itemize}
+\item \texttt{(type value)}, where ``type'' is the pointer's type and
+ ``value'' is the pointer's (numeric) value.
+\item \texttt{(type ptr)}, where the pointer's type is ``type'' and
+ the pointer's value is $x$, where $x$ is the memory location where
+ ``ptr'' (another tagged pointer) lies.
+\item \texttt{(type ptr1 ptr2)}, where the pointer's type is ``type''
+ and the pointer's value is $x$, where $x$ is the memory location
+ where ``ptr1'' lies and $x+1$ is the memory location where ``ptr2''
+ lies.
+\end{itemize}
+
+These three representations map nicely to the tagged pointers
+described in the previous section. The first representation is used
+for constant symbols and variable references, the second for
+procedures, and the third for constant lists, conditionals, and
+procedure calls.
+
+A visual representation of the intermediate representation (from the
+AIM-514 paper) can be seen on the next page. The expression in
+question is
+
+\begin{lstlisting}
+((lambda append (x y) (if (atom x) y (cons (car x) (append (cdr x) y)))) '(a b c) '(d e f))
+\end{lstlisting}
+
+which we would represent as this sexp:
+
+\begin{lstlisting}
+(CALL (MORE (MORE (FUNCALL 0) (PROC (IF (LIST (CALL (MORE (CONS 0) (CALL (MORE (MORE (FUNCALL 0) (VAR -1)) (VAR -2)) (CALL (CDR 0) (VAR -3)))) (CALL (CAR 0) (VAR -3))) (VAR -2)) (CALL (ATOM 0) (VAR -3))))) (LIST (LIST (LIST (LIST 0) (SYMBOL 6)) (SYMBOL 7)) (SYMBOL 8))) (LIST (LIST (LIST (LIST 0) (SYMBOL 3)) (SYMBOL 4)) (SYMBOL 5)))
+\end{lstlisting}
+
+As mentioned in the Background chapter, the processor has a bug (the
+ATOM bug) that causes \texttt{(ATOM NIL)} to be true. As a result,
+\texttt{(atom x)} in this expression is always true, even when
+\texttt{x} is the empty list, and the expression loops forever (or at
+least until memory is exhausted). We can fix this by changing the
+condition from \texttt{(atom x)} to \texttt{x}, which is false when
+\texttt{x} is NIL and true otherwise, and swapping the two branches of
+the conditional. The fixed program is:
+
+\begin{lstlisting}
+((lambda append (x y) (if x (cons (car x) (append (cdr x) y)) y)) '(a b c) '(d e f))
+\end{lstlisting}
+
+which is compiled to the sligthly shorter sexp:
+
+\begin{lstlisting}
+(CALL (MORE (MORE (FUNCALL 0) (PROC (IF (LIST (VAR -2) (CALL (MORE (CONS 0) (CALL (MORE (MORE (FUNCALL 0) (VAR -1)) (VAR -2)) (CALL (CDR 0) (VAR -3)))) (CALL (CAR 0) (VAR -3)))) (VAR -3)))) (LIST (LIST (LIST (LIST 0) (SYMBOL 6)) (SYMBOL 7)) (SYMBOL 8))) (LIST (LIST (LIST (LIST 0) (SYMBOL 3)) (SYMBOL 4)) (SYMBOL 5)))
+\end{lstlisting}
+
+
+\begin{figure}
+\centering\includegraphics[width=18.5cm]{AIM-514-ir.pdf}
+\caption{Example of intermediate representation}
+\end{figure}
+
+\section{Software}
+\subsection{Compiler}
+The compiler takes in Lisp code and translates it to a sexp-based
+format understood by the assembler.
+
+The compiler has several functions for compiling certain kinds of
+expressions, and a function (\texttt{process\_toplevel}) that uses the
+former to compile arbitrary expressions.
+
+The output from any of this functions is a sexp in the intermediate
+form described in the previous section.
+
+Symbols are identified by sequences of letters on the source code side
+and by numbers on the processor side. The compiler therefore keeps a
+mapping between symbol names and their numbers. Whenever a new symbol
+is encountered, a new entry is added to this map.
+
+The \texttt{process\_quoted} function handles constants. For example
+if the source code contains \texttt{'(1 2 3)} then
+\texttt{process\_quoted} is called with \texttt{(1 2 3)}. This
+function handles the symbol interning described in the previous
+paragraph, and converts its input to intermediate form.
+
+The \texttt{process\_proc} function handles lambda abstractions. For
+example if the source code contains \texttt{(lambda first (a b) a)}
+then \texttt{process\_proc} is called with \texttt{first},
+\texttt{(a b)}, and \texttt{a}. This function appends the function
+name and arguments to the environment, then processes the body (using
+\texttt{process\_toplevel}) with the new environment.
+
+The \texttt{process\_funcall} function handles function calls. For
+example if the source code contains \texttt{(reverse-list 2 1)} then
+\texttt{process\_funcall} is called with \texttt{reverse-list}, and
+\texttt{(2 1)}. The arguments are first processed (using
+\texttt{process\_toplevel}), then (if the function is not a primitive)
+the function is processed as well.
+
+Finally the \texttt{process\_toplevel} handles any expression by
+figuring out what sort of expression it is and then processing it
+appropriately. Empty lists and \texttt{NIL} become \texttt{(list 0)},
+numbers and \texttt{T} are processed with \texttt{process\_quoted}
+
+Examples of compiler operation can be found in the compiler tests.
+Here are a few of them:
+
+\begin{itemize}
+\item The Lisp expression \texttt{'()} is compiled to \texttt{(LIST 0)}
+\item The Lisp expression \texttt{'(5 foo)} is compiled to
+ \texttt{(LIST (LIST (LIST 0) (SYMBOL 3)) (SYMBOL 4))}. Observe that
+ the CDR comes before the CAR, and symbols are interned:
+ \texttt{'foo} is compiled to \texttt{(SYMBOL 3)} and \texttt{'5} is
+ compiled to \texttt{(SYMBOL 4)}
+\item The Lisp expression \texttt{(if t '(2 3) 'x)} is compiled to
+ \texttt{(IF (LIST (SYMBOL 5) (LIST (LIST (LIST 0) (SYMBOL 3))
+ (SYMBOL 4))) (SYMBOL 2))}. Observe that \texttt{t} is always
+ compiled to \texttt{(SYMBOL 2)}, as mentioned in the section about
+ the memory format.
+\end{itemize}
+
+\subsection{Assembler}
+The assembler takes in an S-expression in the intermediate form, lays
+out the words in memory, and produces a memory dump that can be
+supplied to the processor.
+
+The core of the assembler is a function called \texttt{process} that
+takes an expression in intermediate form and an optional location in
+memory. This function lays out the expression's subexpressions in
+memory and then lays out the expression itself at the given location
+(or at the end of the memory if there is no location given).
+
+The assembler begins by initializing the first 7 elements of the
+memory with the values needed by the processor. After initialization,
+the \texttt{process} function is called on the input expression with
+no location.
+
+Here is how the \texttt{process} function lays out the expression
+$expr$ at location $l$ (where $l$ can be a given memory location or
+simply ``the first free location in memory''):
+
+\begin{itemize}
+\item If $expr$ is \texttt{(type value)}, then it is directly laid out
+ at $l$
+\item If $expr$ is \texttt{(type ptr)}, then \texttt{process} is
+ called recursively to lay \texttt{ptr} out at the first free
+ location in memory (say this is location $loc$). Then \texttt{(type
+ $loc$)} is laid out at $l$.
+\item If $expr$ is \texttt{(type ptr1 ptr2)}, then two consecutive
+ free locations in memory $loc$ and $loc+1$ are reserved,
+ \texttt{process} is recursively called twice to lay \texttt{ptr1} at
+ $loc$ and \texttt{ptr2} at $loc+1$, and finally
+ \texttt{(type $loc$)} is laid out at $l$.
+\end{itemize}
+
+Once again, examples of assembler operations can be found in the
+assembler tests. Two of them:
+
+\begin{itemize}
+\item \texttt{(quoted (symbol 5))} is assembled to \texttt{00 08 00 00
+ 00 00 20 00 20 00 00 08 E0 07 00 00 20 05}. Observe that each word
+ is made of two bytes, the first word (\texttt{00 08}) indicating the
+ length (in words) of the program. The first 4 words are always
+ fixed: they represent in order the CDR of NIL, the CAR of NIL, the
+ CDR of T, and the CAR of T. The 7th word is also a constant, 0,
+ because that is where the processor puts the result. The 5th word is
+ the first free word in memory (which is equal to the length in words
+ of the program), and the 6th word (\texttt{E0 07}) is the expression
+ to be evaluated. In this case, it has type quote and points to
+ memory location 7 (the 8th word, because pointers are 0-indexed). At
+ memory location 7 we have the value \texttt{20 05} which has type
+ symbol and value 5.
+\item \texttt{(call (more (funcall 0) (proc (var -2))) (number 5))} is
+ assembled to \texttt{00 0C 00 00 00 00 20 00 20 00 00 0C C0 07 00 00
+ 00 09 20 05 E0 00 80 0B 5F FE}. Here we want to evaulate the
+ expression \texttt{C0 07} (type ``function call'', address 7). This
+ points to a cons-cell, whose car (at position 8) is \texttt{20 05}
+ (that is, \texttt{(number 5)}) and whose cdr (at position 7) is
+ \texttt{00 09} (type ``more'' and address 9). The ``more'' points to
+ another cons-cell, whose cdr (at position 9) is \texttt{E0 00} (that
+ is, \texttt{(funcall 0)}), and whose car is \texttt{80 0B}: a
+ procedure whose body is at position 11, namely \texttt{5F FE} (that
+ is, \texttt{(var -2)}).
+
+ So the expression is a call to the primitive \texttt{funcall} with
+ arguments \texttt{(lambda l (x) x)} and \texttt{5}. The original
+ program was probably \texttt{((lambda l (x) x) 5)}. Note that this
+ program was compiled with an old version of the compiler that did
+ not intern symbols, which explains why \texttt{5} was compiled to
+ \texttt{(number 5)} and not \texttt{(symbol 3)}.
+\end{itemize}
+
+\subsection{REPL}
+The REPL ties everything together: it reads a program from the user,
+compiles it, assembles it, sends the assembled program to the
+processor, reads the memory dump from the processor, and finally
+prints the result to the screen.
+
+The REPL includes an S-expression pretty-printer that operates on
+memory dumps. As symbols are interned by the compiler, when the
+pretty-printer hits a symbol it only knows its index, and not the
+original name. To print the original name the pretty-printer searches
+the symbol map built by the compiler and pulls the name from there.
+
+The pretty-printer takes a chunk of memory and index, and prints the
+expression at that index. For example, if the memory chunk is
+\texttt{00 00 00 00 20 00 20 00 00 09 00 07 00 07 20 02 00 00 60 00}
+and the index is 6, then the pretty printer will try to print
+\texttt{00 07}, which is a list with car \texttt{00 00} and cdr
+\texttt{20 02}, and the pretty printer prints \texttt{(nil . t)}.
+
+\clearpage
+An example REPL session is:
+
+\begin{lstlisting}
+YULE REPL
+
+* (cons 1 2)
+(1 . 2)
+* (car '(4 5 6))
+4
+* (cdr '(t t t))
+(T T)
+* ((lambda id (x) x) 5)
+5
+* (lambda first (a b) a)
+<CLOSURE>
+* ((lambda first (a b) a) 7 8)
+7
+* (atom 6)
+T
+\end{lstlisting}
+
+\chapter{Evaluation and Testing}
+To make development easier, ensure everything works correctly, and
+prevent regressions there are unit tests for the compiler and
+assembler, and functional tests for the entire project.
+
+Besides these automated tests, manual evaluation (in the beginning,
+precompiling simple expressions and supplying them to the processor as
+the initial value of the memory; later on, manually typing expressions
+in the REPL and looking at the output). When the processor was not
+operating as expected, the GTKWave wave simulator was used to assist
+with debugging. This piece of software takes in a recorded simulation
+of the circuits and displays the values of all signals inside the
+circuit against time. This allows the designer to look at every clock
+cycle in turn and discover where the error occurs.
+
+The process of debugging the processor had the side effect of finding
+inefficiencies in the original design. While \cite{lambda} mentions
+some limitations of the processors, one important limitation that was
+only discovered during debugging is that for every operation that the
+EVAL performs, the result of that operation will be written to new
+locations in memory. This includes ``read-only'' operations such as
+CAR and CDR. If the programmer requests the CAR of a list, a copy of
+the first element will be taken and a pointer to it will be returned.
+Since YULE only has 4096 words of memory, this severely restricts the
+complexity of programs that can be evaluated on it.
+
+Another avenue to ensure the processor works as it should is formal
+verification using model checking tools. Formal verification is
+commonly employed as part of circuit design evaluation because
+mistakes are more difficult to identify, and if found after the chip
+has been built they are very costly to fix (often the chips that were
+built with the bug need to be thrown away). However, building models
+is a very involved process, and devoting effort to formal verification
+of this project would not have allowed the implementation of several
+features. Due to time constraints and knowing that no physical YULE
+chips are built (the project is so far only synthesised to a FPGA),
+testing and manual evaluation was considered sufficient for YULE.
+
+\section{Unit testing}
+The software was tested with 48 unit tests written in Perl using the
+\texttt{Test::More} framework.
+
+The assembler takes in compiled Lisp code and outputs a memory dump in
+one of two formats (binary or Verilog code). Its tests take a
+configuration for the assembler, an input, two expected outputs, and
+(for documentation purposes) the source Lisp code. An example test:
+
+\begin{lstlisting}
+$expbin =
+ '00 0C 00 00 00 00 20 00 20 00 00 0C C0 07'
+ . ' 00 00 00 09 20 05 E0 00 80 0B 5F FE';
+run_test {addr_bits => 13},
+ '(call (more (funcall 0) (proc (var -2))) (number 5))',
+ <<'EOF', $expbin, '((LAMBDA ID (X) X) 5)';
+mem[ 0] <= 0; // (cdr part of NIL)
+mem[ 1] <= 0; // (car part of NIL)
+mem[ 2] <= 16'b0010000000000000; // (cdr part of T)
+mem[ 3] <= 16'b0010000000000000; // (car part of T)
+mem[ 4] <= 16'd12; // (free storage pointer)
+mem[ 5] <= 16'b1100000000000111; // CALL 7
+mem[ 6] <= 0; // (result of computation)
+mem[ 7] <= 16'b0000000000001001; // MORE 9
+mem[ 8] <= 16'b0010000000000101; // NUMBER 5
+mem[ 9] <= 16'b1110000000000000; // FUNCALL 0
+mem[10] <= 16'b1000000000001011; // PROC 11
+mem[11] <= 16'b0101111111111110; // VAR -2
+EOF
+\end{lstlisting}
+
+Here the compiled code \texttt{(call (more (funcall 0) (proc (var -2))) (number 5))}
+is given to the assembler, and its outputs are compared to the binary
+string on the first line and the block of Verilog code.
+
+The tests do not all contain valid assembler inputs. There are a
+series of tests that give invalid inputs to the assembler and expect
+the assembler to raise an exception matching a pattern. Example tests:
+
+\begin{lstlisting}
+expect_error_like { run_test {}, '((type is a list) 5)'}
+ 'Type of toplevel is not atom';
+expect_error_like { run_test {}, '(badtype 5)'}
+ 'No such type';
+expect_error_like { run_test {}, '(5 700000)'}
+ 'Addr too large';
+\end{lstlisting}
+
+On the compiler side, there are 4 tests for the quoting function,
+but the brunt of the tests are pairs of a compiler input (i.e. Lisp
+code) and a compiler output (i.e. a sexp that the assembler
+understands). For each pair the compiler is run on the first element
+and its output is compared with the second. Example such tests:
+
+\begin{lstlisting}
+is_toplevel '(quote 5)', '(SYMBOL 3)';
+is_toplevel '(reverse-list \'a \'a \'b)',
+ '(CALL (MORE (MORE (REVERSE-LIST 0) (SYMBOL 4)) (SYMBOL 3)) (SYMBOL 3))';
+is_toplevel '(if t \'(2 3) \'x)',
+ '(IF (LIST (SYMBOL 5) (LIST (LIST (LIST 0)'
+ . ' (SYMBOL 3)) (SYMBOL 4))) (SYMBOL 2))';
+\end{lstlisting}
+
+As the compiler code includes a function to pretty-print
+S-expressions, there are a few round-trip tests on this function.
+Given a string, it is parsed using the \texttt{Data::SExpression}
+parsing library then it is pretty-printed. The result should match the
+original string.
+
+There are also tests for handling of invalid input, like in the assembler. These include:
+
+\begin{lstlisting}
+expect_error_like { is_toplevel 'x' } 'Variable x not in environment';
+expect_error_like { is_toplevel '(car)' } 'Cannot call primitive car with no arguments';
+\end{lstlisting}
+
+A test coverage tool, \texttt{Devel::Cover}, was ran on the compiler
+and assembler to find statements and branches that were not covered by
+existing unit tests, and new tests were written to cover them. Right
+now \texttt{Devel::Cover} reports 100\% test coverage of the compiler
+and assembler.
+
+\begin{figure}
+ \centering\includegraphics[height=8cm]{devel-cover.png}
+ \caption{Screenshot of \texttt{Devel::Cover} results, showing 100\%
+ test coverage}
+\end{figure}
+
+\section{Functional testing}
+Besides unit tests, the entire system (hardware and software) has
+undergone functional testing. This means that a set of 21 Lisp
+expressions has been prepared, alongside their correct values computed
+using a software Lisp implementation. These values are given to the
+YULE REPL and the test succeeds if the output equals the known correct
+value of the expression.
+
+Here are some example tests:
+\begin{lstlisting}
+'(1 2 3)
+5
+((lambda id (x) x) 5)
+((lambda id (x) x) '(1 2 3))
+(car '(2 3))
+(car (cdr '(4 5 6)))
+((lambda snd (x y) y) 'first 'second)
+
+(cons '(1 2) '(7))
+(car (cons '(1 2) '(7)))
+(cdr (cons '(1 2) '(7)))
+
+((lambda rev (xs) ((lambda reverse-acc (xs acc) (if xs (reverse-acc (cdr xs) (cons (car xs) acc)) acc)) xs '())) '(4 5 6 7))
+\end{lstlisting}
+
+This test suite tries to cover most kinds of valid expressions. It
+includes constants of all kinds, conditionals, lambda abstractions,
+calls to all primitives, calls to user-defined functions, recursive
+calls.
+
+\section{Timing and performance}
+There are three parts to the performance of YULE:
+
+\begin{enumerate}
+\item The efficiency of the software. This refers to the time taken to
+ compile and assemble input programs, which is negligible.
+
+\item The I/O performance, which refers to the time needed to transfer
+ the program from the computer to the processor's memory, plus the
+ time needed to transfer the memory dump from the memory back to the
+ computer.
+
+\item The speed of the processor itself, that is the time/number of
+ cycles that the processor needs to evaluate a given expression.
+\end{enumerate}
+
+The GC runs at 48MHz, while the EVAL only runs when the GC allows it
+to which is at most half of the time.
+
+The UART runs at 4000000 baud, so a bit is sent every 12 cycles of the
+48MHz clock. A byte is made of 11 bits: a start bit, 8 data bits, and
+one stop bit. A word is two bytes, so 22 bits. Therefore 264 cycles
+are needed to transmit one word.
+
+Since the WRITER just sends a full memory dump, the I/O performance is
+proportional not to \texttt{program\_len + result\_len} but to
+\texttt{program\_len + result\_len + intermediate\_results\_len}. As
+evaluation of any expression involves the creation of at least one
+value (the result), for every expression or subexpression evaluated at
+least 264 cycles will be needed to output that result. The EVAL takes
+significantly less than 264 cycles to evaluate a expression (not
+counting its subexpressions), in one test each expression took between
+30 and 90 cycles to evaluate. The processor performance is therefore
+dominated by I/O.
+
+As an example, the program \texttt{((lambda id (x) x) 5)} is 12 bytes
+long, and takes 258 cycles to evaluate. The memory dump is 54 bytes
+long. Therefore of the roughly 17700 cycles needed from beginning to
+end, about 98.5\% are used to do I/O.
+
+\section{A worked example}
+\label{sec:example}
+Here is an example of what happens when a expression is typed into the
+REPL:
+
+\begin{enumerate}
+\item A user types into the REPL the string
+
+\begin{lstlisting}
+(car '(2 3 4))
+\end{lstlisting}
+
+ This is a call to the CAR primitive, with the list \texttt{(2 3 4)}
+ as an argument. We expect the result to be \texttt{2}, the first
+ element of the list.
+
+\item This string is given to the compiler, producing the sexp
+
+\begin{lstlisting}
+(CALL (CAR 0) (LIST (LIST (LIST (LIST 0) (SYMBOL 3)) (SYMBOL 4)) (SYMBOL 5)))
+\end{lstlisting}
+
+ Observe that in this representation the CDR comes before the CAR. So
+ for example ``(LIST (LIST 0) (SYMBOL 3))'' represents a list whose
+ CAR is ``(SYMBOL 3)'' and CDR is ``(LIST 0)'' (that is, nil). This
+ is a list with one element, ``(SYMBOL 3)''. The sexp shown here
+ represents a call to the CAR primitive with one argument. The list
+ has three elements, which are in order \texttt{(SYMBOL 5), (SYMBOL
+ 4), (SYMBOL 3)}.
+
+ In this stage the compiler maps each number to a symbol, in this
+ case \texttt{(SYMBOL 5)} is 2, \texttt{(SYMBOL 4)} is 3, and
+ \texttt{(SYMBOL 3)} is 2. This mapping is remembered so it can be
+ used later by the pretty printer.
+
+\item This sexp is given to the assembler, producing the 16 words long
+ binary string (here displayed in hex, with a space after each 16-bit
+ word)
+
+\begin{lstlisting}
+000F 0000 0000 2000 2000 000F C007 0000 2000 0009 000B 2005 000D 2004 0000 2003
+\end{lstlisting}
+
+ The first word, \texttt{000F}, indicates the length of the program
+ in
+ words (15 words, this does not include this first word).\\
+ The next four words, \texttt{0000 0000 2000 2000}, represent the CDR
+ and CAR of NIL and T respectively. These words are always
+ constant.\\
+ The next word, \texttt{000F}, represents the first unused position
+ in memory. This is always equal to the first word transmitted.\\
+ The next word, \texttt{C007}, represents the expression to be
+ evaluated.\\
+ The next word, \texttt{0000}, is ignored as this is where the
+ processor will place the result of the evaluation.\\
+ The rest of the words are subexpressions or parts of subexpressions
+ of the expression being evaluated.\\
+
+ The expression that is evaluated is \texttt{C007}, which is a CALL
+ whose CDR is at position 7 (\texttt{2000}, meaning \texttt{(CAR 0)})
+ and whose CAR is at
+ position 8 (\texttt{0009}).\\
+ \texttt{0009} is a list with CAR at 10 (\texttt{2005}, meaning
+ \texttt{(SYMBOL 5)}) and CDR at 9 (\texttt{000B}).\\
+ \texttt{000B} is a list with CAR at 12 (\texttt{2004}, meaning
+ \texttt{(SYMBOL 4)}) and CDR at 11 (\texttt{000D}).\\
+ \texttt{000D} is a list with CAR at 14 (\texttt{2003}, meaning
+ \texttt{(SYMBOL 3)}) and CDR at 13 (\texttt{0000}, meaning NIL).
+
+\item This binary string is sent via UART to the FPGA's READER. The
+ READER writes the string (except the first word) into memory,
+ overwriting the previous contents of the memory. It then reports to
+ the controller that it is done, and the controller advances to
+ \texttt{STATE\_RUN}.
+
+\item The EVAL and GC evaluate the program in memory, and then place
+ the result back into memory. The EVAL reports to the controller that
+ it is done, and the controller advances to \texttt{STATE\_WRITE}.
+
+\item The WRITER sends this memory dump via UART back to the REPL
+
+\begin{lstlisting}
+000F C007 2005 2000 0009 000B 2005 000D 2004 0000 2003 0000 4004 2000 0010 0000 0012 0000 0000 0009
+\end{lstlisting}
+
+ Then the WRITER reports to the controller that it is done, and the
+ controller advances to \texttt{STATE\_READ}.
+
+ Observe that this memory dump is similar to the assembler output.
+ The first two words are the 6th and 7th words in the assembler
+ output, the next word is the result of the evaluation, then the next
+ 8 words are words 9th through 16th in the assembler output. The
+ following words are intermediate results computed by the processor.
+
+\item The REPL's pretty printer interpets this string starting with
+ \texttt{2005}, which means \texttt{(SYMBOL 5)}. The pretty printer
+ looks in the compiler's mapping and finds that the 5th symbol was
+ 3, and so the REPL prints
+
+\begin{lstlisting}
+3
+*
+\end{lstlisting}
+
+ The evaluation is complete, and a new prompt is printed so that the
+ user can input another expression.
+\end{enumerate}
+
+\chapter{Conclusions}
+A Lisp machine processor has been built using the original design and
+techniques presented in \cite{lambda}. It has been extended with input
+and output capabilities, and using a modern FPGA it has been
+synthesised on a physical device slightly larger than a USB flash
+drive. This device can be used as a standalone Lisp evaluator, or the
+processor inside it can be included in a more complicated circuit.
+
+Software has been written to help interact with the processor. This
+includes a compiler, an assembler, and a REPL that together make it
+possible for an end-user unfamiliar with hardware design or the
+processor's internals to submit Lisp expressions to the processor and
+get back their values. The software also allows programmers to convert
+Lisp source code to the binary format understood by the processor, so
+that they may later send the binaries to the processor for evaluation.
+
+The processor and software have been tested to ensure they work
+correctly. This has uncovered bugs and inefficiencies in the original
+paper, some of which could not be gleaned from simply reading the
+paper.
+
+The source files for the hardware and software, and also the automated
+tests have been released under an open-source license to make it easy
+for future circuit designers and programmers to use and extend this
+project. They can be found at \url{https://git.ieval.ro/?p=yule.git}.
+
+The original paper \cite{lambda} is one of the influential Lambda
+Papers that defined the Scheme programming language and is an
+important historical artifact for understading how Lisp machine
+processors can be implemented and more generally how tagged
+architectures work. But all details of the processor cannot be
+understood from simply reading the paper, and most readers would not
+follow by attempting to implement what is described there. This
+projects brings a tangible implementation into the open, which shows
+the limitations of the design to people interested in this design and
+makes it possible to solve this limitations and extend the processor
+beyond its original scope.
+
+\section{Reflections}
+Now that the project is finished, it is worth revisiting ideas I had
+in the beginning that were not ultimately useful.
+
+The original concept had the processor run on a typical development
+board, with the software running on a Raspberry PI. The board and the
+Raspberry PI would be connected through jumper wires, and the UART
+circuitry on the Raspberry PI would be used by the software to talk to
+the processor.
+
+This idea would have produced a much harder to use YULE. Not only
+would the user have to ssh into a Raspberry PI to do anything useful,
+but also the equipment would take more space (both boards are larger
+than the iCEstick). Once I tried the iCEstick and found that
+everything can be done just as well with it, it replaced the two
+boards and made the project easier to use (albeit slightly harder to
+debug, as the iCEstick only has 5 LEDs).
+
+Some code had to be rewritten, sometimes multiple times. The compiler
+was originally written in Common Lisp, as it is the best suited
+language for manipulation of S-expressions, especially Lisp code. This
+meant a working project was obtained more quickly, but then the
+compiler had to be rewritten in another language; if the user has a
+software Lisp implementation already, why would they need YULE? I
+chose Perl as the reimplementation language, as the assembler was
+already written in Perl and it is widely-available, most systems
+coming with a Perl interpreter out of the box.
+
+Throughout development of the hardware part, timing problems were a
+mainstay. The first ones related to the interactions between the
+processor and the memory (the memory was clocked, but the processor
+expected a combinational RAM). What fixed this problem was to run the
+memory at twice the speed of the rest of the processor. At some point,
+a decision was taken to run the GC and EVAL on different clocks (both
+ran at one quarter the speed of the master clock, but one of the
+clocks was delayed by half a cycle. The positive edge on one clock
+would happen midway between a positive edge and a negative edge on the
+other one). This proved to be unwise, as sometimes values sent by one
+module to the other would be cleared before the destination module
+managed to read them.
+
+GTKWave proved to be very useful in debugging these timing issues, as
+the exact point where the issue began was easy to identify and I could
+see why the issue was happening. A workaround for this was to add a
+latch on each side of the common E bus that remembered the value sent
+long enough for the receiving module to see it.
+
+All timing problems were fixed more cleanly in the end when an attempt
+to simplify the clocks was made. First GC and EVAL were changed to use
+the same clock, which removed the need for the latches, and then the
+memory was changed to use the negative edge of the clock instead of
+the positive edge, which meant no more clock division code had to be
+used.
+
+\section{Future work}
+There are several ways to extend this project.
+
+One idea is to fix the noted limitations: the ATOM primitive considers
+NIL to not be an atom, and there is no EQ primitive that compares
+symbols/other objects. The latter problem means that all symbols are
+indistinguishable (note: NIL can still be distinguished from T and
+other symbols, but NIL is not a symbol). To introduce equality a new
+signal needs to be added to the EVAL that compares (for example) the
+value on the E bus with the value of a fixed register, possibly a
+newly added one. Then (EQ A B) would store A in the register, load B
+on the E bus and compare them.
+
+Once equality is implemented, it becomes possible to implement the
+EVAL function that evaluates an arbitrary Lisp expression.
+
+Two more involved instruction set improvements are adding arithmetic
+operations, and input/output. Without arithmetic primitives one has to
+rely on Church numerals, which encodes numbers as lambda abstractions
+and is very inefficient. Input/output primitives would allow programs
+to receive data at runtime over the UART and send data back before
+evaluation is finished. This enables long-running useful programs, for
+example with input/output and equality a REPL can be written (which
+relies on the EVAl function mentioned above).
+
+On the software side, the assembler can support optimizations and then
+the REPL can be extended with a core image. The main optimization
+needed in the assembler is common subexpression elimination. The
+processor never overwrites a value in memory with another value (other
+than overwriting \texttt{mem[6]} with the result of the evaluation),
+so it is safe to share any identical subexpressions. For example, if
+the user inputs the program \texttt{(cons (car '(1 2 3 4)) (cdr '(0 2
+ 3 4)))}, then when the assembler should share the tails of the two
+lists, meaning the second list should compile to \texttt{(LIST (LIST
+ X) (SYMBOL Y))} where X is a pointer to where the second element of
+the first list is stored. This makes long programs significantly
+shorter. Note that no compiler changes are required to implement this,
+as the assembler can just remember all expressions and subexpressions
+it has assembler so far including their locations, and whenever a new
+expression needs to be assembler it can be replaced with a pointer to
+where the same expression has been placed before.
+
+Once this optimization is implemented, the REPL can gain core image
+support. Suppose the user enters the expression \texttt{expr}. Instead
+of sending \texttt{assemble(compile(expr))} to the processor, the REPL
+can remember the last expression sent (or the last memory dump
+received), then append \texttt{assemble(compile(expr))} to that
+previous expression. This way \texttt{expr} can refer to previously
+defined expressions, as long as the REPL or compiler has a way to name
+previously supplied instructions, for example via a \texttt{define}
+special form, via the standard REPL variables (\texttt{+, ++, +++}),
+or by sequentially numbering all expressions submitted by the user.
+
+Returning to hardware, a potential future project is to add actual
+hardware garbage collection to the GC component. At the moment the
+design does no garbage collection, the processor only has 4096 words
+of RAM available, and evaluation is quite memory-inefficient. Adding
+garbage collection would make more complicated programs possible
+despite the limited RAM. One way to implement this is to add a small
+microprocessor to the design which is preprogrammed with a garbage
+collection algorithm (simple choices are a stop-and-copy collector or
+Cheney's algorithm). When the free space pointer gets too high, the
+EVAL and GC are stopped, and the new microprocessor is started up so
+it can perform garbage collection, compact the memory, and update the
+free space pointer. The EVAL/GC registers would have to be updated as
+well. Then the microprocessor can be stopped, EVAL and GC be started
+up again and evaluation can continue. Note that a non-moving collector
+is not sufficient: the GC allocates new words only at the very end of
+the memory, so it cannot benefit from free ``gaps'' in the middle of
+the memory.
+
+\begin{thebibliography}{99}
+\bibitem{lambda} Design of LISP-Based Processors (1979), available at
+ \url{http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-514.pdf}
+\bibitem{osdvu} \url{https://opencores.org/project/osdvu}
+\bibitem{gtkwave} \url{http://gtkwave.sourceforge.net/}
+\bibitem{icestorm} \url{http://www.clifford.at/icestorm/}
+\end{thebibliography}
+\end{document}
projects / yule.git / commitdiff
