August 8, 2008
Students learning to program for the first time face significant challenges. It is all too easy to make syntax errors, and then understanding how the computation works is not easy, especially if it is recursive. I propose a visual functional program development tool which prevents most syntax errors, rather than reporting them (thus extending standard guidelines for graphical user interfaces to the programmer's interface); and makes computations easy to understand, even with recursion.
Not only do diagrams appeal to some students, due to their visual learning styles, but they also provide higher bandwidth feedback compared to a traditional textual debugger. It is easy to see at a glance the relevant flows of data leading to an unexpected value.
Such a language and tool could open the door for a much wider class of people (not just computer science majors) to write programs at a moderate level of sophistication, and thus to enjoy the ultimate power when it comes to controlling the computer.
Syntax is based on tree diagrams. All computations are expressed as expression trees. The figure shows a a definition for the factorial function:
The editor will have tools enabling the programmer to create symbols (functions, variables, and constants) by a mouse click, and connect the symbols. And, of course, we will want commands to erase, copy, and change the content of the boxes, as well as to edit the connecting lines. The resulting tree can be laid out by the software or manually by the user.
The programmer will be able to type in the values of a function's parameters and tell the system to evaluate the function call. The evaluation can show the result only, or, as in the figure below, the intermediate values of the computation. Literals evaluate to themselves, variables evaluate to their values, and function nodes evaluate to the result of the function call. The display is organized in three panels, with the function call and its result at the top, the expression tree and computed intermediate results in the middle, and the user-set arguments at the bottom. User input is shown in teal; values calculated by the computer, in red.
If the function being traced calls another
function, which is non-primitive, the user can expand
the call to the other function to see the details,
as shown here.
Note that in the f x display,
the second branch of the if expression
is unevaluated, because the first branch (the test)
is false. Also note, in the display for g y,
the bottom panel has the argument value in red, not teal;
the value is determined by the call in the f x
display, and is not user input.
Well, of course, if we can expand a nested function
call, we can do it recursively too!
And since recursion is equivalent to iteration,
now we can do anything.
In the example below, which computes the length of a list,
note that in the base case frame, the entire rightmost
branch of the if expression is unevaluated.
A moderate assortment of built-in functions will be provided, including at least:
Arithmetic: +, −, *, /, mod, add1, sub1.
Comparisons: =, <, >, ≤, ≥, ≠
Boolean unary predicates: zero (of numbers), null (of lists).
Logical operations: if, and, or, not.
List operations: ":" (or "cons"), head, tail.
Higher order functions: map, keep (filter in), rem (filter out), foldl, foldr
Possible additions: a case function and/or some sort of pattern matching:
case (or "match") expr value1 result1 value2 result2 ...
This would allow variables to be bound in valuei to be used in resulti. We could do something similar with "let".
let variable1 value1 ... expression