Home > Java, Lisp, Scheme > Scheme interpreter extension

Scheme interpreter extension

I’ve spent one more day on extending my Scheme interpreter. I’ve added booleans, cond, list, length, -, = , so now it is quite capable. For example, now I can write a recursive function which will calculate sum of numbers starting from 1 up to provided number. Internally code was refactored quite a bit, except of ListTools, which remained exactly the same. I’ve also made a tracing facility, which was surprisingly easy to implement.
Very important discovery for me is that now I understand Scheme language much better. It’s a general rule: to use something effectively you should understand how it works. Implementation and description are the same.
Now I want to summarize my results so far. Scheme interpreter consists of two parts: REPL (which includes reader and result printer) and Evaluator. Reader invokes ListParser, which parses user’s input presented as sequence of characters into list structure, so elements of list could be character strings or other lists. Then result of parsing is passed to evaluator. Evaluator evaluates all items in top-level list, and returns list of result values, which are printed by result printer. If error occurs in ListParser or Evaluator, it is also printed.
Since Evaluator is provided with representation of user’s input, it can distinguish raw symbolic data and lists. Raw symbolic data are evaluated by checking if they are numeric, symbolic or boolean literals, and if not they are considered variable names and their values is looked up in environments. Lists are first checked to be special syntax forms (like define, cond, lambda), and if not, then first item is evaluated. If first item is a procedure, then arguments are evaluated and then procedure body is evaluated.
I think that simplicity of language itself and it’s implementation comes from two things: simple syntax and dynamic nature.
Now I use ArrayList to represent lists. I can implement cons, but it will not provide true sharing, it will make copies instead. But users will see no difference until set-car! and set-cdr! are implemented. Later I will implement cons sells, and will make List implementation based on them.
Making Scheme in Java is a simple task, because both languages have garbage collection. I’m afraid that implementation in Z80 assembler will be more diffucult.

Categories: Java, Lisp, Scheme
  1. December 20, 2007 at 6:35 am

    I would like to see a continuation of the topic

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: