Imp Language Tutorial
Imp views programs as sequences of words. These word sequences may come from the keyboard (e.g.: in an interactive session), from files (or other i/o streams), or from structures in memory. Each word is interpreted in sequential order. Any effect the word has is accomplished before the next word is interpreted. Each word is interpreted in the context of any changes caused by the interpretation of preceeding words. The context consists of the value stack and the dictionary (a map from word-symbols to actions).
Imp supports concurrency. Some words initiate activity the may proceed independently of the process that started it. Many of the traditional problems that can occur in concurrent programs are avoided because Imp does not share mutable state between processes.
In general, the language is a sequence of tokens separated by whitespace. Tokens consisting of digits are converted to numeric literals. A numeric literal is executed by pushing itself on the stack. Other tokens are treated as word symbols. A word symbol is executed by looking up its value in the dictionary and executing the value found. If that value is a list, then the elements of the list are executed in sequence, as if they were encountered directly.
The parser implements two exceptions
to the simple whitespace-separated-tokens rule.
Both involve the # character.
If a word symbol begins with a # character,
the rest of the symbol is pushed on the stack
as a symbolic literal value.
The # prefix is actually treated as if
the rest of the symbol was preceeded
by the word quote,
which pushes any token following it
onto the stack as a literal value.
If the # character is encountered
while parsing whitespace,
and it is followed by whitespace,
it is treated as the beginning of a comment.
The comment ends at the next end-of-line character,
and the entire sequence as simply treated as whitespace.
[comments are planned by not yet implemented -Dale]
Here is a transcript of a simple interaction with Imp.
Text like this represents what you type
(with the special symbol ↲
representing the "Enter" or "Return" key).
Text like this represents output from Imp.
3 4 ?↲ 3 4 add ?↲ 7 5 mul .↲ 35
Imp code samples:
#clear [ depth 0 eq? not [ drop clear ] if ] def↲ #pstack [ depth 0 eq? [ #-top- . ] [ depth roll . pstack ] ifelse ] def↲ 1 2 3 [ pstack ] spawn 1000 sleep ?↲ 1 2 3 -top- 1 2 3 clear ?↲ depth .↲ 0 #splice [ empty? [ drop ] [ pop swap splice ] ifelse ] def↲ -1 0 [ 1 2 3 ] splice ?↲ ... 0 1 2 3 mul add . ?↲ 7 -1 0 eq? .↲ false 1 [ dup 5 eq? [ . ] [ dup . 1 add self send ] ifelse ] actor ?↲ send 3000 sleep ?↲ 1 2 3 4 5 #count-down [ -1 add dup 0 lt? not [ dup . count-down ] if ] def↲ 3 count-down↲ 3 2 1 0
Some pre-defined words could be defined in terms of other words. The choice of which to make primitive is a matter of performance optimization and, of course, avoiding circularity.
#dup [ 1 index ] def
#swap [ 2 roll ] def
#over [ 2 index ] def
#r3 [ 3 roll ] def
#i3 [ 3 index ] def
#r4 [ 4 roll ] def
#i4 [ 4 index ] def
#literal [ nil swap push #quote push ] def
#( [ #( ] def
#(...) [ swap dup #( eq? [ drop ] [ push (...) ] ifelse ] def
#) [ nil (...) ] def
#empty? [ dup nil eq? ] def
#true [ 0 0 eq? ] def
#false [ true not ] def
#if [ [ ] ifelse ] def
#gt? [ swap lt? ] def
#not [ [ false ] [ true ] ifelse ] def
#or [ not swap not and not ] def
#or [ [ drop true ] if ] def
#and [ not swap not or not ] def
#and [ not [ drop false ] if ] def
#nor [ or not ] def
#nand [ and not ] def
#xor [ over over or r3 r3 nand and ] def
#xor [ [ not ] if ] def
#test-logic [
false false i3 exec .
false true i3 exec .
true false i3 exec .
true true i3 exec .
.
] def
#neg [ -1 mul ] def
#sub [ neg add ] def
#inc [ 1 add ] def
#dec [ -1 add ] def
#zero? [ 0 eq? ] def
#divmod [
0 [
i4 i4 lt?
[ drop swap drop swap ]
[ r4 i4 sub r4 r4 inc r4 dup exec ]
ifelse
] dup exec
] def
Let's trace the execution of 3 5 divmod
3 5 divmod
3 5 divmod
3 5 divmod
3 5 0 […] dup exec
3 5 0 […] dup exec
3 5 0 […] dup exec
3 5 0 […] […] exec
3 5 0 […] i4 i4 lt? […] […] ifelse
3 5 0 […] 3 i4 lt? […] […] ifelse
3 5 0 […] 3 5 lt? […] […] ifelse
3 5 0 […] true […] […] ifelse
3 5 0 […] true […] […] ifelse
3 5 0 […] true […] […] ifelse
3 5 0 […] drop swap drop swap
3 5 0 swap drop swap
3 0 5 drop swap
3 0 swap
0 3 result: 0 and 3/5
Compare with the execution of 5 3 divmod
5 3 divmod
5 3 divmod
5 3 divmod
5 3 0 […] dup exec
5 3 0 […] dup exec
5 3 0 […] dup exec
5 3 0 […] […] exec
5 3 0 […] i4 i4 lt? […] […] ifelse
5 3 0 […] 5 i4 lt? […] […] ifelse
5 3 0 […] 5 3 lt? […] […] ifelse
5 3 0 […] false […] […] ifelse
5 3 0 […] false […] […] ifelse
5 3 0 […] false […] […] ifelse
5 3 0 […] r4 i4 sub r4 r4 inc r4 dup exec
3 0 […] 5 i4 sub r4 r4 inc r4 dup exec
3 0 […] 5 3 sub r4 r4 inc r4 dup exec
3 0 […] 2 r4 r4 inc r4 dup exec
0 […] 2 3 r4 inc r4 dup exec
[…] 2 3 0 inc r4 dup exec
[…] 2 3 1 r4 dup exec
2 3 1 […] dup exec
2 3 1 […] […] exec
2 3 1 […] i4 i4 lt? […] […] ifelse
2 3 1 […] 2 i4 lt? […] […] ifelse
2 3 1 […] 2 3 lt? […] […] ifelse
2 3 1 […] true […] […] ifelse
2 3 1 […] true […] […] ifelse
2 3 1 […] true […] […] ifelse
2 3 1 […] drop swap drop swap
2 3 1 swap drop swap
2 1 3 drop swap
2 1 swap
1 2 result: 1 and 2/3
This example shows how we can build a list of evaluated, rather than quoted, elements.
#r3 [ 3 roll ] def↲
#( [ #( ] def↲
#) [
nil [
r3 dup #( eq?
[ drop drop ]
[ r3 swap push swap dup exec ]
ifelse
] dup exec
] def↲
#a [ 1 ] def↲
#b [ 2 ] def↲
#c [ 3 ] def↲
( a b c )↲
( a b c )
( a b c )
( 1 b c )
( 1 2 c )
( 1 2 3 )
( 1 2 3 nil […] dup exec
( 1 2 3 nil […] dup exec
( 1 2 3 nil […] dup exec
( 1 2 3 nil […] […] exec
( 1 2 3 nil […] r3 dup #( eq? […] […] ifelse
( 1 2 nil […] 3 dup #( eq? […] […] ifelse
( 1 2 nil […] 3 3 #( eq? […] […] ifelse
( 1 2 nil […] 3 3 ( eq? […] […] ifelse
( 1 2 nil […] 3 false […] […] ifelse
( 1 2 nil […] 3 false […] […] ifelse
( 1 2 nil […] 3 false […] […] ifelse
( 1 2 nil […] 3 r3 swap push swap dup exec
( 1 2 […] 3 nil swap push swap dup exec
( 1 2 […] nil 3 push swap dup exec
( 1 2 […] [ 3 ] swap dup exec
( 1 2 [ 3 ] […] dup exec
( 1 2 [ 3 ] […] […] exec
( 1 2 [ 3 ] […] r3 dup #( eq? […] […] ifelse
( 1 [ 3 ] […] 2 dup #( eq? […] […] ifelse
( 1 [ 3 ] […] 2 2 #( eq? […] […] ifelse
( 1 [ 3 ] […] 2 2 ( eq? […] […] ifelse
( 1 [ 3 ] […] 2 false […] […] ifelse
( 1 [ 3 ] […] 2 false […] […] ifelse
( 1 [ 3 ] […] 2 false […] […] ifelse
( 1 [ 3 ] […] 2 r3 swap push swap dup exec
( 1 […] 2 [ 3 ] swap push swap dup exec
( 1 […] [ 3 ] 2 push swap dup exec
( 1 […] [ 2 3 ] swap dup exec
( 1 [ 2 3 ] […] dup exec
( 1 [ 2 3 ] […] […] exec
( 1 [ 2 3 ] […] r3 dup #( eq? […] […] ifelse
( [ 2 3 ] […] 1 dup #( eq? […] […] ifelse
( [ 2 3 ] […] 1 1 #( eq? […] […] ifelse
( [ 2 3 ] […] 1 1 ( eq? […] […] ifelse
( [ 2 3 ] […] 1 false […] […] ifelse
( [ 2 3 ] […] 1 false […] […] ifelse
( [ 2 3 ] […] 1 false […] […] ifelse
( [ 2 3 ] […] 1 r3 swap push swap dup exec
( […] 1 [ 2 3 ] swap push swap dup exec
( […] [ 2 3 ] 1 push swap dup exec
( […] [ 1 2 3 ] swap dup exec
( [ 1 2 3 ] […] dup exec
( [ 1 2 3 ] […] […] exec
( [ 1 2 3 ] […] r3 dup #( eq? […] […] ifelse
[ 1 2 3 ] […] ( dup #( eq? […] […] ifelse
[ 1 2 3 ] […] ( ( #( eq? […] […] ifelse
[ 1 2 3 ] […] ( ( ( eq? […] […] ifelse
[ 1 2 3 ] […] ( true […] […] ifelse
[ 1 2 3 ] […] ( true […] […] ifelse
[ 1 2 3 ] […] ( true […] […] ifelse
[ 1 2 3 ] […] ( drop drop
[ 1 2 3 ] […] drop
[ 1 2 3 ] result: the list [ 1 2 3 ] as a single value on the stack
[ 1 2 3 ] ?↲
[...] [...] eq? .↲
true
Let's define a word called repeat
that takes a procedure and a count
and executes the procedure
the number of times specified by the count.
We want the word to have
a stack effect like this:
| −3 | −2 | −1 | Word | +1 | +2 | +3 | Description |
|---|---|---|---|---|---|---|---|
| any | n | repeat | perform n executions of any |
repeat is:
#repeat [ dup 0 gt? [ dec 2 index exec repeat ] [ drop drop ] ifelse ] defThis implementation requires that the procedure leaves the stack in the same state that it found it.
