How I’ve discovered Lisp

ALU site has a page “Road to Lisp“, where people describe how they’ve discovered Lisp and came to use it. The story of how I’ve discovered Lisp is quite interesting.

Long time ago I had an 8-bit home computer named ZX-Spectrum. There were plenty of games available, and I was a teenager, so I was playing a lot. At that times there were games of genre almost unheard nowdays: text adventures. In those games player interacted with game environment not by pressing cursor keys or by moving mouse, but by entering textual commands from keyboard, like “open door with golden key” or “shoot alien with laser pistol”. Such games are not as impressive as “mainstream” games: they usually lack graphics and visual effects, environment is described using text. To win such game player should rely on his brains, not on reflexes. Modern genre “quest” is a descendant of early textual adventures. However, such games are not as repetive as mainstream games, they rely heavily on imagination and give to player much greater satisfaction. In “disconnected” age such games were discussed in communities organized around game magazines.

Last time I’ve played such games were 1995. It was a year of decline of ZX Spectrum in Russia, and remaining hardcore users played those games because all noteworthy “mainstream” games were already completed. I don’t remember how but about half of year ago I did found that such games are still been developed and played. Genre nowdays is called “Interactive Fiction“, and games are mostly distributed for free. I’ve downloaded game engine (Windows Frotz) and about 50 games, and started to check them.

One of those games was called “Lists and Lists“. It was made by prominent figure of IF world called Andrew Plotkin. This game is not a usual adventure, it’s a programming tutorial, with Scheme interpreter inside! Game contains small book about Scheme, a “teacher” who gives you tasks, and tests your solution by typing certain expressions and checking results of their evaluation. It means that you can create program with any structure you want, it just should return correct results! Interpreter doesn’t implement full Scheme, only small part, but is capable enough to be fun.

I should admit I was not clever enough to complete this game myself at that time. I did everything myself except last task. Game contains hints, and I used them to solve final problem. However, I was so impressed by Scheme language that I immediatelly started to look for more “serious” implementation. I’ve started from Wikipedia’s article for Scheme, discovered the existance of SICP and HtDP, and…

Lisp is often described as a language where programmer spends more time on thinking then on typing. Text adventures could also be described as games where player spends more time on thinking then on acting. So, it seems natural that text adventure is used to teach Lisp.

This article is very small. It doesn’t tell much about IF, and doesn’t tell much about Lisp. I already have something about Lisp on my site, and I’ll definetly write about IF soon.

Two tricky areas in Lisp

While learning Scheme, I’ve discovered two tricky places which seemed easy at beginning, but turned to be more complex. Now I seem to understand those things, and want to share my experience. All examples are provided in Scheme, but I’m almost sure that same things are also true for Common Lisp.

First area is variables.

When you type

(define a 10)

then you create a variable and initialize it with value 10. There are no way to create a variable without initial value. Now, suppose that you’ll type following:

(define b a)

b

10

Yes, that’s natural to expect that evaluating b will result in 10. Now, suppose you’ll do following:

(set! a 20)

a

20

b

Result of evaluation depends on what semantics does (define b a) have. I thought that it means that b and a point to same place in memory. In this case, changing value of a should also affect b, and evaluation of last expression should return 20. However, if you’ll try this example yourself, you’ll see that result will be 10. That means that (define b a) has different semantics.

Scheme is simple, and (define b a) should have exactly the same meaning as (define a 10) : create new variable and initialize it with some value. In both cases last element is a value, the only difference is that in first case evaluation of a results in value 10, in second case value 10 is provided immediately.

There are no way in Scheme to make several variables to point on same integer value. But two variables can point on same cons cell. So, that’s a language element which works as ”pointer” or “reference”.

Second area is “lexical scope”.

Initially I thought that it means that following code:

(define x 5)

(define (f) x)

(f)

5

(set! x 10)

(f)

Will result in 5. My understanding was that “at place where f was defined value of x was 5, so that value is captured by definition and is not affected by later changes of x”. I thought that was a meaning of “lexical scope”.

As you expect, I was wrong. Above example will print 10. It turns out that meaning of “lexical scope” is totally different. I thought that “scope” means “value scope”, but it should be “name scope”. Look at example:

(define x 5)

(define (f) x)

(f)

5

(let ((x 20)) (list (f) x))

(5 20)

When f is evaluated second time, name global variable x is shadowed by local variable x, so name x is evaluated to 20. But at time of definition of f name x was refered to global variable, and each time f is evaluated it uses global variable.

That’s all for today. I’m very pleased with Scheme, it’s semantics are simple and consistent. Most of my confusion came from my previous experience with other programming languages, so I’m often expect somehting complex and context-dependent.

Update: After I’ve posted that there was a discussion in comp.lang.scheme about reference/value semantics.

Another update: Discussion of these subjects continues in my future post

Basic and recursion

