<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"
><head
><title
>Implementing Pointer Algorithms in Haskell </title
><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"
/><meta name="generator" content="pandoc"
/><meta name="author" content="Péter Diviánszky"
/><meta name="date" content="CEFP 2009, Komarno"
/><style type="text/css"
>
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode, table.sourceCode pre
{ margin: 0; padding: 0; border: 0; vertical-align: baseline; border: none; }
td.lineNumbers { border-right: 1px solid #AAAAAA; text-align: right; color: #AAAAAA; padding-right: 5px; padding-left: 5px; }
td.sourceCode { padding-left: 5px; }
pre.sourceCode { }
pre.sourceCode span.Normal { }
pre.sourceCode span.Keyword { color: #007020; font-weight: bold; }
pre.sourceCode span.DataType { color: #902000; }
pre.sourceCode span.DecVal { color: #40a070; }
pre.sourceCode span.BaseN { color: #40a070; }
pre.sourceCode span.Float { color: #40a070; }
pre.sourceCode span.Char { color: #4070a0; }
pre.sourceCode span.String { color: #4070a0; }
pre.sourceCode span.Comment { color: #60a0b0; font-style: italic; }
pre.sourceCode span.Others { color: #007020; }
pre.sourceCode span.Alert { color: red; font-weight: bold; }
pre.sourceCode span.Function { color: #06287e; }
pre.sourceCode span.RegionMarker { }
pre.sourceCode span.Error { color: red; font-weight: bold; }
</style
><!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<style type="text/css" media="projection" id="slideProj">
/* Do not edit or override these styles! The system will likely break if you do. */
div#header, div#footer, div#controls, .slide {position: absolute;}
html>body div#header, html>body div#footer,
html>body div#controls, html>body .slide {position: fixed;}
.handout {display: none;}
.layout {display: block;}
.slide, .hideme, .incremental {visibility: hidden;}
#slide0 {visibility: visible;}
/* The following styles size, place, and layer the slide components.
Edit these if you want to change the overall slide layout.
The commented lines can be uncommented (and modified, if necessary)
to help you with the rearrangement process. */
/* target = 1024x768 */
/* img { float: right; padding-left: 10%; padding-bottom: 30px } */
div#header, div#footer, .slide {width: 100%; top: 0; left: 0;}
div#header {top: 0; height: 3em; z-index: 1;}
div#footer {top: auto; bottom: 0; height: 2.5em; z-index: 5;}
.slide {top: 0; width: 92%; padding: 3.5em 4% 4%; z-index: 2; list-style: none;}
div#controls {left: 50%; bottom: 0; width: 50%; z-index: 100;}
div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;
margin: 0;}
#currentSlide {position: absolute; width: 10%; left: 45%; bottom: 1em; z-index: 10;}
html>body #currentSlide {position: fixed;}
/*
div#header {background: #FCC;}
div#footer {background: #CCF;}
div#controls {background: #BBD;}
div#currentSlide {background: #FFC;}
*/
/* Following are the presentation styles -- edit away! */
body {background: #FFF url(bodybg.gif) -16px 0 no-repeat; color: #000; font-size: 2em;}
:link, :visited {text-decoration: none; color: #00C;}
#controls :active {color: #88A !important;}
#controls :focus {outline: 1px dotted #227;}
h1, h2, h3, h4 {font-size: 100%; margin: 0; padding: 0; font-weight: inherit;}
ul, pre {margin: 0; line-height: 1em;}
html, body {margin: 0; padding: 0;}
blockquote, q {font-style: italic;}
blockquote {padding: 0 2em 0.5em; margin: 0 1.5em 0.5em; text-align: center; font-size: 1em;}
blockquote p {margin: 0;}
blockquote i {font-style: normal;}
blockquote b {display: block; margin-top: 0.5em; font-weight: normal; font-size: smaller; font-style: normal;}
blockquote b i {font-style: italic;}
kbd {font-weight: bold; font-size: 1em;}
sup {font-size: smaller; line-height: 1px;}
.slide code {padding: 2px 0.25em; font-weight: bold; color: #533;}
.slide code.bad, code del {color: red;}
.slide code.old {color: silver;}
.slide pre {padding: 0; margin: 0.25em 0 0.5em 0.5em; color: #533; font-size: 90%;}
.slide pre code {display: block;}
.slide ul {margin-left: 5%; margin-right: 7%; list-style: disc;}
.slide li {margin-top: 0.75em; margin-right: 0;}
.slide ul ul {line-height: 1;}
.slide ul ul li {margin: .2em; font-size: 85%; list-style: square;}
.slide img.leader {display: block; margin: 0 auto;}
div#header, div#footer {background: #EEE; color: #AAB;
font-family: Verdana, Helvetica, sans-serif;}
div#header {background: #EEE url(bodybg.gif) -16px 0 no-repeat;
line-height: 1px;}
div#footer {font-size: 0.5em; font-weight: bold; padding: 1em 0;}
#footer h1, #footer h2 {display: block; padding: 0 1em;}
#footer h2 {font-style: italic;}
div.long {font-size: 0.75em;}
.slide h1 {position: absolute; top: 0.7em; left: 0px; z-index: 1;
margin: 0; padding: 0.3em 0 0 50px; white-space: nowrap;
font: bold 150%/1em Helvetica, sans-serif;
color: #028; background: #EEE;}
.slide h3 {font-size: 130%;}
h1 abbr {font-variant: small-caps;}
div#controls {position: absolute; left: 50%; bottom: 0;
width: 50%;
text-align: right; font: bold 0.9em Verdana, Helvetica, sans-serif;}
html>body div#controls {position: fixed; padding: 0 0 1em 0;
top: auto;}
div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;
margin: 0; padding: 0;}
#controls #navLinks a {padding: 0; margin: 0 0.5em;
background: #EEE; border: none; color: #779;
cursor: pointer;}
#controls #navList {height: 1em;}
#controls #navList #jumplist {position: absolute; bottom: 0; right: 0; background: #DDD; color: #227;}
#currentSlide {text-align: center; font-size: 0.5em; color: #449;}
#slide0 {padding-top: 3.5em; font-size: 90%;}
#slide0 h1 {position: static; margin: 1em 0 0; padding: 0;
font: bold 2em Helvetica, sans-serif; white-space: normal;
color: #000; background: transparent;}
#slide0 h2 {font: bold italic 1em Helvetica, sans-serif; margin: 0.25em;}
#slide0 h3 {margin-top: 1.5em; font-size: 1.5em;}
#slide0 h4 {margin-top: 0; font-size: 1em;}
ul.urls {list-style: none; display: inline; margin: 0;}
.urls li {display: inline; margin: 0;}
.note {display: none;}
.external {border-bottom: 1px dotted gray;}
html>body .external {border-bottom: none;}
.external:after {content: " \274F"; font-size: smaller; color: #77B;}
.incremental, .incremental *, .incremental *:after {color: #DDE; visibility: visible;}
img.incremental {visibility: hidden;}
.slide .current {color: #B02;}
/* diagnostics
li:after {content: " [" attr(class) "]"; color: #F88;}
*/
</style>
<style type="text/css" media="projection" id="operaFix">
/* DO NOT CHANGE THESE unless you really want to break Opera Show */
.slide {
visibility: visible !important;
position: static !important;
page-break-before: always;
}
#slide0 {page-break-before: avoid;}
</style>
<style type="text/css" media="screen" id="outlineStyle">
/* don't change this unless you want the layout stuff to show up in the outline view! */
.layout div, #footer *, #controlForm * {display: none;}
#footer, #controls, #controlForm, #navLinks, #toggle {
display: block; visibility: visible; margin: 0; padding: 0;}
#toggle {float: right; padding: 0.5em;}
html>body #toggle {position: fixed; top: 0; right: 0;}
/* making the outline look pretty-ish */
#slide0 h1, #slide0 h2, #slide0 h3, #slide0 h4 {border: none; margin: 0;}
#slide0 h1 {padding-top: 1.5em;}
.slide h1 {margin: 1.5em 0 0; padding-top: 0.25em;
border-top: 1px solid #888; border-bottom: 1px solid #AAA;}
#toggle {border: 1px solid; border-width: 0 0 1px 1px; background: #FFF;}
</style>
<style type="text/css" media="print" id="slidePrint">
/* The following rule is necessary to have all slides appear in print! DO NOT REMOVE IT! */
.slide, ul {page-break-inside: avoid; visibility: visible !important;}
h1 {page-break-after: avoid;}
body {font-size: 12pt; background: white;}
* {color: black;}
#slide0 h1 {font-size: 200%; border: none; margin: 0.5em 0 0.25em;}
#slide0 h3 {margin: 0; padding: 0;}
#slide0 h4 {margin: 0 0 0.5em; padding: 0;}
#slide0 {margin-bottom: 3em;}
h1 {border-top: 2pt solid gray; border-bottom: 1px dotted silver;}
.extra {background: transparent !important;}
div.extra, pre.extra, .example {font-size: 10pt; color: #333;}
ul.extra a {font-weight: bold;}
p.example {display: none;}
#header {display: none;}
#footer h1 {margin: 0; border-bottom: 1px solid; color: gray; font-style: italic;}
#footer h2, #controls {display: none;}
/* The following rule keeps the layout stuff out of print. Remove at your own risk! */
.layout, .layout * {display: none !important;}
</style>
<script type="text/javascript">
// S5 v1.1 slides.js -- released into the Public Domain
//
// Please see http://www.meyerweb.com/eric/tools/s5/credits.html for information
// about all the wonderful and talented contributors to this code!
var undef;var slideCSS='';var snum=0;var smax=1;var incpos=0;var number=undef;var s5mode=true;var defaultView='slideshow';var controlVis='visible';var isIE=navigator.appName=='Microsoft Internet Explorer'&&navigator.userAgent.indexOf('Opera')<1?1:0;var isOp=navigator.userAgent.indexOf('Opera')>-1?1:0;var isGe=navigator.userAgent.indexOf('Gecko')>-1&&navigator.userAgent.indexOf('Safari')<1?1:0;function hasClass(object,className){if(!object.className)return false;return(object.className.search('(^|\\s)'+className+'(\\s|$)')!=-1);}
function hasValue(object,value){if(!object)return false;return(object.search('(^|\\s)'+value+'(\\s|$)')!=-1);}
function removeClass(object,className){if(!object)return;object.className=object.className.replace(new RegExp('(^|\\s)'+className+'(\\s|$)'),RegExp.$1+RegExp.$2);}
function addClass(object,className){if(!object||hasClass(object,className))return;if(object.className){object.className+=' '+className;}else{object.className=className;}}
function GetElementsWithClassName(elementName,className){var allElements=document.getElementsByTagName(elementName);var elemColl=new Array();for(var i=0;i<allElements.length;i++){if(hasClass(allElements[i],className)){elemColl[elemColl.length]=allElements[i];}}
return elemColl;}
function isParentOrSelf(element,id){if(element==null||element.nodeName=='BODY')return false;else if(element.id==id)return true;else return isParentOrSelf(element.parentNode,id);}
function nodeValue(node){var result="";if(node.nodeType==1){var children=node.childNodes;for(var i=0;i<children.length;++i){result+=nodeValue(children[i]);}}
else if(node.nodeType==3){result=node.nodeValue;}
return(result);}
function slideLabel(){var slideColl=GetElementsWithClassName('*','slide');var list=document.getElementById('jumplist');smax=slideColl.length;for(var n=0;n<smax;n++){var obj=slideColl[n];var did='slide'+n.toString();obj.setAttribute('id',did);if(isOp)continue;var otext='';var menu=obj.firstChild;if(!menu)continue;while(menu&&menu.nodeType==3){menu=menu.nextSibling;}
if(!menu)continue;var menunodes=menu.childNodes;for(var o=0;o<menunodes.length;o++){otext+=nodeValue(menunodes[o]);}
list.options[list.length]=new Option(n+' : '+otext,n);}}
function currentSlide(){var cs;if(document.getElementById){cs=document.getElementById('currentSlide');}else{cs=document.currentSlide;}
cs.innerHTML='<span id="csHere">'+snum+'<\/span> '+'<span id="csSep">\/<\/span> '+'<span id="csTotal">'+(smax-1)+'<\/span>';if(snum==0){cs.style.visibility='hidden';}else{cs.style.visibility='visible';}}
function go(step){if(document.getElementById('slideProj').disabled||step==0)return;var jl=document.getElementById('jumplist');var cid='slide'+snum;var ce=document.getElementById(cid);if(incrementals[snum].length>0){for(var i=0;i<incrementals[snum].length;i++){removeClass(incrementals[snum][i],'current');removeClass(incrementals[snum][i],'incremental');}}
if(step!='j'){snum+=step;lmax=smax-1;if(snum>lmax)snum=lmax;if(snum<0)snum=0;}else
snum=parseInt(jl.value);var nid='slide'+snum;var ne=document.getElementById(nid);if(!ne){ne=document.getElementById('slide0');snum=0;}
if(step<0){incpos=incrementals[snum].length}else{incpos=0;}
if(incrementals[snum].length>0&&incpos==0){for(var i=0;i<incrementals[snum].length;i++){if(hasClass(incrementals[snum][i],'current'))
incpos=i+1;else
addClass(incrementals[snum][i],'incremental');}}
if(incrementals[snum].length>0&&incpos>0)
addClass(incrementals[snum][incpos-1],'current');ce.style.visibility='hidden';ne.style.visibility='visible';jl.selectedIndex=snum;currentSlide();number=0;}
function goTo(target){if(target>=smax||target==snum)return;go(target-snum);}
function subgo(step){if(step>0){removeClass(incrementals[snum][incpos-1],'current');removeClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos],'current');incpos++;}else{incpos--;removeClass(incrementals[snum][incpos],'current');addClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos-1],'current');}}
function toggle(){var slideColl=GetElementsWithClassName('*','slide');var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');if(!slides.disabled){slides.disabled=true;outline.disabled=false;s5mode=false;fontSize('1em');for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='visible';}}else{slides.disabled=false;outline.disabled=true;s5mode=true;fontScale();for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='hidden';}
slideColl[snum].style.visibility='visible';}}
function showHide(action){var obj=GetElementsWithClassName('*','hideme')[0];switch(action){case's':obj.style.visibility='visible';break;case'h':obj.style.visibility='hidden';break;case'k':if(obj.style.visibility!='visible'){obj.style.visibility='visible';}else{obj.style.visibility='hidden';}
break;}}
function keys(key){if(!key){key=event;key.which=key.keyCode;}
if(key.which==84){toggle();return;}
if(s5mode){switch(key.which){case 10:case 13:if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;if(number!=undef){goTo(number);break;}
case 32:case 34:case 39:case 40:if(number!=undef){go(number);}else if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}
break;case 33:case 37:case 38:if(number!=undef){go(-1*number);}else if(!incrementals[snum]||incpos<=0){go(-1);}else{subgo(-1);}
break;case 36:goTo(0);break;case 35:goTo(smax-1);break;case 67:showHide('k');break;}
if(key.which<48||key.which>57){number=undef;}else{if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;number=(((number!=undef)?number:0)*10)+(key.which-48);}}
return false;}
function clicker(e){number=undef;var target;if(window.event){target=window.event.srcElement;e=window.event;}else target=e.target;if(target.getAttribute('href')!=null||hasValue(target.rel,'external')||isParentOrSelf(target,'controls')||isParentOrSelf(target,'embed')||isParentOrSelf(target,'object'))return true;if(!e.which||e.which==1){if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}}}
function findSlide(hash){var target=null;var slides=GetElementsWithClassName('*','slide');for(var i=0;i<slides.length;i++){var targetSlide=slides[i];if((targetSlide.name&&targetSlide.name==hash)||(targetSlide.id&&targetSlide.id==hash)){target=targetSlide;break;}}
while(target!=null&&target.nodeName!='BODY'){if(hasClass(target,'slide')){return parseInt(target.id.slice(5));}
target=target.parentNode;}
return null;}
function slideJump(){if(window.location.hash==null)return;var sregex=/^#slide(\d+)$/;var matches=sregex.exec(window.location.hash);var dest=null;if(matches!=null){dest=parseInt(matches[1]);}else{dest=findSlide(window.location.hash.slice(1));}
if(dest!=null)
go(dest-snum);}
function fixLinks(){var thisUri=window.location.href;thisUri=thisUri.slice(0,thisUri.length-window.location.hash.length);var aelements=document.getElementsByTagName('A');for(var i=0;i<aelements.length;i++){var a=aelements[i].href;var slideID=a.match('\#slide[0-9]{1,2}');if((slideID)&&(slideID[0].slice(0,1)=='#')){var dest=findSlide(slideID[0].slice(1));if(dest!=null){if(aelements[i].addEventListener){aelements[i].addEventListener("click",new Function("e","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"if (e.preventDefault) e.preventDefault();"),true);}else if(aelements[i].attachEvent){aelements[i].attachEvent("onclick",new Function("","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"event.returnValue = false;"));}}}}}
function externalLinks(){if(!document.getElementsByTagName)return;var anchors=document.getElementsByTagName('a');for(var i=0;i<anchors.length;i++){var anchor=anchors[i];if(anchor.getAttribute('href')&&hasValue(anchor.rel,'external')){anchor.target='_blank';addClass(anchor,'external');}}}
function createControls(){var controlsDiv=document.getElementById("controls");if(!controlsDiv)return;var hider=' onmouseover="showHide(\'s\');" onmouseout="showHide(\'h\');"';var hideDiv,hideList='';if(controlVis=='hidden'){hideDiv=hider;}else{hideList=hider;}
controlsDiv.innerHTML='<form action="#" id="controlForm"'+hideDiv+'>'+'<div id="navLinks">'+'<a accesskey="t" id="toggle" href="javascript:toggle();">Ø<\/a>'+'<a accesskey="z" id="prev" href="javascript:go(-1);">«<\/a>'+'<a accesskey="x" id="next" href="javascript:go(1);">»<\/a>'+'<div id="navList"'+hideList+'><select id="jumplist" onchange="go(\'j\');"><\/select><\/div>'+'<\/div><\/form>';if(controlVis=='hidden'){var hidden=document.getElementById('navLinks');}else{var hidden=document.getElementById('jumplist');}
addClass(hidden,'hideme');}
function fontScale(){if(!s5mode)return false;var vScale=22;var hScale=32;if(window.innerHeight){var vSize=window.innerHeight;var hSize=window.innerWidth;}else if(document.documentElement.clientHeight){var vSize=document.documentElement.clientHeight;var hSize=document.documentElement.clientWidth;}else if(document.body.clientHeight){var vSize=document.body.clientHeight;var hSize=document.body.clientWidth;}else{var vSize=700;var hSize=1024;}
var newSize=Math.min(Math.round(vSize/vScale),Math.round(hSize/hScale));fontSize(newSize+'px');if(isGe){var obj=document.getElementsByTagName('body')[0];obj.style.display='none';obj.style.display='block';}}
function fontSize(value){if(!(s5ss=document.getElementById('s5ss'))){if(!isIE){document.getElementsByTagName('head')[0].appendChild(s5ss=document.createElement('style'));s5ss.setAttribute('media','screen, projection');s5ss.setAttribute('id','s5ss');}else{document.createStyleSheet();document.s5ss=document.styleSheets[document.styleSheets.length-1];}}
if(!isIE){while(s5ss.lastChild)s5ss.removeChild(s5ss.lastChild);s5ss.appendChild(document.createTextNode('body {font-size: '+value+' !important;}'));}else{document.s5ss.addRule('body','font-size: '+value+' !important;');}}
function notOperaFix(){slideCSS=document.getElementById('slideProj').href;var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');slides.setAttribute('media','screen');outline.disabled=true;if(isGe){slides.setAttribute('href','null');slides.setAttribute('href',slideCSS);}
if(isIE&&document.styleSheets&&document.styleSheets[0]){document.styleSheets[0].addRule('img','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('div','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('.slide','behavior: url(ui/default/iepngfix.htc)');}}
function getIncrementals(obj){var incrementals=new Array();if(!obj)
return incrementals;var children=obj.childNodes;for(var i=0;i<children.length;i++){var child=children[i];if(hasClass(child,'incremental')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'incremental');for(var j=0;j<child.childNodes.length;j++){if(child.childNodes[j].nodeType==1){addClass(child.childNodes[j],'incremental');}}}else{incrementals[incrementals.length]=child;removeClass(child,'incremental');}}
if(hasClass(child,'show-first')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'show-first');if(child.childNodes[isGe].nodeType==1){removeClass(child.childNodes[isGe],'incremental');}}else{incrementals[incrementals.length]=child;}}
incrementals=incrementals.concat(getIncrementals(child));}
return incrementals;}
function createIncrementals(){var incrementals=new Array();for(var i=0;i<smax;i++){incrementals[i]=getIncrementals(document.getElementById('slide'+i));}
return incrementals;}
function defaultCheck(){var allMetas=document.getElementsByTagName('meta');for(var i=0;i<allMetas.length;i++){if(allMetas[i].name=='defaultView'){defaultView=allMetas[i].content;}
if(allMetas[i].name=='controlVis'){controlVis=allMetas[i].content;}}}
function trap(e){if(!e){e=event;e.which=e.keyCode;}
try{modifierKey=e.ctrlKey||e.altKey||e.metaKey;}
catch(e){modifierKey=false;}
return modifierKey||e.which==0;}
function startup(){defaultCheck();if(!isOp)
createControls();slideLabel();fixLinks();externalLinks();fontScale();if(!isOp){notOperaFix();incrementals=createIncrementals();slideJump();if(defaultView=='outline'){toggle();}
document.onkeyup=keys;document.onkeypress=trap;document.onclick=clicker;}}
window.onload=startup;window.onresize=function(){setTimeout('fontScale()',50);}
</script>
</head
><body
><div class="layout">
<div id="controls"></div>
<div id="currentSlide"></div>
<div id="header"></div>
<div id="footer">
<h1 id="cefp-2009-komarno"
>CEFP 2009, Komarno</h1
><h2 id="implementing-pointer-algorithms-in-haskell-"
>Implementing Pointer Algorithms in Haskell </h2
></div>
</div>
<div class="presentation">
<div class="slide">
<h1 id="implementing-pointer-algorithms-in-haskell--1"
>Implementing Pointer Algorithms in Haskell </h1
><h3 id="péter-diviánszky"
>Péter Diviánszky</h3
><h4 id="cefp-2009-komarno-1"
>CEFP 2009, Komarno</h4
></div>
<div class="slide">
<h1 id="pointers"
>Pointers</h1
><ul
><li
>Pointers are well known.<ul
><li
>They are called mutable variables in functional languages.</li
><li
>Some algorithms use them heavily.</li
></ul
></li
><li
>Pointers can be modeled with a global store (heap).<ul
><li
>Efficient implementation on CPU and memory.</li
></ul
></li
><li
>Hard to find a stateless / modular model for them.<ul
><li
>This would be the functional way.</li
></ul
></li
></ul
></div>
<div class="slide">
<h1 id="pointers-in-c"
>Pointers in C</h1
><pre class="sourceCode c"
><code
><span class="DataType DataType"
>void</span
><span class="Normal NormalText"
> swap</span
><span class="Normal Symbol"
>(</span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>x</span
><span class="Normal Symbol"
>,</span
><span class="Normal NormalText"
> </span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>y</span
><span class="Normal Symbol"
>)</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>{</span
><br
/><span class="Normal NormalText"
> </span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> xv </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>x</span
><span class="Normal Symbol"
>;</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>// read</span
><br
/><span class="Normal NormalText"
> </span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> yv </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>y</span
><span class="Normal Symbol"
>;</span
><br
/><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>x </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> yv</span
><span class="Normal Symbol"
>;</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>// write</span
><br
/><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>*</span
><span class="Normal NormalText"
>y </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> xv</span
><span class="Normal Symbol"
>;</span
><br
/><span class="Normal Symbol"
>}</span
><br
/><br
/><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> main</span
><span class="Normal Symbol"
>()</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>{</span
><br
/><span class="Normal NormalText"
> </span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> a </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> </span
><span class="DecVal Decimal"
>13</span
><span class="Normal Symbol"
>;</span
><br
/><span class="Normal NormalText"
> </span
><span class="DataType DataType"
>int</span
><span class="Normal NormalText"
> b </span
><span class="Normal Symbol"
>=</span
><span class="Normal NormalText"
> </span
><span class="DecVal Decimal"
>14</span
><span class="Normal Symbol"
>;</span
><br
/><span class="Normal NormalText"
> swap</span
><span class="Normal Symbol"
>(&</span
><span class="Normal NormalText"
>a</span
><span class="Normal Symbol"
>,</span
><span class="Normal NormalText"
> </span
><span class="Normal Symbol"
>&</span
><span class="Normal NormalText"
>b</span
><span class="Normal Symbol"
>);</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>// references</span
><br
/><span class="Normal NormalText"
> printf</span
><span class="Normal Symbol"
>(</span
><span class="String"
>"%d, %d"</span
><span class="Normal Symbol"
>,</span
><span class="Normal NormalText"
> a</span
><span class="Normal Symbol"
>,</span
><span class="Normal NormalText"
> b</span
><span class="Normal Symbol"
>);</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>return</span
><span class="Normal NormalText"
> </span
><span class="DecVal Decimal"
>0</span
><span class="Normal Symbol"
>;</span
><br
/><span class="Normal Symbol"
>}</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="pointers-in-ocaml"
>Pointers in OCAML</h1
><pre class="sourceCode ocaml"
><code
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>swap</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>x</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>y</span
><span class="Normal NormalText"
> =</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>vx</span
><span class="Normal NormalText"
> = !</span
><span class="Normal Identifier"
>x</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>(* read *)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>and</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>vy</span
><span class="Normal NormalText"
> = !</span
><span class="Normal Identifier"
>y</span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>in</span
><br
/><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>x</span
><span class="Normal NormalText"
> := </span
><span class="Normal Identifier"
>vy</span
><span class="Normal NormalText"
>; </span
><span class="Comment"
>(* write *)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>y</span
><span class="Normal NormalText"
> := </span
><span class="Normal Identifier"
>vx</span
><span class="Normal NormalText"
>;;</span
><br
/><br
/><span class="Keyword"
>let</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> = </span
><span class="DataType CoreDataType"
>ref</span
><span class="Normal NormalText"
> </span
><span class="DecVal Decimal"
>13</span
><span class="Normal NormalText"
>;; </span
><span class="Comment"
>(* reference *)</span
><br
/><span class="Keyword"
>let</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>b</span
><span class="Normal NormalText"
> = </span
><span class="DataType CoreDataType"
>ref</span
><span class="Normal NormalText"
> </span
><span class="DecVal Decimal"
>14</span
><span class="Normal NormalText"
>;;</span
><br
/><span class="Normal Identifier"
>swap</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> </span
><span class="Normal Identifier"
>b</span
><span class="Normal NormalText"
>;;</span
><br
/></code
></pre
><p
>Primitives:</p
><pre class="sourceCode ocaml"
><code
><span class="DataType CoreDataType"
>ref</span
><span class="Normal NormalText"
> : '</span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> -> '</span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> </span
><span class="DataType CoreDataType"
>ref</span
><br
/><span class="Normal NormalText"
>(!) : '</span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> </span
><span class="DataType CoreDataType"
>ref</span
><span class="Normal NormalText"
> -> '</span
><span class="Normal Identifier"
>a</span
><br
/><span class="Normal NormalText"
>(:=) : '</span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> </span
><span class="DataType CoreDataType"
>ref</span
><span class="Normal NormalText"
> -> </span
><span class="Normal Identifier"
>a</span
><span class="Normal NormalText"
> -> </span
><span class="DataType CoreDataType"
>unit</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="pointers-in-haskell"
>Pointers in Haskell</h1
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>swap ::</span
><span class="Normal NormalText"
> IORef a -> IORef a -> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> ()</span
><br
/><span class="Normal NormalText"
>swap x y = </span
><span class="Keyword"
>do</span
><br
/><span class="Normal NormalText"
> vx <- readIORef x</span
><br
/><span class="Normal NormalText"
> vy <- readIORef y</span
><br
/><span class="Normal NormalText"
> writeIORef x vy</span
><br
/><span class="Normal NormalText"
> writeIORef y vx</span
><br
/></code
></pre
><p
>Primitives:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>newIORef ::</span
><span class="Normal NormalText"
> a -> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> (IORef a)</span
><br
/><span class="Function FunctionDefinition"
>readIORef ::</span
><span class="Normal NormalText"
> IORef a -> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> a</span
><br
/><span class="Function FunctionDefinition"
>writeIORef ::</span
><span class="Normal NormalText"
> IORef a -> a -> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> ()</span
><br
/></code
></pre
><p
>Side effects are properly indicated with <code
>IO</code
> in types.</p
></div>
<div class="slide">
<h1 id="st-pointers-in-haskell"
>ST Pointers in Haskell</h1
><p
><code
>STRef</code
>s are more safe than <code
>IORef</code
>s because they need less privileges.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>swap ::</span
><span class="Normal NormalText"
> STRef s a -> STRef s a -> ST s ()</span
><br
/><span class="Normal NormalText"
>swap x y = </span
><span class="Keyword"
>do</span
><br
/><span class="Normal NormalText"
> vx <- readSTRef x</span
><br
/><span class="Normal NormalText"
> vy <- readSTRef y</span
><br
/><span class="Normal NormalText"
> writeSTRef x vy</span
><br
/><span class="Normal NormalText"
> writeSTRef y vx</span
><br
/></code
></pre
><p
>Primitives:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>newSTRef ::</span
><span class="Normal NormalText"
> a -> ST s (STRef s a)</span
><br
/><span class="Function FunctionDefinition"
>readSTRef ::</span
><span class="Normal NormalText"
> STRef s a -> ST s a</span
><br
/><span class="Function FunctionDefinition"
>writeSTRef ::</span
><span class="Normal NormalText"
> STRef s a -> a -> ST s ()</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="st-pointers-in-haskell-continued"
>ST Pointers in Haskell (continued)</h1
><p
>Imperative style Fibonacci function:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>fib ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Integer</span
><span class="Normal NormalText"
> -> ST s </span
><span class="DataType TypeConstructor"
>Integer</span
><br
/><span class="Normal NormalText"
>fib n = </span
><span class="Keyword"
>do</span
><br
/><span class="Normal NormalText"
> a <- newSTRef </span
><span class="DecVal Decimal"
>0</span
><br
/><span class="Normal NormalText"
> b <- newSTRef </span
><span class="DecVal Decimal"
>1</span
><br
/><br
/><span class="Normal NormalText"
> replicateM_ n $ </span
><span class="Keyword"
>do</span
><br
/><span class="Normal NormalText"
> av <- readSTRef a</span
><br
/><span class="Normal NormalText"
> bv <- readSTRef b</span
><br
/><span class="Normal NormalText"
> writeSTRef a bv</span
><br
/><span class="Normal NormalText"
> writeSTRef b (av + bv)</span
><br
/><br
/><span class="Normal NormalText"
> readSTRef a</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="st-pointers-in-haskell-continued-1"
>ST Pointers in Haskell (continued)</h1
><p
>Note that the return type of the <code
>ST</code
> computation does not depend on <code
>s</code
>:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>fib ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Integer</span
><span class="Normal NormalText"
> -> ST s </span
><span class="DataType TypeConstructor"
>Integer</span
><br
/></code
></pre
><p
>In this case the <code
>ST</code
> computation can be turned into a pure value:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>runST ::</span
><span class="Normal NormalText"
> (forall s. ST s a) -> a</span
><br
/></code
></pre
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>fib' ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Integer</span
><span class="Normal NormalText"
> -> </span
><span class="DataType TypeConstructor"
>Integer</span
><br
/><span class="Normal NormalText"
>fib' n = runST (fib n)</span
><br
/></code
></pre
><p
>In that way pointers can be used in a pure function.<br
/>Still, we need a strictly scheduled computation inside.</p
></div>
<div class="slide">
<h1 id="other-direction-pointers-in-clean"
>Other Direction: Pointers in Clean</h1
><pre class="clean"
><code
>swap :: (Ptr a) (Ptr a) *Heap -> *Heap
swap x y h1 = h5
where
(vx, h2) = readPtr x h1
(vy, h3) = readPtr y h2
h4 = writePtr x vy h3
h5 = writePtr y vx h4
</code
></pre
><p
>Primitives:</p
><pre class="clean"
><code
>newPtr :: a *Heap -> (Ptr a, *Heap)
readPtr :: (Ptr a) *Heap -> (a, *Heap)
writePtr :: (Ptr a) a *Heap -> *Heap
</code
></pre
></div>
<div class="slide">
<h1 id="problems-with-explicit-heap"
>Problems with Explicit Heap</h1
><p
>The previous pointer interface is</p
><ul
><li
>Typed.</li
><li
>Functional.</li
></ul
><p
>However, an explicit heap value should be carried through the program which determines the evaluation order overly.<br
/>The result is an imperative program in a functional guise.</p
></div>
<div class="slide">
<h1 id="improvement-interchangeable-pointer-reads"
>Improvement: Interchangeable Pointer Reads</h1
><p
>Reading a pointer does not alter the heap but it have to be done in time:</p
><pre class="clean"
><code
>swap :: (Ptr a) (Ptr a) *Heap -> *Heap
swap x y h
#! vx = sreadPtr x h
vy = sreadPtr y h
= writePtr y vx (writePtr x vy h)
</code
></pre
><p
>New primitive:</p
><pre class="clean"
><code
>sreadPtr :: (Ptr a) Heap -> a
</code
></pre
><p
>Note that <code
>Heap</code
> is a subtype of <code
>*Heap</code
>.</p
></div>
<div class="slide">
<h1 id="improvement-typed-heaps"
>Improvement: Typed Heaps</h1
><p
>An <code
>Int</code
>-pointer read and a <code
>Char</code
>-pointer write may be interchanged safely.<br
/>This is modeled with typed heaps.</p
><p
>Primitives (as used in the Clean compiler sources):</p
><pre class="clean"
><code
>newHeap :: .(Heap a)
newPtr :: a *(Heap a) -> (Ptr a, *(Heap a))
readPtr :: (Ptr a) *(Heap a) -> (a, *(Heap a))
sreadPtr :: (Ptr a) (Heap a) -> a
writePtr :: (Ptr a) a *(Heap a) -> *(Heap a)
</code
></pre
><p
>Still a problem: Reading a <code
>Ptr Char</code
> in a <code
>Heap Char</code
> fails if the pointer was constructed in another <code
>Heap Char</code
>.</p
></div>
<div class="slide">
<h1 id="improvement-use-the-st-pointer-trick"
>Improvement: Use the ST Pointer Trick</h1
><p
>We distinguish between different <code
>Heap Char</code
> values by adding a phantom type variable: <code
>Heap k Char</code
>.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>newPtr ::</span
><span class="Normal NormalText"
> a -> Heap k a -> (Ptr k, Heap k a)</span
><br
/><span class="Function FunctionDefinition"
>sreadPtr ::</span
><span class="Normal NormalText"
> Ptr k -> Heap k a -> a</span
><br
/><span class="Function FunctionDefinition"
>writePtr ::</span
><span class="Normal NormalText"
> Ptr k -> a -> Heap k a -> Heap k a</span
><br
/></code
></pre
><p
>Note that the interface use <code
>Ptr k</code
> instead of <code
>Ptr k a</code
> because <code
>a</code
> is not needed.</p
><p
>If the result of a heap-consuming computation does not contain the phantom typevar then we get a heap for free:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>runHCC ::</span
><span class="Normal NormalText"
> (forall k. Heap k a -> b) -> b</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="coming-from-another-direction-finite-maps"
>Coming from Another Direction: Finite Maps</h1
><p
>Finite maps are functions with finite domain.<br
/>Related phrases: dictionary (Python), hash (Perl), association list.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>empty ::</span
><span class="Normal NormalText"
> Map k a</span
><br
/><span class="Function"
>lookup</span
><span class="Normal NormalText"
> :: </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> k => k -> Map k a -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> a</span
><br
/><span class="Function FunctionDefinition"
>insert ::</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> k => k -> a -> Map k a -> Map k a</span
><br
/><span class="Function FunctionDefinition"
>delete ::</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> k => k -> Map k a -> Map k a</span
><br
/></code
></pre
><p
>We will need an additional function:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>modify ::</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> k => k -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> a -> Map k a -> Map k a</span
><br
/><span class="Normal NormalText"
>modify k </span
><span class="Keyword DataConstructor"
>Nothing</span
><span class="Normal NormalText"
> m = delete k m</span
><br
/><span class="Normal NormalText"
>modify k (</span
><span class="Keyword DataConstructor"
>Just</span
><span class="Normal NormalText"
> a) m = insert k a m</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="finite-maps-vs-heaps"
>Finite Maps vs Heaps</h1
><p
><code
>Heap k (Maybe a)</code
> ~ <code
>Map (Id k) a</code
></p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>newtype Id k = Id </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Eq</span
><span class="Normal NormalText"
>, </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
>)</span
><br
/></code
></pre
><p
>We allow only <code
>Maybe</code
>-typed heaps, so we can use an interface similar to finite maps.</p
></div>
<div class="slide">
<h1 id="pointers-with-finite-map-interface"
>Pointers with Finite Map Interface</h1
><p
><code
>Map</code
> here is the abstract heap (not a finite map):</p
><pre class="sourceCode haskell"
><code
><span class="Function"
>lookup</span
><span class="Normal NormalText"
> :: Id k -> Map k a -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> a</span
><br
/><span class="Function FunctionDefinition"
>insert ::</span
><span class="Normal NormalText"
> Id k -> a -> Map k a -> Map k a</span
><br
/><span class="Function FunctionDefinition"
>delete ::</span
><span class="Normal NormalText"
> Id k -> Map k a -> Map k a</span
><br
/></code
></pre
><p
>Instead of including <code
>newPtr</code
>, pointers are created with the map (this decison pays back later):</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>runICC ::</span
><span class="Normal NormalText"
> (forall k. Map k a -> [Id k] -> b) -> b</span
><br
/></code
></pre
><p
><code
>runICC</code
> runs an identifier consuming computation, which receives a map (heap) and an infinite list of identifiers (pointers) allowed to be used with that map.</p
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists"
>Use Case: Doubly Linked Lists</h1
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DList k a</span
><br
/><span class="Normal NormalText"
> = Empty</span
><br
/><span class="Normal NormalText"
> | NonEmpty</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>first ::</span
><span class="Normal NormalText"
> Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> :: Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>nodes ::</span
><span class="Normal NormalText"
> Map k (DListNode k a)</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DListNode k a =</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>previous ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> (Id k)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>next ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> (Id k)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>value ::</span
><span class="Normal NormalText"
> a</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><br
/><span class="Normal NormalText"
>(<|) :: a -> DList k a -> Id k -> DList k a</span
><br
/><span class="Normal NormalText"
>(|>) :: DList k a -> a -> Id k -> DList k a</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v2"
>Use Case: Doubly Linked Lists (v2)</h1
><p
>It is a problem that at insertions free <code
>Id</code
>s are needed. This new version solves that problem:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DList k a</span
><br
/><span class="Normal NormalText"
> = Empty</span
><br
/><span class="Normal NormalText"
> | NonEmpty</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>first ::</span
><span class="Normal NormalText"
> Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> :: Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>nodes ::</span
><span class="Normal NormalText"
> Map k (DListNode k a)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>freeIds ::</span
><span class="Normal NormalText"
> [Id k] </span
><span class="Comment"
>-- stored free Ids</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><br
/><span class="Normal NormalText"
>(<|) :: a -> DList k a -> DList k a</span
><br
/><span class="Normal NormalText"
>(|>) :: DList k a -> a -> DList k a</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v3"
>Use Case: Doubly Linked Lists (v3)</h1
><p
>This version simplifies the creation of <code
>DList</code
>s:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DList a</span
><br
/><span class="Normal NormalText"
> = Empty</span
><br
/><span class="Normal NormalText"
> | forall k . NonEmpty </span
><span class="Comment"
>-- encapsulated heap</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>first ::</span
><span class="Normal NormalText"
> Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> :: Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>nodes ::</span
><span class="Normal NormalText"
> Map k (DListNode k a)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>freeIds ::</span
><span class="Normal NormalText"
> [Id k]</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><br
/><span class="Function FunctionDefinition"
>singleton ::</span
><span class="Normal NormalText"
> a -> DList a</span
><br
/><br
/><span class="Normal NormalText"
>(<|) :: a -> DList a -> DList a</span
><br
/><span class="Normal NormalText"
>(|>) :: DList a -> a -> DList a</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v3-continued"
>Use Case: Doubly Linked Lists (v3, continued)</h1
><p
>Code for <code
>singleton</code
>:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>singleton ::</span
><span class="Normal NormalText"
> a -> DList a</span
><br
/><span class="Normal NormalText"
>singleton x = runICC $ \emptyMap (firstId: otherIds) -></span
><br
/><span class="Normal NormalText"
> NonEmpty</span
><br
/><span class="Normal NormalText"
> { first = firstId</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> = firstId</span
><br
/><span class="Normal NormalText"
> , nodes = insert firstId x emptyMap</span
><br
/><span class="Normal NormalText"
> , freeIds = otherIds</span
><br
/><span class="Normal NormalText"
> }</span
><br
/></code
></pre
><p
>But <code
>DList</code
>s can not be joined because if we open two <code
>NonEmpty</code
> values, the phantom variables can not be unified by the type system (which is right).</p
></div>
<div class="slide">
<h1 id="improvement-identifier-subtyping"
>Improvement: Identifier Subtyping</h1
><p
>If <code
>k1</code
> ≠ <code
>k2</code
> then <code
>Id k1</code
> can not be used instead of <code
>Id k2</code
>. This is right, because this type variables marks "different regions of memory".<br
/>But sometimes memory regions should be joined.</p
><p
><code
>Id (k1 :|: k2)</code
> is the joined set of <code
>Id k1</code
> and <code
>Id k2</code
>.</p
><p
><code
>:|:</code
> is an infix type constructor with kind <code
>* -> * -> *</code
>:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> (a :|: b)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- no constructors</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="identifier-subtyping-continued"
>Identifier Subtyping (continued)</h1
><p
><code
>Id (k1 :|: k2)</code
> is the joined set of <code
>Id k1</code
> and <code
>Id k2</code
>.</p
><p
>A value with type <code
>Id k1</code
> is acceptable when a value with type <code
>Id (k1 :|: k2)</code
> is needed.<br
/>In other words, <code
>Id k1</code
> is a subtype of <code
>Id (k1 :|: k2)</code
>.<br
/>There is no subtyping in Haskell so we use explicit conversion functions:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>left ::</span
><span class="Normal NormalText"
> Id k1 -> Id (k1 :|: k2)</span
><br
/><span class="Function FunctionDefinition"
>right ::</span
><span class="Normal NormalText"
> Id k2 -> Id (k1 :|: k2)</span
><br
/></code
></pre
><p
>One can join two maps (two heaps or two "memory regions") with <code
>union</code
>:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>union ::</span
><span class="Normal NormalText"
> Map k1 a -> Map k2 a -> Map (k1 :|: k2) a</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v4"
>Use Case: Doubly Linked Lists (v4)</h1
><p
>A simplification first: the <code
>freeIds</code
> field is not needed because any number of free <code
>Id</code
>s can be obtained by joining a new "memory region":</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DList a</span
><br
/><span class="Normal NormalText"
> = Empty</span
><br
/><span class="Normal NormalText"
> | forall k . NonEmpty</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>first ::</span
><span class="Normal NormalText"
> Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> :: Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>nodes ::</span
><span class="Normal NormalText"
> Map k (DListNode k a)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- , freeIds :: [Id k] -- not needed</span
><br
/><span class="Normal NormalText"
> }</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v4-continued"
>Use Case: Doubly Linked Lists (v4, continued)</h1
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>(><) :: DList a -> DList a -> DList a</span
><br
/><span class="Normal NormalText"
>Empty >< y = y</span
><br
/><span class="Normal NormalText"
>x >< Empty = x</span
><br
/><span class="Normal NormalText"
>x >< y = NonEmpty</span
><br
/><span class="Normal NormalText"
> { first = left (first x)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> = right (</span
><span class="Function"
>last</span
><span class="Normal NormalText"
> y)</span
><br
/><span class="Normal NormalText"
> , nodes = ... (</span
><span class="Function"
>fmap</span
><span class="Normal NormalText"
> left (nodes x) </span
><br
/><span class="Normal NormalText"
> </span
><span class="Others InfixOperator"
>`union`</span
><span class="Normal NormalText"
> </span
><span class="Function"
>fmap</span
><span class="Normal NormalText"
> right (nodes y))</span
><br
/><span class="Normal NormalText"
> }</span
><br
/></code
></pre
><p
><code
>...</code
> contains code which redirects<br
/><code
>next (last x)</code
> to <code
>first y</code
> and<br
/><code
>previous (first y)</code
> to <code
>(last x)</code
>.</p
></div>
<div class="slide">
<h1 id="improvement-split-maps"
>Improvement: Split Maps</h1
><p
>Redirecting <code
>next (last x)</code
> to <code
>first y</code
> is complicated because a <code
>DListNode</code
> record have to be updated.</p
><p
>This could be improved if three different maps were used for <code
>previous</code
>, <code
>next</code
> and <code
>value</code
> values. But a pointer can only point to one object.</p
><p
>Solution: Maps are tagged with type-level integers. A pointer can be a key in several maps with different integers.</p
><p
>We will use <code
>(Map I0 k a, Map I1 k b, Map I2 k c)</code
><br
/>instead of <code
>Map k (a, b, c)</code
>.</p
></div>
<div class="slide">
<h1 id="improvement-split-maps-continued"
>Improvement: Split Maps (continued)</h1
><p
>To understand the implementation:<br
/>The finite map <code
>Map i k a</code
> represents a scattered memory fragment with the following properties:</p
><ul
><li
>The memory fragment contains an <code
>a</code
>-typed values.</li
><li
>The pieces of the memory fragment are some record's <code
>i</code
>th field.<ul
><li
><code
>i</code
> is a type-level integer (<code
>I0</code
>, <code
>I1</code
>, <code
>I2</code
>, ... in the implementation).</li
><li
>The records need not have the same type.</li
></ul
></li
><li
><code
>k</code
> is an additional tag (for example, to separate two doubly linked lists)</li
></ul
></div>
<div class="slide">
<h1 id="use-case-doubly-linked-lists-v5"
>Use Case: Doubly Linked Lists (v5)</h1
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DList a</span
><br
/><span class="Normal NormalText"
> = Empty</span
><br
/><span class="Normal NormalText"
> | forall k . NonEmpty</span
><br
/><span class="Normal NormalText"
> { </span
><span class="Function FunctionDefinition"
>first ::</span
><span class="Normal NormalText"
> Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function"
>last</span
><span class="Normal NormalText"
> :: Id k</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>previous ::</span
><span class="Normal NormalText"
> Map I0 k (Id k)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>next ::</span
><span class="Normal NormalText"
> Map I1 k (Id k)</span
><br
/><span class="Normal NormalText"
> , </span
><span class="Function FunctionDefinition"
>value ::</span
><span class="Normal NormalText"
> Map I2 k a</span
><br
/><span class="Normal NormalText"
> }</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="creation-of-split-maps"
>Creation of Split Maps</h1
><p
>Basic solution: There are a family of functions</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>runICC1 ::</span
><span class="Normal NormalText"
> (forall k. Map I0 k a -> [Id k] -> b) -> b</span
><br
/><span class="Function FunctionDefinition"
>runICC2 ::</span
><span class="Normal NormalText"
> (forall k. Map I0 k a -> Map I1 k a -> [Id k] -> b) -> b</span
><br
/><span class="Function FunctionDefinition"
>runICC3 ::</span
><span class="Normal NormalText"
> (forall k. Map I0 k a -> Map I1 k a -> Map I2 k a -> [Id k] -> b) -> b</span
><br
/><span class="Normal NormalText"
>...</span
><br
/></code
></pre
><p
>Instead of that, the current implementation use a variant of the function</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>runICC ::</span
><span class="Normal NormalText"
> (forall k. Maps i k -> [Id k] -> b) -> b</span
><br
/></code
></pre
><p
>where <code
>Maps</code
> is a GADT which can be unfolded into <code
>i</code
> maps.</p
></div>
<div class="slide">
<h1 id="conclusion--efficiency"
>Conclusion / Efficiency</h1
><p
>The implementation is as efficient as if mutable references were used:</p
><ul
><li
><code
>Map</code
>s are not present in the generated code (for example, <code
>NonEmpty</code
> has two fields).</li
><li
><code
>Id</code
>s are replaced by pointers to records (arrays actually).</li
></ul
><p
>TODOs:</p
><ul
><li
>The implementation has to be reviewed.</li
><li
>The <code
>Maybe</code
>s still cause some performance loss.</li
></ul
></div>
<div class="slide">
<h1 id="conclusion--safety"
>Conclusion / Safety</h1
><p
>Guarantees by the type system:</p
><ul
><li
>Pointers are typed (by the type of the pointed value).</li
><li
>Pointers can not escape their scope.<ul
><li
>Pointer in "different regions" can not be exchanged by accident.</li
></ul
></li
></ul
><p
>TODOs:</p
><ul
><li
>Linear use is checked <em
>only in runtime</em
>.<ul
><li
>This is a big disadvantage.</li
><li
>Should be checked statically, which needs at least annotated types and a strictness analyzer.</li
></ul
></li
></ul
></div>
<div class="slide">
<h1 id="conclusion--usability"
>Conclusion / Usability</h1
><p
>Pros:</p
><ul
><li
>Highly functional interface (similar to finite maps).<ul
><li
>Less strict evaluation order (more possibility to parallel execution).</li
></ul
></li
><li
>One can virtually join <code
>i</code
>th fields of different records (if the <code
>i</code
>th fields has the same type).</li
></ul
><p
>Cons:</p
><ul
><li
>Linear use should be obeyed.</li
><li
>Creation of maps is a bit uncomfortable (maps has to be carried).</li
></ul
></div>
<div class="slide">
<h1 id="conclusion--semantics"
>Conclusion / Semantics</h1
><p
>The library has a simple semantics.</p
><p
>This is demonstrated by a small pure functional implementation of the interface functions.</p
></div>
<div class="slide">
<h1 id="further-extensions"
>Further Extensions</h1
><p
>Sets can be modeled as maps to unit values.</p
><ul
><li
>The current implementation is more efficient than that: 32 sets are packed into 1 integer map.</li
><li
>The interface of sets and maps are unified.</li
></ul
><p
>Identifiers can refer to static data.<br
/>For example, if a sequence is implemented by a doubly linked map, <code
>previous</code
> and <code
>next</code
> are mutable but <code
>value</code
> is static. So two maps are sufficient.</p
></div>
<div class="slide">
<h1 id="related-work"
>Related Work</h1
><ul
><li
><a href="http://www.haskell.org/haskellwiki/DDC"
>DDC</a
>, The Disciplined Disciple Compiler<ul
><li
>An explicitly lazy dialect of Haskell.</li
><li
>Supports destructive update, computational effects, type directed field projections.</li
></ul
></li
><li
><a href="http://okmij.org/ftp/Haskell/regions.html"
>Monadic Regions</a
><ul
><li
>A technique for managing resources (memory areas, file handles, database connections).</li
></ul
></li
></ul
></div>
<div class="slide">
<h1 id="forthcoming-use-cases"
>Forthcoming Use Cases</h1
><ul
><li
>Graph walks.<ul
><li
>with tagging</li
><li
>with pointer reversal</li
></ul
></li
><li
>Strongly connected components computation.</li
><li
>Linear time type inference algorithm with pointers.</li
></ul
></div>
<div class="slide">
<h1 id="thanks"
>Thanks</h1
><p
>Thanks for your attention!</p
><p
>The code can be found as <code
>linear-maps</code
> on <a href="http://hackage.haskell.org/packages/archive/pkg-list.html"
>HackageDB</a
>.</p
></div>
</div>
</body
></html
>