About Archive Tags RSS Feed


So we come to Lisp

15 July 2022 13:00

Recently I've been working with simple/trivial scripting languages, and I guess I finally reached a point where I thought "Lisp? Why not". One of the reasons for recent experimentation was thinking about the kind of minimalism that makes implementing a language less work - being able to actually use the language to write itself.

FORTH is my recurring example, because implementing it mostly means writing a virtual machine which consists of memory ("cells") along with a pair of stacks, and some primitives for operating upon them. Once you have that groundwork in place you can layer the higher-level constructs (such as "for", "if", etc).

Lisp allows a similar approach, albeit with slightly fewer low-level details required, and far less tortuous thinking. Lisp always feels higher-level to me anyway, given the explicit data-types ("list", "string", "number", etc).

Here's something that works in my toy lisp:

;; Define a function, `fact`, to calculate factorials (recursively).
(define fact (lambda (n)
  (if (<= n 1)
      (* n (fact (- n 1))))))

;; Invoke the factorial function, using apply
(apply (list 1 2 3 4 5 6 7 8 9 10)
  (lambda (x)
    (print "%s! => %s" x (fact x))))

The core language doesn't have helpful functions to filter lists, or build up lists by applying a specified function to each member of a list, but adding them is trivial using the standard car, cdr, and simple recursion. That means you end up writing lots of small functions like this:

(define zero? (lambda (n) (if (= n 0) #t #f)))
(define even? (lambda (n) (if (zero? (% n 2)) #t #f)))
(define odd?  (lambda (n) (! (even? n))))
(define sq    (lambda (x) (* x x)))

Once you have them you can use them in a way that feels simple and natural:

(print "Even numbers from 0-10: %s"
  (filter (nat 11) (lambda (x) (even? x))))

(print "Squared numbers from 0-10: %s"
  (map (nat 11) (lambda (x) (sq x))))

This all feels very sexy and simple, because the implementations of map, apply, filter are all written using the lisp - and they're easy to write.

Lisp takes things further than some other "basic" languages because of the (infamous) support for Macros. But even without them writing new useful functions is pretty simple. Where things struggle? I guess I don't actually have a history of using lisp to actually solve problems - although it's great for configuring my editor..

Anyway I guess the journey continues. Having looked at the obvious "minimal core" languages I need to go further afield:

I'll make an attempt to look at some of the esoteric programming languages, and see if any of those are fun to experiment with.



Comments on this entry

icon philip miller at 00:48 on 16 July 2022

Your examples are a bit verbose

(define zero? (lambda (n) (= n 0))) (define even? (lambda (n) (zero? (% n 2)))) (define odd? (lambda (n) (! (even? n)))) (define sq (lambda (x) (* x x)))

Those conditional expressions that were being tested evaluate to the value the predicates were written to return

(print "Even numbers from 0-10: %s" (filter (nat 11) even?))

(print "Squared numbers from 0-10: %s" (map (nat 11) sq))

The filter predicate and map function can be passed as first-class objects, rather than wrapping them in an extra layer of lambda

icon Steve Kemp at 15:12 on 16 July 2022

Very true. I guess I evolved them slowly as I was putting things together.

Agreed that your versions are better though, without the needless if. Pasted here just for the formatting:

(define zero? (lambda (n) (= n 0)))
(define one?  (lambda (n) (= n 1)))
(define even? (lambda (n) (zero? (% n 2))))
(define odd?  (lambda (n) (! (even? n))))

I've updated the examples as per your suggestion. Thanks :)