See Format about what these are meant for. Christian hasn't solved all of these exercises himself (yet); that should be consistent with the aim for them to get you thinking and for discussion: we might tackle one or the other together. If he asks participants to solve a particular exercise alone, he will first do so himself.
Work out suggestions for VML to which to translate the following example:
(define (f x y)
(/ (* 10 (- x y)) y))
(define (g x y)
(- (f x y) (* x y)))
Write a program in Scheme that interprets P′′ (which is a subset of Brainfuck with a slightly different syntax).
No need to write a string parser (unless you like the challenge), just use S-expressions to represent the P′′ (or Brainfuck) programs, choosing to make them look similar enough. E.g. you could use the symbol r*
instead of r'
.
Write a program (in Scheme) that interprets expressions in Reverse Polish notation. This expression language understands constants (numbers) and "words" (operators), as well as "programs" (unevaluated expressions, as first class values). It also has a value stack to put results to and take arguments from. In its basic form it doesn't have variables, the only names are predefined words.
As with the exercise above, rely on Scheme's parser (read
, or the repl or file loader) to read expressions.
Make it evaluate simple arithmetic expressions like 5 1 2 + 4 * + 3 -
(this one resulting in 14
). This requires the words +
, -
, *
(and why not also /
) to be implemented.
Implement the dup
word, which creates a duplicate of the last value on the value stack: evaluation of the program 1 2 dup
should give a stack ending in 1 2 2
. (Here, the convention of printing the element that was put onto the stack last also as the last item on the line is used. You don't need to follow this convention when pretty-printing the stack from your language implementation.) Or, 3 dup *
would give 9
.
Extend it with a way for users to define words from within the defined language. What's the minimal syntactical language extension (as opposed to just adding new word definitions) necessary to achieve it? (If you think its use is too cumbersome, feel free to also add an alternative form to define words (syntactic sugar).) Implement square
using the implemented language.
Implement linked lists. This will require cons
, car
, cdr
, pair?
and null?
as primitives (adding a boolean data type to the language for the latter two). Implement an if
primitive, taking a boolean, and "yes" and "no" programs from the stack (name it something else if you don't want confusion with the "if" syntax from Forth.)
Implement map
from within the implemented language. You will need more stack access/manipulation operations (like swap
, drop
, over
, pick
, rot
, roll
, perhaps others, see Forth stack operators), as well as eval
to trigger evaluation of a program. There are two approaches to implementing map (also when doing the same in Scheme), one requiring a bit more code than the other.
Optional: implement a program (written either in that language, or probably rather in Scheme) that translates a subset of Scheme to that language. Or, if you prefer, one that translates programs in that language to Scheme.
Implement an SECD machine in Scheme.
(Useful for S3C.) Write a function string.C-identifier
that maps any Scheme symbol string to a corresponding valid C identifier name string that doesn't clash with the string mapped from any other Scheme symbol. Note that Scheme symbols can actually contain any unicode character (if they are quoted using ||). Write test(s) that show(s) that there are no clashes. (Optional: also write proof(s) to show the same.) Plus: write the function in a way that generates nicely human-readable C identifier equivalents to common naming conventions in Scheme (or S3C) identifiers (like using the characters '-' to join name parts, '*' at the end for name alternatives, '?' for predicates, '.' for 'fully qualified method names', ':' for type classification, '!' for those consuming arguments, '@' for unsafe, '#' for fully qualifying with namespace, upper/lowercase characters, (also '*', '/', '+', '-' in arithmetic ops, although these will be prefixed with types like int32:*
since S3C won't use C's generic arithmetic)).
Note: this may need some libraries that are to be written as part of the S3C effort (or the SICP course (logic programming)), so don't despair or spend too much time if you don't get this solved yet.