Skip to content
3 May 32012 / Robin Wellner

Déjà Vu Grew a Pair

Another Déjà Vu post. If you don’t care about the design and implementation of programming languages, this post is not for you.

Anyway, now that I’ve lost the good majority of my readership, I’d like to talk about types.

In Déjà Vu, there used to be 6 types:

  • Strings
  • Idents (symbols would probably have been a better and more familiar name)
  • Numbers
  • Lists
  • Dictionaries
  • Functions

And now I’ve added a 7th: pairs. A pair is similar to a two-element tuple in Python or to a cons cell in Lisp. You can create a pair by calling &, like this:

& "hi" "there"

print &< dup # prints the first element
print &>     # prints the second element

Big deal, right? We already have lists. Anything pairs can do, lists can do better. Lists can do anything better than you. Erm… than pairs.

The thing is, pairs are still useful. Pairs are immutable. Pairs can hold only elements of simple types (strings, idents, numbers and other pairs). These two things mean that a pair can never be a part of a reference cycle, which means they don’t have to be garbage collected. Objects of a simple type are only reference counted, which is better performance-wise and memory wise.

Pairs are small too: except for the minimum amount of data a Value has to have (16 bytes), it only has to hold two pointers to the other Values. Pairs are small and easy on the GC, which means you can create heaps of them for a low price.

I already used them for a number of purposes, among them lightweight binary trees and Lisp-style lists.

Here’s a function that is basically the equivalent of map for pair-based trees:

treemap f:
	if = :pair type dup:
		treemap @f &> dup
		treemap @f &< swap

. treemap @++ & & 0 10 & & & 5 7 -2 & 0 0
# prints      & & 1 11 & & & 6 8 -1 & 1 1

For larger literal trees, the syntax can get rather hard to read. The nature of Déjà Vu makes that a bit hard to fix, unfortunately.

Anyway, that’s it.



Leave a Comment
  1. davisdude / Jul 8 2013 19:55

    How did you go about making your own programming language? Did you follow a specific tutorial or did you just figure it out? I’ve always been curious as to how one would go about making a programming language, and was hoping you could mitigate my curiosity.

    • Robin Wellner / Aug 26 2013 23:08

      Sorry that it took me this long to approve your comment.

      To answer your question, I spent a lot of time trying to make programming languages. The road from initial concept to fully functioning implementation is fairly long, and most attempts failed sooner rather than later, but every attempt I learned something new. Reading articles about the implementation of other languages, especially Python and Lua, helped too.

      Programming languages look like deep magic to the unintiated, but in actuality most of it is really simple once you understand the general concepts.

      • davisdude / Aug 28 2013 4:05

        That’s alright.
        I’ll have to look in to the documentation. Thanks!

Leave a Reply

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

You are commenting using your 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: