Archive

Posts Tagged ‘Programming Languages’

defaultdict() and memoization

June 11th, 2012 Comments off

After the previous post, it came across me that member_missing can be used to implement something like Python’s defaultdict. So I thought it’s interesting to code up an example leveraging this ability.

You know the fibonacci calculating algorithm right? This is the fibonacci code (except written in Bike, not Java) that I use to teach my students about recursion in an entry Java programming course:

var fib = func(n) {
  n < 2 ? 1 : fib(n-1) + fib(n-2)
};

Clean and simple! A base case on the left expression of the ternary and a recursive case on the right. Probably among the best to introduce people to the concept of recursion. What I didn't tell my students is that this is extremely inefficient. Pick fib(30) for example. It will invoke fib(29) + fib(28). fib(29) in turn invokes fib(28) + fib(27). Notice something? No? Read again? Still no? fib(28) is executed twice. And this is just the top part of the call tree. As you go down further, this phenomena is phenomenal, i.e. fib(27) is invoked tree times, fib(26) four times and so on! Needless to say, your CPU won't be very happy. Enter memoization.

In a nutshell, we use memoization as a technique to cache result of previous invocations. Assume the function has no side effect (i.e. being idempotent), which should generally be the case in a functional language, we can later reuse the cached result should the function is invoked again with the same arguments. Here's the code to compute fibonacci making use of memoization technique (and member_missing, as defaultdict).

func memoize(f) {
  var cache = {
    member_missing: func() { null }
  };
  return func recur(n) {
    cache[n] || (cache[n] = f(recur, n));
  };
}

var fib = func(n) {
  n < 2 ? 1 : fib(n-1) + fib(n-2)
};

var m_fib = memoize(func(recur, n) {
  n < 2 ? 1 : recur(n-1) + recur(n-2);
});

load 'stopwatch.bk';
var watch = Bike.Stopwatch.create( ).start( );
println('fib(20) = {0} (elapsed: {1}ms)', fib(20), watch.stop());

watch.reset().start();
println('m_fib(20) = {0} (elapsed: {1}ms)', m_fib(20), watch.stop()); 

Run the code and you should notice a significant difference between the run time of the normal fibonacci and one with memoization.

New feature in Bike: member_missing

June 11th, 2012 Comments off

I always like the ability of objects to dynamically respond to a message without having an explicit binding. Something like method_missing in Ruby or DynamicObject in .NET. It would be great for Bike to have that capability. Fortunately, adding this feature was much easier than I thought, thanks to how the interpreter code was already laid out. Please join me welcoming member_missing in Bike! Let’s examine this feature more closely, shall we?

var obj = {
  member_missing: func(name) {
    return "Member: {0}".with(name);
  }
};

println(obj.notExist); # Member: notExist
println(obj.has_member('notExist')); # False

The code above creates an object and defines the special member_missing method, which will be invoked by the runtime whenever it can’t resolve a member. Therefore, when trying to access notExist, methodMissing is invoked with the member name as its only argument and has a chance to decide what to return. In this case, it returns a string showing what member was being accessed.

This works for method invocation as well. When the interpreter attempts to invoke a method, the first thing it does is resolving the method object (Bike.Function) before invoking it. Therefore, member_missing can also do its magic here by returning a method that the runtime will instead invoke.

obj = {
  member_missing: func(name) {
    if (name == "add") {
      return func(a, b) { a + b };
    }
  }
};

println(obj.add(1, 2)); # 3

You see, Bike’s member_missing doesn’t behave exactly like Ruby’s method_missing. I could modify the runtime to instead of invoking the function returned by member_missing, it will invoke something like method_missing (Bike edition!) and pass in the call information (e.g. name, arguments). Maybe that what I should have done for efficiency sake (i.e. avoid creating a function every time!). Then again, maybe later, one thing at a time, eh. For now, those who care about a bit of efficiency here and there, you can cache the generated method, as follow.

obj = {
  member_missing: func(name) {
    if (name == "cache") {
      return this.cache = func() {};
    }
  }
};

obj.cache();
println(obj.has_member('cache')); # True

The next time obj.cache() is invoked, member_missing() isn’t invoke anymore because an explicit binding already exists.

Now, a more interesting example demonstrating the power of member_missing. If this somehow reminds you of RailsActiveRecord, you’re right.

var db = {
  member_missing: func(name) {
    if (name.starts('find')) {
      return db[name] #! cache it !# = func(obj) {
        var sql = 'SELECT * FROM {0}'.with(name.sub(4).upper());
        obj.members(false, true).each_with_index(func(name, index) {
          sql += (index == 0 ? ' WHERE ' : ' AND ') +
                 name.upper() +
                 (obj[name] is Bike.String ? '' : '=') +
                 obj[name]
        });
        println('Executing...{0}{1}', NL, sql);
        return [#! Suppose I'm a product array, yay! !#];
      };
    }
  }
};

# SELECT * FROM PRODUCTS WHERE CATEGORYID=1 AND PRICE>1000
var products = db.findProducts({categoryId: 1, price: '>1000'});

Interested? Have Bike up and running and start hacking. The examples above can be found in GitHub.

Bike has a homepage!

May 3rd, 2012 Comments off

Had some fun with Python

May 1st, 2012 Comments off

By now, you should have already known I love programming languages, to the extent that I even created one myself. One of the languages I want to learn this year is Python. My first Python program is a port for the Semicolon language. The code is also available in github with examples.

# coding: utf-8

def tokenize(code):
	import re
	ops = {
	  ';;;':  { 'code': 'push', 'arg': 'signed'},
	  ';;⁏':  { 'code': 'dup' },
	  ';⁏;':  { 'code': 'swap' },
	  ';⁏⁏':  { 'code': 'discard' },
	  '⁏;;':  { 'code': 'add' },
	  '⁏;⁏':  { 'code': 'sub' },
	  '⁏⁏;':  { 'code': 'mul' },
	  '⁏⁏⁏':  { 'code': 'div' },
	  '⁏  ':  { 'code': 'mod' },
	  '; ;':  { 'code': 'store' },
	  '; ⁏':  { 'code': 'retrieve' },
	  ' ;;':  { 'code': 'label', 'arg': 'unsigned' },
	  ' ;⁏':  { 'code': 'call', 'arg': 'unsigned' },
	  ' ; ':  { 'code': 'ret' },
	  ' ⁏ ':  { 'code': 'jump', 'arg': 'unsigned' },
	  ' ⁏;':  { 'code': 'jz', 'arg': 'unsigned' },
	  ' ⁏⁏':  { 'code': 'jn', 'arg': 'unsigned' },
	  '  ;':  { 'code': 'exit' },
	  '⁏ ;;': { 'code': 'outchar' },
	  '⁏ ;⁏': { 'code': 'outnum' },
	  '⁏ ⁏;': { 'code': 'readchar' },
	  '⁏ ⁏⁏': { 'code': 'readnum' },
	}
	
	make_int = lambda str:int(''.join('0' if c == ';' else '1' for c in str), 2)
	while code and code != '\n':
		has_match = False
		for key in ops:
			pattern = (key + (r'([;⁏]*)\n' if 'arg' in ops[key] else '()') + r'(.*)$').decode('utf8')
			match = re.match(pattern, code, re.S)
			if match:
				has_match = True
				code = match.group(2)
				if 'arg' in ops[key]:
					if ops[key]['arg'] == 'unsigned':
						tokens.append([ops[key]['code'], make_int(match.group(1))])
					elif ops[key]['arg'] == 'signed':
						tokens.append([ops[key]['code'], 
									   (1 if match.group(1)[0] == ';' else -1) * make_int(match.group(1)[1:])])
				else: tokens.append([ops[key]['code']])
		if not has_match: 
			raise Exception('Unknown command')

def step():	
	global pc
	op = tokens[pc][0]
	arg = None if len(tokens[pc]) == 1 else tokens[pc][1]
	pc += 1
	if op == 'push':
		stack.append(arg)
		step()
	elif op == 'dup':
		stack.append(stack[-1])
		step()
	elif op == 'swap':
		stack[-1], stack[-2] = stack[-2], stack[-1]
		step()
	elif op == 'discard':
		stack.pop()
		step()
	elif op == 'add' or op == 'sub' or op == 'mul' or op == 'div' or op == 'mod':
		bin_ops = { 'add': '+', 'sub': '-', 'mul': '*', 'div': '/', 'mod': '%' }
		stack.append(eval(str(stack.pop()) + bin_ops[op] + str(stack.pop())))
		step()
	elif op == 'store':
		heap[stack[-2]] = stack[-1]
		stack.pop(); stack.pop()
		step()
	elif op == 'retrieve':
		stack.append(heap[stack.pop()])
		step()
	elif op == 'label':
		step()
	elif op == 'call':	
		call_stack.append(pc)
		jump(arg)
	elif op == 'ret':
		pc = call_stack.pop()
		step()
	elif op == 'jump':	
		jump(arg)
	elif op == 'jz':
		if stack.pop() == 0: jump(arg)
	elif op == 'jn':		
		if stack.pop() < 0: jump(arg)
	elif op == 'exit':
		sys.exit()
	elif op == 'outchar':
		print chr(stack.pop())
		step()
	elif op == 'outnum':
		print str(stack.pop())
		step()
	elif op == 'readchar':
		stack.append(ord(sys.stdin.read(1)))
		step()
	elif op == 'readnum':
		stack.append(int(sys.stdin.readline()))
		step()
	else: raise Exception('Unknown opcode')

def jump(label):
	global pc
	for index, token in enumerate(tokens):
		if token[0] == 'label' and token[1] == label:
			pc = index
			break
	step()
		
import sys
if len(sys.argv) == 2:
	tokens = []; pc = 0; heap = {}; stack = []; call_stack = []
	tokenize(open(sys.argv[1], 'r').read().decode('utf8'))
	step()
else: print 'Usage: python semicolon.py [file.sc]'

The Bike Programming Language

February 19th, 2012 6 comments

Bike is a programming language that I develop.  I worked on this interesting toy project a while ago.  I was hoping to have had time to improve it further (plenty of things I want in a language) before announcing it in my blog.  However, work at my new startup has been so hectic (surprise, surprise…) that I can hardly find time to continue, so I guess I just put it out to the public and get everyone’s opinions.

In a nutshell, Bike is an interpreted language running on Windows and Mac/Linux (via Mono).  I developed Bike with the intention of building a language feel most natural by me so that I can use for daily programming tasks.  And since the existing languages that already feel natural to me are Ruby, JavaScript and C#, no surprise that these languages influenced Bike a great deal.  From the language perspective these are the important characteristics of Bike:

  • Dynamic and strong typing
  • Everything is an object
  • Prototypal inheritance
  • First-class function
  • CLR interoperability

No further ado, here’s some Bike.  First, hello world.

print 'Hello, world!'

Everything is object (note that the print function is passed as argument)

10.times( print );
0.upto( 10, print );

Calculating Fibonacci (return keyword is optional, semicolon is optional in the last statement of a block)

func fib( n ) {
    n <= 2 ? n : fib( n - 1 ) + fib( n - 2 )
}
print( "n: " );
var n = readln();
println( fib( n.to_number() ) );

Self-executing function

( func() {
    println( 'executed' );
} )();

Closure

var f = ( func( a, b ) {
     var c = 1;
     return func() { a + b + c };
} )( 2, 5 );
println( f() );

Currying

Bike.Function.curry = func( *args ) {
	if ( args == null || args.size() == 0 ) return this;
	var me = this;
	return func( *more ) {
		if ( more != null )
			args.add_all( more );
		me.call( this, *args );
	};
};

func add( a, b ) { a + b }
var addTo2 = add.curry( 2 );
println( addTo2( 3 ) );

add = add.curry( 2, 3 );
println( add() );

Var-args and array expansion

func add_all( *numbers ) {
    numbers.reduce( 0, func( current, ele ) { current + ele; } );
}
println( add_all( 1, 2, 3 ) );
println( add_all( 1, 2, 3, 4 ) );

var arr = [ 1->10 ];
println( add_all( *arr ) );

Inheritance

var Person = {
    initialize: func( name ) {
        this.name = name;
    },
    to_string: func() {
        this.name;
    }
};

# clone person and invoke initialize on the new obj
var buu = Person.create( 'Buu' );
buu.fav_language = "Bike";
buu.to_string = func() {
    this.super( 'to_string' ) + "'s favorite language is " + this.fav_language;
};
println( buu );

.NET Interoperability

var list = System.Collections.ArrayList();
[ 0->9 ].each( func( i ) { list.Add( i ); } );

for ( var e in list ) print( e + ', ' );

0.upto( list.Count, func( i ){println( list[ i ] );} );

Dynamic code evaluation

var code = 'println( "This is cool!" );';
exec( code );
code = '2 * 3;';
println( exec code );
code = 'var person = {name: "John"};';
println( ( exec code ).name );
println( person.name );

There are more interesting features, but I guess that’s enough for you to get a feel of Bike. if/else/while/for/switch/rescue are all available but they are probably not needed much.  Bike also comes with a minimal base class library to work with file system, multithreading, HTTP, JSON, regex, unit test etc.  All these are written in Bike itself (mostly .NET wrapper since it’s fast to implement although pure native implementation would be interesting).

Go to https://github.com/buunguyen/Bike and check out the samples folder for more.  Interested?  Fork and contribute to the language and/or base class library.  Questions, ideas and feedback, please comment or email (see About).  Thanks and happy biking!

Overview of C# 4.0

November 13th, 2008 7 comments

Note: This article is also posted at The Code Project. Refer to this link. There are quite interesting discussions going on there.

The .NET framework 4.0 CTP has just been released and I think it’s a good time to explore the new features of C# 4.0. In this post, I will introduce about the following features: dynamic lookup, generics covariance and contravariance support, optional and named parameters.
Read more…

Steve Yegge on the Next Big Language

February 13th, 2007 Comments off

What Steve Yegge considers the Next Big Language.  Sound like

  • Ruby + (Java || C# 1.x/2.0)
  • (JRuby || Groovy || Ruby.NET) + good_tools (esp. IDE)
  • C# 3.0 && dynamic_typing (not just type inference) && more_syntactic_sugar (return multiple values, object-literal syntax for hashmap etc.)

The Senior X-Language Developer

January 12th, 2007 4 comments

Lately, I’ve seen some job posts in the local newspapers which seek for senior .NET developers and senior Java developer who have at least 4 years of experience in .NET/Java, and feel a little bit dissatisfied with them. Read more…

Script#

January 5th, 2007 2 comments

Now, they even make a C#-2-JavaScript compiler, besides the GWT on the Java space. Guys, the next step is to completely eliminate all JavaScript we have to write, including those embedded in the HTML pages, port as many JavaScript libraries to .NET and Java as possible and vice versa, and make those libraries browser-independent. The point is to make JavaScript and its infamous browser-incompatibility problem completely transparent from application developers. By doing that, developers do not have to care about JavaScript any longer and it will become the machine language of the browsers. I do not care about the machine code since the appearance of Java and C#, neither do I want to care about JavaScript if you guys decide to generate it from Java/C#.