About Archive Tags RSS Feed

 

I put an LSP in your LISP ..

28 November 2022 22:00

I recently wrote about yet another lisp I'd been having fun with.

Over the past couple of years I've played with a few toy scripting languages, or random interpreters, and this time I figured I'd do something beyond the minimum, by implementing the Language Server Protocol.

In brief the language server protocol (LSP) is designed to abstract functionality that might be provided by an editor, or IDE, into a small "language server". If the language-server knows how to jump to definitions, provide completion, etc, etc, then the editor doesn't need to implement those things for NN different languages - it just needs to launch and communicate with something that does know how to do the job.

Anyway LSP? LISP? Only one letter different, so that's practically enough reason to have a stab at it.

Thankfully I found a beautiful library that implements a simple framework allowing the easy implementation of a golang-based LSP-serverÖ

Using that I quickly hacked up a server that can provide:

  • Overview of all standard-library functions, on hover.
  • Completion of all standard-library functions.

I've tested this in both GNU Emacs and Neovim, so that means I'm happy I support all editors! (More seriously if it works in two then that probably means that the LSP stuff should work elsewhere too.)

Here's what the "help on hover" looks like, within Emacs:

Vim looks similar but you have to press K to see the wee popup. Still kinda cute, and was a good experiment.

| No comments

 

Alphabetical linting ..

3 November 2022 22:00

So this week I recycled a talk I'd given in the past, about how even using extremely simple parsers allows a lot of useful static-analysis to be done, for specific niche use-cases.

This included examples of scanning comments above classes to ensure they referred to the appropriate object, ensuring that specific function calls always included a specific (optional) parameter, etc.

Nothing too complex, but I figured I'd give a new example this time, and I remembered I'd recently written a bunch of functions for an interpreter which I'd ordered quite deliberately.

Assume you're writing a BASIC interpreter, you need to implement a bunch of built-in maths functions such as SIN, COS, TAN, then some string-related functions LEFT$, RIGHT$, MID$, etc.

When it comes to ordering there are a couple of approaches:

  • Stick them all in one package:
    • builtins/builtins.go
  • Create a package and group them:
    • builtins/maths.go
    • builtins/string.go
    • .. etc

Personal preference probably dictates the choice you make, but either way I think it would be rational and obvious that you'd put the functions in alphabetical order:

func ABS( args []primitive.Object) (primitive.Object, error) {
..}

func COS( args []primitive.Object) (primitive.Object, error) {
..}

func SIN( args []primitive.Object) (primitive.Object, error) {
..}

func TAN( args []primitive.Object) (primitive.Object, error) {
..}

I did that myself, and I wrote a perl-script to just parse the file using a simple regexp "^func\s+([^(]+)\(" but then I figured this was a good time to write a real static-analysis tool.

The golang environment is full of trivial little linters for various purposes, and the standard "go vet .." driver makes it easy to invoke them. Realizing that I was going to get driven in the same way it was obvious I'd write something called "alphaVet".

So anyway, half written for a talk, half-written because of the name:

| No comments

 

Trivial benchmarks of toy languages

8 October 2022 15:00

Over the past few months (years?) I've posted on my blog about the various toy interpreters I've written.

I've used a couple of scripting languages/engines in my professional career, but in public I think I've implemented

Each of these works in similar ways, and each of these filled a minor niche, or helped me learn something new. But of course there's always a question:

  • Which is fastest?

In the real world? It just doesn't matter. For me. But I was curious, so I hacked up a simple benchmark of calculating 12! (i.e. The factorial of 12).

The specific timings will vary based on the system which runs the test(s), but there's no threading involved so the relative performance is probably comparable.

Anyway the benchmark is simple, and I did it "fairly". By that I mean that I didn't try to optimize any particular test-implementation, I just wrote it in a way that felt natural.

The results? Evalfilter wins, because it compiles the program into bytecode, which can be executed pretty quickly. But I was actually shocked ("I wrote a benchmark; The results will blow your mind!") at the second and third result:

BenchmarkEvalFilterFactorial-4      61542     17458 ns/op
BenchmarkFothFactorial-4            44751     26275 ns/op
BenchmarkBASICFactorial-4           36735     32090 ns/op
BenchmarkMonkeyFactorial-4          14446     85061 ns/op
BenchmarkYALFactorial-4              2607    456757 ns/op
BenchmarkTCLFactorial-4               292   4085301 ns/op

here we see that FOTH, my FORTH implementation, comes second. I guess this is an efficient interpreter too, bacause that too is essentially "bytecode". (Looking up words in a dictionary, which really maps to indexes to other words. The stack operations are reasonably simple and fast too.)

Number three? BASIC? I expected better from the other implementations to be honest. BASIC doesn't even use an AST (in my implementation), just walks tokens. I figured the TCO implemented by my lisp would make that number three.

Anyway the numbers mean nothing. Really. But still interesting.

| No comments

 

Lisp macros are magical

23 September 2022 19:00

In my previous post I introduced yet another Lisp interpreter. When it was posted there was no support for macros.

Since I've recently returned from a visit to the UK, and caught COVID-19 while I was there, I figured I'd see if my brain was fried by adding macro support.

I know lisp macros are awesome, it's one of those things that everybody is told. Repeatedly. I've used macros in my emacs programming off and on for a good few years, but despite that I'd not really given them too much thought.

If you know anything about lisp you know that it's all about the lists, the parenthesis, and the macros. Here's a simple macro I wrote:

 (define if2 (macro (pred one two)
    `(if ~pred (begin ~one ~two))))

The standard lisp if function allows you to write:

 (if (= 1 a) (print "a == 1") (print "a != 1"))

There are three arguments supplied to the if form:

  • The test to perform.
  • A single statement to execute if the test was true.
  • A single statement to execute if the test was not true.

My if2 macro instead has three arguments:

  • The test to perform.
  • The first statement to execute if the test was true.
  • The second statement to execute if the test was true.
  • i.e. There is no "else", or failure, clause.

This means I can write:

 (if2 blah
    (one..)
    (two..))

Rather than:

 (if blah
    (begin
       (one..)
       (two..)))

It is simple, clear, and easy to understand and a good building-block for writing a while function:

 (define while-fun (lambda (predicate body)
    (if2 (predicate)
       (body)
       (while-fun predicate body))))

There you see that if the condition is true then we call the supplied body, and then recurse. Doing two actions as a result of the single if test is a neat shortcut.

Of course we need to wrap that up in a macro, for neatness:

(define while (macro (expression body)
                 (list 'while-fun
                       (list 'lambda '() expression)
                       (list 'lambda '() body))))

Now we're done, and we can run a loop five times like so:

(let ((a 5))
  (while (> a 0)
     (begin
        (print "(while) loop - iteration %s" a)
        (set! a (- a 1) true))))

Output:

(while) loop - iteration 5
(while) loop - iteration 4
(while) loop - iteration 3
(while) loop - iteration 2
(while) loop - iteration 1

We've gone from using lists to having a while-loop, with a couple of simple macros and one neat recursive function.

There are a lot of cute things you can do with macros, and now I'm starting to appreciate them a little more. Of course it's not quite as magical as FORTH, but damn close!

| No comments

 

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)
    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.

| 2 comments

 

An update on my simple golang TCL interpreter

1 July 2022 19:00

So my previous post introduced a trivial interpreter for a TCL-like language.

In the past week or two I've cleaned it up, fixed a bunch of bugs, and added 100% test-coverage. I'm actually pretty happy with it now.

One of the reasons for starting this toy project was to experiment with how easy it is to extend the language using itself

Some things are simple, for example replacing this:

puts "3 x 4 = [expr 3 * 4]"

With this:

puts "3 x 4 = [* 3 4]"

Just means defining a function (proc) named *. Which we can do like so:

proc * {a b} {
    expr $a * $b
}

(Of course we don't have lists, or variadic arguments, so this is still a bit of a toy example.)

Doing more than that is hard though without support for more primitives written in the parent language than I've implemented. The obvious thing I'm missing is a native implementation of upvalue, which is TCL primitive allowing you to affect/update variables in higher-scopes. Without that you can't write things as nicely as you would like, and have to fall back to horrid hacks or be unable to do things.

# define a procedure to run a body N times
proc repeat {n body} {
    set res ""
    while {> $n 0} {
        decr n
        set res [$body]
    }
    $res
}

# test it out
set foo 12
repeat 5 { incr foo }

#  foo is now 17 (i.e. 12 + 5)

A similar story implementing the loop word, which should allow you to set the contents of a variable and run a body a number of times:

proc loop {var min max bdy} {
    // result
    set res ""

    // set the variable.  Horrid.
    // We miss upvalue here.
    eval "set $var [set min]"

    // Run the test
    while {<= [set "$$var"] $max } {
        set res [$bdy]

        // This is a bit horrid
        // We miss upvalue here, and not for the first time.
        eval {incr "$var"}
    }

    // return the last result
    $res
}


loop cur 0 10 { puts "current iteration $cur ($min->$max)" }
# output is:
# => current iteration 0 (0-10)
# => current iteration 1 (0-10)
# ...

That said I did have fun writing some simple test-cases, and implementing assert, assert_equal, etc.

In conclusion I think the number of required primitives needed to implement your own control-flow, and run-time behaviour, is a bit higher than I'd like. Writing switch, repeat, while, and similar primitives inside TCL is harder than creating those same things in FORTH, for example.

| No comments

 

Writing a simple TCL interpreter in golang

21 June 2022 13:00

Recently I was reading Antirez's piece TCL the Misunderstood again, which is a nice defense of the utility and value of the TCL language.

TCL is one of those scripting languages which used to be used a hell of a lot in the past, for scripting routers, creating GUIs, and more. These days it quietly lives on, but doesn't get much love. That said it's a remarkably simple language to learn, and experiment with.

Using TCL always reminds me of FORTH, in the sense that the syntax consists of "words" with "arguments", and everything is a string (well, not really, but almost. Some things are lists too of course).

A simple overview of TCL would probably begin by saying that everything is a command, and that the syntax is very free. There are just a couple of clever rules which are applied consistently to give you a remarkably flexible environment.

To get started we'll set a string value to a variable:

  set name "Steve Kemp"
  => "Steve Kemp"

Now you can output that variable:

  puts "Hello, my name is $name"
  => "Hello, my name is Steve Kemp"

OK, it looks a little verbose due to the use of set, and puts is less pleasant than print or echo, but it works. It is readable.

Next up? Interpolation. We saw how $name expanded to "Steve Kemp" within the string. That's true more generally, so we can do this:

 set print pu
 set me    ts

 $print$me "Hello, World"
 => "Hello, World"

There "$print" and "$me" expanded to "pu" and "ts" respectively. Resulting in:

 puts "Hello, World"

That expansion happened before the input was executed, and works as you'd expect. There's another form of expansion too, which involves the [ and ] characters. Anything within the square-brackets is replaced with the contents of evaluating that body. So we can do this:

 puts "1 + 1 = [expr 1 + 1]"
 => "1 + 1 = 2"

Perhaps enough detail there, except to say that we can use { and } to enclose things that are NOT expanded, or executed, at parse time. This facility lets us evaluate those blocks later, so you can write a while-loop like so:

 set cur 1
 set max 10

 while { expr $cur <= $max } {
       puts "Loop $cur of $max"
       incr cur
 }

Anyway that's enough detail. Much like writing a FORTH interpreter the key to implementing something like this is to provide the bare minimum of primitives, then write the rest of the language in itself.

You can get a usable scripting language with only a small number of the primitives, and then evolve the rest yourself. Antirez also did this, he put together a small TCL interpreter in C named picol:

Other people have done similar things, recently I saw this writeup which follows the same approach:

So of course I had to do the same thing, in golang:

My code runs the original code from Antirez with only minor changes, and was a fair bit of fun to put together.

Because the syntax is so fluid there's no complicated parsing involved, and the core interpreter was written in only a few hours then improved step by step.

Of course to make a language more useful you need I/O, beyond just writing to the console - and being able to run the list-operations would make it much more useful to TCL users, but that said I had fun writing it, it seems to work, and once again I added fuzz-testers to the lexer and parser to satisfy myself it was at least somewhat robust.

Feedback welcome, but even in quiet isolation it's fun to look back at these "legacy" languages and recognize their simplicity lead to a lot of flexibility.

| No comments

 

A plea for books ..

3 May 2022 20:00

Recently I've been getting much more interested in the "retro" computers of my youth, partly because I've been writing crazy code in Z80 assembly-language, and partly because I've been preparing to introduce our child to his first computer:

  • An actual 1982 ZX Spectrum, cassette deck and all.
    • No internet
    • No hi-rez graphics
    • Easily available BASIC
    • And as a nice bonus the keyboard is wipe-clean!

I've got a few books, books I've hoarded for 30+ years, but I'd love to collect some more. So here's my request:

  • If you have any books covering either the Z80 processor, or the ZX Spectrum, please consider dropping me an email.

I'd be happy to pay €5-10 each for any book I don't yet own, and I'd also be more than happy to cover the cost of postage to Finland.

I'd be particularly pleased to see anything from Melbourne House, and while low-level is best, the coding-books from Usbourne (The Mystery Of Silver Mountain, etc, etc) wouldn't go amiss either.

I suspect most people who have collected and kept these wouldn't want to part with them, but just in case ..

| 3 comments

 

Porting a game from CP/M to the ZX Spectrum 48k

26 April 2022 20:00

Back in April 2021 I introduced a simple text-based adventure game, The Lighthouse of Doom, which I'd written in Z80 assembly language for CP/M systems.

As it was recently the 40th Anniversary of the ZX Spectrum 48k, the first computer I had, and the reason I got into programming in the first place, it crossed my mind that it might be possible to port my game from CP/M to the ZX Spectrum.

To recap my game is a simple text-based adventure game, which you can complete in fifteen minutes, or less, with a bunch of Paw Patrol easter-eggs.

  • You enter simple commands such as "up", "down", "take rug", etc etc.
  • You receive text-based replies "You can't see a telephone to use here!".

My code is largely table-based, having structures that cover objects, locations, and similar state-things. Most of the code involves working with those objects, with only a few small platform-specific routines being necessary:

  • Clearing the screen.
  • Pausing for "a short while".
  • Reading a line of input from the user.
  • Sending a $-terminated string to the console.
  • etc.

My feeling was that I could replace the use of those CP/M functions with something custom, and I'd have done the 99% of the work. Of course the devil is always in the details.

Let's start. To begin with I'm lucky in that I'm using the pasmo assembler which is capable of outputting .TAP files, which can be loaded into ZX Spectrum emulators.

I'm not going to walk through all the code here, because that is available within the project repository, but here's a very brief getting-started guide which demonstrates writing some code on a Linux host, and generating a TAP file which can be loaded into your favourite emulator. As I needed similar routines I started working out how to read keyboard input, clear the screen, and output messages which is what the following sample will demonstrate..

First of all you'll need to install the dependencies, specifically the assembler and an emulator to run the thing:

# apt install pasmo spectemu-x11

Now we'll create a simple assembly-language file, to test things out - save the following as hello.z80:

    ; Code starts here
    org 32768

    ; clear the screen
    call cls

    ; output some text
    ld   de, instructions                  ; DE points to the text string
    ld   bc, instructions_end-instructions ; BC contains the length
    call 8252

    ; wait for a key
    ld hl,0x5c08        ; LASTK
    ld a,255
    ld (hl),a
wkey:
    cp (hl)             ; wait for the value to change
    jr z, wkey

    ; get the key and save it
    ld a,(HL)
    push af

    ; clear the screen
    call cls

    ; show a second message
    ld de, you_pressed
    ld bc, you_pressed_end-you_pressed
    call 8252

    ;; Output the ASCII character in A
    ld a,2
    call 0x1601
    pop af
    call 0x0010

    ; loop forever.  simple demo is simple
endless:
    jr endless

cls:
    ld a,2
    call 0x1601  ; ROM_OPEN_CHANNEL
    call 0x0DAF  ; ROM_CLS
    ret

instructions:
    defb 'Please press a key to continue!'
instructions_end:

you_pressed:
    defb 'You pressed:'
you_pressed_end:

end 32768

Now you can assemble that into a TAP file like so:

$ pasmo --tapbas hello.z80 hello.tap

The final step is to load it in the emulator:

$ xspect -quick-load -load-immed -tap hello.tap

The reason I specifically chose that emulator was because it allows easily loading of a TAP file, without waiting for the tape to play, and without the use of any menus. (If you can tell me how to make FUSE auto-start like that, I'd love to hear!)

I wrote a small number of "CP/M emulation functions" allowing me to clear the screen, pause, prompt for input, and output text, which will work via the primitives available within the standard ZX Spectrum ROM. Then I reworked the game a little to cope with the different screen resolution (though only minimally, some of the text still breaks lines in unfortunate spots):

The end result is reasonably playable, even if it isn't quite as nice as the CP/M version (largely because of the unfortunate word-wrapping, and smaller console-area). So now my repository contains a .TAP file which can be loaded into your emulator of choice, available from the releases list.

Here's a brief teaser of what you can expect:

Outstanding bugs? Well the line-input is a bit horrid, and unfortunately this was written for CP/M accessed over a terminal - so I'd assumed a "standard" 80x25 resolution, which means that line/word-wrapping is broken in places.

That said it didn't take me too long to make the port, and it was kinda fun.

| 4 comments

 

Removing my last server?

5 February 2022 09:00

In the past I used to run a number of virtual machines, or dedicated hosts. Currently I'm cut things down to only a single machine which I'm planning to remove.

Email

Email used to be hosted via dovecot, and then read with mutt-ng on the host itself. Later I moved to reading mail with my own console-based email client.

Eventually I succumbed, and now I pay for Google's Workspace product.

Git Repositories

I used to use gitbucket for hosting a bunch of (mostly private) git repositories. A bad shutdown/reboot of my host trashed the internal database so that was broken.

I replaced the use of gitbucket, which was very pretty, with gitolite to perform access-control, and avoid the need of a binary database.

I merged a bunch of repositories, removed the secret things from there where possible, and finally threw them on a second github account. GPG-encryption added where appropriate.

Static Hosts

Static websites I used to host upon my own machine are now hosted via netlify.

There aren't many of them, and they are rarely updated, I guess I care less.

Dynamic Hosts

That leaves only dynamic hosts. I used to have a couple of these, most notably the debian-administration.org, but that was archived and the final commercial thing I did was retired in January.

I now have only one dynamic site up and running, https://api.steve.fi/, this provides two dynamic endpoints:

  • One to return data about trams coming to the stop near my house.
  • One to return the current temperature.

Both of these are used by my tram-display device. Running these two services locally, in Docker, would probably be fine.

However there is a third "secret" API - blog-comment submission.

When a comment is received upon this blog it is written to a local filesystem, and an email is sent to me. The next time my blog is built rsync is used to get the remote-comments and add them to the blog. (Spam deleted first, of course).

Locally the comments are added into the git-repository this blog is built from - and the remote files deleted now and again.

Maybe I should just switch from writing the blog-comment to disk, and include all the meta-data in the email? I don't wanna go connecting to Gmail via IMAP, but I could probably copy and paste from the email to my local blog-repository.

I can stop hosting the tram-APIs publicly, but the blog comment part is harder. I guess I just need to receive incoming FORM-submission, and send an email.

  • Maybe I host the existing container on fly.io, for free?
  • Maybe I write an AWS lambda function to do the necessary thing?

Or maybe I drop blog-comments and sidestep the problem entirely? After all I wrote five posts in the whole of last year ..

| 2 comments