User:Fizzie

From Esolang
Jump to navigation Jump to search

Articles sort-of under construction, perhaps.

This is work-in-progress, please don't point and laugh.

This sentence will change after every MediaWiki upgrade: MediaWiki 1.38.4 post-upgrade edit test.

This sentence was changed to test the CAPTCHA.

Grasp

This content is outdated and replaced by a real Grasp page. I will remove this later. Honest.

Grasp is a graph-oriented esolang; there are far too few of them so far. Designed (if you can call it that) by User:Fizzie.

The main concept in Grasp is that the code is stored as (multi-field) nodes in a (directed) graph, and there are graph-manipulation operations provided. It is this mostly superficial similarity to Lisp (w.r.t. the "code and data both are lists" thing) that was an inspiration for the name. (It's short for "GRAphS are being Processed".)

Program structure

A Grasp program consists of a set of nodes. Each node has the following set of fields, named vaguely after their common purpose in operations. Each field also has a fixed type, given in parentheses after the field name; the types will be explained later. In many cases, not all fields of the node will be used for anything meaningful.

  • name (symbol): a mostly descriptive label for the node in question. Also used to make subroutine calls less likely to cause horrible edge cluttering in the graph.
  • command (symbol): what the action will be if this node is traversed by the IP.
  • next (pointer): where the IP will go next after this node.
  • in (pointer): usually points to where the primary argument for the command can be found.
  • out (pointer): usually points to where the command result will be put.
  • extra (pointer): an additional pointer value; can be used to store constant pointers, or as a second input argument for the command.
  • value (int): integer-valued field, used to store data in.
  • sym (symbol): used for commands that take a symbol argument (see call).
  • cond (pointer): used for conditional execution.

The data types are:

  • int: an integer, with a range of at least [-2^31 .. 2^31-1]. Can be a bignum if you want.
  • pointer: a graph edge, capable of pointing at another node, or at a particular field inside a node.
  • symbol: interned string, used for label and command names.

More complicated data types can be built from nodes. In particular, strings are represented by singly (or doubly, if you want) linked list of nodes, chained with their next pointers.

Execution and instruction set

In a running Grasp program, there is a list of instruction pointers (IPs). Each IP points to a particular node, and also has a stack that can store both int and pointer values. At each tick, the list of IPs is processed, in order. During the processing, each IP first does whatever the command field of the node it is pointing at says, and then follows the pointer in the next field of that node. If the next field is null, the IP is removed from the list.

If the cond field of the current node points to an integer-valued field, the command will only be executed if the field value is nonzero. Similarly, for pointer-valued fields the command will be executed if the field value is not null.

At start, the IP list contains a single IP pointing at the node named "main". It is an error if such a node does not exist. Execution terminates if the IP list becomes empty.

General-purpose commands:

  • set: a very versatile command. Takes whatever is in the field pointed by the in pointer, and stuffs it into whatever is pointed by the out pointer. Do note that this instruction can therefore manipulate the control flow, since you can alter the next pointers. Dereferencing pointers is also generally handled by setting the in field of some other set node.
  • member: converts node pointers to field pointers. The in argument should point to a node pointer value; the sym field must be one of the defined field names; the node pointer will be converted to a pointer to that particular field of the node, and written to where out points.
  • new: adds a new node to the graph. A pointer to the newly allocated node is written to where out points. The fields of the new node will be mostly empty.
  • delete: removes a node from the graph. The in field should point to a value that's a node pointer; the pointed-to node will be removed. All pointers referring to it revert to null. (You don't need to explicitly delete nodes that fall out of reachability, though.)

Stack manipulation:

  • push: put what in points at to this IP's stack.
  • pop: remove the topmost item in this IP's stack, and put it to whatever out points at.
  • pick: in points to the stack depth (0 == top); write that value (without removing it from the stack) to where out points at.

Subroutine helpers:

  • call: push pointer to itself on the stack; find a node with name matching the sym field of this node, alter IP to point at it; put the value pointed by in of the calling node into value/extra/sym of the called node (depending on type); the out field is used by the ret command.
  • ret: pop a node pointer from the stack, set IP to point at it; put the value pointed by in of the returning node into what's pointed by out of where the IP now points.

Arithmetics:

  • add: read the values pointed by in and extra, write the result to where out points.
  • sub, mul, div, mod: ditto.

IO:

  • getc: read a single character; in must be null (read from stdin) or point to a file handle value, out gives the place where the character will be stored at. On EOF, -1 will be read.
  • putc: write a single character; out must be null (write to stdout) or point to a file handle value, in gives the place where the character will be read from.
  • gets: read a line of text; a pointer to a newly allocated linked-list-string will be written to out.
  • puts: write a string; in should point to the first node in a linked-list-string.

Example programs and snippets

In the hand-drawn examples, underlined text are name field contents, first item (discounting a possible underlined name) is the command, the small square with "N" in it is the next field, and the rest have their names specified. Pointer values are indicated by graph edges starting from the field edge; non-pointer values (or null pointers) are given as "name: value" inside the field. ∅ denotes a null pointer.

cat

Grasp examples cat.jpg

The first node (named "loop"; should be "main") reads a single character, and stores it to the value field of itself. The second node does +1 so that EOF (-1) value would become zero. Third node clears the next field of the fourth node; "by default", execution terminates here. The fourth node tests the +1'd value; if it's nonzero (not at EOF), the node sets its own next pointer to the fifth node. Finally, the fifth node writes out the original value and loops back.

manual subroutine call

Grasp examples call.jpg

Here's how you could do a manual subroutine call; it might be useful for "dynamic" calls, since the call/ret pair can only handle named nodes. It's not very thread-safe, though; you could do something more like the call/ret sequence for that.

The push node stores the old return address (from foo-ret:next) into the calling IP's stack. The set node modifies foo-ret to return to the pop node; then the IP will follow the next pointer to foo. Finally, after returning from foo-ret, the pop node restores the previous return address.

string append routine

Grasp examples append.jpg

A subroutine for appending two linked-list-strings. I'm attempting to construct a BrainFuck interpreter; this thing will be used for reading the BrainFuck source with multiple gets calls.

Usage: pass as input argument (in of call) a pointer to a node where the next and extra fields point to strings. The latter will be appended (destructively) to the former. The return value (out of call) will be the appended string; to append "in-place", point the out at the next field of the in node.

How it works: well, I guess it's obvious from the image. I mean, it's basically just a flowgraph, right?

Incidentally, in case you feel inclined to criticize the penmanship; consider the alternative, Graphviz:

Grasp examples append graphviz.png