DEV Community: Alex Esoposting

Designing an Elm component

Alex Esoposting — Sat, 20 Aug 2022 14:42:23 +0000

In my previous article I have told you a lot of theory about Elm, but to make you see why I like it so much I want to walk you through the process of designing a component for one of my projects. Hopefully you will see how the design choices are influenced by the language and reflected in the code.

Goal

What I'm trying to build

I'm a player of Neptune's Pride - an online strategy game set in space where players fight over stars. I am hosting a tool that lets players record their games and renders animated replays (timelapses) of them in an .mp4 format. I want to use Elm to provide timelapses online, animated as an SVG controlled by a slider.

View

How I want the user to see it

There are tree core elements of Elm application design: model, view and controller. View is the part that translates your model into DOM elements that your user can see and interact with, so to design the view it's best to try and imagine what you want your users to experience. This is how I saw it for the online timelapse tool:

The user enters the online timelapse page with a button from a game's page.
The user sees a loading screen.
The screen changes to contain an SVG picture of the starting state of the game and animation controls.
The user can control which tick of the game is displayed with a slider.
The user can play and pause the animation using a button.

These user stories will not only describe the design of the view, but also be a starting point for designing the model, and help with the controller. At this point I usually draw myself a sketch of how the page will look like, and I keep adjusting it as I progress through the design process.

Don't put too much effort into your sketches

Model

Turining your view into data

With some user stories and a rough idea of the layout of the component I proceed to design the model: a data structure that will hold the state of the app at all times. This can be done very well using Elm's type system, so I create a file scratchpad.elm to hold my notes before I create the project. From the user stories we see that the model should contain:

Timelapse data (possibly unloaded)
Currently displayed tick
State of the animation (Played/Paused)

Which translates to the following Elm code:

type alias Model =
  { stars : Stars
  , tick : Int
  , playing : Bool
  }

This model is incomplete. First of all it will definitely get expanded as the project progresses, but for now it uses a type Stars that has not been defined. In my game recorder I store data about stars by assigning each star a list of pairs indicating when the star got captured by which player. Lets use this representation here, but also take into account the possibilities that star data may have not yet been loaded or that loading may have failed with some error message:

type Stars
  = Stars ( List Star )
  | Loading
  | Failed String

type alias Star =
  { x : Float
  , y : Float
  , owners : List ( Int, Int )
  }

This is enough of a model for now. Knowing what data we operate on and what our users might want to do with it let's proceed to the controller design.

Controller

What makes stuff happen

This is the part that is responsible for reacting to events and updating the model. In Elm the controller is represented by an update function that takes messages generated by the runtime system, but I also consider the initial processing to be a part of the controller.

First lets tackle the messages. They represent events that our application might update on, which are: downloading star data finishing, time progression, manually changing the slider and pressing the play/pause button. This leaves us with a small Msg type, and we don't have to worry about implementing reactions to these messages at the design level.

type Msg
  = SliderChange Float
  | Tick Time.Posix
  | PauseTrigger
  | GotStars (Result Http.Error Stars)

The init function can take some arguments and must return a tuple containing an initial model and a command to execute by the runtime. The initial model is straightforward for now:

defaultModel : Model
defaultModel =
  { stars = Loading
  , tick = 0
  , playing = False
  }

The command to be executed should fetch the stars info for us, so we need an address to fetch it from. The address will be passed as an argument to the init function so that we can reuse the same static application for animating many different games. The resulting function is as follows:

init : String -> ( Model, Cmd Msg )
init sourceURL = ( defaultModel, getStars sourceURL )

This concludes the design of the controller. We can proceed to make the application!

Design complete!

That's it for now

In this article I have shown an example of my design process when working with Elm. I hope you now have a better idea of how Elm encourages and supports design of the app with its application design model and rich type system. In the next article I will create an Elm project and start converting this scratchpad code into an actual working page component. See you soon!

Elm: a good frontend language?

Alex Esoposting — Thu, 11 Aug 2022 06:18:23 +0000

Recently a friend recommended me Elm, a pure functional language for developing web applications. I'd like to compare it to JavaScript and show how the functional paradigm can work in practical applications.

If you need a refresher on what functional programming is check out my previous blog post.

Still just JavaScript

Everything is JavaScript...

JS is the only* language standard that is supported by all major browsers and allows for interactive apps. If you want something except from a static HTML you need to use JS. To write an app in another language you need to compile it to pure JS, like many web languages do. Most of them, like TypeScript, are based on JS and offer limited improvement over JS problems. Elm is something entirely different, having no trace of JS's imperative syntax and error prone type coercion, but still compiles to JS in the end to be run by the browser.

*Web assembly is starting to gain popularity, but it's still in developement

No runtime errors

Everything works

By being a pure functional language Elm can guarantee that no matter the time of day, the randomness or the user input, the app will always be ready for whatever comes and will process it without breaking. That doesn't mean any input is valid, just that invalid input will produce error values, which must be explicitly handled in the code or else it won't compile.

Let's take string to number conversion for example. In JS there are multiple ways of doing it: Number(x), parseInt(x), +x among others. All of them return a value of type "number", but they can actually output what is literally Not a Number, and in case of +x they may even just silently ignore invalid strings and return 0. This may lead to some problems in later stages of the program which will be hard to debug because of those silent errors. Solutions to this include a separate check if the string is numeric, which arguably should be a part of the parsing function, and checking for NaNs every time you handle a "number", which should not be necessary because NaN is Not a Number.

In contrast, Elm's String.toInt function returns a Maybe Int type, which can have values Nothing or Just Int. This is an explicit sign: "Something can go wrong here and requires handling!". This value can be then passed along as Maybe Int, or it can be branched on and some handling can be done in case of Nothing, and in case of Just Int just the Int portion can be returned. In fact this pattern is so common that there already are functions for handling Maybe values, the most obvious one being withDefault which takes a default value and substitutes it in case of Nothing. This is again explicit and allows more control over the behaviour of the process instead of silently passing erroneous values and creating an undebuggable mess.

The Elm Architecture

That apparently everyone uses?

Being a pure functional language Elm can't have functions that rely on data outside their inputs or change data outside their outputs. This means working with time, randomness, user input and DOM shouldn't be possible to implement. Elm solves this problem in a very elegant way: you don't write the entire application. It has a runtime system, and your job as a programmer is to provide this system with three things: the initial application state represented in Elm values, a function from state to DOM that will be displayed to the user, and another function from the state and messages that the user may send to a new, updated state. The runtime then renders the page using the initial state and the view function and handles any user interaction by sending appropriate messages that you defined to the update function. All impurity is abstracted to the runtime, so the user can stay in the pure language of Elm.

There are multiple benefits from this. First of all getting to stay pure guarantees no runtime errors. All the input data comes as messages that you defined and are forced to handle in the update function. Pure functions also benefit heavily from compiler optimisation and caching results: even though the view function is called after every update the code is compiled to only calculate parts of the page that changed which keeps the system efficient.

The Elm architecture also serves as a good design pattern that makes thinking about your code easier. It makes you make a model - a representation of the application state in terms of in-language values - and consider what states your app can be in and what can change about it. It forces you to consider all transitions of this state: what to show the user when the additional content loads? How to react when it fails to load? All this is turned into messages that have to be handled or the code doesn't compile. According to the Elm website many JS frameworks and other application languages have adopted the Elm architecture, more or less openly. It's a design pattern that any language can benefit from.

Conclusion

I like Elm

I hate JavaScript and believe that it's a fundamentally badly designed language, so in my personal projects I have been going out of my way to minimize its use. Elm offers a much better designed alternative despite also having flaws. I can't say about enterprise use, but I definitely recommend Elm for the interactive components of your pages, and If you want a taste of it I will be showing how I designed the online timelapse visualisation for one of my projects in my future posts. Stay tuned!

What is functional programming?

Alex Esoposting — Tue, 02 Aug 2022 17:26:20 +0000

I'm planning on doing a couple of posts on the language Elm and why it may be better than JS, but to fully understand what happens in Elm you need to know some things about the functional paradigm - a clean view on what programming is, designed with mathematical perfection.

Functions

Functions everywhere.

As the name implies functional programming is all about functions. Everything is done using them, and applying the function to a parameter is the fundamental operation. In imperative languages like Python, C++ or JS, to apply a function foo to x you use parenthesis: foo(x), but in functional languages it's sufficient to write the function next to the value: foo x. Parenthesis come up when applying a function to another function's result. For a bigger example:

# Imperative:
foo(x, bar(y), baz)

vs.

-- Functional:
foo x (bar y) baz

This syntax is cleaner and more readable when most of the program is function application: not even commas are required to separate arguments.

Everything in the functional paradigm is a function. Even normal operators like + or * are considered functions. In most functional languages you can put parenthesis around them and apply them like any other function:

(x + y) = (+) x y
(x * y) = (*) x y

Functions can be passed as arguments and assigned to variables. This allows for some powerful operators that I will discuss in later posts.

Purity

No side effects allowed

Functional languages deal with pure functions, which are not allowed to alter any internal or external state. This means a pure function's output can only depend on its inputs, not on time of execution or randomness. It can also not affect outcomes of other operations in any way other than through returning values.

This may seem as overly restrictive: after all the screen is an external state, and how are we supposed to write an application that doesn't depend on time? Most functional languages have their mechanisms for dealing with those problems, usually behind the scenes, without introducing impurity to the programmer's code.

Purity has its benefits: a pure function for a given input will always return the same output, so there may not be a need to recalculate it later. The execution of a part of the program never depends on anything outside of it. This opens opportunities for optimizing compilation and makes thinking about code way easier.

Strong Types

Like in C or Java, but good.

Another property of most functional languages is that they are strongly typed. What this means is that all data flowing through the program has to be assigned a type, like String or Int or Float. Every value traveling along some path in the program has to always have the same type.

In languages like C++ or Java this leads to a ton of unnecessary type annotations that are annoying and obscure the meaning of the code. In functional programs types can almost always be inferred from their surroundings, lifting the burden of attaching labels to everything from the programmer.

Type inference means that from knowing what type the basic literals are (like 21 or "Hello"), and what types the basic operators take and return the compiler can reason about types of other values and functions, in theory requiring almost no type annotations. It's still a good practice to annotate your function definitions so that the compiler can warn you when the type you want doesn't match what is inferred.

Algebraic types

We need to go deeper...

In imperative languages data types reflect how a value is stored in computer memory: int is a four byte number, string is an array of bytes and float is a floating point number as described by The Standard. In functional languages data types reflect what the value represents. You have basic types that all have some implementation-defined representation in memory, but you can also define your own types, usually on top of existing ones.

Types are defined with constructor functions. For example Boolean may be defined as:

type Boolean = True | False

This means the Boolean type can be constructed by either True or False constructors. Neither of them take any arguments, so they always return the same values which can later be interpreted as "true" and "false". A more complex example that uses arguments is:

type Webpage
  = Loading
  | Loaded Html
  | LoadingError String

This represents the fact that a Webpage may be one of three:

Loading, in which case no additional info about it is available,
Loaded, in which case it has a value of type Html to display,
LoadingError, in which case there's an error message available describing what went wrong. This allows for precise modelling of what your data means and can possibly be.

Pattern matching

Elegant conditionality

Algebraic types naturally represent options available to a given value, so the most used conditional construction in functional programming is one that branches based on the constructor. The usual syntax looks like this:

case value of
  Some pattern -> result
  Other pattern -> different result

Going with the Webpage example we could construct a function that takes a Webpage value and returns a rendered view like this:

renderPage : Webpage -> Rendered
renderPage page =
  case page of
    Loading -> renderText "Loading..."
    Loaded html -> renderHtml html
    LoadingError message -> renderText message

This may be a bit to take in, so let's go through it line by line:

renderPage : Webpage -> Rendered
This is how type annotations look like for functions. renderPage is a function that takes a Webpage and returns Rendered.
renderPage page =
Start of the function definition. page is the function argument.
case page of
Start of a case expression.
Loading -> renderText "Loading..."
If page was made with the Loading constructor display the loading text.
Loaded html -> renderHtml html
If page was made with the Loaded constructor render it's parameter as HTML.
LoadingError message -> renderText message
Finally if page was made with the LoadingError then display the error message.

You can see how a case expression can be used to deconstruct the value and assign its contents to variables (html and message in the example). This way of branching can also make sure that the program never breaks, because every possibility has to be accounted for. Any errors have to be explicit (like LoadingError in the example) and passed around openly as values.

Sidenote: Type theory

Very rough explanation.

Algebraic data types are such a powerful concept that you don't need any builtin types to make programs. You can define numbers and lists and operate on them without referencing any existing types. I have already shown the easiest example, the Boolean type, but let me explore this further.

The second simplest example is natural numbers. If you think about it, any natural numbers can be defined as either zero, or a successor of some other number. This translates to:

type Nat = Zero | Succ Nat

This type is defined recursively, which lets us define an infinite amount of numbers with a finite set of symbols. With this whenever you encounter a number you can split the logic into two cases: a simple one when the number is zero, and a recursive one when it isn't. For example addition would work like:

add : Nat -> Nat
add x y =
  case x of
    Zero -> y
    Succ x' -> add x' (Succ y)

When adding zero to y the answer is just y, and when adding a successor of something the Succ can be "moved" to y, decreasing x which guarantees that it finally reaches the base case.

As a closing remark I will add an example of a List type with a map function that transforms each element of the list. This example has some more advanced notation, so don't worry if you don't get it.

type List a = Empty | Cat a List

map : (a -> b) -> List a -> List b
map func list =
  case list of
    Empty -> Empty
    Cat head tail -> Cat (func head) (map func tail)

Conclusion

I'm back to writing!

I hope this gave you a vague idea of what you could stumble upon when dealing with functional languages. If you want some more concrete and in-depth examples look forward to my series on the programming language Elm. I barely have any formal education in functional programming and category or type theory, so if you spot any mistakes please notify me in the comments. See you soon!

Quick minilanguage to steer a submarine with Quackery

Alex Esoposting — Fri, 03 Dec 2021 11:46:00 +0000

Every year I try to solve Advent of Code with some esolang for as long as possible. This year's language of choice was Quackery: a cute concatenative language based on Lisp and Forth, and when I saw the second puzzle I knew that language was perfect.

The problem

Puzzle for day 2 of this year's AoC is about steering a submarine and figuring up what coordinates you end up on. Input is a set of simple commands like this:

forward 5
down 5
forward 8
up 3
down 8
forward 2

Each command consists of one of three directions: forward, up or down, and a number indicating how far in this direction to swim. The important note is that we care about depth and horizontal distance, so down would increase depth, and up would decrease it.

The idea

A standard approach to such problem would be to iterate over the input string word by word and changing some state based on what words are read. For anyone accustomed to concatenative languages this should sound familiar: it's exactly what the interpreter does to execute code! Given that one of the rules of concatenative programming is to never write the same code twice we should use the interpreter itself to interpret our input for us.

About Quackery

Quackery is a stack based concatenative language. Every word executed interacts with the main Data Stack: numbers put themselves on the stack and operators and user defined words act on top values of the stack. There are plenty of stack shuffling words to arrange the top of the stack for other operators. Most notable are:

dup - duplicate the top of the stack
drop - remove the top of the stack
swap - swap top two values on the stack

The rest will be explained when used.

The implementation

The Quackery inerpreter already recognises numbers so the only thing we need to define are direction words: forward, up and down. In addition to that we need some state that these words would update, which I chose to be two numbers on the stack indicating depth and horizontal distance.

To make things nicer I will define a state constructor word which just puts two zeroes on the stack:

( state: depth, horizontal-distance )
[ 0 0 ] is new-state ( -- state )

Parenthesis in Quackery indicate comments, just as in Forth.

up and down should take a number that follows them and add or subtract from the second item on the stack:

[ swap ]'[ + swap ] is down ( state 'n -- state )

[ swap ]'[ - swap ] is up ( state 'n -- state )

]'[ is used to take the item following the word currently executed, so it would be the number after up or down.

forward is a bit tricky because it's already defined as a builder word in Quackery, and redefining builders requires some trickery. I need to first define a normal word with the behaviour I want forward to have and then redefine the builder forward to build that behaviour:

[ ]'[ + ] is forward-behaviour ( state 'n -- state )

[ dip [ ' forward-behaviour
        nested join ] ]      builds forward ( [ $ -- [ $ )

Now that the interpreter can understand our input as source code we just need to run it on said source code:

[ dip new-state
  quackery * ]   is solve-puzzle ( input -- n )

dip takes the top item off the stack, runs the operator that follows it (in this case new-state) and puts the item back on the stack. Coordinates are multiplied at the end to produce the answer that AoC will accept.

Full code, along with the second part of the puzzle, can be found in my AoC github repo.

Conclusion

This solution is a very minimalistic way of showing how easy and convenient it is to implement new languages in stack languages. This is a very useful feature because you don't need to implement a whole new interpreter, just define what each command does and tell the user what commands you support.

If you want to fully understand the code I wrote there check out The Book of Quackery, a 100 page tutorial and documentation for the Quackery language written by it's author and available for free as a PDF. It's very newbie-friendly.

Factor app - http requests

Alex Esoposting — Mon, 08 Nov 2021 13:58:32 +0000

The app I described in the previous tutorial is supposed to fetch data about a game from some server. Before writing any code to process this data it would be nice to know what kind of data we're dealing with and how to find it.

Target API

Where we get the data from

The server we're trying to talk to is a simple HTTPS server with an impossible to remember address of a766-95-160-157-211.ngrok.io. Most of its endpoints provide nice HTML pages, very useful for the browser but entirely useless for us. What we need can be found under /api/game/<game-nr> which is supposed to provide us with all data relevant to the given game number in JSON format.

To summarise: we need to make an HTTP GET request to the given address and receive a JSON in return.

Our toolbox for today

Factor http.client and json.reader vocabularies

Communicating over HTTP can be a huge pain because of the amount of things you need to worry about like headers or where to put data into the request. Fortunately Factor will do most of that for us so that we only need to use exactly one word from each of these libraries.

For GET requests there is a word http-get, but it's not what we need there as it will raise an error if the request is not successful. http-get is actually a wrapper over the word htpp-get* which just performs a request and returns whatever the outcome is.

To decode JSON into meaningful Factor objects there is a word json> which converts a JSON string to a Factor object. If the request is successful then http-get* leaves returned data as a byte array. We then just need to convert it to a string to be able to extract Factor objects out of it. Our json extracting pipeline is two words: >string json>.

Putting knowledge to use

Actual code time!

The word http-get* has a stack effect ( url -- response data ). To modify it to fetch game data we need to provide it with the correct url joined with the game number.

USE: http.client

CONSTANT: api-url "https://a766-95-160-157-211.ngrok.io/api/game/"

: get-game* ( game-id-string -- response data )
    api-url prepend http-get*
;

Now that's not enough. Notice that get-game* returns two values: response and data. If everything is ok then code slot of the response will be 200 and data will be a byte array representing a JSON with game data. A lot of things can go wrong though: the client may be offline, the server may be offline, the game id may be incorrect and so on.

For these cases we need a wrapper word for get-game* that will check for any HTTP errors. That word will then extract any relevant information - either game data or HTTP error code - and return it for further interpretation by the app. HTTP error codes start from 400 and go up so this check is very simple. If it's lower than 400 we can use the words >string json> to convert response data to string and then to a Factor object. The function should also return a flag indicating whether the request was successful.

USE: json.reader

: get-game ( game-id-string -- error/game-object f/t )
    get-game* swap code>> dup 400 <
    [ drop >string json> t ]
    [ nip f ] if
;

Final vocabulary

Just code

I put this code in the nptimelapse.api vocabulary generated with scaffold-work.

! Copyright (C) 2021 Aleksander Sabak.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel strings accessors http.client json.reader ;
IN: nptimelapse.api

CONSTANT: api-url "https://a766-95-160-157-211.ngrok.io/api/game/"


: get-game* ( game-id-string -- response data )
    api-url prepend http-get*
;


: get-game ( game-id-string -- error/game-object f/t )
    get-game* swap code>> dup 400 <
    [ drop >string json> t ]
    [ nip f ] if
;

Conclusion

A short chapter, wasn't it?

Fetching data from a HTTP server turned out to be quite easy given Factor's high-level vocabularies. I chose the easiest part for the beginning though, so don't expect everything to go as smoothly from now on. We are about to get into some UI stuff, and that's never easy in any language.

Factor app - Preparation

Alex Esoposting — Sun, 24 Oct 2021 09:18:30 +0000

My previous posts covered the basics of programming in Factor. Tat was necessary information to start playing around with the language and you wouldn't go far without it. Now that I've laid a foundation it's time to set a goal and learn towards it.

The goal

What it is and why it's that

My goal for this part of the tutorial is to make a desktop app that interactively visualises history of games of Neptune's Pride. You don't need to know anything about NP except from that it's a game about conquering stars in space. I've chosen this project for a couple reasons:

It touches a couple useful aspects of programming in Factor, http requests and UI among others.
There is an easily accessible source of online data to test the project.
I wanted to do it anyway 😋

It's both something I am competent to explain and something I have motivation for doing. I believe that things learned during this project are also useful in other applications.

What we will learn

I'm going to be learning too!

The project tackles two big subjects I haven't covered yet: UI and http communication. The latter will only be required on a basic level so that's what I will start with. For UI Factor offers an extensive gadget-based system that I will spend a lot of time exploring and explaining, and I hope I will manage to get pretty deep into it in the process. Gadgets are also tied closely to models which are worth at least one article by themselves.

As often as possible the articles will contain actual progress on building the app, so there will be no shortage of practical examples to show how to make use of each vocabulary or concept.

Conclusion

That was a short one

I want to make something and share what I learned in the process, which is the main premise of this blog. All source code will be available in the Esoposting Examples repository on github as soon as the next article is published at some point in the next two weeks. Hope to see you there!

Factor pt. 4 - Vocabularies

Alex Esoposting — Sat, 16 Oct 2021 11:41:59 +0000

Over the last three tutorials I dumped a lot of information at you, explained it semi-coherently and only gave a couple practical examples. Now is the time to fix this all at once: this article is all about a big practical example that will touch on everything I have already covered and expand on it a bit. Today we are writing our own Factor vocabulary.

What is a vocabulary?

A bit of theory before the practice

In most languages only the most essential part of available functionality is present by default and if you need any specialised functions or objects you need to import or #include or whatever your favourite language does to load features from an external file. Most languages call those extensions "libraries" or "packages", but because in Factor everything is a word these files are just lists of words: vocabularies.

If you followed the examples I gave on your computer you may have already used vocabularies. Whenever the Listener encounters a word that is in an unloaded vocabulary it will throw an error and present options, one of which will be to use the library including that word. It's useful to not load all libraries by default because it would take up a lot of space to compile all Factor libraries, and some of them use conflicting word names (for example range is in math.ranges, math.statistics and model.range).

You can order Factor to load vocabularies with the words USE: and USING:. Their syntax is as follows:

USE: vocab-name
USING: vocab-names... ;

Usually a Factor program will have a big USING: line at its start that loads all the vocabularies it needs. Words you define in the Listener go into the scratchpad vocabulary which exists as long as the Listener is open.

Creating the vocabulary

Let's get down to business

A user created vocabulary usually sits in the "work" folder in your Factor installation directory. Vocabularies are stored in plaintext source files so in theory you could just find the folder and create the required structure yourself, but Factor conveniently has a vocabulary for defining vocabularies so it can do the hard work for us.

Before we do anything we need to USE: tools.scaffold because this vocabulary will not be automatically suggested by the Listener. I will be making a library-managing vocabulary, so I will call it "esoposting-library". To scaffold a library push it's name as a string onto the stack and call scaffold-work. Now you can do it again, but call edit instead and we will be ready to start.

In summary this is what you should type into the listener to create and edit your vocabulary:

USE: tools.scaffold
"esoposting-library" scaffold-work
"esoposting-library" edit

At this point Factor may ask you for your editor of choice which should launch immediately, provided it is installed. The initialised file should look like this:

! Copyright (C) 2021 Your name.
! See http://factorcode.org/license.txt for BSD license.
USING: ;
IN: esoposting-library

Feel free to substitute your actual name for "Your name" in the header.

Designing the vocabulary

Design first, code second.

Before coding it's good to have an idea what the code is for and how it should work. My idea is a program to keep track of my personal library. It should support adding new books and removing old ones, searching for the book by title, and borrowing books: keeping track of whether a book is currently borrowed and to whom and how many times it has been borrowed. I should also be able to see a list of books I own in alphabetical order.

A more serious approach would look at Factor's database support, but I'll settle on a data structure holding the books that will sit atop the stack. Book management words will act on that object and if I choose the structure well they should mostly turn out to be aliases of already existing words. Because I want the books to be searchable by title I will implement the library with a hashtable.

Classes

What objects do we need?

From the problem specification two object types are apparent: books and the library containing them. Let's start from the simpler one.

Book

What information should a book carry? From what was explained earlier we need to know a book's title, how many times it was borrowed, is it borrowed now and if so then who borrowed it. In addition to that I want know the book's author and genre. That would give us 6 fields for class book.

Not all of these have to be slots of the book tuple though. Info on whether the book is borrowed and by whom could be stored by having a false value when the book is in the library and a string with the borrower's name if it's out. That is actually its own type of data called "maybe string". Additionally the title will be stored as a key to the library hashtable, but I want the redundancy of keeping it in the tuple as well. That way every word that uses a book can automatically use its title.

The final book tuple class declaration looks like this:

USING: classes.maybe math strings ;
TUPLE: book
    { title string read-only }
    { author string read-only }
    { genre string read-only }
    { times-borrowed integer }
    { borrower maybe{ string } }
;

A "maybe string" class in Factor is written as maybe{ string } and that's the type of the borrower slot. Also note that we already need to use some vocabularies. All of them should be gathered in the third line of the generated vocabulary header. To check if everything works correctly call "esoposting-library" reload in the listener.

Library

The library object doesn't need to be anything more than a collection of books searchable by the title. We can get away with not implementing a separate class for this purpose because a hashtable does exactly what we want. A drawback of not declaring a new class is that words we define for working with the library will also attempt to work with other objects if used incorrectly which can lead to hidden bugs and unhelpful error messages.

In our case the project is too small for that to matter. If our vocabulary was supposed to be a part of some bigger application it would be a good practice to define a library class tuple, but it would be an overkill for this purpose.

Words

A top-down approach

I have already mentioned in a previous article that when writing code I like to start with the top level words I need and see what other words will be necessary to implement them. For our application there will be a few of those.

Creating the library

First the user needs to be able to init-library to get the library object and not need to care about how it's implemented:

USE: kernel
: init-library ( -- library )
    H{ } clone
;

H{ } is syntax for a default empty hashtable, and clone makes sure every call to init-library creates a new hashtable and not just a reference to the same one. It's a preferred way of initialising hashtables if you don't need to specify capacity.

Then an add-new-book word would be nice that would take a title, author and genre, create a new book and add it to the library:

USE: accessors
: add-new-book ( library title author genre -- library )
    <book> swap over
    title>> swap
    [ set-at ] keep
;

To add a key-pair value to a hashtable you use the word set-at which stack effect is ( value key assoc -- ). The first problem is that both value (the book) and key (the title) have to be below the assoc (the library hashtable), and this is dealt with by some stack shuffling. The second problem is that set-at consumes the hashtable, but it can be remedied by enclosing it in a quotation and calling via the keep combinator which saves the top value, executes the quotation and restores the saved value.

The third problem with add-new-book is that we didn't define the constructor <book> yet, so let's do that. It needs to take the initial data (title, author and genre), fill the default values of the other slots and use a boa constructor to make a book:

: <book> ( title author genre -- book )
    0 f book boa
;

Accessing the library

After adding all the books to the library it would be nice to be able to interact with them. From what I specified in design we need words for searching, deleting and borrowing books. Let's also make them user friendly, so if I try to interact with a nonexistent book I get a warning message. For these I will use the print word from the io vocabulary which takes a string and displays it on the console.

To get a book from the library we need to pass it's title and the library itself to the generic word at:

USE: io
: find-book ( library title -- library book )
    over at dup
    [ "WARNING: a book of this title was not found!" print ]
    unless
;

at will not throw any errors when the book is not found, it will simply return f. This means we can check the returned value and warn the user unless the book was found.

To delete a book from the library we need the same information as when searching passed to the generic word delete-at:

: delete-book ( library title -- library )
    over at dup
    [ title>> over delete-at ]
    [ "WARNING: a book of this title was not found!" print drop ]
    if
;

Instead of simply deleting the book, which would work even if the book was not present, I check if the books exists beforehand so I can warn the user about it. The action they attempted was not carried out successfully, so they need to know that. Maybe they made a typo?

The final utility expected from this vocabulary is handling borrowed books. For this I will define two words: borrow-book and return-book that will adjust appropriate slots of the book's slot. In addition to that there are two new warnings: borrow-book should not work if the book is already borrowed, and the same for return-book and not borrowed books.

: borrow-book ( library title borrower -- library )
    [ drop find-book ] keep over    ! Fetch the book and warn if isn't found
    [ over borrower>>               ! If is found check if already borrowed
        [ "WARNING: the book has already been borrowed!" print 2drop ]
        [ >>borrower [ 1 + ] change-times-borrowed drop ]
        if ]
    [ 2drop ] if                    ! If not just do nothing
;

: return-book ( library title -- library )
    over at dup             ! Fetch the book
    [ dup borrower>>        ! If found check if borrowed
        [ f >>borrower ]    ! If borrowed return
        [ "WARNING: the book is not borrowed!" print ]
        if ]
    [ "WARNING: a book of this title was not found!" print ]
    if drop
;

Now hold up. Remember the guidelines? Whenever a definition is big enough that comments are needed to explain what is going on it's a sign that you need to factor something out.

Factorisation

The best practice of all

There is a big and obvious factor common to all words in our vocabulary: the "book not found" warning. It could be factored out using just find-book, but there is a better way. Let's define a combinator that will take the library, title and a quotation, call the quotation if the book is found and otherwise warn the user and do nothing:

: if-book-exists ( library title quot: ( book -- x ) -- library x|0 )
    [ drop over at dup ] keep
    [ "WARNING: a book of a given title was not found!" print ]
    if
; inline

This word, like all combinators, is and inline word. It means that before compiling all occurrences of it will be replaced with its body. This lets the compiler handle stack effects more efficiently and is required for most words that take quotations as arguments.

Let's now rewrite previous words in terms of this new combinator. Most of them will have a form of [ body ] if-book-exists.

: find-book ( library title -- library book )
    [ ] if-book-exists
;

: delete-book ( library title -- library )
    [ title>> over delete-at f ] if-book-exists
    drop
;

: return-book ( library title -- library )
    [ dup borrower>>
        [ f >>borrower ]
        [ "WARNING: the book is not borrowed!" print ]
    if ] if-book-exists drop
;

Returning the book takes an additional argument - borrower - but the body quotation's stack effect for if-book-exists must only take a book as an argument. To make this happen we need to construct a quotation that already contains the borrower. This brings us to the concept of partial application, or currying. It's a functional programming term which is most easily explained by example.

Addition is a function that takes two numbers and returns a number. But it can sometimes be useful to first supply it with only one argument and then use as a single argument function. For example if we know that a function that adds 5 to a number will be useful we can apply + to 5 getting [ 5 + ] which still requires one argument to return a number. This can be done with any function, producing a new function that takes one less argument and in Factor currying is achieved with the word curry.

value [ body ] curry
! S: [ value body ]

Now we need to make a quotation with stack effect ( book borrower -- x ) and partially apply it to the borrower producing a quotation with stack effect ( book -- x ) which is what we need for if-book-exists.

: borrow-book ( library title borrower -- library )
    [ over borrower>>
        [ drop "WARNING: the book has already been borrowed!" print ]
        [ >>borrower [ 1 + ] change-times-borrowed ]
    if ] curry if-book-exists drop
;

Final code

Works for me

This is how the "esoposting-library.factor" file looks like after all the words have been added:

! Copyright (C) 2021 Aleksander Sabak.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs classes.maybe io kernel math strings ;
IN: esoposting-library

TUPLE: book
    { title string read-only }
    { author string read-only }
    { genre string read-only }
    { times-borrowed integer }
    { borrower maybe{ string } }
;

: init-library ( -- library )
    H{ } clone
;

: <book> ( title author genre -- book )
    0 f book boa
;

: add-new-book ( library title author genre -- library )
    <book> swap over
    title>> swap
    [ set-at ] keep
;

: if-book-exists ( library title quot: ( book -- x ) -- library x|0 )
    [ drop over at dup ] keep
    [ "WARNING: a book of a given title was not found!" print ]
    if
; inline

: find-book ( library title -- library book )
    [ ] if-book-exists
;

: delete-book ( library title -- library )
    [ title>> over delete-at f ] if-book-exists
    drop
;

: borrow-book ( library title borrower -- library )
    [ over borrower>>
        [ drop "WARNING: the book has already been borrowed!" print ]
        [ >>borrower [ 1 + ] change-times-borrowed ]
    if ] curry if-book-exists drop
;

: return-book ( library title -- library )
    [ dup borrower>>
        [ f >>borrower ]
        [ "WARNING: the book is not borrowed!" print ]
    if ] if-book-exists drop
;

All libraries I am USING: are specified at the top in alphabetical order. I encourage you to try and play around with this vocabulary or whatever you came up with during this tutorial. Remember that you can prettyprint whatever is on the stack with ., even tuples.

Conclusion

That was a lot of writing

I hope you enjoyed this more practical tutorial. You are now ready to go and experiment with writing your own vocabularies. As always remember to make use of the built in help, there is a lot of knowledge to be found in the docs. This is the end of the first chapter of this series, next time I will discuss Factor's GUI vocabularies and start building towards making a desktop application.

Factor pt. 3 - Tuple classes

Alex Esoposting — Mon, 11 Oct 2021 12:40:30 +0000

From my previous tutorials you should already know how to operate with values on the stack and use sequences and combinators to make control structures. Data types paid a crucial role in both of these articles and are very important all over Factor. Today I will explain how Factor class system works based on tuple classes.

Object oriented programming

What I know about it

As far as I know OOP has been the most popular programming paradigm for some time. It's sometimes presented in opposition to Functional Programming, but although both of them are called "paradigms" they touch very different aspects of programming and can easily coexist. Factor manages to be both an object oriented and a concatenative language.

In OOP programs are based on the concept of "objects" that contain data (called fields) and code (called methods). These objects interact with each other and create new objects to perform required tasks. In most languages, including Factor, each object is an instance of a class which tells us its type, what data it holds and what we can do with it. For example 1 is an instance of an integer class. It represents a number and arithmetic operations can be performed on it. [ dup * ] is an instance of quotation. It holds a snippet of code and can be passed as an argument to combinators.

The thing that makes OOP so useful is that a program may define new classes with their own fields and methods. In Factor this is done using class tuples.

Defining a class

Just fields for now

Just as with most definitions in Factor a syntax word is used to create new tuple classes: TUPLE:. It's syntax is:

TUPLE: class-name slots... ;

Slots define fields of a class and can take one of the following forms:

name - A slot that can hold any object
{ name attributes... } - A slot that can hold any object with optional attributes
{ name class attributes... } - A slot that can hold an instance of the class with optional attributes

All this can sound very confusing, so let's look at an example. Let's define a class for books. Let's say each book shall hold information about it's title, author, genre, and how many times it has been borrowed. A tuple class for such books would be defined like that:

TUPLE: book
    { title string read-only }
    { author string read-only }
    { genre string read-only }
    { times-borrowed integer initial: 0 }
;

Each slot of this tuple can only store a particular type of data. It may seem like an unnecessary restriction, but it makes code more readable and can prevent some mistakes later on in the program. Three slots have a read-only attribute which means once they are set they can't be changed. The last slot has an initial: attribute which specifies what value it should have at the start

Instantiating classes

Making actual objects holding data

There are two basic constructor words in Factor that let you create class instances. The simpler one, new ( class -- tuple ), only takes a class as an argument and creates a new tuple with default slot values. Continuing the book example this is how to create a default book:

book new
! S: T{ book f "" "" "" 0 }

This book's prettyprint shows three empty strings and a zero respectively. To actually insert some information into that book we need to use the other constructor: boa ( slots... class -- tuple ). In addition to a class it requires values to be put into the slots by order of arguments - hence the name. For example to describe the toki pona dictionary one would write:

"Toki Pona Dictionary" "Sonja Lang" "Dictionary" 1 book boa
! S: T{ book f "Toki Pona Dictionary" "Sonja Lang" "Dictionary" 1 }

This time you can see contents of each of the slots initialised to a proper value. Disregard the f between the class name and the title: it's just a quirk of Factor literal tuple syntax. For more info visit \ T{ help.

Getters and setters

Working with objects

It is useful to change values of slots of a tuple after we created it. In our example that would be incrementing the times-borrowed slot whenever someone borrows a book. It would also be nice to extract values from the object to use in the program, that's what they are there for after all. To facilitate that each class in factor comes with a set of getter and setter words.

Getters extract values of slots from an object. They are defined automatically based on object's slot names. They consume the object and return the value of a corresponding slot.

slot-name>> ( object -- value )

For example to get a book's title you would use a word title>>.

Setters (as the name suggests) set a slot to a given value. They are also defined by the system for each class but only for writeable slots: those without the read-only attribute. They consume an object and a value and return the same object.

>>slot-name ( object value -- object )

The only writeable slot in our example is times-borrowed, and its setter is >>times-borrowed.

Setters are actually a wrapper over writers: lower level words that consume a value and an object and return nothing. They aren't commonly used in programs because it's usually more convenient to keep the object on the stack.

slot-name<< ( value object -- )

There is one more group of accessor words: changers. They take a quotation and an object and apply the quotation to the slot updating it.

change-slot-name ( object quot -- object )

A change-times-borrowed changer will be very useful to update the counter whenever a book is borrowed.

It is important to remember that most of the time if an object is copied (for example by dup) it is actually still the same object existing on the stack twice. If its slots are changed they are changed for all copies. This is called a "shallow copy" and it is common among high level languages. For those of you familiar with C++ it's comparable to copying a pointer.

Constructors

How to actually instantiate the class

Using only new and boa can get tedious, especially if data needs some processing before being put into slots or if you need some slots to have default initial values. In the book example whenever I get a new book it's times-borrowed value is always 0. Based on the premise that every time some code is about to be repeated it should be factored out I should write a better constructing word for my book class.

By convention constructors that create an instance of a class are called <class-name>. I want my constructor to have a stack effect of ( title author genre -- book ). A constructor word can be defined using new or boa, but in our case new is not useful: it will set read-only slots to their default values before my defined constructor can affect them. In this case a constructor using boa is quite simple: it only needs to add a default 0 and the class.

: <book> ( title author genre -- book )
    0 book boa
;

There is another constructor naming convention used in Factor: new-class-name. These constructors, apart from usual arguments, also take a class as an argument. They are mostly useful when subclassing which is out of scope of this tutorial so I won't be presenting an example.

Defining methods

How to make the same word do different things

Usefulness of methods in OOP comes from the fact that you don't need to know anything about the object except that it implements a particular method to use that method. For example if a program is to do something based on length of an object it can call a length word on it, not matter if it's an array, a quotation, a linked list or a vector. Calculating length works differently for each of these classes, but it is always invoked by the same name.

Usually this is implemented using the dot operator: class.method(). In Factor however there are no operators, only words. Instead of the dot operator Factor allows to define generic words: words that first check what type are their arguments and execute different functions associated with that type. I've already shown examples of generic words: all accessors are generic and they will work on any object that has slots of a certain name.

A generic words are declared with syntax words GENERIC: and GENERIC#:. The first one creates words that check the type of the top value on the stack. The other allows to specify which value to check. Their syntax is:

GENERIC: word ( stack -- effect )
GENERIC#: word n ( stack -- effect )

Notice that generic words have their stack effects defined at declaration. Each method connected to the same generic word must have the same stack effect. What is not declared is the body of the generic word. There will be multiple bodies defined for each class separately.

To attach a method to a generic word we need a syntax word M: with syntax:

M: class generic definition... ;

Stack effect of the word were declared with the word itself. This only serves to attach a method to a word and a class.

As an example let's define a method that would be called whenever someone borrows a book. It needs to take a book as input, increase its times-borrowed by one and not return anything. It's declaration and definition will look like:

GENERIC: borrow ( object -- )

M: book borrow
    [ 1 + ] change-times-borrowed drop
;

For now borrow only has effect on book objects, but it could be implemented for other classes in ways that make sense for these classes.

Conclusion

The tip of the iceberg

What I explained barely scratches the surface of what Factor can do with classes. It is heavily based on them and even though you can do without this knowledge you will be using classes without knowing. This article hopefully shown you enough that you will be able to noticed Object Oriented features and start using them in your own programs. Next time I will be explaining vocabularies.

Factor pt. 2 - Sequences and Control Structures

Alex Esoposting — Sun, 03 Oct 2021 15:18:17 +0000

In the first part of the tutorial I have shown how to use Factor words to put numbers on the stack, shuffle them and perform arithmetic operations on them. I also presented how you can define your own words if you want to reuse code often. All of this only involved numbers on a stack, but Factor can do much more than that. Today I will show you basic sequence types and how to use them for flow control, but first I need to cover something I forgot to mention in the previous article.

Boolean values

And operations

Factor recognises two boolean values: t for true and f for false. In addition to that f is a general value representing lack of other suitable values like Nil or None in other languages, and any other value will be interpreted as t in tests and boolean arithmetics. Factor provides all standard boolean arithmetics operations: not, or, and and xor. Words or, and and xor don't convert their inputs to booleans for testing so their output can also be non-boolean (this behaviour is out of scope of this series, but if you want to know more, check their respective help pages for more information). For the sake of clarity I will only be using them for operations on booleans, but remember that any value that is not f is considered true.

t t and f or t xor
! S: t

Numbers can be compared to produce boolean values:

3 5 < 3 5 > 0 0 >=
! S: f t t

With that out of the way let's proceed to sequences.

Quotations

Lambdas, anonymous functions, etc.

The most commonly used sequence type in Factor is a quotation which stores a series of words. The word that creates quotations, as well as most other collections, is a syntax word. Syntax word for literal quotations is [ with syntax:

[ elements... ]

Note spaces separating brackets from the elements.
Quotations store words for later execution on the stack. You can think of them as anonymous functions or lambdas if it helps you.
Words that operate on quotations are called combinators and control structures are implemented using them.

The simplest combinator is call which simply executes contents of the quotation on top of the stack.

[ 2 4 5 + ] call
! S: 2 9

Way more useful are the cleave combinators: bi, tri and cleave. They take some quotations and execute them one after another on separate copies of the stack element that is just beneath them. bi works with two quotations, tri with three and cleave works with a sequence of quotations.

3 [ 2 + ] [ 1 - ] bi
! S: 5 2
2dup

3 [ 2 + ] [ 1 - ] [ 4 * ] tri
! S: 5 2 12
3dup

3 [ [ 2 + ] [ 1 - ] [ 4 * ] [ dup * ] ] cleave
! S: 5 2 12 9

Note: I used a quotation containing quotations for cleave but normally an array of quotations is used instead.

If you have the Listener handy I encourage you to try experimenting with the cleave combinators, they are used all the time and can let you skip some janky stack shuffling. Also make sure to take a look at their help pages, as well as some similar words like 2bi or bi@. Help is invoked by executing \ bi help.

Control flow

Using combinators

Factor has combinators that can serve the functions of standard control flow structures: if-else, while, for and for-each. Let's first focus on the first three, as for-each requires other sequences and I will touch upon it later.

If-else behaviour is achieved using words if, when, unless or any of the other conditional combinators. Word if expects a flag (t or f) and two quotations. The bottom one will be called when the flag is true, else the top one will be executed:

5 3 f [ + ] [ - ] if
! S: 2

It is important that both quotations have the same stack effects or the compiler will not be able to unambiguously derive the stack effect of the construction and will throw an error. when and unless are variants of if with no false or true quotations respectively.

3 t [ 6 + ] when
5 f [ drop 1 ] unless
! S: 9 1

Quotations supplied to when and unless have to have the same stack effects as their nonexistent counterparts, which means they mustn't change the depth of the stack.

While and for behaviour can be implemented using looping combinators like while, until or loop. The simplest of them, loop, takes a quotation and executes it until it leaves an f on top of the stack:

5 [ 1 swap 1 - dup 0 > ] loop drop
! S: 1 1 1 1 1

The other two looping combinators take two quotations - a predicate and a body - and execute them repeatedly until (or while) the predicate leaves a true value on top of the stack. I'm not going to provide any examples for these because I have never used them and they aren't very useful in practice. A much more important behaviour of for-each will be discussed later.

Basic sequences

Arrays and strings

The most basic sequence type taught for most languages is usually an array. It's a simple ordered sequence of values which can be anything you can put on the stack. Literal arrays are created by a syntax word { with syntax:

{ elements... }

Strings are arrays of numbers representing unicode characters.
Literal strings are created by a syntax word " which has the usual syntax:

"string..."

Note the lack of spaces separating the quotes from the string itself. Factor strings have full unicode support and allow a lot of escape sequences to specify various characters. For more info check \ " help.

Iterating over sequences

Sequences plus combinators

Sequences come with their own words like nth, length or set-nth, but here I would like to focus on sequence combinators, because they allow us to implement the for-each behaviour. There are many words used to iterate over contents of sequences, I will focus on the three most common: each, map and filter.

each takes a sequence and a quotation and executes this quotation on every element of the sequence in order. The quotation can use other elements of the stack but it has to consume exactly one - the sequence element. It can be used for example to implement a sequence reduce combinator:

0 { 0 1 2 3 4 5 6 7 8 9 } [ + ] each
! S: 45

In this example each of the numbers is added to 0 resulting in a sum of all numbers from 0 to 9. This usage actually has its own word, reduce.

map will apply the quotation to each element of the sequence producing new elements that are then collected into a new sequence. It lets you apply a transformation on many values at once. For example if you wanted an array of squares of numbers up to 10:

{ 0 1 2 3 4 5 6 7 8 9 10 } [ sq ] map
! S: { 0 1 4 9 16 25 36 49 64 81 100 }

sq is a word I mentioned in the previous tutorial. It executes dup * which multiplies the number by itself.

filter will apply the quotation to each element of the sequence and create a new sequence with elements for which the quotation returned a true value.

{ 6 925 2 94 0 4 5 3 474 11 } [ even? ] filter
! S: { 6 2 94 0 4 474 }

even?, as the name suggests, returns t for even inputs and f for odd. It is used here to filter out the odds.

Calculating primes

A practical example

Given what we learned today we can finally write something useful. I will be using a top-down design order, meaning I will start with the most general word and figure out what helper words will be needed to implement it. Almost everything I come up in this section is already available in the math.primes vocabulary, but it's a good example so let's pretend we don't know that.

Let's say we want to write a word that will filter only prime numbers from a sequence. For that we can use the word filter with a predicate quotation that returns true if a number is prime. Our general word looks like this:

: filter-primes ( seq -- new-seq )
    [ prime? ] filter
;

If you write it like this into the listener it will complain that word prime? is not in the currently used vocabularies, so let's define prime?.

The simplest way to check if a number is prime is to check if any number from 2 to its square root is its divisor. This method is called a trial division and it's not the most efficient way of looking for primes, but it is simple. To do this we will first transform a sequence of numbers from 2 to sqrt(n) into boolean values indicating divisibility and then reduce this sequence using the function or:

: prime? ( n -- ? )
    dup [2,sqrt(n)]             ! Construct the sequence
    [ over multiple? ] map nip  ! Check divisibility
    f [ or ] reduce not         ! Take a logic or of the whole sequence
;

This didn't help at all! Now we have two undefined words: [2,sqrt(n)] and multiple?! The solution is to keep defining until everything works out.

[2,sqrt(n)] should return a sequence of integers from 2 to sqrt(n). Procedurally generating sequences is not an easy topic so I will yield and use a word from math.ranges vocabulary: [a,b]. This word constructs a sequence of numbers starting at it's first argument and incrementing by one up to but not exceeding the second argument. It's now only a matter of calculating these arguments:

USING: math.ranges math.functions ;
: [2,sqrt(n)] ( n -- range )
    sqrt 2 swap [a,b]
;

USING: and USE: are syntax words that tell Factor in what vocabularies it should search for words we use. Here [a,b] is from math.ranges and sqrt is from math.functions.

Now we are again left with one undefined word: multiple?. It's function is to check whether its second argument is a multiple of the first. A usual way to check for divisibility is by using the modulo function:

: multiple? ( n m -- ? )
    swap mod 0 =
;

And that's it! We're done! If you enter those definitions in a correct order you will have a working filter-primes word!

Now, this code has a bunch of problems. For starters it considers 2 to be composite. It will also break when checking if zero is prime. Check if you can use some constructions we learned today to fix these problems. Bonus points if you can keep all word definitions to three short lines (tip: define more words).

Practical example code

USING: math.functions math.ranges ;

: multiple? ( n m -- ? )
    swap mod 0 =
;

: [2,sqrt(n)] ( n -- range )
    sqrt 2 swap [a,b]
;

: prime? ( n -- ? )
    dup [2,sqrt(n)]
    [ over multiple? ] map nip
    f [ or ] reduce not
;

: filter-primes ( seq -- new-seq )
    [ prime? ] filter
;

! Example use:
3 40 [a,b] filter-primes
! S: V{ 3 5 7 11 13 17 19 23 29 31 37 }

Don't worry about V{. It's a syntax word for literal vectors and it does the same thing as { for arrays. The difference isn't important here.

Conclusion

We did something!

In this tutorial you learned about basic sequences in Factor as well as quotations and how to use them with control flow combinators. I went through a top-down design process for a simple word. Next time I will be looking into Factor's object system: class tuples.

P.S. You may have noticed a style change in the middle of this article. That's because my editor/corrector unfortunately no longer has enough time to edit my articles as fast as I write them. Subsequent articles will be released uncorrected and (hopefully) edited at a later date.

Factor pt. 1 - Concatenative basics

Alex Esoposting — Sun, 05 Sep 2021 07:48:26 +0000

As I mentioned in my previous post, concatenative programming (CP) is cool in theory, but it is different enough that it requires breaking out of the standard imperative mindset. Concatenative advocates claim (quite boldly) that thinkng in CP enforces clean code because ugly code is never more efficient. Let me show you how to think concatenatively so you can decide for yourself.

Terminology and language choice

Things I should've mentioned in the first paragraph

In my CP tutorials I will be using a language called Factor, for the following reasons:

As far as I'm aware, Factor is the most developed concatenative language
It has a lot of useful high level libraries
It is one of two concatenative languages I can program in
It has syntax highlighting on dev.to
You can easily download it for most systems
It has a great interactive environment with all docs built in

Factor can be used as a high level language but exposes low level functionality for the brave folks and compiles to efficient machine code. If you prefer something meant for low level programming try Forth - much older but still well documented and with similar syntax.

Speaking of syntax: Factor doesn't have much of it. In CP there are only functions operating on the program's state, so there is no need for any operators, parentheses or indentation. Because of that Factor functions are called "words" and their names can contain any non-white characters. Every program is just a sequence of words separated with white characters.

Why don't you go and install Factor and open Listener for yourself so that we can take a look at some code!
If you have any burning questions regarding any Factor word just type \ questionable-word help into the Listener and you will get an interactive help that will hopefully satisfy your appetite for information.

The stack

Our lord and saviour

Factor is a stack-based language, meaning its primary way of storing data is on a stack. Factor's stack is like a pile of books: you can put values on top of it and take values from the top. It is easy to access objects near the top of the stack, but trying to operate on deeper stuff is risky. Factor's stack doesn't consist of books though, it holds values like integers, strings or arrays.

In my code examples I will show code and it's effect on the stack like this:

Code will be shown here
! S: The final stack state from bottom to top goes here

So code that puts some literal integers onto the stack will look like this:

9 3 2 5 1 2 5 0
! S: 9 3 2 5 1 2 5 0

Any number in Factor is a word that pushes this number onto the stack. In this example 9 was executed first so number 9 is at the bottom of the stack and 0 was executed last so number 0 is at the top. ! is a word indicating that the rest of the line is a comment and shouldn't be executed.

So far we've seen how to put numbers on a stack. To operate on them Factor offers all the usual arithmetic operations: +, -, *, / and so forth. To add 1 and 2 together you would write:

1 2 +
! S: 3

"What is that weird order?" you might ask? It's called Reverse Polish Notation and it's the natural way of ordering stuff for a stack-based language. What the + word does is take two values on top of the stack and replace them with their sum. It is not an operator - it doesn't care what words are around it. It only operates on the stack, so in order to add 1 and 2 they have to already be on the stack.

This order - operands first and then operator - facilitates arithmetics without parenthesis. Any order of operations is obvious from the order in which those operations are written. No ambiguity, no precedence rules, just execution from left to right. For example, an operation (3 + 4) * 2 - 5 would be written as 3 4 + 2 * 5 -, and 3 + 4 * (2 - 5) would be 3 4 2 5 - * +. If you have the Listener running (or rather - listening) you can enter each of these examples word by word and see how it ends up with the correct answer in the correct order. You can get accustomed to the idea by trying it out on a piece of paper as well.

Stack shuffling

Getting things where we need them

Because the stack is used for most of the operations, the values we need to operate on at a given moment aren't always in the right positions. This is where the stack shuffling words come into play: they are used to rearrange the top of the stack to fit our needs. Most popular shuffling words include:

dup ( a -- a a ) - duplicates the top value on the stack
drop ( a -- ) - removes the top value from the stack
swap ( a b -- b a ) - swaps two values on top of the stack
over ( a b -- a b a ) - copies the second value from the top and puts it on top of the stack
nip ( a b -- b ) - removes the second value from the top of the stack

Each of them has a version that works on two values at once:

2dup ( a b -- a b a b)
2drop ( a b -- )
2swap ( a b c d -- c d a b)

And so on...

All of these are used constantly in Factor programs. You want to square the number on top of the stack?

3 dup *
! S: 9

You want to subtract the number on top of the stack from 10?

3 10 swap -
! S: 7

You want to get rid of all the stuff you put on the stack when playing with the Listener? Just dump a couple of 4dups and enjoy the clean slate!

Defining new words

Factorisation incoming

In CP it is very easy to take any piece of code and define a new word that executes it. You don't have to care about giving your operators all operands or naming variables, after all you can split the code at (almost) any point and both parts would be valid Factor programs. That's where the name concatenative comes from.

Defining a new word uses a syntax word :. Syntax words work differently from normal words - they work with what is written after them instead of with the stack. They introduce the tiny amount of syntax Forth has and are usually used to define new words. Syntax of : is : name stack-effect body ;. Let's see this on the squaring example from before:

: sq ( x -- x^2 ) dup * ;
3 sq
! S: 9

: is the syntax word that parses the definition
( x -- x^2 ) is a stack effect declaration. I will talk about them in a minute
dup * is the body of the word. These words will be invoked each time sq is called
; indicates the end of the : definition. Code after the semicolon resumes normal interpretation

You should define a new word every time:

There is a piece of code you are using in three or more places
You feel the need to use a comment to explain what a piece of code does
Your word definition has more than three lines

This is called factoring and it is the essence of writing clean and self-commenting code. Factor is optimised for calling words from within words so don't worry about inefficiency.

Stack effects

A wannabe type system

You have definitely noticed the syntax ( x y -- z ) used in a couple of places in this article and maybe you have even guessed what it means. It's called a "stack effect description" and it shows what effect the function has on the stack. It is required in every : definition to make compilation more efficient and to make sure you know what you are doing with your code.

The part before the -- needs to include a word for every stack element expected by the word and the part after it includes a word for every stack element left by the word, including all expected elements. You have already seen a lot of examples in the stack-shuffling section. The stack effect description can be as verbose as you like, ranging from ( url http-server -- post-request ) to ( a b -- c ). It is only required that the number of words matches affected elements, but good stack effects make the code cleaner and more understandable.

Conclusion

And what's coming next

This article explained the very basics of concatenative programming in Forth: literals, stack shuffling and word definitions. In the next tutorial I will show you how Factor handles control flow and collections such as arrays and hashtables. Stay tuned for the next week!

What are concatenative languages?

Alex Esoposting — Sat, 28 Aug 2021 13:46:10 +0000

Probably all of you are familiar with the imperative programming paradigm and some of you may know about the functional paradigm, but I recently discovered and fell in love with the third one: concatenative. Let me tell you all about it using opaque examples and bad simplifications!

Trigger warning: section about functional programming is very simplified and I don't have proper education to go in more depth on this topic.

Imperative paradigm

The easy one

Imperative programming (IP) is what most people are familiar with as the majority of the most popular languages heavily support this paradigm. An algorithm in this paradigm is described as a series of orders (imperatives) that the machine executes to get the desired result.

Its popularity comes from the fact that hardware languages are imperative in nature: the processor reads commands one after another executing them in order. Higher level languages were built on top of lower level ones by people familiar with this low level imperativeness. They made these languages imperative too to facilitate efficient compilation or interpretation.

IP has a theoretical basis on Alan Turing's interpretation of computation - the Turing Machine. It's a hypothetical machine that consists of a memory that can be read one cell at a time and directives, which based on the current cell's content can change its value or move to another cell. That's roughly what happens in the processor, albeit in a much more sophisticated way. Not much thought is actually given to Turing's computationnal model directly when programming imperatively.

Functional paradigm

The elegant one

Functional programming (FP) stems from a different basis for computation theory - Alonzo Church's Lambda Calculus. In this model everything is a function that takes a single argument (another function) and returns a new function as a result. That may seem useless - what can you possibly do with just functions? - until you realize that you can define certain functions to represent numbers. If you do this well it is easy to define functions that act as mathematical operations, tuples, arrays, classes and any other thing you know from imperative programming and the whole algorithm ends up being defined as a function from program input to program output. In practice languages define these core concepts for you so you can use your familiar mathematical notation and focus on higher level stuff.

At first this looks like a weird way of writing normal code which doesn't translate that well into machine language. There is actually a grain of truth in the second statement, functional environments have their ways of efficiently translating their code into imperative machine language, though.

The power of FP lays not in how well it can emulate IP, but in what is different between them: just like imperative is close to the hardware, functional is close to maths. This puts off many people. Why would I care about mathematical basis of my code? It is supposed to operate on real data on a physical machine, not in the realm of theoretical constructs. And to that functional programmers answer: why not both?

People who actually learned this in college could tell you a lot about advantages of FP, but there are a couple of things I find particularly neat about it (except for the quirkiness of everything being a function): it doesn't allow for global variables* (or any variables at all), every function works only with information it got on its input, and types.

*If you don't know yet why globals are bad then let me google that for you.

Types

Basically all I know about FP

In IP types are tied to the physical representation of data: integers are a couple of bytes, strings are arrays of bytes, floats are also a couple of bytes but interpreted differently and so on. In FP there is no data, just functions, so types are based on certain properties of these functions, and data is defined as functions that fit these types. Integer is anything that has properties of an integer and can be used as an integer in functions that require integers as input. This makes types just sets of things that belong in this type. If something belongs to a set of integers it is an integer.

It allows to assign types to functions based on the input they require and output they give. Negation for example can have type int -> int because it takes an integer and returns an integer. Addition would be int -> int -> int because it takes an integer and returns a function that takes another integer that returns an integer - a sum of the previous ones. It is not defined for any other input, so it doesn't make sense to give it any other input. It's not that the function will throw an error if this happens: because you know exactly which function uses which types you can check during compile-time if a function receives input that is outside its input type and raise a compilation error. This prevents bad practices based on passing around data of unknown type and with careful code almost eliminates runtime errors.

From this comes the most amazing thing ever: because your whole program is a function in a pure mathematical sense you can prove its correctness. It's not easy and some languages hide the mathematical concepts so deep that it becomes impossible, but in some functional languages you can definitely prove your program does what you think it does. Ever got tired of writing unit tests for your application? Switch to FP and prove that your program will give correct output every time! Isn't that cool?

Why need anything else?

Isn't two enough?

You might think that between hardware efficiency of IP and mathematical purity of FP everyone should find their perfect way of coding, but we can do better! The solution would be to take the imperative paradigm and make it functional. Every IP program can be translated to FP by making each order a function that takes the program's state, transforms it and outputs a new state. If you do that to a normal imperative program then the state would contain all the declared variables and each function would have access to any of them making global variables a problem again. It requires some changes.

The solution most concatenative languages go for is to replace the variables with a stack. Each function can only access the top of the stack (actually a couple of top values), but getting to deeper values is hard which discourages attempts to recreate global variables. Each function can be treated as a functions that takes some arguments and returns some values depending on how it modifies the top of the stack. In this scheme it is even possible to make a whole type system by stating exactly what values the function expects at the top of the stack and what values it leaves there, and all that while retaining the imperative "do this then that" style of coding.

Concatenative syntax

What makes it so awesome

Concatenative programming (CP) takes from FP the fact that a program consists entirely of functions. If you join it with the fact that each function always takes in the state and spits out another state for the next function to take you realize there is no need for parentheses at all - you can just list functions one by one as they should be executed and the state passes through all of them in order. It is reflected by naming conventions: CP functions are called words, and can be any string of non-white characters because only them have any syntactical meaning.

Because each word exists as a standalone function that doesn't really care what's to the left or to the right you can freely mix and match words to create programs. If you have two programs then just writing them one after another will result in a program that runs the first one and passes its output to the second one -- hence the name "concatenative". This freedom of splitting and joining means that if you use certain word sequences often you can (and you should) define a new word that does the same job. Then you can assign this new word a (possibly) more verbose name, which makes the code cleaner - this is called factoring and is the superpower of CP. In fact you should be doing it in every paradigm, but CP makes it blatantly easy.

With good factoring the code should be self-documenting and each word definition shouldn't exceed 3 lines of code. Here you can see an example of a word that takes a game ID and an API key for Neptune's Pride and fetches game info using the API:

: fetch-game ( game-id api-key -- game-json/error-json )
    prepare-params
    prepare-post-data
    game-url fetch-json
;

Obviously each of those four words used here is defined in an earlier section of the vocabulary, but they are of similar size and complexity. The programming language I'm using is called Factor to emphasize how important it is to factor out common code, or just any code that looks too complicated. Factoring groups code into small, understandable words which then make bigger words, which then make bigger words and so on. It is truly a marvel.

Which languages are concatenative?

Not many actually...

Most modern popular languages support both FP and IP despite being IP-based, but there is no viable way to support CP without huge syntax changes. This means we are left with whatever languages are designed to be CP from the start, and most of them are getting pretty old.

The first CP language (so old that they didn't use the word "concatenative" for it yet) is Forth. It's pretty low level and compiles to very fast code but lacks many modern features and useful libraries. Despite that it can be a good intro to the CP world.

A semi-modern language based on Forth is Factor which I presented earlier. Factor incorporates a primitive type system and a more functional-style control flow. It has a lot of useful and well documented libraries as its community was very active back in the day. It's not entirely dead now, but it's not very alive either.

There is a (not very long) list of concatenative languages at concatenative wiki, although most of them are either dead or unfinished. I say it with sorrow, but despite its power the concatenative paradigm is just another esoteric idea now.

Conclusion

What follows

Despite lack of support for the concatenative paradigm I'm still charmed by its simplicity and ease of factorisation and I will continue to play with concatenative languages for a while which may result in a couple more posts of a more practical nature. If you know a concatenative language that you can recommend (even as a curiosity) please drop a line below. See you soon with some tutorials on an old, unusable language.

Brainfuck Assembly Language Tutorial

Alex Esoposting — Sat, 17 Jul 2021 18:06:04 +0000

So you have your personal Brainfuck Processing Unit (or at least its simulation) and you want to do something with it. BAL is based on brainfuck, a language famous for its mind breaking programming experiences, but if you learn to think in a certain way neither of them is that hard. Don't raise your expectations too high though, I'm not building a game or a web app in this tutorial.

Basics

Like brainfuck but better!

BAL uses eight one-character commands: +-><[],.. Each of them can take an argument represented by a number directly after the command. Just like in brainfuck the commands operate on a linear memory using a single pointer. Anything that's not a command or a number is a comment and is ignored by compilers.

+/-: add/subtract the argument from the selected cell.
>/<: move the pointer up or down the memory according to the argument.
[/]: jump forwards/backwards some number of commands if the selected cell is zero/nonzero.
,/.: input/output the selected cell. Argument use depends on the BPU build, I will ignore it completely here.

+-><[] commands are called "add commands" and their argument must be at least one. It's also assumed to be one if you don't specify it, but that's a bad practice and leads to less readable code. ,. commands are "I/O commands" ant their default is zero. There will also be a maximum argument depending on the BPU architecture. This tutorial assumes an 8-bit BPU, so max arguments are 32 for add commands and 31 for I/O commands.

Simple loops

The most basic thing in BAL

Having seen such a limited set of tools you might start to question whether it's possible to program in BAL at all! How can one write a complex program if every command only ever involves a single cell? The answer is loops. While it's true that any single command only uses one cell at most if you wrap them in a loop you can create commands that use multiple cells and involve conditions.

Set cell to zero

Loop base

Let's look at the simplest useful loop: setting a cell to zero. There is no command in BAL that would allow to set a cell to a constant value. Instead you need to use subtraction in a loop that repeats until the cell is zero. You should also only subtract one to make sure you don't jump over zero. Here's the code with comments:

In memory explanations cells are divided with pipes (|)
and the current cell is marked by *asterisks*.
Starting memory: *some number*
[3    Jump over the loop if the cell is already zero
  -1  Subtract one
]1    Jump back until the cell is zero
Final memory: *zero*

You might recognise this construction as an inverse case of a for loop. In another language this could be written as for (i = cell; i > 0; i--) pass;. It's very important to think about actions in BAL in terms of "repeat something N times" and most loops will end with -1 ]X.

Moving values between cells

Loop body

Again, there's no single command to move a value from cell to cell. Thinking with fors, what is the action to repeat N times to move N somewhere? It's not hard to realise it's just "add 1", which gives us the following code:

Starting memory: *N* | zero 
[6    Jump over the loop if the cell is already zero
  >1  Move over to the cell that the value is moved to
  +1  Increment it
  <1  Move back to the original cell
  -1  Decrement it
]4    Repeat until original cell is zero
Final memory: *zero* | N

This code actually doesn't move the value between cells, it increments zero by the value of a cell. If the target cell was something other than zero it would still end up being incremented by the same amount, giving us addition for free.

Another thing achievable for free with this code is multiplication by a constant. If instead of adding one N times you add a constant N times you get N multiplied by the constant.

Multiplication

Nested loops

Let's again start by thinking with fors: what's the action to repeat N times to get M*N? It's adding M, and we already know how to do that, so let's see the code.

Starting memory: *M* | N | target (zero)
[11
  >1  Move over to N
  Add N to the target
  [6 >1 +1 <1 -1 ]4
  <1  Get back to M
  -1 Close up the loop
]9
Final memory: *zero* | zero | N

This looked promising, but the N was moved from source to the target, not copied, so it wasn't there to be added on the next loops. Instead of just moving N to target you need to use another helper cell initialised to zero. Then you move N to target and helper, and after that move helper back to N which leaves it ready for the next loop.

Starting memory: *M* | N | target (zero) | helper (also zero)
[20
  >1  Move over to N
  Move N to the target and helper
  [8
    >1 +1  Increment target
    >1 +1  Increment helper
    <2 -1  Decrement N
  ]6
  >2 Move to helper
  Move helper back to N
  [6 <2 +1 >2 -1 ]4
  <3  Get back to M
  -1 Close up the loop
]18
Final memory: *zero* | N | N*M

Conditional jumps

AKA Ifs

In the previous section most of the work was done by the ] command which jumps back and facilitates looping: executing the same code multiple times. Now is the time to take a closer look at the [ command which jumps forward and facilitates ifs: skipping parts of the code based on a condition.

Skipping loops

Been there, done that

I've already shown examples of the most commonly used forward jumps in BAL: skipping over loops that shouldn't be entered. This is exactly how they are used in pure brainfuck as well. Usually they aren't necessary for the program to work correctly in BAL but they can make it several times faster, depending on the loop.

Let's consider the simplest loop: -1 ]1. It starts by subtracting one, and then repeats it until the cell is zero. The problem arises when the cell is zero before this loop starts. Since BAL is supposed to be executed on hardware solutions, subtracting one from zero will result in overflow and wrap back to the maximum value the cell can hold (255 for 8-byte solutions), and then repeat the loop the maximum possible number of times until it's back at zero. That's why it's usually worth it to spare this one additional memory cell for a [ command before most loops.

Standard ifs

Normal constructions that you know and love

The only data type brainfuck can handle is integers, and the only comparison operation available is "equals". That doesn't sound like much, but it's enough to make basic "if" blocks that branch depending on a number in a cell. In normal languages it might look like this:

if n == 0 then
  do something
else if n == 1 then
  do something else
else if n == 2 then
  do something even more different
else
  do the final thing
end

Execution would skip over sections until finding the one that does fulfill the condition, execute it and skip the rest to continue execution after the end of the if block. BAL only allows jumps when the equality condition is fulfilled, but not on "is not equal to" condition. This follows from the fact that [ offers jumping if the number is equal to zero. This means the code requires some reorganisation:

if n == 0 goto N0
if n == 1 goto N1
if n == 2 goto N2
  do the final thing
  goto END
N0:
  do something
  goto END
N1:
  do something else
  goto END
N2:
  do something even more different
END:

This still includes comparisons to numbers other than zero, but checking if N is equal to X can be converted to checking if N-X is equal to zero which can be easily done in BAL. Let's see what the code looks like using BAL:

[9     Jump if N equals zero
-1 [9  Jump if N minus one equals zero
-1 [9  Jump if N minus two equals zero
do the final thing
-1 ]1  Set N to zero for the jump
[6
do something
[4  N is already zero here so it can be used for jump
do something else
[2
do something even more different

For this example I considered every "do" a single command so jump arguments are quite small, but they will need to be adjusted to whatever happens in each branch and to the amount of branches. Jumping to the end can be done using a cell different than N, but it's important that every branch ends on the same cell unless you deliberately want the program to move.

Moving loops

Complicated stuff

In the first section I talked about BAL loops as for loops, but actually they are more like while loops. They can repeat something N times if you go back to the same cell and decrement it at the end of the loop, but but it's sometimes useful to change the cell in another way or even not come back to the same cell altogether.

Text reversing

Ultimate test of skill

The task is to read a string of bytes representing ASCII symbols terminated by a newline, and then return that string in reverse order.

To reverse a piece of text you need to take each letter as input, store them all and return in reverse order. Seems like a trivial task, but storing a variable number of letters and reading them means moving through a variable number of cells which requires moving loops.

Let's break down the task into smaller parts:

Setup
Reading loop
- Read a byte
- Check if it's newline
- If not then move to the next cell
- If yes then move to the writing loop
Writing loop
- Move to the next saved byte
- Check if it's the end
- If not write the byte
- If yes finish the program

Because newline (ASCII 10) terminates the string it will never appear in it and can be safely used as a bumper telling the writing loop to stop:

Starting memory: *zero* | anything
+10 >1  Set cell to the bumper value and move over
Intermediate memory: bumper | *anything*

Then the reading loop starts. It checks for the ASCII code for newline.

Intermediate memory: bumper | *anything* | more of anything
,       Read a byte
-10 [6  Don't enter the loop if newline
  +10   Restore original value
  >1 ,  Move over and read a new byte
-10 ]4  Stop looping if newline
Memory after one cycle: bumper | byte | *anything minus ten* | more of anything
Intermediate memory after the loop terminates: bumper | many bytes | *zero*

The loop moves one cell right each time, saving respective bytes to consecutive cells. The writing loop reverses this process.

Intermediate memory: bumper | many bytes | *zero*
<1      Move to the last byte
-10 [6  Don't enter the loop if already at the end
  +10   Restore original value
  . <1  Write and move to the next byte
-10 ]4 Stop looping if at the end
Memory after one cycle: bumper | many bytes | *byte* | zero
Final memory: *zero* | many bytes

Moving loops are a powerful tool with many use cases. It's important to always know that the loop will either hit a bumper or terminate in some other way, otherwise it could overwrite other data.

Final remarks

You're almost ready

The text reversing program could almost be a valid program for the BPU, but it needs some minor corrections. The first one is that after finishing the program the computer would not stop but go on to execute whatever else is stored in memory, and in this case it is the text given by the user. When interpreted as code it is just garbage and would lead to unexpected behaviour.

To prevent this from happening each program should include a main loop that loops always, no matter what. In our case it just requires to add some code at the end:

+10 .  Set the bumper back to newline and print it
]19    Jump back to the start

If the jump is too big to fit in a single argument you can insert intermediate jumps right after jumps in the code. For example if you have this piece of code: ]3 ]30 then when it's executed normally either the first jump will take place or no jump will take place. On the other hand if you jump directly into the ]30 it will continue jumping back allowing for jumps bigger than whatever your maximum argument is.

The other minor issue with the program is that both the program pointer and the data pointer start at the first memory cell which is occupied by the first command of the program. The data pointer has to be moved to a code-free area first, and only then the program can be executed. This is accomplished by adding a >22 at the start of the setup, which gives the complete and working program:

>22
+10 >1  Set cell to the bumper value and move over
,       Read a byte

-10 [6  Don't enter the loop if newline
  +10   Restore original value
  >1 ,  Move over and read a new byte
-10 ]4  Stop looping if newline

<1      Move to the last byte
-10 [6  Don't enter the loop if already at the end
  +10   Restore original value
  . <1  Write and move to the next byte
-10 ]4 Stop looping if at the end

+10 .  Set the bumper back to newline and print it
]19    Jump back to the start

Conclusion

Go and write code!

Now you know how to use [ and ] commands to create advanced loops and conditionals. With such powerful tools you can write anything! Just remember to carefully plan your memory usage and the BPU is your oyster.

You can find the BPU simulation as well as a compiler and some examples in the PBU github repo. Have fun with the language!