Thursday, February 28, 2008

Arc internals part 2: Macros

I've written a document on the internals of Arc's macro implementation. It continues where Arc internals part 1 left off.

Tuesday, February 26, 2008

Arc template documentation

I've created some documentation on Arc's template data structure.

Monday, February 25, 2008

Git and the Anarki Arc repository: a brief guide

The official releases of Arc are at arclanguage.org. However, a group of enthusiasts has their own repository of Arc, called Anarki. This repository has versions of the Arc files with bug fixes, documentation, and extended functionality. The repository also contains additional features, documentation, applications, and Emacs tools.

The Anarki repository is stored in a source control system called git. The repository is open for access and updates by Arc users. Accessing the repository is straightforward, and will be described below. Submitting changes to the repository is not much harder, but is beyond the scope of this document; one source of information is on arclanguage.org.

The repository is promptly updated when a new version of Arc is released. Most of the changes in the repository haven't been migrated back to the official Arc releases, so there is considerable divergence between the official Arc version and the Anarki version.

Installing git on Linux

On Linux, git is in the "git-core" package. You can install this with "sudo apt-get git-core" on Ubuntu, or "sudo yum install git-core" on Red Hat.

Installing git on Windows

On Windows, one option is Git on MSys, which can be downloaded from the msysgit site, under "Featured Downloads".

Using git to fetch Anarki

Once git is installed, fetching the repository is surprisingly easy. Run "git clone git://github.com/nex3/arc.git", which will create a directory "arc-wiki" containing a copy of the repository. To get updates from the repository, run "git pull".

Browsing Anarki without git

You can browse the repository directly by going to http://github.com/nex3/arc/tree/master. To view a file, click on the filename.

Once you've downloaded Anarki, you can see the cutting edge of Arc modifications. One of the most interesting features of the Anarki version is docstrings: "(help map)" will display documentation on the map function, for instance.

The stable Anarki branch

A "stable" Anarki branch has also been created. This repository is close to the official Arc release, but with bug fixes and minimal new features. The stable repository lacks the experimental features and rapid changes of the regular repository.

To use the stable repository, check out Anarki as described above. Then run "git branch stable origin/stable" and "git checkout stable". All the experimental files and directories will disappear, and you will be left with the stable branch. For more information, see the arclanguage forum.

The Arc-to-C compiler

An Arc to C compiler is being developed in a separate repository: git://github.com/sacado/arc2c.git, which can be accessed on the web at http://github.com/sacado/arc2c/tree/master.

Sunday, February 24, 2008

What's new in arc2

I took a look at the new version of arc that has been released. The following are my unofficial notes on the differences between arc1 and arc2.

News.YC release

The key difference is the release of the News.YC source in news.arc. This 1769-line file apparently provides the full implementation of news.ycombinator.com. One interesting thing is that stories are ranked according to (score-1) / (age-in-hours ^ gravity), where gravity is 1.4 by default.

There are also some gifs to support the site. The following is a list of the new files in arc2:

  • news.arc: the source for news.ycombinator.com.
  • grayarrow.gif: gray uparrow
  • graydown.gif: gray downarrow
  • s.gif: 1x1 transparent spacer
  • y18.gif: 1x1 spacer (same as s.gif)
Other files have minor changes:

ac.scm

  • arc-list? fix for '()
  • write, disp cleanup

app.arc

  • Renamed when-usermatch to when-umatch, when-usermatchr to when-umatch/r, matchform to uform.
  • Removed pw from good-login record.

arc.arc

  • (firstn nil xs) now returns xs
  • (nthcdr nil xs) now returns xs
  • trav renamed to treewise
  • New function union on sequences.
  • New function addtem to create a template.
  • New functions hours-since and days-since.
  • ensure-dir fix.
  • Function only is now entirely different. Wraps a function to only call it if given args.
  • Function plural moved to strings.arc. Now if w/bars were moved too...
  • New function trav: takes an object and functions. Applies the functions to the object.
  • New function defhook and hook to register and execute functions?

html.arc

  • Added orange as a color.
  • para now takes arguments.
  • Removed image-url and local-images*
  • spacetable renamed to sptab.
  • Added single-input and cdata.

libs.arc

  • Added news.arc.

srv.arc

  • Remove "frug" default account.
  • Excludes .arc as a static filetype, to hide source.

strings.arc

  • plural function moved here from arc.arc.

Tuesday, February 12, 2008

The foundation of Arc: Documentation

The Arc language is implemented by a "foundation" of functionality implemented in Scheme. I have created detailed documentation of the foundation functionality.

Saturday, February 9, 2008

Arc Internals, Part 1

This article is the first part of a description of the implementation of the Arc language, based on my examination of the code.

The core of Arc is implemented in Scheme (in ac.scm), and runs in the mzscheme interpreter. The remainder of the Arc language is implemented in Arc itself (arc.arc), and is loaded into the running Arc implementation. In addition, the Arc distribution includes libraries for a web server, string handling, and a few others. Arc runs a standard Read-Evaluate-Print Loop (REPL), allowing commands to be entered and executed interactively.

In a bit more detail, when an Arc expression is input to the REPL, the Scheme reader reads and parses it. The Arc expression is converted to an analogous Scheme expression, and eval is applied to execute the Scheme code. The result is converted from the internal Scheme representation to a displayable form, and displayed as the output from the REPL.

Interestingly, Arc's [ _ ] syntax is implemented entirely independently from the rest of Arc; the code in brackets.scm extends the reader so the bracket syntax is converted to standard syntax as the input is parsed. The bracket support could easily be run on Scheme without Arc, or Arc could be run without bracket support.

Entering :a into the Arc REPL drops execution into Scheme, allowing easy examination of the internals:

> (= x 3)
3
arc> (= y '(1 (2 3) 4))
(1 (2 3) 4)
arc> (def z () (pr "hello"))
#<procedure: z>
arc> :a
> _x
3
> _y
(1 (2 3 . nil) 4 . nil)
> _z
#<procedure: z>
Arc's data and procedures are stored in the Scheme environment, with a few modifications. Arc symbols have an underscore prepended internally to avoid collisions with Scheme names. In the Arc language, the empty list is nil, while the Scheme empty list is (). Thus, Arc lists are stored in Scheme terminated by the (arbitrary) symbol 'nil, as can be seen by the dotted notation above. Arc macros are stored as a vector of the symbol 'tagged, the symbol 'mac, and the procedure.

The REPL

Arc runs from a Read-Evaluate-Print Loop (REPL), which is started by executing the simple procedure tl:
(define (tl)
  (display "Use (quit) to quit, (tl) to return here after an interrupt.\n")
  (tl2))
Note that the REPL runs in Scheme, not in Arc. tl is a wrapper around tl2, which is the real REPL implementation:
(define (tl2)
  (display "arc> ")
  (on-err (lambda (c) 
            (set! last-condition* c)
            (display "Error: ")
            (write (exn-message c))
            (newline)
            (tl2))
    (lambda ()
      (let ((expr (read)))
        (if (eqv? expr ':a)
            'done
            (let ((val (arc-eval expr)))
              (write (ac-denil val))
              (namespace-set-variable-value! '_that val)
              (namespace-set-variable-value! '_thatexpr expr)
              (newline)
              (tl2)))))))
The arguments to on-err are an error procedure and the body procedure. The error procedure is executed if the main procedure encounters an exeception, similar to a try/catch block, but with the catch procedure first. The on-err procedure is implemented with continuations. If you're looking for the "mind-expanding" parts of Lisp, continuations will definitely interest you, but I will ignore on-err for now.

The meat is the second lambda function. The Scheme read procedure reads the input and creates an object using the Scheme parser. The input is passed to arc-eval, which evaluates the input as an Arc form. The result is converted by arc-denil from the internal 'nil-terminated form to displayable form and written out. The tl2 procedure then calls itself; to the C programmer, this may look like a stack overflow waiting to happen. However, Scheme is tail-recursive so the stack doesn't grow, and the call acts like a simple loop. The Scheme variables _that and _thatexpr record the expression to help debugging.

arc-eval and ac

The arc-eval procedure is the main entry point for executing an Arc form. It calls ac to convert the Arc form to a quoted Scheme form, and then does an eval on the Scheme expression:
(define (arc-eval expr)
  (eval (ac expr '()) (interaction-environment)))
The arc-eval procedure can be executed directly from inside Scheme:
> (arc-eval '((fn (x) (+ x 1)) 42))
43
The ac procedure is the real meat of Arc, as it translates Arc to Scheme. Its second argument is the "environment", a list of symbols that are currently bound. At the REPL, this list is empty.
(define (ac s env)
  (cond ((string? s) (string-copy s))  ; to avoid immutable strings
        ((literal? s) s)
        ((eqv? s 'nil) (list 'quote 'nil))
        ((ssyntax? s) (ac (expand-ssyntax s) env))
        ((symbol? s) (ac-var-ref s env))
        ((ssyntax? (xcar s)) (ac (cons (expand-ssyntax (car s)) (cdr s)) env))
        ((eq? (xcar s) 'quote) (list 'quote (ac-niltree (cadr s))))
        ((eq? (xcar s) 'quasiquote) (ac-qq (cadr s) env))
        ((eq? (xcar s) 'if) (ac-if (cdr s) env))
        ((eq? (xcar s) 'fn) (ac-fn (cadr s) (cddr s) env))
        ((eq? (xcar s) 'set) (ac-set (cdr s) env))
        ((pair? s) (ac-call (car s) (cdr s) env))
        (#t (err "Bad object in expression" s))))
Arc strings are copied to Scheme strings. Arc literals are unchanged. The Arc symbol 'nil is unchanged. Input with ssyntax (i.e. : or ~) is expanded and re-evaluated. Symbols are handled by ac-var-ref. Special operators quote, quasiquote, if, fn, and set are handled by separate procedures. Procedures are handled by ac-call.

xdef

Arc primitives are created with xdef, which enters a Scheme procedure into the namespace:
(define (xdef a b)
  (namespace-set-variable-value! (ac-global-name a) b)
  b)
For example, the Arc newstring procedure is just the Scheme make-string procedure:
(xdef 'newstring make-string)
Note that namespace-set-variable-value! is somewhat similar to define, except it takes a symbol such as 'a, rather than a variable such as a.

Conclusion

Many more interesting aspects of the Arc implementation remain, such as procedures, scoping, and macros. I hope to do more analysis later. Much of the above is based on discussions in the Arc forum. The code snippets from the Arc distribution are copyright Paul Graham and Robert Morris; the distribution is available at http://arclanguage.org/install.