coding trails

hello wisconsin!!!

schildawg

The Word

by Leave a Comment

ἐν ἀρχῇ ἦν ὁ λόγος — Ιωάννης ο αγαπημένος

To understand artificial intelligence, you have to start at the beginning—the word.   If you look up a word in a dictionary, it is defined by other words, which are in turn defined by even more words.  If you keep repeating this process, you end up with a network consisting of all of the words in a language.  You can start at any word in that language and plot a course to any other word.

We tend to think of the relationship between words as being vague or fuzzy, but in fact a language is a precise mathematical model in which distances between words can be measured, angles calculated, and relationships derived using trigonometry and calculus.

A word is a singular point in a hyper-dimensional field.  The number of dimensions determine the semantic preciseness of the word.  Less than a hundred dimensions and the word loses its precision, like a picture out of focus.  If you have more than several hundred dimensions, you start to experience diminishing returns.  Three hundred dimensions is sufficient for general purposes, but models exist with several thousand dimensions.

You could think of words as being stars in a vast hyper-dimensional universe.  It is possible to conceive of time being the fourth dimension and the multiverse as being the fifth, but if you go beyond that it quickly becomes incomprehensible.  But there is a way to visualize it that is easily understandable.  A three dimensional object can be drawn on a mostly two dimensional piece of paper.  A four dimensional being would appear to us as three dimensional with movement.

If you take the dimensions of a word and divide it into three-dimensional slices and superimpose them on top of each other, you have a constellation of dozens of bright stars and hundreds of faint ones.  At the center of gravity of this constellation there is a world, where you can look up into the sky and see millions of other stars, both bright and dim.

If you stand on world “Man” and look up and find the star “King” you can teleport to the same place on world “Woman” and in the exact same place in the sky will be the star “Queen.”  Similarly, looking at “Queen” from “King” is the exact same relationship as “Woman” from “Man.”  There are profound implications and insights that can be derived from this relationship, which we will explore in future posts.

If you break down a word even further into one-dimension points, we now have hundreds or even thousands of sliders or knobs which can be adjusted from off to completely on.  This is the definition of a neuron in a neural network.  With this paradigm, we can conceive of a word as being a “brain” which takes in a phrase of words and calculates the next word.

Returning to the analogy of a galaxy of stars, a word is a sector of space into which a space ship enters and the gravitational pull of each of the stars redirects and forwards the ship to the next sector in space.  The ship starts out with a prompt, and bounces from word to word until it reaches the end of its journal with a complete response.

You see, a language model is a formula, or a condensed mathematical model of the entirety of human knowledge.  The coding necessary to build this model is not complex or even particularly sophisticated.  It just required the Internet to exist, and a great deal of time, and a lot of money to train it.

Now that we have the model, it’s easy and relatively inexpensive to copy it in high and low definition.  But we don’t know what’s in it.  We don’t even understand what all the higher dimensions are.  This is, in my opinion “the final frontier.”  There are insights to be gleaned in linguistics, psychology, and philosophy.   A whole new universe exists which is waiting to be discovered and explored!

Filed Under: AI

Two Sum

by Leave a Comment

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Tests

Let’s start out with the tests:

procedure AssertTwoSum(Input: Array, Target, First, Second: Integer);
begin
    var Result := TwoSum(Input, Target); 
    
    AssertEqual (0, Result[0]); 
    AssertEqual (1, Result[1]);   
end

test '2 7 11 5';
begin
    AssertTwoSum ([2, 7, 11, 15], Target: 9, First: 0, Second: 1); 
end

test '3 2 4';
begin
    AssertTwoSum ([3, 2, 4], Target: 6, First: 1, Second: 2);
end

test '3 3';
begin
    AssertTwoSum ([3, 3], Target: 6, First: 0, Second: 1); 
end

 

Solution

For each item in the array of integers, loop through the array, comparing if the both values add up to the target, making sure the indexes are not the same.  

