Lambda magic

Reflection

Expression of thoughts in the form of spoken and written language is one of the most important traits that makes humans an intelligent species. It helps us transfer knowledge among ourselves and solve problems around us. It lets us think in abstract fashion and provides a way to convey problems and their solutions. This even expands beyond one’s own mind and formulating a way to process a problem can be used by others to process information and get results. That other mind can be another human or a machine and that’s the beauty of it. Mathematical notations, theories, hypotheses etc are few of the examples and so are programming languages designed to talk to a computer. Given an abstraction layer over the internal functioning of a machine (compilers and such) one can write an expressive enough language to instruct the same machine to solve any problem.

Introduction

This post is about appreciating the development of such expressive languages over the last century and to understand how they work. LISP as defined by John McCarthy in his famous paper is one of the first expressive languages that was written keeping this abstraction in mind. The piece of code that I am referring here was mentioned in Paul Graham’s The Roots of Lisp paper under the “The Surprise'' section and was also claimed to be the Most Beautiful Program Ever Written by William Byrd in his presentation.

The Code

The program in question is supposed to be an interpreter with a global environment that handles symbols and procedures. All it needs from the underlying language is a way to identify symbols, lambda, pattern matching and conditional statements. surprisingly no primitives!

This is not an REPL and only takes a program as a quoted string. What makes it beautiful is the ability given to the user to extend the language with bare minimum functionalities.

(define eval-expr
  (lambda (expr env)
    (match expr
      [`,x
       #:when (symbol? x)
        (env x)]
      [`(lambda (,x) ,body)
        (lambda (arg)
          (eval-expr body (lambda (y)
                            (if (eq? x y)
                                arg
                                (env y)))))]
      [`(,rator ,rand)
       ((eval-expr rator env)
        (eval-expr rand env))])))

Architecure Diagram

As depicted in the diagram the initial expression keeps on expanding based on its individual component and doing lookups in the environment. Fully expanded expressions should be able to resolve all unbound expressions from the environment. The base environment is supposed to have all required mapping in it.

How is map implemented ?

fully expanded it actually is a big if-else statement that searches symbol in a linear manner so not exactly a hashmap

;; map is defined and populated
; empty map
(define hmap1 (lambda (x) (error "unbound")))
; adding mapping `5 -> 5
(define hmap2 (lambda (y)
               (if (eq? y 5)
                   5
                   (hmap1 y))))
; adding mapping `x -> x
(define hmap3 (lambda (y)
                (if (eq? y `x)
                    `x
                    (hmap2 y))))

(define env hmap3)

; querying map
(env (quote 5))

Same can be implemented in python as such

def environment(symbol):
if symbol == 5:
return 5
elif symbol == 'x':
return 'x'
else:
raise "unbound"

In Progress

I am working on writing some usable examples that can really show this interpreter in action. Please revisit the page for updates.