Can someone compare/contrast functions and computation?&nbsp; <br><br>thanks<br><br>daryoush<br><br><div class="gmail_quote">On Thu, Feb 5, 2009 at 1:38 AM, Benjamin L. Russell <span dir="ltr">&lt;<a href="mailto:DekuDekuplex@yahoo.com">DekuDekuplex@yahoo.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">On Wed, 4 Feb 2009 21:43:04 -0800, Max Rabkin &lt;<a href="mailto:max.rabkin@gmail.com">max.rabkin@gmail.com</a>&gt;<br>

wrote:<br>
<div class="Ih2E3d"><br>
&gt;On Wed, Feb 4, 2009 at 9:38 PM, Benjamin L. Russell<br>
&gt;&lt;<a href="mailto:DekuDekuplex@yahoo.com">DekuDekuplex@yahoo.com</a>&gt; wrote:<br>
&gt;&gt; Is it possible to write a self-referential function in Haskell that<br>
&gt;&gt; modifies itself?<br>
&gt;<br>
&gt;Is it possible to write *any* kind of function in Haskell that<br>
&gt;modifies *anything*?<br>
<br>
</div>While trying to research this issue, I came across a relevant archived<br>
thread in Haskell-Cafe, entitled &quot;[Haskell-cafe] haskell and<br>
reflection,&quot; started by Greg Meredith, dated &quot;Tue, 11 Sep 2007<br>
07:09:22 -0700&quot; (see<br>
<a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg29882.html" target="_blank">http://www.mail-archive.com/haskell-cafe@haskell.org/msg29882.html</a>),<br>
which at first had me worried. &nbsp;Specifically, Greg wrote as follows:<br>
<br>
&gt;Am i wrong in my assessment that the vast majority of reflective machinery<br>
&gt;is missing from Haskell? Specifically,<br>
&gt;<br>
&gt; &nbsp; - there is no runtime representation of type available for<br>
&gt; &nbsp; programmatic representation<br>
&gt; &nbsp; - there is no runtime representation of the type-inferencing or<br>
&gt; &nbsp; checking machinery<br>
&gt; &nbsp; - there is no runtime representation of the evaluation machinery<br>
&gt; &nbsp; - there is no runtime representation of the lexical or parsing<br>
&gt; &nbsp; machinery<br>
<br>
However, I was somewhat relieved to find that Haskell apparently does<br>
support, in at least one GHC extension to Haskell, a limited form of<br>
reflection. &nbsp;In the same thread, Reinier Lamers, in his response,<br>
dated &quot;Tue, 11 Sep 2007 13:08:38 -0700&quot; (see<br>
<a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg29898.html" target="_blank">http://www.mail-archive.com/haskell-cafe@haskell.org/msg29898.html</a>),<br>
wrote as follows:<br>
<br>
&gt;Op 11-sep-2007, om 18:43 heeft Greg Meredith het volgende geschreven:<br>
&gt;<br>
&gt;[...]<br>
&gt;<br>
&gt;Template Haskell [1] is a system that lets you write programs that get<br>
&gt;executed at *compile time*, and that produce parts of the Haskell program<br>
&gt;to be compiled by manipulating a representation of the program as structured<br>
&gt;data. It&#39;s a form of reflection restricted to compile time, if you&#39;d ask me.<br>
&gt;<br>
&gt;[...]<br>
&gt;<br>
&gt;[1] <a href="http://www.haskell.org/haskellwiki/Template_Haskell" target="_blank">http://www.haskell.org/haskellwiki/Template_Haskell</a><br>
<br>
According to the site referenced by the above-mentioned link,<br>
<br>
&gt;Template Haskell is an extension to Haskell 98 that allows you to do type-safe<br>
&gt;compile-time meta-programming, with Haskell both as the manipulating language<br>
&gt;and the language being manipulated.<br>
<br>
This site is even referenced on the site for &quot;The Meta-Programming<br>
Project&quot; (see<br>
<a href="http://www.infosun.fim.uni-passau.de/cl/metaprog/index.php3" target="_blank">http://www.infosun.fim.uni-passau.de/cl/metaprog/index.php3</a>), as<br>
follows:<br>
<br>
&gt;Languages which we are using for meta-programming<br>
&gt;<br>
&gt; &nbsp; &nbsp;* Template Haskell, permits analysis of object programs<br>
<br>
Additionally, Don Stewart, in an earlier post in the same thread,<br>
dated &quot;Thu, 13 Sep 2007 11:36:11 -0700&quot; (see<br>
<a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg30009.html" target="_blank">http://www.mail-archive.com/haskell-cafe@haskell.org/msg30009.html</a>),<br>
wrote as follows:<br>
<br>
&gt;lgreg.meredith:<br>
&gt;&gt; &nbsp; &nbsp;Haskellians,<br>
&gt;&gt;<br>
&gt;&gt; &nbsp; &nbsp;Am i wrong in my assessment that the vast majority of reflective machinery<br>
&gt;&gt; &nbsp; &nbsp;is missing from Haskell? Specifically,<br>
&gt;&gt;<br>
&gt;&gt; &nbsp; &nbsp; &nbsp;* there is no runtime representation of type available for programmatic<br>
&gt;&gt; &nbsp; &nbsp; &nbsp; &nbsp;representation<br>
&gt;<br>
&gt;&gt; &nbsp; &nbsp; &nbsp;* there is no runtime representation of the type-inferencing or checking<br>
&gt;&gt; &nbsp; &nbsp; &nbsp; &nbsp;machinery<br>
&gt;<br>
&gt;&gt; &nbsp; &nbsp; &nbsp;* there is no runtime representation of the evaluation machinery<br>
&gt;<br>
&gt;&gt; &nbsp; &nbsp; &nbsp;* there is no runtime representation of the lexical or parsing machinery<br>
&gt;<br>
&gt;So there is library support for all of this, in various forms:<br>
&gt;<br>
&gt; &nbsp; &nbsp;* lexer, parser, type checker, evaluator:<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ghc-api<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;hs-plugins<br>
&gt;<br>
&gt; &nbsp; &nbsp;* lexer, parser, pretty printer<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;many parser libs (Language.Haskell, Template Haskell)<br>
&gt;<br>
&gt; &nbsp; &nbsp;* runtime type representation<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Data.Typeable<br>
&gt;<br>
&gt; &nbsp; &nbsp;* reflecting code to data:<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Data.Generics<br>
<br>
As a sidenote, I discovered an interesting post and associated paper<br>
by Lauri Alanko, who in a post in the same thread, dated &quot;Tue, 11 Sep<br>
2007 10:12:09 -0700&quot; (see<br>
<a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg29895.html" target="_blank">http://www.mail-archive.com/haskell-cafe@haskell.org/msg29895.html</a>),<br>
responded that while both structural and procedural reflection are<br>
possible in Haskell, because of static typing, type safety is<br>
nevertheless an issue:<br>
<br>
&gt;On Tue, Sep 11, 2007 at 07:33:54AM -0700, Greg Meredith wrote:<br>
&gt;&gt; Our analysis suggested the following breakdown<br>
&gt;&gt;<br>
&gt;&gt; &nbsp; &nbsp;- Structural reflection -- all data used in the evaluation of programs<br>
&gt;&gt; &nbsp; &nbsp;has a programmatic representation<br>
&gt;&gt; &nbsp; &nbsp;- Procedural reflection -- all execution machinery used in the<br>
&gt;&gt; &nbsp; &nbsp;evaluation of programs has a programmatic representation<br>
&gt;&gt;<br>
&gt;&gt;[...]<br>
&gt;<br>
&gt;As for Haskell, there are various tools for both (at least<br>
&gt;Data.Typeable and hs-plugins), but neither are truly type-safe: it is<br>
&gt;possible to write code that uses these libraries and type-checks, yet<br>
&gt;crashes. Static typing makes reflection very difficult to support<br>
&gt;safely.<br>
<br>
&gt;You might be interested in my MS thesis, where I explored these issues<br>
&gt;in some more length:<br>
&gt;<a href="http://www.cs.helsinki.fi/u/lealanko/alanko04types.pdf" target="_blank">http://www.cs.helsinki.fi/u/lealanko/alanko04types.pdf</a><br>
<br>
This thesis is entitled &quot;Types and Reflection&quot; (see the<br>
above-mentioned URL), and summarizes the problem as follows (see p.<br>
1):<br>
<br>
&gt;This thesis is about reflection in typed programming languages. The central<br>
&gt;idea of this work, the thesis proper, can be summarized in three points:<br>
&gt;. Typed reflection is a good thing.<br>
&gt;. It has not yet been done properly.<br>
&gt;. It is nevertheless possible.<br>
<br>
The basic problem with reflection in a statically typed language seems<br>
to be that &quot;reflection wreaks havoc to the basic assumptions that type<br>
systems are based on&quot; (see p. 11). &nbsp;Specifically, he explains as<br>
follows (see p. 38):<br>
<br>
&gt;[A] type system verifies or infers universal properties about all<br>
&gt;possible executions of a program by making a context-sensitive syntactic analysis of the<br>
&gt;program's structure. Usually this is possible because the computational rules for executing<br>
&gt;the program are simple, tractable and most importantly syntax-directed: the evaluation<br>
&gt;of each expression proceeds in a predictable fashion that is determined mostly by its syntactic<br>
&gt;form and only to a limited extent by run-time state. For each expression there are<br>
&gt;certain invariants that always hold for its evaluation, and these invariants can be expressed<br>
&gt;in the expression's type.<br>
&gt;<br>
&gt;In practice this means that we can prove the soundness of a type system with structural<br>
&gt;induction over the terms, using the dynamic semantics of the language to show that the<br>
&gt;evaluation of each expression will yield a well-typed result.<br>
&gt;<br>
&gt;In the presence of reflective operations this mode of reasoning no longer works. The<br>
&gt;reason is that the effects of all primitive expressions on computational structures are no<br>
&gt;longer simple and tractable: an absorption operation turns an arbitrary run-time value<br>
&gt;into a computational structure, and there are therefore no simple invariants about the<br>
&gt;operation's behavior.<br>
&gt;<br>
&gt;This is of course an inherent property of reflection. Its idea, after all, is to allow the<br>
&gt;program more freedom at run-time instead of completely predefining its behavior when<br>
&gt;the program is written. Yet it is still a rarely used feature and it seems unreasonable that it<br>
&gt;should make static typing completely unattainable. Thankfully, this proves not to be the<br>
&gt;case.<br>
<br>
In Greg Meredith&#39;s solution, he writes as follows (see p. 42):<br>
<br>
&gt;[T]here is a tradeoff to be made between static safety and dynamic flexibility.<br>
&gt;It turns out that it is possible to do quite sophisticated run-time code manipulation while<br>
&gt;still retaining fully static safety guarantees both of the original code and the generated<br>
&gt;code.<br>
<br>
In Section 8.3: &quot;Dynamics in Haskell,&quot; Meredith elucidates as follows<br>
(see p. 62):<br>
<br>
&gt;The language Haskell [H98] has a powerful type system, but the standard version of the<br>
&gt;language has no support for run-time type operations. However, there is a dynamics<br>
&gt;library that has for a long time been included in many implementations [LPJ03, Section<br>
&gt;8]. The library provides a datatype Dynamic and some machinery for injecting values<br>
&gt;of different types into it and for extracting them out from it. Unfortunately, the user<br>
&gt;of the library is required to obey certain programming conventions, and if they are not<br>
&gt;followed, it is very easy to write code that breaks type safety. Moreover, the library<br>
&gt;provides only limited support for dynamics. For instance, it is not possible to inject<br>
&gt;polymorphic functions into a Dynamic.<br>
&gt;<br>
&gt;More recently, Cheney and Hinze [CH02a] and Baars and Swierstra [BS02] have developed<br>
&gt;more flexible and type-safe frameworks for representing type information at runtime<br>
&gt;in Haskell. In fact, dynamic values are only one of the possible applications of the<br>
&gt;frameworks.<br>
<br>
Cheney and Hinze&#39;s system is then described in more detail. &nbsp;Meredith<br>
then concludes as follows (see p. 63):<br>
<br>
&gt;The above system is quite remarkable. The type Rep [tau] &nbsp; bridges the gap between static and<br>
&gt;dynamic type information while remaining completely type-safe even internally. Indeed,<br>
&gt;the type representations are very much like reified types. They can be synthesized and<br>
&gt;analyzed, and the isomorphisms allow a kind of absorption: conversion from run-time to<br>
&gt;compile-time type information.<br>
<br>
Some problems relating to the need for programmer cooperation, the<br>
treatment of new named datatypes, and lack of full reflexivity are<br>
then described. &nbsp;Nevertheless, Meredith summarizes as follows (see p.<br>
64):<br>
<br>
&gt;Nevertheless, these &quot;lightweight dynamics&quot; are surprisingly powerful, considering that<br>
&gt;they can be implemented in a statically typed language without extending the type system.<br>
&gt;For example, Baars and Swierstra demonstrate how to write a type-safe eval function for a<br>
&gt;simple language so that all type checking is done before the code is evaluated. Although<br>
&gt;this is not full reflection due to the simplicity of the object language, the result is still<br>
&gt;encouraging. For one thing, at least now a type can be pretty-printed even without the<br>
&gt;presence of a value of that type.<br>
<br>
Apparently, there is hope for reflection in Haskell with such<br>
libraries.<br>
<br>
What would be especially interesting would be a specific example of a<br>
type-safe Haskell program that could modify itself at runtime. &nbsp;If<br>
anyone has any examples to cite, I would be very interested in reading<br>
about them in this thread.<br>
<div class="Ih2E3d"><br>
-- Benjamin L. Russell<br>
--<br>
Benjamin L. Russell &nbsp;/ &nbsp; DekuDekuplex at Yahoo dot com<br>
<a href="http://dekudekuplex.wordpress.com/%0ATranslator/Interpreter" target="_blank">http://dekudekuplex.wordpress.com/<br>
Translator/Interpreter</a> / Mobile: &nbsp;+011 81 80-3603-6725<br>
&quot;Furuike ya, kawazu tobikomu mizu no oto.&quot;<br>
-- Matsuo Basho^<br>
<br>
_______________________________________________<br>
</div><div><div></div><div class="Wj3C7c">Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br><br>