Logic programming on the JVM

Just a quick post (the time is rather late) to note that my port of the Mini Kanren logic programming system to Scala is now available for download (and bug reports) on GitHub; for the scaladoc API documentation and a presentation discussing the porting effort, visit the project homepage.

It has an almost-complete numerical stack — the missing arithmetic relations are not coded yet because I was documenting and/or getting larger test cases to work — and likewise with list-processing support. The years-old stack overflow problem I initially attributed (when taking a programming language course, and having no time to debug thoroughly) to Java’s lack of TCO turns out to be fixable by some judicious call-by-name optimizations.

Having just discovered metalua and its macro goodness, I’d say that after bringing Kanren to the JVM, the next step would be to have a C-embeddable Kanren written in metalua. There might be some performance snags, though — the Scala port is currently about 3x slower than Mini Kanren running on Petite Chez Scheme.

Technorati Tags: kanren, mini-kanren, functional, logic, programming, lua, scala

OOP in Lua: abstract methods

I discovered Python’s delightful abc module (introduced in PEP 3119) a while back, and have been wondering how a similar functionality could be introduced to other dynamic languages (e.g. Lua and Ruby).

Being more familiar with the former, over the weekend I decided to try and write an equivalent module. Two problems came to mind:

• Python uses an @abstractmethod decorator to mark an otherwise-normal function definition. While a decorator pattern can be used in Lua (though not a standard practice), this Python decorator works by setting an attribute in the function it decorates:
  

  funcobj.__isabstractmethod__ = True

  This is not an option in Lua, because functions don’t have individual metatables.

• Python has a standard way of doing OOP, and the enforcement that an instantiated class does not contain any abstract method is done in the __new__ method of the ABCMeta metaclass. Contrast to Lua, where OOP is normally done in an ad-hoc manner — and even the LOOP library provides several OOP inheritance mechanisms.

The solution I adopted is delightfully simple: the abc module provides two functions: an amethod function that throws an exception no matter what arguments it is passed, and a verify function that takes a classname, and reflects on the members (using loop.cached.allmembers if possible, falling back to pairs if loop is not installed) and check if any of them is equal to amethod.

This works even on simple tables, though it shifts the responsibility a bit to the programmer: unit tests should be used to verify each created class. As a fallback, attempts to use the abstract methods will fail at runtime, but that’s taking dynamism a bit too far…

Still working out how to get the Pythonic behavior (instantiating a class with some abstract members should fail) when using LOOP. Meanwhile, try it out for yourself and make sure to file bug reports!

Technorati Tags: lua, python, oop, abc, abstract-methods, virtual-functions, interfaces, traits

[PYTHON] Find of the day: B+ Tree-based lists

I was looking at implementing Clojure’s persistent data structures on other languages — being able to assume that collections are immutable make writing concurrent programs much easier, since these collections can be shared without locking.

While looking if this has been done before, I came across a rejected Python Enhancement Proposal:

The common case for list operations is on small lists. The current array-based list implementation excels at small lists due to the strong locality of reference and infrequency of memory allocation operations. However, an array takes O(n) time to insert and delete elements, which can become problematic as the list gets large.

This PEP introduces a new data type, the BList, that has array-like and tree-like aspects. It enjoys the same good performance on small lists as the existing array-based implementation, but offers superior asymptotic performance for most operations. This PEP proposes replacing the makes two mutually exclusive proposals for including the BList type in Python:

1. Add it to the collections module, or
2. Replace the existing list type

It is currently rejected, but could be added to the collections module if there is sufficient outside interest. This is not quite the immutable vector from Clojure, but close enough: one merely needs to subclass it, and modify the setters (__setitem__, __setslice__, etc.) to first copy the collection and then operate on the copy. Copy-on-write ensures that only the changed leaf is actually copied, plus the internal nodes on the path leading to the leaf.

I’ve packaged this for Fedora (review request). Anyone cares to review it?

Technorati Tags: fedora, linux, python, data-structures

Dear Interweb: Incremental improvement to credit/debit card security?

2009-10-06|11:30:07|12.34Many of us have fallen victim to credit/debit card fraud, either through operators illegally collecting the numbers of the cards they handle (the small fries) or through crackers breaking into credit card databases.

The question is: short of totally overhauling the system, is there any way security could be improved?

My (preliminary) ruminations on the topic yields the following:

Pre-authentication
For customers who opt-in, require texting the transaction amount (optionally +/- a given amount) for transaction (esp. above a certain amount) to be approved. Problem: SMS is not a secure medium. Using a smartphone, one could get around this (but then the proportion of customers covered will be much smaller), but given that data connectivity is not common (esp. in US and Asia), we’d still be limited to SMS.

If we care only about authentication, the cleartext plus its PGP signature would fit inside 160 chars, but if one wants to encrypt the content as well, it’s not possible.

e.g. for the cleartext

2009-10-06|11:30:07|12.34

(the timestamp is needed to prevent replay attacks. Yes, this is obviously not secure enough still, but the example is to illustrate the transmission size problem).

Signed, the signature takes 104 bytes. Plus the 26 bytes of the message, and a token separator, we get 131 bytes, within the limits. But what if the message is to stay private as well? Using GnuPG, I get a message size of 625 bytes. This could be split into multiple SMSes, but it’s not convenient.

Post-authentication
Have the card issuer send an SMS *after* an authorization request is received. We still have the transmission size problem above, but the issuer can choose to transmit less sensitive information — e.g. rather than the amount, transmit the merchant identifier. Still a privacy problem, and this will obviously not be popular on a busy check-out line. Also has the problem that to make it secure, you’d need a smartphone (to either decode the message, or verify the signature).

Secret code
There already are security mechanisms asking for the CVV/CVC code. Make it ask for a secret number instead, one that is settable by the customer.

But above all…
Raise the base level of authentication required! Some online vendors like Amazon still do not even verify the billing address (which is convenient, if one’s card is issued in a country like Indonesia, where for some reason address verification *never* works, but scary. Though, funnily, I haven’t gotten any card misused on Amazon. I *did* have one stolen card used on iTunes, so Apple’s authentication is obviously comparably weak).

Any other idea I’m missing, or any problem with the three schemes above that I have not noticed, let me know (comment or trackback) and I’ll update the post. Thanks!

Technorati Tags: banking, cryptography, security

Wordling this blog

Technorati Tags: visualization words