scheme

An exercise with continuations, prompts and scheme macros

control resumed inspired me to take a small exercise.

"Code a minimal approximation of the python yield operator based generators"
Here follow the results I managed to get with help from Matthias Felleisen, via the plt mailing list. You can see the non-edited exchange via the mailing list archives and control and macors. All control&prompt are forms specific to plt scheme's control.ss module. The first attempt looks something like this:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) (control resume-here (set! control-state resume-here) value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(step) (step) 

It does the job. Kind of. For me the interesting bit is how the interplay of prompt and control achieve maintaining the current state of execution before the return and allowing to continue from that interruption. It can be done with call/cc but it looks a helluva a lot more complicated and is far more unreadable.

There is a problem with the code above though. As Matthias notes in his email:

LESSON: never 'test' by running things at the top-level prompt. It IS a prompt. -- Matthias

So comes version 2:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) 
    (control resume-here 
             (set! control-state 
                   (lambda () (prompt (resume-here)))) 
             value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(equal? '(1 2 3) (list (step) (step) (step)))

control-state is a variable holding a reference to a function with no arguments, doing what the python function would do. yield is a variable holding a reference to a function which does the interrupt magic. generator is a variable holding a reference to a (sugary) function which does the initial step.

The logic of the above algorithm is roughly as follows - mark thy state, do what you need to do, when you encounter control stop, remember your state by wrapping it in a function (resume-here), remember where do you what to continue from ( the set! control-state ...). Notice that the value of control-state is replaced. This is possible since the resume-here continuation is a function and a first class value.

So what next. Boilerplate code is tedious to write. And there is a lot of boilerplate code there. And every function, which needs to follow this recipe, will need to duplicate it.

So scheme macros to the rescue. It is not a trivial problem. A 'generator' function can look something like this:

LISP cycles



from xkcd

macro processor - initial notes

Most of my work on this is on paper, and some code sketeches. There quite a few non-trivial issues, and hard decisions to be made. Since I have the knack of loosing or recycling the various paper bits lying around, I decided to keep at least some of them in my diary, aka this blog.

initial requirements

convenient syntax and semantics
convenience matters. The syntax should be obvious. The meaning of the syntax should be easy to grasp.
minimal core
the core of the macro processor should be minimal. This will help managing the code quality. The minimal core should be enriched using macros.
retargetable/multi-targets
using one and the same 'surface syntax' to produce different target code. It should be possible to have a one to many code generation. Example application - one definition producing javascript, php and sql code. Alternative example: one definition - three code targets - debug, deployment + a set of autogenerated tests
target and syntax agnostic
no assumptions should be made (at least at top level) about the target or syntax. We should be able to accomodate any theoretically parsable syntax, within reason, of course. Subject to parsing strategy selection, etc...

macros, higher-order functions, datatypes and design patterns

While reading, researching and experimenting for my macros project the terms in the title get mixed a lot. I'll try to summarise what is my understanding of a lot of the above. To be fair, most of these words are heavily overloaded with sometimes contradictory and or ovelapping meanings, so this short is only about my personal summary, no pretence for a general study or lit review.

Generic programming intuitevely corresponds to design patterns, or a tool to implement them. There should be a distinction between the functional or algorithmic side of the term and the structural or data (type) genericity.

Poor man's macro programming in php

Jonnay's post I mentioned before started me thinking - what do you need to have macros in php. What is the closest we can get to that without actually changing anything in php (poor man's version? What minimal sugar does php need to make it comfy? What is the natural syntax for macros in php? I definitely don't know the answers to these questions but let's try: macro delay() { match { delay( $func, ... ) } : { $varname = $func . random(); $$varname = array(new promise( $func, ... ), 'evaluate'); return $varname; } match { $func( ... ) } : { return call_user_func($$varname, ... }; } }

This looks kind of allright, phpish. It has problems, but the above dream code demonstrates the idea enough - match the left-hand-side code and substitute it with the right hand side. The difference from C macros is that this macro is a program fragment/function/..., the result of which is substituted in the AST, as opposed to simple string pattern matching + substitution

Googles Summer of yawn.

Googles Summer of yawn. - Google's "Summer of Code" has started and they have announced a few PHP projects. Some of them look interesting and useful. However, I am going to pick apart one in particular, that to be honest, looks neither interesting or useful: The PHP Macro Preprocessor.
....

Why does the PHP Preprocessor need to be stuck in a world of #ifdefs and #includes? Instead of blindly copying what the C preprocessor does, why not focus on the languages strengths and deficiencies? The object system of PHP needs to be looked at, and see if it can be improved upon through a method of code transformation.

[sacrificial rabbit]

I sooo totally agree with Jonnay on this. In fact it is simply like reading my own thoughts, just put it better english, , ok, nearly. But what to do about it? I don't really know, I'm afraid I chicken out from digging into the guts of php. When I last looked there it was really scary.

LISP-like programming in php

My obsession with things schemish and lispish and having to use php on a daily basis leads to the usual comparison and how would I do this in ... style questions. So here comes another go at how would I program lisp style in php. How much is possible? What is possible? Mind you not everything is really useful or the best way to do it. It is just an intellectual excersise, a study on using some of the php'f features to program in not a typical php (imperative) style.

the compulsory conses, car, cdr in php

Well for the benefit of non-lispers I will use head and tail instead of car and cdr respectively.

Lisp without Parenthesis

Well it’s impossible to remove all of the parentheses in Lisp, ..... One alternative to parentheses is being sensitive to white space, in a way that is reminiscent of Python. Lisp without Parenthesis

A good post, which goes along the lines of what I'm playing with as well. He (Peter Schombert) suggests using \ as line continuation mark, which is in line with tradition. I would probably prefer it in the end, as opposed to the beginning of a line, but that's sugar.

I wonder, how hard it would be to add such a language extention to mzscheme.

Me being a noobie, I haven't had a clue that there is an SRFI, which implements that already.

a sample testsuite for the (any/type) base types

Here comes a sample test suite (it is too long, so only the beginning features in here) for the any/types, I described earlier. I like the clenliness of the schemeunit library. It features a rich set of assertions, simple but powerful grouping and both text and gui result interfaces. In order to use it you need plt scheme. Then you can grab the unit test suite from planet:
(require (planet "test.ss" ("schematics" "schemeunit.plt" 1 2)))

The code here shows testing only the any/text type and all relevant auxilary functions, using this datatatype. Looking at the code, it could be turned into a macro, so we could generate type tests automatically, rather than writing this long code..

scheming anything/anytype - creating base types experiment

This is an experiment to some 'atomic' types in scheme. It was tested only in plt scheme.

The basic idea is that we need some 'atomic' types, from wich to construct everything else in a web cms - users, content nodes, etc... The base field types defined here are - text, stext (short text), date, integer and float.Each field type is a closure, in which some properties, getters, setters and type-checkers are defined.

To define a new field type use the make/any/type macro. In the second part of this code snippet you will find a series of type definitions and helper functions. I quite like how this looks in scheme. I'm surprised actually. This ended up as a very cute OO-like code.

Powered by Drupal, an open source content management system