Probably Programming

After my last post on the A++ programming language, there was quite a bit of discussion on reddit about both a mistake I made about the classification of the language (which I corrected in my previous post), and questions about how A++ is different from Scheme.

Because of the relative simplicity of A++ compared to Scheme, rather than talk about how they compare and contrast (that would mostly be like, “Scheme does this, this, this, this, this, and this, whereas A++ does this”), I’m simply going to talk about the main aspects of A++, namely, its simplicity and the fact that it uses lazy evaluation.

The core of A++ is simplicity (and lambda-calculus)

The idea behind A++ is that it is lambda-calculus, with a simplified uniform syntax (using parens all the time, rather than only in certain cases), and with explicit name-binding added to it.

What this means is that everything is a function, with the exception of named constants, which enable a simple form of message-passing to be implemented. The only thing you can do with named constants is check if they are equal, so they add a very small amount of complexity to the language.

There are no data structures (that aren’t made up of nested lambdas), there are no primitive values, and no built-in operators, aside from those which allow the definition, binding, and applying of functions.

A tiny exception is made in instances when printing things out, but the only thing you can do a with a primitive is increment it, decrement it, or print it out, so it can’t be used in a program. Named constants also don’t count, since they essentially don’t have values. Ignoring these two trivial exceptions, there’s one main rule that A++ follows:

In A++, there are (pretty much) only functions.

The only (non-output-related) built-in operations are define, lambda, apply (which is done when the first thing inside some parenstheses isn’t “define”, “lambda”, or “equal”), and equal (which is used for comparing the aforementioned named constants).

To make A++ the powerful enough to write new language constructs within the language itself, it uses lazy evaluation.

Lazy evaluation

Parameter evaluation is done lazily, meaning an operation passed into a function is only applied (called) when you explicitly apply it (by wrapping it in a pair of parentheses).

This is needed in A++, because there are no built-in control structures. While loops aren’t strictly needed because A++ allows recursion, you do need some sort of conditional statement.

In A++, true, false, and if are defined as follows:

(define true   (lambda (x y) 
                 x))
 
(define false  (lambda (x y) 
                 y))
 
(define if (lambda (b t f) (b t f)))

Any predicate or boolean operation evaluates to either true or false, so when passed to if, it makes sense that only one of the two following parameters is evaluated.

If A++ used eager evaluation, both the t and f parameters would be evaluated before being passed into the if function, which, since A++ allows side-effects, could result in unwanted output. Even if A++ was purely functional, allowing no side-effects, it would waste time to evaluate both branches of the if function.

For example, if you were to run the following code:

(if true (ndisp! four) (ndisp! five))

you would get the expected output from A++ of

-->4

but if A++ eagerly-evaluated the parameters to if, you would end up with

-->4
-->5

instead (or possibly in the opposite order, depending on which evaluation order was used by the language).

Lisp offers deferred evaluation via the quote operator, and allows the construction of control structures with macros. Since the goal of A++ is simplicity, it makes sense that it would pick the lazy evaluation scheme, which allows it to fulfill both of those roles without any extra feature being added to the language.

I didn’t intend for it to take me a week to write this post, but I had some technical difficulties in getting started, which prevented me from even starting to learn the language until I solved them.

I expected to run into some problems getting things set up as I worked on this project, but I assumed most of those problems would be along the lines of getting the compiler and/or interpreter for a particular language to compile or run on my machine.

What I didn’t expect was to have so many issues just getting my text to be in the encoding that the language expects, but that is exactly what I ran into with A+.

Introduction to A+

A+ is a high-level language with a large number of primitive functions for manipulating arrays of data. It was created in 1988 at Morgan Stanley by Arthur Whitney, after he decided that none of the existing APL implementations would be suitable for their purposes.

A+ is a dialect of APL, and offers some extensions, such as a graphical user interface and inter-process communication, as well a module for storing and loading objects (functions, variables, and dependencies) and even a built-in database system.

Another feature A+ adds is the ability to set up dependencies between variables, so when a depended-upon variable is changed, the dependent variable changes as well. This allows for spreadsheet-like or reactive programming, with barely any effort. Actually, combined with the graphical display capabilities, you could actually pretty easily implement a spreadsheet in A+ if you felt like it.

Any dyadic (two-argument) function can be called using infix notation, which takes a little getting used to, especially with the right-to-left no order-of-operations precedence rules.

The language uses a healthy subset of the crazy hieroglyphs included in APL, and requires a special font for properly displaying the special characters. It’s also possible to use one of two ASCII-based modes when programming in A+, but where’s the fun in that?

After playing around with the language for a while, I can see why people enjoy APL and its derivatives so much. It’s one of those language where once you wrap your brain around it, it opens up new ways of solving problems that you’d never even considered before.

My First A+ program

I decided on a (sort-of) graphical implementation of Conway’s Life, to demonstrate both the graphical system and the array-handling capabilities of A+.

This program is special because it’s not only my first A+ program, it’s my first program in an APL-like language of any sort.

You won’t be able to copy and paste this program directly and run it from A+, because I’ve converted the symbols to unicode in hopes of having them display properly in more browsers. If they don’t display properly, you can take a look at a screen-shot of the source code.

If you would like to run it, you can download the A+ life source.

$load s          ⍝ Load the graphical system
 
xy take2 m: xy[0] ↑ ⍉ xy[1] ↑ ⍉ m  ⍝ helper function to resize an array in 2d
n xr m: ⍉ n ⌽ ⍉m                   ⍝ helper function to rotate on the x axis
xy rot2 m: xy[0] ⌽ ⍉ xy[1] ⌽ ⍉m    ⍝ helper function to rotate in 2d
 
nextgen gen: {   ⍝ Calculate the next generation
        sums ← +/+/> (1;0;¯1) xr¨ 3⍴<>(1;0;¯1) ⌽¨ 3⍴<gen ;
        (gen ∧ 4=sums) ∨ (3=sums)
        }
 
cells ← ¯6 ¯6 rot2 15 15 take2 3 3⍴0 1 0 0 0 1 1 1 1 ⍝ start with a glider centered
`cells is `array
 
step c: .cells ← nextgen cells
step_button ← (step;cells)
`step_button has (`class; `button;
                  `title; "Step")
 
w ← (`cells;`step_button)     ⍝ Initialize our window
`w is `layout
`w has (`title; "A+ Life")
show `w

The most important function of the program is the “nextgen” function.

On the first line, reading from right to left, it does the following:

1. Make an matrix containing 3 copies of the gen matrix
2. Rotate each of those three copies verically by 1, 0, and -1 rows, respectively
3. Make three copies of each of the three copies from the first step.
4. Rotate the copies of copies horizontally by 1, 0, and -1 columns.
5. Sum the rows and columns of matrices together into a single matrix.

On the second line, again, reading from the right to left:

1. Get an matrix with any cell equal to 3 changed to 1, and any others changed to 0.
2. Logically OR that matrix together with the array consisting of ones in the place of any 4s in the sums matrix, ANDed with the original gen matrix.

A more thorough explanation of the algorithm can be found at the APL wiki. You’ll notice that my version is quite different. That’s mostly because of difference in how the various build-in functions work in A+ and other APL implementations. That’s the same reason I had to implement the take2 and rot2 functions, since the A+ rotate (circle with a vertical line) and take (arrow pointing up) functions only allow you to rotate or take in a single dimension.

continue reading to learn more about A+

(more…)

I mentioned yesterday that I would be starting a series, talking about “some number” of programming languages.

Well, that number, as it turns out, it at least 500.

What?

I’m very interested in programming languages, but I’ve probably only ever written code in about 25 different languages, so I’m sure there’s some great language features and paradigms that I’ve never really tried. With this series, I aim to remedy this problem.

The goal of this project is to write a blog post about, and code in, every real programming language that I can get my hands on and a few of them which some might not call “real”, with an end goal of writing about and code in at least 500 different languages.

Based on languages I’ve found over the years, and the Wikipedia list of programming languages, there should be at least 500 languages I can get my hands on. There are at least 700 esoteric programming languages, but I will only be covering a few of those, like Brainfuck, LOLCODE, and Unlambda, since I want the posts of this project to be at least somewhat useful.

Why?

Aside from my own Pokémon-style reasons for wanting to do this project (gotta catch ‘em all!), I want to share information about programming languages with others.

The idea is for each post to be a sort of introduction and crib-sheet for the language it’s about, ideally enough information for someone to gauge whether or not they’d like to try this particular language out.

For older languages, it will be more of a history, since generally most people wouldn’t be interested in actually writing code in an old, dead language.

Also, I would love to see some conversation emerging around various languages, be it discussions of good and bad things about a particular language, or elaboration on parts that I may have overlooked.

The Plan

For each language, I plan on doing the following:

• Write a summary of the language, including who created it, what it’s main uses might be, what paradigms it supports or encourages, and any other tidbits about the language itself.
• Cover the anatomy of a basic program in the language.
• Write a somewhat non-trivial program in the language. This I will only do for languages which I can get a running compiler or interpreter for. I’m not going to spend any money on this, so I will most likely not write any code in strictly-commercial languages or ones which would require me to buy an IBM mainframe to run.
• Cover where and how to get and set up the language. If a language is particularly hard to find and/or get compiling, I’ll include information on how I got it and got it set up.
• List plenty of links to language resources (for languages which have plenty of resources). I am by no means going to give a complete, exhaustive look at each language, so for those who are interested I will give you links to wherever it is that I think you can get more in-depth information.
• Anything else that seem appropriate at the time.

If anyone can think of anything else they would like me to add to this list, please let me know. I really want this to be a project for others, not just me, so I’ll be glad to get any feedback anyone has.

The List

For those who are interested in which languages I’m planning on writing about, the tenative list is below.

If you know of a programming language that is not on the list, please let me know and I’ll add it. There are currently 518 languages on the list, but I know that I won’t be able to get my hands on some of them, so I’d like to be sure that I have at least 500 that I can get my hands on.

As I have time to do so, I will update the list to include links to the most relevant page about each language, and as I publish each post I will add a link to the post in the list as well.

I will be going through the list in lexicographical order, so first up: A+

And now, without further ado, the list:

(more…)

Prefix notation?

Have you ever dreamed of a language which uses strictly prefix (a.k.a. polish, Łukasiewicz) notation?

No? Well, I can’t say I’m surprised. Lisp is often called a prefix notation language, but I’ll let you in on a secret, it’s not purely prefix notation. It uses another notation you’ve probably never heard of: outfix notation.

Outfix notation?

I’d say I made outfix notation up, but I found a reference to it on abstractmath.org, so I at least have something to back this claim up with. Basically, the parentheses are a function which says, “put these items into a list.”

Of course, Lisp uses lists for everything, so you can hardly call it a prefix notation language any more.

Real prefix notation

Now, how about making a real prefix notation language? A real prefix notation language needs no parentheses because it knows how many arguments each function takes, so it can simply pull in the next two expressions following the function name.

A real prefix notation language is a piece of cake to implement, as long as every function has a fixed arity and that arity is known at compile time. Of course, then how do we represent things such as lists with varying amounts of items. How do we pass a variable number of arguments to a function?

The same way Lisp does, we use a list.

(more…)

It’s been far too long since I’ve posted, so I’m writing a short post about a quick one-line I just used to solve a problem.

The problem was a rogue newline appearing at the beginning of some generated XML files, which is against the rules for XML.

This problem, and a similar one involving data being sent before headers can be sent, often happens in PHP when an extra newline is included after the closing “?>”. One way to fix it is to just leave off the closing bit, since PHP is smart enough to realize the file has ended in PHP mode.

Anyway, we had to track down which file had this problem in it, and the solution ended up being this:

for i in `find . -name '*.php'`; do echo $i:`tail $i -n 1` | grep -v '\?>'; done

That finds each php file and checks its last line for “?>”, printing it out if it’s not there.

Of course, there will be some false positives for PHP files which have HTML after their PHP code or don’t have the closing “?>”, but it’s good enough to track down those potentially offending files.

The Problem

There are many pieces of software in the world, but very few of them are anywhere near what one would consider “perfect.”

I don’t blame anyone in particular for this. Writing perfect software is quite difficult if the software is to accomplish any sort of non-trivial task. Some come close to the lofty goal of perfection.

Even still, there are certain areas where the mark has always been missed, if only enough to be slightly annoying. I’m being purposely vague here because there are lots of different things wrong with lots of different pieces of software. I’ll get more specific later.

Probably the biggest contributer to this problem is the fact that nobody really knows what perfect software is. I usually know what annoys me about a particular piece of software, but I’m not always sure what would be a better solution.

My solution

There are some types of software which have gotten closer than others to perfection. Web browsers, for example. I’ll readily admit that there are things which annoy me about Firefox, but on the whole it’s a good piece of software, and improving all the time. I have some ideas of my own about the was a browser should do certain things, and I’m not about to go hacking about in the monstrous labyrinth that is the Mozilla source code, so I’ve [started my own browser project][mybrowser]. It will probably never catch up with the other, “real” browsers, but it will keep me entertained and provide me a way to prototype various ideas I have for user interfaces.

There are also some good programming languages out there. Languages like Python, Erlang, and many others make programming “fun again.” Still, for every language there’s something that’s missing, or something that might be cool to be able to do, some area which has been left mostly unexplored. Once again, I’ve started [some][booter] [prototyping][stacklang] so I can play around with some new ideas and push some boundaries which I think should be pushed (or at least ones which look as though they may be fun to push).

So what’s the way to write perfect software?

(more…)

The “Big Block” Method

Joshua Clanton posted a guest post on Jarkko Laine’s blog yesterday, talking about how to get into a state of “flow” to increase your productivity.

I commented that I seem to be able to get into a state of flow better when I have a large chunk of time allocated to work on a task.

To me there’s nothing worse than coming back to something I had to stop in the middle of. It takes far too much time to get back up to speed on what I was doing, and often I’ll have forgotten about something essential, which results in bugs.

Joshua pointed out in another blog post that it helps flow to have not only big blocks of time but also to have your tasks divided into big blocks as well.

I definitely agree with Joshua on the “big block method,” though this is the first time I’ve put much conscious thought into it. Looking back, it seems that I’ve done better work when I’ve used this method, and I’ve always hated working in short bursts, since it feels like I’m wasting too much time in “context switching.”

How big of a block?

There’s one question I’m not really sure of the answer to yet: How big should a big block be?

The first answer that comes to mind is “Just big enough, but no bigger” (a modified Einstein quote)

So far my technique has been to just pick what seems to be a single functional unit, or perhaps a piece of functionality that all belongs together.

I suppose that different people will have different definitions of what a big block task is, but to me it works out that it’s something that is a complete unit. A complete unit can be a full module, or one step in the implementation of a full module. The key is, though, that there is a clear stopping point and something isn’t left unfinished.

For example, working on my browser, I have index cards (old business cards, actually) which each have an individual task on them. I sort these cards by the order I plan to do them in. These cards contain something like “Implement DOM 2 HTML” or “Rendering Engine support for inline elements.”

The former is a complete module which could (and was) finished in one big block section of time.

The latter won’t result in the final version of the layout engine, but it will get it to a point where it is functioning, and then the next step would be to support block elements. Absolutely and relatively positioned elements would be yet another separate task.

I’ve spent a good chunk of my vacation working on some of what will become the internals of a web browser written in Python.

Some of the goals of the browser include:

• Full conformance to all DOM 2 Modules (and equivalent DOM 3 modules when they become recommendations). This goal is already about 60% done.
• Full conformance to CSS2.1, and eventually CSS3
• Javascript support.
• SVG and Canvas support
• Little or no explicit support for deprecated standards and technologies (yes, this is a feature).

The most important features, and thus the ones getting the most attention, will the standards compliance and JavaScript support. Standards compliance is important because I want this browser to be an example of a browser which people should take seriously. I won’t, however, do extra work because somebody out there decided to not follow the standard when designing their webpage. JavaScript support is important for the same reason. Nobody is going to take a browser seriously (or be able to use it for any modern website) if it doesn’t support JavaScript.

So far I’ve got a complete (but also completely untested) implementation of the DOM 2 HTML, which took me a good amount of time longer than expected.

I started with a good base: pxdom, a complete implementation of DOM 3 Core and LS (Load and Save), and implemented my additions on top of that. It’s still a separate module, though, but there are a few places where I rely on some of the implementation specific details of pxdom. I have plans to remove the dependency at some point so that I can swap in other DOM core implementations.

On top of that I built my DOM HTML implementation, and laid a little bit of groundwork for DOM StyleSheets and CSS. I’ll be using cssutils, which is a mostly complete python DOM CSS implementation. The cssutils version 0.9.4b1 was just released with mention of some sort of selector support being added in version 0.9.5, which will hopefully make it so I don’t have to do a full CSS cascade implementation myself.

I’m taking a break from working on DOM implementations now and moving back to something which will actually allow me to see results: the rendering engine. I’m starting with just a stub implementation of the ViewCSS interface which allows me to use the getComputedStyle function to get the default style for any given element. With that, I should be able to render any HTML document as if it had no style applied to it. Later on I will hopefully be able to use the upcoming selector support in cssutils to make getComputedStyle work as expected.

This browser is something that I’ve been wanting to do for a very long time. I even sort of started to implement the rendering engine a long time ago using pycairo as the backend. I’m going to stick with that because it seems to be an ideal rendering backend for webpages (which would explain why it will be the only thing used for rendering as of Firefox 3.0 ), and for eventual SVG and Canvas support. Once I get to the part where I’m actually working on the user interface portion, I’m planning on writing a Python binding for glitz, which will provide the browser with OpenGL accelerated rendering by default.

My coworker Scott Martin recently posted a list of things to do from the beginning of a project..

I had planned to post something along those same lines myself, but I guess he beat me to it.

I’ll throw in my two cents with a much shorter and vaguer list, with my comments and a few extra items as well. This will make a lot more sense if you read the list at the above link first.

• Internationalization + Smarty

  These two items go together. Basically, there shouldn’t be any text which makes its way to the users which comes from anything but a template file. Seriously, don’t put text in your code.

• Code standards

  Here’s a secret: what your standards are really doesn’t matter. It’s the fact that you have standards that matters. It’s really annoying to read code with two different layouts. Pick one and stick with it.

• Code generation

  I disagree with Scott about code generation being bad. The one thing that needs to be done for it to be okay, however, is for it to be generated, and updated, automatically. The first code you should write isn’t the code to generate the code, but the code to call the code to generate the code when the source of the data used to generate the code is changed.

  For example, if you are reading in one file to generate another, then before you read in the file, run some code which checks the last modified time of the generated file and compares that with the last modified time of the source file, if the source file is newer, regenerate.

  If you feel so inclined, also check the timestamp on the code which generates the file, and if it is newer than the generated file, regenerate also. This will get rid of the instance where you change the generator code but don’t change the input file.

  Alternatively, if you have some sort of interface or tool which generates the input file, have that tool run the script to update the generated file.

• URL rewriting

  As we all know, Cool URIs don’t change. So make some sensible decisions at the start of your site design, and stick with the URLs from there on out. All you need is a single script to redirect all URLs to (except images and CSS and things), which then delegates the work out to some actual PHP files. This is also helpful in that it makes it so you don’t have to have all of your PHP files inside of your document root, just the one that does the routing, which brings me to my first new rule…

• Keep non-documents out of your document root.

  The fewer things you actually have in your document root, the fewer unexpected security holes there will be. If a file is not going to be directly accessed from a web browser, don’t put it where a web browser can get to it. All of your configuration files and almost all of your code should be kept out of your document root.

  A structure like the following works well:

  • application root
    • htdocs – static HTML files, images, CSS files, a single code file to load in other files based on the requested URL
    • src – all of your actual code. Set your inclide_path to here and keep everything neatly organized into subdirectories
    • templates – Smarty, or whatever templates you are using.
    • cache – whatever sort of disk cache you need. This includes Smarty cache, RSS feed cache, etc…

• Don’t Repeat Yourself (DRY)

  This is basic stuff right here, but it can never be said enough: Don’t write code that does the same thing as code you’ve already written. Or if you have to do so, then combine the two pieces of code together. It is a huge pain when you have to figure out why something is working the old way when you already changed the code that does that thing to do it a new way.

  If you are copying and pasting code, then something is probably wrong.

• Don’t Repeat Other People/Don’t Reinvent the Wheel

  This one is a bit different. What I mean by this is don’t write any code that you don’t have to. If somebody else has a library that already does what you want, use that, unless there is a very, very compelling reason for you not to. If a library has licensing issues, or is really slow, or doesn’t fit into your platform somehow, it might makes sense to write it yourself, but first check to see if there’s already something else which meets your needs.

  Spending an hour searching something is going to take less time than writing it yourself.

What guidelines do you follow from the start with every project that you do?

Edit: Apparently the way to prove a new esoteric language is turing-complete is to implement a [BF][] interpreter. This technique has been used to show that [LOLCODE is turing complete][lolcode-bf], so I suppose I could target that as the first non-trivial program to write as soon as I get a working BooTer interpreter Or, I suppose I could implement a LOLCODE interpreter in BooTer in which I could run a BF interpreter…

Thinking about BooTer, I decide that I wasn’t making it esoteric enough..so I’ve slimmed down my specification for simpler implementation, and much more difficulty doing anything useful with it

The only thing allowed is simple expressions and boolean ternary expressions. No comma-separated lists of expressions, no assigning expressions to variables, no symbols, no quoting of expressions.

Maybe in the future I’ll re-expand it out into a more “real” language, but for now I just want to do something that I can do simply and easily without accidentally building an entire broken LISP.

So, with all that stuff gone..what’s left? What’s different now?

• The boolean-ternary operator is in an order which won’t drive me insane to write programs in. The boolean expression comes first. If true, the expressions evaluates to the second expression, if not, it evaluates to the third. This now works basically just like the ternary operator in most other languages…but with a different syntax and the possibility of using the re-eval operator.

• A BooTer program is now a single boolean-ternary (booter) expression, with optional nested booter expressions.

• The center portion of a booter expression (the “boo” part), must evaluate to either true or false. False is represented by the integer 0, or by null. Anything else is true.

• null is represented by the lack of a value. This is useful for instances where the left or right portion of an expression will never be used, for example: ( ...do something here... : x = 5 : )

• There are only numbers and strings as primitive types.

• Variable names can start with upper or lowercase letters.

• There’s only a single array type. Array items are assigned and accessed using the standard [] subscript operator. Creation of an array is implicit with the assignment of the first item to that array. If you use the subscript operator to make an assignment to a previously existing variable, the old variable is overwritten with the new array. The previous array literal syntax still applies. Only primitive values and variable names can be used in the array literal syntax.

• Math and boolean order of operations are the same as in most programming languages these days.

• The re-eval operator, ^, still works as previously stated.

• Comments start with a semicolon and continue to the end of a line.

The previous example programs are both a bit more complex than they were previously (but hey, the parser and interpreter will be much easier to implement!):

Infinite NOOP loop: ( ^ : : )

100 bottles of beer:

(n = 101 :
  (
    (n = n-1 : 
      print [n, "bottles of beer on the wall!\n"] : 
    ) : 
    ^ : 
  ) : 
)

In the beer example, assume that print prints the items passed into its array to the stdout and then evaluates to the same string it printed out.

• While n is greater than 0, the sub-expression will evaluate to the string returned by print, which by the rules above equates to true, thus causing the re-eval operator to be evaluated, looping back to the expression (n = n-1).

• When n finally gets assigned 0, the expression will evaluate to the third, empty, sub-expression, which equates to false, which means the center of the outer expression now evaluates to false as well, and thus the third expression of the outer expression is evaluated. It evaluates to null, which is the return of the program.

Here’s a BooTer “for loop” with more of an explanation of what’s going on:

(i = -1 :              ; initialize loop variable
  (
    (100 > i = i + 1 : ; increment loop variable, check it against condition
      ...              ; do things, must evaluate to true
    :
      ...              ; this one must evaluate to false (leaving it empty works)
    ) 
  :
    ^                  ; re-evaluate this expression, causing the loop
  :
    ...                ; whatever can go here, this will be evaluated after the loop is done
  )
: )                    ; done, this last sub-expression will never be run

Even with this new “simplified” syntax, it’s enough to make your head hurt. Now I just need to actually write a reference implementation with some standard library calls, then try to write something non-trivial with it. Who wants to try their hand at writing a BooTer web server?