Tuesday, January 24, 2023

Semantic Versioning

Semantic Versioning (or "semver" for short) is a specification for handling version numbers, and providing a way to sort and specify compatibility using a MAJOR.MINOR.PATCH structure with optional "pre-release" and "build" information.

Some examples of semantic version numbers:

  • 1.0.0-alpha
  • 1.0.0-beta+win32
  • 1.0.0-rc.1
  • 1.0.0

For a long time, I thought it might be funny to follow the upcoming release of Factor version 0.99 with version 0.100. Well, if we wanted to be consistent with "semver", it might instead have to be something like 0.100.0-joke+haha.

There is now a semver vocabulary that provides some words for sorting and working with semantic version numbers. Here's an example using it:

IN: scratchpad USE: semver

IN: scratchpad "0.99.0" >semver bump-alpha semver.
0.99.1-alpha.0

IN: scratchpad "0.99.0" >semver bump-preminor bump-rc semver.
0.100.0-rc.0

IN: scratchpad "0.99.0" "0.100.0" semver<=> .
+lt+

IN: scratchpad "0.100.0-joke+haha" >semver bump-major semver.
1.0.0

Reading the Semantic Versioning 2.0.0 specification, it suggests using the version numbers to represent compatibility with previous versions. And many languages have package managers that use these compatibility guarantees with "semver ranges" to manage project dependencies.

Saturday, January 21, 2023

Five Questions

Many years ago, there was a blog post containing five programming problems every software engineer should be able to solve in less than 1 hour. I had bookmarked it at the time and didn't notice the controversy it created on Reddit. The original link seems to be down — you can view a copy of it on the Wayback Machine — but there are various solutions posted online, including a solution in Python.

I finally got around to looking at it and writing up some solutions to the problems listed. Apparently, instead of solving this in 1 hour in Factor, it took me almost 8 years:

IN: scratchpad 2015 05 09 <date> days-since >integer .
2814

Problem 1

Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.

In idiomatic Factor, this is just sum, and we would typically use sequence combinators, but instead here are a few solutions using lexical variables.

Using a for-loop, iterating forwards:

:: solve-1 ( seq -- n )
    0 seq length [ seq nth-unsafe + ] each-integer ;

Using a while-loop, iterating forwards:

:: solve-1 ( seq -- n )
    0 0 seq length :> n
    [ dup n < ] [
        [ seq nth-unsafe + ] [ 1 + ] bi
    ] while drop ;

Using recursion, iterating backwards:

:: (solve-1) ( accum i seq -- accum' )
    accum i [
        1 - seq [ nth-unsafe + ] 2keep (solve-1)
    ] unless-zero ;

: solve-1 ( seq -- n )
    0 swap [ length ] keep (solve-1) ;

Some test cases to confirm behavior:

{ 0 } [ { } solve-1 ] unit-test

{ 1 } [ { 1 } solve-1 ] unit-test

{ 6 } [ { 1 2 3 } solve-1 ] unit-test

Problem 2

Write a function that combines two lists by alternatively taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

We can alternately choose items from each list:

: solve-2 ( seq1 seq2 -- newseq )
    [ min-length 2 * ] 2keep '[
        [ 2/ ] [ even? ] bi _ _ ? nth-unsafe
    ] { } map-integers-as ;

Some test cases to confirm behavior:

{ { "a" 1 "b" 2 "c" 3 } } [
    { "a" "b" "c" } { 1 2 3 } solve-2
] unit-test

{ { "a" 1 "b" 2 "c" 3 } } [
    { "a" "b" "c" "d" } { 1 2 3 } solve-2
] unit-test

Problem 3

Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

There are many approaches, including using memoization, but instead we'll just iterate from the starting values and use replicate to build up an output array.

: solve-3 ( n -- seq )
    [ 0 1 ] dip [ dup rot [ + ] keep ] replicate 2nip ;

Some test cases to confirm behavior:

{ { } } [ 0 solve-3 ] unit-test

{ { 0 } } [ 1 solve-3 ] unit-test

{ { 0 1 } } [ 2 solve-3 ] unit-test

{ { 0 1 1 2 3 5 8 13 21 34 } } [ 10 solve-3 ] unit-test

{ 573147844013817084100 } [ 100 solve-3 sum ] unit-test

Problem 4

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

We can try each-permutation of the input numbers, looking for their largest numerical value when the digits are concatenated.

: solve-4 ( seq -- n )
    0 swap [ number>string ] map
    [ concat string>number max ] each-permutation ;

Some test cases to confirm behavior:

{ 95021 } [ { 50 2 1 9 } solve-4 ] unit-test

{ 5523 } [ { 52 5 3 } solve-4 ] unit-test

Problem 5

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

This one is more complicated than the previous ones, but we can build it up piece by piece, using a test-case on each step to show how it works.

First, we want a word to interleave numbers amongst operators using solve-2.

: insert-numbers ( operators -- seq )
    [ length [1..b] ] [ solve-2 ] [ length 1 + suffix ] tri ;

{ { 1 f 2 + 3 f 4 } } [ { f + f } insert-numbers ] unit-test

Next, we want a word that will join adjacent digits — separated by f:

GENERIC: digits, ( prev intermediate -- next )
M: number digits, [ 10 * ] [ + ] bi* ;
M: object digits, [ [ , 0 ] dip , ] when* ;

: join-digits ( seq -- seq )
    [ [ ] [ digits, ] map-reduce , ] { } make ;

{ { 12 + 34 } } [ { 1 f 2 + 3 f 4 } join-digits ] unit-test

Since Factor is a kind of Reverse Polish notation, we'll want to swap from infix to postfix:

: swap-operators ( seq -- seq )
    dup rest-slice 2 <groups> [ 0 1 rot exchange ] each ;

{ { 12 34 + } } [ { 12 + 34 } swap-operators ] unit-test

The solution, then, is to use all-selections of addition, subtraction, and adjacency — interleaving the numbers, joining adjacent digits, swapping operators, and then calling each sequence as a quotation, filtering for the ones that return 100:

: solve-5 ( -- solutions )
    { + - f } 8 all-selections
    [ insert-numbers join-digits swap-operators ] map
    [ >quotation call( -- x ) 100 = ] filter ;

We can print the formula out by swapping the operators back to infix and printing them out:

: print-formula ( solutions -- )
    [ present ] map swap-operators " " join print ;

: solve-5. ( -- )
    solve-5 [ print-formula ] each ;

Spoilers! The printed solutions:

IN: scratchpad solve-5.
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 + 45 - 67 + 8 - 9
123 - 4 - 5 - 6 - 7 + 8 - 9
123 - 45 - 67 + 89

Thursday, January 19, 2023

GetPercentageRounds

There was a funny post on Twitter a couple of days ago about a recent event where the "Dutch government was forced to release the source code of their DigiD digital authentication iOS app" with this piece of C# code:

Some very funny discussions continued, with comments about how good or bad this code is, and how one might rewrite it in various ways. I thought it would be a fun opportunity to show a few variations of this simple function in Factor.

Implementations

A direct translation of this code, might use cond which is basically a sequence of if statements:

: get-percentage-rounds ( percentage -- str )
    {
        { [ dup 0.0 <= ] [ drop "⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ dup 0.0 0.1 between? ] [ drop "πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ dup 0.1 0.2 between? ] [ drop "πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ dup 0.2 0.3 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ dup 0.3 0.4 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪" ] }
        { [ dup 0.4 0.5 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪" ] }
        { [ dup 0.5 0.6 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪" ] }
        { [ dup 0.6 0.7 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪" ] }
        { [ dup 0.7 0.8 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪" ] }
        { [ dup 0.8 0.9 between? ] [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪" ] }
        [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅" ]
    } cond ;

But since this is a series of if statements checked sequentially, you can just check the upper bounds. And since we only care about the argument for the comparison, we can use cond-case:

: get-percentage-rounds ( percentage -- str )
    {
        { [ 0.0 <= ] [ "⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ 0.1 <= ] [ "πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ 0.2 <= ] [ "πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ 0.3 <= ] [ "πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪" ] }
        { [ 0.4 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪" ] }
        { [ 0.5 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪" ] }
        { [ 0.6 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪" ] }
        { [ 0.7 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪" ] }
        { [ 0.8 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪" ] }
        { [ 0.9 <= ] [ "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪" ] }
        [ drop "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅" ]
    } cond-case ;

One suggestion was to generate a substring based on the input — with the somewhat negative aspect that it allocates memory for the returned string when called:

: get-percentage-rounds ( percentage -- str )
    10 * 10 swap - >integer dup 10 +
    "πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪" subseq ;

But another way would be to just index into the possible results, using quoted words to reduce the amount of tokens involved — resulting in this fairly aesthetic result:

: get-percentage-rounds ( percentage -- str )
    10 * ceiling >integer qw{
        ⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪
        πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪⚪
        πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅⚪
        πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅πŸ”΅
    } nth ;

It's always fun to see different ways to solve problems. In the Twitter thread, that includes using binary search, building the output character-by-character, generating solutions using ChatGPT, one-liners in Python, pattern matching, unit testing, and discussions of edge cases and naming conventions.

Monday, January 16, 2023

Project Gemini

Project Gemini is a neat modern take on the Gopher protocol. You can read the Gemini FAQ or the Gemini specification to learn more details, but the home page has a nice summary:

Gemini is a new internet protocol which

  • Is heavier than gopher
  • Is lighter than the web
  • Will not replace either
  • Strives for maximum power to weight ratio
  • Takes user privacy very seriously

There are some nice Gemini clients implemented in various languages, for both the command-line and with nice user interfaces. I happen to enjoy using AV-98 and Lagrange, but many others are also great.

In a similar manner to my Gopher implementation in Factor, I recently implemented the Gemini protocol as well as a Gemini server and a Gemini user interface:

Instead of going into how the protocol or the user interface is implemented, I wanted to go over the Gemini command-line interface. In the spirit of Python's cmd module, I contributed the command-loop vocabulary to support generic line-oriented command interpreters.

We start by making a sequence of commands that our Gemini interpreter will support:

CONSTANT: COMMANDS {
    T{ command
        { name "back" }
        { quot [ drop gemini-back ] }
        { help "Go back to the previous Gemini URL." }
        { abbrevs { "b" } } }
    T{ command
        { name "forward" }
        { quot [ drop gemini-forward ] }
        { help "Go forward to the next Gemini URL." }
        { abbrevs { "f" } } }
    T{ command
        { name "history" }
        { quot [ drop gemini-history ] }
        { help "Display recently viewed Gemini URLs." }
        { abbrevs { "h" "hist" } } }
    T{ command
        { name "less" }
        { quot [ drop gemini-less ] }
        { help "View the most recent Gemini URL in a pager." }
        { abbrevs { "l" } } }
    T{ command
        { name "ls" }
        { quot [ gemini-ls ] }
        { help "List the currently available links." }
        { abbrevs f } }
    T{ command
        { name "go" }
        { quot [ gemini-go ] }
        { help "Go to a Gemini URL" }
        { abbrevs { "g" } } }
    T{ command
        { name "gus" }
        { quot [ drop "gemini://gus.guru/search" gemini-go ] }
        { help "Submit a query to the GUS search engine." }
        { abbrevs f } }
    T{ command
        { name "up" }
        { quot [ drop gemini-up ] }
        { help "Go up one directory from the recent Gemini URL." }
        { abbrevs { "u" } } }
    T{ command
        { name "url" }
        { quot [ drop gemini-url ] }
        { help "Print the most recent Gemini URL." }
        { abbrevs f } }
    T{ command
        { name "reload" }
        { quot [ drop gemini-reload ] }
        { help "Reload the most recent Gemini URL." }
        { abbrevs { "r" } } }
    T{ command
        { name "root" }
        { quot [ drop gemini-root ] }
        { help "Navigate to the most recent Gemini URL's root." }
        { abbrevs f } }
    T{ command
        { name "shell" }
        { quot [ gemini-shell ] }
        { help "'cat' the most recent Gemini URL through a shell." }
        { abbrevs { "!" } } }
    T{ command
        { name "quit" }
        { quot [ drop gemini-quit ] }
        { help "Quit the program." }
        { abbrevs { "q" "exit" } } }
}

And then we define a custom command-loop that will allow us to number the links on a Gemini page, and then by typing a number we can navigate to one of the links by detecting a "missing command":

TUPLE: gemini-command-loop < command-loop ;

M: gemini-command-loop missing-command
    over string>number [ 1 - LINKS ?nth ] [ f ] if* [
        gemini-go 3drop
    ] [
        call-next-method
    ] if* ;

You can see it in action:

$ ./factor -run=gemini.cli
Welcome to Project Gemini!
GEMINI> go gemini.circumlunar.space/news/

Official Project Gemini news feed

[1] Atom feed

2023 News

[2] 2023-01-14 - Tidying up gemini.circumlunar.space user capsules
[3] 2023-01-08 - Changing DNS server

2022 News

[4] 2022-06-20 - Three years of Gemini!
[5] 2022-01-30 - Minor specification update (0.16.1)
[6] 2022-01-22 - Mailing list archives, Atom feed for official news
[7] 2022-01-16 - Mailing list downtime, official news feed

Sunday, January 15, 2023

Guided Tour of Factor

Many years ago, Andrea Ferretti created a Factor tutorial which I had written about at the time.

One of our new core developers, Raghu Ranganathan, got permission to include the tutorial in the main Factor repository, and has reformatted it and updated it for the not-yet-released version 0.99 as the Guided tour of Factor.

You can access it in a recent nightly build by doing:

IN: scratchpad "tour" help

Check it out!

Friday, February 4, 2022

Speedrun Feedback

Recently, Tomasz Wegrzanowski chose Factor for his 100 Languages Speedrun: Episode 71: Factor and it encouraged us to make some improvements that I wanted to describe.

Many of our users use the Factor environment through the UI developer tools or on the command-line with the listener. Another important use case is being able to eval and run scripts -- and this is where much of Tomasz' criticism was focused.

We now do command-line eval and run scripts with auto-use? enabled. This will be available in the nightly builds and as part of an upcoming 0.99 release.

So this works now:

$ ./factor -e="1 2 + ."
3

$ cat foo.factor
USE: io
"Hello World" print
12

$ ./factor foo.factor
Hello World

--- Data stack:
12

Previously, the first example would error with a "No word named “+” found in current vocabulary search path" and the second example would complain that the "Quotation's stack effect does not match call site" because the script did not have a ( -- ) stack effect.

I appreciate that some users approach Factor differently than I do, and we love getting feedback. I wish we could solve the name conflict with factor(1), but that is more challenging.

We may adjust this slightly as it just landed last night, and if anyone has further suggestions, please keep them coming!

Tuesday, July 31, 2018

Factor 0.98 now available

“Even though you're growing up, you should never stop having fun.” - Nina Dobrev

I'm very pleased to announce the release of Factor 0.98!

OS/CPUWindowsMac OS XLinux
x86
x86-64

Source code: 0.98

This release is brought to you with almost 4,300 commits by the following individuals:

Alexander Ilin, Arkady Rost, Benjamin Pollack, BjΓΆrn Lindqvist, Cat Stevens, Chris Double, Dimage Sapelkin, Doug Coleman, Friedrich von Never, John Benediktsson, Jon Harper, Mark Green, Mark Sweeney, Nicolas PΓ©net, Philip Dexter, Robert Vollmert, Samuel Tardieu, Sankaranarayanan Viswanathan, Shane Pelletier, @catb0t, @hyphz, @thron7, @xzenf

Besides several years of bug fixes and library improvements, I want to highlight the following changes:

  • Improved user interface with light and dark themes and new icons
  • Fix GTK library issue affecting some Linux installations
  • Support Cocoa TouchBar on MacOS
  • Factor REPL version banner includes build information.
  • Bindings for ForestDB
  • New graphical demos including Minesweeper, Game of Life, Bubble Chamber, etc.
  • Better handling of "out of memory" errors
  • Improved VM and compiler documentation, test fixtures, and bug fixes
  • Much faster Heaps and Heapsort
  • Support for Adobe Brackets, CotEditor, and Microsoft Visual Studio Code editors
  • On Mac OS X, allow use of symlinks to factor binary
  • Lots of improvements to FUEL (Factor's emacs mode)

Some possible backwards compatibility issues:

  • Flattened unicode namespace (either USE: ascii or USE: unicode).
  • Unified CONSTRUCTOR: syntax to include generated word name
  • Returning a struct by value with two register-sized values on 64bit now works correctly
  • Since shutdown hooks run first, calling exit will now unconditionally exit even if there is an error
  • On Windows, don't call cd to change directory when launching processes; there is another mechanism for that
  • In libc, renamed (io-error) to throw-errno
  • In match, renamed ?1-tail to ?rest
  • In sequences, renamed iota to <iota>
  • In sequences, renamed start/start* to subseq-start/subseq-start-from
  • In syntax, renamed GENERIC# to GENERIC#:
  • Improve command-line argument parsing of "executable"
  • Make buffered-port not have a length, because of problem with Linux virtual files and TCP sockets
  • Fix broken optimization that made floats work for integer keys in case statements
  • Growable sequences expand by factor of 2 (instead of 3) when growing
  • Removed support for "triple-quote" strings

What is Factor

Factor is a concatenative, stack-based programming language with high-level features including dynamic types, extensible syntax, macros, and garbage collection. On a practical side, Factor has a full-featured library, supports many different platforms, and has been extensively documented.

The implementation is fully compiled for performance, while still supporting interactive development. Factor applications are portable between all common platforms. Factor can deploy stand-alone applications on all platforms. Full source code for the Factor project is available under a BSD license.


New Libraries:


Improved Libraries: