[ planet-factor ]

Joe Groff: Type-erased generic functions for C: A modest non-proposal

Earlier this year, I read Martin Uecker's proposal N3212 to add parametric polymorphism to C. It's easy to scoff at the idea of adding generic programming to plain C, when C++ already has templates, a…

Mon, 30 Sep 2024 00:40:00

John Benediktsson: Battlesnake

Battlesnake is “a competitive game where your code is the controller”. In particular, in answering the question “What is Battlesnake?”, the documentation says:

In this game, each Battlesnake is controlled in real-time by a live web server, responding to the Battlesnake API. It navigates the game board based on your algorithm, trying to find food, avoid other Battlesnakes, and survive as long as possible. Battlesnakes can be built using any tech stack you’d like, and we encourage you to step outside of your comfort zone.

It is also a very neat set of episodes of “Coding Badly” from almost two years ago that talks about building battlesnakes using Factor. In particular, they use a live-coding style to explore the development environment, build web servers using the furnace web framework, and learn how to use and deploy their program!

I did not know about these videos until today, but I thought it makes a nice series to share with the world. I love it when people build things using Factor and am always glad to hear about it!

More information is also available on the @BattlesnakeOfficial GitHub organization, as well as an archive of the Coding Badly implementation and a different Factor battlesnake library by another contributor.

Episode 1

Episode 2

Episode 3

Sun, 15 Sep 2024 15:00:00

John Benediktsson: Factor 0.100 now available

“Life can only be understood backwards; but it must be lived forwards.” — Kierkegaard

I’m very pleased to announce the release of Factor 0.100!

OS/CPU Windows Mac OS Linux
x86 0.100 0.100
x86-64 0.100 0.100 0.100

Source code: 0.100

This release is brought to you with over 1400 commits by the following individuals:

Aditya Aryaman Das, Alex null Maestas, Alexander Ilin, Andy Kluger, Bhargav Shirin Nalamati, Charlie Weismann, Dave Carlton, David Enders, Doug Coleman, Evgenii Petrov, Giftpflanze, Ikko Eltociear Ashimine, J. Ryan Stinnett, Jean-Marc Lugrin, John Benediktsson, Keldan Chapman, Limnanthes Serafini, Marc Michael, Michael Raitzam, Michael Thies, Pragya Pant, Raghu Ranganathan, Rebecca Kelly, Rudi Grinberg, Sandesh Pyakurel, Sebastian Strobl, Shruti Sen, Surav Shrestha, Val Packett, @Capital-EX, @Smoothieewastaken, @TheWitheredStriker, @TryAngle, @chunes3, @inivekin, @nomennescio, @olus2000.

Besides some bug fixes and library improvements, I want to highlight the following changes:

  • Upgraded to Unicode 15.1
  • Fix some xmlns that were accidentally changed to https
  • Improved the printing of shortest decimal representation of floating-point numbers
  • Some early support for ARM64 in the non-optimizing compiler, more to do for full support
  • Automatic light/dark theme detection works on Microsoft Windows
  • Support for compressed images, useful when reducing file size is important

Some possible backwards compatibility issues:

  • ui: focusable-child* now returns f to indicate parent should be focused
  • peg: change to compile-time PEG: and PARTIAL-PEG: forms, not delay to first invocation
  • system: renamed macosx to macos
  • math.trig: moved deg>rad and rad>deg to math.functions vocabulary
  • math.functions: fix divisor? to support mixed numbers (floats and integers)
  • math.functions.integer-logs: moved integer-log10 and integer-log2 to math.functions vocabulary
  • ranges: fixed exclusive range to be more correct for non-integer types
  • http.client: moved some download words to http.download vocabulary
  • rosetta-code: moved solutions to the factor-rosetta-code git repository
  • json: read-json returns a single object, use read-jsons to read multiple
  • base32: now contains all of the words from the base32-crockford and base32hex vocabularies

I would also like to bring particular recognition to Raghu Ranganathan, also known as @razetime, who was an incredible developer with an incredibly good attitude and contributing member to many technical communities including code golfing and various programming languages including Factor. We are very sad that he passed away a couple of months ago and would like to have this moment dedicated in his memory.

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:

VM Improvements:

  • Improved ARM64 bootstrap assembly to allow small forms to execute successfully and natively in the non-optimizing compiler. This continues to be a work-in-progress to fully support ARM64.
  • Tentative support for compressed images, allowing Factor images to be as much as 8x smaller in size with run-time uncompression overhead.
  • Improved console I/O on windows to work in environments such as cygwin and GitHub Actions.

Wed, 11 Sep 2024 15:00:00

John Benediktsson: Cash Register

Building a “cash register” is an often used example project, from places like the freeCodeCamp’s Javascript Algorithms and Data Structures Project “Cash Register” or codecademy’s “Building a Cash Register” along with other examples like the Simple Cash Register in Python.

I thought it would be fun to write about building something similar, but not the same, in Factor.

We are going to make a few assumptions:

  1. We handle one currency – the “buck”.
  2. We can make change in various units – from the penny to the Benjamin.
  3. Despite still being legal tender, we do not support $500, $1,000, $5,000, or $10,000 bills.
  4. Despite being rare, we include the two-dollar bill.

Here are our units of change along with their descriptions:

CONSTANT: COINS {
    { 10000 "$100" }
    { 5000 "$50" }
    { 2000 "$20" }
    { 1000 "$10" }
    { 500 "$5" }
    { 200 "$2" }
    { 100 "$1" }
    { 25 "quarters" }
    { 10 "dimes" }
    { 5 "nickels" }
    { 1 "pennies" }
}

If we want to make change, we can generate it using something like the greedy algorithm to find minimum number of coins, starting with the largest denomination possible and iterating to smaller ones:

: make-change ( n -- assoc )
    COINS [ [ /mod swap ] dip ] assoc-map swap 0 assert= ;

For convenience, we can make a formatting word to format our coins into dollars:

: $. ( n -- )
    100 /f "$%.2f\n" printf ;

And now a word to print out the change we made:

: change. ( n -- )
    "CHANGE: " write dup $. make-change [
        '[ _ "%d of %s\n" printf ] unless-zero
    ] assoc-each ;

We can store the amount owed and the amount paid in dynamic variables:

INITIALIZED-SYMBOL: owed [ 0 ]

INITIALIZED-SYMBOL: paid [ 0 ]

Using that, we can make a word to display the balance due:

: balance. ( -- )
    "OWED: " write owed get-global $.
    "PAID: " write paid get-global $. ;

A word to add a charge, increasing the amount owed:

: charge ( n -- )
    "CHARGE: " write dup $.
    owed [ + ] change-global balance. ;

A word to make a payment, providing change if the amount paid is greater than the amount owed:

: pay ( n -- )
    "PAY: " write dup $.
    paid [ + ] change-global balance.
    paid get-global owed get-global - dup 0 >=
    [ change. 0 owed set-global 0 paid set-global ] [ drop ] if ;

And a word to cancel a transaction, refunding any paid amounts:

: cancel ( -- )
    "CANCEL" print
    0 owed set-global
    paid [ change. 0 ] change-global ;

Using a word that parses input into a number of pennies:

: parse-$ ( args -- n )
    "$" ?head drop string>number 100 * round >integer ;

We can then define a set of commands using the command-loop vocabulary:

CONSTANT: COMMANDS {
    T{ command
        { name "balance" }
        { quot [ drop balance. ] }
        { help "Display current balance." }
        { abbrevs { "b" } } }
    T{ command
        { name "charge" }
        { quot [ parse-$ charge ] }
        { help "Charge an item." }
        { abbrevs { "c" } } }
    T{ command
        { name "pay" }
        { quot [ parse-$ pay ] }
        { help "Pay with money." }
        { abbrevs { "p" } } }
    T{ command
        { name "cancel" }
        { quot [ drop cancel ] }
        { help "Cancel transaction." }
        { abbrevs { "x" } } }
}

And then define the loop that we run as MAIN:

: cash-register-main ( -- )
    "Welcome to the Cash Register!" "$>"
    command-loop new-command-loop
    COMMANDS [ over add-command ] each
    run-command-loop ;

MAIN: cash-register-main

And you can see an example from running it:

Welcome to the Cash Register!
$> c 10.23
CHARGE: $10.23
OWED: $10.23
PAID: $0.00

$> c 15.37
CHARGE: $15.37
OWED: $25.60
PAID: $0.00

$> p 100.00
PAY: $100.00
OWED: $25.60
PAID: $100.00
CHANGE: $74.40
1 of $50
1 of $20
2 of $2
1 of quarters
1 of dimes
1 of nickels

It could be fun to extend this example to have an inventory of purchasable items, allow users to ring up these items instead of a series of charges, maybe implement taxable items and discounts, display and print receipts, handle refunds, handle available bills and coins when making change, support other currencies, and other features that you might find in a more “complete” or “real-world” cash register.

