Skip to content

Instantly share code, notes, and snippets.

@kenwebb
Last active August 29, 2015 13:58
Show Gist options
  • Save kenwebb/10419442 to your computer and use it in GitHub Desktop.
Save kenwebb/10419442 to your computer and use it in GitHub Desktop.
SICP - A Simulator for Digital Circuits
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Fri Apr 11 2014 09:51:00 GMT-0400 (EDT)-->
<XholonWorkbook>
<Notes><![CDATA[
Xholon
------
Title: SICP - A Simulator for Digital Circuits
Description:
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 10419442
Keywords:
My Notes
--------
This Xholon Workbook explores the `Simulator for Digital Circuits` model
described in section 3.3.4 of Abelson and Sussman's
`Structure and Interpretation of Computer Programs, second edition` book[1].
The book provides Scheme[8] code for one possible implementation of the model.
I've jotted down a few ideas in my journal, but I'm not yet sure which of
several Xholon-based approaches I'll proceed with.
The book is freely available online in several formats, including PDF[3], HTML5, and SVG.
This workbook includes one or more of the SVG images created by Andres Raba[4].
Goal:
- write as little code as possible
- how much can I do with structure only?
A Petri Net approach
--------------------
One promising approach is to implement the circuits as Petri Nets,
a mechanism that Xholon already supports.
Petri Net places represent the wires, which carry a signal with a value of 0 or 1.
Petri Net transitions represent the primitive functions,
which act on the values in the wires.
The circuits themselves are just containers for the primitive functions.
References
----------
(1) http://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs
(2) http://sicpebook.wordpress.com/
(3) http://sicpebook.files.wordpress.com/2012/11/sicp.pdf
(4) https://github.com/sarabander/sicp
(5) https://github.com/robertberry/SICP-Exercises
(6) https://github.com/zodiac/isicp
(7) http://sarabander.github.io/sicp/
(8) http://en.wikipedia.org/wiki/Scheme_%28programming_language%29
]]></Notes>
<_-.XholonClass>
<DigitalSystem/>
<Wire superClass="PlacePN"/>
<PrimitiveFunctionBox superClass="TransitionPN">
<Inverter/>
<AndGate/>
<OrGate/>
</PrimitiveFunctionBox>
<!-- containers -->
<Circuit>
<HalfAdder/>
<FullAdder/>
</Circuit>
</_-.XholonClass>
<xholonClassDetails>
</xholonClassDetails>
<DigitalSystem>
<Wire roleName="a" token="1"/>
<Wire roleName="b" token="1"/>
<Wire roleName="s"/>
<Wire roleName="c"/>
<!-- Truth Table expected after several time steps when the circuit stabilizes
inputs outputs
a b s c
1 1 0 1
1 0 1 0
0 1 1 0
0 0 0 0
-->
<HalfAdder>
<Wire roleName="d"/>
<Wire roleName="e"/>
<OrGate kineticsType="KINETICS_LOGIC_OR"> <!-- KINETICS_LOGIC_OR 9 -->
<InputArcs>
<InputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='a']"/>
<InputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='b']"/>
</InputArcs>
<OutputArcs>
<OutputArc weight="1" connector="ancestor::HalfAdder/Wire[@roleName='d']"/>
</OutputArcs>
</OrGate>
<AndGate kineticsType="KINETICS_LOGIC_AND"> <!-- KINETICS_LOGIC_AND 8 -->
<InputArcs>
<InputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='a']"/>
<InputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='b']"/>
</InputArcs>
<OutputArcs>
<OutputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='c']"/>
</OutputArcs>
</AndGate>
<AndGate kineticsType="KINETICS_LOGIC_AND"> <!-- KINETICS_LOGIC_AND 8 -->
<InputArcs>
<InputArc weight="1" connector="ancestor::HalfAdder/Wire[@roleName='d']"/>
<InputArc weight="1" connector="ancestor::HalfAdder/Wire[@roleName='e']"/>
</InputArcs>
<OutputArcs>
<OutputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='s']"/>
</OutputArcs>
</AndGate>
<Inverter kineticsType="KINETICS_LOGIC_NOT"> <!-- KINETICS_LOGIC_NOT 10 -->
<InputArcs>
<InputArc weight="1" connector="ancestor::DigitalSystem/Wire[@roleName='c']"/>
</InputArcs>
<OutputArcs>
<OutputArc weight="1" connector="ancestor::HalfAdder/Wire[@roleName='e']"/>
</OutputArcs>
</Inverter>
</HalfAdder>
<PetriNet roleName="sicpDigitalCircuit01">
<QueueTransitions connector="ancestor::DigitalSystem"/>
<AnalysisPetriNet/>
<AnalysisCRN/>
<AnalysisCat/>
</PetriNet>
</DigitalSystem>
<Blockbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
// TODO ?
]]></Blockbehavior>
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<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" preserveAspectRatio="xMinYMin meet" viewBox="0 0 562 222" id="svg4049" version="1.1">
<defs id="defs4051"/>
<metadata id="metadata_3.25">
<!--
<rdf:RDF>
<cc:Work rdf:about="">
<dc:format>image/svg+xml</dc:format>
<dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage"></dc:type>
<dc:title></dc:title>
<cc:license rdf:resource="http://creativecommons.org/licenses/by-sa/3.0/"></cc:license>
<dc:description>Based on the diagram in Abelson, Sussman &amp; Sussman's "Structure and Interpretation of Computer Programs", 2nd ed.</dc:description>
<dc:source>http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_fig_3.25</dc:source>
<dc:creator>
<cc:Agent>
<dc:title>Andres Raba</dc:title>
</cc:Agent>
</dc:creator>
<dc:date>2012-11-17</dc:date>
<dc:subject>
<rdf:Bag>
<rdf:li>half-adder</rdf:li>
<rdf:li>circuit</rdf:li>
</rdf:Bag>
</dc:subject>
</cc:Work>
<cc:License rdf:about="http://creativecommons.org/licenses/by-sa/3.0/">
<cc:permits rdf:resource="http://creativecommons.org/ns#Reproduction"></cc:permits>
<cc:permits rdf:resource="http://creativecommons.org/ns#Distribution"></cc:permits>
<cc:requires rdf:resource="http://creativecommons.org/ns#Notice"></cc:requires>
<cc:requires rdf:resource="http://creativecommons.org/ns#Attribution"></cc:requires>
<cc:permits rdf:resource="http://creativecommons.org/ns#DerivativeWorks"></cc:permits>
<cc:requires rdf:resource="http://creativecommons.org/ns#ShareAlike"></cc:requires>
</cc:License>
</rdf:RDF>
-->
</metadata>
<g transform="scale(0.5, 0.5)">
<g transform="translate(-55.032221,-71.625)" id="layer8" style="display:inline">
<path id="Chameleon/DigitalSystem/HalfAdder" d="m 145.24355,77.12029 379.90965,0 c 11.45456,0 15.27274,3.818187 15.27274,15.272744 l 0,179.454806 c 0,11.45456 -3.81818,15.27275 -15.27274,15.27275 l -379.90965,0 c -11.41552,0 -15.27275,-3.68678 -15.27275,-15.27275 l 0,-179.454806 c 0,-11.454557 3.81819,-15.272744 15.27275,-15.272744 z" id="rect4940" style="fill:#e8e8e8;fill-opacity:1;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
</g>
<g transform="translate(-55.032221,-71.625)" id="layer2" style="display:inline">
<path d="m 338.06201,167.74431 c 1.85276,0 5.72729,1.9091 43.90916,21.00003 2.39122,1.30645 2.45149,4.30031 0,5.72728 -38.18187,19.09094 -42.05363,21.00003 -43.90916,21.00003 -1.87375,0 -3.38224,-1.50847 -3.38224,-3.38224 l 0,-40.96283 c 0,-1.87378 1.50849,-3.38227 3.38224,-3.38227 z" id="Chameleon/DigitalSystem/HalfAdder/Inverter" style="fill:#ffffff;fill-opacity:1;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 458.33492,115.30216 19.09093,0 c 34.36369,0 34.36369,47.72734 0,47.72734 l -19.09093,0 c -1.87376,0 -3.38225,-1.50847 -3.38225,-3.38224 l 0,-40.96284 c 0,-1.87377 1.50849,-3.38226 3.38225,-3.38226 z" id="Chameleon/DigitalSystem/HalfAdder/AndGate[2]" style="fill:#ffffff;fill-opacity:1;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 503.36973,139.26806 75.23809,0" id="path5898-9" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 227.33458,215.42734 19.09094,0 c 34.36368,0 34.36368,47.72735 0,47.72735 l -19.09094,0 c -1.87376,0 -3.38225,-1.50847 -3.38225,-3.38225 l 0,-40.96283 c 0,-1.87378 1.50849,-3.38227 3.38225,-3.38227 z" id="Chameleon/DigitalSystem/HalfAdder/AndGate[1]" style="fill:#ffffff;fill-opacity:1;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 91.78893,253.60922 131.89793,0" id="path5898-5" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 272.42964,239.39325 306.17818,0" id="path5898-9-7" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 320.88017,124.84763 133.81735,0" id="path5898-11" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 454.69752,153.48403 -23.08992,0 c -3.81818,0 -5.72728,1.9091 -5.72728,5.72728 l 0,26.72731 c 0,3.81819 -1.90909,5.72729 -5.72728,5.72729 l -24.30685,0" id="path5898-9-7-4" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 91.78893,110.42719 172.58548,0" id="path5898-11-5" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 334.41429,191.66591 -23.07959,0 c -3.81819,0 -5.72728,1.90909 -5.72728,5.72728 l 0,42.00006" id="path5898-9-7-4-2" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 196.78908,110.46125 0,108.95469 c 0,3.81819 1.90909,5.72728 5.79546,5.72728 l 21.10232,0" id="path5898-11-5-2" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:butt;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 264.33054,139.06232 -96.17786,0 c -3.81819,0 -5.72729,2.11484 -5.72729,5.93302 l 0,107.76156" id="path5898-9-7-4-6" style="fill:none;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"/>
<path d="m 259.78917,100.91572 22.90913,0 c 19.09093,0 32.45459,11.45457 38.18187,23.86368 -5.72728,12.4091 -19.09094,23.86367 -38.18187,23.86367 l -22.90913,0 c 9.54547,-13.36366 9.54547,-34.36369 0,-47.72735 z" id="Chameleon/DigitalSystem/HalfAdder/OrGate" style="fill:#ffffff;fill-opacity:1;stroke:#383838;stroke-width:1.01467574;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 212,188.36218 a 1,1 0 1 1 -2,0 1,1 0 1 1 2,0 z" transform="matrix(1.9090937,0,0,1.9090937,-97.211347,-120.2078)" id="path4802-7" style="fill:#383838;fill-opacity:1;stroke:#383838;stroke-width:0.70866144;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 212,188.36218 a 1,1 0 1 1 -2,0 1,1 0 1 1 2,0 z" transform="matrix(1.9090937,0,0,1.9090937,-206.20014,-249.1739)" id="path4802-9-9" style="fill:#383838;fill-opacity:1;stroke:#383838;stroke-width:0.70866144;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 212,188.36218 a 1,1 0 1 1 -2,0 1,1 0 1 1 2,0 z" transform="matrix(1.9090937,0,0,1.9090937,-240.39337,-105.99187)" id="path4802-9-0" style="fill:#383838;fill-opacity:1;stroke:#383838;stroke-width:0.70866144;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
<path d="m 285.5625,209.86218 a 3.0625,3.0625 0 1 1 -6.125,0 3.0625,3.0625 0 1 1 6.125,0 z" transform="matrix(1.9090937,0,0,1.9090937,-149.59211,-209.03857)" id="path3164" style="fill:#ffffff;fill-opacity:1;stroke:#383838;stroke-width:0.53149605;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0;display:inline"/>
</g>
<g transform="translate(-55.032221,-71.625)" id="layer3" style="display:inline">
<text x="328.51654" y="113.39307" id="text4958" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:start;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="328.51654" y="113.39307" id="tspan4960">D</tspan></text>
<text x="402.97119" y="180.21135" id="text4962" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:start;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="402.97119" y="180.21135" id="tspan4964">E</tspan></text>
<text x="82.243462" y="117.21126" id="text4942" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:end;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:end;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="82.243462" y="117.21126" id="tspan4944">A</tspan></text>
<text x="82.243462" y="260.39328" id="text4946" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:end;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:end;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="82.243462" y="260.39328" id="tspan4948">B</tspan></text>
<text x="588.15326" y="145.84766" id="text4950" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:start;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="588.15326" y="145.84766" id="tspan4952">S</tspan></text>
<text x="588.15326" y="247.02963" id="text4954" xml:space="preserve" style="font-size:24.81821823px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:start;fill:#383838;fill-opacity:1;stroke:none;display:inline;font-family:Linux Biolinum O;-inkscape-font-specification:Linux Biolinum O"><tspan x="588.15326" y="247.02963" id="tspan4956">C</tspan></text>
</g>
</g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
</XholonWorkbook>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment