All 4 entries tagged Programming

View all 120 entries tagged Programming on Warwick Blogs | View entries tagged Programming at Technorati | There are no images tagged Programming on this blog

August 29, 2008

Program Design

There are certain general precepts of program design that are quite general in nature, for example attempting to separate different components of a program away from each other so that if one needs to make changes to one component it only affects that component and not the whole program. A similar property that can be generally considered good design of a library is to reduce bugs in the usage of the library. The specific manner in which one implements these issues is quite specific to languages.

MissingPy is a library that aims to provide libraries missing from the Haskell standard libraries, by implementing a low level python binding and also some specific bindings on top of it. It seems to be relatively incomplete, and also implements things that are now part of Haskell – but the concept of giving an easy binding to python libraries offers general utility.

I was playing around with said bindings the other week, which caused me some frustration due to what I perceive as poor library design. The libraries themselves have a function called py_initialize, that it is necessary to call before any calls into the interpreter bindings are made. The unfortunate behaviour of this library is to segfault programs that call other methods before calling py_initialize.

Were one to implement this in an object oriented language a possible idea would be to have an interpreter class – and force initialization in the constructor. That way any execution of python code by your bound interpreter instance would have to occur after the interpreter had been initialized.

Unfortunately the translation of these concepts into Haskell was highly procedural in nature. ie one had to call the py_initialize – or be damned if they were foolish. This may be an appropriate choice in something like C – but not in a high level, strongly and statically typed language such as haskell. There are several viable solutions that I can think of – I strongly encourage readers to offer their own.

The simplest solution would be to have py_initialize return a value, that must be passed as an argument to other functions. One could export the type of this value from the module but not its constructor. This would ensure that any user of the module didn’t screw themselves (as I did 4 times in 35 minutes) by only allowing them to call the other function with this as an argument. Unfortunately – passing around immutable tokens in order to enforce security is a little bit ugly, it increases the length of the argument from every function, and is incredibly imperative. It also fails to hide the internal security of the module from the user.

An alternative, that I believe would be better, would be to introduce a new monad, that we shall call PY. Any function that involves a call to the interpreter would need to be in the PY monad. One would replace the py_initialize function with a runPY function that promotes oneself from the IO monad to the PY monad, and initialization could be performed here, thus statically ensuring that this module didn’t combine with my stupidity to cause my test code to segfault.

My point here is that idioms from different paradigms to the same basic problem can frequently be translated into alternative programming languages, but are unnatural in such a setting – resulting in errors that one wouldn’t otherwise expect. Yesterday Faux asked me if I felt programming for another 10 years would genuinely make me a better programmer. I cannot help but answer yes, there are plenty of things that I didn’t know 10 years ago, when I started programming, and plenty of things that I still haven’t figured out yet (list to be supplied on demand). The fact there will inevitably be new languages, new language features, new approaches and new idioms during that period means that I will need to understand solutions to existing problems, that I don’t yet know of. Norvig suggests I might have already reached competency – I hope that is right, but if you stop at competency you have already lost the game (as everyone reading this sentence has).


April 30, 2008

Weak Typing vs Weak Testing

I haven’t written a blog post on anything vaguely related to Computer Science in a while, so here’s an effort to change that. Bruce Eckel (BE) wrote a noted entry a while back, which seems to have been heavily discussed in what the guardian would refer to as the ‘blogosphere’, I’m thinking the kind of inflamatory and inaccurate articles that get posted on prc (not to say there aren’t good articles, but I find it increasingly difficult to sieve for something new and interesting these days).

I don’t intend to discuss BE’s terrible misconceptions that are perpetuated by this article, for example his reference to C++ as strongly typed, or blame him for not fixing the myriad of problems that the language has, after all standards bodies are mirred in backwards compatibility issues and compromise. I will blame him for the link to his blog not working, but thats another matter entirely.

What I really want to discuss is the limits of testing. Thats not to say that testing software isn’t a crucial part of the development process, and has helped me to find numerous bugs in software that I’ve written over time, but it has its limits. Now I’m not talking about expressiveness here – its plainly apparent to me that a test written in a turing complete programming language can test any property of the program that a decidably complete type checking algorithm can. Thats not really an idiomatic approach to testing unfortunately, since once one writes a test that is harder to reason about than the computer program they are trying to debug they have got a problem trying to test their test harness. I’ve numerous times found that the mistake was in a testcase, or harness that I’d coded up rather than the program itself.

A considerable number of unit tests are of a very simple form, for example testing that the sum of the numbers in the list [1,2,3,4] is 10. This is to be encourage and is all well and good. Unfortunately the problem occurs when one tries to extend these simple test cases to check complex properties. Let us imagine we are trying to write a function that sums up some numbers in a list, and we want to be confident that this function terminates. This is a trivial problem that I find it hard to think of how to test. Let us consider the following implementation, written in ML.

fun sum [] = 0
    | sum (h :: t) = h + sum t;

I can be highly confident that this function terminates because I am using primitive recursion. This is a highly important approach in the development of usable theorem provers, for example the Isabelle theorem prover automatically generates proofs of termination for functions that are defined using primitive recursion. It is also easy to see how one would construct such a proof informally for this function:

1. Base Case: the list is empty so Its sum is 0. Statement holds true vacuously.
2. Inductive case: we have a list of length n. We assume that the sum of a list of length n-1 terminates and we know the addition function takes a finite amount of time to compute. Thus conclude that summing a list of length n terminates.

This is pretty much a trivial case for any primitive recursion function in ML. Our type checker helps us here – case exhaustiveness is checked for the function’s domain, in case we forget any possible cases. This may seem trivial for this function – but its incredibly useful. For example if one is writing an interpreter based on an IR composed from a union type of different datatype constructors for different IR elements.

I find it hard to convince myself that the python (chosen because of Mr. Eckel’s rampant fanboying) equivalent terminates. I have implemented the function like this:

def sum(l):
  total = 0
  for i in l:
    total += i
  return total

I don’t know where to begin in formulating a testcase to check termination. If someone does – then please comment on this blog, I’d really like to know if its possible.

A quick superficial glance would suggest that the foreach loop used here would allow me to conclude termination, but unfortunately it only return iterable items. Here’s an example:

def inf():
  i = 0
  while(True):
    i = (i + 1) % 100
    yield i

print sum(inf())

I can’t use static type checking to ensure that the parameter is a List unfortunately. I could add a decorator with explicit type checking, but unfortunately this can simply be monkey patched away. Similar problems exist if I choose to write this function in Java. For example:

int sum(Iterable<Integer> entries) {
    int sum = 0;
    for (Integer i: entries) {
        sum += i;
    }
    return sum;
}

Since one could implement an iterable that always returns true. This can be resolved in Java (I think) through the following changes:

1. Write your function like:

int sum(ArrayList<Integer> entries) throws Exception {
    if(entries.getClass() == java.util.ArrayList.class) {
        int sum = 0;
        for (Integer i: entries) {
            sum += i;
        }
    return sum;
    } else {
        throw new Exception("Might not terminate since you are using a subclass of ArrayList"); 
    }
}

2. Use a custom security manager in order to ensure that system classes have been replaced.

This has obvious disadvantages – for example if one later decides that you want to use a LinkedList or a Vector. It also assumes that no one has replaced the system classes files (e.g. rt.jar) with miscreant ones. Though obviously that could be checked using the Class Data Sharing parameters. All in all – its a massive bunch of hacks that one doesn’t want to be forced into doing just to be convinced that a damn sum function terminates!

So here’s an open challenge – can anyone convince me that they can write a simple sum function in a weakly typed language (static or dynamic) and be sure that it terminates. If you can do it via testing then its bonus points! Either way you get my respect. Note that this is my definition of weakly typed languages – anything with a type system with more loopholes/problems/lack of expressiveness in than ML is weakly typed.


June 09, 2007

Pro C is Pro