The code for this is on my GitHub.

Thu, 8 Aug 2024 12:00:00

John Benediktsson: Reflecting on 20 Years

As close as I can tell, Factor is the result of contributions from around 180 contributors over the past 20 years.

Recently, I was reminded of a tool that can produce graphs showing some aspects of contributions to git repositories. The tool is called Git of Theseus written in the Python programming language, which can be used to generate a series of interesting plots showing statistics over time about a project. A similar tool is Hercules, which claims to be a bit faster and is written in the Go programming language.

We can look at code written in each year which, aside from the first few years, mostly continues to exist in the latest version. In addition, we see a healthy and increasing chart over time:

When wondering about the half-life of code, we might want to see how long a particular line of code continues to exist in the project. We can see that 50% of them are still existing after 5 years:

Many of those early contributions came from Slava Pestov, Doug Coleman, Chris Double, and others, and we continue to benefit from the impressive early work that they did for the Factor programming language. We can plot author statistics, and see the large blocks of contributions over time by various authors:

And, as a percentage of lines of code, see that beginning with almost 100% of the source code contributed by Slava Pestov, more recently we have around 20% each from Slava Pestov, Doug Coleman, and myself as well as several other significant authors:

We can generate a more detailed breakdown of these lines of code by language using tokei, but in particular see that we have over 388,000 lines of Factor source code in our latest development version:

$ tokei .

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 Language            Files        Lines         Code     Comments       Blanks
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 Factor               4952       503452       388845        25717        88890
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

It was pretty great to generate these graphs, and to reminisce about all the vocabularies available so far, and ponder all those still yet to be written.

Happy coding!

Fri, 2 Aug 2024 21:00:00

John Benediktsson: Deploy Issues on MacOS

While trying to help get the BitGuessr game deployed on macOS, I ran into a few issues that were interesting, and I wanted to discuss the process of troubleshooting them.

Sometimes, using the deploy tool is easy, and sometimes it is not-so-easy. There are some challenges around choosing the right level of reflection for the features used in the application you are trying to deploy – we suggest starting with Full environment and then reducing until the program breaks – but besides that it is typically one command:

IN: scratchpad "bitguessr" deploy

That command results in a per-platform executable, which on macOS is an .app bundle that includes the Factor executable, a deployed image, any resources the deployed image uses, and any libraries that the deployed image depends on:

$ find bitguessr.app 
bitguessr.app
bitguessr.app/Contents
bitguessr.app/Contents/Frameworks
bitguessr.app/Contents/Frameworks/libraylib.dylib
bitguessr.app/Contents/Info.plist
bitguessr.app/Contents/MacOS
bitguessr.app/Contents/MacOS/bitguessr
bitguessr.app/Contents/Resources
bitguessr.app/Contents/Resources/bitguessr
bitguessr.app/Contents/Resources/bitguessr/_resources
bitguessr.app/Contents/Resources/bitguessr/_resources/bitguessr_icon.png
bitguessr.app/Contents/Resources/bitguessr/_resources/bitguessr_soundtrack.wav
bitguessr.app/Contents/Resources/bitguessr/_resources/button-0.png
bitguessr.app/Contents/Resources/bitguessr/_resources/button-1.png
bitguessr.app/Contents/Resources/bitguessr/_resources/correct.wav
bitguessr.app/Contents/Resources/bitguessr/_resources/wrong.wav
bitguessr.app/Contents/Resources/bitguessr.image
bitguessr.app/Contents/Resources/Icon.icns

After building this application, checking that it works for me, and uploading it to the server, of course we got a bug report when someone else tried to run it:

$ ./bitguessr.app/Contents/MacOS/bitguessr
...
Cannot resolve C library function
Library: DLL" libraylib.dylib"
Symbol: InitWindow
DlError: none
See https://concatenative.org/wiki/view/Factor/Requirements

Is the InitWindow symbol in the library?

$ nm -gU ./bitguessr.app/Contents/Frameworks/libraylib.dylib | grep InitWindow
0000000000017920 T _InitWindow

Yes, it is.

Is it loading the correct libraylib.dylib file?

$ DYLD_PRINT_LIBRARIES=1 ./bitguessr.app/Contents/MacOS/bitguessr
...
dyld[69951]: <B5534AF8-58E9-3F59-A5DE-F33164570F6B> ./bitguessr.app/Contents/Frameworks/libraylib.dylib

Yes, it seems to be.

Let’s learn more about how dynamic libraries work. There is a nice thread on dynamic library identification that goes into some details about how these are identified and then loaded.

Let’s start with the library – we get our Raylib from Homebrew:

$ cd $(brew --prefix raylib)

$ otool -l libraylib.dylib | grep -A 2 LC_ID_DYLIB
          cmd LC_ID_DYLIB
      cmdsize 72
         name /usr/local/opt/raylib/lib/libraylib.450.dylib (offset 24)

Okay, so this probably needs to be relative to a “runtime path” or rpath, which you can either set:

$ install_name_tool -id "@rpath/libraylib.dylib" libraylib.dylib

Or, fix by downloading a Raylib release that is already set properly for embedding.

Did it change?

$ otool -l libraylib.dylib | grep -A 2 LC_ID_DYLIB
          cmd LC_ID_DYLIB
      cmdsize 48
         name @rpath/libraylib.dylib (offset 24)

Yes, it did!

Now that we have that, we can re-deploy and see if it works:

$ ./bitguessr.app/Contents/MacOS/bitguessr
...
Cannot resolve C library function
Library: DLL" libraylib.dylib"
Symbol: InitWindow
DlError: none
See https://concatenative.org/wiki/view/Factor/Requirements

Nope.

Okay, maybe the rpath that is used to lookup dynamic libraries isn’t set properly:

$ otool -l ./bitguessr.app/Contents/MacOS/bitguessr| grep -A 2 LC_RPATH

Hmm, it is not set at all. The dynamic linker maintains a list of these “runtime path” directories. Maybe we can make sure it looks in the right place by adding one:

$ cd ./bitguessr.app/Contents/MacOS

$ install_name_tool -add_rpath "@executable_path/../Frameworks" bitguessr

Okay, now it looks right:

$ otool -l ./bitguessr.app/Contents/MacOS/bitguessr | grep -A 2 LC_RPATH
          cmd LC_RPATH
      cmdsize 48
         path @executable_path/../Frameworks (offset 12)

Let’s try again… and, it works!

I pushed a change to set the rpath directory properly for future deploys, changed to distributing it as an Apple Disk image, and also made sure to codesign the application so that it launches easily after being downloaded and gave Joseph Oziel an updated macOS build of BitGuessr which included an Icons.icns file in the Apple Icon Image format for the application icon.

Neat!

Thu, 18 Jul 2024 10:00:00

John Benediktsson: Rosetta Code Downloaded

I have been quite distracted by Rosetta Code shenanigans in the past few days. For anyone that is curious about the backstory, I removed the rosetta-code vocabulary from the main Factor git repository, and then decided to archive all the Factor solutions to a separate factor-rosetta-code repository for posterity, utility, and analysis.

I thought it would be fun to talk about different ways to do web scraping for the Rosetta Code website, ultimately choosing to write a Factor vocabulary to do it, which I’ll go into below.

Public Datasets

There are a couple public datasets and scraper tools that you can use:

  1. Hugging Face has a @christopher/rosetta-code dataset, but it looks like it was updated “about 2 years ago”, so perhaps doesn’t contain recently contributed solutions.
  2. The @acmeism/RosettaCodeData repository seems to be quite up-to-date and uses a RosettaCode CPAN module and the MediaWiki API to synchronize their data files periodically. At the moment, this is over 600 MB to clone.
  3. The @brollb/rosetta-code-scraper repository is a Rust scraper that uses the reqwest and scraper crates to parse the web pages and extract task descriptions and solutions. This required some minor tweaks to get working with a recent Rust version, and had some issues with the newer HTML being generated.

Using Factor

I started with the previous approaches, but then I realized that I kinda wanted to build my own program that only grabbed the Factor solutions and weaved them into solution files with the task description for the factor-rosetta-code repository.

After considering using the rendered HTML from the Rosetta Code website, I decided it would be a lot simpler to use the MediaWiki API and our mediawiki.api vocabulary to extract the tasks. That vocabulary requires an endpoint to be specified, so we define a simple combinator that sets it before running a quotation.

: with-rosetta-code ( quot -- )
    [ "https://rosettacode.org/w/api.php" endpoint ] dip
    with-variable ; inline

The Rosetta Code solutions consists of a list of pages as well as sub-categories with their own lists of pages. We need a list-category word that will get the members of a given category, memoized in case pages reference each other or to speed up subsequent calls through caching:

MEMO: list-category ( title -- members )
    'H{ { "list" "categorymembers" } { "cmtitle" _ } }
    query [ "title" of ] map ;

And a list-categories word that will recursively resolve categories containing other categories:

: list-categories ( title -- tasks )
    list-category [ "Category:" head? ] partition swap
    [ list-categories ] map concat append harvest members sort ;

Using these, we can retrieve all tasks and draft tasks:

: all-tasks ( -- tasks )
    "Category:Solutions_by_Programming_Task" list-categories ;

: draft-tasks ( -- tasks )
    "Category:Draft_Programming_Tasks" list-categories ;

Each task page is a series of sections, beginning with the task description, and then a series of solutions in different programming languages. Using page-content, we can see what one of these pages looks like:

IN: scratchpad [ "Sieve_of_Eratosthenes" page-content ] with-rosetta-code

We can build a word that extracts a section that is specified by a begin text and an end text, searching for them using subseq-index to find where they occur in the page:

:: extract-section ( page begin end -- section/f )
    page begin subseq-index [
        begin length +
        dup page end subseq-index-from
        [ page length ] unless*
        page subseq
    ] [ f ] if* ;

The description is everything before the first header section:

: get-description ( page -- description/f )
    "=={{header" over subseq? [
        "" "=={{header" extract-section
    ] [ drop f ] if ;

The solution code is the first <syntaxhighlight> block for our desired language:

: get-code ( page lang -- code/f )
    "<syntaxhighlight lang=\"" "\">" surround
    "</syntaxhighlight>" extract-section ;

We can use those words to weave the commented-out description with the Factor source code:

: get-solution ( task -- solution/f )
    page-content [ get-description ] keep over empty?
    [ 2drop f ] [
        [ string-lines [ "! " prepend ] map "\n" join ]
        [ "factor" get-code "\n\n" glue "\n" append ] bi*
    ] if ;

That works great, you can try it by printing out one of the draft tasks:

IN: scratchpad [ "10001th_prime" get-solution print ] with-rosetta-code
! Task:
!
! Find and show on this page the 10001st prime number.

USING: math math.primes prettyprint ;

2 10,000 [ next-prime ] times .

Now we want a way to save a task, and since the tasks have names that aren’t all valid in filenames or vocabulary names, we do a little cleanup to turn a task name into a path:

: task-path ( task -- path )
    [ dup { [ Letter? ] [ digit? ] } 1|| [ drop CHAR: - ] unless ] map
    >lower R/ --+/ "-" re-replace [ CHAR: - = ] trim ".factor" append ;

Saving a task is getting the solution and then saving to a file:

: save-task ( task -- )
    "vocab:rosetta-code/solutions" [
        [ get-solution ]
        [ task-path '[ _ utf8 set-file-contents ] when* ] bi
    ] with-directory ;

With that, we can finally save all the tasks, or all the draft tasks:

: save-all-tasks ( -- )
    all-tasks [ save-task ] each ;

: save-draft-tasks ( -- )
    draft-tasks [ save-task ] each ;

I used this, with some minor changes to ignore certain categories that do not contain solutions, as well as using Pandoc to convert the MediaWiki markup before embedding in the solution files.

Anyway, pretty cool!

Wed, 17 Jul 2024 14:00:00

John Benediktsson: Rosetta Code Revisited

I recently wrote about removing the Rosetta Code solutions from our main Factor repository. We only had 62 solutions out of 1,276 tasks, and I didn’t really want to maintain a subset of the solutions, nor mirror them ineffectively into the main git repository.

As it turns out – and pretty much immediately afterwards – I got curious enough to try and download all of the Factor solutions so we could maybe do some analysis of all the various solutions that have been contributed to the Rosetta Code project. And, it’s not a small amount of code – it’s 12,461 lines of Factor code!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 Language            Files        Lines         Code     Comments       Blanks
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 Factor               1663        74221        12461        55885         5875
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Not all of those are fully solved, but almost 1,000 of them seem to be!

This is available in the newly created factor-rosetta-code git repository, if anyone else is as curious as I was. I don’t think we are going to be able to consistently keep this in sync with the Rosetta Code website, but at least it represents a checkpoint today for quite a lot of nice Factor source code.

Some of these were written for older versions of Factor, but most of it is usable as is, or with minor edits.

Check it out!

Tue, 16 Jul 2024 14:00:00

Blogroll


planet-factor is an Atom/RSS aggregator that collects the contents of Factor-related blogs. It is inspired by Planet Lisp.

Syndicate