Einführung
AST
Der abstrakte Syntaxbaum (AST), auch quotierter Ausdruck genannt, ist eine Möglichkeit, Code als Daten darzustellen.
Jeder Knoten im AST ist ein Tupel mit drei Elementen.
# AST representation of:
# 2 + 3
{:+, [], [2, 3]}
Das erste Element, ein Atom, ist die Operation. Das zweite Element, eine Schlüsselwortliste, sind die Metadaten. Das dritte Element ist eine Liste von Argumenten, die weitere Knoten enthält. Literale Werte wie Ganzzahlen, Atome und Strings werden im AST als sie selbst dargestellt und nicht als Tupel mit drei Elementen.
Code in ASTs umwandeln
Elixir-Code in ASTs umzuwandeln und ASTs wieder zurück in Code ist Teil der Standardbibliothek. Funktionen für die Arbeit mit ASTs findest du in den Modulen Code (z. B. um einen String mit Code in einen AST umzuwandeln) und Macro (z. B. um den AST zu durchlaufen oder ihn in einen String umzuwandeln).
Beachte, dass alle Funktionen der Standardbibliothek den Namen „quoted“ verwenden, um den AST zu bezeichnen (kurz für quotierter Ausdruck).
Die Spezialform, mit der du Code in einen AST umwandelst, heißt quote. Sie nimmt einen Block entgegen und gibt dessen AST zurück.
quote do
2 + 3 - 1
end
# => {:-, [], [
# {:+, [], [2, 3]},
# 1
# ]}
Anwendungsfälle
Die Fähigkeit, Code als AST darzustellen, ist der Kern der Metaprogrammierung in Elixir. Makros, also die Möglichkeit, Elixir-Code zu schreiben, der Elixir-Code erzeugt, funktionieren, indem sie ASTs als Ergebnis liefern.
Ein weiterer Anwendungsfall für ASTs ist die statische Codeanalyse, etwa durch das eigene Tool Analyzer von Exercism, das du vielleicht schon als den kleinen Bot kennst, der Kommentare zu deinen Lösungen hinterlässt.
Anleitung
Du bist Teil einer Task Force, die gegen Wirtschaftsspionage kämpft. Du hast eine geheime Informantin bei Shady Company X, von der du vermutest, dass sie Geheimnisse von ihren Konkurrenten stiehlt.
Deine Informantin, Agent Ex, ist Elixir-Entwicklerin. Sie verschlüsselt geheime Nachrichten in ihrem Code.
Um ihre geheimen Nachrichten zu entschlüsseln:
- Nimm alle Funktionen (öffentliche und private) in der Reihenfolge, in der sie definiert sind.
- Nimm von jeder Funktion die ersten
n Zeichen ihres Namens, wobei n die Arity der Funktion ist.
1. Code in Daten umwandeln
Implementiere die Funktion TopSecret.to_ast/1. Sie soll einen String mit Elixir-Code entgegennehmen und dessen AST zurückgeben.
TopSecret.to_ast("div(4, 3)")
# => {:div, [line: 1], [4, 3]}
2. Einen einzelnen AST-Knoten parsen
Implementiere die Funktion TopSecret.decode_secret_message_part/2. Sie soll einen AST-Knoten und einen Akkumulator für die geheime Nachricht (eine Liste) entgegennehmen. Sie soll ein Tupel zurückgeben, dessen erstes Element der unveränderte AST-Knoten und dessen zweites Element der Akkumulator ist.
Wenn die Operation des AST-Knotens eine Funktion definiert (def oder defp), stelle den Funktionsnamen (in einen String umgewandelt) dem Akkumulator voran. Wenn die Operation etwas anderes ist, gib den Akkumulator unverändert zurück.
ast_node = TopSecret.to_ast("defp cat(a, b, c), do: nil")
TopSecret.decode_secret_message_part(ast_node, ["day"])
# => {ast_node, ["cat", "day"]}
ast_node = TopSecret.to_ast("10 + 3")
TopSecret.decode_secret_message_part(ast_node, ["day"])
# => {ast_node, ["day"]}
Diese Funktion muss keine rekursiven Aufrufe machen, um den gesamten AST zu prüfen, sondern nur den gegebenen Knoten. Den gesamten AST durchlaufen wir im letzten Schritt mit eingebauten Werkzeugen.
3. Den Teil der geheimen Nachricht aus einer Funktionsdefinition dekodieren
Erweitere die Funktion TopSecret.decode_secret_message_part/2. Wenn die Operation im AST-Knoten eine Funktion definiert, gib nicht den ganzen Funktionsnamen zurück. Prüfe stattdessen die Arity der Funktion. Gib dann nur die ersten n Zeichen des Namens zurück, wobei n die Arity ist.
ast_node = TopSecret.to_ast("defp cat(a, b), do: nil")
TopSecret.decode_secret_message_part(ast_node, ["day"])
# => {ast_node, ["ca", "day"]}
ast_node = TopSecret.to_ast("defp cat(), do: nil")
TopSecret.decode_secret_message_part(ast_node, ["day"])
# => {ast_node, ["", "day"]}
4. Die Dekodierung für Funktionen mit Guards korrigieren
Erweitere die Funktion TopSecret.decode_secret_message_part/2. Stelle sicher, dass der Name und die Arity der Funktion für Funktionsdefinitionen mit Guards korrekt erkannt werden.
ast_node = TopSecret.to_ast("defp cat(a, b) when is_nil(a), do: nil")
TopSecret.decode_secret_message_part(ast_node, ["day"])
# => {ast_node, ["ca", "day"]}
5. Die vollständige geheime Nachricht dekodieren
Implementiere die Funktion TopSecret.decode_secret_message/1. Sie soll einen String mit Elixir-Code entgegennehmen und die geheime Nachricht als String zurückgeben, dekodiert aus allen im Code gefundenen Funktionsdefinitionen. Achte darauf, die in den vorherigen Schritten definierten Funktionen wiederzuverwenden.
code = """
defmodule MyCalendar do
def busy?(date, time) do
Date.day_of_week(date) != 7 and
time.hour in 10..16
end
def yesterday?(date) do
Date.diff(Date.utc_today, date)
end
end
"""
TopSecret.decode_secret_message(code)
# => "buy"
Lernübung
