klisp

an open source interpreter for the Kernel Programming Language.
git clone http://git.hanabi.in/repos/klisp.git
Log | Files | Refs | README

Environments.html (17742B)


      1 <html lang="en">
      2 <head>
      3 <title>Environments - klisp Reference Manual</title>
      4 <meta http-equiv="Content-Type" content="text/html">
      5 <meta name="description" content="klisp Reference Manual">
      6 <meta name="generator" content="makeinfo 4.13">
      7 <link title="Top" rel="start" href="index.html#Top">
      8 <link rel="prev" href="Pairs-and-lists.html#Pairs-and-lists" title="Pairs and lists">
      9 <link rel="next" href="Combiners.html#Combiners" title="Combiners">
     10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
     11 <meta http-equiv="Content-Style-Type" content="text/css">
     12 <style type="text/css"><!--
     13   pre.display { font-family:inherit }
     14   pre.format  { font-family:inherit }
     15   pre.smalldisplay { font-family:inherit; font-size:smaller }
     16   pre.smallformat  { font-family:inherit; font-size:smaller }
     17   pre.smallexample { font-size:smaller }
     18   pre.smalllisp    { font-size:smaller }
     19   span.sc    { font-variant:small-caps }
     20   span.roman { font-family:serif; font-weight:normal; } 
     21   span.sansserif { font-family:sans-serif; font-weight:normal; } 
     22 --></style>
     23 <link rel="stylesheet" type="text/css" href="css/style.css">
     24 </head>
     25 <body>
     26 <div class="node">
     27 <a name="Environments"></a>
     28 <p>
     29 Next:&nbsp;<a rel="next" accesskey="n" href="Combiners.html#Combiners">Combiners</a>,
     30 Previous:&nbsp;<a rel="previous" accesskey="p" href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a>,
     31 Up:&nbsp;<a rel="up" accesskey="u" href="index.html#Top">Top</a>
     32 <hr>
     33 </div>
     34 
     35 <!-- node-name,  next,  previous,  up -->
     36 <h2 class="chapter">8 Environments</h2>
     37 
     38 <p><a name="index-environments-104"></a><a name="index-ignore-105"></a>
     39   An environment consists of a set of bindings, and a list of zero or
     40 more references to other environments called its parents. 
     41 <!-- TODO add xref to lookup algo & ground env -->
     42 Changing the set of bindings of an environment, or setting the
     43 referent of the reference in a binding, is a mutation of the
     44 environment. (Changing the parent list, or a referent in the list,
     45 would be a mutation of the environment too, but there is no facility
     46 provided to do it.) The Kernel data type environment is encapsulated. 
     47 Among other things, there is no facility provided for enumerating all
     48 the variables exhibited by an environment (which is not required,
     49 after all, to be a finite set), and no facility for identifying the
     50 parents of an environment.  Two environments are <code>equal?</code> iff
     51 they are <code>eq?</code>.
     52 
     53    <p>An auxiliary data type used by combiners that perform binding is
     54 ignore. The ignore type consists of a single immutable value, having
     55 external representation <code>#ignore</code>.  The ignore type is
     56 encapsulated.
     57 
     58 <div class="defun">
     59 &mdash; Applicative: <b>environment?</b> (<var>environment? . objects</var>)<var><a name="index-environment_003f-106"></a></var><br>
     60 <blockquote><p>  The primitive type predicate for type environment. 
     61 <code>environment?</code> returns true iff all the objects in <code>objects</code>
     62 are of type environment. 
     63 </p></blockquote></div>
     64 
     65 <div class="defun">
     66 &mdash; Applicative: <b>ignore?</b> (<var>ignore? . objects</var>)<var><a name="index-ignore_003f-107"></a></var><br>
     67 <blockquote><p>  The primitive type predicate for type ignore.  <code>ignore?</code>
     68 returns true iff all the objects in <code>objects</code> are of type ignore. 
     69 </p></blockquote></div>
     70 
     71 <div class="defun">
     72 &mdash; Applicative: <b>eval</b> (<var>eval expression environment</var>)<var><a name="index-eval-108"></a></var><br>
     73 <blockquote><!-- TODO add xref to tail context -->
     74      <!-- TODO add xref to evaluation description -->
     75         <p>The <code>eval</code> applicative evaluates <code>expression</code> in
     76 <code>environment</code>, as a tail context, returning the resulting value. 
     77 </p></blockquote></div>
     78 
     79 <div class="defun">
     80 &mdash; Applicative: <b>make-environment</b> (<var>make-environment . environments</var>)<var><a name="index-make_002denvironment-109"></a></var><br>
     81 <blockquote><p>  The applicative constructs and returns a new environment, with
     82 initially no local bindings, and parent environments the environments
     83 listed in <code>environments</code>. The constructed environment internally
     84 stores its list of parents independent of the first-class list
     85 <code>environments</code>, so that subsequent mutation of
     86 <code>environments</code> will not change the parentage of the constructed
     87 environment. If the provided list <code>environments</code> is cyclic, the
     88 constructed environment will still check each of its parents at most
     89 once, and signal an error if no binding is found locally or in any of
     90 <!-- TODO add xref to cons, mutation, eq? and equal? -->
     91 the parents.  No two objects returned by different calls to
     92 <code>make-environment</code> are <code>eq?</code> to each other. 
     93 </p></blockquote></div>
     94 
     95 <div class="defun">
     96 &mdash; Operative: <b>$define!</b> (<var>$define! &lt;definiend&gt; &lt;expression&gt;</var>)<var><a name="index-g_t_0024define_0021-110"></a></var><br>
     97 <blockquote><!-- TODO move formal parameter tree definition to the intro -->
     98      <!-- TODO move matching definition to the intro -->
     99         <p><code>&lt;definiend&gt;</code> should be a formal parameter tree, as described
    100 below; otherwise, an error is signaled.
    101 
    102         <p>The <code>$define!</code> operative evaluates <code>&lt;expression&gt;</code> in the
    103 dynamic environment and matches <code>&lt;definiend&gt;</code> to the result in
    104 the dynamic environment, binding each symbol in definiend in the
    105 dynamic environment to the corresponding part of the result; the
    106 matching process will be further described below. The ancestors of the
    107 dynamic environment, if any, are unaffected by the matching process,
    108 as are all bindings, local to the dynamic environment, of symbols not
    109 in <code>&lt;definiend&gt;</code>.  The result returned by <code>$define!</code> is
    110 inert.
    111 
    112         <p>A formal parameter tree has the following context-free structure:
    113      <pre class="example">          ptree:: symbol | #ignore | () | (ptree . ptree)
    114 </pre>
    115         <p>That is, a formal parameter tree is either a symbol, or ignore, or
    116 nil, or a pair whose car and cdr referents are formal parameter trees. 
    117 A formal parameter tree must also be acyclic, and no one symbol can
    118 occur more than once in it.  It is not an error for a pair in the tree
    119 to be reachable from the root by more than one path, as long as there
    120 is no cycle; but if any particular symbol were reachable from the root
    121 by more than one path, that would count as occurring more than once. 
    122 Thus, if a pair is reachable by more than one path, there must be no
    123 symbols reachable from it.
    124 
    125         <p>Matching of a formal parameter tree <code>t</code> to an object <code>o</code>
    126 in an environment <code>e</code> proceeds recursively as follows.  If the
    127 matching process fails, an error is signaled.
    128           <ul>
    129 <li>If <code>t</code> is a symbol, then <code>t</code> is bound to <code>o</code> in
    130 <code>e</code>.
    131 
    132           <li>If <code>t</code> is <code>#ignore</code>, no action is taken.
    133 
    134           <li>If <code>t</code> is nil, then <code>o</code> must be nil (else matching fails).
    135 
    136           <li>If <code>t</code> is a pair, then <code>o</code> must be a pair (else matching
    137 fails). The car of <code>t</code> is matched to the car of <code>o</code> in
    138 <code>e</code>, and the cdr of <code>t</code> is matched to the cdr of <code>o</code> in
    139 <code>e</code>. 
    140 </ul>
    141         </p></blockquote></div>
    142 
    143 <div class="defun">
    144 &mdash; Operative: <b>$let</b> (<var>$let &lt;bindings&gt; . &lt;objects&gt;</var>)<var><a name="index-g_t_0024let-111"></a></var><br>
    145 <blockquote><!-- TODO add xref to formal parameter tree -->
    146         <p><code>&lt;bindings&gt;</code> should be a finite list of
    147 formal-parameter-tree/expression pairings, each of the form
    148 <code>(formals expression)</code>, where each <code>formals</code> is a formal
    149 parameter, and no symbol occurs in more than one of the
    150 <code>formals</code>.
    151 
    152         <p>The following equivalence holds:
    153 
    154      <pre class="example">          ($let ((form1 exp1) ... (formn expn)) . objects) ==
    155             (($lambda (form1 ... formn) . objects) exp1 ... expn)
    156 </pre>
    157         <!-- TODO add xref to tail context -->
    158         <p>Thus, the <code>expk</code> are first evaluated in the dynamic environment,
    159 in any order; then a child environment <code>e</code> of the dynamic
    160 environment is created, with the <code>formk</code> matched in <code>e</code> to
    161 the results of the evaluations of the <code>expk</code>; and finally the
    162 subexpressions of <code>objects</code> are evaluated in <code>e</code> from left
    163 to right, with the last (if any) evaluated as a tail context, or if
    164 <code>objects</code> is empty the result is inert. 
    165 </p></blockquote></div>
    166 
    167 <div class="defun">
    168 &mdash; Operative: <b>$binds?</b> (<var>$binds? &lt;exp&gt; . &lt;symbols&gt;</var>)<var><a name="index-g_t_0024binds_003f-112"></a></var><br>
    169 <blockquote><p>  Operative <code>$binds</code> evaluates <code>&lt;exp&gt;</code> in the dynamic
    170 environment; call the result <code>env</code>.  <code>env</code> must be an
    171 environment.  The operative is a predicate that returns true iff all
    172 its later operands, <code>&lt;symbols&gt;</code>, are visibly bound in <code>env</code>. 
    173 </p></blockquote></div>
    174 
    175 <div class="defun">
    176 &mdash; Applicative: <b>get-current-environment</b> (<var>get-current-environment</var>)<var><a name="index-get_002dcurrent_002denvironment-113"></a></var><br>
    177 <blockquote><p>  The <code>get-current-environment</code> applicative returns the dynamic
    178 environment in which it is called. 
    179 </p></blockquote></div>
    180 
    181 <div class="defun">
    182 &mdash; Applicative: <b>make-kernel-standard-environment</b> (<var>make-kernel-standard-environment</var>)<var><a name="index-make_002dkernel_002dstandard_002denvironment-114"></a></var><br>
    183 <blockquote><!-- TODO add xref to ground environment/standard environment -->
    184         <p>The <code>make-kernel-standard-environment</code> applicative returns a
    185 standard environment; that is, a child of the ground environment with
    186 no local bindings. 
    187 </p></blockquote></div>
    188 
    189 <div class="defun">
    190 &mdash; Operative: <b>$let*</b> (<var>$let* &lt;bindings&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024let_002a-115"></a></var><br>
    191 <blockquote><!-- TODO add xref to formal ptree -->
    192         <p><code>&lt;bindings&gt;</code> should be a finite list of
    193 formal-parameter-tree/expression pairings, each of the form
    194 <code>(formals expression)</code>, where each <code>formals</code> is a formal
    195 parameter tree; <code>&lt;body&gt;</code> should be a list of expressions.
    196 
    197         <p>The following equivalences hold:
    198 
    199      <pre class="example">          ($let* () . body) == ($let () . body)
    200           
    201           ($let* ((form exp) . bindings) . body) ==
    202             ($let ((form exp)) ($let* bindings . body))
    203 </pre>
    204         </blockquote></div>
    205 
    206 <div class="defun">
    207 &mdash; Operative: <b>$letrec</b> (<var>$letrec &lt;bindings&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024letrec-116"></a></var><br>
    208 <blockquote><!-- add xref for $let -->
    209         <p><code>&lt;bindings&gt;</code> and <code>&lt;body&gt;</code> should be as described for
    210 <code>$let</code>.
    211 
    212         <p>The following equivalence holds:
    213      <pre class="example">          ($letrec ((form1 exp1) ... (formn expn)) . body) ==
    214             ($let () ($define! (form1 ... formn) (list exp1 ... expn)) . body)
    215 </pre>
    216         </blockquote></div>
    217 
    218 <div class="defun">
    219 &mdash; Operative: <b>$letrec*</b> (<var>$letrec* &lt;bindings&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024letrec_002a-117"></a></var><br>
    220 <blockquote><!-- TODO add xref to $let* -->
    221         <p><code>&lt;bindings&gt;</code> and <code>&lt;body&gt;</code> should be as described for
    222 <code>$let*</code>.
    223 
    224         <p>The following equivalences hold:
    225      <pre class="example">          ($letrec* () . body) == ($letrec () . body)
    226           
    227           ($letrec* ((form exp) . bindings) . body) ==
    228             ($letrec ((form exp)) ($letrec* bindings . body))
    229 </pre>
    230         </blockquote></div>
    231 
    232 <div class="defun">
    233 &mdash; Operative: <b>$let-redirect</b> (<var>$let-redirect &lt;exp&gt; &lt;bindings&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024let_002dredirect-118"></a></var><br>
    234 <blockquote><!-- TODO add xref to $let -->
    235         <p><code>&lt;bindings&gt;</code> and <code>&lt;body&gt;</code> should be as described for
    236 <code>$let</code>.
    237 
    238         <p>The following equivalence holds:
    239 
    240      <pre class="example">          ($let-redirect exp ((form1 exp1) ... (formn . body) expn)) ==
    241             ((eval (list $lambda (form1 ... formn) body) exp) expn ... expn)
    242 </pre>
    243         </blockquote></div>
    244 
    245 <div class="defun">
    246 &mdash; Operative: <b>$let-safe</b> (<var>$let-safe &lt;bindings&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024let_002dsafe-119"></a></var><br>
    247 <blockquote><!-- TODO add xref to $let -->
    248         <p><code>&lt;bindings&gt;</code> and <code>&lt;body&gt;</code> should be as described for
    249 <code>$let</code>.
    250 
    251         <p>The following equivalence holds:
    252 
    253      <pre class="example">          ($let-safe bindings . body) ==
    254             ($let-redirect (make-kernel-standard-environment) bindings . body)
    255 </pre>
    256         </blockquote></div>
    257 
    258 <div class="defun">
    259 &mdash; Operative: <b>$remote-eval</b> (<var>$remote-eval &lt;exp1&gt; &lt;exp2&gt;</var>)<var><a name="index-g_t_0024remote_002deval-120"></a></var><br>
    260 <blockquote><!-- TODO add xref to tail context -->
    261         <p>Operative <code>$remote-eval</code> evaluates <code>&lt;exp2&gt;</code> in the dynamic
    262 environment, then evaluates <code>&lt;exp1&gt;</code> as a tail context in the
    263 environment that must result from the first evaluation. 
    264 </p></blockquote></div>
    265 
    266 <div class="defun">
    267 &mdash; Operative: <b>$bindings-&gt;environment</b> (<var>$bindings-&gt;environment . &lt;bindings&gt;</var>)<var><a name="index-g_t_0024bindings_002d_003eenvironment-121"></a></var><br>
    268 <blockquote><!-- TODO add xref to $let -->
    269         <p><code>&lt;bindings&gt;</code> should be as described for <code>$let</code>.
    270 
    271         <p>The following equivalence holds:
    272 
    273      <pre class="example">          ($bindings-&gt;environment . bindings) ==
    274             ($let-redirect (make-environment) bindings (get-current-environment))
    275 </pre>
    276         </blockquote></div>
    277 
    278 <div class="defun">
    279 &mdash; Applicative: <b>eval-string</b> (<var>eval-string string environment</var>)<var><a name="index-eval_002dstring-122"></a></var><br>
    280 <blockquote><p><code>string</code> should be the external representation of a single
    281 object.  If none or more than one external representation is found in
    282 <code>string</code> then an error is signaled.
    283 
    284         <p>Applicative <code>eval-string</code> reads an external representation from
    285 string, and evaluates the resulting object in <code>environment</code>, as a
    286 tail context, returning the resulting value. 
    287 <!-- TODO add xref to tail context. -->
    288 </p></blockquote></div>
    289 
    290 <div class="defun">
    291 &mdash; Operative: <b>$set!</b> (<var>$set! &lt;exp1&gt; &lt;formals&gt; &lt;exp2&gt;</var>)<var><a name="index-g_t_0024set_0021-123"></a></var><br>
    292 <blockquote><!-- TODO add xref to $define! -->
    293      <!-- TODO add xref to matching algo -->
    294         <p><code>&lt;formals&gt;</code> should be as described for the <code>$define!</code>
    295 operative.  The <code>$set!</code> operative evaluates <code>&lt;exp1&gt;</code> and
    296 <code>&lt;exp2&gt;</code> in the dynamic environment; call the results <code>env</code>
    297 and <code>obj</code>.  If <code>env</code> is not an environment, an error is
    298 signaled.  Then the operative matches <code>&lt;formals&gt;</code> to <code>obj</code>
    299 in environment <code>env</code>.  Thus, the symbols of <code>&lt;formals&gt;</code> are
    300 bound in <code>env</code> to the corresponding parts of <code>obj</code>. 
    301 The result returned by <code>$set!</code> is inert. 
    302 </p></blockquote></div>
    303 
    304 <div class="defun">
    305 &mdash; Operative: <b>$provide!</b> (<var>$provide! &lt;symbols&gt; . &lt;body&gt;</var>)<var><a name="index-g_t_0024provide_0021-124"></a></var><br>
    306 <blockquote><p>  <code>&lt;symbols&gt;</code> must be a finite list of symbols, containing no
    307 duplicates.  <code>&lt;body&gt;</code> must be a finite list.
    308 
    309         <p>The <code>$provide!</code> operative constructs a child <code>e</code> of the
    310 dynamic environment <code>d</code>; evaluates the elements of <code>&lt;body&gt;</code>
    311 in <code>e</code>, from left to right, discarding all of the results; and
    312 exports all of the bindings of symbols in <code>&lt;symbols&gt;</code> from
    313 <code>e</code> to <code>d</code>, i.e., binds each symbol in <code>d</code> to the
    314 result of looking it up in <code>e</code>.  The result returned by
    315 <code>$provide!</code>  is inert.
    316 
    317         <p>The following equivalence holds:
    318 
    319      <pre class="example">          ($provide!  symbols . body) ==
    320           ($define!  symbols ($let () ($sequence . body) (list . symbols)))
    321 </pre>
    322         </blockquote></div>
    323 
    324 <div class="defun">
    325 &mdash; Operative: <b>$import!</b> (<var>$import! &lt;exp&gt; . &lt;symbols&gt;</var>)<var><a name="index-g_t_0024import_0021-125"></a></var><br>
    326 <blockquote><p>  <code>&lt;symbols&gt;</code> must be a list of symbols.
    327 
    328         <p>The <code>$import!</code> operative evaluates <code>&lt;exp&gt;</code> in the dynamic
    329 environment; call the result <code>env</code>. <code>env</code> must be an
    330 environment. Each distinct symbol <code>s</code> in <code>&lt;symbols&gt;</code> is
    331 evaluated in <code>env</code>, and <code>s</code> is bound in the dynamic
    332 environment to the result of this evaluation.
    333 
    334         <p>The following equivalence holds:
    335 
    336      <pre class="example">          ($import! exp . symbols) ==
    337           ($define! symbols ($remote-eval (list symbols) exp))
    338 </pre>
    339         </blockquote></div>
    340 
    341 <!-- *-texinfo-*- -->
    342    </body></html>
    343