There was a discussion of how to lock down the compsoc gaming account, such that programs such as firefox couldn’t simply execute arbitrary files which they have downloaded. A suggestion brought to the table by Bucko & Fred was to simply use LD_PRELOAD to stop the necessary syscall being made. So after failing at tower defense and hero defense until gone 4am, I felt like trying something which firstly seemed to suit my skillset better and also achieve something more productive. The whole thing worked within about 20 minutes, which I attribute to google and C being quite good for this kind of thing. Here’s some code:

#include <stdio.h>

int execve(const char *filename, char *const argv [],char *const envp[]) {
printf(“in your syscalls, stopping your execs\n”);
return -1;
}

If you want to compile this, try pasting into ‘noexec.c’ and then running …

gcc -fPIC -shared -o noexec.so noexec.c

... now, compare the output between …

bash -c ‘exec ls -l’

... and …

LD_PRELOAD=./noexec.so bash -c ‘exec ls -l’

Realising how easy that was, brings many possibilities to the table, and I’m sure someone else has done them before, but its open my eyes somewhat.

a. dtrace implemented in userspace
b. implementing a security manager, similar to the one java has, but for arbitrary executables
c. hilarious comedy
d. FUSE in userspace (Bucko suggested this and he’s bloody right – does FUSE need to be a kernel module?)


January 19, 2007

Javac

This week’s Xing (I nearly called it bugflug) will probably be trying to fix stuff on the compsoc website. This should be nice and accessible stuff that has obvious benefit to people. But, I am still interesting in running some more ‘exotic’ projects, so I thought I would air some thoughts on the proposed collections operations to be implemented in Javac, which I hope to work on again with Lamby and maybe more people if they are interested.

The essential idea of the for .. do loop is to be a variant of the map higher order function that can be found in both functional languages such as Ocaml and dynamic languages like Python. So the basic idea that was proposed last week was:

for do

Where the expr evaluates to a collections object. For example the following conversion would occur in Javac:

for this.list do m;

becomes

List newList = new Vector ;
for(ListElementType element:this.list) {
newList.add(m(element));
}
this.list = newList;

This conversion happens with the safety condition that the method m takes one parameter of type ‘ListElementType’ and its return type is of the same type, where ListElementType is the type of element’s of this.list. Some implementation effort has gone on with this idea, and I think it would be possible to finish it at the next LAN with some concerted effort and thought.

I was thinking the other day of some extensions to this basic syntax, for example by adding multiple parameters, so that:

for this.list1 this.list2 do m;

becomes

if(this.list1.size() == this.list2.size()) {
List newList = new Vector ;
for(int i = 0;i newList.add(m(this.list1.get(i),this.list2.get(i)));
}
this.list = newList;
}

Obviously this would be implemented for n number expressions, rather than just two. Similar safety conditions apply as the first example. The primary issue that I can think of is that one of the safety conditions has to be checked at runtime, which doesn’t really fit into Java’s paradigm.

There would also be the potential for adding non-list parameters to such a construct, that would be passed to every method call. For example:

for this.list this.variable do m

becomes

List newList = new Vector ;
for(ListElementType element:this.list) {
newList.add(m(element,this.variable));
}
this.list = newList;

Such things obviously add more complexity to java, but I think for very commonly used syntactic forms such as this, it might be a good idea to have such a construct.


January 2022

Mo Tu We Th Fr Sa Su
Dec |  Today  |
               1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31                  

Search this blog

Tags

Galleries

Most recent comments

  • Apart from the plea "can I have your old one?" (the yearning never diminishes) I'd like to leave you… by Sue on this entry
  • Unfortunately I still haven't seen a film for which you have to read up on quantum mechanics as I mi… by Sue on this entry
  • I've never been to watch a film before when it's been recommended that you first read up on quantum … by Sue on this entry
  • Well this is very interesting, i really liked reading this blog, this was very informative and very … by Mio Navman Spirit S300 on this entry
  • I thought it was fascinating. Griffin isn't like any other, media–trained, polished politician, and … by Tim on this entry

Blog archive

Loading…
RSS2.0 Atom

Hello

Not signed in
Sign in

Powered by BlogBuilder
© MMXXII