Skip to main content

Learning by doing

About a year ago I read a programming post by Peter Norvig: (How to Write a (Lisp) Interpreter (in Python)), being a Python programmer, of course I had to try write my own Lisp interpreter as a way to learn lisp.

My implementation is relatively short, but can do some surprisingly complex things like this Y Combinatorial Factorial from wikipedia (which is one of my unittests):

(begin 
(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (v) ((x x) v))))
     (lambda (x) (f (lambda (v) ((x x) v)))))))

(define fact
  (Y (lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))))

(fact 10)
)

I've recently dug up the files, rinsed them off, and put them on my bitbucket account. The reason I took another look at this project was my desire to translate it with Pypy. After having to battle just to get the tokeniser into valid RPython to translate I've put that on the backburner for now.

I learnt a surprising amount of functional programming "tricks" and techniques that apply equally to Python as to Lisp. As when I started learning Haskell, I grew more as a programmer and most importantly had fun!

Now I see Norvig has posted a follow up lispy2 so I'll have to read through it carefully to learn some more gems.

Popular posts from this blog

Bluetooth with Python 3.3

Since about version 3.3 Python supports Bluetooth sockets natively. To put this to the test I got hold of an iRacer from sparkfun . To send to New Zealand the cost was $60. The toy has an on-board Bluetooth radio that supports the RFCOMM transport protocol. The drive  protocol is dead easy, you send single byte instructions when a direction or speed change is required. The bytes are broken into two nibbles:  0xXY  where X is the direction and Y is the speed. For example the byte 0x16 means forwards at mid-speed. I was surprised to note the car continues carrying out the last given demand! I let pairing get dealt with by the operating system. The code to create a  Car object that is drivable over Bluetooth is very straight forward in pure Python: import socket import time class BluetoothCar : def __init__ ( self , mac_address = "00:12:05:09:98:36" ): self . socket = socket . socket ( socket . AF_BLUETOOTH , socket . SOCK_STREAM , socket .

Matplotlib in Django

The official django tutorial is very good, it stops short of displaying data with matplotlib - which could be very handy for dsp or automated testing. This is an extension to the tutorial. So first you must do the official tutorial! Complete the tutorial (as of writing this up to part 4). Adding an image to a view To start with we will take a static image from the hard drive and display it on the polls index page. Usually if it really is a static image this would be managed by the webserver eg apache. For introduction purposes we will get django to serve the static image. To do this we first need to change the template. Change the template At the moment poll_list.html probably looks something like this: <h1>Django test app - Polls</h1> {% if object_list %} <ul> {% for object in object_list %} <li><a href="/polls/{{object.id}}">{{ object.question }}</a></li> {% endfor %} </ul> {% else %} <p>No polls

Homomorphic encryption using RSA

I recently had cause to briefly look into Homomorphic Encryption , the process of carrying out computations on encrypted data. This technique allows for privacy preserving computation. Fully homomorphic encryption (FHE) allows both addition and multiplication, but is (currently) impractically slow. Partially homomorphic encryption just has to meet one of these criteria and can be much more efficient. An unintended, but well-known, malleability in the common RSA algorithm means that the multiplication of ciphertexts is equal to the multiplication of the original messages. So unpadded RSA is a partially homomorphic encryption system. RSA is beautiful in how simple it is. See wikipedia to see how to generate the public ( e , m ) and private keys ( d , m ). Given a message x it is encrypted with the public keys it to get the ciphertext C ( x ) with: C ( x ) = x e mod m To decrypt a ciphertext C ( x ) one applies the private key: m = C ( x ) d mod m The homomorphic prop