The Artima Developer Community
Sponsored Link

Weblogs Forum
The Adventures of a Pythonista in Schemeland/8

11 replies on 1 page. Most recent reply: Oct 25, 2008 2:00 AM by Michele Simionato

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 11 replies on 1 page
Michele Simionato

Posts: 222
Nickname: micheles
Registered: Jun, 2008

The Adventures of a Pythonista in Schemeland/8 (View in Weblogs)
Posted: Oct 25, 2008 2:00 AM
Reply to this message Reply
Summary
In this episode I will explain the meaning of the "code is data" concept. To this aim I will discuss the quoting operation which allows to convert a code fragment into a list of symbols and primitive values - i.e. converts code into data. Then, I will discuss the issue of evaluating data as code.
Advertisement

Quoting

A distinguishing feature of the Lisp family of languages is the existence of a quoting operator denoted with a quote ' or with (quote ), the first form being syntactic sugar for the second. The quoting operator works as follows:

  1. on primitive values such as numbers, literal strings, symbols, etc, it works as an identity operator:
> '1
1
> '"hello"
"hello"
> ''a
'a
  1. expressions are converted into lists; for instance '(display "hello") is the list
> (list 'display '"hello")
(display "hello")

whereas '(let ((x 1)) (* 2 x)) is the list

> (list 'let (list (list 'x '1)) (list '* '2 'x))
(let ((x 1)) (* 2 x))

et cetera.

Hence every Scheme/Lisp program admits a natural representation as a (nested) list of symbols and primitive values: code is data. On the other hand, every nested list of symbols and primitive values corresponding to a syntactically valid Scheme/Lisp programs can be executed, both at runtime - with eval - or at compilation time - through macros. The consequences are fascinating: since every program is a list, it is possible to write programs that, by building lists, build other programs. Of course, you can do the same in other languages: for instance in Python you can generate strings corresponding to valid source code and you can evaluate such strings with various mechanisms (eval, exec, __import__, compile, etc). In C/C++ you can generate a string, save it into a file and compile it to a dynamic library, then you can import it at runtime; you also have the mechanism of pre-processor macros at your disposal for working at compile time. The point is that there is no language where code generation is as convenient as in Scheme/Lisp where it is buil-in, thanks to s-expressions or, you wish, thanks to parenthesis.

Quasi-quoting

In all scripting languages there is a form of string interpolation; for instance in Python you can write

def say_hello(user):
     return "hello, %(user)s" % locals()

In Scheme/Lisp, there is also a powerful form of list interpolation:

