Introduction to continue and macros in Scheme

If you have not heard about call/cc, then you should definitely get acquainted with this powerful tool! Let's talk about the sequel to (call/cc), simple but difficult to understand design with a great strength in the right hands,. Implement the mechanism of yield/next/for... in, similar to that in Python. Wrap the inside with macro — another interesting mechanism Scheme.

The article is intended for beginners. Listary hardly learn something new, but I'd be grateful for any errors found.

the

What and why

Every programmer periodically confronted with insufficient expressiveness of your code when a simple beautiful idea requires writing hundreds of lines. It is always pushed to create new, more expressive tools such as OP, much more density per unit of program text.

Continued (continuation) is one of the mechanisms that allow the programmer on the move to create such tools. The history of call/cc (call-with-current-continuation, the syntactic structure that reflects the idea of sequels) is closely connected with Scheme, not the most popular language, which is, however, a few decades is a source of inspiration for programmers. So the story will be the Scheme language, and all code samples intended for interpretatsii Guile (I'm sure that with almost zero effort starts in Racket, Chicken, and probably a hundred other interpreters of this dialect of Lisp).

the

Part I. Continue

the

the Beginning (the essence of continuations)

Continued — this is my older brother GoTo, operator, cannot be used. The continuation gives the ability to:

the

the
• to (grab) the program state in the moment
the
• to Keep this state (there are other options)
the
• to Return to this condition later, when you want

But why go back to the previous state?

the

the
• again to go forward with the convening of a cycle. It's pretty naive application (in fact, the use of GoTo).
the
• to understand the real power of extensions, you need to figure out what means "program state" above. In fact remains the current call stack of functions, i.e. current context. But another function that should return a value of the previous (i.e. the one we actually wrap design call/cc — see below), is not saved. Subsequently it can be replaced by other code (in particular, by some constant). Imagine that you can get back to myself from the future to give the past any knowledge/material objects/indications for further action!

let us illustrate this in practice:

Let us imagine a piece of software. Function 1 calls function 2 that calls function 3 from some other variables. Before you call, for example, function 2, save state (called current context). Subsequently at any time we can return to this context replacing the result of the function chain with (func2 (func3 a b c)) with a required value, for example, d.

Check that everything works really so.

the

First example

Create some spherical example in vacuum. Define a function test-func:

the

; some function for example
(define test-func 
(if (> 3 5) "true" "false "))

(display test-func)
(newline)

The result (obvious):

the

>> false

Now save the context before evaluation of the condition in the if. Let's see how to do it:

the

(call/cc 
(lambda (cc) (Some actions)))

The advent of the call/cc requires the interpreter to take the current context and passed it into the lambda function, defined us inside. The lambda function takes a single argument (hereafter, the code will call it cc — short for "current continuation"). Can we keep this context:
the

(define *env* #f)
(call/cc 
(lambda (cc) 
(begin
(set! *env* cc) ; Take the context of cc, and store it in a variable *env*
(Some actions))))

Now take a magic. Take the saved context and turn to him. We wrapped design call/cc condition in the if block, so you need when calling context to pass in a value that should be returned instead of computing (> 3 5).

This is done as follows:

the

(*env* Any_value)

Here the "Any value" can be any code that returns a certain value, or the value.

Now, if we write:

the

(*env* #t)

we get back to the point, where was obtained the context, and it will look for the external in relation to the block (call/cc ...) code like a function inside this block (the if condition) returned #t!

the

the result

UPDATE:

comments have given understanding that the code (display (*env* #t)) may confuse you. Design (display ..) in this line will never print, because as soon as the interpreter reaches (*env* #t), will be made permanent transition to another state (more in comments). Thus, the following code does will not change from replacing (display (*env* #t)) to (*env* #t).

the

(define test-func 
(if (call/cc (lambda (cc) 
(begin
(set! *env* cc)
(> 3 5))
)) "true" "false "))
(display test-func)

(display (*env* #t))
(newline)

the

>> false true true true true true true true true true true true true true true true true true true true true true true true true true true true ... 

Everything works the way we wanted, but... an infinite loop?! Quietly, all in agreement with the theory. Let us examine how this example works.

We return to the state of the program somewhere within the call stack generated by the (display ...). There we substitute pleasing to us #t affecting the result (displays true), is safe output of (display ...), invoked (*env* #t), and in the new...

the

Make your own generator

First introduction to call/cc is an understanding of the power of this tool, but not immediately obvious how to use it and what you can implement. A classic list of things implemented with call/cc, includes loops, exit from a loop or recursion, the loop or recursion with a return, coroutines and multitasking kooperativnoe. Thus, the continuation can change the flow of vypolneniya program in every conceivable way.

Try to use this opportunity to implement the language Scheme of the analog generators in Python. We require that the result worked well:

the

; Define a generator function
(define-generator (generator-func arg1 arg2 ...)
(...
(yield result) ; Return new value
...))

; Define the values of the arguments. Now my-gen — generator:
(define my-gen (generator-10 30 func ...))

(display my-gen) ; Prints the first value
(display my-gen) ; Prints the second value

; Or print out all that is
(for item in (generator, func 100 70 ...)
(display item))

Perhaps not as simple as in Python, but Scheme is still limited by its syntax (which does not prevent him to be extremely simple and incredibly versatile).

the

First billet

The implementation of the function yield is almost obvious. Need to save the current context (in order then to continue with it), then make the jump back where you were caused by the generator and this generator is to substitute returned by yield value:

the

(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc) ; save the context
(*return* value)))) ; jump to the context saved earlier, with podstanovki value

the

the
• Immediately clear that each generator (there may be several in the program), must have their *env* and *return* stored within some local scope.
the
• From the first it follows that the yield cannot be global and, therefore, it is necessary to pass a function that invokes the yield
Implement this at the same time writing an example generator of the squares of the integers from 1 to n:

the

(define (create-generator func)
(define *env* (lambda () (func yield)))
(define *return* #f)

(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc) 
(*return* value))))

(lambda () 
(here is the logic generator)))

; The generator of the squares of numbers
(define (squares-gen n)
(lambda (yield)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1)))))))


