?

Log in

icfp: 2d language - Tobin's Lab Notebook [entries|archive|friends|userinfo]
Tobin Fricke's Lab Notebook

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

icfp: 2d language [Aug. 13th, 2006|08:01 pm]
Tobin Fricke's Lab Notebook
[Tags|]

We log into ohmega's account and we find a specification, an interpreter, and a couple of problem statements for a perverse programming language called 2d, in which programs are drawn out as "ASCII art" flowcharts. Hilariously the specification explains, "This language frees the programmer from the shackles of linear programming by allowing programs to occupy two dimensions. However, unlike 3- and 4- dimensional languages like CUBOL and Hypercard, it does not distract the programmer's attention with needless dimensional abandon." The flowchart describes not just the data flow, but also the control flow of a program, because boxes aren't evaluated until all of their inputs have values.

The specification for 2d is available on Wikipedia.

I found it useful to first write my programs in Scheme, and then translate them into 2d. For example, here's a function that concatenates two lists, written first in Scheme and then in 2d:

(define (append listA listB)
  (if (empty? listA)
      listB
      (cons (car listA)
            (append (cdr listA) listB))))

The same program, implemented in 2d:

       ,..........................|........................................,
       :append                    |                                        :
       :                          v                                        :
       :                     *==================*                          :
       :                     !send [(N,S),(N,E)]!-----+                    :
       :                     *==================*     |                    :
       :                          |                   v                    :
       :   *=============*        |            *============*              :
       --->!case W of S,E!--------#----------->!send [(N,E)]!---------------
       :   *=============*        |            *============*              :
       :      |                   |                                        :
       :      v                   v                                        :        
       :   *=======*         *==========*                                  :
       :   !split N!-------->!use append!------------+                     :
       :   *=======*         *==========*            |                     :
       :      |                                      v                     :
       :      |                                *====================*      :
       :      +------------------------------->!send [(Inl (W,N),E)]!-------
       :                                       *====================*      :
       ,...................................................................,  
LinkReply

Comments:
[User Picture]From: nibot
2006-08-14 06:01 am (UTC)

reverse

Here's my solution for reverse:

       ,..........................|........................................,
       :append                    |                                        :
       :                          v                                        :
       :                     *==================*                          :
       :                     !send [(N,S),(N,E)]!-----+                    :
       :                     *==================*     |                    :
       :                          |                   v                    :
       :   *=============*        |            *============*              :
       --->!case W of S,E!--------#----------->!send [(N,E)]!---------------
       :   *=============*        |            *============*              :
       :      |                   |                                        :
       :      v                   v                                        :
       :   *=======*         *==========*                                  :
       :   !split N!-------->!use append!------------+                     :
       :   *=======*         *==========*            |                     :
       :      |                                      v                     :
       :      |                                *====================*      :
       :      +------------------------------->!send [(Inl (W,N),E)]!-------
       :                                       *====================*      :
       ,...................................................................,

       ,......|............................................................,
       :rev   |                                                            :
       :      v                                                            :
       :   *=============*                     *================*          :
       :   !case N of S,E!-------------------->!send [(Inr W,E)]!-----------
       :   *=============*                     *================*          :
       :      |                                                            :
       :      |         +-------+                +-------+                 :
       :      |         |       |                |       |                 :
       :      v         |       v                |       v                 :
       :   *=======*    |    *=======*           |   *==========*          :
       :   !split N!----+    !use rev!-----------#-->!use append!-----------
       :   *=======*         *=======*           |   *==========*          :
       :      |                                  |                         :
       :      |  *===========================*   |                         :
       :      +->!send [(Inl (W, Inr ()), E)]!---+                         :
       :         *===========================*                             :
       ,...................................................................,

Again, it's modeled on Scheme code:

(define (append listA listB)
  (if (null? listA)
      listB
      (cons (car listA)
            (append (cdr listA) listB))))

(define (reverse x)
  (if (null? x)
      x
      (append (reverse (cdr x))
              (list (car x)))))

More points are given for smaller solutions, where the size of a solution is computed as its area (again, hilarious)! So this solution could be doubtlessly by improved substantially.

(Reply) (Thread)
[User Picture]From: nibot
2006-08-14 06:20 am (UTC)

multiply

The problem statement:

Let me make a challenge: I've attached an implementation of addition for unary numbers (0 is represented as Inr (), 1 as Inl(Inr ()), 2 as Inl(Inl(Inr ())) and so on) in 2D. See if you can write a module called "mult" (you can even use my "plus" module) whose output is the product of its north and west inputs. The first one to send me a correct solution gets a package of gobstoppers!

Scheme implementation:

(define (decrement x)  (cdr x))
(define (add x y) (append x y))

(define (multiply x y)
  (if (null? x)
      x
      (add (multiply (decrement x) y) 
           y)))

2d implementation:

       ,..............................|....................................,
       :mult                          |                                    :
       :  *=============*             |                *=================* :
       -->!case W of S,E!-------------#--------------->!send [(Inr (),E)]!--
       :  *=============*             |                *=================* :
       :         |                    |                                    :
       :         |                    v                                    :
       :         |                 *==================*                    :
       :         |                 !send [(N,E),(N,S)]!----+               :
       :         |                 *==================*    |               :
       :         |                        |                |               :
       :         |                        v                v               :
       :         |                 *========*          *========*          :
       :         +---------------->!use mult!--------->!use plus!-----------
       :                           *========*          *========*          :
       ,...................................................................,
(Reply) (Thread)
From: evan
2006-08-14 06:35 am (UTC)
Clearly, the hax0ry thing to do is make a program that generates 2d output.
(My partner also just wrote the programs by hand, I think.
(Reply) (Thread)
[User Picture]From: nibot
2006-08-14 07:34 am (UTC)
And as a spin-off, we'd have an ASCII-art backend to graphviz!
(Reply) (Parent) (Thread)
From: evan
2006-08-14 10:16 am (UTC)
I thought of that (you could maybe use graphviz to do the note layout) but I don't think you can tell it to respect ordering constraints ("node a must be the the left of node b").
(Reply) (Parent) (Thread)
[User Picture]From: nibot
2006-08-14 07:44 pm (UTC)
In this post the author alleges that [s]he wrote a sort of Lisp-to-2d compiler: http://schani.wordpress.com/2006/07/24/the-icfp-programming-contest-2006/
(Reply) (Parent) (Thread)
[User Picture]From: nibot
2006-08-14 07:46 pm (UTC)
Syndicated as schani_rss.
(Reply) (Parent) (Thread)