> (define (say-hello user)
    `("hello" ,user))

> (say-hello "Michele")
   ("hello" "Michele")

The backquote or (quasiquote ) syntax ` introduces a list to be interpolated (template); it is possible to replace some variables within the template, by prepending to them the unquoting operator (unquote ) or ,, denotated by a comma. In our case we are unquoting the user name, ,user. The function say-hello takes the user name as a string and returns a list containing the string "hello" together with the username.

There is another operator like unquote, called unquote-splicing or comma-at and written ,@, which works as follows:

> (let ((ls '(a b c))) `(func ,@ls))
(func a b c)

In practice ,@ls "unpacks" the list ls into its components: without the splice operator we would get:

> (let ((ls '(a b c))) `(func ,ls))
(func (a b c))

The power of quasiquotation stands in the code/data equivalence: since Scheme/Lisp code is nothing else than a list, it is easy to build code by interpolating a list template. For instance, suppose we want to evaluate a Scheme expression in a given context, where the contexts is given as a list of bindings, i.e. a list names/values:

(eval-with-context '((a 1)(b 2) (c 3))
  '(* a  (+ b c)))

How can we define eval-with-context? The answer is by eval-uating a template:

(define (eval-with-context ctx expr)
 (eval `(let ,ctx ,expr) (environment '(rnrs))))

Notice that eval requires a second argument that specifies the language known by the interpreter; in our case we declared that eval understands all the procedures and macros of the most recent RnRS standard (i.e. the R6RS standard). The environment specification has the same syntax of an import, since in practice it is the same concept: it is possible to specify user-defined modules as the eval environment. This is especially useful if you have security concerns, since you can run untrusted code in a stricter and safer subset of R6RS Scheme.

eval is extremely powerful and sometimes it is the only possible solution, in particular when you want to execute generic code at runtime, i.e. when you are writing an interpreter. However, often you only want to execute code known at compilation time: in this case the job of eval can be done more elegantly by a macro. When that happens, in practice you are writing a compiler.

Programs writing programs

http://www.phyast.pitt.edu/~micheles/scheme/writer.jpg

Once you realize that code is nothing else than data, it becomes easy to write programs taking as input source code and generating as output source code, i.e. it is easy to write a compiler. For instance, suppose we want to convert the following code fragment

(begin
 (define n 3)
 (display "begin program\n")
 (for i from 1 to n (display i)); for is not defined in R6RS
 (display "\nend program\n"))

which is not a valid R6RS program into the following program, which is valid according to the R6RS standard:

(begin
 (define n 3)
 (display "begin program\n")
 (let loop (( i 1)) ; for loop expanded into a named let
   (unless (>= i  n) (display i) (loop (add1 i))))
   (display "\nend program\n")))

begin is the standard Scheme syntax to group multiple expressions into a single expression without introducing a new scope (you may introduce a new scope with let) and preserving the evaluation order (in most functional languages the evaluation order is unspecified).

More in general, we want to write a script which is able to convert

(begin                                 (begin
  (expr1 ...)                            (expr1' ...)
  (expr2 ...)             -->            (expr2' ...)
   ...                                    ...
  (exprN ...))                           (exprN' ...))

where the expressions may be of kind for or any other kind not containing a subexpression of kind for. Such a script can be thought of as a preprocessor expanding source code from an high level language with a primitive for syntax into a low level language without a primitive for. Preprocessors of this kind are actually very primitive compilers, and Scheme syntax was basically invented to make the writing of compilers easy.

In this case you can write a compiler expanding for expressions into named lets as follows:

(import (rnrs) (only (ikarus) pretty-print))

;; a very low-level approach
(define (convert-for-into-loop begin-list)
  (assert (eq? 'begin (car begin-list)))
  `(begin
     ,@(map (lambda (expr)
              (if (eq? 'for (car expr)) (apply convert-for (cdr expr)) expr))
            (cdr begin-list))))

; i1 is subject to multiple evaluations, but let's ignore the issue
(define (convert-for i from i0 to i1 . actions)
  ;; from must be 'from and to must be 'to
  (assert (and (eq? 'from from) (eq? 'to to)))
  `(let loop ((i ,i0))
     (unless (>= i ,i1) ,@actions (loop (+ i 1)))))

(pretty-print
 (convert-for-into-loop
  '(begin
     (define n 3)
     (display "begin program\n")
     (for i from 1 to n (display i))
     (display "\nend program\n"))))

Running the script you will see that it replaces the for expression with a named let indeed. It is not difficult to extend the compiler to make it able to manage sub-expressions (the trick is to use recursion) and structures more general than begin: but I leave that as an useful exercise. In a future episode I will talk of code-walkers and I will discuss how to convert generic source code. In general, one can convert s-expression based source code by using an external compiler, as we did here, or by using the built-in mechanism provided by Scheme macros. Scheme macros are particularly powerful, since they feature extremely advanced pattern matching capabilities: the example I have just given, based on the primitive list operations car/cdr/map is absolutely primitive in comparison.

The next episode will be entirely devoted to macros. Don't miss it!

Appendix: solution of the exercises

In the latest episode I asked you to write an equivalent (for lists) of Python built-ins enumerate and zip. Here I give my solutions, so you may check them with yours.

Here the equivalent of Python enumerate:

(define (py-enumerate lst)
  (let loop ((i 0) (ls lst) (acc '()))
    (if (null? ls) (reverse acc)
        (loop (+ 1 i) (cdr ls) (cons `(,i ,(car ls)) acc)))))

and here is an example of usage:

> (py-enumerate '(a b c))
  ((0 a) (1 b) (2 c))

Here is the equivalent of Python zip:

(define (zip . lists)
 (apply map list lists))

Here is an example of usage:

> (zip '(0 a) '(1 b) '(2 c))
((0 1 2) (a b c))

Notice that zip works like the transposition operation in a matrix: given the rows, it returns the columns of the matrix.


Paddy McCarthy

Posts: 12
Nickname: paddy3118
Registered: Dec, 2005

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 25, 2008 5:18 AM
Reply to this message Reply
"
The point is that there is no language where code generation is as convenient as in Scheme/Lisp
"

How about TCL http://www.ledair.com/software/tcltk/ ?

- Paddy.

Michele Simionato

Posts: 222
Nickname: micheles
Registered: Jun, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 25, 2008 5:26 AM
Reply to this message Reply
Tcl does not have a syntax based on s-expressions, so if you want to manipulate source code you need a parser. Only for languages of the Lisp family the Abstract Syntax Tree is explicit. This is the important feature that makes code generation easy.

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 25, 2008 7:39 AM
Reply to this message Reply
Here's my implementation of enumerate (untested). Added bonus: free range function.

; creates a list of numbers from a to b
; (range 2 5) => (2 3 4)
(define (range a b)
  (if (>= a b)
      '()
      (cons a (range (+ a 1) b))))
 
(define (enumerate xs)
   (zip (range 0 (length xs)) xs))

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 25, 2008 7:53 AM
Reply to this message Reply
BTW

`(,i ,(car ls))


is equivalent to:

(list i (car ls))

Alexander Makhaev

Posts: 4
Nickname: macedonian
Registered: Oct, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 27, 2008 12:09 AM
Reply to this message Reply
It seems, that there is the missing unquote operator just before i1 at the last line of the convert-for procedure.

Fixed version:
(define (convert-for i from i0 to i1 . actions)
;; from must be 'from and to must be 'to
(assert (and (eq? 'from from) (eq? 'to to)))
`(let loop ((i ,i0))
(unless (>= i ,i1) ,@actions (loop (+ i 1)))))

Michele Simionato

Posts: 222
Nickname: micheles
Registered: Jun, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 27, 2008 12:45 AM
Reply to this message Reply
> It seems, that there is the missing unquote operator just
> before i1 at the last line of the
> convert-for procedure.

Indeed, it slipped somewhat. I have just fixed it, thanks for the catch!

Alexander Makhaev

Posts: 4
Nickname: macedonian
Registered: Oct, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 27, 2008 1:56 AM
Reply to this message Reply
> > It seems, that there is the missing unquote operator just
> > before i1 at the last line of the
> > convert-for procedure.

> I have just fixed it, thanks for the catch!

No problem, thanks for the great "The Adventures of a Pythonista in Schemeland" series!

Paul Frederiks

Posts: 1
Nickname: pantoffel
Registered: Oct, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 28, 2008 4:56 PM
Reply to this message Reply
I went a bit further with enumerate and zip. My versions mimic the behavior of the python functions. enumerate returns an object that has a next method that generates 1 pair at a time of an index and a value. In scheme returning a function is common solution. My zip works with lists with different lenghts.

#!r6rs
(import (rnrs))

(define (enumerate lst)
(define tuples (letrec ([loop (lambda (i lst acc)
(if (null? lst)
(reverse acc)
(loop (+ i 1) (cdr lst) (cons (cons i (car lst)) acc))))])
(loop 0 lst '())))
(lambda () (if (null? tuples)
'end
(let ([tuple (car tuples)])
(set! tuples (cdr tuples))
tuple))))

(define (enum/cc lst)
(letrec ([caller '()]
[next (lambda () (pair 0 lst))]
[pair (lambda (i lst)(cond [(null? lst) (caller 'end)]
[else (call/cc (lambda (rest-of-enumeration)
(set! next (lambda () (rest-of-enumeration (pair (+ i 1) (cdr lst)))))))
(caller (cons i (car lst)))]))])
(lambda () (call/cc (lambda (k) (set! caller k) (next))))))

(define (ormap predicate lst)
(call/cc (lambda (return)
(for-all (lambda (x) (if (predicate x) (return #t))) lst)
#f)))

(define (zip . lists)
(let zipper ([acc '()][lsts lists])
(if (ormap null? lsts)
(reverse acc)
(zipper (cons (map car lsts) acc) (map cdr lsts)))))

(define for-iter (lambda (next proc) (let ([e (next)]) (unless (eq? e 'end) (proc (car e) (cdr e)) (for-iter next proc)))))

Michele Simionato

Posts: 222
Nickname: micheles
Registered: Jun, 2008

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Oct 28, 2008 11:44 PM
Reply to this message Reply
Eh, your are cheating here! I meant solutions using only the concepts explained until now. So, not set!
e no call/cc please. I don't want my readers scared to death! ;-)

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Nov 6, 2008 10:56 PM
Reply to this message Reply
> The point is that there is no language where code generation
> is as convenient as in Scheme/Lisp where it is buil-in,
> thanks to*s*-expressions or, you wish, thanks to parenthesis.

I tend to think this is a funny short circuit that presents a problem as a solution. The problem is that people don't like to read and manipulate ASTs a lot. Really. So give them a disgusting program notation where this is the only mode of doing things and hence turn it into a convenience.

robert young

Posts: 361
Nickname: funbunny
Registered: Sep, 2003

Re: The Adventures of a Pythonista in Schemeland/8 Posted: Nov 14, 2008 11:06 AM
Reply to this message Reply
Self-modifying programs are a bygone concept in computer science. Modern programming languages preclude this ability, and good assembly language practice also avoids such tricks. It is ironic that a programming language attempting to open a new era in computer programming opens the door to such arcane techniques,...
-- Sterling and Shapiro/1994 [The Art of Prolog]

Flat View: This topic has 11 replies on 1 page
Topic: The Adventures of a Pythonista in Schemeland/11 Previous Topic   Next Topic Topic: New Control Structures for Java


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us