In this episode of SKILL for the Skilled I'll introduce a feature of the let
primitive that Scheme programmers will find familiar, but other readers may have never seen before. The feature is called named let, and I'll show you how to use it to sum the numbers in a given list.
Named LET
There is a feature of let
available in SKILL++ which is not available in traditional SKILL, called named let. Here is an example of how it can be used to sum a given list of numbers. (defun sumlist_7a (numbers)
(let REPEAT
((sum_so_far 0)
(rest numbers))
(if rest
(REPEAT (plus sum_so_far (car rest))
(cdr rest))
sum_so_far)))
In this example, the named let defines a local function named, REPEAT
and calls it once with the two arguments, 0
and numbers
. Of course, REPEAT
is by no means a reserved word; you can name the local function any valid variable name. Within the body of the named let you may call the local function with two arguments. You may recursively call the function zero, one, or more times as your algorithm requires. Testing the function
If we enable tracing of sumlist_7a
and REPEAT
, we can see what happens when calling sumlist_7a
. We can see that the local function, REPEAT
is called recursively several times, and that the implementation does in fact return the correct sum of the given list of numbers. (trace sumlist_7a)
(trace REPEAT)
(sumlist_7a '(1 2 3 4 5))
|sumlist_7a((1 2 3 4 5))
||(REPEAT 0 (1 2 3 4 5))
|||(REPEAT 1 (2 3 4 5))
||||(REPEAT 3 (3 4 5))
|||||(REPEAT 6 (4 5))
||||||(REPEAT 10 (5))
|||||||(REPEAT 15 nil)
|||||||REPEAT --> 15
||||||REPEAT --> 15
|||||REPEAT --> 15
||||REPEAT --> 15
|||REPEAT --> 15
||REPEAT --> 15
|sumlist_7a --> 15
15
Equivalent to labels
The named let is more or less equivalent to a declaration and call of a local function as if by using labels
. If you recall, this is exactly what was shown in sumlist_3b
in SKILL for the Skilled: Many Ways to Sum a List (Part 3).
(defun sumlist_3b (numbers)
(labels ((sum (sum_so_far rest)
(if rest
(sum (plus (car rest) sum_so_far)
(cdr rest))
sum_so_far)))
(sum 0 numbers)))
If you trace sumlist_3b
and sum
you'll see that it executes pretty much the same thing as sumlist_7a
.
(trace sumlist_3b)
(trace sum)
(sumlist_3b '(1 2 3 4 5))
|sumlist_3b((1 2 3 4 5))
||(sum 0 (1 2 3 4 5))
|||(sum 1 (2 3 4 5))
||||(sum 3 (3 4 5))
|||||(sum 6 (4 5))
||||||(sum 10 (5))
|||||||(sum 15 nil)
|||||||sum --> 15
||||||sum --> 15
|||||sum --> 15
||||sum --> 15
|||sum --> 15
||sum --> 15
|sumlist_3b --> 15
15
Illusion of jumping to the top
The illusion (or abstraction) presented by the named let is that of being able to jump back to the top of the let
form, and evaluate it again with different initialization values.
Consider this simple let
example.
(let loop
((a 10)
(b 0))
(println (list a b))
(when (plusp a)
(loop (sub1 a)
(add1 b))))
Which prints the following output. (10 0)
(9 1)
(8 2)
(7 3)
(6 4)
(5 5)
(4 6)
(3 7)
(2 8)
(1 9)
(0 10)
Doesn't work in traditional SKILL
If you try to evaluate a named let in traditional SKILL (e.g., with a .il file extension), you'll get an error something like the following, which basically means that SKILL let expects a list as its first operand and you have given the symbol loop
instead.
*Error* let: local bindings must be a proper list - loop
let is syntactic sugar for lambda
In SKILL++ the normal let has the same semantics as calling an unnamed function with particular parameter values. For example:
(let ((a X)
(b Y)
(c Z))
(expr1 a b)
(expr2 b c))
Is semantically the same as the following arguably less readable expression. The expression uses funcall to call a nameless function, defined by the (lambda (a b c) ...)
; in particular to call it with the three values X
, Y
, and Z
. In fact the two code snippets are simply syntactical transforms of each other. (funcall (lambda (a b c)
(expr1 a b)
(expr2 b c))
X
Y
Z)
When you look at the equivalent lambda
form of let
it is immediately clear that the expressions within the lambda are not able to make recursive calls to this unnamed function. This limitation is solved by the named let. Named let and tail-call optimization
The illusion of jumping back to the top in sort of a goto
fashion is indeed what happens if tail-call-elimination is enabled via the optimizeTailCall status flag explained in SKILL for the Skilled: Many Ways to Sum a List (Part 4).
Summary
In this post I've shown some examples of how to used the named let construct of SKILL++. This construct converts the conventional let
into a loop --- a loop which can be repeated by calling the label as a function, providing the next iteration's variable values.
More to come
In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.
See Also
SKILL for the Skilled: Many Ways to Sum a List (Part 3)
SKILL for the Skilled: Many Ways to Sum a List (Part 4)
Scheme In particular see the discussion of named let