Writing A Simple ARM OS - Part 1

25 Feb 2025

Introduction

In this series, we’ll build a small operating system for the ARM platform from the ground up. Along the way, we’ll explore fundamental OS concepts and incrementally add components, turning abstract ideas into working code. Each article will focus on a specific piece of the system, guiding you through the process step by step.

We’re going to use QEMU, an open-source emulator, so we can develop and test our code directly on a PC—no hardware required (for now).

In Part 1, we’ll first discuss ARM, then move on to the following:

Installing prerequisites
Setting up a project structure
Creating a repeatable build environment
Running your bootloader

The code for this article is available in my Github repository.

Let’s make a start.

What is ARM?

ARM, short for Advanced RISC Machine, is a family of Reduced Instruction Set Computing (RISC) architectures that power billions of devices, from smartphones and tablets to embedded systems and IoT devices. Originally known as Acorn RISC Machine, ARM has become a cornerstone of modern computing due to its energy efficiency and simplicity compared to Complex Instruction Set Computing (CISC) architectures like x86. Designed around the RISC philosophy, ARM processors use a small, highly optimized instruction set, enabling greater performance per watt and making them ideal for low-power and mobile environments.

Why Emulation?

While ARM assembly is usually executed on physical devices, emulation tools like QEMU allow you to:

Test code without requiring hardware.
Experiment with different ARM-based architectures and peripherals.
Debug programs more effectively using tools like GDB.

Supported ARM Hardware

Before we begin coding, let’s take a brief look at some popular ARM-based platforms:

Raspberry Pi: A widely used single-board computer.
BeagleBone Black: A powerful option for embedded projects.
STM32 Microcontrollers: Common in IoT and robotics applications.

Installing prerequisites

Before we begin, we need to setup our development and build environment. I’m using Manjaro so package names might be slightly different for your distro of choice.

To build our software, we’ll install the arm-none-eabi toolchain, which provides the assembler (as), linker (ld), and other essential utilities.

sudo pacman -S arm-none-eabi-binutils arm-none-eabi-gcc

We will also need a virtual machine / emulator to run the software that we build. We’ll use QEMU.

sudo pacman -S qemu-system-arm

With our toolchain and emulator installed, we’re ready to move forward.

Setup the Project

I’ve called my project armos, and have created the following structure:

.
├── asm
├── build
├── docs
├── README.md
└── src

asm will hold our assembly language modules
build is where our binaries are built to
docs is for any documentation that we might have
src will hold our c language modules

Code!

Now that our project structure is in place, we can begin writing our first piece of assembly code: the bootloader.

If we add bootstrap.s to the asm folder we can make a start on the bootloader.

.section    .text
.global     _start

_start:
    LDR     sp, =stack_top   @ initialize the stack pointer
    BL      kernel_main      @ jump to the kernel main loop

kernel_main:
1:  B 1b                     @ infinite loop to keep the OS running

    B .                      @ fallback loop
    
.section    .bss             
.align      4
stack_top:
.space      1024             @ allocate 1kb for the stack

This is a pretty basic module to begin with. At the start we define our code with a .text section and _start is a global symbol:

.section    .text
.global     _start

Next, we setup our stack pointer sp by loading the address of our stack_top. The equal sign preceeding stack_top tells the assembler to load the immediate value of the address. We have stack_top defined down a little further.

Then, we jump on to our kernel.

Interesting note, BL which is Branch with Link works very much like a branch (B) but it will store the address from where we branched into the link register r14.

_start:
    LDR     sp, =stack_top   @ initialize the stack pointer
    BL      kernel_main      @ jump to the kernel main loop

Now we have two endless loops setup. The first one loops back to the 1: loop:

1:  B 1b                     @ infinite loop to keep the OS running

If we do get an unexpected address sneak in for whatever reason, we’ve got a fallback loop that continually jumps to itself using the shorthand ..

B .                      @ fallback loop

Finally, we complete the module by defining our stack with the .bss section. You’ll notice the stack_top label that we referenced earlier.

.section    .bss             
.align      4
stack_top:
.space      1024             @ allocate 1kb for the stack

Build environment

We need to make this easy to build, so we create a Makefile in the root directory. The Makefile will use the toolchain that we installed earlier, building our binaries into the build folder:

