articles

still scheming away

In scheming_away I started exploring things and stopped somewhere in the middle. Strated with defining things as structures, then as a tree structure. Now comes a third attempt at the same height. Thank god I'm not competing.

Take 3, or coming back to structures


;a tuple is a structure with an id and a value
(define-struct tuple (id value))

;tuple + -> list of tuples
(define make-thing (lambda( head . rest)
  (map (lambda(x)
          (make-tuple 
            (car x) 
            (cdr x))) 
          (cons head rest))))

;just print the bleeding thing

scheming away

In yesterday's write-up I started touching scheme. It is part of my attempt to study the language. It might be a bit ambitious as a first "real" problem, though. So until I reach a solution for that, I will try and solve a few randomly selected different problems. Most of them will be something I already know how to say in other languages, the aim for most of them should be a cleaner solution. In the end I must prove to myself that it is worth learning scheme.

Today's problem

Things or the theory of anything
There were a lot of discussions going in the Drupal development circles around what is a node, what is a user, is a user a node, is a taxonomy term a node, etc... In Amsterdam a few of us were really impressed my anymeta by mediamatic, where everything is a thing.

scheming templates

I'm intrigued. You might have noticed that I like Lisp. Itellectually, that is. I don't really speak it. I finally decided to dive and try and learn it. On the surface it is not that hard - the language is extremely simple, essentially it has brackets and white space as separators, a couple of special forms - something like built in functions or language constructs in other language terminology, and a few really cool features like quote, unquote, quasiquote, (precious special forms actually), oh, yes, it has an eval.

In order to go forward with the learning I shall try and implement a simple web-design friendly template for xml applications. The idea is similar to TAL, or taglibs, etc...

Some ways to use saved state with closures in php

In a previous short post Idescribe a way to emulate closures in php. Using that technique execution environment, otherwise known as a call stack can be saved for future use. This can be put to good use. A couple of patterns or programming techniques could be useful in practice.

State pattern

A closure represents a state => implemenation of a state pattern. This is a bit rich. Usually in OO programming the state pattern is implemented by encapsulating different protocols, for denoted states. This is simple to implement by substituting your protocol specification with a different name. Drupal hooks are a good example implementation of this. The following is a simplisting example implementation of a state pattern based on closures. The last argument of the deduced function is the closure itself.


class function_object {
  var $scope;
  function __get($name) {
    return $this->$scope->$name;
  }
  function __call($name,$args) {
    $func =$this->$state."_$name";
    $args[]=$this;
    return call_user_func_args($func,$args);
  }
  function __constructor($scope) {
    $this->scope=$scope;
  }
  function __clone() {
    $this->scope = clone($this->scope);
  }
  function state($state) {
    $this->state=$state;
  }
  function call() {
    //the function body - do some work
  }
}

To save the state for future use, for example as part of an undo cycle:


  $saved = clone($closure);

Call/cc or call with current continuation in php

Closure effectively represent the future of computation. This means that we can say what we want to do, by where we are. Since php doesn't implement any call stack optimisation, the call/cc style of programming makes sense in a limited number of cases. To use this style of programming we need to redefine our functions to use the continuation

f(x,c) : c(f,x);
(var, continuation) -> continuation

and in php


//the function closure call method
...
function call($x, $continuation) {
$this->scope=$continuation; // emulate c(f,x)
...
do whatever you want here
}
...

OK, this is rather crude. In reality this is very limited - it is assumed that the function is defined in a 'global' scope, so we are putting it in some exhisting stack. It will be cleaner if the continuation implements the stack assignment, rather than rely on the function.

Emulating closures in PHP

In programming languages, a closure is an abstraction that combines a function and a special lexical environment bound to that function (scope). The variables in the lexical environment are designed to retain state information between function calls. Unlike garden-variety functions which retain no memory of what happened in previous calls, closures are capable of storing information across function calls.closulres in computer science (wikipedia)

PHP doesn't have closures as an element of the language. What can we do to emulate it?

We need to be able to encapsulate in one entity scope, state and execution. The most obvious candidate will be a PHP object.

With the introduction of the __get(), __set() and __call() magic functions for PHP classes, something the manual calls overloading, PHP opens the gate to transparently enhance a class to add variables and methods to an object's body. We can abuse the __get() to implemet nested scopes. The state is preserved as part of the object body. The default function (call()) is a protocol to add a uniformity of execution between different function objects.


class function_object {
  var $scope;
  function __get($name) {
    return $this->$scope->$name;
  }
  function __constructor($scope) {
    $this->scope=$scope;
  }
  function call() {
    //the function body - do some work
  }
}
If all $scope objects are function objects we get a closure emulation in PHP. This opens the doors to such fancy ideas as namespaces, modules et.al. This technique opens the possibilities for functional style programming techniques and idioms as delayed evaluation, continuation, ...

Update: I've added closures to my design patterns collection

Learning lessons from Lisp or patterns and languages in PHP

In Lisp and its dialects everything is a first class language construct, that is it can be evaluated and changed from within the language. This gives a few very powerful abstractions, which help in constructing short but still readable programs. There are a few very powerful patterns coming from this single concept.

A function is a first class variable. It can be assigned to.

This is directly applicable in PHP. Since the php symbol table is a big hash (roughly), you can access the function by it's name - for example: $func = 'a_function'; $var = $func();

A program is a data structure, a list, so you can manipulate it using the language

Relations and their domain structures

In this scribble I'll discuss an implementation of different topological structures, which can be used for indexing different "relation systems", for example trees for menus, book structures, etc... graphs for caching links between pages.

We can split the problem into two main subproblems. First, navigation and queries withing a single relation domain. For example local table of contents for a section in a book. Second is higher order or inter-domain queries. For example: given a node, determine the all related nodes, ordering them by their distance from the node, based on taxonomy, their position in a book(s), and their position in the site's "link web". We should be able to implement second and hier order based queries, based on the results of these two basic problems.

Powered by Drupal, an open source content management system