read


read
or learn more

Map As Homoiconic Basis

Jul 23, 2009

While throwing out the idea in the title as a Twitter post, I was surprised at the seeming interest. Therefore, in hopes to open up a discussion, here is how I would envision a programming language homoiconic on maps. (note: Slava Pestov of Factor fame provided a link to a language named Misc that implements this idea in some way, but having not looked at it yet any similarities are incidental)

I have been turning these ideas over in my mind for a while, and actually started toward an implementation named Jaka, but any such implementation has to wait its turn in my ever-deepening queue.

Things to note:
{}
map literal syntax
()
tuple literal syntax
||
set literal syntax
[]
list literal syntax
foo
a symbol
“foo”
a string
foo => bar
a pair
:.
a block (similar to progn)
=
bind
~
merge
<~
merge bind
?
property query
foo(42)
symbol followed by a tuple is a function call
foo.fun()
call a method
foo fun()
call a method
$
similar to this or self
foo {}
function followed by map is same as foo({})
foo:.
function followed by a block is same as foo(:.)

[sourcecode lang=”js” gist=”153045″] def foo = {} // start with an empty map foo.n = 42 // put a property foo.z = 0
foo?n // does foo have property n? foo.n // lookup property n

def bar = {|| => [print(“Hello Cleveland”)]} bar() // prints Hello Cleveland bar.|| // returns [print("Hello Cleveland")] bar?() // accepts zero args? bar.||.first() // returns the symbol print

def baz = {|| => [print($.n)]} baz() // returns notset baz.n = 138 // sets property n baz() // prints 138

def qux = {||=> baz.||} // grab function body qux() // returns object notset qux <~ foo // foo has n qux() // prints 42 qux.n = baz.n // set qux.n to baz.n qux() // prints 138 qux <~ {|x| => [
print($.n – x) // merge arity1 fun ]} qux(100) // prints 38

qux <~ {|x| => [
{|y| => [x + y]} ]} // merge arity1 fun

def frob = {} frob <~ { || => [print(“arity0”)] |x| => [print(“arity1”)] |x y| => [print(“arity2”)] } frob() // prints “arity0” frob(2) // prints “arity1” frob(3 4) // prints “arity2”

def add2 = qux(2)
add2 // Lexical closure add2.|_| // returns list [$.x + y] add2?x // false – x is closed add2(10) // returns 12

/** Multimethods **/ def mm = multimethod // prototypal defmulti object mm.on // default dispatch function mm.on // {|| => [.class]} mm.on?Object // has a method for Object? true mm.on.Object // {|| => []} mm.on.Object = method {|| => [.str()]} mm(42) // returns “42” mm.on.Number = method {|| => [ + 2)]} mm(10) // returns 12 mm([1 2]) // returns “[1 2]” mm.on.List = method {|_| => _.length()} mm([1 2]) // returns 2 [/sourcecode]

Thoughts?

-m

8 Comments, Comment or Ping

  1. Not sure why this is homoiconic – since you don’t provide any examples showcasing how to work with code. To be honest, I’m not sure what a map-based representation of code would look like.

    The code above is more or less a simple prototype based language.

  2. Johan Lindberg

    Having looked very briefly at Misc, as you mention in the post, it doesn’t seem to use maps very well for the code part of “code as data”.

    Don’t know why anyone would ever want to write [0:+ 1:3 2:4] instead of [+ 3 4] (see http://will.thimbleby.net/misc/help.php?page=2) or what the keys in the mapping would be used for.

    Sure, introspection by numbers might be easier to read than car/cdr combinations but still… the only place I can think of where it would feel really usable is in conditionals but there (see http://will.thimbleby.net/misc/help.php?page=12) it seems to use ‘then’ and ‘else’ as the only(?) possible keys instead of having a more ‘case’-based approach which seems to fit quite naturally.

    It’s an interesting thought though, sadly I can’t think of anything it would be “better” at (than lists) but I’m waiting (and hoping) to be amazed.

  3. @olabini: Fair point; but the precursor to homoiconicity is of course code as data. I definitely left it open for interpretation how one might work with the code and also completely ignored a macro system (which would most-certainly be required). I plead innocence based on this only being the seed of an idea. ;) However, given the brief description above, it is imaginable how such a language might facilitate meta-circular evaluation given that each language element is a data element.

    -m

  4. Well, sure. But there is nothing that says code is data in the examples either – and if code is data, it doesn’t say anything about that representation as being map-driven.

    Which goes back to my original point, I’m not sure if it even makes sense to represent code as maps, and I certainly can’t imagine what it would look like – and you have no content in this blog post about it either.

    In fact, I would say that the above code examples are definitely not represented with maps – since maps are unordered and the code above depends on being sequenced.

  5. Ola is right, the language given in the article does not appear to be homoiconic at all. However, the following could be a simple map-oriented, homoiconic functional language (I hope this “example” is reasonably clear):

    { call:letrec name:fac    ;; cheaters way of avoiding fixpoint
      value:{ call:def args:args
        body:{ call:if cond:{ call:<= x:args[x] y:1 }
          then:1
          else:{ call:* 
            0:args[x] 
            1:{ call:fac x:{ call:- 0:args[x] 1:1 } } } } } }

    Obviously, all of this could have been more elegantly accomplished using Lisp. That’s because I’m not really exploiting the map data structure in any way. Also, I suspect that maps aren’t as ideally suited to lambda calculus as are lists. It deserves some thought…

  6. Upon further reflection, here’s an example of a somewhat more consistent homoiconic language based on maps. Well, maybe not more consistent, but certainly more sane:

    {
      weird-fac:fac[ x:0 ]:0      ;; factorial where fac(0) = 0
      
      fac:{                       ;; simple factorial
        { x:0 }:1
        
        args:if[
          cond:<[ left:args[x] right:0 ]
          then:fac[ x:0 ]
          else:*[
            0:args[x]
            1:fac[
              x:-[ 0:args[x] 1:1 ]
            ] 
          ]
        ]
      }
    }
    
    do[
      0:print[ str:"Enter a number: " ]
      1:let[ num:readLine[]
        body:println[
          str:format[ str:"Factorial of %d is %d" 0:num 1:fac[ x:num ] ]
        ]
      ]
    ]

    The weird-fac “function” demonstrates remapping existing values. So, weird-fac is equal to the fac map with the x:0 key remapped to the 0 value. Map keys can themselves be maps, values or symbols. Function calls (if you can give it that term) are done by dereferencing the “function” map based on its key. In the case of a function, that key is most often a map itself, but it can of course be a value as well.

    It’s just an idea, but I think you get the picture.

  7. @djspiewak

    Thank you for the thoughtful posts. You’ve definitely elaborated on my sugared examples. I tried to make a more readable version, but you’ve captured a more homoiconic illustration. I would be interesting to take these thoughts further, I only hope that time allows me to do so.

    -m

  8. @olabini

    In fact, I would say that the above code examples are definitely not represented with maps – since maps are unordered and the code above depends on being sequenced.

    Small point of contention; the maps above are listed in order, but only for clarity’s sake. There is no reason to think that they would need to be.

    -m

Reply to “Map As Homoiconic Basis”