NevilleDNZ

Saturday, December 27, 2014

A bit of fun with Jabberwocky, classes, mixins, python and method resolution order (MRO)

I was trying to figure out and demonstrate python's Member Resolution Order... In particular, pay attention to the output from __str__...

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class BeastBase(dict):
def __init__(self, **characteristics):
super(BeastBase, self).__init__(**characteristics)

def __str__(self):
return "; ".join(["%s=%r"%item for item in super(BeastBase, self).iteritems()])

class Mixin(object): pass

class BitingMixin(Mixin):
def __init__(self, jaws=2, teeth_per_mouth=32, **characteristics):
self.jaws=jaws
self.teeth_per_mouth=teeth_per_mouth
super(BitingMixin, self).__init__(**characteristics)

def bite(self):
print "Bite: jaws=%s, teeth=%s"%(self.jaws, self.teeth_per_mouth*self.jaws/2)

def __str__(self):
return "Jawed: %s; %s"%(self.jaws, super(BitingMixin, self).__str__())

class JawedBeast(BeastBase, BitingMixin): pass

class ClawingMixin(Mixin):
def __init__(self, feet=4, toes_per_foot=3, **characteristics):
self.feet=feet
self.toes_per_foot=toes_per_foot
super(ClawingMixin, self).__init__(**characteristics)

def catch(self):
print "Catch: feet=%s, toes=%s"%(self.feet, self.toes_per_foot*self.feet)

def __str__(self):
return "Claws: %s; %s"%(self.toes_per_foot*self.feet, super(ClawingMixin, self).__str__())

class ClawedBeast(BeastBase, ClawingMixin): pass

class FlamingMixin(Mixin):
def __init__(self, eyes=6, flames_per_eye=1, **characteristics):
self.eyes=eyes
self.flames_per_eye=flames_per_eye
super(FlamingMixin, self).__init__(**characteristics)

def flame(self):
print "Flames:", self.eyes*self.flames_per_eye

def __str__(self):
return "Eyes: %s, Flames: %s; %s"%(self.eyes, self.eyes*self.flames_per_eye, super(FlamingMixin, self).__str__())

class FlamedBeast(FlamingMixin, BeastBase): pass

class WhifflingMixin(Mixin):
def whiffle(self): print "Whiffle...."
def __str__(self): return "Whiffling... "+super(WhifflingMixin, self).__str__()

class WhifflingBeast(WhifflingMixin, BeastBase): pass

class BurblingMixin(Mixin):
def burble(self): print "Burble...."
def __str__(self): return "Burbling... "+super(BurblingMixin, self).__str__()

class BurblingBeast(BurblingMixin, BeastBase): pass

class Jabberwocky(BitingMixin, ClawingMixin, FlamingMixin, WhifflingMixin, BurblingMixin, BeastBase):
def __init__(self, **characteristics):
super(Jabberwocky, self).__init__(**characteristics)

def __str__(self):
return "JabberWocky: "+super(Jabberwocky, self).__str__()+" ... Beware! "

if __name__ == "__main__":

# Beware the Jabberwock, my son!
jabberwocky1=Jabberwocky(personality="Friendly", consideration="Temperamental", eyes=5, flames_per_eye=3)
print jabberwocky1

# Beware the Jubjub bird, and shun
# The frumious Bandersnatch!

# The jaws that bite, the claws that catch!
jabberwocky1.bite()
jabberwocky1.catch()

# And as in uffish thought he stood,
# The Jabberwock, with eyes of flame,
jabberwocky1.flame()

# Came whiffling through the tulgey wood,
jabberwocky1.whiffle()
# And burbled as it came!
jabberwocky1.burble()

Output:
JabberWocky: Jawed: 2; Claws: 12; Eyes: 5, Flames: 15; Whiffling... Burbling... consideration='Temperamental'; personality='Friendly' ... Beware!
Bite: jaws=2, teeth=32
Catch: feet=4, toes=12
Flames: 15
Whiffle....
Burble....

Saturday, March 8, 2014

A brief history of Air Traffic Control and on-line Aircraft Tracking Systems...

Today's loss of flight MH370 got me wꜵndering the internet briefly investigating how Aircraft Tracking/Control systems have changed over the years.

1958 - Semi-Automatic Ground Environment - The prototype was an IBM 4020 Military Computer
"SAGE—Air Force project 416L—became the pattern for at least twenty-five other major military command-control systems… These were the so-called “Big L” systems [and] included 425L, the NORAD system; 438L, the Air Force Intelligence Data Handling System; and 474L, the Ballistic Missile Early Warning System (BMEWS). … Project 465L, the SAC Control System (SACCS) [with] over a million lines, reached four times the size of the SAGE code and consumed 1,400 man-years of programming; SDC invented a major computer language, JOVIAL, specifically for this project."

http://www.computermuseum.li/Testpage/IBM-SAGE-computer.htm

1958 - Algol58/JOVIAL created.
1961- AN/FSQ-31V ‎ - SAGE Solid State Computer was a planned military computer central for deployment to Super Combat Centers in nuclear bunkers
1968 - ALGOL 68 Final Report^r0 Presented at Munich Meeting

1980 - re: 1968 ... The best we could do was to send with it a minority report, stating our considered view that, "... as a tool for the reliable creation of sophisticated programs, the language [ALGOL 68] was a failure." [...] - C. A. R. Hoare Oct 1980

2002 - Air Traffic Control dependent on 1970s software until 2011
"The IBM mainframe-based Flight Data Processing System (FDPS) based at West Drayton, near Heathrow, crashed twice in 2002, causing major disruption to air traffic and delays for thousands of passengers."
2004 - Failed air traffic control system dates back to 70s
2007 - DDC-I Announces Industry's First Quick-Turn, Low-Cost JOVIAL-to-C Conversion Service
2011 - The futurist: The US’ new air traffic control system
2011 - FAA Remains Quiet on Eram Budget Overruns, Delay
2013 - How UK air traffic control system was caught asleep on the job
2012-2025 "Next Generation Air Transportation System"

... estimates that by 2018, NextGen will reduce aviation fuel consumption by 1.4 billion gallons, reduce emissions by 14 million tons and save $23 billion in costs.^[5] Each mile in the air costs an airline about $0.10-$0.15 per seat in operating expenses like flight crew and fuel.^[6]

¢ My commentary: Algol68 should have been adopted and replaced Algol60, but [IMHO] instead Algol68 was shot down by a vocal minority. Sure, I would love to own and drive a 1961 E-type Jaguar, but it would be better with airbags and a GPS. So the 1968 Security, Efficiency, Type-safety, Standardization and Internationalization offered by Algol68 (which predates C11 well by over 40 years!) should have been leveraged in 1968! Algol68 is kind of like a 1961 E-type Jaguar, but with seat-belts, air-bags, a roll-bar, traction-control and modern tyres! ¢

BTW: As a wonderful example of today's "crowd-sourcing": Do you regularly have aircraft pass (or cross paths) over your home/community? but you live in the "middle-of-every-where"... How about becoming part of "flight-aware" and to help track aircraft? If your location is "desirable", then you may get a free [ADS-B] to put on your roof... Here is the current coverage map: http://flightaware.com/adsb/coverage.

Click MH370 for an example of this flightaware's tracking of MH370.

Update: My best guess as to where MH370 is... On a "great circle" west of Kuda Huvadhoo (in the Maldives).

Friday, March 7, 2014

Was Algol ever used for “mainstream” programming?

¢ I rather liked this answer on Stackoverflow, so I am reproducing it here ¢

Algol58 seems to have been the most successful in terms of important applications.

From Wikipedia:

JOVIAL is an acronym for “Jules Own Version of the International Algorithmic Language.” The “International Algorithmic Language” was a name originally proposed for ALGOL 58. It was developed to compose software for the electronics of military aircraft by Jules Schwartz in 1959.

Then:

Notable systems using JOVIAL include the Milstar Communications Satellite, Advanced Cruise Missile, B-52, B-1B, B-2 bombers, C-130, C-141, and C-17 transport aircraft, F-111, F-15, F-16 (prior to Block 50), and F-117 fighter aircraft, LANTIRN, U-2 aircraft, E-3 Sentry AWACS aircraft, Navy Aegis cruisers, Army Multiple Launch Rocket System (MLRS), Army UH-60 Black Hawk helicopters, F100, F117, and F119 jet engines, the NORAD air defense & control system (Hughes HME-5118ME system) and RL-10 rocket engines. Airborne radar systems with embedded JOVIAL software include the APG-70, APG-71 and APG-73

ALGOL 68 was used in part of DRA for the same purpose. cf. Wikipedia:

The ”’Defence Research Agency”’ (normally known as ”’DRA”’), was an executive agency of the UK Ministry of Defence (MOD) from April 1991 until April 1995. At the time the DRA was Britain’s largest science and technology organisation.

DRA’s Algol68 compiler was finally open-sourced in April 1999 and is now available for linux for download from sourceforge. (However an interpreter for “Algol68g” is easier to use).

ICL’s Algol68 was/is S3 – It was developed by the UK company International Computers Limited (ICL) for its 2900 Series mainframes. It is a system programming language based on ALGOL 68 but with data types and operators aligned to those offered by the 2900 Series. It was the implementation language of the operating system VME.

There are (at least) two other British operating systems – Flex and Cambridge_CAP_computer – written in Algol68 variants. And also 1 Soviet OS: Эльбрус-1 (Elbrus-1), but I have yet to find any of their source code. (If anyone can find and distribute to this source code please let me know)

BTW: I believe that VME is still running – in production – as a Linux/Unixware guest VM. Mostly at Commonwealth of Nations Custom/Immigration services.
Also over the same period the USSR was using Algol68, c.f. history link. Algol68 is used in Russian telephone exchanges. And Algol58 was used in the Russian “Buran/Буран” Space Shuttle landing system.

ALGOL68 was internationalized in 1968. I suspect there are other Algol projects in other countries. esp in German, in Dutch Japanese and Chinese but I have no details.

If you want to actually tryout Algol68 and/or contribute your code, check out Rosettacode’s ALGOL 68 repository, then as a class project try one of the “Tasks not implemented“.

enjoy!

Wednesday, February 12, 2014

Déjà vu: SMIL-2.0 vs Algol-68

SMIL-2.0: The example assume video and audio media that are recorded to be in exact sync with one another:

<par dur="indefinite">
  <img id="foo" end="click" .../>
  <video id="bar" begin="foo.endEvent" .../>
  <audio id="copy" begin="foo.end" .../>
</par>

Algol-68: An example of a parallel-clause which synchronizes eating and speaking:

PROC VOID eat, speak; SEMA mouth = LEVEL 1;
   PAR BEGIN
       DO
           DOWN mouth;
           eat;
           UP mouth
       OD, 
       DO
           DOWN mouth;
           speak;
           UP mouth
       OD
   END.

...

plus ça change, plus c'est la même chose
c.f. golang: On Go (published 2009 November 15)

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 -*- #
COMMENT REQUIRES:
  mode VALUE = ~;
# For example: #
  mode VALUE = union(int, real, compl)
end COMMENT
 
mode LINKNEW = struct (
  LINK next, prev,
  VALUE value
);
 
mode LINK = ref LINKNEW;
 
skip

File: prelude/Doubly-linked_list_Operator.a68

# -*- coding: utf-8 -*- #
mode LISTNEW = LINKNEW;
mode LIST = ref LISTNEW;
 
op LISTINIT = (LIST self)LIST: (
  self := (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;
  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 #
  link
);
 
# 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);
 
skip

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
    od;
 
# 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
    od;
    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
    od;
    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, " "))
    od;
    print(new line)
)

Output:

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:

Q: Run C or C++ file as a script

"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 "./script.py".
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.

Difficulties:

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!"

C

File: script_gcc.c

#!/usr/local/bin/script_gcc.sh
/* Optional: this C code initially is-being/can-be boot strapped (compiled) using bash script_gcc.sh */
#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:
#!/usr/local/bin/script_gcc.c
*/
 
/* general readability constants */
typedef char /* const */ *STRING;
typedef enum{FALSE=0, TRUE=1} BOOL;
const STRING ENDCAT = NULL;
 
/* script_gcc.c specific constants */
#define DIALECT "c" /* or cpp */
const STRING
  CC="gcc",
  COPTS="-lm -x "DIALECT,
  IEXT="."DIALECT,
  OEXT=".out";
const BOOL OPT_CACHE = TRUE;
 
/* general utility procedured */
char strcat_out[BUFSIZ];
 
STRING STRCAT(STRING argv, ... ){
  va_list ap;
  va_start(ap, argv);
  STRING arg;
  strcat_out[0]='\0';
  for(arg=argv; arg != ENDCAT; arg=va_arg(ap, STRING)){
     strncat(strcat_out, arg, sizeof strcat_out);
  }
  va_end(ap);
  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);
 
  out=pclose(compiler);
  return out;
}
 
void main(int argc, STRING *argv, STRING *envp){
 
  STRING binpath,
         srcpath=argv[1],
         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),
    "/usr/local/bin",
    ".",
    STRCAT(getenv("HOME"), "/tmp", ENDCAT),
    getenv("HOME"),
    STRCAT(getenv("HOME"), "/Desktop", ENDCAT),
/*  "/tmp" ... a  bit of a security hole */
    ENDCAT
  };
 
  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 */
  if(OPT_CACHE == FALSE){
    binpath=STRCAT(*dirnamew, "/", argv0_basename, itoa(getpid()), OEXT, ENDCAT);
    if(compile(srcpath, binpath) == EXIT_SUCCESS){
      if(fork()){
        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));
  exit(errno);
}

Test Source File: echo.c

#!/usr/local/bin/script_gcc.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);
  }
  putchar('\n');
  exit(EXIT_SUCCESS);
}

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.
File: script_gcc.sh

#!/bin/bash
 
# Actual shebang when using bash:
#!/usr/local/bin/script_gcc.sh
 
# Alternative shebang when using bash:
#!/bin/bash /usr/local/bin/script_gcc.sh
 
# CACHE=No # to turn off caching...
 
# Note: this shell should be re-written in actual C! :-)
 
DIALECT=c # or cpp
CC="gcc"
COPTS="-lm -x $DIALECT"
IEXT=.$DIALECT
OEXT=.out
 
ENOENT=2
 
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")
$HOME/bin
/usr/local/bin
.
$HOME/tmp
$HOME
$HOME/Desktop"
#/tmp
 
while read dirnamew; do
  [ -w "$dirnamew" ] && break
done << end_here_is
$paths
end_here_is
 
compile(){
  sed -n '2,$p' "$srcpath" | "$CC" $COPTS -o "$binpath" -
}
 
if [ "'$CACHE'" = "'No'" ]; then
  binpath="$dirnamew/$basename-v$$$OEXT"
  if compile; then
    ( sleep 0.1; exec rm "$binpath" ) & exec "$binpath" "$@"
  fi
else
  while read dirnamex; do
    binpath="$dirnamex/$basename$OEXT"
    if [ -x "$binpath" -a "$binpath" -nt "$srcpath" ];
      then exec "$binpath" "$@"; fi
  done << end_here_is
$paths
end_here_is
 
  binpath="$dirnamew/$basename$OEXT"
  if compile; then exec "$binpath" "$@"; fi
 
  echo "$binpath: executable not available" 1>&2
  exit $ENOENT
fi