the

Almost ready


The case remained for small: to record something in the variable *return*. To called once the generator is given the value, you need to save the context at the beginning of the generator, then to substitute its internal part of the return value. This is what the picture from the beginning of the post:





We are in a part of the program and want to go further forward. But you need to get the next value from the generator (box c). Go to the generator (persistent state and up the stairs), pick up the box and "teleported" back (back to the saved state), but with a box! In fact, you need to add a couple of lines:

the

(define (create-generator func)
(define ...)
...
(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*))))) ; Initially, just enter the function func, subsequently continue with a saved place, 
; substituting (yield smth) func in the code... nothing!


the

Result


Putting it all together:


Result

(define (create-generator func)
(define *env* (lambda () (func yield)))
(define *return* #f)

(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc) 
(*return* value))))

(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*)))))

; The generator of the squares of numbers
(define (squares-gen n)
(lambda (yield)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1)))))))

(define my-gen (create-generator (squares-gen 10)))


Check:

the

; Call my-gen 7 times
(let loop ((n 7))
(if (>n 0)
(begin
(display (my-gen))
(display " ")
(loop (- n 1)))))



the

>> 1 4 9 16 25 36 49 


the Hurrah! Works!

the

Note


I hope you noticed one obvious mistake. If we call the obtained generator more than 10 times, we'll enter an infinite loop. Calling (*env*), we return wholly to the state, which was the last iteration, because it is not persistent new, as it comes from the function code generator to yield. You can do, for example: if the generator is unable to give the next value, it returns the value of the cap, for example, "Stop Iteration".

How to do it? Test your understanding, think for yourself (welcome to comment). Need to add one line of code inside (define (create-generator func) ...).

the

Part II. Macros


the

Why?


We have achieved the desired behavior. But the syntax is not the same. To create a generator function, we need to wrap it with a lambda function, to make many unnecessary movements... fortunately, Scheme is a powerful mechanism macros. Macros, as always, evil if to plaster them everywhere, but if you write it once and for a long time, why not make your life beautiful syntactic sugar?

the

Brief description


the Macros-lit on the Internet is much better than continuing with it, so just briefly ostanovilsya on them (the second reason is the unexpectedly large size of the article; if the community deems it necessary for a detailed description of macros in Scheme, I will write a second article).

the
the
• Macros in Scheme are like preprocessor Macros in C. open to translation into bytecode.
the
• Macros transform syntax, and only them. We write some lines of code, the output of others.
the
• define-syntax and others like him define the rules for which there is marked transformation.

the Must will be incorrect in fact duplicate what has been told more than once, and on habré in particular.

Here we consider a subtlety that will play a significant role.

Write an example macro that defines a function is simply summing the elements of the list (for this macro, of course, is not necessary; for example, as always, from the air, but needed for understanding):

the

; adder list structure (sum (list 5 9 1 ...))
(define-syntax sum
(syntax-rules ()
((_ args-list)
(let loop ((res 0) (left-list args-list))
(if (not (null? left-list))
(loop (+ res (car left-list)) (cdr left-list))
res)))))

(display (sum (list 3 4 5 1)))
(newline)


the

>> 13


Everything works.

Now do this:

the

(define loop (list 3 4 5 1))
(display (sum loop))


Imagine what a mess will unfold this macro (because of the coincidence of names — loop, inside the macro and outside)? Ah, here comes the compile error... Run...

the

>> 13


Oh really?! How could this work? In fact, in Scheme the macro is not such a straight design, as it seems. In our case, the macro will unfold:

the

(let loop-1 ((res 0) (left-list loop))
(if (not (null? left-list))
(loop-1 (+ res (car left-list)) (cdr left-list))
res))


Macros can define name conflicts inside and outside, so the internal variable loop received another name, loop 1.

the

Syntax-case, with-syntax, datum->syntax


In our case, unfortunately, this intelligence macro only prevents. Inside the macro we will use a yield, which will be converted to yield-1.

To get the macro to work the way we need to, there is a more powerful design, the syntax-case.

Article and so it turned out too big, so detailed description of this instrument will be in next post (if need be).

The syntax is similar to syntax-rules, the difference is in the wrapper of the lambda function and method return values, using (syntax something) — function that returns the syntactic structure of "something".

Scheme contains a shorthand for (syntax ...): #'.
So the previous example will be copied (and the below code is in all senses equivalent code using syntax-rules):


sum via syntax-case
(define-syntax sum
(lambda (x)
(syntax-case x ()
((_ args-list)
#'(let loop ((res 0) (left-list args-list))
(if (not (null? left-list))
(loop (+ res (car left-list)) (cdr left-list))
res))))))



Enter the ID of the object from external to the macro scope (so to speak, out of the ordinary Scheme) in the inner scope of the macro, you can use datum->syntax.

For example, to yield should not become yield-1 inside (syntax ...), you can do this:

the

(define-syntax sum
(lambda (x)
(syntax-case x ()
((pattern)
(syntax-case (datum- > syntax x 'yield) ()
(yield (syntax ... yield ...)))))))


Scheme provides some syntactic sugar to make this code look nicer:

the

(define-syntax sum
(lambda (x)
(syntax-case x ()
((pattern)
(with-syntax (yield (datum- > syntax x 'yield))
(yield (syntax ... yield ...)))))))


As a result, we used the syntax-case, in fact, create a regular macro in which we can without any problems use the yield, and everything will work the way we expect.

the

Finally, use the macros in


Remember the syntax that we have made:


Syntax
; Define a generator function
(define-generator (generator-func arg1 arg2 ...)
(...
(yield result) ; Return new value
...))

; Define the values of the arguments. Now my-gen -- generator:
(define my-gen (generator-10 30 func ...))

(display my-gen) ; Prints the first value
(display my-gen) ; Prints the second value



Create a macro define-generator that generates a function with arguments arg1, arg2 ..., which returns a generator. The code is similar to what we already wrote:

the

; Create the right macro:
(define-syntax define-generator 
(lambda (x) ; the formal syntax syntax-case
(syntax-case x ()
((_ (name . args) body)
(with-syntax ((yield (datum- > syntax x 'yield))) ; will enter the external ID of the yield in the area vidisti macro

(define *env* (lambda () (body))) ; here and further duplicate the code written in the article
(define *return* #f)

(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc) 
(*return* value))))

(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*)))))))))))

(define-generator (squares-gen n)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1))))))

(define my-gen (squares-gen 10))

(let loop ((n 7))
(if (>n 0)
(begin
(display (my-gen))
(display " ")
(loop (- n 1)))))


the

>> 1 4 9 16 25 36 49 


the hurrah! Works!

the

Epilogue


If you knew a bit about continuations and macros, and I managed to convey to you what is written above, you can easily similar write implementation of a for ... in ... do Not forget about the mistake, intentionally left in the code.

Thank you if you read to the end. Hopefully now the Scheme will give someone else some inspiration in our favorite sport.

Article based on information from habrahabr.ru