-
Notifications
You must be signed in to change notification settings - Fork 1
/
srfi-26.html
435 lines (411 loc) · 17.5 KB
/
srfi-26.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
<!DOCTYPE html PUBLIC "-//IETF//DTD HTML//EN" "http://www.w3.org/TR/html.dtd">
<html lang="en">
<head>
<title>SRFI 26: Notation for Specializing Parameters without Currying</title>
<meta charset="utf-8" />
<meta content="width=device-width, initial-scale=1" name="viewport" />
<link href="https://srfi.schemers.org/srfi.css" rel="stylesheet" type="text/css" />
<link href="/favicon.png" rel="icon" sizes="192x192" type="image/png" />
</head>
<body>
<h1><a href="https://srfi.schemers.org/"><img alt="SRFI surfboard logo" class="srfi-logo" src="https://srfi.schemers.org/srfi-logo.svg" /></a>26: Notation for Specializing Parameters without Currying</h1>
<p>by Sebastian Egner</p>
<h2>Status</h2>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+26+at+srfi+dotschemers+dot+org">srfi-26@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-26">archive</a>.</p>
<ul>
<li>Draft: 2002-02-06--2002-04-06 </li>
<li>Revised: 2002-02-15</li>
<li>Revised: 2002-02-28</li>
<li>Revised: 2002-06-04</li>
<li>Revised: 2002-06-06</li>
<li>Final: 2002-06-14</li>
</ul>
<h2>Abstract</h2>
<p>
When programming in functional style,
it is frequently necessary to specialize some of the
parameters of a multi-parameter procedure.
For example, from the binary operation <code>cons</code>
one might want to obtain the unary operation
<code>(lambda (x) (cons 1 x))</code>.
This specialization of parameters is also known as
"partial application", "operator section" or "projection".
</p>
<p>
The mechanism proposed here allows to write this sort
of specialization in a simple and compact way.
The mechanism is best explained by a few examples:
</p>
<table>
<tr>
<td><code>(cut cons (+ a 1) <>)</code></td>
<td>is the same as</td>
<td><code>(lambda (x2) (cons (+ a 1) x2))</code></td>
</tr>
<tr>
<td><code>(cut list 1 <> 3 <> 5)</code></td>
<td>is the same as</td>
<td><code>(lambda (x2 x4) (list 1 x2 3 x4 5))</code></td>
</tr>
<tr>
<td><code>(cut list)</code></td>
<td>is the same as</td>
<td><code>(lambda () (list))</code></td>
</tr>
<tr>
<td><code>(cut list 1 <> 3 <...>)</code></td>
<td>is the same as</td>
<td><code>(lambda (x2 . xs) (apply list 1 x2 3 xs))</code></td>
</tr>
<tr>
<td><code>(cut <> a b)</code></td>
<td>is the same as</td>
<td><code>(lambda (f) (f a b))</code></td>
</tr>
</table>
<p>
As you see, the macro <code>cut</code> specializes some of the
parameters of its first argument.
The parameters that are to show up as formal
variables of the result are indicated by the symbol <code><></code>,
pronouced as "slot". In addition, the symbol <code><...></code>,
pronounced as "rest-slot", matches all residual arguments of a variable
argument procedure.
As you can see from the last example above, the first argument can also
be a slot, as one should expect in Scheme.
</p>
<p>
In addition to <code>cut</code>, there is a variant called <code>cute</code>
(a mnemonic for "<code>cut</code> with evaluated non-slots") which evaluates
the non-slot expressions at the time the procedure is specialized, not at
the time the specialized procedure is called.
For example,
</p>
<table>
<tr>
<td><code>(cute cons (+ a 1) <>)</code></td>
<td>is the same as</td>
<td><code>(let ((a1 (+ a 1))) (lambda (x2) (cons a1 x2)))</code></td>
</tr>
</table>
<p>
As you see from comparing this example with the first example above,
the <code>cute</code>-variant will evaluate <code>(+ a 1)</code>
once, while the <code>cut</code>-variant will evaluate it during
every invokation of the resulting procedure.
</p>
<p>
The mechanism proposed in this SRFI allows specializing any subset
of the variables of a procedure.
The result can be of fixed arity or of variable arity.
The mechanism does not allow permutation, omission, duplication
or any other processing of the arguments;
for this it is necessary to write to use a different
mechanism such as <code>lambda</code>.
</p>
<h2>Rationale</h2>
<p>
A particularly elegant way to deal with specialization is known
as <em>currying</em> (Schönfinkel 1924, Curry 1958).
The idea of currying is to reduce multi-argument functions to
single-argument functions by regarding an <i>n</i>-ary
function as a unary function mapping its first argument into
an (<i>n</i>-1)-ary function (which is curried in turn).
This point of view, apart from its theoretical elegance,
allows an extremely compact notation for specializing the
first argument of a function.
In the first example, one could simply write <code>(cons 1)</code>.
</p>
<p>
Yet, Scheme is not a curried language---the
number of arguments passed to a procedure must match
the number of its parameters at all times.
This allows zero- and variable-arity procedures
but in order to specialize parameters
one usually has to write down a lambda-expression
and invent some irrelevant identifiers for its
formal variables (<code>x</code> in the example).
For this reason, the mechanism proposed in this SRFI
provides a simple and compact notation for specializing
any subset of the parameters of a procedure.
</p>
<p>
Note: <em>The mechanism proposed here is not currying!</em>
</p>
<p>
The purpose of the mechanism proposed here is to make the benefits
of currying available within the programming language Scheme.
There are two primary benefits of currying in practice:
Higher-order types are substantially simplified and
there is a simple notation for specializing parameters.
The type aspect is irrelevant as Scheme has latent typing.
The specialization aspect is largly covered with this SRFI.
</p>
<p>
Here are a few more examples for illustration:
</p>
<table>
<tr>
<td><code>(map (cut * 2 <>) '(1 2 3 4))</code></td>
</tr>
<tr>
<td><code>(map (cut vector-set! x <> 0) indices)</code></td>
</tr>
<tr>
<td><code>(for-each (cut write <> port) exprs)</code></td>
</tr>
<tr>
<td><code>(map (cut <> x y z) (list min max))</code></td>
</tr>
<tr>
<td><code>(for-each (cut <>) thunks)</code></td>
</tr>
</table>
<h2>Specification</h2>
<p>
The formal syntax of a specialized expression, in the style of the
<a href="http://www.schemers.org/Documents/Standards/R5RS/"><i>Revised^5 Report on the Algorithmic Language Scheme</i></a>:</p><p>
</p>
<table>
<tr id="cut">
<td><code><cut-expression></code></td>
<td><code>--></code></td>
<td></td>
<td><code>(cut <slot-or-expr> <slot-or-expr>*)</code></td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td>|</td>
<td><code>(cut <slot-or-expr> <slot-or-expr>* <...>)</code></td>
<td>; with "rest-slot"</td>
</tr>
<tr id="cute">
<td></td>
<td></td>
<td>|</td>
<td><code>(cute <slot-or-expr> <slot-or-expr>*)</code></td>
<td>; evaluate non-slots at specialization time</td>
</tr>
<tr>
<td></td>
<td></td>
<td>|</td>
<td><code>(cute <slot-or-expr> <slot-or-expr>* <...>)</code></td>
<td>; with "rest-slot"</td>
</tr>
<tr>
<td><code><slot-or-expr></code></td>
<td><code>--></code></td>
<td></td>
<td><code><></code></td>
<td>; a "slot"</td>
</tr>
<tr>
<td></td>
<td></td>
<td>|</td>
<td> <code><expression></code></td><td>; a "non-slot expression"</td>
</tr>
</table>
<p>
The macro <code>cut</code> transforms a <code><cut-expression></code>
into a <code><lambda expression></code> with as many formal variables
as there are slots in the list <code><slot-or-expr>*</code>.
The body of the resulting <code><lambda expression></code> calls
the first <code><slot-or-expr></code> with arguments from
<code><slot-or-expr>*</code> in the order they appear.
In case there is a rest-slot symbol, the resulting procedure is also of
variable arity, and the body calls the first <code><slot-or-expr></code>
with all arguments provided to the actual call of the specialized procedure.
</p>
<p>
The macro <code>cute</code> is similar to the macro <code>cut</code>,
except that it first binds new variables to the result of evaluating
the non-slot expressions (in an unspecific order) and then substituting
the variables for the non-slot expressions.
In effect, <code>cut</code> evaluates non-slot expressions at the time
the resulting procedure is called, whereas <code>cute</code> evaluates
the non-slot expressions at the time the procedure is constructed.
</p>
<h2>Implementation</h2>
<p>
The reference implementation defines the two macros
<code>cut</code> and <code>cute</code> using macro
mechanism of R5RS.
It does not use any other SRFI or any library.
The implementation makes use of internal macros to
run through the list of <code><slot-or-expr;></code>s.
As macros in R5RS are hygienic and referentially transparent,
the macro mechanism makes sure the names of the newly
introduced formal variables are unique and do not clash.
The template <code>(param ... slot)</code>, see
<a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%25_sec_7.1.5">Sect. 7.1.5. of R5RS</a>,
allows to preserve the order of arguments---which would get
reversed otherwise.
</p>
<p>
The reference implementation has been written by
Al Petrofsky. It can be found <a href="cut.scm">here</a>.
</p>
<p>
Finally, there is a small collection of
<a href="check.scm">confidence tests</a>.
It checks some special cases of the mechanism defined
in this SRFI and signals an error in case something is wrong.
Passing the tests does not mean a correct implementation.
</p>
<h2>Design Rationale</h2>
<h3>Why not real currying/uncurrying?</h3>
<p>
It is possible in Scheme to implement a macro turning a multi-argument
procedure into a nesting of single-argument procedures and back.
These operations are usually called "curry" and "uncurry" in
other programming languages.
Yet, Scheme remains an inherently uncurried language and is not
prepared to deal with curried procedures in a convenient way.
Hence, a "by the book" implementation of currying would only be useful
if you apply it in the sequence "curry, specialize some arguments,
and uncurry again"---which is exactly the purpose of the macro
<code>cut</code> specified in this document.
The primary relevance of currying/uncurrying in Scheme is to
teach concepts of combinatory logic.
</p>
<h3>Why not a more general mechanism, also allowing permutation,
omission and duplication of arguments?</h3>
<p>
The reason is that I, the author of this SRFI, consider more general
mechanisms too dangerous to mix them with the mechanism proposed here.
In particular, as soon as parameters are being rearranged it
is usually necessary to be aware of the meaning of the parameters;
unnamed variables can be quite harmful then.
The mechanism proposed here is designed to prevent this.
Please refer to the discussion threads
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00018.html">"OK, how about...,"</a> (Alan Bawden),
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00038.html">"is that useful?"</a> (Walter C. Pelissero), and
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00040.html">"l, the ultimate curry that is not curry"</a> (Al Petrofsky).
</p>
<h3>Why are the macro called <code>cut/cute</code> and not
[<em>enter your favourite here</em>]?</h3>
<p>
Well, the original name proposed for this SRFI was <code>curry</code>
which immediately stirred some emotions as it does not what is
commonly known as currying.
Some alternatives have been discussed, such as <code>section</code>,
<code>specialise</code>, <code>specialize</code>, <code>partial-apply</code>,
<code>partial-call</code>, <code>partial-lambda</code>,
<code>_j</code>, <code>_i</code>, <code>$</code>,
<code>&</code>, <code>srfi-26</code>, <code>foobar</code>,
<code>xyz</code>, <code>schoenfinkelize</code>,
<code>curry-which-isnt-curry</code>, <code>tandoori</code>,
and it has also been suggested to pick a five letter symbol uniformly
at random and fix this as a name.
To be fair, not all of these name have been put forward as serious proposals,
some of them were merely to illustrate a point in the discussion.
In addition, I have played with the game of the name quite a bit
and considered other candidates not listed here.
Despite the fact that the discussion list only represents a highly
biased random sample of people's opinion (motivation to post a message
is higher if you disagree, for example) it told me that the SRFI
could potentially benefit from a different name---however impractical
it may be to go for unanimous popularity.
The name <code>cut</code> refers to "operator section", as the
concept is often called in other programming languages,
but I tend to remember it as the acronym for "Curry Upon This" ;-).
The names for the evaluating version of <code>cut</code> that
have been proposed were <code>cut!</code>, <code>cutlet</code>,
<code>cut*</code>, and <code>cute</code>.
</p>
<h3>Is it possible to implement the SRFI without macros?</h3>
<p>
Not really.
As Stephan Houben has pointed out during the discussion (refer to
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00008.html">"Implementing it as a procedure"</a>) it is possible to implement the
<code>cute</code>-mechanism as a procedure.
Refer also to Al Petrofsky's posting
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00048.html">"Problems with "curry"'s formal specification"</a> for details.
However, the procedural implementation comes with a slight performance
penalty and it is not possible the implement the <code>cut</code>-mechanism
as a procedure, too.
As both are needed, we rely on macros to implement the SRFI.
</p>
<h3>Why is there another symbol for the rest-slot when lambda-expressions
use the dotted notation for variable length argument lists?</h3>
<p>
There are two reasons.
The first one is the existence of a procedural implementation
of a related mechanism (refer to the previous paragraph).
For a procedure, however, it is not possible to have dotted notation.
The second reason is the way the hygienic macro mechanism in R5RS
is defined to deal with dotted notation, as Felix Winkelmann has pointed out.
Refer to the discussion threads
<a href="https://srfi.schemers.org/srfi-26/mail-archive/msg00001.html">"Improper lists in macros [WAS: none]"</a>.
</p>
<h3>Why is it impossible to specify when a non-slot is evaluated individually per non-slot?</h3>
<p>
<code>Cut</code> evaluates all non-slots at the time the specialized
procedure is called and <code>cute</code> evaluates all non-slots at
the time the procedure is being specialized.
These are only the two extremes and it is possible to define a
syntax that allows to choose per non-slot.
However, I am convinced that the benefit of the greater flexibility
is not worth the risk of confusion.
If a piece of code really depends on the distinction, it might be
better to make this explicit through <code>let</code> and
<code>lambda</code>.
</p>
<h3>Why is <code>(cut if <> 0 1)</code> etc. illegal?</h3>
<p>
It is specified that a <code><slot-or-expr></code> must be
either the slot symbol or an <code><expression></code> in the sense
of <a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%25_sec_7.1.3"><i>R5RS,
Section 7.1.3</i></a>.
As <code>if</code> is no <code><expression></code>,
the above case is illegal.
The reason why <code>cut</code> and <code>cute</code> are
restricted in this sense is the difficulty of defining
the meaning of such generalized expressions.
Please refer to the discussion archive for details.
</p>
<h2>Acknowledgements</h2>
<p>
An important part of this SRFI is based on the contribution
of other people, mostly through the discussion archive.
In particular, the semantics and the design rationale have
been greatly improved in the course of the discussion.
I would like to thank all who have contributed.
</p>
<h2>Copyright</h2>
<p>Copyright (C) Sebastian Egner (2002). All Rights Reserved.</p>
<p>
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
</p>
<p>
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
</p>
<p>
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
</p>
<hr />
<address>Editor: <a href="mailto:srfi%20minus%20editors%20at%20srfi%20dot%20schemers%20dot%20org">Mike Sperber</a></address>
<address>Author: <a href="mailto:sebastian.egner@philips.com">Sebastian Egner</a></address>
<!-- Created: Mon Feb 4 15:20:00 EST 2002 -->
<!-- hhmts start -->
Last modified: Sun Jan 28 13:40:30 MET 2007
<!-- hhmts end -->
</body>
</html>