Lisplet

REPL

This is a live REPL for Lisplet powered by WebAssembly. Take a look at some of the examples and try it out!

The REPL (Read Evaluate Print Loop) in Lisplet provides an interactive environment for executing Lisp expressions. It operates as follows: First, the environment is loaded with the prelude, which contains a set of predefined functions and variables. The user is then prompted to input a single expression, followed by a terminating newline or return to submit it for evaluation. To exit the REPL session, the user can simply input an empty expression.

def repl(prompt='lisplet> '):
    env = prelude.copy()
    while True:
        expr = input(prompt)
        if expr == '':
            break
        res = evaluate(parse(lex(expr)), env)
        if res is not None:
            print(res)

lisplet> (define factorial (lambda (n) (reduce * 1 (range 1 n))))
lisplet> (factorial 5)
120
lisplet> (define grades (93 99 85 82))
lisplet> (/ (reduce + 0 grades) (length grades))
89.75
lisplet>

Interpreter

The Lisplet interpreter is implemented using a simple recursive descent parser and an environment-based model of evaluation. The core interpreter weighs in at less than 60 lines of code, with the prelude adding less than 100 lines.

Lisplet’s syntax is based on S-expressions. S-expressions consist of a sequence of atoms and/or nested S-expressions enclosed in parentheses, forming a tree structure that can be easily processed and manipulated. The lexer is responsible for tokenizing the input text into individual elements, such as symbols, numbers, or the S-expression delimiters.

def lex(s):
    s = s.splitlines()
    s = ' '.join(s)
    s = s.replace('(', ' ( ')
    s = s.replace(')', ' ) ')
    return s.split()

The following implements the recursive descent parser that builds a hierarchical structure of nested expressions based on the grammar rules of S-expressions. While consuming the token stream, if the function encounters an opening parenthesis, it recursively calls itself on each subsequent token until it reaches a closing parenthesis, and returns the resulting expression.

def parse(tokens):
    token = tokens.pop(0)

    if token == '(':
        expr = []
        while tokens[0] != ')':
            expr.append(parse(tokens))
        tokens.pop(0)
        return expr

    try:
        return int(token)
    except ValueError:
        try:
            return float(token)
        except ValueError:
            return token

Special forms are expressions that are handled differently since they require different specialized evaluation rules despite looking similar to normal procedure calls.

def _define(expr, env):
    _, name, exp = expr
    env[name] = evaluate(exp, env)

def _if(expr, env):
    _, cond, conseq, alt = expr
    return evaluate(conseq if evaluate(cond, env) else alt, env)

def _lambda(expr, env):
    _, params, body = expr
    return lambda *args: evaluate(body, {**env, **dict(zip(params, args))})

special_forms = {
    'define': _define,
    'if': _if,
    'lambda': _lambda,
}

S-expressions are recursively evaluated by applying a set of rules based on structure. It performs pattern matching against the expression to apply special evaluation rules for special forms. When encountering a function call, the head of the expression is recursively evaluated to obtain a callable object, and then the arguments are evaluated to be bound to the parameters of the callable. The resulting evaluation can be a list of evaluated results for a list of sub-expressions or the expression itself for primitive values or non-lists.

def evaluate(expr, env):
    match expr:
        case str(name) if name in env:
            return env[name]
        case [str(head), *_] if head in special_forms:
            return special_forms[head](expr, env)
        case [head, *args] if callable(f := evaluate(head, env)):
            return f(*(evaluate(arg, env) for arg in args))
        case list(_):
            return [evaluate(arg, env) for arg in expr]
        case _:
            return expr

The interpret function serves as the entry point to the interpreter. It expects an environment, which can be a prepopulated Python dictionary, and a variable number of expressions in string format as arguments. It orchestrates the entire process by calling the lexer to split the expressions into tokens, the parser to build an abstract syntax tree (AST), and the evaluator to pattern match against the AST and update the environment accordingly.

def interpret(env, *exprs):
    value = None
    for expr in exprs:
        value = evaluate(parse(lex(expr)), env)
    return value

Prelude

The prelude in Lisplet includes a set of procedures that directly expose some of Python’s functionality to Lisplet. These procedures cover arithmetic, logic, list, and record operations. List operations utilize Python lists while records are akin to an immutable Python dictionary.

Additionally, the prelude includes higher-level operations and utility functions implemented in Lisplet itself. These procedures are interpreted directly into the prelude environment. The majority of these procedures are written for LISt Processing.

from math import prod