function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
begin
    for var I := 0; I < Input.Length; I := I + 1 do
    begin
        for var J := 0; J < Input.Length; J := J + 1 do
        begin
            if Input[I] + Input[J] = Target And I <> J then
            begin
                Exit [I, J];
            end
        end
    end
    raise 'Invalid Input!';
end

This is the simplest way to solve the problem, but not the most time efficient.  It has a time complexity of O(n2).  The time can be reduced by initializing the J loop variable with I, since, if you think about it, these permutations have already been covered.

Let’s run the tests:

Alternate Solution

With a solution in place, and all our tests passing, now we can think of performance.  By adding a hash table lookup we can reduce the time complexity to O(n) at the cost of the extra memory that the hash table takes up.  

function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
var
   Lookup : Map := Map();

begin
    for var I := 0; I < Input.Length; I := I + 1 do
    begin
        var Value := Input[I];
        var Complement := Target - Value;

        if Lookup.Contains(Complement) then
        begin
            Exit [Lookup.Get(Complement), I];
        end
        Lookup.Put(Value, I);
    end
    raise 'Invalid Input!';
end

Of course, the performance is going to depend on the implementation of the hash table, but for a properly written hash table the lookup should be in constant time regardless of how many keys are in the table.

Replace the implementation, and run the tests again!

World’s Tiniest Language

by Leave a Comment

BrainF*ck is an esoteric language created in 1993 by Swiss physics student Urban Müller.  (Don’t blame me, I didn’t come up with the name!)  It consists of 8 instructions and is fully Turing-complete.  Here is a complete implementation in Algol-24:

var MEMORY_SIZE  := 65535;
var ScreenBuffer := '';

procedure Interpret(Code : String);
var
   Loop := 0;
   Instruction := 0;
   Memory := Buffer(MEMORY_SIZE, 0);

begin
   procedure Find(StartChar, EndChar, Increment);
   begin
      Instruction := Instruction + Increment;
      while Loop > 0 Or Code[Instruction] <> EndChar do
      begin
         if Code[Instruction] = StartChar then
            Loop := Loop + 1;
         else if Code[Instruction] = EndChar then
            Loop := Loop - 1;
         
         Instruction := Instruction + Increment;
      end
   end

   while Instruction < Length(Code) do
   begin
      var Value := Memory.GetValue();

      case Code[Instruction] of
         '>' : Memory.Advance();
         '<' : Memory.Rewind();
         '+' : Memory.SetValue(Value + 1);
         '-' : Memory.SetValue(Value - 1);
         '.' : ScreenBuffer := ScreenBuffer + Char(Value);
         '[' : if Value = 0 then Find('[', ']', 1);
         ']' : if Value <> 0 then Find(']', '[', -1);
      end
      Instruction := Instruction + 1;
   end
end

test 'Run BF Program';
begin
   var Code := '-[------->+<]>-.-[->+++++<]>++.+++++++..+++.[--->+<]>-----.' + 
      '---[->+++<]>.+++[->++++<]>+.++++++++++.+++[->+++<]>+.++++++++++++.-.' + 
      '+++++.----------.+++++.-[->+++++<]>.';
   Interpret(Code);

   AssertEqual('????? ??????????', ScreenBuffer);
end

Coming in 42 lines of code, it is truly tiny!  Lamborghini to the first person in the comments who can fill in the value to make the unit test pass 😀

******************************************

If you run this program:

[sierpinski.b -- display Sierpinski triangle
(c) 2016 Daniel B. Cristofani]
++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<]>.>+[>>]>+]

This is the output:

Pretty amazing, huh?

How I Learn A New Programming Language

by Leave a Comment

How I Learn A New Programming Language

Recently I received an invitation on LinkedIn as a selected “expert” to write up the best way to learn a new programming language.  It’s a good topic so I figured I’d go ahead and cover it here.

Get It In Your Brain

When I learned Rust, the recommended approach was to read through the book once as quickly as possible to get the entire overview into your brain.  I was happy to see this advice, because I have been doing this for many years.  Back in the 1980’s my dad photocopied the IBM BASIC manual, had it bound in 4 or 5 volumes, and put it on my desk to read.  The stack of books was intimidating.  I started reading and quit.  I couldn’t understand half of it.  My dad said, “Read it and don’t try to understand.  You will remember it when you need to.”  Over the years I have learned to trust the capability of the mind to comprehend things beyond our conscious understanding.  But it can’t remember something if you haven’t read or heard it.

Type Out the Examples

The next step is to slow down and attempt to understand the concepts.  Find a good book, and go through it one chapter per day.  To move beyond the academic and into the practical, type in each example and run it.  Try playing around with the examples, changing values to really grasp what is being illustrated by the example.  For me, this generally, takes a month, and can take anywhere between 30 – 100 hours.

Learn the Culture

When I learned Java, my mentor told me, “If you haven’t read Effective Java, you aren’t really a Java developer.” I followed his example and read, and re-read Effective Java every year for close to a decade.  It introduced me to the concept of idioms in programming.  Beyond simple syntax difference, every language is designed with a certain development philosophy.  You can’t program Java the way you would C++, or Python the way you would Java, or for that matter Rust like any other language.  I always start out learning a new language by searching for the “Effective Java” for that language.  They usually start with “Effective”, like “Effective C,” “Effective C++,” “Effective Python,” etc.

Beyond syntax and idioms, there is also culture.  This can take much longer to absorb and assimilate.  Typically a community grows around a language and acceptable patterns and practices emerge.  What is perfectly acceptable in one language could be an egregious “sin” in another.  I have found, for example, the Rust community is extremely harsh about the “right and wrong” ways to program in Rust.

Practice, Practice, Practice

You can’t learn a programming language without programming in it.  I have a “playground” project which contains reproductions of all the coding tests I’ve taken throughout my career, all the way back to Fizz Buzz.  I rewrite my “playground” in each new language I learn, copying the style, idioms, and culture to the best of my ability.  Recently I have been writing Lox from “Crafting Interpreters” in each new language.  Between the code and unit tests this typically comes up to around 5 – 7K lines of code.

Summary

When I learned Rust, I read “The Rust Programming Language” in 2 days.  Then, I spent 3 weeks walking through the book chapter-by-chapter, running each code example.  Then I translated my “playground” to Rust.  Then I wrote 5,000 lines of Rust, converting the Lox tree-walk interpreter.  Well, at least till I got stuck on Environments, and realized I didn’t understand Rust’s memory management and lifecycles as well as I thought I did.  So, I read the book again, and rewrote Lox using smart pointers.  Final step, add “Rust” to resume… as beginner 🙂

CIA Adventure

by Leave a Comment

CIA Adventure is a text adventure game written for DOS in 1982, which I have been fascinated with for 40 years.  Frustrated with trying to get the ruby out of the glass case at the end of the game, I peeked into the BASIC code to find the answer.

CIA.bas consists of 271 lines of dense, unreadable spaghetti code.  Working my way through the code line by line, I discovered the glass case needed to be cut with a razor blade!  The problem was solved, but it created a life-long obsession.  As I lay in bed that night, I had a crystal-clear image in my mind of how the code should look like.  

Over the years, I have written and rewritten CIA over and over, in various languages, such as Pascal, C++, and Java.  Each try brought me closer, but fell short of my vision because of language constraints.  A domain-specific language I wrote in 2011 came incredibly close.  It was concise and readable, but ultimately didn’t have the power or flexibility I wanted.

With the completion of JPascal this May, I decided to have some fun and take another shot at CIA.  (JPascal is a tree-walk interpreter prototype of Algol-24).  The result is exactly what I dreamed of 40 years ago!  30 rooms, 50 items, and 19 verbs.  The code is concise and easy-to-read, but still has the power and flexibility I wanted.  As a matter of fact, it turned out even better than I had envisioned.  It has a full regression of 170 unit tests which was invaluable in converting all of the rooms and items to prototypes.

I am very proud of this accomplishment.  It is the proof-of-concept showcasing Algol-24, and it the foundation on which PRISM will be built.  But more than that, it captures my love of programming as an art form.  There is no better code demonstrating who I am as a programmer, from the language syntax, all the way to the storybook style!

Take a look:
CIA Adventure

Crafting An Interpreter In Pascal!

by Leave a Comment

Crafting Interpreters by Bob Nystrom has become one of my favorite programming books.  It walks you line-by-line through creating Lox, a fully functional object-oriented programming language.  Over the past year, I’ve worked my way through the book five times, implementing the tree-walk interpreter in Java, Python, and Rust, and the byte-code virtual machine in C and Zig.  My next challenge would be to write it in Pascal!

Pascal is my first love.  I started learning programming in 1984 on an IBM computer in Basica.  I didn’t like the way my programs scrolled onto the screen line-by-line.  I wanted them to pop onto the screen the way Norton Utilities did.  So, I picked up Peter Norton’s book and taught myself Assembly.  A friend saw me writing a program in Assembly, and asked “What are you doing???”  The next day he handed me a floppy disk labeled “Turbo Pascal 3.0”.  I took one look at the example programs, and I was hooked.  The code looked like stories, unlike the illegible lumps that were Basic programs and the terse syntax of Assembly.  The line “SetColor(Red);” jumped out at me.  My mind was blown.  It was so much more expressive than “SCREEN 0: COLOR 12“.  This set the tone for everything I’ve programmed since then.

My Lox port to Zig came out much better than I hoped for.  I expected it to run slightly slower than in C, but when I cut a release build, the benchmarks all were as good or better.  The book says “…our implementation is portable to any platform with a C compiler and is fast enough for real-world production use.  We have a single-pass bytecode compiler, a tight virtual machine interpreter for our internal instruction set, compact object representation, a stack for storing variables without heap allocation, and a precise garbage collector.”  Wow!  This is a great place to start at.  But, in Bob’s own words, Lox is still a “toy” language. So how do we turn it into a full-fledged language?  Well, writing a language in it isn’t a bad way to begin.  Lox in Lox.  Someone’s already done that.  Good idea.  Instead, I will work on creating a tree-walk interpreter for Pascal, and then write Lox in it.  So, JPascal and PLox.

Syntax

Changing the syntax from Lox to Pascal was the easy part.  Braces change to begin/end.  Operator = changes to := and == to just =, and != becomes <>.  Operator ! changes to not.  Add in then and change fun to procedure and function.  Add in a toLower() and a few equalsIgnoreCase() and Lox is no longer case-sensitive!  A few hours, and a handful of changes to the Scanner and Parser, and it is looking very much like Pascal.

Getting Started

Back to page one of Crafting Interpreters!  Only this time I’m writing Lox in a Pascal dialect of Lox.  Getting through the first chapter was undoubtedly the hardest part.  Lox doesn’t have Lists and Maps or even Arrays.  There are no Char or Integer types, and no subscript to index into the provided String.  And no case statement or enums.  On his website Bob provides code to his Array challenge, using a native function.  List, Map, and Stack is just more of the same.  Adding Char and Integers was straightforward.  The subscript operator was a little harder, but once I determined the precedence, it wasn’t too hard.  The case statement is nothing but a glorified if/else if/else series.  Similar to what the book does for the for statement, I added “syntactic sugar” to parse in the case statement and add if statements to the AST.  The same thing with enum types.  Following the type-safe enumeration pattern from “Effective Java”, I wrote TokenType in Lox using classes, and added the Pascal type keyword to the Parser as more “sweetener”.

Test-Driven Development

With Scanner.pas finished and running, it dawned on me what was missing.  Unit tests.  I don’t code without unit tests.  I just don’t.  Well, I had for several hundred lines of code.  Well, not really.  I mean, I have unit tests for JPascal, but not for Scanner.pas.  Programming at 3 levels simultaneously can be intense, like a scene from Inception.   

I don’t know what a unit test is supposed to look like in Pascal, so I modeled it after Rust and Zig, with a Pascal feel:

test 'Scan Tokens';
begin
    var Uut := Scanner('(){},.-+;*');
    Uut.ScanTokens();
    AssertEqual(TOKEN_LEFT_PAREN, Uut.Tokens[0].TypeOfToken);
end

I’ve already written a good suite of unit tests for RLox, all that remains is copying them over, and converting from Rust to Pascal.  Of course it needs to indicate a pass or fail, so a little borrowing from Rust and Zig, and a lot from Maven:

Static Typing

Ok, now for the elephant in the room.  One of Pascal’s claim-to-fame is that it is a strongly typed language, and Lox is dynamic.  I actually prefer dynamic languages, but being able to see the type can be incredibly useful.  I’m not going to lie, I had to think about this problem for a few days.  I could go with Python’s “type hints”, but that feels unsatisfying.  If I specify a type, I want that type to be enforced.  In the end, I decided to go with optional but enforced typing. 

Crafting Interpreters doesn’t have much to say on this other than it can be accomplished by adding a type checking pass.  Purple Dragon book to the rescue!  That uses static typing, so it has a good deal to say about reducing expression types.  In the Parser, the type definition is optional.   And, as the book suggests, I added a TypeChecker as a separate pass, based on the Resolver class.  If a variable or parameter has a type, the type checker enforces it, throwing a RuntimeError for any mismatches.

To make the collections work, I had to add “generics” using the keyword of.  As in “List of String”.  For typecasting, I also added the keyword as.

Quality of Life

With static types in place, methods can have “signatures” allowing method overloading.  Scanner’s AddToken methods are an example of this.  This is not necessary but is nicer than having to come up with two separate names, like in Rust.  Modifying the + operator to concatenate Strings with any other type of value was a huge improvement.  And a number of native functions were needed, such as Write, WriteLn, Ord, Str, and Copy.

Imports and Use Keyword

Whew.  That was alot of work for one chapter.  Moving on to the next chapter.   Wait, I’m not writing this in one massive file!  Ok, we need to implement the use keyword.  I would like to have individual class imports such as “use Token, TokenType from Token”, but for now, let’s keep it simple.  A simple C style file include will work, but we can do slightly better.   Automatically add the guards that every C header has to prevent circular includes.  

Onward!

From chapter 2 on, things moved much more quickly.  Parser, Interpreter, Resolver, and on.  There were more features that needed to be added, such as the break statement, the raise statement, and try/except.  13 chapters, 404 tests, and close to 14,000 lines of code later I have a good approximation of Pascal written, and a fully functional version of Lox, running in Pascal, running in Java 🙂

Looking Forward

This is a significant milestone in the development of PRISM.  So, what’s next?  Some of the code in JPascal is less than perfect, and I am sure there are numerous bugs remaining.  I’m not going to fix all of them.  I don’t have to.  This work has to be done all over again in Zig in the bye-code virtual machine.

I chose to go this route to make a concrete list of what’s needed for the foundation of Algol-24.  I have 24 years of experience in Java, and 14 in recursive descent parsing, so it made sense to start there.

The 5,500 lines of code in PLox will not need to be rewritten.  It can be used as it is to guide the work in Zig.  I had a lot of fun.  It felt really, really good to code in my “native language” after close to 30 years. 

The code for PLox and jars for JPascal can be found on GitHub here:

PLox: Lox Tree-walk Interpreter, converted to “Pascal” from JLox

Next up, I will be making a “Macro Assembler” front-end for my virtual machine to create a CLR (common language runtime) to allow custom languages to be easily plugged in to PRISM.

For now, though, I’m going to take a break, and play a little.  I’m going to write the 1982 game “CIA Adventure” in Pascal!