Thursday, October 3, 2013

Doubly-linked_list implemented in Algol68

I was pleasantly surprised how easy Doubly-linked_lists are in Algol68.

Here are a few tricks:
 1. How to append to the end of the list:
TAIL example list +:= this
2. How to prefix to the start of a list:
this +=: HEAD example list
3. How to insert in the middle of the list:
next of next of HEAD example list +:= this
4. How to extract an item from the list and iterate forward or backward:

LINK next = example list -:= this;
LINK prev = (this -=: example list)

 I only know a handful of languages so I was curious as to how other programming languages have integrated link-list, so I asked at StackExchange: What language has integrated “list insertion” as part of code *syntax*?

Over all the most interesting thing I found out is that is using a sentinel node makes thing so much easier....  It seems that you should not need one at all, but somewhere you need to store the address of the link, this forces you to check for it every time you insert/remove links from a list, just in case you are inserting before the "address" of this list, or (indeed), removing the link that is the "address" of the list.

Notice the following code is devoid of any "if" conditional statements when inserting or deleting items from the list.

e.g. Compare the "if" count in this Algol68 code to the "if" count in insert and remove code examples cited in wikipedia: "A doubly linked list has O(1) insertion and deletion at both ends, so is a natural choice for queues".

When I dropped the sentinel node altogether I quickly discovered this leads to an ambiguity when you try to insert a new link at the start of the list vs adding a link to the end of the list.  Annoying....

Compare with other languages: ALGOL 68 @ Rosettacode

Still... the following Algol68 code is rather nice!

File: prelude/Doubly-linked_list_Link.a68

# -*- coding: utf-8 -*- #
  mode VALUE = ~;
# For example: #
  mode VALUE = union(int, real, compl)
mode LINKNEW = struct (
  LINK next, prev,
  VALUE value
mode LINK = ref LINKNEW;

File: prelude/Doubly-linked_list_Operator.a68

# -*- coding: utf-8 -*- #
mode LIST = ref LISTNEW;
op LISTINIT = (LIST self)LIST: (
  self := (self, self, ~);
op ISEMPTY = (LIST self)bool:
  (LIST(prev of self) :=: LIST(self)) and (LIST(self) :=: LIST(next of self));
op HEAD = (LIST self)LINK: next of self;
op TAIL = (LIST self)LINK: prev of self;
# insert after #
op +:= = (LINK cursor, LINK link)LINK: (
  next of link := next of cursor;
  prev of link := cursor;
  next of cursor := link;
  prev of next of link := link;
# insert before #
op +=: = (LINK link, LINK cursor)LINK: prev of cursor +:= link;
# delete current and step forward #
op -:= = (LIST ignore, LINK link)LINK: (
  next of prev of link := next of link;
  prev of next of link := prev of link;
  next of link := prev of link := nil; # garbage collection hint #
# delete current and step backward #
prio -=: = 1;
op -=: = (LIST link, LIST ignore)LINK: (
  ignore -:= link; prev of link
prio ISIN = 1; # low priority #
op ISIN = (LINK link, LIST self)bool:
  link isnt LINK(self);

File: test/Doubly-linked_list_Operator_Usage.a68

#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
mode VALUE = string; # user defined data type #
pr read "prelude/doubly-linked_list_link.a68" pr;
pr read "prelude/doubly-linked_list_operator.a68" pr;
main: (
    []VALUE sample = ("Was", "it", "a", "cat", "I", "saw");
    LIST example list := LISTINIT heap LISTNEW;
    LINK this;
# Add some data to a list #
    for i to upb sample do
        this := heap LINKNEW;
        value of this := sample[i];
        TAIL example list +:= this
# Iterate throught the list forward #
    this := HEAD example list;
    print("Iterate forward: ");
    while this ISIN example list do
        print((value of this, " "));
        this := next of this
    print(new line);
# Iterate throught the list backward #
    this := TAIL example list;
    print("Iterate backward: ");
    while this ISIN example list do
        print((value of this, " "));
        this := prev of this
    print(new line);
# Finally empty the list #
    print("Empty from tail: ");
    while not ISEMPTY example list do
          this := (example list -:= TAIL example list);
          print((value of this, " "))
    print(new line)


Iterate forward: Was it a cat I saw 
Iterate backward: saw I cat a it Was
Empty from tail: saw I cat a it Was 

Thursday, September 5, 2013

Q: Run C or C++ file as a script, my "almost" c-interpreter and c-scripting utility.

This question on stackoverflow that sparked my curiosity:
"So this is probably a long shot, but is there any way to run a C or C++ file as a script"

With gcc it is not so straight forward, but with the tiny C compiler tcc this is easy, e.g.:
File: hw.c
#!/usr/local/bin/tcc -run
#include <stdio.h>

int main() 
    printf("Hello, world!\n");
    return 0;
¢ Didn't someone (Rusty?) manage to get linux to boot completely from a source-code C-script, starting with only a tcc binary? ¢

In Algol68g (my weekend extreme sport language) this is "reasonably" easy... mostly because a "#comment#" is native to the Algol68 language. e.g. here is an implementations of the classic echo command.

File: echo.a68
#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
STRING ofs := "";
FOR i FROM 4 TO argc DO print((ofs, argv(i))); ofs:=" " OD

But how can we natively do this in C with gcc? ...

Simple shebangs can help with scripting, e.g. "#!/usr/bin/env python" at the top of a Python script will allow it to be run in a terminal as "./".
The task Multiline shebang largely demonstrates how to use "shell" code in the shebang to compile and/or run source-code from a 3rd language.
However in this task Native shebang task we are go native. In the shebang, instead of running a shell, we call a binary-executable generated from the original native language, e.g. when using C with gcc "#!/usr/local/bin/script_gcc" to extract, compile and run the native "script" source code.
Other small innovations required of this Native shebang task:
  • Cache the executable in some appropriate place in a path, dependant on available write permissions.
  • Generate a new cached executable only when the source has been touched.
  • If a cached is available, then run this instead of regenerating a new executable.
  • Naturally, some languages are not compiled. These languages are forced to use shebang executables from another language, eg "#!/usr/bin/env python" uses the C binaries /usr/bin/env and /usr/bin/python. If this is the case, then simply document the details of the case.
  • In a perfect world, the test file (e.g. echo.c) would still be a valid program, and would compile without error using the native compiler (e.g. gcc for text.c). The problem is that "#!" is syntactically incorrect on many languages, but in others it can be parsed as a comment.
  • The "test binary" should be exec-ed and hence retain the original Process identifier.
Test case:
  • Create a simple "script file" (in the same native language) called "echo" then use the "script" to output "Hello, world!"


File: script_gcc.c
/* Optional: this C code initially is-being/can-be boot strapped (compiled) using bash */
#include <errno.h>
#include <libgen.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
/* the actual shebang for C target scripts is:
/* general readability constants */
typedef char /* const */ *STRING;
typedef enum{FALSE=0, TRUE=1} BOOL;
/* script_gcc.c specific constants */
#define DIALECT "c" /* or cpp */
const STRING
  COPTS="-lm -x "DIALECT,
/* general utility procedured */
char strcat_out[BUFSIZ];
  va_list ap;
  va_start(ap, argv);
  STRING arg;
  for(arg=argv; arg != ENDCAT; arg=va_arg(ap, STRING)){
     strncat(strcat_out, arg, sizeof strcat_out);
  return strndup(strcat_out, sizeof strcat_out);
char itoa_out[BUFSIZ];
STRING itoa(int i){
  sprintf(itoa_out, "%d", i);
  return itoa_out;
time_t modtime(STRING filename){
  struct stat buf;
  if(stat(filename, &buf) != EXIT_SUCCESS)perror(filename);
  return buf.st_mtime;
/* script_gcc specific procedure */
BOOL compile(STRING srcpath, STRING binpath){
  int out;
  STRING compiler_command=STRCAT(CC, " ", COPTS, " -o ", binpath, " -", ENDCAT);
  FILE *src=fopen(srcpath, "r"),
       *compiler=popen(compiler_command, "w");
  char buf[BUFSIZ];
  BOOL shebang;
  for(shebang=TRUE; fgets(buf, sizeof buf, src); shebang=FALSE)
    if(!shebang)fwrite(buf, strlen(buf), 1, compiler);
  return out;
void main(int argc, STRING *argv, STRING *envp){
  STRING binpath,
         argv0_basename=STRCAT(basename((char*)srcpath /*, .DIALECT */), ENDCAT),
         *dirnamew, *dirnamex;
  argv++; /* shift */
/* Warning: current dir "." is in path, AND * /tmp directories are common/shared */
  STRING paths[] = {
    dirname(strdup(srcpath)), /* not sure why strdup is required? */
    STRCAT(getenv("HOME"), "/bin", ENDCAT),
    STRCAT(getenv("HOME"), "/tmp", ENDCAT),
    STRCAT(getenv("HOME"), "/Desktop", ENDCAT),
/*  "/tmp" ... a  bit of a security hole */
  for(dirnamew = paths; *dirnamew; dirnamew++){
    if(access(*dirnamew, W_OK) == EXIT_SUCCESS) break;
/* if a CACHEd copy is not to be kept, then fork a sub-process to unlink the .out file */
    binpath=STRCAT(*dirnamew, "/", argv0_basename, itoa(getpid()), OEXT, ENDCAT);
    if(compile(srcpath, binpath) == EXIT_SUCCESS){
        sleep(0.1); unlink(binpath);
      } else {
        execvp(binpath, argv);
  } else {
/* else a CACHEd copy is kept, so find it */
    time_t modtime_srcpath = modtime(srcpath);
    for(dirnamex = paths; *dirnamex; dirnamex++){
      binpath=STRCAT(*dirnamex, "/", argv0_basename, OEXT, ENDCAT);
      if((access(binpath, X_OK) == EXIT_SUCCESS) && (modtime(binpath) >= modtime_srcpath))
        execvp(binpath, argv);
  binpath=STRCAT(*dirnamew, "/", argv0_basename, OEXT, ENDCAT);
  if(compile(srcpath, binpath) == EXIT_SUCCESS)
    execvp(binpath, argv);
  perror(STRCAT(binpath, ": executable not available", ENDCAT));
Test Source File: echo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char **argv, char **envp){
  char ofs = '\0';
  for(argv++; *argv; argv++){
    if(ofs)putchar(ofs); else ofs=' ';
    fwrite(*argv, strlen(*argv), 1, stdout);
Test Execution:
$ ./echo.c Hello, world!
Test Output:
Hello, world!

UNIX Shell

Works with: Bourne Again SHell
Note: this Native shebang task does not exactly apply to bash because bash is interpretive, but as a skeleton template the following script is an example of how compiled languages can implement the shebang. Also: this bash code can be used to automatically compile the C code in /usr/local/bin/script_gcc.c above.
# Actual shebang when using bash:
# Alternative shebang when using bash:
#!/bin/bash /usr/local/bin/
# CACHE=No # to turn off caching...
# Note: this shell should be re-written in actual C! :-)
DIALECT=c # or cpp
srcpath="$1"; shift # => "$@"
#basename="$(basename "$srcpath" ."$DIALECT")"
basename="$(basename "$srcpath")"
# Warning: current dir "." is in path, AND */tmp directories are common/shared
paths="$(dirname "$srcpath")
while read dirnamew; do
  [ -w "$dirnamew" ] && break
done << end_here_is
  sed -n '2,$p' "$srcpath" | "$CC" $COPTS -o "$binpath" -
if [ "'$CACHE'" = "'No'" ]; then
  if compile; then
    ( sleep 0.1; exec rm "$binpath" ) & exec "$binpath" "$@"
  while read dirnamex; do
    if [ -x "$binpath" -a "$binpath" -nt "$srcpath" ];
      then exec "$binpath" "$@"; fi
  done << end_here_is
  if compile; then exec "$binpath" "$@"; fi
  echo "$binpath: executable not available" 1>&2
  exit $ENOENT
Test Source File: echo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char **argv, char **envp){
  char ofs = '\0';
  for(argv++; *argv; argv++){
    if(ofs)putchar(ofs); else ofs=' ';
    fwrite(*argv, strlen(*argv), 1, stdout);
Test Execution:
$ ./echo.c Hello, world!
Test Output:
Hello, world!
Here is a summary of the input script files, together with binary files generated:
$ ls -ltr hw.* echo.* /usr/local/bin
-rwxr-xr-x. 1 nevillednz nevillednz   193 Sep  6 13:17 hw.c
-rwxr-xr-x. 1 nevillednz nevillednz  4757 Sep  6 13:18 hw.c.out
-rwxr-xr-x. 1 nevillednz nevillednz   131 Sep  6 13:19 echo.a68
-rwxr-xr-x. 1 nevillednz nevillednz 12373 Sep  6 13:20
-rwxr-xr-x. 1 nevillednz nevillednz   315 Sep  6 13:29 echo.c
-rwxr-xr-x. 1 nevillednz nevillednz  5128 Sep  6 13:30 echo.c.out

total 20
-rwxr-xr-x. 1 nevillednz nevillednz 1216 Sep  6 13:13
-rwxr-xr-x. 1 nevillednz nevillednz 3431 Sep  6 13:15 script_gcc.c
-rwxr-xr-x. 1 nevillednz nevillednz 8564 Sep  6 13:16 script_gcc.c.out

One interesting thing to observe is that "script_gcc.c" is boot strapped by "", so as long as gcc is installed, you don't have to compile anything... not even the script_gcc.c "script"...  (But you do have to have the right permissions to start off with!)


Sunday, May 12, 2013

Video: "Bringing Algol68 forward to its own time" FSCONS2011 (Free Society Conference and Nordic Summit)

  1. A Bit of History, 
  2. The Language, 
  3. The World Dominations Plan
c.f. video: Back to the Future - ALGOL 68

Truly amasing, even after 45 years the language still inspires adventure.

Saturday, April 27, 2013

User defined pipe and redirection operators... a code tribute to (my annoying cousin) Warren's encouragement... :-)

  1. These "pipes" can be any type (including tagged unions), in essence you have "strong typed" pipes (compile time checked) ...  Perfect for a message passing system.
  2. The shell "&" can also be implemented.  Happily the "&" is trivial when implemented with Algol68's parallel clause...  
Hope you enjoy this "space-aged" code (a.k.a. 1960s code)... :-)

 File: Iterator_pipe_operators.a68

  PAGEIN =         PAGE,
  FILTER = PROC(GENLINE)GENLINE, # the classic shell filter #
  MANYTOONE = PROC([]GENLINE)GENLINE; # eg cat, as in con[cat]enate #
PRIO =: = 5, << = 5, >> = 5;
OP <  = (FILTER filter, PAGEIN page)GENLINE: filter(READ page),
   <  = (MANYTOONE cmd, PAGEIN page)GENLINE: cmd(READ page),
   << = (FILTER filter, PAGEIN page)GENLINE: filter(READ page),
   >  = (GENLINE gen, PAGEOUT page)VOID: gen(WRITE page),
   >> = (GENLINE gen, PAGEAPPEND page)VOID: gen(APPEND page),
   =: = (GENLINE gen, FILTER filter)GENLINE: filter(gen),
   =: = (GENLINE gen, MANYTOONE cmd)GENLINE: cmd(gen);

File: Iterator_pipe_utilities.a68

 # Sample ''utilities'' PROCedure declarations #
PROC cat = ([]GENLINE argv)GENLINE:~;
PROC tee = ([]YIELDLINE args filter)FILTER:~;
PROC grep = (STRING pattern, []GENLINE argv)GENLINE:~;
PROC head = (INT n, []GENLINE args)GENLINE:~;
PROC tail = (INT n, []GENLINE args)GENLINE:~;

File: Iterator_pipe_page.a68

# Sample ''pipe I/O'' OPerator declarations #

File: test_Iterator_pipe_page.a68

#!/usr/local/bin/a68g --script #
# First define what kind of record (aka LINE) we are piping and filtering #
FORMAT line fmt = $xg$;
PR READ "Iterator_pipe_page.a68" PR
PR READ "Iterator_pipe_operators.a68" PR
PR READ "Iterator_pipe_utilities.a68" PR
PAGE list of computer scientists = (
  "Wil van der Aalst - business process management, process mining, Petri nets",
  "Hal Abelson - intersection of computing and teaching",
  "Serge Abiteboul - database theory",
  "Samson Abramsky - game semantics",
  "Leonard Adleman - RSA, DNA computing",
  "Manindra Agrawal - polynomial-time primality testing",
  "Luis von Ahn - human-based computation",
  "Alfred Aho - compilers book, the 'a' in AWK",
  "Stephen R. Bourne - Bourne shell, portable ALGOL 68C compiler",
  "Kees Koster - ALGOL 68",
  "Lambert Meertens - ALGOL 68, ABC (programming language)",
  "Peter Naur - BNF, ALGOL 60",
  "Guido van Rossum - Python (programming language)",
  "Adriaan van Wijngaarden - Dutch pioneer; ARRA, ALGOL",
  "Dennis E. Wisnosky - Integrated Computer-Aided Manufacturing (ICAM), IDEF",
  "Stephen Wolfram - Mathematica",
  "William Wulf - compilers",
  "Edward Yourdon - Structured Systems Analysis and Design Method",
  "Lotfi Zadeh - fuzzy logic",
  "Arif Zaman - Pseudo-random number generator",
  "Albert Zomaya - Australian pioneer of scheduling in parallel and distributed systems",
  "Konrad Zuse - German pioneer of hardware and software"
PAGE algol pioneers list, the scientists list;
PAGE aa;
# Now do a bit of plumbing: #
    head(4, ) <  list of computer scientists,
    cat(READ list of computer scientists) =: grep("ALGOL", ) =: tee(WRITE algol pioneers list),
    tail(4, READ list of computer scientists)
  )) =: sort =: uniq =: tee(WRITE the scientists list) =: grep("aa", ) >> aa;
# Finally check the result: #
  $"Pioneer: "$, line fmt, aa, $l$,
  $"Number of Algol pioneers: "g(-0)$, UPB algol pioneers list, $l$,
  $"Number of scientists: "g(-0)$, UPB the scientists list, $l$


Pioneer:  Adriaan van Wijngaarden - Dutch pioneer; ARRA, ALGOL
Number of Algol pioneers: 6
Number of scientists: 15

Saturday, April 20, 2013

Have you ever wanted to test drive Algol68?... are ANY of the rumours true?

Have you ever coded in Algol68?... 

Or have you ever wanted to test drive Algol68?...

If so, download Linux's Algol68 Compiler, Interpreter & Runtime:
But wait... maybe you want to hack your first "Hello, world!" program and run it online NOW:
NJoy NevilleDNZ

Wednesday, April 3, 2013

Algol68 FAQ: re: What operators in C were modeled on similar operators in ALGOL 68?

The short answer is probably these C operators +=, -=, *=, /= * %= are from Algol68′s +:=, -:=, *:=, /:= & %:=.

c.f. usenet: Ada and C and Algol 68

BTW: The best quote about C’s ancestory comes from Dennis Ritchie himself:
“The scheme of type composition adopted by C owes considerable debt to Algol 68, although it did not, perhaps, emerge in a form that Algol’s adherents would approve of. The central notion I captured from Algol was a type structure based on atomic types (including structures), composed into arrays, pointers (references), and functions (procedures). Algol 68′s concept of unions and casts also had an influence that appeared later.” Apr 1993 c.f. Dennis Ritchie (April 1993). "The Development of the C Language" (PDF)

End of short answer…
——– 8>< - - - - - - - - cut here - - - - - - - -

But note that the /= and /:= are subtly different. Also C's %= is the same as Algol's %*:= operator.

Note also that the majority of C's operators came from Algol (+ – * / = ≠ etc ). However the “%” operator is notability different.
* Wikipedia: Monadic_operators
* Wikipedia: Dyadic_operators_with_associated_priorities

C has the “return” and “sizeof” operator, whereas Algol68 has syntax “EXIT” (or "□") and operator “UPB”  (or  "⌈") that achieve a similar function.

Algol 68 also has some related constants: “max int”, “max real”, “int width”, “real width” etc to determine sizes of things. These are not the same a C’s sizeof, but similar.

The most peculiar operators of C’s are /\ & \/, these come from Algol's ∧ & ∨ operators. These “C originals” were replaced by the current && and || operators. c.f. What _did_ the C operators /\ and \/ do?

Algol68 further allows operators to be define using non-ASCII characters:
               ×, ÷, ≤, ≥, ¬, ∨, ∧, , ↓, ↑, ⌊, ⌈, ⎩, ⎧ and ⊥;
And used the characters →, ○, □, ␣ and ¢ for other purposes. It is kind of like Algol68 was taking the liberty of using unicode some 20 years before Unicode characters were defined. {Earlier Algol60 used non-ASCII ⊂ and ≡}

* C's: int i = b ? a : b; /* pick maximum */
* A68′s: INT i := ( a > b | a | b );

c.f. Wikipedia: ?: - a ternary operator

The assignment “:=” looks like an operator, but in terms of “Algol68″ OPerators it isn’t. I believe they are called “Units associated with names” c.f. Array, Procedure, Dereference and coercion operations
(Or – if you are a language lawyer c.f. Algol 68 r1 report.html#52)

Similarly: Left assign, right assign and compare ( :=, =:, =) are also not "Algol68" Operators.

Pointers are not operators per se. There are a few “identity relations” associated with pointers: e.g. :=:, :/=:, IS & ISNT
c.f. Assignation and identity relations etc
(Or – if you are a language lawyer c.f. Algol 68 r1 report.html#5221)

Monday, April 1, 2013

Thinking about Go documentation - Language Specification through the years ... Algol68 then, then C89 & Go now. (From: Google Groups/golang-nuts, with links to original A68 & C89 specs&books as PDFs)

ALGOL 68 was the first (and possibly one of the last) major language for which a full formal definition was made before it was implemented.
C.H.A. Koster Algol68 Report co-editor, [7]
Sadly Koster was killed in a motorcycle accident last week. c.f.

1960s was a time for Informaticians to blaze a path and the construction of the Algol68 Report was a very early example of collaborations that has left echos in how collaborations have been done ever since.  Aside from being the first as above, it was early IT days so the actual report may well have been the first in several other areas.  It was certainly pioneering.

For example:
  • "Translations of the standard were made for Russian, German, French and Bulgarian, and then later Japanese and Chinese.  The standard was also made available in Braille."
    • The report "invented" its own vocabulary as was mentioned above.  
      • My favourite is GOMMA, for a ";" meaning "Go on comma", i.e. sequentially (vs in parallel or collaterally)
    • Arguably this vocabulary aided in the documents translation, moreover served as a technical blue print for actual implementation in other countries on other disparate computer systems (6-bit, 7-bit, 8-bit chars, 16-bit, 24-bit, 36-bit CPUs etc.)
    • (Maybe) As a result there are at least 20 independently constructed Algo68 compilers, plus a few interesting dialects such as S3 & Mary.
  • IMHO the report was targeted at compiler implementers not end users. 
    • e.g. Algol68's description is not just a 4 page BNF description as it includes lots of language semantic rules, hence it is not just purely about syntax.  
    • {Iconically here the Algol68 Report breaks "Wadler's Law": about semantics vs syntax.}
    • Moreover the alternative could have been be to "code" these semantics in "English", hope they survive linguistic translations, or implement them in a 3GL like C then wait 10+ years for a the formal "English" version to be drafted as a actual formal standard.
  • The "Data Security" requirement allowed detecting semantic errors at compile time.
    • Compile time detection is better then run time cure (such as type error exception handling while code is in production)
    • Most of these "Data Security" semantics are specifically detailed in the actual "Algol68 Report" and were a language requirement.
Regarding documentation, here are some links:
Some people prefer to learn a language by reading source code: Don't get me wrong, the Algol68 Report is hard to read, especially to non-compiler writers.
  • Compare with the first C standard
  • The Go Programming Language Specification, Version of September 4, 2012
    • 110 pages of A4 as at March 2013.
    • Clear and easy to read.
    • Some of "English" semantics
      • Fortunately(?) only one implementation of Go will ever need exist
    • Good syntax description, but not much in the way of "Formal Semantics",
Confession: I have not learned Go yet... I'm itching to give it a go as I like many of the ideas incorporated.

All the best and enjoy