prelude = {
    '+': lambda *args: sum(args),
    '-': lambda *args: args[0] - sum(args[1:]),
    '*': lambda *args: 1 if len(args) == 0 else prod(args),
    '/': lambda *args: args[0] if len(args) == 1 else (args[0] // prod(args[1:])),
    'mod': lambda x, y: x % y,

    '<': lambda x, y: x < y,
    '>': lambda x, y: x > y,
    '=': lambda x, y: x == y,

    'not': lambda x: not x,
    'and': lambda x, y: x and y,
    'or': lambda x, y: x or y,

    'cons': lambda x, y: [x] + y if isinstance(y, list) else [x, y],
    'car': lambda x: x[0],
    'cdr': lambda x: x[1:],
    'null?': lambda x: not bool(x),

    'record': lambda *fields: (lambda *args: {k: v for k, v in zip(fields, args)}),
    'get': lambda aggregate, index: aggregate[index],
}

(define map (lambda (f xs)
    (if (null? xs) ()
        (cons (f (car xs)) (map f (cdr xs))))))

(define filter (lambda (pred xs)
    (if (null? xs) ()
        (if (pred (car xs))
            (cons (car xs) (filter pred (cdr xs)))
            (filter pred (cdr xs))))))

(define reduce (lambda (f acc xs)
    (if (null? xs) acc
        (reduce f (f acc (car xs)) (cdr xs)))))

(define zip (lambda (xs ys)
  (if (or (null? xs) (null? ys)) ()
      (cons (cons (car xs) (car ys))
            (zip (cdr xs) (cdr ys))))))

(define range (lambda (start end)
  (if (> start end) ()
      (cons start (range (+ start 1) end)))))

(define length (lambda (xs)
  (if (null? xs) 0
      (+ 1 (length (cdr xs))))))

(define reverse (lambda (xs acc)
  (if (null? xs) acc
      (reverse (cdr xs) (cons (car xs) acc)))))

(define take (lambda (n xs)
    (if (or (= n 0) (null? xs)) ()
        (cons (car xs) (take (- n 1) (cdr xs))))))

(define drop (lambda (n xs)
  (if (or (= n 0) (null? xs)) xs
      (drop (- n 1) (cdr xs)))))

(define min (lambda (x y) (if (< x y) x y)))

(define max (lambda (x y) (if (> x y) x y)))

Examples

Here are some simple examples that demonstrate the capabilities of Lisplet. These examples showcase how Lisplet can be used to perform algorithms and define data schemas using prelude functions and records. Despite its minimalistic nature, Lisplet can model many interesting computations.

Shoelace Algorithm

The shoelace algorithm calculates the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane. This algorithm utilizes the shoelace formula, which involves cross-multiplying the coordinates that make up the polygon.

(define Point (record x y))

(define shoelace (lambda (polygon)
    (/ (reduce + 0 (map (lambda (pair)
        (- (* (get (car pair) x) (get (car (cdr pair)) y))
           (* (get (car pair) y) (get (car (cdr pair)) x))))
        (zip polygon (cdr polygon)))) 2)))

(shoelace ((Point 0 0) (Point 5 0) (Point 5 3) (Point 0 3)))

15

0/1 Knapsack Problem

The knapsack proroblem is a combinatorial optimization problem where we are given a set of items, each with a weight and a value. The goal is to determine which items to include in the collection, considering a weight limit, in order to maximize the total value.

(define Item (record weight value))

(define knapsack (lambda (items capacity)
  (if (or (null? items) (= capacity 0)) 0
      ((lambda (item remaining)
         (if (> (get item weight) capacity)
             (knapsack remaining capacity)
             (max (knapsack remaining capacity)
                  (+ (get item value)
                     (knapsack remaining (- capacity (get item weight)))))))
       (car items) (cdr items)))))

(define items ((Item 1 1) (Item 3 4) (Item 4 5) (Item 5 7)))

(define capacity 7)

(knapsack items capacity)

9

Discrete 1D Convolution

A 1D convolution is an operation that combines two sequences by computing their element-wise dot product at each position, yielding a new sequence representing local correlations. Similar to algorithms used in signal processing, image analysis, and deep learning for feature extraction and pattern recognition.

(define slide (lambda (a b index)
  (cons (take (min (+ index 1) (length a))
          (drop (max 0 (+ (- index (length b)) 1)) a))
      ((take (min (- (+ (length a) (length b)) index 1) (length b))
          (drop (max 0 (- (length b) index 1)) b))))))

(define dot (lambda (a b)
    (if (or (null? a) (null? b)) 0
        (+ (* (car a) (car b))
           (dot (cdr a) (cdr b))))))

(define convolve (lambda (a b n)
    (if (= n (- (+ (length a) (length b)) 1)) ()
        (cons (dot (car (slide a (reverse b ()) n))
                (car (cdr (slide a (reverse b ()) n))))
            (convolve a b (+ n 1))))))

(convolve (1 2 3) (4 5 6) 0)

(4 13 28 27 18)