If at first you don't succeed...

About | Archive

\(\newcommand{\th}{^\mathrm{th}}\) \(\newcommand{\false}{\mathrm{F}}\) \(\newcommand{\true}{\mathrm{T}}\)

Dictp Part 1

So, a friend and I (I’m going to protect his anonymity in case he doesn’t want to be associated with the travesty that is what we ended up thinking up) were discussing ridiculous ideas for programming languages: you know the deal, writing C interpreters in Python, using only integers to represent everything, etc.

One idea, however, seemed a little less ridiculous to us (OK, just to me): a language in which there are two data types: Dictionary and String.

Everything is a dictionary

Every dictionary has keys which are dictionaries and values which are dictionaries. Lists are just a special case of dictionary:

[a, b, c]
    == {'__len__' : '3', '0' : a, '1' : b, '2' : c}

And strings are just a special case of lists:

'Hello'
    == ['H', 'e', 'l', 'l', 'o']
    == {'__len__' : '5', '0' : 'H', '1' : 'e', '2' : 'l', '3' : 'l', '4', 'o'}

Integers, floating points, etc. are just special cases of strings, and objects are just special cases of dictionaries, where keys are attribute names and values are their values. In fact, the current environment is merely a dictionary of the current bindings and a parent frame.

Functions are themselves just dictionaries. For example, add is a dictionary which maps list of number inputs to a numeric output:

plus[['2','3']] == '5'

Types of Dictionaries

There are two basic types of dictionary.

  • Discrete and strictly finite. e.g., Strings. These dictionaries need no special marker.
  • Continuous and lazy, potentially infinite. e.g., functions. These dictionaries contain the mapping __lazy__ : 'True'

Language built-ins

The empty dictionary

An empty dictionary is built by using the directive __empty__. It produces a dictionary containing no keys and no values. __empty__ itself is not a dictionary, it is merely replaced by the call to generate a new dictionary and use it in that context.

Strings

Strings are built according to python string conventions. They can be represented with single or double quotes; both "this" and 'this' should work. It contains the key __len__ which maps to the length of the string as well as keys 0, 1, 2… up till one less than the value of __len__.

Contains

<dictionary>[<key>]? outputs 'True' if the dictionary contains the key and 'False' otherwise. Note that this does not check parent frames (see “Get”)

Nonlocal directive

By convention, the dictionary {'__nonlocal__' : 'True'} is referred to as a “Nonlocal Directive”.

Get

<dictionary>[<key>] outputs the key associated with the given value. If the key is not in the dictionary or if it is associated with a nonlocal directive, it checks for a __parent__ and looks it up there. If there is no __parent__, it raises a KeyError which results in the halting of the given code.

Put

<dictionary>[<key>] = <value> associates the given key with the given value in the given dictionary. This does not check parent frames unless the given key is associated with a nonlocal directive, in which case it does. If there is no error, it raises a KeyError. It’s value is the empty dictionary.

Local

__local__ is the local frame, it can be discrete or continuous (see __call__ for how this case can come to pass).

If

__if__[<condition>][<ifso>][<ifelse>] evaluates the condition in the local environment, then conditionally evaluates the ifso and ifelse programs (text).

Call

__call__ is a higher-order dictionary that takes a sequence of lines of code (with the key __program__) and an environment (__env__) and outputs a continuous dictionary mapping input dictionaries to the result of executing the program on the given frame with the parent frame forced to be the given parent frame. The result is defined as the value of the last statement.

An Example

__local__['factorial'] = __empty__
__local__['factorial']['__program__']
    = '__if__ \
            [__local__["=="] \
                [__local__["n"]] \
                ["0"]] \
            ["\"1\""] \
            ["__local__[\"*\"] \
                [__local__[\"n\"]] \
                [__local__[\"factorial\"] \
                    [__local__[\"-\"] \
                        [__local__[\"n\"]] \
                        [\"1\"]]]"]'
__local__['factorial']['__env__'] = __local__
__local__['factorial'] = __call__[__local__['factorial']]
__local__['four'] = __empty__
__local__['four']['n'] = '4'
__local__['toprint'] = __empty__
__local__['toprint']['__toprint__']
    = __local__['factorial'][__local__['four']]
__local__['print'][__local__['toprint']]
# ^ Should print 24, given that "print" is defined

OK, so nothing beautiful. Hopefully, in a future post, we can look at sugaring and turning this into a practical language.

comments powered by Disqus