Arc Forum | Toy lisp interpreter in lua

Arc Forum

3 points by meric 5427 days ago | 18 comments

url: http://code.google.com/p/paren/ I don't know if this is legal because I've copied some error messages from arc.

I decided to learn lisp after stumbling reading about Blub, and mentions of it by lecturers. After the horrible SLIME and tedius 1.5 chapters in the SICP scheme book, I've figured I could make the learning more interesting implementing lisp myself. (I'm still haven't even mastered vim yet)

One thing I immediately dislike about lisp (like most others I suppose) was the insane number of parens I had to type. I tolerated the parens around the + - / * operators but the ones around var/cond lists in let and cond was just too much.

I poked around the internets and found Arc. It's probably not merely a coincidence that one of its authors is the one who wrote about Blub, and seeing that it has less parens than the other two lisps, I decided I'll write an interpreter for this one as it answered my earlier concerns well.

I know lua very well, so naturally it is written in lua.

It can only read in the first 3 macro definitions in arc.arc and call only the first one properly. (`do`).

To make it work the next step is to implement disp, sref and sig. (I've no clue what the last two are, probably why I am stopping). I don't think I'll continue it because I feel there isn't point (for me) to do more than just the base primitives, compared to the time it will take me.

Implemented tokens: . ' ` , ,@ + - * / t nil car cdr cons fn if eval len type assign annotate type rep is bound

Macros are also implemented, but not `mac`. A function tagged 'mac is a macro, as in arc. It only has an repl and can't read file but that should be easy to fix. It also keeps on trying to evaluate an expression even after an error is detected so it might crash if there is an error in the input code.

I'm posting it so the next time someone, if any, wants to write a lua interpreter for arc they could find bits of the code useful. Personally I doubt it, but it feels better than just leaving it forgotten on my hard disk. I look forward to when arc becomes big enough that I'll use it, but before then I'll continue to program in lua as my hobby.

My turn to a comment on lisp. Let Blub, y = lisp, tables "How can you get anything done in Blub? It doesn't even have y."

Lua tables are meta-syntactically pumped up and optimized hash tables that can make every data structure possible. It implements arc's tagging in a dozen lines (maybe because lua already has it ;)) I was disappointed when I found out lisp lacks it.

P.S It's annoying that arc's t is reserved, I use t a lot as a temporary variable in other programming languages.

edit: I forgot to mention lualisp http://code.google.com/p/lualisp/ I learnt how to write an interpreter from reading its source code. That said, it think its lua is quite hastily written because alot of its functions overlap in, well, functionality.

5 points by aw 5427 days ago | link

It's annoying that arc's t is reserved, I use t a lot as a temporary variable in other programming languages.

Actually Arc's t is not reserved:

  arc> (let t 3 (+ t 4))
  7
  arc> t
  t

t is merely a global variable; and you're free to make a local variable which happens to have the same name as a global variable.

You can do the same with function names, as functions are a global variable which contain an fn:

  arc> (map even '(1 2 3 4))
  (nil t nil t)
  arc> (let map 3 (+ map 4))
  7
  arc> (map even '(1 2 3 4))
  (nil t nil t)

The only place where you'll run into trouble is if you attempt to "call" a local variable that has the same name as a macro:

  arc> (let foo even (foo 4))
  t
  arc> (let each even (each 4))
  Error: "procedure  each: expects at least 2 arguments, given 1: 4"

Here "each" being a macro trumps "each" as a local variable.

My turn to a comment on lisp. Let Blub, y = lisp, tables "How can you get anything done in Blub? It doesn't even have y."

I'm not familiar with Lua's tables, but in general when I've wanted to add something to Arc I've found it easy to do. So if I want to write a program in Arc but Arc doesn't have Y, I implement Y, and then I write my program.

I don't know if this is legal because I've copied some error messages from arc

If you were copying more Arc source than would be covered by fair use, the easiest thing to do would be to simply put your derived version under the same license as Arc, the Perl Foundations's Artistic License 2.0 (http://www.perlfoundation.org/artistic_license_2_0)

You'd want to avoid relicensing the Arc source (or a portion of it) under the MIT License as that license doesn't provide the end-user protections required by the Artistic license in paragraph 4 section c ii.

However I wouldn't worry about a couple of error messages :-)

-----

4 points by fallintothis 5426 days ago | link

t is merely a global variable

Except you can't destructively update it. So it's really more of a global constant. This is an important caveat because it affects locally scoped ts, too.

  arc> (= t 1)
  Error: "Can't rebind t"
  arc> (= nil 1)
  Error: "Can't rebind nil"
  arc> (let t 4 (+ t 1))
  5
  arc> (let t 4 (++ t))
  Error: "Can't rebind t"

I imagine that's what made it seem reserved. You still probably shouldn't name variables t or nil.

-----

2 points by aw 5426 days ago | link

Except you can't destructively update it

Hmm, good point. Since it does no harm to change t when it is a local variable, I'd remove the restriction for that case.

I might even drop the restriction altogether, as it doesn't seem to have much useful purpose. I can break Arc just as badly by rebinding "car" or other variables, so why this particular effort to keep me from hurting myself?

-----

1 point by meric 5426 days ago | link

That doesn't change the fact that I shouldn't use t for anything other than `t`, but good point.

-----

1 point by meric 5426 days ago | link

    Arc doesn't have Y, I implement Y, and then I write my program.

Its a bit long so I put it here: http://pastebin.org/94450 This is how awesome tables are. :) I see how lisps can implement many features... but I can't see how those features could include adding to the syntax...

    However I wouldn't worry about a couple of error messages :-)

Okay I won't. :)

edit: in the pastebin post on line 14, by 'it' I mean 'OO'

-----

2 points by fallintothis 5425 days ago | link

I see how lisps can implement many features... but I can't see how those features could include adding to the syntax...

Actually, that's an interesting feature of several Lisps: reader macros. For example, in Arc you can make anonymous single-argument functions with some special syntax.

  arc> [+ _ 1]
  #<procedure>
  arc> ([+ _ 1] 1)
  2

In Common Lisp, you are resigned to the more verbose

  [1]> (lambda (x) (+ x 1))
  #<FUNCTION :LAMBDA (X) (+ X 1)>
  [2]> ((lambda (x) (+ x 1)) 1)
  2

What if we want the bracket syntax in Common Lisp? We can extend the parser to dispatch on certain characters, hence "reader macros":

  (set-macro-character #\] (get-macro-character #\)))

  (set-macro-character #\[
                       #'(lambda (stream char)
                           `(lambda (_) ,(read-delimited-list #\] stream t))))

Now when Common Lisp sees an open bracket, it will read from the stream until a closing bracket is found, then shove that all into a (lambda (_) (...)) form.

  [3]> [+ _ 1]
  #<FUNCTION :LAMBDA (_) (+ _ 1)>
  [4]> ([+ _ 1] 1)
  2

Arc doesn't have reader macros (though uses Scheme's for bracket functions; see brackets.scm), but they're an interesting way to work in new syntax (though it probably won't be much fancier than Lisp's already-minimal syntax).

Arc does, however, extend syntax in certain ways. I gave an overview of this so-dubbed ssyntax in another post: http://arclanguage.org/item?id=11179.

This is how awesome tables are.

1. Arc doesn't have destructuring assignment built in, though macros make it easy (see http://arclanguage.org/item?id=8122; it's a bit old, so set is now called assign). Otherwise, the standard approach is

  arc> (= h (table))
  #hash()
  arc> (= h!a 1 h!b 2 h!c 3)
  3
  arc> h
  #hash((b . 2) (c . 3) (a . 1))

2. In Lua, I gather that

  t = { a = 1, b = 2, c = 3 }

is the same as

  t = { ["a"] = 1, ["b"] = 2, ["c"] = 3 }

In Arc, this looks more like strings versus symbols (a datatype I don't think Lua has). Symbols are simply-compared blobs of text, so you often use them as keys in hash tables (e.g., that's what I did in 1). Macros give you a shortcut for this common case.

  arc> (= h (obj a 1 b 2 c 3))
  #hash((b . 2) (c . 3) (a . 1))

3. obj works by quoting the keys you pass in. Quoting literal data will just return that data, so strings can be used in obj, too.

  arc> (= h (obj "a" 1 "b" 2 "c" 3))
  #hash(("c" . 3) ("a" . 1) ("b" . 2))

4. We can't use ssyntax here as in 1 because of its inherent limitations. But we can still do

  arc> (= h (table))
  #hash()
  arc> (= (h "a") 1 (h "b") 2 (h "c") 3)
  3
  arc> h
  #hash(("c" . 3) ("a" . 1) ("b" . 2))

The standard libraries, e.g string, math, etc are tables. e.g math.sin, math.cos.

I wish Arc even had modules. :) But you could do the same thing, in principle.

  arc> (= math (obj sin sin cos cos tan tan))
  #hash((tan . #<procedure:tan>) (cos . #<procedure:cos>) (sin . #<procedure:sin>))
  arc> (math!sin 3.14)
  0.0015926529164868282

In fact, Arc uses this approach for sig.

  arc> (type sig)
  table
  arc> (sig 'rand-key) ; looks like a fn call, but it's a hash lookup
  (h)
  arc> (n-of 5 (rand-key sig))
  (urlend urform admin-gate caris trues)

Tables can have any value as keys besides strings, that includes functions and even other tables.

I think that goes for hash tables in general: anything that's hashable. ;)

  arc> (def f (x) (+ x 1))
  #<procedure: f>
  arc> (= h (table))
  #hash()
  arc> (= (h f) 5)
  5
  arc> h
  #hash((#<procedure: f> . 5))
  arc> (h f)
  5
  arc> (= h2 (obj a 1 b 2 c 3))
  #hash((b . 2) (c . 3) (a . 1))
  arc> (= (h h2) 'hi)
  hi
  arc> h
  #hash((#<procedure: f> . 5) (#hash((b . 2) (c . 3) (a . 1)) . hi))
  arc> (h h2)
  hi

lua doesn't come with it [OO] by default, but you can implement it with tables in a dozen lines

That's how Arc's "object system" works.

  arc> (deftem object a 1 b 2 c 3)
  ((a #<procedure: gs1820>) (b #<procedure: gs1820>) (c #<procedure: gs1820>))
  arc> (inst 'object 'a 5 'c 10)
  #hash((b . 2) (c . 10) (a . 5))

A table can have a `metatable` (mt).

I think I understand what you're saying (it sounds a lot like Python's operator overloading), but I'd probably need to use Lua to appreciate it.

Here's a linked list created with a table.

Aha. I was expecting this earlier: in Lua, you can use tables to make arrays. It's all pretty unified syntactically, whereas Lisps tend to add functionality with Yet Another Macro (instead of overloading syntax).

  arc> (def array values
         (w/table a (on value values (= (a index) value))))
  #<procedure: array>
  arc> (array 'a 'b 'c)
  #hash((0 . a) (1 . b) (2 . c))
  arc> (array 'a (array 'b (array 'c (array))))
  #hash((0 . a) (1 . #hash((0 . b) (1 . #hash((0 . c) (1 . #hash()))))))

If Arc had reader macros, we could make {...} expand into (array ...). But saying "hey, you could bolt that on with a function" is a bit disingenuous: we're still comparing apples and oranges.

-----

2 points by meric 5425 days ago | link

Okay you got me. Lisp can do all that, too ;). About reader macroes: If arc had them and you really liked the {} syntax, would to write a macro for it? And what if you're writing an arc library, would it collide if other people did something else with their braces?

    (it sounds a lot like Python's operator overloading)

re mt: (+ t t1) would fail because they aren't numbers. But if they overloaded the + operator then it would do something instead. Yes it's like python's op-overload but a bit better because of __index and __newindex.

-----

1 point by fallintothis 5425 days ago | link

Lisp can do all that, too ;)

But it's more important whether a language can do something nicely, which I don't necessarily claim Lisp can. After all, Turing machines can do all that, too. :)

would it collide if other people did something else with their braces?

My guess is: yes, they'd probably clash to no end. I'm not familiar with Common Lisp "in the wild", so I don't really know. http://www.faqs.org/faqs/lisp-faq/part2/section-18.html seems to back me up a little.

You could hypothetically package the reader changes into their own modules so that you'd need to explicitly say which braces you're using, modules keep their changes local, etc. Anyone know of work done on this front?

Yes it's like python's op-overload but a bit better because of __index and __newindex.

So are __index and __newindex roughly like in the following (silly) Python code?

  $ python
  Python 2.5.4 (r254:67916, Jan 24 2010, 12:18:00)
  [GCC 4.4.3] on linux2
  Type "help", "copyright", "credits" or "license" for more information.
  >>> class foo:
  ...     def __init__(self, x):
  ...         self.x = x
  ...     def __getitem__(self, index):
  ...         return self.x + index
  ...     def __setitem__(self, index, value):
  ...         self.y = index + value
  ...
  >>> bar = foo(5)
  >>> bar[10]
  15
  >>> bar[20] = 5
  >>> bar.y
  25

If so, I imagine that overloading table operators in Lua becomes all the more powerful since tables are so ubiquitous. Thanks for the explanations.

-----

1 point by aw 5425 days ago | link

Hmm, giving the job of custom readers to modules strikes me as making implementing both modules and custom readers complicated and difficult; and makes unnecessary impositions on the programmer: I might well want to implement one part of my module using one syntax and another part of my module using a different syntax.

On the other hand I think being able to choose your custom reader by source code file would simple to use, simple to understand, easy to implement, would make it easy to customize your editor or IDE to understand your different syntaxes by file, and means that modules can also be easily implemented as they could do their work entirely after the source code has been read in.

I wonder if modules could be implemented with namespaces? You want to call my function foo which calls my function bar, but you don't necessarily want to have to name it "foo" in your own code and you want to be able to have your own "bar" without breaking my function foo. I'll have to think about that one.

-----

1 point by fallintothis 5424 days ago | link

I wonder if modules could be implemented with namespaces?

I guess I use the words "module" and "namespace" interchangeably. I'm not sure what else "module" ("package", "namespace", sometimes "library" (loosely), etc.) would mean.

What I meant was that, say, you have two files:

a.arc

  (use "braces-for-table.arc")

  (def table-I-really-want ()
    {foo 1 bar 2 baz 3})

b.arc

  (use "braces-for-set-builder-notation.arc")
  (load "a.arc")

  (def set-I-really-want ()
    { (* v v) for v in (vals (table-I-really-want)) })

You wouldn't want a.arc's use of braces for tables to leak into b.arc, which uses braces for set-builder notation (which you further don't want to clobber the braces in the definition of table-I-really-want).

With a fancier module system, you might even have

b.arc

  (qualify "braces-for-set-builder-notation.arc" s)
  (load "a.arc") ; doesn't qualify its braces for tables

  (def set-I-really-want ()
    s{ (* v v) for v in (vals (table-I-really-want)) })

  (def another-table-I-want ()
    {foo 5 bar 10 baz 15})

Though there shouldn't be a reason you couldn't do something like

c.arc

  (use "braces-for-table.arc")

  (def some-table ()
    {x 5 y 10})

  (use "braces-for-set-builder-notation.arc")
  ; braces hereafter are for set-builder notation

  (def some-set ()
    { x for x in (vals sig) })

As Arc lacks a proper module system, you can already see the clobber-some effects of definitions being global/unqualified. APIs leak all over the place:

  arc> (load "sscontract.arc") ; only really needs to provide sscontract
  nil
  arc> (priority #\!) ; but the user gets all of the implementation details!
  1

Similarly, I don't want to load some library and have implementation-detail reader macros polluting the reader. (If the library's specifically for reader macros, then of course that's okay.)

Even some simple public/private control would be nice. I've played around with this in Arc before. E.g.,

  (let localize nil

    (assign localize
            (fn (expr fs)
              (when (caris expr 'def)
                (if (~mem (cadr expr) fs)
                    `(assign ,(cadr expr) (fn ,@(cddr expr)))
                    expr))))

    (mac provide (fs . body)
      (let private (trues [and (caris _ 'def)
                               (~mem (cadr _) fs)
                               (cadr _)]
                          body)
        `(let ,private nil
           ,@(map [localize _ fs] body))))
    )

  arc> (macex1 '(provide (f g)
                  (def f (x) (h (+ x 1)))
                  (def g (x) (+ (h x) 1))
                  (def h (x) (* x x))))
  (let (h) nil
    (def f (x) (h (+ x 1)))
    (def g (x) (+ (h x) 1))
    (assign h (fn (x) (* x x))))

  arc> (def foo () (prn "outer foo") nil)
  #<procedure: foo>
  arc> (provide (bar)
         (def foo () (prn "inner foo") nil)
         (def bar () (prn "bar") (foo)))
  #<procedure: bar> ; note: no redef warning, since def changed to assign
  arc> (bar)
  bar
  inner foo
  nil
  arc> (foo)
  outer foo
  nil

But this particular approach doesn't interact with macros nicely, doesn't let you qualify namespaces, isn't general, etc. So it's really suboptimal.

-----

1 point by aw 5424 days ago | link

I guess I use the words "module" and "namespace" interchangeably.

By "namespace", I was thinking specifically of MzScheme namespaces, which is where global variables live.

But like you say that doesn't help with macros, so to answer my own question: no, I don't think namespaces are enough to implement modules...

-----

1 point by meric 5425 days ago | link

blushes Yes, like that. Now I feel like when I program in lua I do so in an ivory tower.

    Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
    > t_mt =  { __index = function(self, k)
    >>         return self.x + k
    >>     end,
    >>     __newindex = function(self, k, v)
    >>         self.y = k + v
    >>     end }
    > 
    > function foo(x)
    >>     return setmetatable({x = x, y = 0}, t_mt)
    >> end
    > 
    > bar = foo(5)
    > print(bar[10]) --> 15
    15
    > 
    > bar[20] = 5
    > print(bar.y) --> 25
    25

-----

1 point by fallintothis 5424 days ago | link

  return setmetatable({x = x, y = 0}, t_mt)

I find this line really interesting. If I'm reading it right, you can alter the metatable (operator overloading) on the fly? So you could pass in a table as a parameter, set a metatable, play with some operators, then set a different metatable to overload operators differently?

In Python, the operators are kind of tied to specific classes. I guess you can go about casting and converting and inheriting and monkeypatching and such, but I don't think it's as straightforward as just setting a new metatable. Admittedly, I can't think of when I've ever needed to alter operator-overloading dynamically like that, so I've never really tried. Do you know if it's useful in Lua code? Or am I completely off-base here?

-----

1 point by meric 5424 days ago | link

Hmm, the only times I've used it as where I'd be casting objects in other languages... I've used it to 'cast' between 'tables' doing similar things. like `my1.rect` to `my2.rect`, if they both use .x, .y, .width and .height to store their coordinates. (Not sure that's a good practice because they can change.) Yes, you can alter metatables any time, but I don't do it that often.

-----

1 point by aw 5425 days ago | link

but I can't see how those features could include adding to the syntax...

I'm not sure if this is what you mean, but if you want to create your own syntax, one option is to use http://awwx.ws/extend-readtable0. What this does is allow you to specify a particular character that you want to trigger a call to your own parser. When the reader sees that character, it calls your parser, which reads your syntax from the input and returns the Arc value that you want your syntax to generate.

For example, here's a simple syntax parser for literal tables (from http://awwx.ws/table-rw3):

  (def parse-table-items (port (o acc (table)))
    (scheme.skip-whitespace port)
    (if (is (peekc port) #\})
         (do (readc port) acc)
         (with (k (read port)
                v (read port))
           (= (acc k) v)
           (parse-table-items port acc))))

  (extend-readtable #\{ parse-table-items)

The example above returns a table value, but you can also return a list, which can then be expanded as a macro:

  arc> (extend-readtable #\@ (fn (port) `(at ,(read port))))
  #<void>
  arc> (read "@3")
  (at 3)
  arc> (mac at (v) `(+ ,v 1))
  #(tagged mac #<procedure: at>)
  arc> @3
  4

-----

2 points by fallintothis 5427 days ago | link

You mentioned not knowing what sref and sig are, so FYI:

sref is "set reference". It's used for indexed assignment.

  arc> (= xs '(a b c))
  (a b c)
  arc> (sref xs 'd 0)
  d
  arc> xs
  (d b c)

sig is a global hashtable where function signatures are stored.

  arc> (sig 'map1)
  (f xs)
  arc> (def f (a b c) (+ a b c))
  #<procedure: f>
  arc> (sig 'f)
  (a b c)

There's more Arc documentation at http://arcfn.com/doc/index.html.

-----

1 point by pmarin 5427 days ago | link

I am also writting my own toy lisp: Muddy Scheme in Tcl. I am planning to implement R4RS and to add all the feactures of Arc (without continuations and with different thread model). I want to try if is possible to have one interpreter with two modes scm/arc, only changing the eval functions and special forms.

Of course It is too slow for real use, It is just a learning tool (I even had to learn how to do the mark and sweep garbage collector).

The code (use only the gc2 branch): http://github.com/pmarin/Muddy-Scheme/tree/gc2

-----

1 point by meric 5426 days ago | link

"This interpreter tries to follow the awesome "Scheme from Scratch" articles written by Peter Michaux." I learnt alot from his code too! I thought about doing some thing like "implement R4RS" eventually but figured I should learn a bit more about lisp first. I think its possible to do scm/arc together.. I'm not sure you even need to change the eval function...

-----