domingo, 5 de julio de 2009

keep plaiyng (part 2). End of chapter 3

I've finally found the time to finish chapter 3 of PLAI.

For the moment, the book has introduced only a couple of basic concepts on programming languages, but the fact that's being done all in scheme, gives some cool insights to how variables and basic operations are handled. It's a pretty different approach to the 'classical' one I was taught @ university, where they based everything on c-like languages, and the lexing, parsing and evaluating (compiling there) was done through flex, yacc, and pure c.

The only tricky part of this chapter is getting how to do the parsing and substituting of local vars and fine tunning the scope of those local vars. It's similar to scheme's 'let'.

As we seen in my previous post about PLAI, The basic process of interpreting our pseudo-scheme is based on 3 parts.
define-type: This function allows us to define the different types of elements (primitives, with, and so) in a high abstraction level, just defining the keywords and which elements must have each definition. While defining the WAE structure, we defined num, add, sub and with, all with their structure, and it creates boolean functions called WAE?, add?, sub?...

For example, we can test if a given sexp 'evaluates' to an add:

(add? (add (num 3) (num 2))) ; -> true

parse: This is the process that takes the input, and has to do the sintactical transformations, to make it calc-friendly. This function has to be modified by the 'user' of the book. For the moment, it's been pretty easy to do.

calc: Here is where most action happens. This function is the one which takes an imput (parse's output) and converts it back to scheme, to do the arithmetic (in + and -) or applies substitution on with blocks. Uses the type-case function, so its input has to be coherent with the define-type declared avobe.
(type-case WAE an-ae
(num (n) n)
(add (l r) (+ (calc l) (calc r)))
here we see an example of what happens with plain numbers, and 'add'. Given a num, that has one parameter, we just return a number. If the expression we enter is an 'add' one, we just apply recursively the calc function to its args , and finally, we evaluate the (+ arg1 arg2) sexp.

subst: If we encounter a 'with' in the calc function, we have to substitute all subsequent bound-ids to the value of the evaluated bind-expression (with except when we find a nested with binding the same variable id).

This allows us to do things like:
{with {x {+4 3}} {with {y x} y} } ; 7
or even
{with {x {+4 3}} {with {x {+ x 3}} x}} ;10
Well, I think it's enough for now. When I come back from San Fermín party, I'll continue with chapter 4, which introduces the implementation of simple functions.

Thank you for listenning :)

As always, comments, suggestions, kisses, insults... welcome :)