tag:blogger.com,1999:blog-58948392024-03-13T07:58:08.078+01:00Kazimir Majorinc's Blog (currently not in use)Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.comBlogger141125tag:blogger.com,1999:blog-5894839.post-54622813393768839022013-05-07T19:00:00.000+02:002013-05-07T19:00:53.348+02:00Spring evening in my hacklab<div style="text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3UdhNW1hcc51hE_gR_bvngWvBtq9k7ymEuAJlDib6UThsDv0R70kd4pGvvHwzmhqvf-WRS0DfpMMZEbd35JFOnmsQDg1f1M9qmaZ24MJ0tg8SQMHYccY3G-kX_Ls-NkQwPB7v_g/s1600/HacklabMama2013.jpg" imageanchor="1"><img border="0" height="384" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3UdhNW1hcc51hE_gR_bvngWvBtq9k7ymEuAJlDib6UThsDv0R70kd4pGvvHwzmhqvf-WRS0DfpMMZEbd35JFOnmsQDg1f1M9qmaZ24MJ0tg8SQMHYccY3G-kX_Ls-NkQwPB7v_g/s640/HacklabMama2013.jpg" width="640" /></a></div>
<br />
<div style="text-align: center;">
Veljko, Lovro and Psy Shree Krishna</div>
Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com2tag:blogger.com,1999:blog-5894839.post-15275852071090637762013-05-06T12:05:00.000+02:002013-05-06T12:05:55.068+02:00Epigram on idiom<center><table style=""><tbody>
<tr><td><br />
<div style="color: lime; font-family: Times, 'Times New Roman', Serif; text-align: center; margin: 20px; padding: 20px; margin-top:0px; font-size:200%;">An idiom is scar on the spot where<br /> programmer was injured by language.</div><div style="text-align:right;font-size:100%">(K. Majorinc)</div></td></tr></tbody></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com1tag:blogger.com,1999:blog-5894839.post-34607274606980872482012-08-24T22:44:00.000+02:002012-08-25T17:51:27.981+02:00There is Little Interest in Lisp History.<center><table style="width: 640px;"><tbody>
<tr><td><br />
<div style="background: white; color: black; font-family: Times, 'Times New Roman', Serif; margin: 20px; padding: 80px; text-align: justify;"><h1 style="background: white; color: #d00000; font-family: Times, 'Times New Roman', Serif; text-align: center;"><b>There is Little Interest in Lisp History.</b></h1><br />
<br />
<br />
<span style="color: black; font-size: x-large;">I</span>f Lisp is a cult then <b>McCarthy</b> is deity and <b>Steve Russell</b> is, well, archangel, right? <br />
<br />
At the popular video site, there is four months old video with <b>Steve Russell</b>'s talk about <b>John McCarthy</b>; in four months, less than 60 people have seen the video. <br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-TyfvUzD5voU/UDfj6okP53I/AAAAAAAAAO0/hOWpbmEaPgM/s1600/Capture.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="353" src="http://3.bp.blogspot.com/-TyfvUzD5voU/UDfj6okP53I/AAAAAAAAAO0/hOWpbmEaPgM/s400/Capture.PNG" width="400" /></a></div><br />
<br />
Is it lack of initial exposure, or people just do not have interest in such material? Any case, you are warned, and you can compensate for that now.<br />
<br />
<br />
<iframe allowfullscreen="allowfullscreen" frameborder="3" height="360" src="http://www.youtube.com/embed/lrohXv6cXEY?feature=player_detailpage" width="640"></iframe><br />
<br />
</div></td></tr>
</tbody><tbody></tbody></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-80123489442691663082012-07-08T12:30:00.000+02:002012-07-08T12:30:09.838+02:00Don't say you were not warned ...<table width="100%" style="background:#ffffff;padding:30px;text-align:left;"><tr><td><br />
<center><br />
<img src="http://instprog.com/blogposts/artificial-intelligence-in-1930s/artificial-intelligence-in-1930s.jpg" style="text-align:center;" ><br />
</center></td></tr>
</table>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-67852060764435875932012-03-08T21:43:00.016+01:002013-10-31T05:27:05.095+01:00Few Examples of Lisp Code Typography.moved on <a href="http://kazimirmajorinc.com">kazimirmajorinc.com</a>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com7tag:blogger.com,1999:blog-5894839.post-38359598120963308692011-08-12T06:31:00.051+02:002011-08-17T00:03:16.405+02:00The Similarities Between Axioms of Natural Numbers and Axioms of S-expressions.<style type="text/css">
ol{font-family:'Times', serif;text-align:justify;
padding-top:2px;padding-bottom:2px;}
li {font-family:Times New Roman', 'Times', serif;text-align:justify;
padding-top:2px;padding-bottom:2px;}
</style>
<span style="color: black;">.</span>
<br />
<br />
<br />
<center><table cellpadding="50" style="background: none repeat scroll 0% 0% white; color: black; padding: 20px; text-align: justify; width: 640px;"><tbody style="text-align: left;"><tr style="text-align: left;"><td style="color: black; font-size: 100%; text-align: left;"><div style="color: #cf0000; font-size: 161%;"><center style="font-family:'Times New Roman', 'Times', serif;padding-bottom: 40px;"><b>The Similarities Between Axioms of Natural Numbers and Axioms of S-expressions</b></center></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;">
In <a href="http://kazimirmajorinc.blogspot.com/2011/08/three-meanings-of-term-s-expression.html" style="background: white; color: #cf0000; text-decoration: underline;">last post</a>, it was shown that in Lisp practice, the term "<i>symbolic expression</i>", shorter "<i>s-expression</i>", "<i>sepxr</i>", "<i>sexp</i>" is used on few different, although similar meanings.</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:25px;">
It is not unusual. Other terms, even mathematical ones, like "<i>lines</i>" or "<i>numbers</i>" are not uniquely defined as well. Ambiguity usually motivates the search for the essence of the discussed entities; the result of the search is axiomatic theory.
For example, the axioms of natural numbers are developed in late <b>1880</b>'s by <b>R. Dedekind</b> and <b>G. Peano</b>.</div>
<div style="background-color: #dfffdf; border: solid #009f00 2px; padding-bottom: 10px; padding: 20px;">
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;color: #009f00; font-size: 130%; padding-bottom: 15px; text-align: center;">
<b>Axioms of Natural Numbers</b></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;">
There is a set <b>N</b> ("<i>numbers</i>"), distinctive element of the <b>N</b> denoted with <b>1</b> ("<i>base</i>", "<i>initial number</i>") and mapping</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
successor: <b>N</b> → <b>N</b></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:0px;padding-bottom: 0px;">
such that</div>
<ol style="padding-top: 0px;">
<li style="padding-top: 0px;">all numbers, except <b>1</b>, are <i>successors </i>of some numbers, i.e.<br />
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
{ successor(<i>n</i>) | <i>n</i> ∈ <b>N</b> } = <b>N</b> \ {<b>1</b>};</div>
</li>
<li>the successor function is <i>injection</i>, or <br />
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
successor(<i>n</i>) = successor(<i>m</i>) => <i>n</i> = <i>m</i>;</div>
</li>
<li>if <b>S</b> is a <i>set of numbers</i> such that<br />
<ol type="i">
<li> <b>S</b> contains <i>all initial numbers</i> (i.e. <b>1</b>);</li>
<li> if <b>S</b> contains <i>n</i>, then <b>S</b> contains successor(<i>n</i>);</li>
</ol>
then <b>S</b> contains <i>all numbers</i>. </li>
</ol>
</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;padding-bottom: 25px; padding-top: 25px;">
Search for axioms of symbolic expressions might be equally justified. I designed following axioms (version in which lists are only shorter way of writing "<i>dotted pairs</i>") to emphasize the similarities to axioms of natural numbers.</div>
<div style="background-color: #ffdfdf; border: solid #cf0000 2px; padding-bottom: 10px; padding: 20px;">
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;color: #cf0000; font-size: 130%; padding-bottom: 15px; text-align: center;">
<b>Axioms of Symbolic Expressions</b></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;">
There is a set <b>SEXPR </b>("<i>symbolic expressions</i>"), <b>infinite</b> set of distinct elements of the <b>SEXPR</b> denoted with <b>A</b> ("<i>atoms</i>") and mapping</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
cons: <b>SEXPR </b>× <b>SEXPR </b> → <b>SEXPR</b></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;padding-bottom: 0px;">
such that</div>
<ol style="padding-top: 0px;">
<li style="padding-top: 0px;">all symbolic expressions, except atoms, are <i>conses</i>, i.e.<br />
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
{ cons(<i>x</i>, <i>y</i>) | <i>x</i>, <i>y</i> ∈ <b>SEXPR</b> } = <b>SEXPR </b>\ <b>A</b>;</div>
</li>
<li>the function cons is <i>injection</i>, i.e.<br />
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;text-align: center;">
cons(<i>n</i>, <i>p</i>) = cons(<i>m</i>, <i>q</i>) => <i>n</i> = <i>m</i> and <i>p</i> = <i>q</i>;</div>
</li>
<li>if <b>S</b> is a <i>set of symbolic expressions</i> such that<br />
<ol type="i">
<li><b>S</b> contains <i>all atoms</i>;</li>
<li>if <b>S</b> contains <i>n</i> and <i>p</i> then <b>S</b> contains cons(<i>n</i>, <i>p</i>);</li>
</ol>
then <b>S</b> contains <i>all symbolic expressions</i>.</li>
</ol>
</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;padding-top: 25px;">
<i>Symbolic expressions</i> in <a href="http://kazimirmajorinc.blogspot.com/2011/08/three-meanings-of-term-s-expression.html" style="background: white; color: #cf0000; text-decoration: underline;">all three meanings</a> satisfy the axioms; cons structures satisfy axiom (3) only if <i>cyclic structures</i> are not allowed, like in original, <b>McCarthy</b>'s Lisp. I'm not aware of <i>unintended</i>, <i>perverse</i> models that satisfy given axioms; but I am not sure that such models do not exist.</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:0px;">There are only two differences between these axiom systems.<ol style="padding-top:0px;padding-bottom:0px;"><li style="padding-top:0px;">There is one "<i>base element</i>" for <i>numbers</i> and infinitely many for <i>S-expressions</i>.</li><li style="padding-top:5px;padding-bottom:0px;">The function "successor" is function of a single variable; the function "cons" is function of two variables. </li></ol></div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;padding-top:0px;">It is not obvious that <i>symbolic expressions</i> require infinitely many <i>atoms</i>; it could be only convenience. Perhaps <i>S-expressions</i> like <span style="background-color: #ffdfdf; color: black; font-family: Consolas,'Courier New',Courier,monospace;"><b>(A . (B . (C . D)))</b></span> can be used instead of symbols like <span style="background-color: #ffdfdf; color: black; font-family: Consolas,'Courier New',Courier,monospace;"><b>ABCD</b></span>, eliminating need for infinitely many <i>atoms</i>.</div>
<div style="font-family:'Times New Roman', 'Times', serif;text-align:justify;
padding-top:5px;padding-bottom:5px;">It remains unclear why these two <i>systems of axioms</i> are so similar. </div>
</td></tr>
</tbody></table>
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com1tag:blogger.com,1999:blog-5894839.post-5832921443070352992011-08-07T21:03:00.051+02:002011-08-16T23:25:38.746+02:00Three Meanings of The Term 'S-expression.'<span style="color: black;">.</span><br />
<br />
<br />
<br />
<center><table cellpadding="50" style="background: none repeat scroll 0% 0% white; color: black; padding: 20px; text-align: justify; width: 640px; border:2px dark red;"><tbody style="text-align: left;">
<tr style="text-align: left;"><td style="color: black; font-family: Consolas,monospace,fixed; font-size: 100%; text-align: left;"><div style="color: #cf0000; font-size: 161%;text-align:center;font-family: 'Times New Roman', Times, serif;font-weight:bold;">Three meanings of the term 'S-expression'<br /><br /><br />
</div><div style="font-family: 'Times New Roman',Times,serif; text-align: justify;">"<i>Symbolic expressions</i>" or "<i>S-expressions</i>" are the basic data type in Lisp. Particularly, Lisp programs are S-expressions as well. The notion has immense importance in Lisp community. <br />
<br />
Surprisingly, designers of recent Lisp dialects avoid the term "<i>symbolic expression</i>" or "<i>S-expression</i>". It is used once in Picolisp documentation; only twice, almost accidentally, in CLtL2, and it isn't used in CL Hyperspec or recent Scheme standards. Clojure, according to its web site "<i>extends the code-as-data system beyond parenthesized lists (s-expressions) to vectors and maps.</i>" Only Newlisp documentation appear to regularly uses the term.<br />
<br />
However, the term <i>S-expression</i> is still extensively used in daily communication and literature. Unfortunately, there is no universal, unique meaning. Inconsistent use is sometimes noted; for instance, in <b>P. Siebel</b>'s "<i>Practical Common Lisp</i>." More frequently, it is ignored. <br />
<br />
For <b>J. McCarthy</b>, <i>S-expression</i> is finite sequence consisting of dots and parentheses and symbols. The symbols, truly atomic, cannot be analysed on characters. For instance, <i>S-expression</i> <b style="color: black;"><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">(left.right)</span></b> is sequence of five elements: <b style="color: black;"><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">(</span></b>, <b style="color: black;"><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">left</span></b>, <b style="color: black;"><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">.</span></b>, <b style="color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;"><span style="background-color: #f4cccc; color: black;">right</span></b> and <b style="color: black;"><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">)</span></b>. <br />
<br />
More often<sup style="font-size:60%;">1</sup>, <i>S-expression</i> is seen as sequence of characters. In that meaning, <i>S-expression</i> <b><span style="background-color: #f4cccc; color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;">(left . right)</span></b> is sequence consisting of 14 elements.<br />
<br />
The most usually<sup style="font-size:60%;">2</sup>, <i>S-expression</i> is data structure, perhaps tree consisting of cons cells and symbols. In that meaning <i>S-expression</i> <b style="color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;"><span style="background-color: #f4cccc; color: black;">(left . right)</span></b> is cons cell, containing adresses of symbols <b style="font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;"><span style="background-color: #f4cccc; color: black;">left</span></b> and <b style="color: black; font-family: Consolas, 'Lucida Console', "Courier New",Courier,monospace;"><span style="background-color: #f4cccc; color: black;">right</span></b> in memory. </div><br />
<hr align='left' width='20%' /><br />
<div style="font-family: Times,"Times New Roman",serif; text-align: justify;"><span style="color: #000000; font-size: 85%;">1 For instance, in <b>E. Shaphiro</b>, "<i>Common Lisp - an interactive approach</i>"; <b>F. Turbak</b> and <b>D. Gifford</b>, "<i>Design concept of programming languages.</i>" </span><br />
<br />
<span style="color: #000000; font-size: 85%;">2 For instance, in <b>J.</b> and <b>G. Sussman</b> and <b>H. Abelson</b>, "<i>SICP</i>"; <b>D. Touretsky</b>, "<i>Common Lisp - A gentle introduction to symbolic computation</i>"; <b>R. Finkel</b>, "<i>Advanced programming languages design</i>".</span> </div><br />
</td></tr>
</tbody></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-23679742769858486702011-07-10T09:55:00.011+02:002011-08-17T17:59:42.261+02:00Implementing Data Structures with Symbols.<span style="color: black;">.</span><br />
<br />
<br />
<center><table cellpadding="50" style="background: none repeat scroll 0% 0% white; color: black; padding: 20px; text-align: justify; width: 640px;"><tbody style="text-align: left;"><tr style="text-align: left;"><td style="color: black; font-family: 'Times New Roman', Times, serif; font-size: 100%; text-align: justify;"><div style="color: #cf0000; font-family: 'Times New Roman', Times, serif; font-size: 161%;font-weight:bold;">
<center>Implementing Data Structures with Symbols</center><br /><br />
</div>
Original Lisp had only symbols as atoms. Symbol names, if used on the same way variables are used in mathematics, are flexible enough to support wide variety (all?) data structures. <br />
<br />
For instance, matrices 2 x 2 can be implemented with symbols as <span style="font-family: Consolas, monospace;font-weight:bold;background-color: #fff0f0; color: black;">a11</span> instead of <span style="font-family: Consolas, monospace;font-weight:bold;background-color: #fff0f0; color: black;">a[1,1]</span> in some other language, or <span style="font-family: Consolas, monospace;font-weight:bold;background-color: #fff0f0; color: black;">(a 1 1)</span></span> in Lisp and names could be created as needed. <br />
<br />
The code will be more complicated and less efficient than if matrices are directly supported by language, but neither one is essential problem - complexity of the code can be "abstracted away" with functions, and computational complexity is increased only for factor of constant * log <i>n</i> where <i>n</i> is the number of used symbols (if symbol reaching in Lisp is implemented efficiently.) Newlisp code follows.
<br />
<br />
<pre style="background: #fff0f0; font-family: Consolas,monospace,fixed; padding: 20px;border:solid 2px #Cf0000;"><b>(define (<span style="color: #cf0000;">matrix-</span></b><b><span style="color: #cf0000;">element</span> </b><i>m</i><b> </b><i>i</i><b> </b><i>j</i><b>)
(sym (append (string </b><i>m</i><b>) (string </b><i>i</i><b>) (string </b><i>j</i><b>))))
(define (<span style="color: #cf0000;">set-matrix</span> </b><i>m</i><b> </b><i>m11</i><b> </b><i>m12</i><b> </b><i>m21</i><b> </b><i>m22</i><b>)
(for(</b><i>i</i><b> 1 2)
(for(</b><i>j</i><b> 1 2)
(set (<span style="color: #cf0000;"></span></b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>m</i><b> </b><i>i</i><b> </b><i>j</i><b>)
(nth (+ (* 2 (- </b><i>i</i><b> 1)) (- </b><i>j</i><b> 1))
(list </b><i>m11</i><b> </b><i>m12</i><b> </b><i>m21</i><b> </b><i>m22</i><b>))))))
(define (<span style="color: #cf0000;">println-matrix</span> </b><i>m</i><b>)
(for(</b><i>i</i><b> 1 2)
(for(</b><i>j</i><b> 1 2)
(println m "<span style="background-color: #e06666; color: black;">[</span>" </b><i>i</i><b> "<span style="background-color: #e06666; color: black;">,</span>" </b><i>j</i><b> "<span style="background-color: #e06666; color: black;">]=</span>"
(eval (<span style="color: #cf0000;">matrix-element</span> </b><i>m</i><b> </b><i>i</i><b> </b><i>j</i><b>))))))
(define (<span style="color: #cf0000;">multiply-matrix</span> </b><i>a</i><b> </b><i>b</i><b> </b><i>c</i><b>)
(for(</b><i>i</i><b> 1 2)
(for(</b><i>j</i><b> 1 2)
(set (<span style="color: #cf0000;"></span></b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>c</i><b> </b><i>i</i><b> </b><i>j</i><b>) 0)
(for(</b><i>k</i><b> 1 2)
(set (<span style="color: #cf0000;"></span></b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>c</i><b> </b><i>i</i><b> </b><i>j</i><b>)
(+ (eval (<span style="color: #cf0000;"></span></b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>c</i><b> </b><i>i</i><b> </b><i>j</i><b>))
(* (eval (<span style="color: #cf0000;"></span></b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>a</i><b> </b><i>i</i><b> </b><i>k</i><b>))
(eval (</b><b><span style="color: #cf0000;">matrix-element</span></b><b><span style="color: #cf0000;"></span> </b><i>b</i><b> </b><i>k</i><b> </b><i>j</i><b>)))))))))
(<span style="color: #cf0000;">set-matrix</span> (quote </b><i>X</i><b>) 1 2 3 4)
(<span style="color: #cf0000;">set-matrix</span> (quote </b><i>Y</i><b>) 2 3 4 5)
(<span style="color: #cf0000;">multiply-matrix</span> (quote </b><i>X</i><b>) (quote </b><i>Y</i><b>) (quote </b><i>Z</i><b>))
(<span style="color: #cf0000;">println-matrix</span> (quote </b><i>Z</i><b>))
---------------------------
Program output
Z[1,1]=10
Z[1,2]=13
Z[2,1]=22
Z[2,2]=29
</b></pre></td></tr>
</tbody></table><br />
<br />
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com4tag:blogger.com,1999:blog-5894839.post-8001962390041154872011-07-09T12:04:00.023+02:002011-08-16T23:58:36.244+02:00More on Another Encoding of S-expressions in Symbols.<span style="color: black;">.</span><br />
<br />
<br />
<br />
<center><table width='640' cellpadding='50' style="background: white; color: black; padding: 20px; text-align: justify;"><tbody style="text-align: justify;">
<tr style="text-align: justify;"><td style="color: black; font-family:'Times New Roman', Times, serif; font-size: 100%; text-align: justify;"><div style="color: #cf0000; font-size: 161%;font-family:'Times New Roman',Times,serif;font-weight:bold;text-align:center;">More on Another Encoding of S-expressions in Symbols<br />
<br /></div>
In <a href="http://kazimirmajorinc.blogspot.com/2011/07/another-encoding-of-s-expressions-in.html" style="background: #ffefef; color: #cf0000; text-decoration: underline;">previous post</a>, I have shown another interesting method for encoding of <i>S-expressions</i> into symbols. In this post, I'll show how it can be implemented in Lisp dialects that print symbols on different way from <i>S-expressions</i>, i.e. encapsulated in vertical bars or other symbols (<b>Common Lisp</b>, <b>ISLisp</b>, <b>Picolisp</b>, some implementations of <b>Scheme</b>). This is, normally, good feature. However, <a href="http://kazimirmajorinc.blogspot.com/2011/06/exponential-explosion-of-escape.html" style="background: #ffefef; color: #cf0000; text-decoration: underline;">repeated encoding of the symbols results in exponential growth</a>. So, we must get rid of those vertical bars inside our symbols.<br />
<br />
The code, here in <b>Common Lisp</b>, is sort of trickier than it is in <b>Newlisp </b>or it would be in <b>Clojure</b>. <br />
<pre style="background: #fff0f0; color: black; font-family: Consolas,monospace,fixed; padding: 20px;border:solid 2px #cf0000;"><b>(defun <u><span style="color: #cf0000;">decode-deep</span></u> (</b><i>r</i><b>)
(cond ((symbolp </b><i>r</i><b>) (let((</b><i>result</i><b><i> </i>(read-from-string (string </b><i>r</i><b>))))
(if (symbolp </b><i>result</i><b>)
</b><i>result</i><b>
(<span style="color: #cf0000;">decode-deep</span> </b><i>result</i><b>))))
((listp </b><i>r</i><b>) (mapcar (quote <span style="color: #cf0000;">decode-deep</span>) </b><i>r</i><b>))))
(defun <u><span style="color: #cf0000;">sexpr->symbol</span></u> (</b><i>r</i><b>)
(make-symbol (write-to-string (list '</b><i>q</i><b> (<span style="color: #cf0000;">decode-deep</span> </b><i>r</i><b>)))))
(defun <u><span style="color: #cf0000;">encode-deep</span></u> (</b><i>r</i><b>)
(cond ((symbolp </b><i>r</i><b>) </b><i>r</i><b>)
((listp </b><i>r</i><b>)(if (eq (first </b><i>r</i><b>) (quote </b><i>q</i><b>))
(make-symbol (write-to-string </b><i>r</i><b>))
(mapcar (quote <span style="color: #cf0000;">encode-deep</span>) </b><i>r</i><b>)))))
(defun <u><span style="color: #cf0000;">strip-q</span></u> (</b><i>r</i><b>) (first (rest </b><i>r</i><b>)))
(defun <u><span style="color: #cf0000;">symbol->sexpr</span></u> (</b><i>r</i><b>)
(<span style="color: #cf0000;">encode-deep</span> (<span style="color: #cf0000;">strip-q</span> (read-from-string (string </b><i>r</i><b>)))))
-------------
[43]> (setq </b><i>q0</i><b> (sexpr->symbol (list (quote </b><i>b</i><b>) (quote </b><i>c</i><b>))))
<span style="color: #cf0000;">#:|(Q (B C))|</span>
[44]> (setq </b><i>s</i><b> (sexpr->symbol (list (quote </b><i>a</i><b>) </b><i>q0</i><b>)))
<span style="color: #cf0000;">#:|(Q (A (Q (B C))))|</span>
[45]> (setq </b><i>s0</i><b> (symbol->sexpr </b><i>s</i><b>))
<span style="color: #cf0000;">(A #:|(Q (B C))|)</span></b></pre></td></tr>
</tbody></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-74526793149243165162011-07-09T00:17:00.025+02:002011-08-17T01:57:26.092+02:00Another Encoding of S-expressions in Symbols.<span style="color: black;">.</span><br />
<br />
<br />
<br />
<br />
<center><table cellpadding="50" style="background: none repeat scroll 0% 0% white; color: black; padding: 20px; text-align: justify; width: 640px;"><tbody style="text-align: left;">
<tr style="text-align: left;"><td style="color: black; font-family: 'Times New Roman',Times,serif; font-size: 100%; text-align: justify;"><div style="color: #cf0000; font-size: 161%; font-weight: bold; padding-bottom: 40px; text-align: center;">
Another Encoding of S-expressions in Symbols.</div>
Unlike encoding from the last post, this one maintains form of <i>S-expression</i>. If <i>e</i> is <i>S-expression</i>, then its code is <u>symbol</u> <span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>(Q </b></span><i>e</i><span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>)</b></span>. <br />
<br />
<i>Encoding</i><b> </b>is relatively simple, because built in functions for conversion of symbols and strings into symbols can be used; especially if symbols converted to strings are not encapsulated within vertical bars or quotation marks. <i>Decoding<b> </b></i>is slightly more complicated. For instance, symbol<br />
<br />
<div style="text-align: center;">
<span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>(Q (a (Q b)))</b></span></div>
<br />
should be decoded into list <span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>(a (Q b))</b></span> where <span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>(Q b)</b></span> isn't list, but symbol. Hence, built in conversion functions are not enough, but one must define his own "code walker." The code in Newlisp follows. <br />
<br />
<pre style="background: #ffefef; border: 2px solid #cf0000; color: black; font-family: Consolas,monospace,fixed; font-weight: bold; padding: 20px;">(define (<span style="color: #990000;">sexpr->symbol</span> <i><span style="color: black; font-weight: normal;">r</span></i>) (sym (string (list (quote <i><span style="color: black; font-weight: normal;">Q</span></i>) <i><span style="color: black; font-weight: normal;">r</span></i>))))
(define (<span style="color: #990000;">qlist?</span> <i><span style="color: black; font-weight: normal;">r</span></i>)
(and (list? <i><span style="color: black; font-weight: normal;">r</span></i>)
(not (empty? <i><span style="color: black; font-weight: normal;">r</span></i>))
(= (first <i><span style="color: black; font-weight: normal;">r</span></i>) (quote <i><span style="color: black; font-weight: normal;">Q</span></i>))))
(define (<span style="color: #990000;">symbol->sexpr</span> <i><span style="color: black;font-weight: normal;">r</span></i>)
(let((<i><span style="color: black;font-weight: normal;">codewalker</span></i>
(lambda(<i><span style="color: black; font-weight: normal;">r</span></i>)
(cond ((symbol? <i><span style="color: black; font-weight: normal;">r</span></i>) <i><span style="color: black; font-weight: normal;">r</span></i>)
((<span style="color: #990000;">qlist?</span> <i><span style="color: black; font-weight: normal;">r</span></i>) (sym (string <i><span style="color: black; font-weight: normal;">r</span></i>)))
((not (qlist? <i><span style="color: black; font-weight: normal;">r</span></i>)) (map <i><span style="font-weight: normal;color:black;">codewalker </span><span style="color: black; font-weight: normal;">r</span></i>))))))
(codewalker (last (read-expr (string <i><span style="color: black; font-weight: normal;">r</span></i>))))))
--------
> (setq <i><span style="color: black; font-weight: normal;">s</span></i> (sexpr->symbol (quote (<i><span style="color: black; font-weight: normal;">a</span></i> <i><span style="color: black; font-weight: normal;">b</span></i>))))
<span style="color: #cf0000;">(Q (a b))</span>
> (symbol? <i><span style="color: black; font-weight: normal;">s</span></i>)
<span style="color: #cf0000;">true</span>
> (setq <i><span style="color: black; font-weight: normal;">q0</span></i> (sexpr->symbol (quote <i><span style="color: black; font-weight: normal;">b</span></i>)))
<span style="color: #cf0000;">(Q b)</span>
> (setq <i><span style="color: black; font-weight: normal;">s</span></i> (sexpr->symbol (list (quote <i><span style="color: black; font-weight: normal;">a</span></i>) <i><span style="color: black; font-weight: normal;">q0</span></i>)))
<span style="color: #cf0000;">(Q (a (Q b)))</span>
> (symbol? <i><span style="color: black; font-weight: normal;">s</span></i>)
<span style="color: #cf0000;">true</span>
> (setq <i><span style="color: black; font-weight: normal;">s0</span></i> (symbol->sexpr <i><span style="color: black; font-weight: normal;">s</span></i>))
<span style="color: #cf0000;">(a (Q b))</span>
> (symbol? <i><span style="color: black; font-weight: normal;">s0</span></i>)
<span style="color: #cf0000;">nil</span>
> (symbol? (last <i><span style="color: black; font-weight: normal;">s0</span></i>))
<span style="color: #cf0000;">true</span>
</pre>
<br />
Behaviour of <span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed; font-weight: bold;">Q</span> strongly reminds on <span style="background-color: #ffefef; color: black; font-family: Consolas,monospace,fixed;"><b>QUOTE</b></span>. <br />
<br /></td></tr>
</tbody></table>
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-69380317010824761192011-07-05T15:02:00.017+02:002011-08-24T03:06:22.264+02:00More Sophisticated Encoding of S-exprs into Symbols.<br />
<br />
<center style="font-family: 'Times New Roman',Times,serif;"><br />
<table cellpadding="50" style="background: none repeat scroll 0% 0% white; color: black; padding: 20px; text-align: justify; width: 640px;"><tbody>
<tr style="text-align: justify;"><td><div style="color: #cf0000; font-family: 'Times New Roman',Times,serif; font-size: 161%; padding-bottom: 50px; text-align: center;"><b>
More Sophisticated Encoding of S-exprs into Symbols</b></div>
<i>Encoding of S-expressions into symbols</i> is frequent topic of
discussion in this blog. It is motivated by the idea that
<a href="http://kazimirmajorinc.blogspot.com/2009/12/symbols-as-sexprs.html" style="background: none repeat scroll 0% 0% rgb(255, 255, 255); color: #dd0000; text-decoration: underline;">names should be equally flexible as S-expressions</a>. (Actually,
it might be the best if not only every symbol is S-expression,
but also every S-expression is the symbol. OK, it is almost
mystical statement.)<br />
<br />
Trivial encoding was demonstrated in <a href="http://kazimirmajorinc.blogspot.com/2011/07/sexpr-symbol-and-symbol-sexpr-in-six.html" style="background: none repeat scroll 0% 0% rgb(255, 255, 255); color: #dd0000; text-decoration: underline;">last post</a>: S-expression is encoded in symbol which has exactly same
characters as printed representation of S-expression. For instance, <i>S-expression</i> <b style="background-color: #ffeeee; font-family: Consolas,monospace;">(+ a b)</b> is encoded into <i>symbol </i><b style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">(+ a b)</b>. This trivial encoding has some limitations. For instance, if we
look at symbol <br />
<br />
<div style="font-family: Consolas,monospace; text-align: center;">
<span style="background-color: #ffeeee; color: black; font-weight: bold;">((+ a b) c)</span></div>
<br />
and try to decode it, we'll find that it cannot be determined whether
<b style="background-color: #ffeeee; font-family: Consolas,monospace;">(+ a b)</b> is S-expression, or it is symbol. In some Lisp dialects (Common Lisp, Picolisp, ISLisp) there is no such problem. Symbol
<b style="background-color: #ffeeee; font-family: Consolas,monospace;">(+ a b)</b> is written as <b style="background-color: #ffeeee; font-family: Consolas,monospace;">|(+ a b)|</b> so difference
between S-expression and symbol is obvious. However, in these dialects,
repeated encoding results in <a href="http://kazimirmajorinc.blogspot.com/2011/06/exponential-explosion-of-escape.html" style="background: none repeat scroll 0% 0% rgb(255, 255, 255); color: #dd0000; text-decoration: underline;">the symbols that grow exponentially</a>.<br />
<br />
In this post more sophisticated encoding, without that problem, is presented. Let us define encoding <i>k</i>, such that
for every S-expression <i>e</i>, <i>k</i>(<i>e</i>) is defined as follows.<br />
<ol>
<li>If <i>e</i> is symbol, then <i>k</i>(<i>e</i>) = <i>e</i><b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">;</b></li>
<li>if <i>e</i> = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">(</b><i>e</i><sub>1</sub> ... <i>e<sub>n</sub></i><b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">)</b> then <i>k</i>(<i>e</i>) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">[</b><i>k</i>(<i>e</i><sub>1</sub>) <i>k</i>(<i>e</i><sub>2</sub>) ... <i>k</i>(<i>e<sub>n</sub></i>)<b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">];</b>
</li>
</ol>
Semi-colon is part of the symbol. For instance<br />
<br />
<div style="text-align: center;">
<i>k</i>(<b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">a</b>) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">a;</b><br />
<i>k</i>(<b style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">(a b)</b>) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">[</b><i>k</i>(<b><span style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">a</span></b>) <i>k</i>(<b><span style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">b</span></b>)<b style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">];</b> =<b> <span style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">[a;b;];</span></b></div>
<br />
If only codes of the S-expressions contain characters <b><span style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">[</span></b>, <b><span style="background-color: #ffeeee;font-family: Consolas,monospace;color:black;font-weight:bold;">]</span></b> and <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">;</span></b>, then encoding <i>k</i> is <i>injection</i>, i.e. for two S-expressions<i> e</i> and <i>f</i>,<br />
<br />
<div style="text-align: center;">
<i>k</i>(<i> e</i> ) =<i> k</i>(<i> f </i>) => <i>e</i> = <i>f</i>. </div>
<br />
Furthermore, there is no exponential explosion in case of multiple
encoding. For instance,<br />
<br />
<div style="text-align: center;">
<i>k</i>(<b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">(a b)</b>) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">[a;b;];</b><br />
<i>k</i>(<i>k</i>(<b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">(a b)</b>)) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">[a;b;];;</b><br />
<i>k</i>(<i>k</i>(<i>k</i>(<b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">(a b)</b>))) = <b style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">[a;b];;;</b></div>
<br />
Here is implementation of encoding and decoding in R<sup>5</sup>RS Scheme. <br />
<div style="background-color: #ffeeee;font-family: Consolas,monospace;font-weight:bold;">
<pre style="background: none; border: 2px solid #cf0000; padding: 20px; text-align: left;font-family: Consolas,monospace;font-weight:bold;"><b>(define (<span style="color: #990000;">sexpr->string</span> L)
(string-append
(if (symbol? L) (symbol->string L)
(string-append
"["
(apply string-append
(map sexpr->string L))
"]"))
";"))
(define (<span style="color: #990000;">sexpr->symbol</span> L)
(string->symbol (sexpr->string L)))
(define (<span style="color: #990000;">string->sexpr</span> S)
(let((S1 (substring S 0 (- (string-length S) 1))))
(if (equal? (string-ref S1 (- (string-length S1) 1)) #\])
(let((substring-begin 1)
(level 0)
(result (list)))
(do ((i 1 (+ i 1)))
((= i (string-length S1)) result)
(if (and (= level 0)
(equal? (string-ref S1 i) #\;)
(not (equal? (string-ref S1 (+ i 1)) #\;)))
(begin
(set! result
(append result
(list (string->sexpr
(substring S1
substring-begin
(+ i 1))))))
(set! substring-begin (+ i 1))))
(cond ((equal? (string-ref S1 i) #\[)
(set! level (+ level 1)))
((equal? (string-ref S1 i) #\])
(set! level (- level 1))))))
(string->symbol (substring S 0 (- (string-length S) 1))))))
(define (<span style="color: #990000;">symbol->sexpr</span> s)
(string->sexpr (symbol->string s)))</b>
<b>
-------------------------
</b>
<b>> (sexpr->symbol (quote (a b)))
<span style="color: #990000;">|[a;b;];|</span>
> (define s2 (sexpr->symbol (quote (|[a;b;];| c))))
> s2
<span style="color: #990000;">|[[a;b;];;c;];|</span>
> (symbol->sexpr s2)
<span style="color: #990000;">(|[a;b;];| c)</span></b>
</pre></div></td></tr></tbody></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-86687147517433637092011-06-27T18:11:00.010+02:002011-09-02T00:42:18.758+02:00Exponential Explosion of Escape Characters.<style type="text/css">
i {background:white;color:black;font-family:serif;}
pre {background:white;color:black;font-family:serif;}
span {color:lime;}
.S0 {font-family: Consolas, monospace;font-weight:bold;
color: #0000FF;
}
.S1 {font-family: Consolas, monospace;font-weight:bold;
color: #FF7F7F;
}
.S2 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
.S3 {font-family: Consolas, monospace;font-weight:bold;
color: #BF0000;
}
.S5 {font-family: Consolas, monospace;font-weight:bold;
background: #FFEFEF;
color: #CF0000;
}
.S6 {font-family: Consolas, monospace;font-weight:bold;
color: #7F0000;
background: #FFEFEF;
text-decoration: inherit;
}
.S9 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
.S10 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
</style> <br />
<b><br /></b><br />
<center>
<table width='640' style="background: none repeat scroll 0% 0% white; color: black; padding: 50px; text-align: left;"><tbody>
<tr><td style="color:black;text-align:left;font-weight:bold;padding:20px;background:white;">
<h1 style="font-size:161%;background:white;color:#d00000;text-align:center;font-family:'Times New Roman',Times,serif;font-weight:bold;">Exponential Explosion of Escape Characters<br /><br /><br /></h1>
<div style="font-family:'Times New Roman';">
This time, Common Lisp:
</div><br /><br />
<table style="background: none repeat scroll 0% 0% #ffefef; color: black; text-align: left;"><tbody>
<tr><td>
<div style="background:#ffefef;padding:20px;border:1px solid #efdfdf;">
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q nil)</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #990000; font-family: "Courier New",Courier,monospace;">
<b>NIL</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #990000; font-family: "Courier New",Courier,monospace;">
<b>#:NIL</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #990000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:NIL|</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #990000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:NIL\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:NIL\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:NIL\\\\\\\|\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:\\\\\\\\\\\\\\\|#:NIL\\\\\\\\\\\\\\\|\\\\\\\|\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:NIL</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\|\\\\\\\|\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:NIL\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\|\\\\\\\\\\\\\\\|\\\\\\\|\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:NIL\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\|\\\\\\\|\\\|\||</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b>? (setf q (make-symbol (write-to-string q)))</b></div>
<div style="font-family: "Courier New",Courier,monospace;">
<b><br /></b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>#:|#:\|#:\\\|#:\\\\\\\|#:\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|#:NIL\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|\\\\\\\\\\\\\\\|\\\\\\\|\\</b></div>
<div style="color: #cc0000; font-family: "Courier New",Courier,monospace;">
<b>\|\||</b></div>
</div>
</td></tr></tbody></table>
</td></tr>
</tbody></table>
<div style="font-family: "Courier New",Courier,monospace;">
</div>
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-62581615068788608312011-05-07T23:20:00.035+02:002011-09-02T00:35:51.302+02:00Tangent.<style type="text/css">
i {background:white;color:black;font-family:serif;}
pre {background:white;color:black;font-family:serif;}
span {color:lime;}
.S0 {font-family: Consolas, monospace;font-weight:bold;
color: #0000FF;
}
.S1 {font-family: Consolas, monospace;font-weight:bold;
color: #FF7F7F;
}
.S2 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
.S3 {font-family: Consolas, monospace;font-weight:bold;
color: #BF0000;
}
.S5 {font-family: Consolas, monospace;font-weight:bold;
background: #FFEFEF;
color: #CF0000;
}
.S6 {font-family: Consolas, monospace;font-weight:bold;
color: #7F0000;
background: #FFEFEF;
text-decoration: inherit;
}
.S9 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
.S10 {font-family: Consolas, monospace;font-weight:bold;
color: #000000;
}
</style> .<br /><br /><br /><center> <table border='0' bordercolor='#7f0000' style="background-color: #7f0000; color:black;font-family:serif;" width='640'><tr><td style="padding:40px;background-color: white;"> <center> <table style="background-color: white; color:black; font-family:serif; max-width:100%;"><tbody>
<tr><td style="background-color: white; color:black; font-family:serif;text-align:justify;"><h1 style="text-align: center; color:#cf0000; background-color:white;font-family:'Times New Roman',Times,serif;font-weight:bold;font-size:161%;">Tangent<br />
</h1><br />
<br />
The specificity of Lisp is, maybe, best visible on problems that require processing of data naturally represented as S-expressions. An example of such problem is "<a href="http://kazimirmajorinc.blogspot.com/2009/09/probability-that-random-propositional.html" style="color:#c00000;background:#FFEFEF;text-decoration:underline;">Probability that random propositional formula is tautology</a>." In this post, the variation of classical example - symbolic differentiation - is presented: newLISP (and it is very similar in other Lisps) program that computes the tangent of the graph of the function <em>f</em> of single variable, defined as composition of elementary functions (+, -, sin, cos ...) in given point <em>x</em><sub style="font-size: x-small">0</sub>. The tangent of the function <em>f</em> in <em>x</em><sub style="font-size: x-small">0 </sub>is defined as linear function <br />
<br />
<div style="text-align:center;"><em>y</em>(<em>x</em>)<em> </em>=<em> a</em>·(<em>x </em>-<em> x</em><sub style="font-size: x-small">0</sub>) +<em> b</em>,</div><br />
where <em>a</em> = <em>f </em>'(<em>x</em><sub style="font-size: x-small">0</sub>) and <em>b</em> = <em>f</em>(<em>x</em><sub style="font-size: x-small">0</sub>). The program consists of:<br />
<br />
<ul><li>The function <span style="font-family: Consolas, monospace;color:#c00000;"><strong>tangent</strong></span> that accepts two arguments: the function <span style="font-family: Consolas, monospace; color: #C00000;"><strong>f</strong></span> in form of lambda list and the floating point number <span style="font-family: Consolas, monospace; color: #C00000;"><strong>x0</strong></span>. The function <span style="font-family: Consolas, monospace; color: #C00000"><strong>tangent</strong></span> analyzes the code of the function <span style="color: #C00000; font-family: Consolas, monospace"><strong>f</strong></span>, calculates the values <span style="color: #C00000; font-family: Consolas, monospace"><strong>a</strong></span> and <span style="font-family: Consolas, monospace; color: #C00000"><strong>b</strong></span> according to mathematical definition of tangent (see above) and constructs the code of the function <br />
<br />
<div style="text-align: center; font-family: Consolas, monospace; color: #C00000"><strong>(lambda(x)(+. (*. a (-. x x0)) b))</strong></div><br />
where symbols <span style="color: #C00000; font-family: Consolas, monospace"><strong>a</strong></span>, <span style="color: #C00000; font-family: Consolas, monospace"><strong>b</strong></span> and <span style="color: #C00000; font-family: Consolas, monospace"><strong>x0</strong></span> are replaced with their respective values; that function is then returned as result of the function <span style="color: #C00000; font-family: Consolas, monospace"><strong>tangent</strong></span>. The implementation is very short, but it delegates main part of the work to the function <span style="font-family: Consolas, monospace; color: #C00000"> <strong>d</strong></span>. </li>
<li>The function <span style="font-family: Consolas, monospace; color: #C00000;"><strong>d</strong></span> accepts two arguments: <span style="font-family: Consolas, monospace; color: #C00000"> <strong>formula</strong></span> and <span style="color: #C00000; font-family: Consolas, monospace"><strong>variable</strong></span>. It returns the expression obtained by <em>symbolic differentiation</em> of the <span style="font-family: Consolas, monospace; color: #C00000;"><strong>formula</strong></span> for given <span style="font-family: Consolas, monospace; color: #C00000;"><strong>variable</strong></span>. It is main function in this program, typical recursive "code walking" through <span style="color: #C00000; font-family: Consolas, monospace"><strong>formula</strong></span>. Simple "domain specific language" is used for descriptions of the rules for symbolic differentiation that should be applied, for example <br />
<br />
<div style="text-align: center; font-family: Consolas, monospace; color: #C00000;"><strong>(+. (*. df g) (*. f dg))</strong></div><br />
for multiplication. The application of rules for symbolic differentiation frequently give result that can be simplified. For instance, derivation of <span style="color: #C00000; font-family: Consolas, monospace"> <strong>(*. 2 x)</strong></span> is<br />
<br />
<div style="font-family: Consolas, monospace; color: #C00000; text-align: center;"> <strong>(+. (*. 0 x) (*. 2 1))</strong></div><br />
so function <span style="font-family: Consolas, monospace; color: #C00000;"><strong>simplify</strong></span> is called when appropriate.</li>
<li>The function <span style="font-family: Consolas, monospace; color: #C00000;"><strong>simplify</strong></span> accepts only one argument: symbolic expression <span style="color: #C00000; font-family: Consolas, monospace"><strong>formula</strong></span>. It analyzes and simplify formula, again, using typical recursive "code walking". For instance, S-expression <span style="font-family: Consolas, monospace; color: #C00000;"><strong>(- x x)</strong></span> is simplified to <span style="font-family: Consolas, monospace; color: #C00000;"><strong>0</strong></span>. There are infinitely many possible rules for simplification; the function performs only few of these. The function uses <span style="font-family: Consolas, monospace; color: #C00000;"><strong>eval</strong></span> at one place: if some expression contains only operators and constants, but not variables then the easisest way to simplify it is to <span style="font-family: Consolas, monospace; color: #C00000;"><strong>eval</strong></span> it. (One might speculate that <span style="font-family: Consolas, monospace; color: #C00000;"><strong>simplify</strong></span> is generalized <span style="font-family: Consolas, monospace; color: #C00000;"><strong>eval</strong></span>.) <span style="font-family: Consolas, monospace; color: #C00000;"><strong>Simplification</strong></span> is, actually, not necessary for computation of the <span style="font-family: Consolas, monospace; color: #C00000;"><strong>tangent</strong></span>. However, its use in the context of symbolic differentiation is reasonable.</li>
</ul>Few operators from my library are used; function <span style="color: #C00000; font-family: Consolas, monospace"><strong>expand//</strong></span> i.e. parallel expand, fexpr <span style="color: #C00000; font-family: Consolas, monospace"><strong>println=</strong></span> for convenient printing and floating point arithmetic operators <span style="color: #C00000; font-family: Consolas, monospace"><strong>+.</strong></span>, <span style="color: #C00000; font-family: Consolas, monospace"><strong>-.</strong></span>, <span style="color: #C00000; font-family: Consolas, monospace"><strong>*.</strong></span> and <span style="color: #C00000; font-family: Consolas, monospace"><strong> /.</strong></span>, synonymous for built-in <span style="color: #C00000; font-family: Consolas, monospace"><strong>add</strong></span>, <span style="font-family: Consolas, monospace; color: #C00000"><strong>sub</strong></span>, <span style="font-family: Consolas, monospace; color: #C00000"><strong>mul</strong></span> and <span style="color: #C00000; font-family: Consolas, monospace"><strong> div</strong></span>. These functions are not essential.<br />
<br />
The graph of the complicated function and tangent on the curve suggests that program, generally, works.<br />
<br />
<span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S9">f0</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">+.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sin</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S2">12</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">cos</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S2">32</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><span class="S0"> </span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">tan</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S2">1.4</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">asin</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">acos</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">atan</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cos</span><span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S2">7</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S2">9</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">pow</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sinh</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cosh</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">asinh</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">sin</span><span class="S0"> </span><span class="S10">(</span><span class="S3">acosh</span><span class="S0"> </span><span class="S10">(</span><span class="S3">+.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">atanh</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))))</span><br />
<span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S9">x0</span><span class="S0"> </span><span class="S2">0.4</span><span class="S10">)</span><br />
<span class="S10">(</span><span class="S3">println=</span><span class="S0"> </span><span class="S10">(</span><span class="S9">tangent</span><span class="S0"> </span><span class="S9">f0</span><span class="S0"> </span><span class="S9">x0</span><span class="S10">))</span><br />
<span class="S1">; (tangent f0 x0)=(lambda (x) (+. (*. -21.491 (-. x 0.4)) 10.252))</span> <br />
<br />
<br />
<center> <img alt="graph" height="330" src="http://www.instprog.com//blogposts/tangent/tangent.png" style="text-align: center" width="330" /><br />
</center> <br />
<br />
Finally, the code:<br />
</td></tr>
</tbody></table><table border='0' bordercolor='#ff0000' style="text-align:left;background:white;"><tr><td style="text-align:left;background:white;"><pre><span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S10">[</span><span class="S9">print.supressed</span><span class="S10">]</span><span class="S0"> </span><span class="S3">true</span><span class="S0"> </span><span class="S10">[</span><span class="S9">println.supressed</span><span class="S10">]</span><span class="S0"> </span><span class="S3">true</span><span class="S10">)</span>
<span class="S10">(</span><span class="S3">load</span><span class="S0"> </span><span class="S6">"http://www.instprog.com/Instprog.default-library.lsp"</span><span class="S10">)</span>
<span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S10">[</span><span class="S9">print.supressed</span><span class="S10">]</span><span class="S0"> </span><span class="S3">nil</span><span class="S0"> </span><span class="S10">[</span><span class="S9">println.supressed</span><span class="S10">]</span><span class="S0"> </span><span class="S3">nil</span><span class="S10">)</span>
<span class="S10">(</span><span class="S3">define</span><span class="S0"> </span><span class="S10">(</span><span class="S9">tangent</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">x0</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">variable</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">expression</span><span class="S0"> </span><span class="S10">(</span><span class="S3">last</span><span class="S0"> </span><span class="S9">f</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">derived-expression</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">expression</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">a</span><span class="S0"> </span><span class="S10">(</span><span class="S3">eval</span><span class="S0"> </span><span class="S10">(</span><span class="S3">expand</span><span class="S0"> </span><span class="S9">derived-expression</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S9">variable</span><span class="S0"> </span><span class="S9">x0</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">b</span><span class="S0"> </span><span class="S10">(</span><span class="S9">f</span><span class="S0"> </span><span class="S9">x0</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">expand//</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">x</span><span class="S10">)(</span><span class="S3">+.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">a</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S9">x0</span><span class="S10">))</span><span class="S0"> </span><span class="S9">b</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">'</span><span class="S5">a</span><span class="S0"> </span><span class="S10">'</span><span class="S5">b</span><span class="S0"> </span><span class="S10">'</span><span class="S5">x0</span><span class="S10">)))</span>
<span class="S10">(</span><span class="S3">define</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">formula</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">=</span><span class="S0"> </span><span class="S9">formula</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">atom?</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">list?</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">operator</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">operands</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">expr</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">flatexpr</span><span class="S0"> </span><span class="S10">(</span><span class="S3">flat</span><span class="S0"> </span><span class="S9">expr</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">f</span><span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S10">'</span><span class="S5">f</span><span class="S0"> </span><span class="S9">flatexpr</span><span class="S10">)(</span><span class="S9">operands</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S10">'</span><span class="S5">df</span><span class="S0"> </span><span class="S9">flatexpr</span><span class="S10">)(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">g</span><span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S10">'</span><span class="S5">g</span><span class="S0"> </span><span class="S9">flatexpr</span><span class="S10">)(</span><span class="S9">operands</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">dg</span><span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S10">'</span><span class="S5">dg</span><span class="S0"> </span><span class="S9">flatexpr</span><span class="S10">)(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">g</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">expand//</span><span class="S0"> </span><span class="S9">expr</span><span class="S0"> </span><span class="S10">'</span><span class="S5">f</span><span class="S0"> </span><span class="S10">'</span><span class="S5">df</span><span class="S0"> </span><span class="S10">'</span><span class="S5">g</span><span class="S0"> </span><span class="S10">'</span><span class="S5">dg</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">case</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">+.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">+.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">op</span><span class="S10">)(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">op</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">op</span><span class="S10">)(</span><span class="S9">d</span><span class="S0"> </span><span class="S9">op</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">case</span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'</span><span class="S5">df</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S2">2</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">+.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S9">g</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">dg</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">true</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S9">variable</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">case</span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">/.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S2">2</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S9">g</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">dg</span><span class="S10">))</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">g</span><span class="S0"> </span><span class="S9">g</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">true</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">/.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S9">variable</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">pow</span><span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">exp</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">g</span><span class="S0"> </span><span class="S10">(</span><span class="S3">log</span><span class="S0"> </span><span class="S9">f</span><span class="S10">))))</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">exp</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">log</span><span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S9">f</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">d</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">log</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">log</span><span class="S0"> </span><span class="S9">g</span><span class="S10">)))</span><span class="S0"> </span><span class="S9">variable</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S2">0.5</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">sin</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cos</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cos</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sin</span><span class="S0"> </span><span class="S9">f</span><span class="S10">))</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">tan</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">pow</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cos</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S2">2</span><span class="S10">))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">asin</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">))))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">acos</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)))))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">atan</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">+.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">sinh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cosh</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cosh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sinh</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">tanh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">*.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">pow</span><span class="S0"> </span><span class="S10">(</span><span class="S3">tanh</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S2">2</span><span class="S10">))</span><span class="S0"> </span><span class="S9">df</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">asinh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S3">+.</span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">acosh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">sqrt</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">atanh</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lexpand</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S9">df</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S10">(</span><span class="S3">*.</span><span class="S0"> </span><span class="S9">f</span><span class="S0"> </span><span class="S9">f</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">))))))</span>
<span class="S10">(</span><span class="S3">define</span><span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">atom?</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">list?</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">operator</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">operands</span><span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">formula</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; if all operands are constants, then </span>
<span class="S0"> </span><span class="S1">; simplified formula is evaluated formula</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">for-all</span><span class="S0"> </span><span class="S3">number?</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)(</span><span class="S3">eval</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (*. x), (+. x) => x</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">or</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">+.</span><span class="S10">))</span><span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (*. ... 0 ...) => 0 </span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S2">0</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (*. ... 1 ...) => (*. ...)</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S2">1</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">clean</span><span class="S0"> </span><span class="S10">(</span><span class="S3">curry</span><span class="S0"> </span><span class="S3">=</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (+. ... 0 ...) => 0</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">+.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">find</span><span class="S0"> </span><span class="S2">0</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">clean</span><span class="S0"> </span><span class="S3">zero?</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (-. (-. ...)) => ...</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">match</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">-.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">-.</span><span class="S0"> </span><span class="S3">?</span><span class="S10">))</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">last</span><span class="S0"> </span><span class="S10">(</span><span class="S3">last</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (-. minuend ...)</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">-.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">></span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">minuend</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">subtrahends</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">subtrahend</span><span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">+.</span><span class="S0"> </span><span class="S9">subtrahends</span><span class="S10">))))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span><span class="S10">((</span><span class="S3">zero?</span><span class="S0"> </span><span class="S9">minuend</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">-.</span><span class="S0"> </span>
<span class="S0"> </span><span class="S9">subtrahend</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">zero?</span><span class="S0"> </span><span class="S9">subtrahend</span><span class="S10">)</span><span class="S0"> </span><span class="S9">minuend</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">=</span><span class="S0"> </span><span class="S9">minuend</span><span class="S0"> </span><span class="S9">subtrahend</span><span class="S10">)</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">true</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">-.</span><span class="S0"> </span><span class="S9">minuend</span><span class="S0"> </span>
<span class="S0"> </span><span class="S9">subtrahend</span><span class="S10">)))))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (/. (/. ...))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">match</span><span class="S0"> </span><span class="S10">'(</span><span class="S3">/.</span><span class="S0"> </span><span class="S10">(</span><span class="S3">/.</span><span class="S0"> </span><span class="S3">?</span><span class="S10">))</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">last</span><span class="S0"> </span><span class="S10">(</span><span class="S3">last</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S1">; (/. dividend ...)</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">and</span><span class="S0"> </span><span class="S10">(</span><span class="S3">=</span><span class="S0"> </span><span class="S9">operator</span><span class="S0"> </span><span class="S10">'</span><span class="S5">/.</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">></span><span class="S0"> </span><span class="S10">(</span><span class="S3">length</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">dividend</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">divisors</span><span class="S0"> </span><span class="S10">(</span><span class="S3">rest</span><span class="S0"> </span><span class="S9">operands</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">divisor</span><span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">cons</span><span class="S0"> </span><span class="S10">'</span><span class="S5">*.</span><span class="S0"> </span><span class="S9">divisors</span><span class="S10">))))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span><span class="S10">((</span><span class="S3">zero?</span><span class="S0"> </span><span class="S9">dividend</span><span class="S10">)</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">=</span><span class="S0"> </span><span class="S9">divisor</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)</span><span class="S0"> </span><span class="S9">dividend</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">=</span><span class="S0"> </span><span class="S9">divisor</span><span class="S0"> </span><span class="S9">-1</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S9">simplify</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">-.</span><span class="S0"> </span><span class="S9">dividend</span><span class="S10">)))</span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">=</span><span class="S0"> </span><span class="S9">dividend</span><span class="S0"> </span><span class="S9">divisor</span><span class="S10">)</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">true</span><span class="S0"> </span><span class="S10">(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">'</span><span class="S5">/.</span><span class="S0"> </span><span class="S9">dividend</span><span class="S0"> </span><span class="S9">divisor</span><span class="S10">)))))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">true</span><span class="S0"> </span><span class="S9">formula</span><span class="S10">))))))</span>
</pre></td></tr>
</tbody></table></center> </td></tr>
</table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-39267749042220006482011-05-03T15:17:00.015+02:002011-09-02T01:33:58.528+02:00Conflation of Subtraction and Additive Inverse in Lisp.<style type="text/css">
i {background:white;color:black;font-family:serif;}
pre {background:white;color:black;font-family:serif;}
span {color:black;}
</style><br />
<table width='100%'style="color:black; font-family:serif;"><tbody>
<tr><td style="color:black; font-family:serif;"><br />
<center><table width='640' cellpadding='50' style="background-color: white; color:black; font-family:serif;"><tbody>
<tr><td style="background-color: white; color:black; font-family:serif;text-align:justify;"><h1 style="font-size:161%;text-align: center; color:#cf0000; background-color:white;font-family:serif;font-weight:bold;">Conflation of Subtraction and Additive Inverse in Lisp<br /><br /></h1>
In mathematics, the symbol - is used as name of two different operations: subtraction and additive inverse. For instance, that symbol has different meaning in the expressions (-3)+7 and (6-3)+7. There is no ambiguity. The edge case of subtraction<br \><br />
<div style="text-align: center;"><i>c</i> - <i>b</i><sub>1</sub> - <i>b</i><sub>2</sub> - ... - <i>b</i><sub><i>n</i></sub></div><br />
for <i>n</i> = 0, i.e. <i>subtraction with zero subtrahends</i>, is <i>c</i>, which is clearly different than <i>additive inverse</i> of <i>c</i>: -<i> c</i>. However, in prefix notation use of the same symbol for two different operators will cause ambiguity so <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(- c)</span> can be interpreted as both <i>additive inverse</i> of <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">c</span> and <i>the edge case of subtraction with zero subtrahends</i>. Designers of almost all Lisp dialects have chosen to keep the same symbol and implement both operations. The decision is based on the number of operands: if there is only one operand, operator <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">-</span> behaves as additive inverse; if there is two or more operands <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">-</span> behaves as subtraction.<br />
<br />
This decision rarely causes any problems with "hand written" expressions because humans automatically, without much thinking, reduce edge case of subtraction to minuend, so, we'll not see the edge case of subtraction in any mathematical formulas. However, if expressions are processed by programs the reduction of the edge case doesn't happen automatically. For instance, the program that simplifies arithmetic expression could contain the function that deletes zeroes from subtrahends. That function should accept expression as<br />
<br />
<div style="font-family: Consolas, monspace; text-align: center;"><span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(- c b1 0 b2 0 0 0)</span></div><br />
as argument and return expression<br />
<br />
<div style="font-family: Consolas, monspace; text-align: center;"><span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(- c b1 b2)</span>.</div><br />
However, simple implementation like this one in Newlisp <br />
<pre style="background-color: #ffffff;background-image:none;font-weight:bold;padding:10px;"><span style="color:#800000;font-family: Consolas,monospace;">(define (simplify E)</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (let ((operator (first E))</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (minuend (first (rest E)))</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (subtrahends (rest (rest E))))</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (setf new-subtrahends (clean zero? subtrahends))</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (append (list operator)</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> (list minuend)</span>
<span style="color:#800000;font-family: Consolas,monospace;font-weight:bold;"> new-subtrahends)))</span></pre>
will not work correctly, because, for instance, <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(- 3 0)</span> will be reduced into <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(- 3)</span> and these two expressions have not the same value. Explicit treatment of the edge case is required:<br />
<pre style="background-color: #ffffff;background-image:none;font-weight:bold;"><span style="color:#007000;font-family: Consolas,monospace;padding:10px;;font-weight:bold;">(define (simplify E)</span>
<span style="color:#007000;font-family: Consolas,monospace;;font-weight:bold;"> (let ((operator (first E))</span>
<span style="color:#007000;font-family: Consolas,monospace;;font-weight:bold;"> (minuend (first (rest E)))</span>
<span style="color:#007000;font-family: Consolas,monospace;"> (subtrahends (rest (rest E))))</span>
<span style="color:#007000;font-family: Consolas,monospace;"> (setf new-subtrahends (clean zero? subtrahends))</span>
<span style="color:#007000;font-family: Consolas,monospace;"> (if (empty? new-subtrahends)</span>
<span style="color:#007000;font-family: Consolas,monospace;"> minuend</span>
<span style="color:#007000;font-family: Consolas,monospace;"> (append (list operator)</span>
<span style="color:#007000;font-family: Consolas,monospace;"> (list minuend)</span>
<span style="color:#007000;font-family: Consolas,monospace;"> new-subtrahends))))</span></pre>
The second definition is significantly (~ 15%) larger and less consistent: one can get rid of subtrahends equal to zero only if he removes whole subtraction. On the other hand, edge cases for some other operations like addition are well supported in all Lisp dialects: not only that <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(+ a 0)</span> can be safely simplified to <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(+ a)</span>, but even <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(+ 0 0)</span> can be simplified to <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">(+)</span>.<br />
<br />
Hence, merging of the two operators into one could be design mistake. It would be, arguably, better to <br />
<ul><li>define new operator for additive inverse and</li>
<li>extend definition of subtraction on special case with zero subtrahends.</li>
</ul>Of course, S-expressions would look even less similar to arithmetic expressions, however, clarity and consistency over convenience is, I think, the element of the philosophy of Lisp.<br \><br \>It is even more surprising that this merging is generalized: division operator, <span style="font-family: Consolas,monospace;color:#cf0000;font-weight:bold;">/</span> which is not used as divisional inverse in mathematical expressions is used on the way analogous to - in almost all Lisp dialects.<br \><br \> It is hard to expect change in existing Lisp dialects because lot of existing code uses "conflated operator", although I think that such changes should be, gradually, done: <i>the past is finite and future is infinite</i>. However, I think that for future Lisp dialects it would be better to keep the difference between subtraction (division) and additive (multiplicative) inverse. </td></tr>
</tbody></table></center> </td></tr>
</tbody></table>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com2tag:blogger.com,1999:blog-5894839.post-3111387395075919222011-04-26T19:09:00.004+02:002011-09-04T19:06:09.491+02:00Parallel "expand".<style type="text/css">
.S0 { font-family:Consolas,monospace;font-weight:bold;
color: #0000FF;
}
.S1 {font-family:Consolas,monospace;font-weight:bold;
color: #000000;
}
.S2 {font-family:Consolas,monospace;font-weight:bold;
color: #0000CF;
}
.S3 {font-family:Consolas,monospace;font-weight:bold;
color: #BF0000;
}
.S5 {font-family:Consolas,monospace;font-weight:bold;
color: #0000FF;
background: #C7C7FF;
}
.S6 {font-family:Consolas,monospace;font-weight:bold;
color: #7F007F;
background: #FFEFFF;
text-decoration: inherit;
}
.S9 {font-family:Consolas,monospace;font-weight:bold;
color: #0000CF;
/*background: #CFCFFF;*/
}
.S10 {font-family:Consolas,monospace;font-weight:bold;
color: #000000;
}
span {font-family:Consolas,monospace;font-weight:bold;
font-size:104%;font-weight:bold;
}
</style><br />
<br />
<br />
<br />
<center><br />
<table style="background: none repeat scroll 0% 0% white; padding: 3px; text-align: left; width: 640px;"><tbody>
<tr><td style="background: #ffffff; color: black; font-family: serif; font-size: 100%; padding: 50px; text-align: left;"><h1 style="background: none; color: #cf0000; font-family: serif; font-size: 161%; font-weight: bold; padding-bottom: 30px; text-align: center;">
<b>Parallel "Expand"</b></h1>
<span class="S1"><br /></span><br />
Almost all Lisp dialects support both "parallel" and "serial" assignment operators like let and letn in Newlisp. For example<br />
<br />
<div style="color: #990000;">
<span class="S1"> (setf y 1)</span></div>
<div style="color: #990000;">
<span class="S1"> (let((y 2)(x y)) x) ==> 1 (parallel)</span></div>
<br />
but<br />
<br />
<div style="color: #990000;">
<span class="S1"> (setf y 1)</span></div>
<div style="color: #990000;">
<span class="S1"> (letn((y 2)(x y)) x) ==> 2 (serial)</span></div>
<br />
Expand-expression in Newlisp<br />
<br />
<div style="color: #990000; text-align: center;">
<span class="S1"> (expand '(x y) 'x 'y)</span></div>
<br />
results in replacement of <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">x</span> and <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">y</span> in <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">(x y)</span> with values of <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">x</span> and <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">y</span>. Expand-expression in other form:<br />
<br />
<div style="color: #990000; text-align: center;">
<span class="S1"> (expand '(x y) ((x <value1>)(y <value2>)))</span></div>
<br />
results in replacement of <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">x</span> and <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">y</span> in <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">(x y)</span> with <value1> and
<value2>. <br />
<br />
In both cases, the replacement is performed in serial fashion. For
example,<br />
<span class="S1"></span><br />
<div style="color: #990000; text-align: center;">
<span class="S1"> (expand '(x y) '((x y)(y 3))) ==> (3 3)</span></div>
<br />
In this post I present the implementation of parallel expand, <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">expand//</span> in Newlisp; two slashes in name remind on parallel lines such that, for instance<br />
<br />
<div style="color: #990000; text-align: center;">
<span class="S1"> (expand// '(x y) '((x y)(y 3))) ==> (y 3).</span></div>
<br />
Parallel expand expression can be reduced to serial expand with introduction of new variables. <br />
<br />
<div style="color: #990000;">
<span class="S1"> (expand// <expr> '((<var1> <val1>)...(<varn> <valn>))) = </span></div>
<div style="color: #990000;">
<br /></div>
<div style="color: #990000;">
<span class="S1"> (expand <expr> '((<var1> expand//1) ... (<varn> expand//<n>)</span></div>
<div style="color: #990000;">
<span class="S1"> (expand//1 <val1> ) ... (expand//n <valn>)))</span></div>
<br />
Fexpr expand// can use always the same temporary variables expand//1, ..., expand//n, without need for generating fresh variables each time <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">expand//</span> is called. Other form of <span style="color: black; font-family: Consolas,monospace; font-weight: bold;">expand//</span>,<br />
<br />
<div style="color: #990000; text-align: center;">
<span class="S1"> (expand// <expr> '<var0> ... '<varn>)</span></div>
<br />
can be reduced on form<br />
<br />
<div style="color: #990000;">
<span class="S1"> (expand <expr> </span></div>
<div style="color: #990000;">
<span class="S1"> '((<var0> expand//0) ... (<varn> expand//<n>)</span></div>
<div style="color: #990000;">
<span class="S1"> (expand//0 <value of var0>) ... (expand//<n> <value of var<n>>))).</span></div>
<br />
Using that idea, the implementation is not very technical<br />
<br />
<pre style="background-color: white; background-image: none;"><b><span class="S10">(</span><span class="S3">define</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//</span><span class="S0"> </span><span class="S9">expr</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">letn</span><span class="S10">((</span><span class="S9">a</span><span class="S0"> </span><span class="S10">(</span><span class="S3">args</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">expand//sym</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">n</span><span class="S10">)(</span><span class="S3">sym</span><span class="S0"> </span><span class="S10">(</span><span class="S3">append</span><span class="S0"> </span><span class="S6">"expand//"</span><span class="S0"> </span><span class="S10">(</span><span class="S3">string</span><span class="S0"> </span><span class="S9">n</span><span class="S10">)))))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S9">expandlist</span><span class="S0"> </span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">if</span><span class="S0"> </span><span class="S10">(</span><span class="S3">empty?</span><span class="S0"> </span><span class="S9">a</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">throw-error</span><span class="S0"> </span><span class="S6">"expand//: arguments missing."</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">cond</span><span class="S0"> </span><span class="S10">((</span><span class="S3">symbol?</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">a</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">append</span><span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">i</span><span class="S10">)(</span><span class="S3">list</span><span class="S0"> </span><span class="S9">i</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//sym</span><span class="S0"> </span><span class="S3">$idx</span><span class="S10">)))</span><span class="S0"> </span><span class="S9">a</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">i</span><span class="S10">)(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//sym</span><span class="S0"> </span><span class="S3">$idx</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S3">eval</span><span class="S0"> </span><span class="S9">i</span><span class="S10">)))</span><span class="S0"> </span><span class="S9">a</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">((</span><span class="S3">list?</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">a</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">append</span><span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">i</span><span class="S10">)(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">(</span><span class="S9">i</span><span class="S0"> </span><span class="S2">0</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//sym</span><span class="S0"> </span><span class="S3">$idx</span><span class="S10">)))</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">a</span><span class="S10">))</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">map</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda</span><span class="S10">(</span><span class="S9">i</span><span class="S10">)(</span><span class="S3">list</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//sym</span><span class="S0"> </span><span class="S3">$idx</span><span class="S10">)</span><span class="S0"> </span><span class="S10">(</span><span class="S9">i</span><span class="S0"> </span><span class="S2">1</span><span class="S10">)))</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">a</span><span class="S10">))))))))</span>
<span class="S0"> </span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S6">"expandlist="</span><span class="S0"> </span><span class="S9">expandlist</span><span class="S10">)</span>
<span class="S0"> </span><span class="S10">(</span><span class="S3">expand</span><span class="S0"> </span><span class="S9">expr</span><span class="S0"> </span><span class="S9">expandlist</span><span class="S10">)))</span>
<span class="S0"> </span>
<span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S9">x</span><span class="S0"> </span><span class="S10">'</span><span class="S5">y</span><span class="S10">)</span>
<span class="S10">(</span><span class="S3">setf</span><span class="S0"> </span><span class="S9">y</span><span class="S0"> </span><span class="S2">3</span><span class="S10">)</span>
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">(</span><span class="S3">expand</span><span class="S0"> </span><span class="S10">'(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)</span><span class="S0"> </span><span class="S10">'</span><span class="S5">x</span><span class="S0"> </span><span class="S10">'</span><span class="S5">y</span><span class="S10">))</span><span class="S0"> </span><span class="S1">; => (3 3)</span>
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//</span><span class="S0"> </span><span class="S10">'(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)</span><span class="S0"> </span><span class="S10">'</span><span class="S5">x</span><span class="S0"> </span><span class="S10">'</span><span class="S5">y</span><span class="S10">))</span><span class="S0"> </span><span class="S1">; => (y 3)</span>
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">(</span><span class="S3">expand</span><span class="S0"> </span><span class="S10">'(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)</span><span class="S0"> </span><span class="S10">'((</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)(</span><span class="S9">y</span><span class="S0"> </span><span class="S2">3</span><span class="S10">))))</span><span class="S0"> </span><span class="S1">; => (3 3)</span>
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">(</span><span class="S9">expand//</span><span class="S0"> </span><span class="S10">'(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)</span><span class="S0"> </span><span class="S10">'((</span><span class="S9">x</span><span class="S0"> </span><span class="S9">y</span><span class="S10">)(</span><span class="S9">y</span><span class="S0"> </span><span class="S2">3</span><span class="S10">))))</span><span class="S0"> </span><span class="S1">; => (y 3)</span>
<span class="S10">(</span><span class="S3">exit</span><span class="S10">)</span></b></pre>
</td></tr>
</tbody></table>
</center><br />
<br />
--Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-21685450613026604002011-04-23T16:20:00.008+02:002011-08-28T17:15:30.067+02:00"Nothing Will Happen" in Belgrade, April 2011<br />
<br />
<center><br />
<table style="padding: 50px; text-align: left; width: 640px;"><tbody>
<tr><td style="background: white; color: black; font-family: 'Times New Roman',Times,serif; padding: 50px; text-align: justify; text-align: left;">
<h1 style="font-size:161%;background:white;color:#df0000;font-family:'Times New Roman',Times,serif;text-align:center;font-weight:bold;">Nothing Will Happen in Belgrade, April 2011</h1>
<br />
<div style="text-align: justify;">
I returned from another <a href="http://www.nsnd.org" style="background: white; color: #df0000; text-decoration: underline;">"Ništa se neće dogoditi"</a> (Nothing will happen) hacker conference, this time in <b>Belgrade, Serbia</b>. As usually, the program was made on place on the base of existing supply and demand. No attendance fee. Lot of fun and enthusiasm. I didn't prepared presentation but as there was some interest in Lisp, I discussed some of the most popular topics discussed in this blog. </div>
<br />
I forgot my camera, so I borrow few photos made by other participants. <br />
<br />
Thanks to organizers. <br />
<br />
<br />
<center><br />
<a href="http://www.flickr.com/photos/zsteva/5624311482/" title="data by zsteva, on Flickr"><img alt="data" height="375" src="http://farm6.static.flickr.com/5070/5624311482_86427917ae.jpg" width="500" /></a><br />
<br />
Waiting for the start. I'm third from the left.<br />
<br />
<a href="http://www.flickr.com/photos/goran_zec/5630859459/" title="DSC_0986.JPG by Goran Zec, on Flickr"><img alt="DSC_0986.JPG" height="333" src="http://farm6.static.flickr.com/5104/5630859459_8536886421.jpg" width="500" /></a><br />
<br />
One presentation held in "Magacin."<br />
<br />
<a href="http://www.flickr.com/photos/goran_zec/5630799723/" title="DSC_0810.JPG by Goran Zec, on Flickr"><img alt="DSC_0810.JPG" height="333" src="http://farm6.static.flickr.com/5185/5630799723_5f657e2a22.jpg" width="500" /></a><br />
<br />
One presentation held in bar.<br />
<br />
</center><br />
<br />
See also <a href="http://kazimirmajorinc.blogspot.com/2010/08/few-photographies-from-nothing-will.html" style="background: white; color: #df0000; text-decoration: underline;">"Nothing will Happen", Split, August 2010</a></td></tr>
</tbody></table>
<br />
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-37005489628101537862011-04-08T00:11:00.018+02:002011-09-04T22:54:57.117+02:00One Picolisp Snippet.<br />
<br />
<br />
<br />
<center><br />
<table style="background: none repeat scroll 0% 0% white; color: black; font-family: 'Times New Roman',Times,serif; padding: 50px; text-align: justify; width: 640px;"><tbody>
<tr><td><h1 style="background: white; color: #df0000; font-family: 'Times New Roman',Times,serif; font-weight: bold; text-align: center;">
One Picolisp Snippet</h1>
<h1 style="background: none repeat scroll 0% 0% white; color: #df0000; font-family: 'Times New Roman',Times,serif; font-weight: bold; text-align: center;">
</h1>
<h1 style="background: none repeat scroll 0% 0% white; color: #df0000; font-family: 'Times New Roman',Times,serif; font-weight: bold; text-align: center;">
</h1>
I had presentation on <a href="http://picolisp.com/" style="background: white; color: red; text-decoration: underline;">Picolisp</a> in <a href="http://hackerspaces.org/wiki/Hacklab_in_mama" style="background: white; color: red; text-decoration: underline;">Hacklab "<b>Mama</b>"</a> in <b>Zagreb </b>few weeks ago.<br />
<br />
<br />
<center>
<img src="http://hackerspaces.org/images/6/60/Inside_hacklab_in_mama.JPG" width="300px" /></center><br />
<br />
Not that I'm expert in <b>Picolisp</b>, but I think I understand
it well enough for short introduction. <b>Picolisp </b>is somehow
Spartan dialect of <b>Lisp </b>- for example, it doesn't support
floating point numbers, and it is not available on <b>Windows
</b>- except by using <b>VirtualBox</b> or something like that. But
it is dynamically scoped, and it supports some powerful
and interesting features as fexprs, coroutines and
anonymous symbols, integrated <b>Prolog </b>and database. It is
particularly interesting that <b>Picolisp </b>doesn't have
strings - the symbols are used for that purpose. On the
first sight, absence doesn't look like advantage, but it
is, because all usual functions defined on strings now
work directly on symbols, without need for conversion. <br />
<br />
As a bonus, <b>Picolisp </b>might be the fastest <b>Lisp </b>interpreter,
written entirely (in 64 bit version) in assembly language. <br />
<br />
The author of <b>Picolisp </b>is <b><a href="http://software-lab.de/" style="background: white; color: red; text-decoration: underline;">Alexander Burger</a></b>; as <b>Picolisp
</b>is, in spirit, very similar to <b>Newlisp</b>, we can almost speak
about <a href="http://blog.fogus.me/2011/05/03/the-german-school-of-lisp-2/" style="background: white; color: red; text-decoration: underline;">German school of <b>Lisp</b></a>. OK, maybe another similar
<b>Lisp </b>"made in Germany" is needed for that. <br />
<br />
The reactions on <b>Picolisp </b>and presentation were positive; <b>
Zagreb </b>is one of the places where Lispers encourage
each other, no matter of dialect. We had three days of
"<b>Clojure </b>Fest" few months ago (unfortunately collided
with swine flue fest.) <br />
<br />
I don't want to allow you to go home without any code,
so this was the most liked example from presentation.<br />
<br />
<div style="background: black; color: #ffcf00; font-family: Consolas,monospace; font-weight: bold; padding: 10px;">
<span style="color: red;">:</span> (setq my '(list 1 2))<br />
<span style="color: red;">-></span> (list 1 2)<br />
<span style="color: red;">:</span> (intern (name (zap 'list) "popis")) <span style="color: lime;"> # not a string</span><br />
<span style="color: red;">-></span> popis<br />
<span style="color: red;">:</span> (popis 1 2 3) <br />
<span style="color: red;">-></span> (1 2 3)<br />
<span style="color: red;">:</span> my <br />
<span style="color: red;">-></span> (popis 1 2)</div>
</td></tr>
</tbody></table>
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-35736280335251410912011-04-06T09:15:00.008+02:002011-09-05T06:35:13.630+02:00Variable Definitions Supported in Clojure, Common Lisp, ISLisp, newLISP, Picolisp and Scheme.<style type="text/css">
.auto-style1 {
text-align: center;
}
.auto-style2 {
text-align: center;
}
</style><br />
<center><br />
<table style="text-align:left;background-color:white;color:black;font-family:'Times New Roman',Times,serif;text-align:left;padding:50px;" width='640'><tr> <td style="text-align:left;"><center><h1 style="font-family:'Times New Roman',Times,serif;background:white;color:#df0000;font-weight:bold;font-size:161%;">Variable Definitions Supported in Clojure, Common Lisp, ISLisp, newLISP, Picolisp and Scheme<br /><br /></h1>
<table cellpadding="10" border="1" style="text-align:left;background-color:white;color:black;font-family:'Times New Roman',Times,serif;"><tr> <td class="auto-style2"> </td> <td class="auto-style2"> </td> <td class="auto-style1"><strong>variable</strong></td> <td class="auto-style1"><strong>constant<br />
("immutable variable")</strong></td> </tr>
<tr> <td rowspan="2"><strong>global</strong></td> <td><strong>lexical</strong></td> <td>ISLisp (defglobal)<br />
Scheme (define)</td> <td> </td> </tr>
<tr> <td><strong>dynamic</strong></td> <td>Clojure (def)<br />
CL (defvar, defparameter)<br />
ISLisp (defdynamic)<br />
Picolisp (de)<br />
Newlisp (define)</td> <td>CL (defconstant)<br />
ISLisp (defconstant)<br />
Newlisp (define + constant)</td> </tr>
<tr> <td rowspan="2"><strong>local</strong></td> <td><strong>lexical</strong></td> <td>CL (let, let*)<br />
ISLisp (let, let*)<br />
Scheme (let, let*, letrec, letrec*)</td> <td>Clojure (let, let*)</td> </tr>
<tr> <td><strong>dynamic</strong></td> <td>Clojure (def + binding)<br />
CL (let + declare special, def... + let)<br />
ISLisp (dynamic-let)<br />
Newlisp (let, letn)<br />
Picolisp (let)</td> <td> </td> </tr>
</table></center></td> </tr>
<tr><td><br />
If I forgot something or made mistake, please, let me know.<br />
</table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-35821134899772334782011-04-04T22:40:00.010+02:002012-02-20T19:33:23.674+01:00Symmetric Support for Lexical and Dynamic Scope (Binding) in ISLisp.<center><br />
<table width='640' align="center"><tr><td align="left" style="background:white;color:black;font-family:'Times New Roman',Times,serif;padding:50px;text-align:justify;">
<div style="text-align:center;font-size:161%;color:#cf0000;font-weight:bold;">Symmetric Support for Lexical and Dynamic Scope (Binding) in ISLisp.<br /><br /></div>
In ISLisp, all combinations of global/local and lexical/dynamic
operators for definition of variables are supported.
If operator contains word "dynamic", then the binding will be dynamic.
The operator 'dynamic' is needed for reference of such variables.
Hence, ISLisp is only dialect of Lisp that allows all versions of
standard example for explanation of difference between lexical
and dynamic scope.
<ol>
<li>Variable x is defined with lexical/dynamic global binding and
value 1. The function <tt>f=(lambda()x)</tt> is defined on top level. </li>
<br/>
<li>Variable x is defined with lexical/dynamic local binding and
value 2. The function f is called from the scope of that binding.</li>
</ol>
There are four combinations:
<pre style="background:white;font-size:110%;color:rgb(0,0,0);padding:20px;">
global binding of x in
place of function definition
| lexical | dynamic
------------+ ----------+-----------
local binding of lexical | 1 | 1
x in place of ------------+-----------+-----------
function call dynamic | 1 | 2
------------+-----------+-----------
</pre>
Here is the code: <br>
<pre style="background:#ffefef;font-size:110%;color:rgb(0,0,0);padding:20px;font-weight:bold;">
;-----------------
(defglobal x 1)
(defun f()x)
(let((x 2))
(print (f))) ;=>1
;-----------------
(defglobal x 1)
(defun f()x)
(dynamic-let((x 2))
(print (f))) ;=>1
;-----------------
(defdynamic x 1)
(defun f()(dynamic x))
(let((x 2))
(print (f))) ;=>1
;-----------------
(defdynamic x 1)
(defun f()(dynamic x))
(dynamic-let((x 2))
(print (f))) ;=>2
;-----------------
</pre>
ISLisp is simplified and on few places, like this one, improved
Common Lisp. I must recommend the most mature implementation of ISLisp:
<b>Christian Jullien</b>'s <a href="http://christian.jullien.free.fr/" style="background:white;color:red;text-decoration:underline;">Eligis OpenLisp</a>,
commercial compiler which supports more than 90 architectures, from 16-bit MSDOS to
IBM mainframe; there is also an interpreter, free for
personal use, and so well implemented that on <a href="http://kazimirmajorinc.blogspot.com/2008/12/speed-of-newlisp-eval-test-v100.html" style="background:white;color:red;text-decoration:underline;">my EVAL test</a> it is second
only to in assembly language written <a href="http://www.picolisp.com" style="background:white;color:red;text-decoration:underline;">Picolisp</a>, so OpenLisp can be
attractive to those who like both lexical scope and dynamic scope and eval. Support is excellent.
Check it. It definitely deserves more attention.
</td></tr>
</table><br />
<br />
</center><br />
--Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-25141511204317499912011-02-07T23:50:00.006+01:002011-11-24T07:28:16.088+01:00Lambda Calculus Meta-variables Supported in my Newlisp Library.<center><br />
<table style="text-align:left;" width='640' style=""><tr><td style="padding:50px;margin:50px;text-align:justify;background:white;color:black;font-family:'Times New Roman',Times,serif;"><br />
Lambda calculus is very small and still "Turing complete" language. However, because of its simplicity and small size, it is very hard to write real programs - even harder than in assembly language. Most of the materials demonstrating programming in lambda calculus> use meta-variables. For instance, TRUE is defined as <br />
<br />
<center><b style="font-family:Consolas,monospace">'(^ x .(^ y . x)))</b>,</center><br />
and after that, TRUE is used instead of given expression. If such meta-variables are used, lambda-expressions are much shorter and more readable, however, there is no essential difference, since before reduction, all meta-variables are "expanded" into real lambda-expressions. <br />
<br />
I already implemented support for reduction of lambda expressions in my Newlisp library. The code that deals with meta-variables is rather simple. It is just recursive substitution of meta-variable's value for meta-variable itself. <br />
<br />
You can see how it works in my <a href="http://kazimirmajorinc.blogspot.com/2011/02/some-basic-concepts-implemented-and.html" style="background:white;color:#c00000;text-decoration:underline">previous post, now updated</a>. <br />
<br />
<br />
<center>
<img style="background-color:black;" src="http://www.instprog.com//blogposts/metavariables/meta.png" /></center><br /></td></tr>
</table>
<br />
</center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-88307286727054917622011-02-05T21:49:00.009+01:002011-11-24T08:20:53.878+01:00Some Basic Concepts Implemented and Reduced in Lambda-calculus.<center><table style="text-align:left;background:white;padding:50px;margin:50px;"><tr><td style="text-align:left;background:white;font-weight:bold;"><br />
<span style="color:black;"><span style="color:black;"><span style="color:#3f1f00;">;</span> After <a href="http://kazimirmajorinc.blogspot.com/2011/02/lambda-calculus-metavariables-supported.html">support for meta-variables in lambda-calculus is integrated</a></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> <a href="http://kazimirmajorinc.blogspot.com/2011/02/lambda-calculus-metavariables-supported.html">in my Newlisp library</a>, I can easily demonstrate few fundamental </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> concepts: Boolean constants, integers, IF, predecessor, successor, </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> multiplication and recursion are implemented in lambda calculus </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> and how reduction of the expressions really looks like. </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> At the end, factorial function is implemented - this time without </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> full reduction, because even reduction of (FACTORIAL 0) is too </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> large to be published in blog. However, you can try it for yourself. </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> Watch out: it is frequently said this can be done, but it is</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> rarely actually done.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> LOADING LIBRARY</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:black;">[</span><span style="color:#0000cf">print.supressed</span><span style="color:black;">]</span><span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;"> </span><span style="color:black;">[</span><span style="color:#0000cf">println.supressed</span><span style="color:black;">]</span><span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;">(</span><span style="color:#c00">load</span><span style="color:black;"> </span><span style="color:ff7f7f">"http://instprog.com/Instprog.default-library.lsp"</span><span style="color:black;">)</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:black;">[</span><span style="color:#0000cf">print.supressed</span><span style="color:black;">]</span><span style="color:black;"> </span><span style="color:#c00">nil</span><span style="color:black;"> </span><span style="color:black;">[</span><span style="color:#0000cf">println.supressed</span><span style="color:black;">]</span><span style="color:black;"> </span><span style="color:#c00">nil</span><span style="color:black;">)</span><br />
<br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">TRUE</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">y</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">)))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'((</span><span style="color:#0000cf">TRUE</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:black;"><span style="color:#3f1f00;">;</span> <- lambda-expression</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><span style="color:black;"> </span><span style="color:black;"><span style="color:#3f1f00;">;</span> <- max number of expansions</span><br />
<span style="color:black;"> </span><span style="color:black;"><span style="color:#3f1f00;">;</span> and reductions</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:black;"><span style="color:#3f1f00;">;</span> <- true if output is needed </span><br />
<br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF ((TRUE a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> ((TRUE a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> (((^x.(^y.x)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> (((^x.(^y.x)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ beta ]==> ((^y.a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ alpha ]==> ((^x.a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ beta ]==> a</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">FALSE</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">y</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:#0000cf">y</span><span style="color:black;">)))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'((</span><span style="color:#0000cf">FALSE</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF ((FALSE a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> ((FALSE a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> (((^x.(^y.y)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> (((^x.(^y.y)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ beta ]==> ((^y.y) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ alpha ]==> ((^x.x) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ beta ]==> b</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">IF</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">v</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">t</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">v</span><span style="color:black;"> </span><span style="color:#0000cf">t</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;">)))))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(((</span><span style="color:#0000cf">IF</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">c</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (((IF a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (((IF a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((((^v.(^t.(^f.((v t) f)))) a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((((^v.(^t.(^f.((v t) f)))) a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((((^x.(^y.(^z.((x y) z)))) a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ eta ]==> ((((^x.(^y.(x y))) a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ eta ]==> ((((^x.x) a) b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> ((a b) c)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(((</span><span style="color:#0000cf">IF</span><span style="color:black;"> </span><span style="color:#0000cf">TRUE</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:88%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (((IF TRUE) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (((IF TRUE) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((((^v.(^t.(^f.((v t) f))))(^x.(^y.x))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((((^v.(^t.(^f.((v t) f))))(^x.(^y.x))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((((^x.(^y.(^z.((x y) z))))(^u.(^v.u))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ eta ]==> ((((^x.(^y.(x y)))(^u.(^v.u))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((((^x.(^y.(x y)))(^z.(^u.z))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ eta ]==> ((((^x.x)(^z.(^u.z))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> ((((^x.x)(^y.(^z.y))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (((^y.(^z.y)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (((^x.(^y.x)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> ((^y.a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> ((^x.a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> a</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(((</span><span style="color:#0000cf">IF</span><span style="color:black;"> </span><span style="color:#0000cf">FALSE</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:88%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (((IF FALSE) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (((IF FALSE) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((((^v.(^t.(^f.((v t) f))))(^x.(^y.y))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((((^v.(^t.(^f.((v t) f))))(^x.(^y.y))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((((^x.(^y.(^z.((x y) z))))(^u.(^v.v))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ eta ]==> ((((^x.(^y.(x y)))(^u.(^v.v))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((((^x.(^y.(x y)))(^z.(^u.u))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ eta ]==> ((((^x.x)(^z.(^u.u))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> ((((^x.x)(^y.(^z.z))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (((^y.(^z.z)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (((^x.(^y.y)) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> ((^y.y) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> ((^x.x) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> b</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">APPLY</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">v</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">v</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;">))))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'((</span><span style="color:#0000cf">APPLY</span><span style="color:black;"> </span><span style="color:#0000cf">a</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">b</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>----------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF ((APPLY a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> ((APPLY a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> (((^v.(^f.(v f))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> (((^v.(^f.(v f))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> (((^x.(^y.(x y))) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ eta ]==> (((^x.x) a) b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ beta ]==> (a b)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>----------------------------------------------------------------</span><br />
<br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> Y-combinator is tool that could be used for implementation of</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> recursion</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">Y</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">)))</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">))))))</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">Y</span><span style="color:black;"> </span><span style="color:#0000cf">g</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">12</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><span style="color:black;"> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:88%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (Y g)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (Y g)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^f.((^x.(f (x x)))(^x.(f (x x))))) g)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^f.((^x.(f (x x)))(^x.(f (x x))))) g)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.((^y.(x (y y)))(^z.(x (z z))))) g)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> ((^y.(g (y y)))(^z.(g (z z))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((^x.(g (x x)))(^y.(g (y y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (g ((^y.(g (y y)))(^y.(g (y y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (g ((^x.(g (x x)))(^y.(g (y y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (g (g ((^y.(g (y y)))(^y.(g (y y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (g (g ((^x.(g (x x)))(^y.(g (y y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> (g (g (g ((^y.(g (y y)))(^y.(g (y y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> (g (g (g ((^x.(g (x x)))(^y.(g (y y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> (g (g (g (g ((^y.(g (y y)))(^y.(g (y y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 12. ==[ alpha ]==> (g (g (g (g ((^x.(g (x x)))(^y.(g (y y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> UNREDUCED: MAX NUMBER OF REDUCTIONS REACHED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> Take a look on the way "reduced" lambda-expression looks like; </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> (Y g) is reduced to (g (Y g))! If we use some more complicated</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> formula instead of g, and normal order of reduction, then</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> g will be evaluated first.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">)))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (^f.(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (^f.(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> (^f.(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> (^x.(^y.y))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">))))))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:94%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (SUCCESSOR ZERO)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (SUCCESSOR ZERO)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.(^y.(^z.(y ((x y) z)))))(^u.(^v.v)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> (^y.(^z.(y (((^u.(^v.v)) y) z))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> (^x.(^y.(x (((^z.(^u.u)) x) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (^x.(^y.(x ((^u.u) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (^x.(^y.(x ((^z.z) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (^x.(^y.(x y)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ eta ]==> (^x.x)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">ONE</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:#0000cf">x</span><span style="color:black;">))</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">))</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:67%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (SUCCESSOR (SUCCESSOR ZERO))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (SUCCESSOR (SUCCESSOR ZERO))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.(^y.(^z.(y ((x y) z)))))((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> (^y.(^z.(y ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) y) z))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> (^x.(^y.(x ((((^z.(^u.(^v.(u ((z u) v)))))(^w.(^p.p))) x) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (^x.(^y.(x (((^u.(^v.(u (((^w.(^p.p)) u) v)))) x) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (^x.(^y.(x (((^z.(^u.(z (((^v.(^w.w)) z) u)))) x) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (^x.(^y.(x ((^u.(x (((^v.(^w.w)) x) u))) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (^x.(^y.(x ((^z.(x (((^u.(^v.v)) x) z))) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> (^x.(^y.(x (x (((^u.(^v.v)) x) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> (^x.(^y.(x (x (((^z.(^u.u)) x) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> (^x.(^y.(x (x ((^u.u) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 12. ==[ alpha ]==> (^x.(^y.(x (x ((^z.z) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 13. ==[ beta ]==> (^x.(^y.(x (x y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO?</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">TRUE</span><span style="color:black;"> </span><span style="color:#0000cf">FALSE</span><span style="color:black;">))</span><span style="color:black;"> </span><span style="color:#0000cf">TRUE</span><span style="color:black;">)))</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">ZERO?</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:74%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (ZERO? ZERO)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (ZERO? ZERO)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^n.((n (TRUE FALSE)) TRUE))(^f.(^x.x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ expanded ]==> ((^n.((n ((^x.(^y.x))(^x.(^y.y))))(^x.(^y.x))))(^f.(^x.x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^n.((n ((^x.(^y.x))(^x.(^y.y))))(^x.(^y.x))))(^f.(^x.x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.((x ((^y.(^z.y))(^u.(^v.v))))(^w.(^p.w))))(^q.(^r.r)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> (((^q.(^r.r))((^y.(^z.y))(^u.(^v.v))))(^w.(^p.w)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> (((^x.(^y.y))((^z.(^u.z))(^v.(^w.w))))(^p.(^q.p)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> ((^y.y)(^p.(^q.p)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> ((^x.x)(^y.(^z.y)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (^y.(^z.y))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (^x.(^y.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">ZERO?</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">))</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:57%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (ZERO? (SUCCESSOR ZERO))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (ZERO? (SUCCESSOR ZERO))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^n.((n (TRUE FALSE)) TRUE))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ expanded ]==> ((^n.((n ((^x.(^y.x))(^x.(^y.y))))(^x.(^y.x))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^n.((n ((^x.(^y.x))(^x.(^y.y))))(^x.(^y.x))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.((x ((^y.(^z.y))(^u.(^v.v))))(^w.(^p.w))))((^q.(^r.(^x1.(r ((q r) x1)))))(^y1.(^z1.z1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> ((((^q.(^r.(^x1.(r ((q r) x1)))))(^y1.(^z1.z1)))((^y.(^z.y))(^u.(^v.v))))(^w.(^p.w)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((((^x.(^y.(^z.(y ((x y) z)))))(^u.(^v.v)))((^w.(^p.w))(^q.(^r.r))))(^x1.(^y1.x1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (((^y.(^z.(y (((^u.(^v.v)) y) z))))((^w.(^p.w))(^q.(^r.r))))(^x1.(^y1.x1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (((^x.(^y.(x (((^z.(^u.u)) x) y))))((^v.(^w.v))(^p.(^q.q))))(^r.(^x1.r)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> ((^y.(((^v.(^w.v))(^p.(^q.q)))(((^z.(^u.u))((^v.(^w.v))(^p.(^q.q)))) y)))(^r.(^x1.r)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> ((^x.(((^y.(^z.y))(^u.(^v.v)))(((^w.(^p.p))((^q.(^r.q))(^x1.(^y1.y1)))) x)))(^z1.(^u1.z1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> (((^y.(^z.y))(^u.(^v.v)))(((^w.(^p.p))((^q.(^r.q))(^x1.(^y1.y1))))(^z1.(^u1.z1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> (((^x.(^y.x))(^z.(^u.u)))(((^v.(^w.w))((^p.(^q.p))(^r.(^x1.x1))))(^y1.(^z1.y1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> ((^y.(^z.(^u.u)))(((^v.(^w.w))((^p.(^q.p))(^r.(^x1.x1))))(^y1.(^z1.y1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 12. ==[ alpha ]==> ((^x.(^y.(^z.z)))(((^u.(^v.v))((^w.(^p.w))(^q.(^r.r))))(^x1.(^y1.x1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 13. ==[ beta ]==> (^y.(^z.z))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 14. ==[ alpha ]==> (^x.(^y.y))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">MULTIPLY</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">m</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">m</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;">))))))</span><br />
<span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'((</span><span style="color:#0000cf">MULTIPLY</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)))</span><span style="color:black;"> </span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)))</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:24%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF ((MULTIPLY (SUCCESSOR (SUCCESSOR ZERO)))(SUCCESSOR (SUCCESSOR ZERO)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> ((MULTIPLY (SUCCESSOR (SUCCESSOR ZERO)))(SUCCESSOR (SUCCESSOR ZERO)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> (((^m.(^n.(^f.(m (n f)))))((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))))((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> (((^m.(^n.(^f.(m (n f)))))((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))))((^n.(^f.(^x.(f ((n f) x)))))((^n.(^f.(^x.(f ((n f) x)))))(^f.(^x.x)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> (((^x.(^y.(^z.(x (y z)))))((^u.(^v.(^w.(v ((u v) w)))))((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> ((^y.(^z.(((^u.(^v.(^w.(v ((u v) w)))))((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1))))(y z))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((^x.(^y.(((^z.(^u.(^v.(u ((z u) v)))))((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1))))(x y))))((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (^y.(((^z.(^u.(^v.(u ((z u) v)))))((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1))))(((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))) y)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (^x.(((^y.(^z.(^u.(z ((y z) u)))))((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> (^x.((^z.(^u.(z ((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))) z) u))))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> (^x.((^y.(^z.(y ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) y) z))))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> (^x.(^z.((((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q)))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)) z))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> (^x.(^y.((((^z.(^u.(^v.(u ((z u) v)))))((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1)))) x)((((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))(((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))((^x2.(^y2.(^z2.(y2 ((x2 y2) z2)))))(^u2.(^v2.v2)))) x)) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> (^x.(^y.(((^u.(^v.(u ((((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1))) u) v)))) x)((((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))(((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))((^x2.(^y2.(^z2.(y2 ((x2 y2) z2)))))(^u2.(^v2.v2)))) x)) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 12. ==[ alpha ]==> (^x.(^y.(((^z.(^u.(z ((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))) z) u)))) x)((((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))(((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))((^r1.(^x2.(^y2.(x2 ((r1 x2) y2)))))(^z2.(^u2.u2)))) x)) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 13. ==[ beta ]==> (^x.(^y.((^u.(x ((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))) x) u)))((((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))(((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))((^r1.(^x2.(^y2.(x2 ((r1 x2) y2)))))(^z2.(^u2.u2)))) x)) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 14. ==[ alpha ]==> (^x.(^y.((^z.(x ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) x) z)))((((^r.(^x1.(^y1.(x1 ((r x1) y1)))))(^z1.(^u1.u1)))(((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))((^q1.(^r1.(^x2.(r1 ((q1 r1) x2)))))(^y2.(^z2.z2)))) x)) y))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 15. ==[ beta ]==> (^x.(^y.(x ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) x)((((^r.(^x1.(^y1.(x1 ((r x1) y1)))))(^z1.(^u1.u1)))(((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))((^q1.(^r1.(^x2.(r1 ((q1 r1) x2)))))(^y2.(^z2.z2)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 16. ==[ alpha ]==> (^x.(^y.(x ((((^z.(^u.(^v.(u ((z u) v)))))(^w.(^p.p))) x)((((^q.(^r.(^x1.(r ((q r) x1)))))(^y1.(^z1.z1)))(((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))(^x2.(^y2.y2)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 17. ==[ beta ]==> (^x.(^y.(x (((^u.(^v.(u (((^w.(^p.p)) u) v)))) x)((((^q.(^r.(^x1.(r ((q r) x1)))))(^y1.(^z1.z1)))(((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))(^x2.(^y2.y2)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 18. ==[ alpha ]==> (^x.(^y.(x (((^z.(^u.(z (((^v.(^w.w)) z) u)))) x)((((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1)))(((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 19. ==[ beta ]==> (^x.(^y.(x ((^u.(x (((^v.(^w.w)) x) u)))((((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1)))(((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 20. ==[ alpha ]==> (^x.(^y.(x ((^z.(x (((^u.(^v.v)) x) z)))((((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1)))(((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 21. ==[ beta ]==> (^x.(^y.(x (x (((^u.(^v.v)) x)((((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1)))(((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 22. ==[ alpha ]==> (^x.(^y.(x (x (((^z.(^u.u)) x)((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r)))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 23. ==[ beta ]==> (^x.(^y.(x (x ((^u.u)((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r)))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 24. ==[ alpha ]==> (^x.(^y.(x (x ((^z.z)((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q)))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 25. ==[ beta ]==> (^x.(^y.(x (x ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q)))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 26. ==[ alpha ]==> (^x.(^y.(x (x ((((^z.(^u.(^v.(u ((z u) v)))))(^w.(^p.p)))(((^q.(^r.(^x1.(r ((q r) x1)))))((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 27. ==[ beta ]==> (^x.(^y.(x (x (((^u.(^v.(u (((^w.(^p.p)) u) v))))(((^q.(^r.(^x1.(r ((q r) x1)))))((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 28. ==[ alpha ]==> (^x.(^y.(x (x (((^z.(^u.(z (((^v.(^w.w)) z) u))))(((^p.(^q.(^r.(q ((p q) r)))))((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))) x)) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 29. ==[ beta ]==> (^x.(^y.(x (x ((^u.((((^p.(^q.(^r.(q ((p q) r)))))((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))) x)(((^v.(^w.w))(((^p.(^q.(^r.(q ((p q) r)))))((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))) x)) u))) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 30. ==[ alpha ]==> (^x.(^y.(x (x ((^z.((((^u.(^v.(^w.(v ((u v) w)))))((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1)))) x)(((^z1.(^u1.u1))(((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))((^q1.(^r1.(^x2.(r1 ((q1 r1) x2)))))(^y2.(^z2.z2)))) x)) z))) y)))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 31. ==[ beta ]==> (^x.(^y.(x (x ((((^u.(^v.(^w.(v ((u v) w)))))((^p.(^q.(^r.(q ((p q) r)))))(^x1.(^y1.y1)))) x)(((^z1.(^u1.u1))(((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))((^q1.(^r1.(^x2.(r1 ((q1 r1) x2)))))(^y2.(^z2.z2)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 32. ==[ alpha ]==> (^x.(^y.(x (x ((((^z.(^u.(^v.(u ((z u) v)))))((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1)))) x)(((^y1.(^z1.z1))(((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))(^x2.(^y2.y2)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 33. ==[ beta ]==> (^x.(^y.(x (x (((^u.(^v.(u ((((^w.(^p.(^q.(p ((w p) q)))))(^r.(^x1.x1))) u) v)))) x)(((^y1.(^z1.z1))(((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))((^p1.(^q1.(^r1.(q1 ((p1 q1) r1)))))(^x2.(^y2.y2)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 34. ==[ alpha ]==> (^x.(^y.(x (x (((^z.(^u.(z ((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))) z) u)))) x)(((^x1.(^y1.y1))(((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 35. ==[ beta ]==> (^x.(^y.(x (x ((^u.(x ((((^v.(^w.(^p.(w ((v w) p)))))(^q.(^r.r))) x) u)))(((^x1.(^y1.y1))(((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))((^w1.(^p1.(^q1.(p1 ((w1 p1) q1)))))(^r1.(^x2.x2)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 36. ==[ alpha ]==> (^x.(^y.(x (x ((^z.(x ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) x) z)))(((^r.(^x1.x1))(((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))) x)) y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 37. ==[ beta ]==> (^x.(^y.(x (x (x ((((^u.(^v.(^w.(v ((u v) w)))))(^p.(^q.q))) x)(((^r.(^x1.x1))(((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))((^v1.(^w1.(^p1.(w1 ((v1 w1) p1)))))(^q1.(^r1.r1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 38. ==[ alpha ]==> (^x.(^y.(x (x (x ((((^z.(^u.(^v.(u ((z u) v)))))(^w.(^p.p))) x)(((^q.(^r.r))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 39. ==[ beta ]==> (^x.(^y.(x (x (x (((^u.(^v.(u (((^w.(^p.p)) u) v)))) x)(((^q.(^r.r))(((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))((^u1.(^v1.(^w1.(v1 ((u1 v1) w1)))))(^p1.(^q1.q1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 40. ==[ alpha ]==> (^x.(^y.(x (x (x (((^z.(^u.(z (((^v.(^w.w)) z) u)))) x)(((^p.(^q.q))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 41. ==[ beta ]==> (^x.(^y.(x (x (x ((^u.(x (((^v.(^w.w)) x) u)))(((^p.(^q.q))(((^r.(^x1.(^y1.(x1 ((r x1) y1)))))((^z1.(^u1.(^v1.(u1 ((z1 u1) v1)))))(^w1.(^p1.p1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 42. ==[ alpha ]==> (^x.(^y.(x (x (x ((^z.(x (((^u.(^v.v)) x) z)))(((^w.(^p.p))(((^q.(^r.(^x1.(r ((q r) x1)))))((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 43. ==[ beta ]==> (^x.(^y.(x (x (x (x (((^u.(^v.v)) x)(((^w.(^p.p))(((^q.(^r.(^x1.(r ((q r) x1)))))((^y1.(^z1.(^u1.(z1 ((y1 z1) u1)))))(^v1.(^w1.w1)))) x)) y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 44. ==[ alpha ]==> (^x.(^y.(x (x (x (x (((^z.(^u.u)) x)(((^v.(^w.w))(((^p.(^q.(^r.(q ((p q) r)))))((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))) x)) y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 45. ==[ beta ]==> (^x.(^y.(x (x (x (x ((^u.u)(((^v.(^w.w))(((^p.(^q.(^r.(q ((p q) r)))))((^x1.(^y1.(^z1.(y1 ((x1 y1) z1)))))(^u1.(^v1.v1)))) x)) y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 46. ==[ alpha ]==> (^x.(^y.(x (x (x (x ((^z.z)(((^u.(^v.v))(((^w.(^p.(^q.(p ((w p) q)))))((^r.(^x1.(^y1.(x1 ((r x1) y1)))))(^z1.(^u1.u1)))) x)) y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 47. ==[ beta ]==> (^x.(^y.(x (x (x (x (((^u.(^v.v))(((^w.(^p.(^q.(p ((w p) q)))))((^r.(^x1.(^y1.(x1 ((r x1) y1)))))(^z1.(^u1.u1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 48. ==[ alpha ]==> (^x.(^y.(x (x (x (x (((^z.(^u.u))(((^v.(^w.(^p.(w ((v w) p)))))((^q.(^r.(^x1.(r ((q r) x1)))))(^y1.(^z1.z1)))) x)) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 49. ==[ beta ]==> (^x.(^y.(x (x (x (x ((^u.u) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 50. ==[ alpha ]==> (^x.(^y.(x (x (x (x ((^z.z) y)))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 51. ==[ beta ]==> (^x.(^y.(x (x (x (x y))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">PREDECESSOR</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(((</span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">p</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">z</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">z</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">p</span><span style="color:black;"> </span><span style="color:#0000cf">TRUE</span><span style="color:black;">)))</span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">p</span><span style="color:black;"> </span><span style="color:#0000cf">TRUE</span><span style="color:black;">)))))</span><br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">z</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">z</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO</span><span style="color:black;">)))</span><br />
<span style="color:black;"> </span><span style="color:#0000cf">FALSE</span><span style="color:black;">)))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">PREDECESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ONE</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:33%;"><span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EXPANSION AND REDUCTION OF (PREDECESSOR ONE)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ original ]==> (PREDECESSOR ONE)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ expanded ]==> ((^n.(((n (^p.(^z.((z (SUCCESSOR (p TRUE)))(p TRUE)))))(^z.((z ZERO) ZERO))) FALSE))(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ expanded ]==> ((^n.(((n (^p.(^z.((z ((^n.(^f.(^x.(f ((n f) x)))))(p (^x.(^y.x)))))(p (^x.(^y.x)))))))(^z.((z (^f.(^x.x)))(^f.(^x.x)))))(^x.(^y.y))))(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> META-VARIABLES EXPANDED.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 1. ==[ start ]==> ((^n.(((n (^p.(^z.((z ((^n.(^f.(^x.(f ((n f) x)))))(p (^x.(^y.x)))))(p (^x.(^y.x)))))))(^z.((z (^f.(^x.x)))(^f.(^x.x)))))(^x.(^y.y))))(^x.x))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2. ==[ alpha ]==> ((^x.(((x (^y.(^z.((z ((^u.(^v.(^w.(v ((u v) w)))))(y (^p.(^q.p)))))(y (^r.(^x1.r)))))))(^y1.((y1 (^z1.(^u1.u1)))(^v1.(^w1.w1)))))(^p1.(^q1.q1))))(^r1.r1))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 3. ==[ beta ]==> ((((^r1.r1)(^y.(^z.((z ((^u.(^v.(^w.(v ((u v) w)))))(y (^p.(^q.p)))))(y (^r.(^x1.r)))))))(^y1.((y1 (^z1.(^u1.u1)))(^v1.(^w1.w1)))))(^p1.(^q1.q1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 4. ==[ alpha ]==> ((((^x.x)(^y.(^z.((z ((^u.(^v.(^w.(v ((u v) w)))))(y (^p.(^q.p)))))(y (^r.(^x1.r)))))))(^y1.((y1 (^z1.(^u1.u1)))(^v1.(^w1.w1)))))(^p1.(^q1.q1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 5. ==[ beta ]==> (((^y.(^z.((z ((^u.(^v.(^w.(v ((u v) w)))))(y (^p.(^q.p)))))(y (^r.(^x1.r))))))(^y1.((y1 (^z1.(^u1.u1)))(^v1.(^w1.w1)))))(^p1.(^q1.q1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 6. ==[ alpha ]==> (((^x.(^y.((y ((^z.(^u.(^v.(u ((z u) v)))))(x (^w.(^p.w)))))(x (^q.(^r.q))))))(^x1.((x1 (^y1.(^z1.z1)))(^u1.(^v1.v1)))))(^w1.(^p1.p1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 7. ==[ beta ]==> ((^y.((y ((^z.(^u.(^v.(u ((z u) v)))))((^x1.((x1 (^y1.(^z1.z1)))(^u1.(^v1.v1))))(^w.(^p.w)))))((^x1.((x1 (^y1.(^z1.z1)))(^u1.(^v1.v1))))(^q.(^r.q)))))(^w1.(^p1.p1)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 8. ==[ alpha ]==> ((^x.((x ((^y.(^z.(^u.(z ((y z) u)))))((^v.((v (^w.(^p.p)))(^q.(^r.r))))(^x1.(^y1.x1)))))((^z1.((z1 (^u1.(^v1.v1)))(^w1.(^p1.p1))))(^q1.(^r1.q1)))))(^x2.(^y2.y2)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 9. ==[ beta ]==> (((^x2.(^y2.y2))((^y.(^z.(^u.(z ((y z) u)))))((^v.((v (^w.(^p.p)))(^q.(^r.r))))(^x1.(^y1.x1)))))((^z1.((z1 (^u1.(^v1.v1)))(^w1.(^p1.p1))))(^q1.(^r1.q1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 10. ==[ alpha ]==> (((^x.(^y.y))((^z.(^u.(^v.(u ((z u) v)))))((^w.((w (^p.(^q.q)))(^r.(^x1.x1))))(^y1.(^z1.y1)))))((^u1.((u1 (^v1.(^w1.w1)))(^p1.(^q1.q1))))(^r1.(^x2.r1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 11. ==[ beta ]==> ((^y.y)((^u1.((u1 (^v1.(^w1.w1)))(^p1.(^q1.q1))))(^r1.(^x2.r1))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 12. ==[ alpha ]==> ((^x.x)((^y.((y (^z.(^u.u)))(^v.(^w.w))))(^p.(^q.p))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 13. ==[ beta ]==> ((^y.((y (^z.(^u.u)))(^v.(^w.w))))(^p.(^q.p)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 14. ==[ alpha ]==> ((^x.((x (^y.(^z.z)))(^u.(^v.v))))(^w.(^p.w)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 15. ==[ beta ]==> (((^w.(^p.w))(^y.(^z.z)))(^u.(^v.v)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 16. ==[ alpha ]==> (((^x.(^y.x))(^z.(^u.u)))(^v.(^w.w)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 17. ==[ beta ]==> ((^y.(^z.(^u.u)))(^v.(^w.w)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 18. ==[ alpha ]==> ((^x.(^y.(^z.z)))(^u.(^v.v)))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 19. ==[ beta ]==> (^y.(^z.z))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 20. ==[ alpha ]==> (^x.(^y.y))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">setf</span><span style="color:black;"> </span><span style="color:#0000cf">FACTORIAL</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">Y</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">^</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;"> </span><span style="color:blue;">.</span><span style="color:black;">((((</span><span style="color:#0000cf">IF</span><span style="color:black;"> </span><span style="color:#0000cf">ZERO?</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:#0000cf">ONE</span><span style="color:black;">)</span><br />
<span style="color:black;"> </span><span style="color:black;">((</span><span style="color:#0000cf">MULTIPLY</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;">)</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">f</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">PREDECESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">n</span><span style="color:black;">))))))))</span><br />
<br />
<span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">expand-and-reduce^</span><span style="color:black;"> </span><span style="color:black;">'(</span><span style="color:#0000cf">FACTORIAL</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:black;">(</span><span style="color:#0000cf">SUCCESSOR</span><span style="color:black;"> </span><span style="color:#0000cf">ONE</span><span style="color:black;">)))</span><br />
<span style="color:black;"> </span><span style="color:blue;">5000</span><br />
<span style="color:black;"> </span><span style="color:#c00">true</span><span style="color:black;">)</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<div style="font-size:91%;"><span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> Roughly ten minutes and 100000 of lines later, on my computer</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> </span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> ...</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2379. ==[ beta ]==> (^x.(^y.(x (x (x (x (x (x ((^u.u) y)))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2380. ==[ alpha ]==> (^x.(^y.(x (x (x (x (x (x ((^z.z) y)))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> 2381. ==[ beta ]==> (^x.(^y.(x (x (x (x (x (x y))))))))</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> REDUCED TO NORMAL FORM.</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span></span><br />
</div><span style="color:black;"><span style="color:#3f1f00;">;</span>---------------------------------------------------------------</span><br />
<span style="color:black;"><span style="color:#3f1f00;">;</span> EVERYTHING WORKS!</span><br />
<br />
<span style="color:black;">(</span><span style="color:#c00">exit</span><span style="color:black;">)</span><br />
</span><br />
</td> </tr>
</table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-92064235121442999892011-01-31T19:10:00.005+01:002012-07-29T06:40:04.721+02:00Some differences between lambda-calculus and Lisp (2).<center><br />
<table style="text-align:left;"><tr> <td style="text-align:left;"><br />
<span><span class="S1"><span style="color:#1f0000;">;</span> This is the second part of <a href="http://kazimirmajorinc.blogspot.com/2011/01/some-differences-between-lambda.html" /> previous post </a>. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:150%;color:#ff7f00;">4. Evaluation in Lisp vs. </span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:150%;color:#ff7f00;">reduction to normal form in lambda-calculus</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> As noted in previous post, in Lisp, evaluation of the function</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> application is defined recursively:</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> 1. evaluation of the function arguments is performed</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> 2. resulting values are assigned to the parameters of </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> the function</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> 2. evaluation of the function body is performed</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> In lambda calculus, beta-reductions do not recurse on that way. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> There is no "automatic" beta-reductions of the argument of the </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> application. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> Because of that, in general case, one applies reductions many </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> times to achieve similar effect. How many times? Typically,</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> until further reduction is impossible; in that case, it is</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> said that expression is reduced to normal form. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> There are few differences between evaluation in Lisp and </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> reduction to normal form in lambda-calculus:</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">4.1. Order of reductions in </span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">lambda-calculus is not defined</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> Lambda-calculus is not an algorithm. It is a "formal system". One</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> who performs reductions - human or computer - can pick the order of</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> reductions by any criteria. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">4.2. Lisp evaluation strategy is not the best for</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">lambda-calculus</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> In Lisp, order of evaluations is "from inside"; if application</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> is evaluated, for example,</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> ((lambda(x)(+ x x)) ((lambda(x)(* x x)) 3) 2)</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> then inner left argument, in this case </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> ((lambda(x)(* x x)) 3)</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> is evaluated first. That order is called "applicative order".</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> In lambda-calculus, some expressions cannot be reduced applying</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> that order of reductions. For example, </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> ((^x.a) ((^x.(x x)) (^x.(x x))))</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> would be reduced indefinitely, because reduction of </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> ((^x.(x x)) (^x.(x x)))</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> doesn't terminate. Some other evaluation strategies, for example, </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> "normal order", "from outside", as defined in lambda-Church, terminate:</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">((</span><span class="S9">lambda-Church</span><span class="S0"> </span><span class="S10">(</span><span class="S9">x</span><span class="S10">)</span><span class="S0"> </span><span class="S9">a</span><span class="S10">)</span><span class="S0"> </span><span class="S10">((</span><span class="S9">lambda-Church</span><span class="S10">(</span><span class="S9">x</span><span class="S10">)(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S9">lambda-Church</span><span class="S10">(</span><span class="S9">x</span><span class="S10">)(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)))))</span><br />
<span class="S0"> </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> => a</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">4.3. Reduction to normal form is more </span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> <span style="font-size:125%;color:#ff7f00;">extensive than single evaluation</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> 1. In Lisp, function, like </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> (lambda(x)((lambda(y)y) x)), </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> if evaluated is either evaluated to some "compiled value", </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> i.e. it is not S-expression any more - or evaluates to </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> itself, as in Newlisp. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> In lambda-calculus, reduction is performed inside the function</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> body. For example, </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> (^x.((^y.y) x)) => (^x.x).</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> </span><br />
<span class="S1"><span style="color:#1f0000;">;</span> 2. In Lisp, result of the evaluation of the S-expression is frequently</span><br />
<span class="S1"><span style="color:#1f0000;">;</span> in form that allows further evaluation. </span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> ((lambda(x)(list '+ 1 2 x)) 3) => '(+ 1 2 3)</span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span>But, it is not evaluated automatically.</span><br />
<br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span></span><br />
<span class="S1"><span style="color:#1f0000;">;</span> To be continued ...</span><br />
<span class="S0"></span></span><br />
<br />
</td> </tr>
</table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-74182799898824315572011-01-29T13:51:00.021+01:002011-02-01T13:05:41.546+01:00Some differences between lambda-calculus and Lisp (1).<center><br />
<table style="text-align: left;"><tbody>
<tr> <td style="text-align: left;"><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">0. Introduction</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> At the first sight, <b>Lisp</b> dialects appear like extensions of the </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <b>lambda-calculus</b>. Syntax of the two is especially similar. For </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> instance, </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^ <i>x</i> . <i>x</i>) <i>y</i>)</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> in <b>lambda-calculus</b> is very similar to</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((lambda(x)x) y)</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> in <b>Lisp</b>. However, it turns that there are many important </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> differences between <b>lambda-calculus</b> and <b>Lisp</b>, some of these </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> are obvious, and others are quite subtle. In this post, I'll </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> list and comment few of these I've find to be interesting and</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> important. The post is not tutorial on <b>lambda-calculus</b>, but </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> another view that might be interesting to those who already </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> know <b>lambda-calculus</b>, but maybe also - to some extent - to those</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> who do not know it yet. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">1. The notion of lambda-expression </span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> There is significant difference even in basic terminology. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> For instance, this is definition of lambda-expression in Common </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <b>Lisp</b> Hyperspec:</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> "<i><b>lambda expression</b> n. a list which can be used in place of a </i></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <i>function name in certain contexts to denote a function by</i> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> directly describing its behavior rather than indirectly by </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <i>referring to the name of an established function; its name</i> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <i>derives from the fact that its first element is the symbol</i> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <i>lambda</i>."</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> In <b>lambda-calculus</b>, lambda-expression is the name used for </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> all allowed expressions of <b>lambda-calculus</b>. According to definition,</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> lambda expressions are:</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 1. variables: <i>a</i>, <i>b</i>, <i>c</i>, <i>d</i> ...<i> a</i>1, <i>a</i>2, ...</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 2. functions: (^ <i>v</i> . <i>F</i>), where v is any variable, <i>F</i> any lambda-expr.</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 3. applications: (<i>E</i> <i>F</i>), where <i>E</i> and <i>F</i> are lambda-expressions.</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> This difference, although not essential is very confusing one. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">2. Evaluation vs. reduction</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> In <b>Lisp</b>, expressions are "evaluated." For instance,</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((lambda(x)x) y) => value of y.</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> In <b>lambda-calculus</b>, expressions are "reduced". Reduction </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> doesn't require replacement of the variables with values, so</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^ <i>x</i> . <i>x</i>) <i>y</i>) => <i>y</i></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> and not </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^ <i>x</i> . <i>x</i>) <i>y</i>) => value of <i>y</i>. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> If we remember high school math, some of the exercises were of </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> the form "simplify" or "expand", and didn't required knowledge </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> about value of the variables to be solved.</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (<i>x</i>+1)^2 -1 ==> (<i>x</i>^2+2<i>x</i>+1) -1 =<i> x</i>(<i>x</i>+2)</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> Other group of exercises clearly required evaluation:</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> "Find the area of the rhomboid with sides </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <i>a</i>=4, <i>b</i>=3, and angle of 30° between them." </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">; </span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">3. Recursiveness of evaluation in Lisp</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">vs.</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">non-recursiveness of beta-reduction </span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 150%;">in lambda-calculus</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> There are three reductions in <b>lambda-calculus</b>; only short</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> resume here - formal definition find somewhere else. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 1. <b>Beta-reduction</b>: the application of the function</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^<i>x</i>.<i>x</i>) <i>a</i>) => <i>a,</i> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^<i>x</i>.(<i>x</i> <i>x</i>)) <i>a</i>) => (<i>a</i> <i>a</i>).</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 2. <b>Alpha-reduction</b>: renaming of the bounded variables</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (^<i>x</i>.<i>x</i>) => (^<i>y</i>.<i>y</i>).</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> 3. <b>Eta-reduction</b>: elimination of the redundant function</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (^<i>x</i>.((^<i>y</i>.<i>y</i>)<i>x</i>)) => (^<i>y</i>.<i>y</i>).</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (eta-reduction is not essential; it can be replaced</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> with other two.)</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> Beta-reduction is very similar to function application</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> in <b>Lisp</b>. However, there are significant differences.</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;"></span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> In <b>Lisp</b>, evaluation of the function application, for instance,</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((lambda(x)(x x)) (a b))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> is performed on the following way:</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - argument (here (a b)) is evaluated;</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - result is assigned to the parameter (here x), and </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - body of the function, (here (x x)) is evaluated. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - the result is returned as the result of evaluation of </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> whole expression. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> In <b>lambda-calculus</b>, beta-reduction of the application,</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> for instance,</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((^<i>x</i>.(<i>x</i> <i>x</i>)) (<i>a</i> <i>b</i>))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> is performed on a following way: </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - argument (here (<i>a b</i>)) is substituted for parameter (here <i>x</i>)</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> in the body of the function (here (<i>x x</i>)).</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> - the result of the substitution is result of beta-reduction. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> The result of the two is significantly different. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> Note that beta reduction does significantly less than</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> evaluation. Beta-reduction doesn't apply itself recursively</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> on y and on (<i>x x</i>), while evaluation in <b>Lisp</b> does - it requires</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> evaluation of </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> <span style="color: #ff7f00; font-size: 125%;">3.1. Example: <b>Church</b>'s lambda in Newlisp</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> I'll use previous discussion to define </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> lambda-Church </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> in Newlisp, so expressions using it are evaluated just like</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> lambda-expressions are beta reduced in <b>lambda-calculus</b>. For </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> instance, I want</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((lambda-Church (x) (x x)) (a b))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> to evalute to </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ((a b)(a b)).</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> What should I do? In Newlisp, because it has fexprs, its easy. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> Expression</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (lambda-Church (x) (x x)) </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> should be evaluated to </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (lambda-macro(x)(expand (quote (x x))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> (quote x)))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> and that's all. </span><br />
<br />
<span class="S10">(</span><span class="S3">define-macro</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lambda-Church</span><span class="S0"> </span><span class="S9">head</span><span class="S0"> </span><span class="S9">body</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">let</span><span class="S0"> </span><span class="S10">((</span><span class="S9">var</span><span class="S0"> </span><span class="S10">(</span><span class="S3">first</span><span class="S0"> </span><span class="S9">head</span><span class="S10">)))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">expand</span><span class="S0"> </span><span class="S10">(</span><span class="S3">lambda-macro</span><span class="S10">(</span><span class="S9">var</span><span class="S10">)(</span><span class="S3">expand</span><span class="S0"> </span><span class="S10">(</span><span class="S3">quote</span><span class="S0"> </span><span class="S9">body</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">quote</span><span class="S0"> </span><span class="S9">var</span><span class="S10">)))</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">quote</span><span class="S0"> </span><span class="S9">body</span><span class="S10">)</span><br />
<span class="S0"> </span><span class="S10">(</span><span class="S3">quote</span><span class="S0"> </span><span class="S9">var</span><span class="S10">))))</span><br />
<br />
<span class="S1"><span style="color: #3f3f3f;">;</span> Let's test it.</span><br />
<br />
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">(</span><span class="S9">lambda-Church</span><span class="S0"> </span><span class="S10">(</span><span class="S9">x</span><span class="S10">)(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">x</span><span class="S10">)))</span><br />
<br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ==> (lambda-macro (x) (expand (quote (x x)) (quote x)))</span><br />
<br />
<span class="S10">(</span><span class="S3">println</span><span class="S0"> </span><span class="S10">((</span><span class="S9">lambda-Church</span><span class="S0"> </span><span class="S10">(</span><span class="S9">x</span><span class="S10">)(</span><span class="S9">x</span><span class="S0"> </span><span class="S9">x</span><span class="S10">))</span><span class="S0"> </span><span class="S10">(</span><span class="S9">a</span><span class="S0"> </span><span class="S9">b</span><span class="S10">)))</span><br />
<br />
<span class="S1"><span style="color: #3f3f3f;">;</span> ==> ((a b) (a b))</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> It works. In future, lambda-Church expressions can</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> be freely mixed with other Newlisp expressions. </span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span> To be <a href="http://kazimirmajorinc.blogspot.com/2011/01/some-differences-between-lambda_31.html"> continued </a> ...</span><br />
<span class="S1"><span style="color: #3f3f3f;">;</span></span></td> </tr>
</tbody></table></center><br />
<br />
---Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0tag:blogger.com,1999:blog-5894839.post-52267516619759851492011-01-25T14:28:00.003+01:002011-01-26T06:40:17.494+01:00Find Your Way Through Lisp Labyrinth.<center><br />
<table width='760' style="text-align:left;"><tr><td style="text-align:left;"><br />
The programmer who wants to start using Lisp -- not because of practical reasons, but because he is intrigued with language itself -- is frequently in doubt where to start. I made one proposal he might follow; that proposal reflects my values - other Lisp users might make different proposals. I'd like to hear your comments. <br />
<br />
<img src="http://www.instprog.com//blogposts/find-your-way-through-Lisp-labyrinth/pic.png" /><br />
</table></tr><br />
<br />
</td> </center>
If you like this post, you might be interested in<br><br>
<a href="http://kazimirmajorinc.blogspot.com/2011/01/when-were-best-days-for-lisp.html"> When were the best days for Lisp </a>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com7tag:blogger.com,1999:blog-5894839.post-45679372125401305782011-01-24T10:51:00.001+01:002011-01-24T10:53:10.659+01:00Why they say this is the most important metacircular blog post?<center><table width='50%'><tr><td>What? <b>Why they say this is the most important metacircular blog post?</b> I have not the slightest clue. Let us <a href="http://www.google.com/search?q=Why%20they%20say%20this%20is%20the%20most%20important%20metacircular%20blog%20post?">ask Google!</a></td></tr></table></center>Kazimir Majorinchttp://www.blogger.com/profile/03407339997157446200noreply@blogger.com0