I’m still reading book about data structures in Basic. Of course, this book didn’t missed an oportunity to show one of usage for stack: recursion. As everybody can imagine, implementation of recursion in plain old Basic is horrible: hard to read, hard to understand. And finally, they demonstrate how to replace recursion with iteration. My main feeling is “never do recursion in Basic”. But reading of this chapter gave me lots of insights.

First, about recursion itself. Lots of books explain it, every Lisp book for beginners have explanation of recursion. They assume that recursion is something which is not tought in school. Yes, that’s right, in school they always prefer iterative approach. I was tough that multiplication is addition of equal values: a*n = a + a + a + … + a (n times). Same thing about factorial. Recursion here is a nice way to avoid those dots and make precise definition of repetitive process by defining such process through itself. But in those cases iteration and recursion give same results, their difference is that recursion is more beautiful but harder to understand. In programming it’s often better to use approach which is simpler to understand. Also, in Basic recursion is not as beautiful as in math, so for Basic iteration for such tasks is a better solution.

There are other cases where recursion is natural: solving “Hanoi towers”, doing binary search in lists and trees. This “naturality” comes from fact that process itself is really recursive or data structures used are recursive. Unfortunatelly, in Basic such data structures are represented in some ugly way, so their recursive nature is not helping to solve task beautifully.

Recursion is a term which belongs to semantics of data structures and algorithms. If you really want to design data structures and algorithms in this way, you should better use programming language which supports semantics of “recursion”. For data structures this means pointers/references, for algorithms it means invokations using stack.

Above is just a concrete case of principle “use tool appopriate for your task”. Nobody tries to do object-oriented programming in C. Nobody should do recursion in Basic.

Your first and second OCaml programs for Win32

Since “C Programming language” by Kernigan and Ritchie most books about C started with “first program in C” to print “Hello, world!” on console. Windows is so much different from Unix so it even has it’s own “main function” named “WinMain” (instead of “main” for Unix). Because of that huge difference books about programming with Win32API usually start with their own “first program in C for Windows”, simple 5-line program for showing same message using MessageBox function. You can find such examples in book by Petzold and tutorials like this. Let’s make exactly the same program in OCaml.

Program will look like:

open Win32

let _ =
  ignore (message_box null_hwnd “Content of MsgBox” “Caption of MsgBox” [MB_OK]);
  exit 0;

Yes, that’s it, simple. There are no WinMain here, because it’s OCaml, not C. OCaml specifies it’s own entry point to program. WinMain has several arguments; they are available as global variables, however they are stored not by implementation of WinMain, but by invoking some Win32 API functions.

After this simple program books go in different directions. Some books go to windows, message reading/dispatching cycle and window procedures. I prefer to go to dialogs, because first program was also about dialogs. Dialogs are convenient because they could be defined in resources. My second OCaml program for Win32 consists of two files. Here is a OCaml file:

open Win32

let dlg_processors = [
    on_wm_initdialog (fun ~wnd ~msg ~focus ->
        message_return true)
    ;
    on_wm_command (fun ~wnd ~msg ~notify_code ~id ~ctrl ->
        if id == control_id_of_standard IDOK && notify_code == bn_clicked then
           end_dialog ~dlg:wnd ~result:0;
   message_handled
 )
]

let _ =
    try
        ignore (
            dialog_box
                ~inst:the_instance
                ~name:(Rn_string “TestDialog”)
                ~parent:null_hwnd
                ~proc:(standard_dialog_proc ~processors:dlg_processors));

        exit 0

    with
        e ->
            let s = Printexc.to_string e in
            ignore (message_box ~wnd:null_hwnd ~text:s ~caption:”Uncaught exception” ~options:[MB_OK]);
            exit 1

And here is test.rc file:

#include <windows.h>
ABOUTDLG DIALOG 20, 20, 199, 99
STYLE DS_SETFONT |DS_MODALFRAME |WS_POPUP |WS_VISIBLE |WS_SYSMENU |WS_CAPTION
CAPTION “Example caption”
FONT 8, “MS Shell Dlg”
BEGIN
  CONTROL “&OK”,1,”BUTTON”,BS_DEFPUSHBUTTON |WS_CHILD |WS_TABSTOP |WS_VISIBLE ,72,74,40,14
  CONTROL “Hello everybody”,104,”STATIC”,SS_LEFT |WS_CHILD |WS_VISIBLE ,45,14,128,8
  CONTROL “example custom dialog”,105,”STATIC”,SS_LEFT |WS_CHILD |WS_VISIBLE ,45,35,99,8
END

First program used pre-defined generic purpose dialog, second procedure used custom dialog defined in resource file. I hope these two programs will give a good start for everybody who are interested in using OCaml for Win32 programming. Next steps will include making custom resizable Windows with menues, and much more. Unfortunatelly there are not so many information about writing GUI application in OCaml. But maybe with time there will be books even better then one by Petzold!