AS = arm-none-eabi-as
LD = arm-none-eabi-ld
OBJCOPY = arm-none-eabi-objcopy

# Files and directories
ASM_SRCS = asm/bootloader.s
BUILD_DIR = build
TARGET = armos.elf

all: $(BUILD_DIR)/$(TARGET)

$(BUILD_DIR)/$(TARGET): $(ASM_SRCS)
	@mkdir -p $(BUILD_DIR)
	$(AS) -o $(BUILD_DIR)/bootloader.o $(ASM_SRCS)
	$(LD) -Ttext 0x0 -o $(BUILD_DIR)/$(TARGET) $(BUILD_DIR)/bootloader.o
	$(OBJCOPY) -O binary $(BUILD_DIR)/$(TARGET) $(BUILD_DIR)/armos.bin

clean:
	rm -rf $(BUILD_DIR)

Our call out to our assembler is pretty straight forward, trading our .s files for .o object files. We use -Ttext 0x0 to explicitly tell the linker that our program should start at address 0x0, which is necessary for bare-metal environments.

Give it a build.

make

All going well you should see some output as follows:

arm-none-eabi-as -o build/bootloader.o asm/bootloader.s
arm-none-eabi-ld -Ttext 0x0 -o build/armos.elf build/bootloader.o
arm-none-eabi-objcopy -O binary build/armos.elf build/armos.bin

You should also find some built binaries in your build folder.

First launch

We can give our new operating system a run via qemu with the following instruction:

qemu-system-arm -M versatilepb -kernel build/armos.elf -nographic

Here we have a few switches:

-M versatilepb emulates a popular ARM development board
-kernel build/armos.elf loads our compiled bootloader/OS binary
-nographic runs qemu without a graphical user interface

If everything works, you won’t see much—your bootloader is running in an infinite loop, waiting for further development.

Debugging

Because we are running in a virtualised environment, we have a full debugger at our disposal. Having a debugger attached to your code when things aren’t quite going to plan can be very valuable to understand what’s happening in the internals of your program.

Using the -gdb option, you can instruct qemu to open a debugging port.

qemu-system-arm -M versatilepb -kernel boot.elf -S -gdb tcp::1234

You can then connect to gdb with the following:

arm-none-eabi-gdb boot.elf
target remote :1234

Deployment

Finally, we’ll touch on deployment.

For deployment, we’ll use a Raspberry Pi as an example. This process is similar for other ARM-based boards.

Flashing

First, we need to convert the ELF file to a raw binary format suitable for booting:

arm-none-eabi-objcopy -O binary boot.elf boot.bin

Use a tool like dd to write the binary to an SD card:

Caution: Be very careful with the dd command! Double-check /dev/sdX before running it to avoid overwriting important data.

dd if=boot.bin of=/dev/sdX bs=512 seek=2048

Conclusion

In this post, we’ve built the foundation for armos. We’ve installed and configured the ARM toolchain, set up QEMU to emulate our target board, organized our project directory for clarity and scalability, and even wrote a simple bootloader to jumpstart our operating system. With these critical components in place, you’re now ready to embark on the next steps—enhancing the bootloader, adding essential kernel functionalities, and ultimately constructing a full-fledged minimalist OS.

Writing Your Own Lisp Interpreter in Haskell - Part 7

18 Feb 2025

Introduction

In this update, we’re introducing first-class functions to our Lisp interpreter! This allows users to define and use functions just like they would in a real Lisp environment.

Before this update, function definitions looked like this:

(define square (lambda (x) (* x x)))
(square 4) ;; Expected 16

This worked, but wasn’t very Lisp-like. In Lisp, we usually define functions using a shorthand syntax:

(define (square x) (* x x))
(square 4) ;; Expected 16

We’re going to support both styles while keeping our implementation clean.

Extending `define`

The first change we made was updating eval to detect function definitions and create a lambda automatically.

We extend define to detect function definitions and transform them into lambda expressions automatically:

eval env (List [Atom "define", List (Atom funcName : params), body]) = do
    let paramNames = map extractParam params
    defineVar env funcName (Lambda paramNames body env)
  where
    extractParam (Atom name) = name
    extractParam nonAtom = error $ "Expected parameter name, got: " ++ show nonAtom

This means that:

If define receives a list as the first argument, it assumes we’re defining a function.
The first element of that list (funcName) is the function name.
The remaining elements (params) are the parameter names.
The function body is stored as a lambda expression.

Example

With this change, both of these definitions are now equivalent:

;; Using explicit lambda
(define square (lambda (x) (* x x)))

;; Using shorthand function definition
(define (square x) (* x x))

(square 4) ;; 16

This makes function definitions much cleaner and easier to read!

Fixing `if` Expressions

While making these changes, we discovered a bug in our if implementation.

Previously, if did not evaluate the then or else branch before returning it:

eval env (List [Atom "if", condition, thenExpr, elseExpr]) = do
    result <- eval env condition
    case result of
        Bool True  -> return thenExpr  
        Bool False -> return elseExpr  
        _          -> throwError $ TypeMismatch "Expected boolean in if condition" result

This meant that calling:

(if (> 10 5) (* 2 2) (* 3 3))

Would return (* 2 2) instead of 4!

The Fix

We simply added eval env to ensure the chosen branch is evaluated before being returned:

eval env (List [Atom "if", condition, thenExpr, elseExpr]) = do
    result <- eval env condition
    case result of
        Bool True  -> eval env thenExpr  
        Bool False -> eval env elseExpr  
        _          -> throwError $ TypeMismatch "Expected boolean in if condition" result

Now, if expressions behave correctly:

(if (> 10 5) (* 2 2) (* 3 3)) ;; 4
(if (< 10 5) (* 2 2) (* 3 3)) ;; 9

Recursion

With function definitions and the fixed if statement, we can now write recursive functions!

Example: Factorial Function

(define (factorial n)
  (if (<= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 5) ;; 120

Example: Fibonacci Sequence

(define (fib n)
  (if (<= n 1)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(fib 10) ;; 55

This is a huge milestone 🎉 because recursion is essential in functional programming!

Conclusion

In this update, we:

Added shorthand function definitions (e.g., (define (square x) (* x x))).
Fixed if expressions to evaluate branches properly.
Enabled recursion, making functions like factorial and fib possible.

Writing Your Own Lisp Interpreter in Haskell - Part 6

18 Feb 2025

Introduction

In this update, we extend our Lisp interpreter with floating point numbers and floating point math functions. This brings us closer to full numeric support, allowing for a much richer mathematical capability.

If you’re following along, you can find the implementation for this article here.

Floating Point Type

Until now, our Lisp implementation only supported integers:

data LispVal
    = Atom String
    | Number Integer
    | Bool Bool
    | String String
    | Float Double  -- Added floating point support
    | List [LispVal]
    | Pair LispVal LispVal
    | Lambda [String] LispVal Env
    | BuiltinFunc ([LispVal] -> ThrowsError LispVal)
    | BuiltinFuncIO ([LispVal] -> IOThrowsError LispVal)

We introduced a new constructor Float Double to represent floating point numbers.

Parsing

We needed to update our parser to recognize floating point literals. We do this in such a way to operate alongside the current integer math that we currently support. We don’t want to disturb the work that we’ve already done, so we’ll use that effort here.

parseInteger :: Parser LispVal
parseInteger = do
    sign <- optionMaybe (char '-')  -- Look for optional '-'
    digits <- many1 digit
    let number = read digits
    return $ Number $ case sign of
        Just _  -> -number
        Nothing -> number

parseFloat :: Parser LispVal
parseFloat = do
    sign <- optionMaybe (char '-')  -- Look for optional '-'
    whole <- many1 digit
    char '.'
    fractional <- many1 digit
    let number = read (whole ++ "." ++ fractional)
    return $ Float $ case sign of
        Just _  -> -number
        Nothing -> number

parseNumber :: Parser LispVal
parseNumber = try parseFloat <|> parseInteger

So, we changed the meaning of parseNumber from our original implementation. Instead of parseNumber handling only integers, we split the logic into parseInteger and parseFloat, ensuring both number types are correctly parsed

This ensures that expressions like 3.14 are correctly interpreted as floating point numbers, while still maintaining expressions like 3 being handled as integers.

One extra added feature here is handling negative numbers. We never observed the - symbol that can appear before some numbers, so we’ve fixed this in the parser at the same time.

Numeric Coercion

Next, we needed to handle operations between integers and floats.

Our previous numeric functions assumed only integers, so we modified them to coerce integers to floats when necessary. This means that we can use integers and floats together in our expressions.

numericAdd, numericSub, numericMul, numericDiv :: [LispVal] -> ThrowsError LispVal

numericAdd [Number a, Number b] = return $ Number (a + b)
numericAdd [Float a, Float b] = return $ Float (a + b)
numericAdd [Number a, Float b] = return $ Float (fromIntegral a + b)
numericAdd [Float a, Number b] = return $ Float (a + fromIntegral b)
numericAdd args = throwError $ TypeMismatch "Expected numbers" (List args)

This same logic was applied to subtraction, multiplication, and division.

Division Considerations

Division needed special attention because it must always return a float when dividing integers:

numericDiv [Number a, Number b] =
    if b == 0 then throwError $ TypeMismatch "Division by zero" (Number b)
    else return $ Float (fromIntegral a / fromIntegral b)
numericDiv [Float a, Float b] = return $ Float (a / b)
numericDiv [Number a, Float b] = return $ Float (fromIntegral a / b)
numericDiv [Float a, Number b] = return $ Float (a / fromIntegral b)
numericDiv args = throwError $ TypeMismatch "Expected numbers" (List args)

This ensures that (/ 3 2) evaluates to 1.5 instead of performing integer division.

Adding Floating Point Math Functions

With float support in place, we introduced math functions like sin, cos, tan, exp, log, and sqrt:

import Prelude hiding (log)

numericSin, numericCos, numericTan, numericExp, numericLog, numericSqrt :: [LispVal] -> ThrowsError LispVal

numericSin [Float a] = return $ Float (sin a)
numericSin [Number a] = return $ Float (sin (fromIntegral a))
numericSin args = throwError $ TypeMismatch "Expected a number" (List args)

numericCos [Float a] = return $ Float (cos a)
numericCos [Number a] = return $ Float (cos (fromIntegral a))
numericCos args = throwError $ TypeMismatch "Expected a number" (List args)

numericTan [Float a] = return $ Float (tan a)
numericTan [Number a] = return $ Float (tan (fromIntegral a))
numericTan args = throwError $ TypeMismatch "Expected a number" (List args)

numericExp [Float a] = return $ Float (exp a)
numericExp [Number a] = return $ Float (exp (fromIntegral a))
numericExp args = throwError $ TypeMismatch "Expected a number" (List args)

numericLog [Float a] =
    if a <= 0 then throwError $ TypeMismatch "Logarithm domain error" (Float a)
    else return $ Float (log a)
numericLog [Number a] =
    if a <= 0 then throwError $ TypeMismatch "Logarithm domain error" (Number a)
    else return $ Float (log (fromIntegral a))
numericLog args = throwError $ TypeMismatch "Expected a positive number" (List args)

numericSqrt [Float a] =
    if a < 0 then throwError $ TypeMismatch "Square root of negative number" (Float a)
    else return $ Float (sqrt a)
numericSqrt [Number a] =
    if a < 0 then throwError $ TypeMismatch "Square root of negative number" (Number a)
    else return $ Float (sqrt (fromIntegral a))
numericSqrt args = throwError $ TypeMismatch "Expected a non-negative number" (List args)

We then added them to the built-in function table:

primitives =
  [ ("sin", BuiltinFunc numericSin),
    ("cos", BuiltinFunc numericCos),
    ("tan", BuiltinFunc numericTan),
    ("exp", BuiltinFunc numericExp),
    ("log", BuiltinFunc numericLog),
    ("sqrt", BuiltinFunc numericSqrt)
  ]

Testing

With these changes, we can now perform floating point math:

(sin 0.0)   ;; 0.0
(cos 0.0)   ;; 1.0
(exp 1.0)   ;; 2.718281828
(log 10.0)  ;; 2.302585092
(sqrt 16.0) ;; 4.0

Conclusion

In this update, we:

Added floating point support.
Added negative support.
Introduced numeric coercion between integers and floats.
Implemented floating point math functions.
Ensured division always returns a float.

Writing Your Own Lisp Interpreter in Haskell - Part 5

16 Feb 2025

Introduction

In our previous installment, we added basic list operations to our Lisp interpreter, including cons, car, cdr, append, and reverse.

Now, we are expanding that functionality by introducing higher-order list functions:

map
filter
foldl and foldr
sort

Additionally, we’re introducing string manipulation functions that allow us to treat strings as lists of characters:

string->list
list->string

These changes bring our Lisp interpreter closer to standard Scheme-like behavior.

If you’re following along, you can find the updated implementation for this article here.

Lambda Expressions

A lambda function in computer programming is an anonymous function that we use to pass to higher-order functions.

To support map, filter, and fold, we implemented lambda functions properly. Previously, our Lisp could parse lambdas but couldn’t correctly apply them.

Adding Lambda Support

We modified eval to properly capture the current environment and store parameter names:

eval env (List [Atom "lambda", List params, body]) =
    case mapM getParamName params of
        Right paramNames -> return $ Lambda paramNames body env
        Left err -> throwError err
  where
    getParamName (Atom name) = Right name
    getParamName badArg = Left $ TypeMismatch "Expected parameter name" badArg

When a lambda function is applied, it creates a new local environment that maps function parameters to actual arguments.

apply (Lambda params body closure) args = do
    env <- liftIO $ readIORef closure
    if length params == length args
        then do
            let localEnv = Map.union (Map.fromList (zip params args)) env
            newEnvRef <- liftIO $ newIORef localEnv
            eval newEnvRef body
        else throwError $ NumArgs (length params) args

Example

Now, we can define and call lambda functions:

(define square (lambda (x) (* x x)))
(square 5)  ;; 25

Higher-Order List Functions

Now that lambda functions work, we can introduce list processing functions.

Map

map applies a function to each element in a list and returns a new list.

listMap :: [LispVal] -> IOThrowsError LispVal
listMap [Lambda params body env, List xs] =
    List <$> mapM (\x -> apply (Lambda params body env) [x]) xs
listMap args = throwError $ TypeMismatch "Expected a function and a list" (List args)

Example

(map (lambda (x) (* x 2)) '(1 2 3 4))
;; => (2 4 6 8)

Filter

filter removes elements that don’t satisfy a given predicate.

listFilter :: [LispVal] -> IOThrowsError LispVal
listFilter [func@(Lambda _ _ _), List xs] = do
    filtered <- filterM (\x -> do
        result <- apply func [x]
        case result of
            Bool True  -> return True
            Bool False -> return False
            _          -> throwError $ TypeMismatch "Expected boolean return" result
        ) xs
    return $ List filtered
listFilter args = throwError $ TypeMismatch "Expected a function and a list" (List args)

Example

(filter (lambda (x) (> x 5)) '(2 4 6 8))
;; => (6 8)

Fold (Reduce)

foldl and foldr accumulate values from left to right or right to left.

listFoldL :: [LispVal] -> IOThrowsError LispVal
listFoldL [Lambda params body env, initial, List xs] =
    foldM (\acc x -> apply (Lambda params body env) [acc, x]) initial xs
listFoldL args = throwError $ TypeMismatch "Expected a function, initial value, and a list" (List args)

listFoldR :: [LispVal] -> IOThrowsError LispVal
listFoldR [Lambda params body env, initial, List xs] =
    foldM (\acc x -> apply (Lambda params body env) [x, acc]) initial (reverse xs)
listFoldR args = throwError $ TypeMismatch "Expected a function, initial value, and a list" (List args)

Example

(foldl (lambda (acc x) (+ acc x)) 0 '(1 2 3 4 5))
;; => 15

This works like (((((0 + 1) + 2) + 3) + 4) + 5).

Whilst swapping out foldr for foldl in this scenario gives us the same result, it’s very different in execution. It ends up working like (1 + (2 + (3 + (4 + (5 + 0))))).

Sort

sort Sorts a list in ascending order by default or with a custom comparator.

listSort :: [LispVal] -> ThrowsError LispVal
listSort [List xs] =
    case xs of
        [] -> return $ List []
        (Number _:_) -> return $ List (sortBy compareNumbers xs)
        (String _:_) -> return $ List (sortBy compareStrings xs)
        _ -> throwError $ TypeMismatch "Cannot sort mixed types" (List xs)
  where
    compareNumbers (Number a) (Number b) = compare a b
    compareStrings (String a) (String b) = compare a b

listSort [Lambda params body closure, List xs] =
    case xs of
        [] -> return $ List []
        _  -> throwError $ TypeMismatch "Custom sorting requires ThrowsErrorIO" (List xs)
        -- If you later want custom sorting, you'd need `ThrowsErrorIO`
listSort args = throwError $ TypeMismatch "Expected a list (optionally with a comparator function)" (List args)

Example

(sort '(5 3 8 1 4))
;; => (1 3 4 5 8)

Optionally, the implementation allows you to specify a predicate to control the sort.

String Manipulation

Strings are now treated as lists of characters in our Lisp. This can sometimes make things easier to work with when dealing with strings.

Example

We can convert a string into a list (and therefore operate on it like it’s a list) by using string->list.

stringToList :: [LispVal] -> ThrowsError LispVal
stringToList [String s] = return $ List (map (String . (:[])) s)
stringToList args = throwError $ NumArgs 1 args

(string->list "hello")
;; => ("h" "e" "l" "l" "o")

We reverse this process with list->string.

listToString :: [LispVal] -> ThrowsError LispVal
listToString [List chars] = case mapM extractChar chars of
    Right strList -> return $ String (concat strList)
    Left err -> throwError err
  where
    extractChar (String [c]) = Right [c]
    extractChar invalid = Left $ TypeMismatch "Expected a list of single-character strings" invalid
listToString args = throwError $ NumArgs 1 args

(list->string '("h" "e" "l" "l" "o"))
;; => "hello"

Conclusion

We now how have higher order functions and lambda functions controlling our list processing. Stay tuned for further updates as we add more features to our Lisp.

Writing Your Own Lisp Interpreter in Haskell - Part 4

16 Feb 2025

Introduction

In the previous post we added conditionals to our basic Lisp interpreter. Now, it’s time to introduce list manipulation – one of Lisp’s most fundamental features.

This update brings support for:

Pairs (cons), first element (car), and rest (cdr)
List predicates (null?)
Common list operations (append, length, reverse)
Proper parsing of quoted lists ('(...))

Pairs and Lists

In Lisp, lists are built from pairs (cons cells). Each pair contains a head (car) and a tail (cdr). We’ll add Pair into our LispVal data type:

data LispVal
    = Atom String
    | Number Integer
    | Bool Bool
    | String String
    | List [LispVal]
    | Pair LispVal LispVal  
    | Lambda [String] LispVal Env
    | BuiltinFunc ([LispVal] -> ThrowsError LispVal)

This allows us to represent both lists and dotted pairs like:

(cons 1 2)    ;; (1 . 2)
(cons 1 '(2)) ;; (1 2)

`cons`, `car`, and `cdr`

cons is a function in most dialects of Lisp that constructs memory objects which hold two values or pointers to two values.

cons :: [LispVal] -> ThrowsError LispVal
cons [x, List xs] = return $ List (x : xs)  
cons [x, y]       = return $ Pair x y       
cons args         = throwError $ NumArgs 2 args

This allows us to build pairs and lists alike:

(cons 1 2)       ;; (1 . 2)
(cons 1 '(2 3))  ;; (1 2 3)

(car and cdr)[https://en.wikipedia.org/wiki/CAR_and_CDR] are list primitives that allow you to return the first or second component of a pair.

The expression (car (cons x y)) evaluates to x, and (cdr (const x y)) evaluates to y.

car :: [LispVal] -> ThrowsError LispVal
car [List (x : _)] = return x
car [Pair x _]     = return x  
car [List []]      = throwError $ TypeMismatch "Cannot take car of empty list" (List [])
car [arg]          = throwError $ TypeMismatch "Expected a pair or list" arg
car args           = throwError $ NumArgs 1 args

cdr :: [LispVal] -> ThrowsError LispVal
cdr [List (_ : xs)] = return $ List xs  
cdr [Pair _ y]      = return y          
cdr [List []]       = throwError $ TypeMismatch "Cannot take cdr of empty list" (List [])
cdr [arg]           = throwError $ TypeMismatch "Expected a pair or list" arg
cdr args            = throwError $ NumArgs 1 args

We can now uwe these functions to work with our lists and pairs:

(car '(1 2 3))   ;; 1
(car '(a b c))   ;; a
(car '(5 . 6))   ;; 5

(cdr '(1 2 3))   ;; (2 3)
(cdr '(a b c))   ;; (b c)
(cdr '(5 . 6))   ;; 6

Checking for Empty Lists

We need a way to determine if our list is empty, and we do that with isNull:

isNull :: [LispVal] -> ThrowsError LispVal
isNull [List []] = return $ Bool True
isNull [_]       = return $ Bool False
isNull args      = throwError $ NumArgs 1 args

This is pretty straight forward to use:

(null? '())      ;; #t
(null? '(1 2 3)) ;; #f

Extending List Operations

Going a little bit further now, we can easily implement append, length, and reverse.

listAppend :: [LispVal] -> ThrowsError LispVal
listAppend [List xs, List ys] = return $ List (xs ++ ys)
listAppend [List xs, y] = return $ List (xs ++ [y])  
listAppend [x, List ys] = return $ List ([x] ++ ys)  
listAppend args = throwError $ TypeMismatch "Expected two lists or a list and an element" (List args)

listLength :: [LispVal] -> ThrowsError LispVal
listLength [List xs] = return $ Number (toInteger (length xs))
listLength [arg] = throwError $ TypeMismatch "Expected a list" arg
listLength args = throwError $ NumArgs 1 args

listReverse :: [LispVal] -> ThrowsError LispVal
listReverse [List xs] = return $ List (reverse xs)
listReverse [arg] = throwError $ TypeMismatch "Expected a list" arg
listReverse args = throwError $ NumArgs 1 args

These functions allow us to perform some more interesting processing of our lists:

(append '(1 2) '(3 4))  ;; (1 2 3 4)
(append '(a b) 'c)      ;; (a b c)
(append 'a '(b c))      ;; (a b c)

(length '(1 2 3 4 5))   ;; 5
(length '())            ;; 0

(reverse '(1 2 3 4 5))   ;; (5 4 3 2 1)
(reverse '())            ;; ()

Quoted Lists

Finally, Lisp allows shorthand notation for quoting lists. For example, '(1 2 3) is equivalent to (quote (1 2 3)).

parseQuote :: Parser LispVal
parseQuote = do
    char '\''
    expr <- parseExpr 
    return $ List [Atom "quote", expr]

Conclusion

Our Lisp interpreter is now becoming a little more sophisticated. List processing is so fundamental to how Lisp operates that we needed to get this implemented as soon as possible. The code for this particular article is available up on GitHub to pull down and take a look at.

(define names '("Sally" "Joe" "Tracey" "Bob"))
("Sally" "Joe" "Tracey" "Bob")

(reverse names)
("Bob" "Tracey" "Joe" "Sally")

(car (cdr (reverse names)))
"Tracey"

(append names '("Stacey" "Peter"))
("Sally" "Joe" "Tracey" "Bob" "Stacey" "Peter")

Older Newer

Cogs and Levers A blog full of technical stuff

Writing A Simple ARM OS - Part 1

Introduction

What is ARM?

Why Emulation?

Supported ARM Hardware

Installing prerequisites

Setup the Project

Code!

Build environment

First launch

Debugging

Deployment

Flashing

Conclusion

Writing Your Own Lisp Interpreter in Haskell - Part 7

Introduction

Extending define

Example

Fixing if Expressions

The Fix

Recursion

Example: Factorial Function

Example: Fibonacci Sequence

Conclusion

Writing Your Own Lisp Interpreter in Haskell - Part 6

Introduction

Floating Point Type

Parsing

Numeric Coercion

Division Considerations

Adding Floating Point Math Functions

Testing

Conclusion

Writing Your Own Lisp Interpreter in Haskell - Part 5

Introduction

Lambda Expressions

Adding Lambda Support

Example

Higher-Order List Functions

Map

Example

Filter

Example

Fold (Reduce)

Example

Sort

Example

String Manipulation

Example

Conclusion

Writing Your Own Lisp Interpreter in Haskell - Part 4

Introduction

Pairs and Lists

cons, car, and cdr

Checking for Empty Lists

Extending List Operations

Quoted Lists

Conclusion

Extending `define`

Fixing `if` Expressions

`cons`, `car`, and `cdr`